| 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: |
- Pages:
- 1
- 2
| Cracking A Vig With Ic | |
|---|---|
| Topic Started: May 7 2008, 03:33 AM (822 Views) | |
| Paarth Dave | May 10 2008, 12:28 PM Post #16 |
|
Advanced Member
  ![]](http://209.85.122.85/static/1/pip_r.png)
|
I am having problems with the chi test. I don't know how to go about it with paper and pencil. |
|
Cryptography Vanquished.... | |
 |
 
|
| jdege | May 10 2008, 01:17 PM Post #17 |
Elite member
|
OK. You have some text, and you want to see if it has a frequency distribution that is similar to that of ordinary English. First, you need a frequency distribution for ordinary English. You can find that all over the web: http://en.wikipedia.org/wiki/Letter_frequencies. It doesn't matter whether these are expressed as percentages, or per thousand, or whatever, because you're going to be dividing by their sum. It's only the ratios that matter.The next thing you need is to add up all the numbers above so as to get a total count. In this case, because our numbers are percentages, we should end up very close ro 100, which we do. These numbers sum to 99.999. Next, we need the text we're testing. For this, we also need a frequency count - a count of how many times each letter appears in the text. And again we need a total - a sum of all the numbers. This time, it's 434. Now we need to multiply the value for A in the standard frequency count by the value for A in our test frequency count, and do the same for B, C, etc.. And when we're done, we need to add up all those products: The final step is to divide this sum - the sum of the products - by the product of the two sums you obtained for the two distributions separately. The next question is what does this tell us? Remember - the IC of random text is 0.0385 and the IC of normal English is 0.0653. The chi test returns values in the same range. A chi of 0.0652 tells us that the distribution of this sample text is almost exactly the same as that of our sample of ordinary English. |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| Paarth Dave | May 10 2008, 02:37 PM Post #18 |
|
Advanced Member
|
Thanks a lot. Now I have understood it perfectly. |
|
Cryptography Vanquished.... | |
|
|
|
| Paarth Dave | May 11 2008, 10:46 AM Post #19 |
|
Advanced Member
|
As you mentioned earlier,
How is the shifting related to the chi test? I am confused yet again! |
|
Cryptography Vanquished.... | |
|
|
|
| jdege | May 11 2008, 03:45 PM Post #20 |
|
Elite member
|
Think about the problem. We have a Vig ciphertext, that was encrypted with a keyword of length nine. That means that the characters 0, 9, 18, 27, ... were encrypted with one caesarshift, 1, 10, 19, 28, ... were encrypted with a second caesarshift, and so on, for a total of nine different caesar shifts. Each Caesar shift is a simple substitution cipher implemented by adding a constant between 0 and 25 to the numeric value of each character in the plaintext. The first thing we need to do to break a Vig is to figure out how long the keyword was. We've done that, with the IC, and found it was nine. The next thing we need to do is to determine the value of each letter of the keyword. Which is to say, we need to find out by how much each slice of the text was shifted. There are nine letters in the keyword, so the text can be divided into nine slices, so that all of the letters in a slice were encrypted with the same letter from the keyword. We take each slice, individually, and do a frequency count, and then use the chi test to measure how similar it is to ordinary text. If that slice was not shifted - which is to say that the letter of the keyword that was used to encrypt that slice was 'A', or 0 - the chi test will have a value of over 0.06. If it's a poor fit, the chi test will have a value below 0.04. So we subtract 1 from each letter in the slice, do a new frequency count, do another chi test comparing it to standard English, and then repeat, until we've done this for every number between 0 and 25. When we're done, we'll have the results of 26 chi tests. And in almost every case, the case in which the chi test returned the highest value will be the one where subtracted the correct amount. If the chi test had the highest result when we were subtracting 6, that means that the letter in the keyword that was used to encrypt this slice was 'G' (A=0, B=1, C=2, D=3, E=4, F=5, G=6). Then we need to do the same thing, for each of the other eight slices. That's 9 slices * 26 chi tests = 234 chi tests. You can see why people invented computers. |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| Paarth Dave | May 13 2008, 08:25 AM Post #21 |
|
Advanced Member
|
Ya..You are right. Is there any shorter way than this to break a Vig manually i.e with paper and pencil? For me, this method is quite tedious but effective also. |
|
Cryptography Vanquished.... | |
|
|
|
| jdege | May 13 2008, 12:41 PM Post #22 |
|
Elite member
|
There are two parts to the problem. Identifying the keylength, and identifying the shifts. I know of two other methods of identifying the keylength. The first is the Kasiski method - you look for repeated ngrams - sequences of characters that appear more than once. You factor the distances between the repeats, and look for common factors. English text contains repeats. When these repeats line up with the key, the repeats will show up in the cipher text.
We have a code-word of length 8, and we have three repeats. MLQ appears at positions 0 and 8, distance 8 ML appears at positions 0, 8, and 16, distances 8 and 8 So we have a keyword of length 8 - or possibly 2 or 4. Normally, you need a lot more text to get enough repeats to be certain, and it's normal to get distances that are multiples of the keyword length. If your keyword length is 7, you might get distances of 14, 21, and 35. 7 is the common denominator. Also keep in mind that you will see occasional accidental repeats, that have nothing to do with the keylength. The other method I've never seen named, but it's mentioned in Schneier's "Applied Cryptography". The idea is to compare the text to itself, shifted by various amounts. When the text is shifted by the length of the keyword, you should see a higher number of matching letters. Schneier talks about subtracting the texts, and looking for zeros. By hand, it's easier to just look for matches. Write out the text on a strip of paper. Then write out the text twice on another strip of paper. Then lne them up, shift one over by one letter, and count how many times the same letter appears on both strips. When you have shifted by the length of the keyword you will see far more matches than you will otherwise.
You expect to see matches in about 6% of the cases when you have the text aligned properly, and in about 4% of the cases when you don't. In this case, you see a lot more, because I intentionally chose the text to have repeats at the keyword length. |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| Donald | May 13 2008, 05:23 PM Post #23 |
|
Elite member
|
jdege listed some other nice attacks. But none of them are actually EASY to do with paper and pencil. Cracking a Vig completely by hand is a nightmare under just about any circumstances. I once did a vig challenge here that left in the word divisions. That actually made the vig relatively easy to crack by hand. Also, if you had a really nice crib, that could make it easy. But for regular old vig, working them completely by hand is certainly possible, but involves way to much counting to be "fun" in my book. |
|
|
|
| jdege | May 13 2008, 06:01 PM Post #24 |
|
Elite member
|
The old-timers had tools to make things easier. Strips of wood or cardboard with the alphabet, for example. You could lay them out one above the other, and shift them relative to each other so that one column gave you one slice's ciphertext. You could then read every other possible shift in the other columns.
If you had enough practice, you could pick out the column that had the highest -frequency of high-frequency letters almost instantaneously. But it takes a lot of tedious work, to have had enough practice. |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| 1 user reading this topic (1 Guest and 0 Anonymous) | |
| « Previous Topic · General · Next Topic » |
- Pages:
- 1
- 2
9:52 AM Nov 23
