| 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: |
| Announcement: Official Vigenčre Tutorial | |
|---|---|
| Topic Started: Oct 6 2005, 02:30 PM (1,008 Views) | |
| Revelation | Oct 6 2005, 02:30 PM Post #1 |
Administrator
  ![]](http://209.85.122.85/static/1/pip_r.png)
|
Since the major success of Donald's Vigenčre tips, I have decided to make an official one together with you. This will be posted (and pinned) in the General section of Cryptanalysis. I will soon post a first version.
|
|
RRRREJMEEEEEPVKLWENFNVJKEEEEEAOLKAFKLXCFZAASDJXZTTTTTTTLSIOWJXMOKLAFJNNKFNXN RAGRBAQEMHIGDJVDSEOXVIYCELFHWLELJFIENXLRATALSJFSLCYTKLASJDKMHGOVOKAJDNMNUITN RRRRLJVEEEEECLYVYHNVPFTAEEEEEMWLMEIRNGLARWJAKJDFLWNTIERJMIPQWOTZEOCXKNUBNXCN RJIRPOWEANFUSNCZVDVZNMSFEKLOEPZLDKDJWSAAAAAAAOERHJCTNCKFRIMVKSOFOMKMANREWNBN RZUDRGXEEEEENFQIDVLQNCKNEEEEEDGLLLLLLAWIOSNCDARLODMTOEJXMILDFJROTKJSDNLVCZNN | |
 |
 
|
| Revelation | Oct 6 2005, 03:42 PM Post #2 |
|
Administrator
|
Well, this is version one. It contains some background info, but no cracking methods yet. Feel free to edit it and write some more
Source: Wikipedia As said in the quote above, the Vigenčre cipher consists of numerous Caesar ciphers. In a Caesar cipher (shift cipher) the alphabet is shifted by a fixed number. For an example, the plain text ‘gamma’ is shifted by 3: ABCDEFGHIJKLMNOPQRSTUVWXYZ DEFGHIJKLMNOPQRSTUVWXYZABC GAMMA JDPPD The Vigenčre cipher uses shifts too, but the main differences are that the fixed number is a letter and that multiple letters are used. Lets start with the first one. Lets say we want to use letter K for the shift: ABCDEFGHIJKLMNOPQRSTUVWXYZ turns into KLMNOPQRSTUVWXYZABCDEFGHIJ That wasn’t that hard, was it? Now onto the multiple shifts. The fixed numbers (password) shall now be referred to as the key. The key for the next example will be hello.
Now, you can find the right ciphered letter by looking at the offset of your plaintext letter. If this is at position 1, the letter will be replaced by the one with the same alphabetical offset in alphabet H. The letter at position 2 is encrypted with E, etc. So the plain text ‘ape’ with key ‘hello’ would become HTP. If the length of the plain text exceeds the length of the key, the key is repeated. For example:
|
|
RRRREJMEEEEEPVKLWENFNVJKEEEEEAOLKAFKLXCFZAASDJXZTTTTTTTLSIOWJXMOKLAFJNNKFNXN RAGRBAQEMHIGDJVDSEOXVIYCELFHWLELJFIENXLRATALSJFSLCYTKLASJDKMHGOVOKAJDNMNUITN RRRRLJVEEEEECLYVYHNVPFTAEEEEEMWLMEIRNGLARWJAKJDFLWNTIERJMIPQWOTZEOCXKNUBNXCN RJIRPOWEANFUSNCZVDVZNMSFEKLOEPZLDKDJWSAAAAAAAOERHJCTNCKFRIMVKSOFOMKMANREWNBN RZUDRGXEEEEENFQIDVLQNCKNEEEEEDGLLLLLLAWIOSNCDARLODMTOEJXMILDFJROTKJSDNLVCZNN | |
|
|
|
| insecure | Oct 6 2005, 05:44 PM Post #3 |
|
Elite member
|
Just a hint: When columns matter, as with Vigenere for example, use a non-proportional font (e.g. by using code tags). |
|
|
|
| Revelation | Oct 6 2005, 06:39 PM Post #4 |
|
Administrator
|
Well, I used tabs, but they don't seem to work 
|
|
RRRREJMEEEEEPVKLWENFNVJKEEEEEAOLKAFKLXCFZAASDJXZTTTTTTTLSIOWJXMOKLAFJNNKFNXN RAGRBAQEMHIGDJVDSEOXVIYCELFHWLELJFIENXLRATALSJFSLCYTKLASJDKMHGOVOKAJDNMNUITN RRRRLJVEEEEECLYVYHNVPFTAEEEEEMWLMEIRNGLARWJAKJDFLWNTIERJMIPQWOTZEOCXKNUBNXCN RJIRPOWEANFUSNCZVDVZNMSFEKLOEPZLDKDJWSAAAAAAAOERHJCTNCKFRIMVKSOFOMKMANREWNBN RZUDRGXEEEEENFQIDVLQNCKNEEEEEDGLLLLLLAWIOSNCDARLODMTOEJXMILDFJROTKJSDNLVCZNN | |
|
|
|
| PulsarSL | Oct 6 2005, 07:03 PM Post #5 |
|
Super member
|
Yea, tab takes you to the next form. Pulsar |
|
|
|
| Donald | Oct 6 2005, 07:37 PM Post #6 |
|
Elite member
|
Instead of tabs, manually space to make things line up. Like this:
WARNING! for some reason the CODE tag sometimes strips one space off of lines that begin with a space. I haven't figured out why. Just be certain to do a preview before you post. The above text required FOUR spaces before the ABC line in order to get it to line up right. Oh, don't look now, but your Vigenere tutorial is turning into a BBCODE tutorial! Well, while we are off-topic. Any of you using firefox should get the BBCODE extension. It's a wonderful little tool for regular board users. Donald |
|
|
|
| cows | Oct 11 2005, 03:21 PM Post #7 |
|
Unregistered
|
o.K. am i understanding this? If i wanted to type my name would the finished code be:
Or am i getting this wrong? --Edit-- Don't worry i misread the first post. The code would be
No need to panic - sorted it now |
|
|
|
| insecure | Oct 11 2005, 03:31 PM Post #8 |
|
Elite member
|
Donald was talking about cracking a Vigenere, not using one. To use a Vigenere is easy enough. Pick a codeword. Example: NOTASTRONGKEY Remove all duplicate letters: NOTASRGKEY Using a Vigenere square... oh. To construct a Vigenere square, take a square 27 cells by 27 cells in size. Top row, starting at column 2, write the alphabet. Left column, starting at row 2, write the alphabet. Rows 2-27: starting in column 2, continue the alphabet started in column 1, re-starting from A when necessary. Top bit of table looks like this:
and so on. Locate your plaintext letter on the top row. Locate your key letter on the leftmost column. Where that row and column cross, is your ciphertext letter. Move on to next plaintext letter and next key letter (starting at the beginning of the key if you reach the end), and go round again until you run out of plaintext. |
|
|
|
| rot13 | Oct 11 2005, 03:31 PM Post #9 |
|
Elite member
|
If you wanted your name to be the keyword, you pretty much have it:
Then to encrypt a message like "til the cows come home" you encrypt the first letter using the C line, the next letter using the O line, and so on. Here is the message with the line used to encrypt it written below:
so for line C, T is encrypted as V for line O, I is encrypted as W for line W, L is encrypted as H for line S, T is encryptes as L, for line C, H is encrypted as J for line O, E is encrypted as S ...and so forth The final encrypted message, with word breaks preserved, would be: VWH LJS YGYG YGOS DGOS Notice the repeating YGYG YG. That's an interesting thing. With Vigenere, encrypting C with a key of W is the same as encrypting W with a key of C. The word COWS is encrypted with a key of WSCO. So CO with a key of WS encrypts as YG. Likewise, WS with a key of CO also encrypts as YG. |
|
|
|
| sas01 | Dec 31 2005, 05:46 PM Post #10 |
|
Just registered
|
I'm slightly confused :s if I wanted to write my name it would be
Ok that's all easy what I don't understand is this
Can anyone explain to me please? |
|
|
|
| rot13 | Jan 1 2006, 03:26 AM Post #11 |
|
Elite member
|
Okay, first of all, a typical Vigenere cipher only uses letters, so the 01 at the end of your name wouldn't count. Second, Vigenere is done by shifting a regular A-Z alphabet by different positions. To make a key from your name, at least the SAS part, you create three alphabets, the first and last starting with S, wrapping around and finally ending at R. The middle alphabet, since it starts with A would be a regular A-Z alphabet:
Notice that your name appears if you look at the first letter in each row. You have three alphabets to work with. You encode the 1st letter with the first alphabet, the second letter with the second alphabet, the third letter with the third alphabet ,and then the fourth letter goes back to the first alphabet. To encode a letter with the first alphabet, you can write it like this:
So to encrypt a letter, you look on the Plain line to find the letter. The encrypted letter is the one below it. For example, C is encrypted as U, F is encrypted as X, and so on. Now, on your middle alphabet, since it starts with A, the letters aren't really encrypted since A encrypts as A, B as B and so on. Going back to the previous example, the sentence to be encrypted was "TIL THE COWS COME HOME" I wrote "COW SCO WSCO WSCO WSCO" underneath it to indicate which alphabet to use. The alphabet beginning with C works like this:
I said that T is encrypted as V. To get that, I looked at the Plain line, found T, then looked for the letter beneath it, which was V. For the O alphabet, you have:
I want to encrypt I, and I see that W appears under it, so I is encrypted as W. I hope that makes sense. |
|
|
|
| sas01 | Jan 1 2006, 10:31 AM Post #12 |
|
Just registered
|
That makes perfect sense! Thankyou! I can't believe I couldn't figure that out last night lol. Regards sas01 |
|
|
|
| PulsarSL | May 25 2006, 01:27 AM Post #13 |
|
Super member
|
What we need now is a definitive guide to cracking a vigenere using IOC attacks. Pulsar |
|
|
|
| Revelation | May 25 2006, 10:54 AM Post #14 |
|
Administrator
|
Well, most of us know how to do that. You can search the forum for an IOC calculator. When you have downloaded it, let ik check the text and the shift with the highest number (around 6.5) is the keylength. |
|
RRRREJMEEEEEPVKLWENFNVJKEEEEEAOLKAFKLXCFZAASDJXZTTTTTTTLSIOWJXMOKLAFJNNKFNXN RAGRBAQEMHIGDJVDSEOXVIYCELFHWLELJFIENXLRATALSJFSLCYTKLASJDKMHGOVOKAJDNMNUITN RRRRLJVEEEEECLYVYHNVPFTAEEEEEMWLMEIRNGLARWJAKJDFLWNTIERJMIPQWOTZEOCXKNUBNXCN RJIRPOWEANFUSNCZVDVZNMSFEKLOEPZLDKDJWSAAAAAAAOERHJCTNCKFRIMVKSOFOMKMANREWNBN RZUDRGXEEEEENFQIDVLQNCKNEEEEEDGLLLLLLAWIOSNCDARLODMTOEJXMILDFJROTKJSDNLVCZNN | |
|
|
|
| rot13 | May 26 2006, 08:49 PM Post #15 |
|
Elite member
|
Do keep in mind that IOC is useful for determining the key length, but after that, you have to use something else to actually recover the key. In general, you can shift through possible key values and compare the decoded results with the standard frequencies for English. For a Vigenere text of a resonable size, this technique works quite well. For shorter texts it can be a little more difficult and you may have to resort to trial and error, or crib dragging. I have found myself using IOC several times lately and I almost wonder if we need a tutorial in how to use IOC to attack various ciphers. Maybe it will due to just mention what it is good for and what it isn't. IOC tests whether the repetitiveness of a group of items is similar to a known group. The most common example is, do these letters repeat in roughly the same amounts that English does? If letters are about evenly distributed, the IOC is usually in the 0.03 to 0.04 range. For English text it is in the 0.06 to 0.07 range. If there are only a few letters you could see much higher values. The IOC for the raw ADFGVX ciphertext in Loki's challenge is just under 0.2. To compute the IOC (technically, what I am presenting here isn't IOC but the PHI test, but it works out the same), sum f*(f-1) where f is the number of occurrences of each letter. If you have 5 A's, 3 B'2 and 1 C, you add 5*4 + 3*2 + 1*0. You divide this sum by N*(N-1) where N is the total number of letters. Again, with 5 A's, 3 B's and 1 C, that's 9 * 8. So the IOC is 26/72 or about 0.36. To apply IOC to a Vigenere or other periodic cipher, you are basically trying various key lengths and seeing if the IOC of the resulting alphabets is close to English (or whatever language you think the plaintext is in). For a key length of 3, for example, you take letters 1, 4, 7, 10, 13, etc. and compute the IOC. Then you take letters 2,5,8,11,14,etc. and compute the IOC, then take letters 3,6,9,12,15,etc. and compute the IOC. Then you average those 3 IOCs. Next, you do the same procedure for the 4 alphabets generated for a key length of 4, and so forth. The highest IOC probably indicates the right key length, although sometimes multiples of the actual key length may score higher. IOC can also be used for fractionating systems like ADFGVX and straddling checkerboards. For ciphers like these, you are not looking for a key length, but for an equivalent monoalphabetic substitution (i.e. instead of just solving the cipher outright, you convert it into a monoalphabetic substition and THEN solve it). With ADFGVX, a plaintext letter is represented by a pair of letters, and these pairs are broken up and scrambled. If you think you have unscrambled these pairs back into the original representation, you can use IOC to see whether your unscrambling produces text with the same repetition characteristics as English. Likewise, with straddling checkerboard where a letter can be represented by either a single digit or by a 2-digit number, you can try various possibilities for the 2 first digits of the 2-digit numbers, and check the resulting text to see if it has the same repetition characteristics as English. I found with the checkerboard that I often had alphabets with more repetition, so the IOC was higher. Instead of picking the highest, I picked what was closest to 0.066. IOC is typically useless for a monoalphabetic substitution because the IOC of the substituted text is the same as the original. Where in the original you might have 14 E's, the substitution man have 14 Q's, and when that's converted into a number, it makes no difference what the original letter was. IOC on single letters is also pretty useless for a transposition, because the letter frequency should already be about the same as English. For some transpositions, however, it may be useful to compute a digraphic IOC. That is, instead of doing the IOC on the frequency of single letters, you can do it on every pair of letters. It is the same procedure, sum f*(f-1) for all digraphic frequencies (how many AA's, AB's, .. ZZ's) and divide by N*(N-1) the total number of digraphs, which should be the number of letters / 2. For English, that number should be around 0.0069 as opposed to 0.0015 for random text (I get these numbers from Lanaki's Lesson 2 which has a great discussion on IOC. You can also use IOC to help identify ciphers. An issue of The Cryptogram last year had a table with a number of expected test values for various ciphers that included the expected monographic and digraphic IOC's. |
|
|
|
| 1 user reading this topic (1 Guest and 0 Anonymous) | |
| « Previous Topic · News · Next Topic » |
4:38 PM Nov 23
