# Simple Crypto Operations

In a pure transposition cipher, the text “AAAAAA” is transformed to “AAAAAA”.

In a pure, static substitution cipher, the text “AAAAAA” is transformed to (say) “ZZZZZZ”.

In a vignere pad, the string “AAAAAA” input  is transformed to an output which is equal to the keyword (or an offset of all its letters, making it easy to guess).

If the keyword were completely random and not used again, but still shared between two parties, one would arrive at the one-time pad, which has perfect secrecy.  Is this possible ? Wikipedia says information-theoretic secrecy is used in top secret communications.

The Enigma cipher was a dynamic substitution cipher where the substitution maps changes as the rotors rotate before each letter is entered. This machine and its code-breaking machine is the subject of the movie The Imitation Game, discussed in my previous blog post.

# The Imitation Game – The Movie

The number of permutations of the 26 alphabet, 26! is ~0.4 billion billion billion – 0.4 octillion – 4 followed by 26 zeros. This is the number of maps from the set of 26 letters to itself, and the size of the space of all maps that the German Enigma machine played in.

The number of maps the Enigma actually utilized to transform an input letter to another is much smaller. At the core the machine has a handful of rings which implement fixed maps. Each individual ring implements one fixed permutation map of the numbers 1-26 to itself.   The fixedness is important – bit hard to believe as it appears to considerably simplify the attack – the ring does not vary its map (input-output permutation) except due to rotation of the ring – which can be in any of 26 different positions. With 3 rings, they could be ordered in 6 ways and total of 6×26^3 maps – only about 106,000. With the 3 rings chosen from 5 available rings instead of 3, there could be 5x4x3 or 60 combinations and 60×26^3 maps – a million. At each letter entry the rotors would change to use another of the ~10600 maps.  Guessing a valid map (10^5) from the much larger space of all maps (4*10^26) made cracking the code near impossible – assuming good operating procedures. The plugboard implemented another (fixed) permutation.

The Polish bomba utilized leaked knowledge of both the maps and the known number of rings – and with that information tried a brute force attack for the 3-ring design. Even with knowledge of the machine internals this required ingenuity to look for patterns in the messages – duplicate input letters that were frequently mapped to duplicates in the output reduced the search space.

This worked until the Germans added two more rings to the original 3. At this point the Polish method was not effective. Turing understood a different method was needed.

The machine that was built at Bletchley park and was shown in the movie was also a brute force machine, not a general purpose computer (as I assumed before the movie). It used input text that was likely to be in the transmitted data, encrypted it in several combinations then compared it with the actual transmissions. This is called a chosen plaintext attack.

An interesting aspect in the movie was how hard Turing had to fight to keep the idea of this machine alive as it was an unknown and unproven concept to the military generals. When he succeeded and U-boats were started to be destroyed (with a cover of air surveillance as the source of sighting the subs), Admiral Karl Dönitz on the German side had to convince his own chain of command of the need to change Enigma – a request deflected for several months as the German chain of command bought the air surveillance story. Dönitz eventually succeeded in adding a fourth rotor and the submarine attacks subsided immediately – until a couple subs were captured and the details of the newer rings were found by the British.

In a way, the machines on either side were trying to get smarter but were slowed down by a human bottleneck. The selfish machines.

The basic idea of a small set of pseudo-random (fixed) permutations embedded in a larger space of permutations is utilized in block-ciphers (DES, AES) in form of P-boxes. A difference is the presence of S-boxes which achieve mixing of the inputs so an input pattern does not have a deterministic effect on output patterns.

What’s interesting is an information theoretic notion of security which is not susceptible to attacks. Some of these ideas are used in the IDEA cipher.