| Viewing Single Post From: Cracking A Vig With Ic | |
|---|---|
| jdege | May 7 2008, 03:33 AM |
Elite member
  ![]](http://209.85.122.85/static/1/pip_r.png)
|
I was talking about using the Index of Coincidence to break Vigs, and someone asked for an example. Let me start by saying that in my opinion, the most important thing computers can do for us, when we're playing around with hobby crypto, is to create cyphertexts for us, without our having to know which keys were used. So we'll start with a ciphertext, encrypted as a plain Vig, with a keyword length of somewhere between 3 and 10. Let's start with some frequency counts: For a total of 473 letters. Every letter appears, and even the least frequent letters appear with some regularity. This is far flatter a distribution than we'd expect from a mono-alphabet substitution cipher, and the Index of Coincidence should reflect that. The kappa for this ciphertext is calculated from the frequency counts, as follows: We scale this by the kappa of random text, to obtain the Index of Coincidence: Now remember what we expect for an IC. Random text should give us an IC of 1.0. Ordinary English text should give us an IC of 1.7. What we have is an IC of 1.1, which is very near to random text, and exactly what we would expect of Vig using anything other than a very short keyword. So, next we have to find the length of the keyword. First, trying a keyword of length two, we calculate the IC for the even and for the odd letters. The letters with indexes of 0 and 1, mod 2. The average: And we do the same for a keylength of 3: And continue: Our IC peaks where n=9 and again where n=18. Which is what we'd expect for a keyword of length 9. So lets assume a keyword of length 9, and look at the slices. Slice 0 has this frequency count: And a total of 53 letters. Doing a chi-test against a file of english letter frequencies, we get 0.04179. Next is to try shifting. Our chi tests for shifting slice 0 from 0-25: We have a clear peak at a shift of 6, or a keyword value of 'G'. ('A' == 0). Do the same for slice 2: Here, we have a peak at 1, or 'B'. Do the same for slices 3-8: Or a keyword of "GBMHYJUEV". (Which is what I should expect, having used random letters for a keyword, instead of picking some nice, readable word out of a dictionary.) Decrypted with that keyword our message is: If the text is long enough, this almost always works. As it gets shorter, the differences between the chi tests becomes less distinct. I should note, this text is three times as long as the recommended length for Vigs in the ACA. Shorter messages are more challenging, because normal variation can make the statistics less clear, Even in this one, slice 4 nearly had an incorrect peak. The correct shift had a chi of 0.06431 for a "Y", but a shift of 11 had a chi of 0.06069, which would have been an "L". If one or two slices have incorrect shifts, though, the text usually comes through, if you format the decrypted text one line per keyword length: From this, it's obvious that you're on the right track, and that its slice four that is incorrect. |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
 |
|
| Cracking A Vig With Ic · General | |
12:04 AM Nov 26
