Welcome Guest [Log In] [Register]
Welcome to Crypto. We hope you enjoy your visit.


You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free.


Join our community!


If you're already a member please log in to your account to access all of our features:

Username:   Password:
Add Reply
Hard; A Vigenere Challenge!
Topic Started: Sep 20 2005, 03:08 AM (2,460 Views)
Donald
NSA worthy
[ *  *  *  *  *  * ]
And for those of you ready for a serious challenge, the cipher once thought to be unbreakable by cryptographic science... A Vigenere!

But don't panic folks, it's a very simple one. The alphabets used are not mixed in any way, just Caesar ciphers. The keyword isn't very long, and I've given you a fairly long text to work with. (a literary excerpt from a famous work). And to make it super easy, I've left in the word divisions and punctuation.

This cipher will be vulnerable to all of the attacks I laid out in <this post>. Try probable word dragging, Index of coincidence, and the Kasiski method. The Kasiski method should prove VERY fruitful, there are several repeated sequences, and the word divisions make them very obvious. Also, the word divisions should give you SEVERAL probable word hints.

You might find this applet useful (or not)
http://math.ucsd.edu/~crypto/java/EARLYCIPHERS/Vigenere.html

Good luck!

EWJ OK QF G JBEGEOR ZYQAM, SCG ZYQAMJ BUGK IEK XWBJ KW UGMM NTU LNEJ BUGK IEK XWBJ KW FVVVQ GIM FUFV GUCL NHFCG, GEL AUK UHIY BB RZAGKE BB; CYQYK KPVTXA GNRB NXV CAIFUSUIBNHCM, CGCXVZRBVTX, IAJ VDRT XZHKJWZK, DIL SRSR G XWBJ KIYK, RVQ ZRSR G UMNR FN GKCTVTX IAENIL. -P.I.Z. GUCSVKE
Offline Profile Quote Post Goto Top
 
Guest
Unregistered

kpvy kmkz za rttzlvkmq czbu zym fgdm xkp if zym pnrtykeor, gel hyva gnv ansv iymfzvzyu. queiyj, z'u nliivj z kegtsrj kpvy sg ugel,. oak q jgj i gulku rlkxe, zv gnrb v mlmfyvl gnv ihzywe liwz zym aadjrx fn uoj qaokqnrj, if sp drxp nvxjb fzvx. oktihyv buk bml cra fu jpbxk, buk imfz nif kral. o uqqt'k mike jbzyme czbu ofk bx bifojsv.


Quote Post Goto Top
 
insecure
NSA worthy
[ *  *  *  *  *  * ]
miz, v lfztuk bb rfo vt. jbvrc, q gnzvx efc cxfjnhcg tavafku qg cra zk.
Offline Profile Quote Post Goto Top
 
Donald
NSA worthy
[ *  *  *  *  *  * ]
congratulations guest (Insecure?) Good work! I figured someone would notice that very obvious probable word. :thumbsup:

I'm still working on Insecure's message. Hopefully I'll have time later this evening to work on it.

(I swear I know exactly what the first sentence is, but it's just not working out. I'm outta time, have to work on it later!)
Offline Profile Quote Post Goto Top
 
Donald
NSA worthy
[ *  *  *  *  *  * ]
Ha! Got that last message finally Insecure! Yes, you are correct, I did guess! :) And I'm a moron, I must have been half asleep the other day because I did my probable word check wrong or I would have decrypted your message right then.

A clarification of the probable word technique for others, just so you don't make the same stupid mistake I did!

Let's encrypt DOG with the key word CAT

Code:
 

key=CAT
pln=dog
crp=FOZ


So we have the code word FOZ and we think it might be "dog". To recover the key we DECRYPT the crypt text using the plain text as the key. So we need the D, O and G alphabets:
Code:
 

___abcdefghijklmnopqrstyvwxyz   <-plain text
D: DEFGHIJKLMNOPQRSTUVWXYZABC  
O: OPQRSTUVWXYZABCDEFGHIJKLMN  
G: GHIJKLMNOPQRSTUVWXYZABCDEF  

FOZ
dog


decrypt F in the D alphabet and get "c"
decrypt O in the O alphabet and get "a"
decrypt Z in the G alphabet and get "t"

Tada, keyword recovered.

So just be clear, decrypt the CRYPT by the PLAIN Do not decrypt the plain by the crypt, do not encrypt either by the other. Just decrypt the crypt by the plain. :)
Offline Profile Quote Post Goto Top
 
rot13
Elite member
[ *  *  *  *  * ]
I have been experimenting with a new way of determining the key on a Vigenere cipher (new to me, anyway). It is essentially the same as making a slide and matching up the letter frequencies, but you don't have to make a slide. I used Index of Coincidence to determine the key length. Next, I counted the letter frequencies at each position. Let me give one for an example (I won't mention the key length or which position it is):

B(8) I(7) M(4) Q(4) W(7) (I only want the really frequent ones, I ignore the rest)

Next, convert these values to numbers, with A=0, B=1, C=2, etc

1 8 12 16 22
B I M Q W

Now, starting with the most frequent letter (B), I look at the distance between it and each of the other frequent letters:

B->I = 8 - 1 = 7
B->M = 12 - 1 = 11
B->Q = 16 - 1 = 15
B->W = 22 - 1 = 21

Now I consult this chart, which lists the distances between the most frequent letters:
Code:
 

   A   E   H   I   N   O   R   S   T
--------------------------------------
A:  0   4   7   8  13  14  17  18  19
E: 22   0   3   4   9  10  13  14  15
H: 19  23   0   1   6   7  10  11  12
I: 18  22  25   0   5   6   9  10  11
N: 13  17  20  21   0   1   4   5   6
O: 12  16  19  20  25   0   3   4   5
R:  9  13  16  17  22  23   0   1   2
S:  8  12  15  16  21  22  25   0   1
T:  7  11  14  15  20  21  24  25   0


What I am looking for is the line that contains most of the numbers 7, 11, 15 and 21. I see that row T has all of them, so that tells me that B probably represents T (then I=A, M=E, Q=I, W=O)

Now, to convert that to the key value is just a little math:
B=T+key
1=19+key (since the key would have to be negative here, just add 26 to B)
27=19+key key = 8, which is I

I applied this method to the other positions and most of them worked well. I had some trouble with the first position, so I had to add in the letters that occurred 4 times, and then I was able to find a likely match. In practice, this method doesn't get every key value, and sometimes you have to try different positions (getting the same key from two different positions is a great indicator). It does seem to recover a decent portion of the key, though.

When you are computing distances between letters, if you are starting from a letter high in the alphabet, like T (19) and going to a lower one, like E (4), where the result (4-19) is negative, you can always add 26 to the first number (30-19) to figure out that E is 11 places to the right of T.
Offline Profile Quote Post Goto Top
 
insecure
NSA worthy
[ *  *  *  *  *  * ]
The proof of the pudding is in the eating. Did your method solve the challenge text?
Offline Profile Quote Post Goto Top
 
rot13
Elite member
[ *  *  *  *  * ]
Yes, although for the first letter I had to add in some additional letters.

RA LUL IYXVIQE BVBC, KPR QVG VY IQAM
Offline Profile Quote Post Goto Top
 
Donald
NSA worthy
[ *  *  *  *  *  * ]
Quote:
 
I have been experimenting with a new way of determining the key on a Vigenere cipher

WOW! What an incredibly cool technique you've come up with here! Thanks for sharing it, and congrats on solving the Challenge!

And welcome to the board! We are having a lot of fun playing and learning and it's great to add another classical crypto enthusiast to the Forum. :thumbsup:
Offline Profile Quote Post Goto Top
 
Revelation
Member Avatar
Administrator
[ *  *  *  *  * ]
Nice, I have cracked a vigenere cipher :D

SPOILER
**************
NOW IT IS A STRANGE THING, BUT THINGS THAT ARE GOOD TO HAVE AND DAYS THAT ARE GOOD
TO SPEND ARE SOON TOLD ABOUT, AND NOT MUCH TO LISTEN TO; WHILE THINGS THAT ARE
UNCOMFORTABLE, PALPITATING, AND EVEN GRUESOME, MAY MAKE A GOOD TALE, AND TAKE A
DEAL OF TELLING ANYWAY. -J.R.R. TOLKIEN

**************
END SPOILER

I am writing an application that will make the shifting easier. I cracked your code with that app :)
RRRREJMEEEEEPVKLWENFNVJKEEEEEAOLKAFKLXCFZAASDJXZTTTTTTTLSIOWJXMOKLAFJNNKFNXN
RAGRBAQEMHIGDJVDSEOXVIYCELFHWLELJFIENXLRATALSJFSLCYTKLASJDKMHGOVOKAJDNMNUITN
RRRRLJVEEEEECLYVYHNVPFTAEEEEEMWLMEIRNGLARWJAKJDFLWNTIERJMIPQWOTZEOCXKNUBNXCN
RJIRPOWEANFUSNCZVDVZNMSFEKLOEPZLDKDJWSAAAAAAAOERHJCTNCKFRIMVKSOFOMKMANREWNBN
RZUDRGXEEEEENFQIDVLQNCKNEEEEEDGLLLLLLAWIOSNCDARLODMTOEJXMILDFJROTKJSDNLVCZNN
Offline Profile Quote Post Goto Top
 
Donald
NSA worthy
[ *  *  *  *  *  * ]
"Revelation"
 
Nice, I have cracked a vigenere cipher

Cool! And congrats!
Wanna give us a few details as to how your program does it?

Donald
Offline Profile Quote Post Goto Top
 
rot13
Elite member
[ *  *  *  *  * ]
I also have a couple of tools I hacked together to work on ACA cryptograms. One of them is for working the Vigenere class of ciphers (Vigenere, Beaufort, Variant and Porta). They are written in python. I wrote them under Linux, but they should work from Windows as well. They are available here.

The Vigenere solver is vig.py. I just type "python vig.py"

If the cipher is in a file, you can type "load xxxx"
Otherwise, you can type "new" and then enter the cipher.

It has some features that make it pretty trivial to crack a vigenere. First, if you type "ics" it shows you the Index of Coincidence for various key lengths. Usually, the correct key length will really stand out.

The "k" command lets you try a key. If you don't know a position, just use "." in that position. For example, if you think the key is 6 characters long and starts with MA, you can do "MA...."

The really handy command is "score". It needs to have some idea of a key length, so use the k command first, even if you just have to do all dots. Score figures out which key values generate the most SENORITA letters. You can usually get a good stab at the key there.


There is also a tool for cracking monoalphabetic substitutions "python crypto.py"
There are a number of utilities there, including an option for swedish/norwegian/danish for cracking some of the Xenocrypts in The Cryptogram. You use the "m" command to try various substutions. If you think that ciphertext XYZ represents THE, the command is "m xyz the" (I'm a command-line guy, if you couldn't tell). There are other commands that are useful when working on stuff from The Cryptogram.

Also, for both vig.py and crypto.py, if you loaded from a file, or saved a new con to a file, if you type "save", it will store the current solution to <originalfilename>.sol
Offline Profile Quote Post Goto Top
 
Donald
NSA worthy
[ *  *  *  *  *  * ]
Shiny! Thanks! Now I'm downloading Python so I can try it out. :)

Donald
Offline Profile Quote Post Goto Top
 
Revelation
Member Avatar
Administrator
[ *  *  *  *  * ]
In my app, which I am still building, you can shift by pressing the button. If your key has a length of three, there will be three buttons.

@rot13, I am interested in that IOC command.
RRRREJMEEEEEPVKLWENFNVJKEEEEEAOLKAFKLXCFZAASDJXZTTTTTTTLSIOWJXMOKLAFJNNKFNXN
RAGRBAQEMHIGDJVDSEOXVIYCELFHWLELJFIENXLRATALSJFSLCYTKLASJDKMHGOVOKAJDNMNUITN
RRRRLJVEEEEECLYVYHNVPFTAEEEEEMWLMEIRNGLARWJAKJDFLWNTIERJMIPQWOTZEOCXKNUBNXCN
RJIRPOWEANFUSNCZVDVZNMSFEKLOEPZLDKDJWSAAAAAAAOERHJCTNCKFRIMVKSOFOMKMANREWNBN
RZUDRGXEEEEENFQIDVLQNCKNEEEEEDGLLLLLLAWIOSNCDARLODMTOEJXMILDFJROTKJSDNLVCZNN
Offline Profile Quote Post Goto Top
 
rot13
Elite member
[ *  *  *  *  * ]
If you don't know python, it might be a little tough to follow. I took advantage of some pretty handy features. For example, the following function takes a string and a period (key length) and returns an array of strings representing the characters at that position:

Code:
 

def periodic_split(str,period):
   return [str[start::period] for start in range(0,period)]


This works because str[start::period] is a substring of str starting at start and going every period'th character.

I just uploaded my C source for computing IoC for various key lengths. Maybe that might be easier to follow. When it reads in a text file, it converts the letters to numbers in the range 0-25. After that, it's just a matter of counting.
Offline Profile Quote Post Goto Top
 
1 user reading this topic (1 Guest and 0 Anonymous)
Go to Next Page
« Previous Topic · Challenges · Next Topic »
Add Reply