| 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: |
| A Difficult Cipher, Double Vigenere | |
|---|---|
| Topic Started: Nov 1 2005, 05:04 PM (328 Views) | |
| rot13 | Nov 1 2005, 05:04 PM Post #1 |
|
Elite member
  ![]](http://209.85.122.85/static/1/pip_r.png)
|
Donald's Calculator Cipher got me thinking this morning about what I would consider a good balance between easy to use and difficult to break pencil&paper ciphers. The Calculator Cipher seemed a like a bit more work than I would like, and to remember 21 digits seems like a lot for a key, although the method of converting from a string is reasonable. At first, I thought about doing something with a numeric cipher like a homophonic, but since that it basically just a Vigenere with numbers instead of letters, I thought I'd just stick to Vigenere. We know how easy it is to crack a straight Vigenere. One thing I thought of was to do a double Vigenere using keys of different length. For example:
So to encrypt T you first encrypt it with S to get L, then you encrypt L with Z to get K. The interesting thing about this is that the effective key length is the least common multiple of the two key lengths. In this case, 5*6 = 30. With a really long text, you can still use the same attacks as usual. This does make IOC and Kasiski much tougher. Of course, all you need is a small amount of known text and I think it still falls apart. For example, suppose that you know that the text starts with "THISISANEXAMPLE". Using the Vigenere table, you can find out what key generates KSVRQRGRIULAOGG from THISISANEXAMPLE. In this case, it is RLNZIZGEEXLOZVC. This resulting key represents key 1 Vigenere encrypted against key 2. To recover the key, assuming you somehow can guess the lengths of the respective keys, you only need to try 26 different letters for key1 and everything else falls apart. Look how the numbering of the key positions lines up:
key2[1] = ct[1] - key1[1] // Compute first letter of key 2 from 1st of key1 key1[2] = ct[7] - key2[1] // Compute 2nd letter of key1 from 1st of key2 key1[3] = ct[13] - key2[1] // Compute 2rd letter of key1 from 1st of key2 key2[2] = ct[2] - key1[2] // Compute 2nd letter of key2 from 2nd letter of key1 key2[3] = ct[3] - key1[3] // Compute 3rd letter of key2 from 3rd letter of key1 key1[4] = ct[9] - key2[3] // Compute 4th letter of key1 from 3rd letter of key2 key1[5] = ct[15] - key2[3] // Compute 5th letter of key1 from 3rd letter of key2 At this point, we have a guess for key1. We can fill out the remaining guesses for key2: key2[4] = ct[4] - key1[4] key2[5] = ct[5] - key1[5] key2[6] = ct[6] - key1[1] Trying all 26 possible values for key1[1] you get a list like this:
You can see SHARP and ZENITH show up there. This assumes that you can guess the key lengths, but really, you can try lengths up to 10 for each key and you're really only doing 2600 possible values. Now, the way to throw a wrench into this whole thing, and frankly I can't come up with any quick attacks off the top of my head, is to use a mixed alphabet instead of a Vigenere alphabet. For example, I might use a mixed alphabet of MAGNVOXBCDEFHIJKLPQRSTUWYZ:
Now, even if I know "THISISANEXAMPLE" at the beginning and I even know the key lengths, I can't easily recover the keys because I no longer know what key was used to turn plaintext T into ciphertext K. I'll have to think for a while on how I would attack this. I guess you would call this a Double Quagmire III. |
 |
 
|
| cows | Nov 1 2005, 05:52 PM Post #2 |
Advanced Member
|
Interesting read - I was thinking something similar a couple of weeks ago not knowing if it was already done or not so disgarded it but you have proved me wrong
|
|
Everything is possible, The impossible just takes longer If we do not know what a particle is doing then it is allowed t do everything possible simultaneously. "Anyone who can contemplate Quantum Mechanics without getting dizzy, didn't understand it." | |
|
|
|
| Donald | Nov 1 2005, 06:13 PM Post #3 |
|
Elite member
|
This is certainly not a crack, but it is a TINY hole. With our known plaintext, note that we have two S's that both encrypt to an R:
This is because in our key: R+I= 18+9 =27 and S+H=19+8=27. Ok, it's not much, but we DO know from this a little bit of information about the two keys, or at least about the way they combine. Only certain letter combinations can produce that result. And this gives us further information about the rest of the cryptogram. We now know that characters at position 4 and 6 are encrypted with the same super key shift. It's only a TINY hole, and it requires a sizable chunk of known plain text. I think there may be more that can be done along these lines, but I'm outta time for now. Donald |
|
|
|
| Donald | Nov 3 2005, 01:59 PM Post #4 |
|
Elite member
|
I just can't get anywhere with it. Not good enough at math. This is, as Rot13 pointed out, a Quag with a really big key. An unbelievably big key. all you have to do is up your two keywords to lengths of 7 and 13 and you have a key length of 91. 13x17 would give you 221. Ouch. I do not think this is actually as strong as if it really WERE just a Quagmire III with that key length. Our key here is composed of only combinations of the few letters in our two smaller keys. This has simply GOT to lead to some patterns and weaknesses. But they aren't VERY weak. I haven't been able to find any useful hole through these patterns, but perhaps that is simply my ignorance. Take our example, for example.
We find some interesting relationships here. a4+b4=a1+b6 a4+b4=a3+b2-5 (or a3+b2+21) a2+b1=a4+b2+11 (or a4+b2-15) a2+b1=a5+b3+4 (or a5+b3-22) (a4= 4th character of key a. b1=first character of key b) These relationships limit the possible letter combinations that could be in the primary key. But in the case of a mixed cipher alphabet, knowing the key is only of limited help. The formulas provide hints and clues as to how the mixed cipher alphabet is shifted (for some letters). But really, not much of a clue. And no more than we would have had from a real Quagmire with a very long key. Given sufficient text, the cipher would fall to the same techniques as a Quag III, but with this key length, that would be one unbelievable hunk of text. I THINK it would fall easier than a normal Quag III with a key that was actually that long, BUT, easier here is a VERY relative term. And who could remember a 221 character key? But it's pretty easy to remember two short keys and the key for the mixed alphabet. If you post a challenge in this cipher, encrypt an entire book. Donald |
|
|
|
| cows | Nov 8 2005, 04:01 PM Post #5 |
|
Advanced Member
|
I vaguely understood that... *head throbs in pain* Just so people don't get the wrong idea - i had the random thought of double encryping a text, but then a) read about it in rot13's post and b) just read about public key encryption in simon singh's: The code book and now realise that i have not made a revolutionary breakthrough, just repeating an old technique. Ah well... |
|
Everything is possible, The impossible just takes longer If we do not know what a particle is doing then it is allowed t do everything possible simultaneously. "Anyone who can contemplate Quantum Mechanics without getting dizzy, didn't understand it." | |
|
|
|
| Donald | Nov 8 2005, 04:21 PM Post #6 |
|
Elite member
|
Be very careful with double encryption. SOMETIMES (as in rot13's double Vigenere) it makes the cipher more difficult to break. But frequently the added difficulty is just an illusion. For example: Say we do the following. I'm going to encrypt something with a CAESAR shift, but to make it complicated I'm going to encrypt it three times!
Pretty complicated huh? nope. The decryptor will never know you used three Caesar shifts. Because a Caesar shift of 1 then 3 then 2 equals a single Caesar shift of 6.
This is true for ANY monsubstitution cipher. Pile them on top of each other as much as you wish, you haven't increased the security of the cipher at all because it all adds up to one new cipher where A in the input equals some unique character of output. Donald |
|
|
|
| 1 user reading this topic (1 Guest and 0 Anonymous) | |
| « Previous Topic · General · Next Topic » |
5:24 PM Nov 28
