Difference between revisions of "Enigma/Key Length"

From Franklin Heath Ltd Wiki
Jump to: navigation, search
(new page)
 
m (moved Enigma Machine Key Length to Enigma/Key Length: Create a hierarchy for Enigma-related stuff)
 
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
__TOC__
 
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.
 
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.
  
Line 10: Line 11:
  
 
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.
 
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.
 +
 +
==Calculating the number of possible plug board settings==
 +
The plug board was used on German military machines to exchange connections of pairs of letters on the keyboard and lamp board.  Before World War II varying numbers of jumper connections were used, 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).
 +
 +
Working out the total number of possible combinations turns out to be somewhat complex (I initially tried to work this out myself and got it wrong, Ralph Simpson of [http://ciphermachines.com ciphermachines.com] kindly set me straight).  Each arrangement with a certain number of jumpers is distinct from every arrangement with a different number of jumpers, so we calculate the combinations for each possible number of jumpers separately, then add them together.  For each number of jumper connections, we calculate how many ways there are to divide the set of 26 letters into sets of jumpered letters and unjumpered letters.  Then for the jumpered letters we calculate how many different ways they can be arranged in pairs.  We then multiply the number of possible set divisions by the number of possible pairings to give the total number of possible settings with that number of jumpers.
 +
 +
Mathematically, the number of possible divisions is a [http://jumk.de/combinatorics/binomial-coefficient.php k-Combination], C(26,k) where k is the number of jumpered letters; the number of possible pairs within k jumpered letters is a [http://keisan.casio.com/has10/SpecExec.cgi?path=08000000%2eSpecial%20Function%2f07000300%2eDouble%20factorial%2f10000100%2eDouble%20factorial%2fdefault%2exml&charset=utf-8 double factorial] (k-1)!! .
  
 
==Enigma M4==
 
==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 increasing the number of possible settings, so this will have a longer "key length" than many other models.
+
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===
 
===Settings Contributing to Effective Key Length===
Line 23: Line 31:
 
: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.
 
: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
 
;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).
+
Any number of jumpers (<b>j</b> below) from 0 to the maximum 13 with every letter connected to another could be used:
:Mathematically, each connection is a <b>combination without repetition</b> of 2 from <i>n</i> items, where <i>n</i> is the number of unconnected letters remaining.  Using the formula
+
<code>
+
::<i>n!/(2!*(n-2)!) = n!/(n-2)!/2 = (n-1)*n/2</i>
+
</code>
+
:gives the following number of possible arrangements for each available number of connections:
+
 
::{| border="1" cellpadding="4" cellspacing="0"
 
::{| border="1" cellpadding="4" cellspacing="0"
!Jumpers
+
!j
!Possibilities
+
!C(26,2j)
!=
+
!(2j-1)!&#33;
 +
!Result
 
|-
 
|-
|0||1||1
+
|0||1||1||1
 
|-
 
|-
|1||25*13||325
+
|1||325||1||325
 
|-
 
|-
|2||,, * 23*12||89,700
+
|2||14,950||3||44,850
 
|-
 
|-
|3||,, * 21*11||20,720,700
+
|3||230,230||15||3,453,450
 
|-
 
|-
|4||,, * 19*10||3,936,933,000
+
|4||1,562,275||105||164,038,875
 
|-
 
|-
|5||,, * 17*9||602,350,749,000
+
|5||5,311,735||945||5,019,589,575
 
|-
 
|-
|6||,, * 15*8||72,282,089,880,000
+
|6||9,657,700||10,395||100,391,791,500
 
|-
 
|-
|7||,, * 13*7||6,577,670,179,080,000
+
|7||9,657,700||135,135||1,305,093,289,500
 
|-
 
|-
|8||,, * 11*6||434,126,231,819,280,000
+
|8||5,311,735||2,027,025||10,767,019,638,375
 
|-
 
|-
|9||,, * 9*5||19,535,680,431,867,600,000
+
|9||1,562,275||34,459,425||53,835,098,191,875
 
|-
 
|-
|10||,, * 7*4||546,999,052,092,292,800,000
+
|10||230,230||654,729,075||150,738,274,937,250
 
|-
 
|-
|11||,, * 5*3||8,204,985,781,384,392,000,000
+
|11||14,950||13,749,310,575||205,552,193,096,250
 
|-
 
|-
|12||,, * 3||24,614,957,344,153,176,000,000
+
|12||325||316,234,143,225||102,776,096,548,125
 
|-
 
|-
|13||,,||24,614,957,344,153,176,000,000
+
|13||1||7,905,853,580,625||7,905,853,580,625
 
|-
 
|-
|Total|| ||58,001,875,979,005,301,132,726
+
|colspan="3"|Total possibilities||532,985,208,200,576
 
|}
 
|}
 
;Indicator settings
 
;Indicator settings
Line 68: Line 72:
  
 
===Calculated Effective Key Length===
 
===Calculated Effective Key Length===
Multiplying all these possibilities together (as they are all independent) gives a total of:
+
Multiplying all these possibilities together (as they are all set independently) 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
+
:2 * 672 * 456,976 * 532,985,208,200,576 * 676 = 221,286,292,668,406,558,235,295,744 possible keys
 +
 
 +
Log<sub>2</sub> of 2.213e26 is 87.52, so the effective key length of an Enigma M4 machine is between 87 and 88 bits, compared to today's typical 128-bit encryption of e-commerce web pages.
  
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 that more than half that key length is due to the plug board settings (log<sub>2</sub> of 5.330e14 being 48.92) 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 quite a bit 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!)
  
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!)
+
==Further Reading==
 +
;<span id="Miller1995">Miller, A. Ray (1995)</span>
 +
:''[http://www.nsa.gov/about/_files/cryptologic_heritage/publications/wwii/engima_cryptographic_mathematics.pdf The Cryptographic Mathematics of Enigma''], NSA Center for Cryptologic History

Latest revision as of 11:47, 26 January 2012

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.

Calculating the number of possible plug board settings

The plug board was used on German military machines to exchange connections of pairs of letters on the keyboard and lamp board. Before World War II varying numbers of jumper connections were used, 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).

Working out the total number of possible combinations turns out to be somewhat complex (I initially tried to work this out myself and got it wrong, Ralph Simpson of ciphermachines.com kindly set me straight). Each arrangement with a certain number of jumpers is distinct from every arrangement with a different number of jumpers, so we calculate the combinations for each possible number of jumpers separately, then add them together. For each number of jumper connections, we calculate how many ways there are to divide the set of 26 letters into sets of jumpered letters and unjumpered letters. Then for the jumpered letters we calculate how many different ways they can be arranged in pairs. We then multiply the number of possible set divisions by the number of possible pairings to give the total number of possible settings with that number of jumpers.

Mathematically, the number of possible divisions is a k-Combination, C(26,k) where k is the number of jumpered letters; the number of possible pairs within k jumpered letters is a double factorial (k-1)!! .

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

Any number of jumpers (j below) from 0 to the maximum 13 with every letter connected to another could be used:

j C(26,2j) (2j-1)!! Result
0 1 1 1
1 325 1 325
2 14,950 3 44,850
3 230,230 15 3,453,450
4 1,562,275 105 164,038,875
5 5,311,735 945 5,019,589,575
6 9,657,700 10,395 100,391,791,500
7 9,657,700 135,135 1,305,093,289,500
8 5,311,735 2,027,025 10,767,019,638,375
9 1,562,275 34,459,425 53,835,098,191,875
10 230,230 654,729,075 150,738,274,937,250
11 14,950 13,749,310,575 205,552,193,096,250
12 325 316,234,143,225 102,776,096,548,125
13 1 7,905,853,580,625 7,905,853,580,625
Total possibilities 532,985,208,200,576
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 set independently) gives a total of:

2 * 672 * 456,976 * 532,985,208,200,576 * 676 = 221,286,292,668,406,558,235,295,744 possible keys

Log2 of 2.213e26 is 87.52, so the effective key length of an Enigma M4 machine is between 87 and 88 bits, compared to today's typical 128-bit encryption of e-commerce web pages.

It's interesting to note that more than half that key length is due to the plug board settings (log2 of 5.330e14 being 48.92) 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 quite a bit 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!)

Further Reading

Miller, A. Ray (1995)
The Cryptographic Mathematics of Enigma, NSA Center for Cryptologic History