- #1
- 35,005
- 21,683
- TL;DR Summary
- Why did the Enigma decryption take the path that it did, as opposed to a different one?
I've been thinking about the German Enigma machine, and how it might have been analyzed in a more modern perspective, without using attacks using known (or guessed) plaintext.
My understanding how the Engima worked is as follows: there are 3 (sometimes 4) rotars, each with 26 letters A-Z marked on it. Each rotar has one of several rings attactched to it, and each ring performs a simpler substitution cipher. As each letter is encrypted, the rings are advanced (AAA, AAB, AAC...ABA, ABB...BAA< BAB...) so the whole thing is a giant substitution cipher with period 263 or 17576. At the end there is a plugboard, which does another simple substitution cipher, and a reflector sending the message back through teh system: so messages are encrypted by Ring 1, Ring 2, Ring 3, Plugboard, Ring 3, Ring 2 and Ring 1.
The initial rotor position was sent in cleartext at the start of each message - the idea was to spread messages evenly over the the 175786 period to make cryptanalysis harder.
The Germans assumed (more or less correctly) that the Allies had Enigmas, but did not have the daily code settings.
If I have this substantially wrong, please correct me.
Given this, an ahistorical means of attack would be as follows:
(1) Two simple substitution ciphers in series is equivalent to one simple substitution cipher. If A encrypts to Q, it doesn't matter if iut goes via H and T and K first. So the whole complicated process can be turned into a ring set selection, a ring set initial position, and a substitution cipher.
(2) Simple substitution ciphers are easy to decrypt via frequency analysis. If we decrypt it to the point where we are left with a Simple substitution cipher, we're done.
(3) What's left is not too bad: ~102 ring choices and ~104 settings, so we're talking a few 106 possibilities. You would essentially try all the possibilities looking for repeated letters: it takes a shockingly short time for English (or German) to repeat a letter: 4-6 letters in my unscientific look at random bits of text. (And about 8 for gibberish) Counting the rate of multiple letters would be a good metric to see that the ring choice is right.
That seems to be in the possibility for an exhaustive search with 1940's era technology. A few machines running fgor a few hours could break the code in a day or less. All electronic - not electromechanical.
I suspect the fastest solution is progressive - drop 90% of the permutations quickly, then spend 10x as much time on the remaining ones, etc.
I'm sort of curious why things didn't work this was. Is my analysis flawed? Is it that the observation that multiple simples substitutions are equivalent to one? (The Enigma sure depended on these) Is it that the idea you could build an all-electronic solution too new? Or that you could brute-force it with existing technology?
My understanding how the Engima worked is as follows: there are 3 (sometimes 4) rotars, each with 26 letters A-Z marked on it. Each rotar has one of several rings attactched to it, and each ring performs a simpler substitution cipher. As each letter is encrypted, the rings are advanced (AAA, AAB, AAC...ABA, ABB...BAA< BAB...) so the whole thing is a giant substitution cipher with period 263 or 17576. At the end there is a plugboard, which does another simple substitution cipher, and a reflector sending the message back through teh system: so messages are encrypted by Ring 1, Ring 2, Ring 3, Plugboard, Ring 3, Ring 2 and Ring 1.
The initial rotor position was sent in cleartext at the start of each message - the idea was to spread messages evenly over the the 175786 period to make cryptanalysis harder.
The Germans assumed (more or less correctly) that the Allies had Enigmas, but did not have the daily code settings.
If I have this substantially wrong, please correct me.
Given this, an ahistorical means of attack would be as follows:
(1) Two simple substitution ciphers in series is equivalent to one simple substitution cipher. If A encrypts to Q, it doesn't matter if iut goes via H and T and K first. So the whole complicated process can be turned into a ring set selection, a ring set initial position, and a substitution cipher.
(2) Simple substitution ciphers are easy to decrypt via frequency analysis. If we decrypt it to the point where we are left with a Simple substitution cipher, we're done.
(3) What's left is not too bad: ~102 ring choices and ~104 settings, so we're talking a few 106 possibilities. You would essentially try all the possibilities looking for repeated letters: it takes a shockingly short time for English (or German) to repeat a letter: 4-6 letters in my unscientific look at random bits of text. (And about 8 for gibberish) Counting the rate of multiple letters would be a good metric to see that the ring choice is right.
That seems to be in the possibility for an exhaustive search with 1940's era technology. A few machines running fgor a few hours could break the code in a day or less. All electronic - not electromechanical.
I suspect the fastest solution is progressive - drop 90% of the permutations quickly, then spend 10x as much time on the remaining ones, etc.
I'm sort of curious why things didn't work this was. Is my analysis flawed? Is it that the observation that multiple simples substitutions are equivalent to one? (The Enigma sure depended on these) Is it that the idea you could build an all-electronic solution too new? Or that you could brute-force it with existing technology?