Enigma/Key Length - Revision history

Craig: moved Enigma Machine Key Length to Enigma/Key Length: Create a hierarchy for Enigma-related stuff

2012-01-26T11:47:51Z

moved Enigma Machine Key Length to Enigma/Key Length: Create a hierarchy for Enigma-related stuff

Craig: added reference

2012-01-15T01:29:22Z

added reference

Craig: corrected calculation of plug board combinations

2012-01-15T00:47:11Z

corrected calculation of plug board combinations

Craig: Force table of contents

2012-01-14T19:09:10Z

Force table of contents

Craig: /* Enigma M4 */

2012-01-14T18:15:57Z

‎Enigma M4

Craig: new page

2012-01-14T18:14:52Z

new page

New page

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 increasing 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
<code>
::n!/(2!*(n-2)!) = n!/(n-2)!/2 = (n-1)*n/2
</code>
:gives the following number of possible arrangements for each available number of connections:
::{| border="1" cellpadding="4" cellspacing="0"
!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!)

← Older revision		Revision as of 01:29, 15 January 2012
Line 78:		Line 78:

	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 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!)
		+
		+	==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

← Older revision		Revision as of 19:09, 14 January 2012
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.

← Older revision	Revision as of 11:47, 26 January 2012
(No difference)

@@ Line 11: / 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.
 ==Enigma M4==
@@ Line 24: / 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.
 ;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"
-!Jumpers
+!j
-!Possibilities
+!C(26,2j)
-!=
+!(2j-1)!&#33;
 |-
-|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
@@ Line 69: / Line 72: @@
 ===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 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.
+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.
-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!)
+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!)

@@ Line 13: / Line 13: @@
 ==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===