|Substitution encryption||Cryptanalysis||How it works?||Construction|
In the transmission protocol, Germans used to send the initial rotor positions twice (these positions were composed of 3 letters). This 6-letter message had to strengthen security; however, it opened a breach in Enigma. While sending this 6-letter message, only the first rotor will turn: in fact, if the ring set for the second rotor rotation is not close to the initial position (less than 6 letters before), we can “forget” the other two rotors. Mathematically, a rotation of the first rotor means a probability of .
Rotors internal connections
Let’s consider the following example:
In this schematic, following substitutions are performed:
- A I through rotor #1.
- I K through rotor #2.
- K B through rotor #3.
- On the reflector side: B P.
- Return trip: P U H F.
Now, let’s forget rotors #2 and #3: there is a new “virtual reflector” performing the combinations made by rotor #2 + rotor #3 + the actual reflector. A given reflector is only defined by 13 substitutions. In the figure above, a partial definition would be the pair .
Now, we consider that we have a large portion on the message (here A I H F). If we have correctly identified the rotor #1 and the virtual reflector, we could only have 13 pairs in the reflector. However, if we don’t have the correct rotor #1, we will find more than 13 possible pairs and/or two opposing pairs ( and ). Nevertheless, we do not know the plaintext yet: we can verify but not discover. This hypothesis is the first search phase.
In order to understand how mathematicians bypassed this issue, we must see Polish scientists who have studied the Enigma since 1929. Moreover, Marian Rejewski found a method to discover rotors connections.
Polish scientists started by buying a commercial Enigma, taking it to pieces and seeing if they could get to a military version. Rejewski determined 6 equations which uses permutations (more details can be found here):
We set : this value is equivalent to the virtual reflector previously defined. Furthermore, these permutations are fixed during encryption. If we add an useless H interconnection, Enigma equations are:
Therefore, we have a set of equations with 4 unknowns (H, S, N and Q). We are in 1931, Rejewski is blocked: the equation set cannot be resolved…
How the French helped
In 1931, Gustave Bertrand travelled in Poland and discovered the Enigma in Rejewski’s team. Polishs were convinced that Germans would use the Enigma for military purposes. From that time, France started a collaboration with Poland and Rejewski.
One year later, Hans-Thilo Schmidt went to meet the Frenchs: he wanted to share information about the Enigma (not for free !). In november 1932, a first meeting is scheduled: Schmidt shared technical documents about Enigma construction but also daily keys. Schmidt will work for the next 10 years for Frenchs.
Nevertheless, French and British secret services were unable to use these information… On 8 December 1932, Gustave Bertrand decided to share those documents with Poland without telling them their origin. Rejewski took the keys of September and October 1932: permutations S and H were now uncovered and messages from these two months could be deciphered!
Polish did not want to decipher old messages, they wanted to decipher messages day by day. The only solution is to discover P and Q (rotors internal connections): unfortunately, it is not resolvable.
Nevertheless, we know that rotors positions are encrypted twice when a message is transmitted (for instance, a plaintext ZSFZSF).
If ZSFZSF is encrypted as TYUBGJ, it is known that T and B (after 3 rotations) represent the same plaintext letter (similarly for Y and G, U and J). Permutations can be written as follows:
A: ? T, D: ? B. B: ? Y. E: ? G. C: ? U. F: ? J
AD: T U. F: ? ? U. F: ? B. BE: Y U. F: ? ? U. F: ? G. CF: U U. F: ? ? U. F: ? J
Rejewski demonstrated that all alphabet letters are in all positions of the “message key” using only 80 messages or more. Here is a list of these 6 keys (extracted from Polish Mathematicians Finding Patterns in Enigma Messages by C. Christensen, http://www.matematiksider.dk/enigma/MAA%20article%20about%20Enigma%20.pdf):
|AUQ AMN||IND JHU||PVJ FEG||SJM SPO||WTM RAO|
|BNH CHL||JWF MIC||QGA LYB||SJM SPO||WTM RAO|
|BCT CGJ||JWF MIC||QGA LYB||SJM SPO||WTM RAO|
|CIK BZT||KHB XJV||RJL WPX||SUG SMF||WKI RKK|
|DDB VDV||KHB XJV||RJL WPX||SUG SMF||XRS GNM|
|EJP IPS||LDR HDE||RJL WPX||TMN EBY||XRS GNM|
|FBR KLE||LDR HDE||RJL WPX||TMN EBY||XOI GUK|
|GPB ZSV||MAW UXP||RFC WQQ||TAA EXB||XYW GCP|
|HNO tdD||MAW UXP||SYX SCW||USE NWH||YPC OSQ|
|HNO tdD||NXD QTU||SYX SCW||VII PZK||YPC OSQ|
|HXV TTI||NXD QTU||SYX SCW||VII PZK||ZZY YRA|
|IKG JKF||NLU QFZ||SYX SCW||VQZ PVR||ZEF YOC|
|IKG JKF||OBU DLZ||SYZ SCW||VQZ PVR||ZSJ YWG|
The same work is done as we know that all the first letters are encrypted with the same permutation: AD: A A but also B C, D V… As all letters appear in all positions, the full permutation scheme can be written:
Cycle lengths are: 2*10 letters, 2*2 letters, 2*1 letter. Rejewski used these observations to break the Enigma.
Rejewski and classic permutations theorems
Definition: a reflection A is a permutation of all the alphabet letters. Furthermore, no letter can be encrypted by itself: the reflector achieves both features.
Definition: the conjugation of Q by X is .
Theorem: the cyclic structure is invariant compared to the conjugation. Proof: we suppose that . ; therefore: .
If Q cycle is , the cycle when conjugated by P is:
Simplifying the equation
In the initial position: encrypt means applying permutation A then B, etc. After some simplifications, with . We can identify the form of a conjugation of X by S. AD has the same cycles as X: the plugboard does not add any security! AD known and will be equivalent and easily comparable.
Using the trick
Let’s write the equations of AD and BE:
We can already simplify: . We use the following theorem:
Theorem: if a permutation is even with an even number of equal length cycles, this permutation is the product of two permutations made of disjointed transpositions (cf. link).
Example: and . We can deduce that
With the technique described above, we can obtain AD, BE and CF:
In AD: 2 cycles of length 1, 1 cycle of length 2 and 2 cycles of length 10.
In BE: 2 cycles of length 1, 2 cycles of length 3 and 2 cycles of length 9.
In CF: 2 cycles of length 13.
AD, BE and CF are in the alphabet permutations set (size equal to 26).Each permutation has the same number of cycles for each length. Therefore, it exists a permutation of length 2: A, D, B, E, C and F. From this remark, we can already establish that (as) belongs to A and D and (dk) belongs to B and E.
Now, cycles of length equal to 2: we should have (br)(cw) in A and (rc)(wb) in D or (bw)(cr) in A and (wc)(rb) in D. In we apply the theorem previously defined to our example: if (a1a3a5a7)(a8 a6a4a2) is in XY, therefore (a1a2)(a3a4)(a5a6)(a7a8) is in X and (a2a3)(a4a5)(a6a7)(a8 a1) is in Y.
Now, cycles of length equal to 10: if we set that A must perform x i; then, g e, z t, etc. As we know AD, D must perform i g; then, e z, etc. Therefore, we have 10 possibilities. AD has 10*2 tests, BE 3*9 and CF 13: 7020 possibilities over , the progress is huge!
However, it is not the latest step. Germans used simple letters (AAA, ABC, QWE…).
If the enquiring reader asks how the cryptologist knows – before breaking the cipher – the preferences of the cryptographers, we can reply that the cryptologist does not know these preferences but he tries to compensate his ignorance with long tests, imagination, and sometimes with an once of luck. Rejewski, An Application of the Theory of Permutations inBreaking the Enigma Cipher, Applicationes Mathematicae, 1980.
Finally, Rejewski found the solution! We suppose that the key was aaa. In the above list, SYX appears quite often. If we write aA (a applied to A): , and .
CF is composed to 2 cycles of length 13: as a x, C and F are known. For BE, A and Y belong to two different cycles of length 3. We obtain 6 elements of B and E. Using this method, we could obtain all permutations:
|AUQ AMN||sss||IKG JKF||ddd||QGA LYB||xxx||VQZ PVR||ert|
|BNH CHL||rfv||IND JHU||dfg||RJL WPX||bbb||WTM PAO||ccc|
|BCT CGJ||rtz||JWF MIC||ooo||RFC WQQ||bnm||WKI RKK||cde|
|CIK BZT||wer||KHB XJV||lll||SYX SCW||aaa||XRS GNM||qqq|
|DDB VDV||ikl||LDR HDE||kkk||SJM SPO||abc||XOI GUK||qwe|
|EJP IPS||vbn||MAW UXP||yyy||SUG SMF||asd||XYW GCP||qay|
|FBR KLE||hjk||NXD QTU||ggg||TMN EBY||ppp||YPC OSQ||mmm|
|GPB ZSV||nml||NLU QFZ||ghj||TAA EXB||pyx||ZZY YRA||uvw|
|HNO tdD||fff||OBU DLZ||jjj||USE NWH||zui||ZEF YOC||uio|
|HXV TTI||fgh||PVJ FEG||tzu||VII PZK||eee||ZSJ YWG||uuu|
Several message keys are quite simple as expected….
At this point, we know the characteristics of A, B, C, D, E and F. From December 1932, Polishs have the keys of the two previous months. Rejewskji rewrote equations as follows:
We can see similar factors in all these equations, we multiply consecutive terms:
appears several times. We can rewrite equations as:
We can identify the conjugation with and VW. A theorem can be used to prove the limited quantity of solutions. We can find quite fast in order to satisfy all the equations. It is also a conjugated of P: we found N, the first rotor!
The next step was to find the internal connections of rotor #2 and #3. Rotors positions were changed every 3 months: Polishs manged to get the internal rotors connections for rotor II.
The latest rotor was easy to identify as for the reflector. In Janaury 1933, Polish created a fully working replica of the Enigma in its military version. Polishs gave their replica and their results to the Frenchs and Englishs only in 1939. Regardng the security breach in the message keys, it had been fixed in 1938. However, internal connections were known, reducing the security of the Enigma encryption scheme.