|
My crypto Home Page Enigma Cryptanalysis home Page
|
IntroductionAt the end of 1932, the Polish Rejewski reconstructed on paper the Enigma cipher machine used by the German army. At the end of January 1933, a Enigma replica was built by Antoni Palluth. This replica allowed the deciphering of Enigma traffic when the key of the day could be found. The heart of the Enigma are the elements that permute the electric current: the reflector, the three rotors, the ETW (which connects the right rotor to the keyboard) and finally the steckers that allow the electric circuit to be changed every day. In this document, we will describe the most important step of Rejewski's feat: the reconstruction of the wiring of the right rotor, the one that turns each time a letter must be encrypted. Note: We will rely on the description made by Craig Bauer which itself is based directly on Rejewski's own account. To simplify our description and allow you to redo it yourself, we will use a simplified vision of the Enigma consisting of a reflector and a single rotor. On the other hand, we will use only 6 cables instead of the 26 cables representing the 26 letters of the alphabet. Finally, we will use the Python computer language to perform the calculations. The material Rejewski hadRejewski had the following material:
The Indicator Method used in 1932This method is essential in Rejewski's feat. Here is its description: A message key composed of three numbers (from 01 to 26) is chosen by the cipher clerk for each message. The rotors are positioned as part of the daily key (Grundstellung), and the message key is encrypted twice. Here is an example of the beginning of a message: 1035-96-341 PKPJX IGCDS EAHUG WTQGR …The time is represented by 1035 (10h35), 96 is the length of the message, and 341 is the encryption network identifier. The first six letters of the message, PKPJXI, correspond to the encryption of ABLABL at Grundstellung FOL (or 06-15-12). The message (GCDSEAHUG …) is encrypted or decrypted by positioning the rotors at the ABL key (or 01-02-12). As we can see, to be sure of the correct reception of the message key, the indicator encrypts this key twice. This was a huge mistake by the German cipher service, as we will see. Mathematical vision of the Enigma encryption, simplificationsRejewski used group theory and more specifically permutations to describe the Enigma encryption. Consider the following permutations:
We can make some simplifications:
In short, we get a much simpler equation (i being the position of the fast rotor):
\( Enigma_i = P^{i} \cdot N \cdot P^{-i} \cdot Q \cdot P^{i} \cdot N^{-1} \cdot P^{-i} \) Note: as we can see, this is the formula that describes our simplified Enigma. 1st step: Find the value of the equations AD, BE and CFAn example of Enigma trafficHere are the headers collected from one day's traffic. As a reminder, these groups of 6 letters were encrypted at the same position and correspond to the encryption of the message key performed twice (for example 012 012 for the key 012). As we can see, some headers are very frequent. 144 543 x 12 155 524 x 9 053 425 x 9 535 314 x 8 212 031 x 7 300 102 x 6 402 201 x 5 …The other headers (about twenty) are rarer. The mathematical visionDue to the way the indicator works, the first and fourth letters of the indicator are identical. The same is true for the second and fifth as well as the third and sixth. Let the permutations A, B, C, D, E and F correspond to the first six permutations respectively at position 0, 1, 2, 3, 4, 5 of the right rotor. For example D corresponds to
\( D = Enigma_3 = P^{3} \cdot N \cdot P^{-3} \cdot Q \cdot P^{3}
\cdot N^{-3} \cdot P^{-3} \) These permutations are unknown, however, the permutations AD, BE and CF are known. Indeed, permutation A transforms the letter x into the first letter of the indicator and permutation D transforms the same letter x into the fourth letter of the indicator. So the composition AD transforms the letter x into the letter x (but we do not know the value of x). If we take the 1st indicator (141543), the letter 1 is transformed into 5 in position 0, similarly 0 is transformed into 4, 2 into 0, 3 into 1, … So we can reconstruct the value of the different compositions AD, BE, CF: AD = ((0, 4, 2)(1, 5, 3)) BE = ((0), (4)(1,3)(2,5)) CF = ((0, 2, 1)(3, 5, 4)) 2nd step: Find the value of the permutations A, B, C, D, E and FFactorization of the compositionsWe now want to deduce from the compositions AD, BE and CF the permutations A to F. We must factorize these compositions. This is more complex than factoring numbers into primes.
Let \( XY= ((x_1 x_3 x_5 … x_{2n-1}) (y_{2n} … y6 y4 y2), \) then we have The cycles \( (x_1, x_3, x_5, …, x_{2n-1}) \quad \textrm{and} \quad (x_3, x_5, …, x_{2n-1}, x_1) \quad \) give different factorizations. Note: This method of factorization was invented by Rejewski. Here are the details of the operations: BE includes cycles of length 1 ((0) and (4)), so (0 4) is part of E. BE includes cycles (1 3) and (2 5), so we have two possibilities for E:
Following the same reasoning, the permutation B is equal to ((0 4)(1 2)(3 5)) or ((0 4)(2 3)(1 5)). In conclusion, B1 E1 and B2 E2 can have the following values:
Compositions AD, BE, CF: Verification with PythonThe different possibilities (e.g. B1 E1 and B2 E2) are compatible with the observed values. >>> B1 = Permutation([[0,4],[1,2],[3,5]]) >>> E1 = Permutation([[0,4],[2,3],[1,5]]) >>> (B1*E1).full_cyclic_form [[0], [1, 3], [2, 5], [4]] >>> B2 = Permutation([[0,4],[2,3],[1,5]]) >>> E2 = Permutation([[0,4],[1,2],[3,5]]) >>> (B2*E2).full_cyclic_form [[0], [1, 3], [2, 5], [4]] >>> A1 = Permutation([[0,1],[4,3],[2,5]]) >>> D1 = Permutation([[2,3],[5,0],[1,4]]) >>> A1*D1 Permutation(0, 4, 2)(1, 5, 3) >>> A2 = Permutation([[0,5],[4,1],[2,3]]) >>> D2 = Permutation([[3,0],[5,4],[1,2]]) >>> A2 * D2 Permutation(0, 4, 2)(1, 5, 3) >>> A3 = Permutation([[0,3],[4,5],[2,1]]) >>> A3**2 Permutation(5) >>> D3 = Permutation([[2,5],[4,3],[0,1]]) >>> A3 * D3 Permutation(0, 4, 2)(1, 5, 3) >>> C1 = Permutation([[0,4],[2,5],[1,3]]) >>> F1 = Permutation([[4,2],[5,1],[3,0]]) >>> C1 * F1 Permutation(0, 2, 1)(3, 5, 4) >>> >>> C2 = Permutation([[2,4],[1,5],[0,3]]) >>> F2 = Permutation([[1,4],[0,5],[2,3]]) >>> C2 * F2 Permutation(0, 2, 1)(3, 5, 4) >>> >>> C3 = Permutation([[1,4],[0,5],[2,3]]) >>> F3 = Permutation([[4,0],[5,2],[3,1]]) >>> C3 * F3 Permutation(0, 2, 1)(3, 5, 4) Permutations A to FAs we have seen, there are 18 (2x3x3) sets of permutations A to F. Which one is correct? Note: Craig Bauer shows that for the real Enigma, there are 7020 possibilities (20 x 27 x 13) Here too, Rejewski's genius comes into play: He assumes that the operators manipulating the Enigma do not use random message keys (as the manual recommends). He assumes that the keys AAA, BBB, ABC, … are more often used. In all cases, the keys used are influenced by human choice and are not random. Rejewski could test the 7020 possibilities and see which one gave non-random keys. He could also start by testing the indicators that were most frequent and guess their value. For our simplified Enigma, the indicator 144,543 is the most frequent. Let's imagine that it corresponds to the encryption of 000 000.
Now let's take the indicator 155 524 and suppose that it corresponds to 012 012. In this case, for BE, we have 1=>5 and 1=>2. Only B1 and E1 are possible. We have therefore found the 6 permutations A to F:
VerificationTo verify our hypothesis, we just need to decipher all the indicators: 144 543 => 000 000 155 524 => 012 012 053 425 => 111 111 535 514 => 222 222 402 201 => 345 345 212 031 => 555 555 300 102 => 444 444We have a sequence of non-random keys. The underside of the cardsHere is the description of the operations that allowed us to create the test set. >>> from sympy.combinatorics import Permutation >>> >>> N = Permutation([0,1,4,3,5,2]) >>> Q = Permutation([1,0,4,5,2,3]) >>> P = Permutation([1,2,3,4,5,0]) >>> >>> A = ((P**0)*N*(P**-0))*Q*((P**0)*~N*(P**-0)) >>> A Permutation(0, 1)(2, 5)(3, 4) >>> B = ((P**1)*N*(P**-1))*Q*((P**1)*~N*(P**-1)) >>> B Permutation(0, 4)(1, 5)(2, 3) >>> C = ((P**2)*N*(P**-2))*Q*((P**2)*~N*(P**-2)) >>> C Permutation(0, 4)(1, 3)(2, 5) >>> D = ((P**3)*N*(P**-3))*Q*((P**3)*~N*(P**-3)) >>> D Permutation(0, 5)(1, 4)(2, 3) >>> E = ((P**4)*N*(P**-4))*Q*((P**4)*~N*(P**-4)) >>> E Permutation(0, 4)(1, 2)(3, 5) >>> F = ((P**5)*N*(P**-5))*Q*((P**5)*~N*(P**-5)) >>> F Permutation(0, 3)(1, 5)(2, 4) >>> >>> A * D Permutation(0, 4, 2)(1, 5, 3) >>> B * E Permutation(1, 3)(2, 5) >>> C * F Permutation(0, 2, 1)(3, 5, 4) >>> (B * E).full_cyclic_form [[0], [1, 3], [2, 5], [4]] 3rd step: Calculate U to Z and compositions UV, VW, and TCreation of the permutations U to ZWe create the permutations U to Z which are the conjugates of the permutations A to F thanks to the permutations linked to the rotation (P).
\( U = P^{-0} \cdot A \cdot P^{0} = P^{-0} \cdot P^{0} \cdot N \cdot P^{-0} \cdot Q
\cdot P^{0} \cdot N^{-1} \cdot P^{-0} \cdot P^{0} = N \cdot P^{-0} \cdot Q \cdot
P^{0} \cdot N^{-1} = N \cdot Q \cdot N^{-1} \) We use the compositions UV, VW, ...\( UV = (N \cdot Q \cdot N^{-1}) \cdot (N \cdot P^{-1} \cdot Q \cdot P^{1} \cdot N^{-1}) \)\( VW = (N \cdot P^{-1} \cdot Q \cdot P^{1} \cdot N^{-1}) \cdot (N \cdot P^{-2} \cdot Q \cdot P^{2} \cdot N^{-1}) \) \( WX = (N \cdot P^{-2} \cdot Q \cdot P^{2} \cdot N^{-1}) \cdot (N \cdot P^{-3} \cdot Q \cdot P^{3} \cdot N^{-1}) \) \( XY = (N \cdot P^{-3} \cdot Q \cdot P^{3} \cdot N^{-1}) \cdot (N \cdot P^{-4} \cdot Q \cdot P^{4} \cdot N^{-1}) \) \( YZ = (N \cdot P^{-4} \cdot Q \cdot P^{4} \cdot N^{-1}) \cdot (N \cdot P^{-5} \cdot Q \cdot P^{5} \cdot N^{-1}) \)
We simplify (N and reverse N) and decompose the powers of P.
We add the action of \( N P^{-1} N^{-1} \) and \( N P N^{-1} \)
to each side of the equations.
We simplify again:
We recognize that the expressions to the right of = correspond to the
compositions VW, WX, XY, YZ: In the above equations, only N is unknown! Use of the permutation T
Given the permutation \( T = N P N^{-1} \), we can rewrite the equations
in the form:
Using Python to calculate U, V, ... and UV, VW, ...>>> U = A >>> V = ~P * B * P >>> W = (P**-2) * C * (P**2) >>> X = (P**-3) * D * (P**3) >>> Y = (P**-4) * E * (P**4) >>> Z = (P**-5) * F * (P**5) >>> >>> UV = U * V >>> VW = V * w >>> WX = W * X >>> XY = X * Y >>> YZ = Y * Z >>> >>> UV.full_cyclic_form [[0, 5], [1, 2], [3], [4]] >>> VW.full_cyclic_form [[0], [1, 3], [2], [4, 5]] >>> WX.full_cyclic_form [[0, 3], [1], [2, 5], [4]] >>> XY.full_cyclic_form [[0], [1, 2], [3, 4], [5]] >>> YZ.full_cyclic_form [[0, 2], [1], [3], [4, 5]] Note: the different permutations (UV, VW, ...) have the same type: 2.2.1.1. So they are conjugate. Here too we use a theorem invented by Rejewski. Calculate the permutation TWe can see that the permutations UV and VW are conjugate (as are VW and WX, ...). In this case, it is very easy to calculate the permutation T that transforms UV into VW. To do this, we write VW under UV and assume that the first line is the plaintext and the second line is the ciphertext. We write the result in the form of cycles.
UV = ((0 5)(1 2)(3)(4)) VW = ((4 5)(1 3)(0)(2)) Gives: T = ((0 4 2 3)(5)(1))
Unfortunately, UV can be written differently, for example: UV = ((1 2)(0 5)(4)(3)) VW = ((4 5)(1 3)(0)(2)) Gives: T2 = ((1 4 0)(2 5 3)) In conclusion, there are several solutions for the permutation T. Note: the number of solutions depends of type of the UV permutation. In the case of the 26-contact Enigma, C. Bauer tells us that there are 338 (13x13x2) possibilities. Verification with Python>>> T = Permutation([[5],[1],[0,4,2,3]]) >>> (~T * UV * T) == VW True >>> (~T * UV * T).full_cyclic_form [[0], [1, 3], [2], [4, 5]] >>> >>> T2 = Permutation([[1,4,0],[2,5,3]]) >>> (~T2 * UV * T2) == VW True >>> (~T2 * UV * T2).full_cyclic_form [[0], [1, 3], [2], [4, 5]] >>> Calculate UV, VW, WX, XZ
UV = ((0 5)(1 2)(3)(4)) VW = ((1 3)(4 5)(0)(2)) WX = ((0 3)(2 5)(1)(4)) XY = ((1 2)(3 4)(0)(5)) YZ = ((0 2)(4 5)(1)(3)) Finding the right TAs we have seen, there are several solutions that are compatible with the permutation T. How to find the right solution? We will calculate all the possibilities of T for two pairs of equations, for example UV/VW and WX/XY. If we find a common solution, it will be the right one!
UV = ((0 5)(1 2)(3)(4)), VW = ((4 5)(1 3)(0)(2)), T_uv_1 = ((0 4 2 3)(5)(1)) UV = ((0 5)(1 2)(3)(4)), VW = ((4 5)(1 3)(2)(0)), T_uv_2 = ((0 4)(2 3)(1)(5)) UV = ((0 5)(1 2)(3)(4)), VW = ((4 5)(3 1)(0)(2)), T_uv_3 = ((0 4 2 1 3)(5)) UV = ((0 5)(1 2)(3)(4)), VW = ((4 5)(3 1)(2)(0)), T_uv_4 = ((0 4)(1 3 2)(5)) UV = ((0 5)(1 2)(3)(4)), VW = ((1 3)(4 5)(0)(2)), T_uv_5 = ((0 1 4 2 5 3)) UV = ((0 5)(1 2)(3)(4)), VW = ((1 3)(4 5)(2)(0)), T_uv_6 = ((0 1 4)(5 3 2)) UV = ((0 5)(1 2)(3)(4)), VW = ((1 3)(5 4)(0)(2)), T_uv_7 = ((0 1 5 3)(2 4)) UV = ((0 5)(1 2)(3)(4)), VW = ((1 3)(5 4)(2)(0)), T_uv_8 = ((0 1 5 3 2 4)) UV = ((0 5)(1 2)(3)(4)), VW = ((3 1)(4 5)(0)(2)), T_uv_9 = ((0 3)(5 1 4 2)) UV = ((0 5)(1 2)(3)(4)), VW = ((3 1)(4 5)(2)(0)), T_uv_10= ((0 3 2 5 1 4)) UV = ((0 5)(1 2)(3)(4)), VW = ((3 1)(5 4)(0)(2)), T_uv_11= ((0 3)(5 1)(2 4)) UV = ((0 5)(1 2)(3)(4)), VW = ((3 1)(5 4)(2)(0)), T_uv_12= ((0 3 2 4)(5 1)) WX = ((0 3)(2 5)(1)(4)), XY = ((1 2)(3 4)(0)(5)), T_wx_1 = ((0 1)(3 2)(5 4)) WX = ((0 3)(2 5)(1)(4)), XY = ((1 2)(3 4)(5)(0)), T_wx_2 = ((0 1 5 4)(2 3)) WX = ((0 3)(2 5)(1)(4)), XY = ((1 2)(4 3)(0)(5)), T_wx_3 = ((0 1)(3 2 4 5)) WX = ((0 3)(2 5)(1)(4)), XY = ((1 2)(4 3)(5)(0)), T_wx_4 = ((0 1 5 3 2 4)) ...Bingo! The solution ((0 1 5 3 2 4)) is present in both sets of equations. We can set: \( T = N \cdot P \cdot N^{-1} = ((0\ 1\ 5\ 3\ 2\ 4)) \)
4th step: Reconstitution of the permutation N (the fast rotor)We found T (0 1 4 3 2 4), we know P (1 2 3 4 5 0). If we want to find N, we just put P under T and assume that it is the encryption of T. Of course, there are 6 possibilities depending on the starting point of the permutation P.
T = ((0 1 5 3 2 4)) T = ((0 1 5 3 2 4)) T = ((0 1 5 3 2 4)) P1= ((1 2 3 4 5 0)) P2= ((2 3 4 5 0 1)) P3= ((3 4 5 0 1 2)) N1= ((0 1 2 5 3 4)) N2= ((0 2)(1 3 5 4)) N3= ((0 3)(1 4 2)(5)) T = ((0 1 5 3 2 4)) T = ((0 1 5 3 2 4)) T = ((0 1 5 3 2 4)) P4= ((4 5 0 1 2 3)) P5= ((5 0 1 2 3 4)) P6= ((0 1 2 3 4 5)) N4= ((0 4 3 1 5)(2)) N5= ((0 5 1)(3 2)(4)) N6= ((0)(1)(5 2 4)(3)) Note: The correct solution is N6 which I used to create the examples.
>>> N6.full_cyclic_form [[0], [1], [2, 4, 5], [3]] >>> (N6 * P * ~N6).full_cyclic_form [[0, 1, 5, 3, 2, 4]]Of course, all other solutions (N1 to N5) give T. >>> N3 = Permutation([[0,3],[1,4,2],[5]]) >>> (N3 * P * ~N3).full_cyclic_form [[0, 1, 5, 3, 2, 4]] Reconstruction of the complete EnigmaRejewski concludes that at this stage of his work, any of the 26 solutions of N are equivalent (as many solutions as there are possible rotations of the rotor), and it is enough to choose any one. To find the right one, it will be necessary to have all the other wiring (the other two rotors and the reflector). Similarly, it will be necessary to know when the slow rotors turn. When everything is known, the Enigma will no longer have any secrets and we will be able to decode any message ... if we know the key of the day! Note: The steps not described by Rejewski are discussed in the article by Jiménez and Vázquez (see the reference section below). ReferencesBooks & Articles
Internet links
|