| 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 (1,091 Views) | |
| jdege | May 7 2008, 03:33 AM Post #1 |
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. | |
 |
 
|
| Donald | May 8 2008, 11:50 AM Post #2 |
|
Elite member
|
This is incredibly detailed good stuff, thanks! I added it to the tutorials. |
|
|
|
| jdege | May 8 2008, 02:01 PM Post #3 |
|
Elite member
|
I'd been intending to take a shot at cracking polyalphabetic substitutions - Vig, Beaufort, Variant, Porta, Gronsfeld, Quagmires I-IV - for some time. Now that I'm done wasting my time on cryptograms.org, I've started putting some scripts together. |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| Revelation | May 8 2008, 03:21 PM Post #4 |
Administrator
|
I've posted a polyalphabetic substitution cipher a while ago. I was surprised about how fast it was cracked! Thanks for the tutorial btw 
|
|
RRRREJMEEEEEPVKLWENFNVJKEEEEEAOLKAFKLXCFZAASDJXZTTTTTTTLSIOWJXMOKLAFJNNKFNXN RAGRBAQEMHIGDJVDSEOXVIYCELFHWLELJFIENXLRATALSJFSLCYTKLASJDKMHGOVOKAJDNMNUITN RRRRLJVEEEEECLYVYHNVPFTAEEEEEMWLMEIRNGLARWJAKJDFLWNTIERJMIPQWOTZEOCXKNUBNXCN RJIRPOWEANFUSNCZVDVZNMSFEKLOEPZLDKDJWSAAAAAAAOERHJCTNCKFRIMVKSOFOMKMANREWNBN RZUDRGXEEEEENFQIDVLQNCKNEEEEEDGLLLLLLAWIOSNCDARLODMTOEJXMILDFJROTKJSDNLVCZNN | |
|
|
|
| jdege | May 8 2008, 03:48 PM Post #5 |
|
Elite member
|
Truth is, once you know how to find the keylength, Vig is easier to crack than simple substitution. Underneath, it's just a couple of Caesar shifts. It's Pats that drive me nuts. I have one more in mind, on what I've learned about attacking Pats when you don't have a crib. |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| Paarth Dave | May 9 2008, 07:09 AM Post #6 |
|
Advanced Member
|
How do you do that? And how do you do a chi test? |
|
Cryptography Vanquished.... | |
|
|
|
| jdege | May 9 2008, 07:54 PM Post #7 |
|
Elite member
|
Have you read: http://z13.invisionfree.com/Crypto/index.php?showtopic=456? You split the ciphertext into n slices, where n is your provisional keylength. So if you're testing to see if the keylength is 3, you split the ciphertext into three slices, where slice 0 has letters 0,3,6,9,12,...slice 1 has letters 1,4,7,10,..., and slice 2 has letters 2,5,8,11,... The for each slice we do a frequency count, and then calculate the Incidence of Coincidence of that slice, and then we average the IC's for the n slices. You need two frequency counts, one of slice you're testing, and one of a piece of standard English text that you're using as a reference. Suppose you have F1: {A=3, B=1, C=1, D=1, E=12, F=3,...} and F2: {A=8, B=1, C=3, D=0, E=21, F=8,...}. Where the sum of the counts for F1 is N1: 105, and the sum of the counts for F2 is N2: 306. You multiple the count for A in F1 by the count for A in F2, and add to it the product of the count for B in F1 and B in F2, etc. Then divide by the product of the sums.
|
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| Donald | May 9 2008, 09:02 PM Post #8 |
|
Elite member
|
Pats are hard, but rot13's playfair was the hardest nut I ever cracked. And the scary thing is, that was a very easy playfair with a simple and obviously keyed matrix and a nice long easy to place crib. Whoo! |
|
|
|
| jdege | May 9 2008, 09:32 PM Post #9 |
|
Elite member
|
And the problem is that the solutions of so many of the polyalphabets involve converting to a pat. The Quags and the Gronsfeld, are, in effect, mixed-alphabet Vigs. So the approach I described here should work for all of them. It would even work for the Porta. though the shifting would be a bit different. But what this gives you is a Pat - which I can pretty much always solve given a couple of hundred letters to work with, but for shorter messages I get stuck as much as half the time. I can cheat the ACA K1-K3, with a dictionary attack. But the unkeyed and the K4 I just bang my head against as often as not. |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| Paarth Dave | May 10 2008, 05:16 AM Post #10 |
|
Advanced Member
|
So for calculating the IOC of the n slices, do we also have to do the kappa test? |
|
Cryptography Vanquished.... | |
|
|
|
| jdege | May 10 2008, 05:58 AM Post #11 |
|
Elite member
|
The IC is the kappa test, divided by a scaling factor. And yes, we need to calculate it for each slice, then calculate the average for all of the slices, then do it again for the next prospective key length. It's tedious to do it by hand, but it's what computers were invented for. (And I'm not being figurative - it's solving exactly this kind of problem for which the first computer was invented.) |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| Paarth Dave | May 10 2008, 06:06 AM Post #12 |
|
Advanced Member
|
Can you please explain to me the chi test in simple terms? I have read your topics based on it...but it went above my head... |
|
Cryptography Vanquished.... | |
|
|
|
| jdege | May 10 2008, 07:44 AM Post #13 |
|
Elite member
|
You use the chi test to measure how similar two frequency distributions are. When you draw a graph a frequency distribution, you get a curve with peaks and valleys. If two messages are encoded with the same alphabet, they will have similar curves. If they are encoded with alphabets that are shifted relative to one another, they will have curves that won't match up - the peaks and valleys of one will be shifted relative to the other. The Vig uses the standard alphabet - A-Z, shifted by an amount equal to the numeric value of the key letter. If the key letter is 'B', the cipher text consists of the plaintext shifted by one character, if it's 'D', it's shifted by three. So, after we've figured out how many alphabets there are - how many letters there are in the keyword - the next step is to figure out by how much each of the alphabets has been shifted. And we do that by trying out the 26 different shift amounts, and comparing the frequency distribution of each against the frequency distribution of plain text, to see which lines up the best. This is the frequency distribution of normal English text: Now suppose you were trying to crack a vig, and you'd already figured out that it had a five-letter keyword. Starting at the first letter, you'd take every fifth letter, and do a frequency distribution, and you might get something like this: Now this doesn't line up nicely with the graph above. But it does have the same number of peaks and valleys. So when we shift it over a bit, we get a graph that does line up nicely: The question is how do you recognize that you things lined up properly? It's not a matter of finding the perfect fit, because you'll never get a perfect fit. It's a matter of recognizing which is the best fit, of the 26 possibilities you have. You can do it by eye, but we'd really rather have a process we can use that's a little more reliable, and it'd be really nice if we had something we could program into a computer. That's what the chi test is - a measure of how closely two frequency distributions match. And the calculation is pretty simple: 257 is the sum of the frequency counts of the first text - the total number of latters in the first text. 101 is the sum of the frequency counts of the second text. 741 is the sum of the products of the frequncy counts for each letter. And chi is: The sum of the products divided by the product of the sums Your result will range from about 0 - meaning that the frequency distributiions are inverses of each other (one peaks where the other vallteys, and vice versa), to about 0.0385 - meaning that there is no correlation whatsoever between the two distributions, to about 0.070 - meaning that the two distributions line up almost perfectly. |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| Paarth Dave | May 10 2008, 07:48 AM Post #14 |
|
Advanced Member
|
Can you explain it to me with an example? |
|
Cryptography Vanquished.... | |
|
|
|
| jdege | May 10 2008, 11:53 AM Post #15 |
|
Elite member
|
That was an example. What are you having problems with? How to do the arithmetic? How to calculate the frequencies? How you shift an alphabet? |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
|
|
|
| 1 user reading this topic (1 Guest and 0 Anonymous) | |
| Go to Next Page | |
| « Previous Topic · General · Next Topic » |
- Pages:
- 1
- 2
10:40 PM Mar 21
