Enigma/Key Length

From Franklin Heath Ltd Wiki
Revision as of 19:15, 14 January 2012 by Craig (Talk | contribs)

Jump to: navigation, search

Much discussion of cryptography involves the key length used in encryption algorithms, as this directly influences the security provided by the algorithm. For modern computerised encryption algorithms like RSA or AES, the key length is expressed as a number of bits in a binary representation of the number given as the key. For an Enigma machine, which doesn't use binary and doesn't have a single number as a key, it's a lot harder to determine what the effective "key length" is.

An Enigma machine's "key" is a combination of various machine settings applied before enciphering of the message:

  • The reflector selection
  • The rotor selection
  • The ring settings on the rotors
  • The plug board connections
  • The indicator settings

Different models of Enigma machine have different numbers of possibilities for these selections (non-military ones have no plug board, for instance) so the key length calculation will be different for each model. The overall "key length" can be determined by multiplying the number of possibilities for each of these settings together, and taking the logarithm in base 2 of the result to give the number of bits in a theoretical binary representation.

Enigma M4

This model included a plug board, and used a thin reflector and an extra thin rotor taking the place of the normal reflector on a three-rotor Enigma M3 to increase the number of possible settings, so this will have a longer "key length" than many other models.

Settings Contributing to Effective Key Length

Reflector selection
There were two possible reflectors, "Thin B" or "Thin C".
Rotor selection
There were two possible rotors for the thin left-hand position ("Beta" and "Gamma"). The three other rotors were chosen, in any order, from a possible eight supplied with the machine (numbered "I" to "VIII"). This gives a total of 2*8*7*6 = 672 possibilities.
Ring settings
Each of the four rotors could have its outer ring rotated through 26 positions to change the alignment of the internal wiring. This gives 26*26*26*26 = 456,976 possibilities.
Plug board connections
The plug board was used to exchange the connections of pairs of letters on the keyboard and lamp board. Before World War II the German military used varying numbers of jumper connections, but latterly they standardised on 10. The machine however is capable of using any number of connections from 0 to 13 (maximum number of pairs in 26 letters).
Mathematically, each connection is a combination without repetition of 2 from n items, where n is the number of unconnected letters remaining. Using the formula

n!/(2!*(n-2)!) = n!/(n-2)!/2 = (n-1)*n/2

gives the following number of possible arrangements for each available number of connections:
Jumpers Possibilities =
0 1 1
1 25*13 325
2 ,, * 23*12 89,700
3 ,, * 21*11 20,720,700
4 ,, * 19*10 3,936,933,000
5 ,, * 17*9 602,350,749,000
6 ,, * 15*8 72,282,089,880,000
7 ,, * 13*7 6,577,670,179,080,000
8 ,, * 11*6 434,126,231,819,280,000
9 ,, * 9*5 19,535,680,431,867,600,000
10 ,, * 7*4 546,999,052,092,292,800,000
11 ,, * 5*3 8,204,985,781,384,392,000,000
12 ,, * 3 24,614,957,344,153,176,000,000
13 ,, 24,614,957,344,153,176,000,000
Total 58,001,875,979,005,301,132,726
Indicator settings

At the start of the message, the operator would turn the rotors so that a particular set of letters (or numbers on some models) were visible in the windows. Although this is part of the message key, it only adds any cryptographic complexity if the particular rotor being turned affects the stepping of the next rotor along; this is because the notches which control stepping and the indicator are both on the outer ring, whereas the internal wiring is on the inner part of the rotor and the 26 possible positions of that are already accounted for above in the "Ring settings" section. Therefore, only the indicator settings of the two right-hand rotors contribute to the effective key length, giving 26*26 = 676 possibilities.

Calculated Effective Key Length

Multiplying all these possibilities together (as they are all independent) gives a total of:

2 * 672 * 456,976 * 58,001,875,979,005,301,132,726 * 676 = 24,081,381,444,973,685,021,319,958,847,545,344 possible keys

Log base 2 of 2.408e34 is 114.2, so the effective key length of an Enigma M4 machine is between 114 and 115 bits, which is comparable to today's typical 128-bit encryption of e-commerce web pages.

It's interesting to note though that the majority of that key length is due to the plug board settings (log base 2 of 5.800e22 being 75.62) and that the plug board's part in the algorithm is a fixed substitution cipher; such ciphers are very susceptible to cryptanalysis using letter frequency counts, so the security provided is likely to be a lot less than this calculated effective key length suggests (not to mention the weakness of a letter never encrypting to itself, but that's another story!)