|
Enigma Home Page
The first methods
|
IntroductionIn late 1932, Rejewski reconstructed the Enigma. During 1933, Polish cryptanalysts were able to read Enigma messages by reconstructing the daily key. This page describes how the Poles identified first the right-hand rotor, that is, the rotor that advances with every encrypted letter (the "fast rotor"), and the whole Walzenlage. This method is known as the "clock method." It was created by Różycki and undoubtedly inspired Turing to develop his Banburismus method. The "clock method" itself derives from the methods of the American Friedman. Indeed, it is almost certain that Polish cryptanalysts had access to the French translation of Friedman’s work, "The Index of Coincidence and Its Applications in Cryptography", translated by General Cartier and published in 1921. The Poles were fluent in French and keenly interested in the many cryptology books published in that language (by authors such as Givierge, Bazeries, etc.). The general principleReminder: the Ringstellung conceptEach rotor features a configurable ring (the Ringstellung setting). This ring bears a notch on its side that triggers the rotation of the rotor to its left. The designers of the military Enigma (Enigma I) made the mistake of creating a different ring for each rotor. In other words, the turnover of the adjacent rotor, occurs at a different point depending on the rotor. Consequently, the ring acts as a sort of signature for the rotor. Here are the letters (as displayed in the machine's window) that trigger the turnover of the rotor that is to its left: Rotor I Q Rotor II E Rotor III V Note: Instead of specifying the letter that triggers the turnover for the next encrypted character, one can specify the letter at which the turnover actually occurs. British cryptanalysts used a mnemonic phrase to remember these letters: "Royal Flags Wave Kings Above." In the convention I use, this corresponds to Rotor I: Q, Rotor II: E, Rotor III: V, Rotor IV: J, Rotor V: Z. In the following example, the message "HELLO" is encrypted starting from the initial position TTT. The right-hand rotor is Rotor III; therefore, the middle rotor will rotate after the letter V appears in the right-hand position (TTV). Of course, the encryption result itself depends on the wiring orientation, which in turn depends on the absolute position of the rotors. This position is determined by both the letter visible in the window and the Ringstellung setting. $ echo HELLO |python3 M3.py B I II III "AQ:ED:RF:TG:YH:OL" DVK TTT c [0001] = T T U = H -> Y : H K O < M > I T R -> F [0002] = T T V = E -> D : N J T < Z > D L G -> T [0003] = T U W = L -> O : P N P < I > Y J Z -> Z [0004] = T U X = L -> O : Q D Z < T > J G W -> W [0005] = T U Y = O -> L : A F S < F > S H X -> X FTZWX Reminder: the concept of the Index of CoincidenceCryptanalysis employs a very powerful method: the Index of Coincidence (IC). By taking two ciphertexts, one can determine whether or not they were encrypted using the same key. It involves simply superimposing the two ciphertexts and counting the number of identical letters in each column. Theory shows that there will be approximately 4% (0.038) identical letters if the ciphertexts are unrelated, and around 8% (0.076) if both ciphertexts represent German texts encrypted with the same key (the percentage depends on the language used).
The method for identifying the right-hand rotorTwo messages encrypted on the same day within the same network (Army, Air Force, or SD) using slightly different starting keys can be superimposed if their message keys are known. We studied how the Poles managed to achieve this feat (finding the message key). In principle, one might expect about 8% of the letters to be identical. In reality, this depends on the right-hand rotor. In short, depending on the starting keys and the right-hand rotor, the two messages (which must have similar keys) will either be in phase or not. By measuring the IC, one can deduce whether or not a turnover of the middle rotor occurred between the two keys, and thereby identify the right-hand rotor. With a bit of luck, two messages might suffice to identify the correct rotor. In practice, however, the process is usually more complex. For example, if the messages are too short, multiple pairs of messages will be required. Even if the messages are long, the indicator settings can be ambiguous (due to standard deviations); in this case, too, multiple pairs of messages will be needed. The phenomenon explainedSuppose we have intercepted two messages encrypted with the Enigma. We have managed to determine their starting keys. We can therefore align them with respect to the right-hand rotor. Thus, if the keys are AAA and AAF, one might think it suffices to shift the second message by five positions (do not forget that the rotors advance before encryption). 1st bcdefghijklmnopqrstuvwxyzbcdefghijklmnopqrstuvwxyz 2nd ghijklmnopqrstuvwxyz...In fact, it is more complex, as one must take into account the nature of the right-hand rotor, whose Ringstellung configuration causes the middle rotor to advance (turnover). In the first case, rotor I is on the right (turnover occurs after the letter Q). The following example shows the positions of the three rotors for the two messages.
1st aaaaaaaaaaaaaaaaaaaaaa...aaaa...aaaa...
aaaaaaaaaaaaaaaabbbbbb...bccc...cddd...
bcdefghijklmnopqrstuvw...qrst...qrst...
2nd aaaaaaaaaaaaaaaaa...aaaa...aaaa...
aaaaaaaaaaabbbbbb...bccc...cddd...
ghijklmnopqrstuvw...qrst...qrst...
In this case, the messages are indeed superimposed (in-depth), and one would
expect an Index of Coincidence (IC) of 8%.
In the second case, rotor II is on the right (turnover after the letter E). Here, there are two ways to superimpose the messages, yielding different results:
1st aaaaaaaaaaaaaaaaaaaaaa...aaaa...aaaa...
aaaabbbbbbbbbbbbbbbbbb...bbbc...ccdd...
bcdefghijklmnopqrstuvw...cdef...defg...
2nd aaaaaaaaaaaaaaaaaaaaaa...aaaa...aaaa...
aaaaaaaaaaaaaaaaa...aaab...bbcc...
ghijklmnopqrstuvw...cdef...defg...
It can be seen that at no point are the messages "in-depth".
However, if the messages are offset differently, the "in-depth" messages do appear:
1st aaaaaaa...aaaa...aaaa...
aaaaabb...bbbc...ccdd...
bcdefgh...cdef...defg...
2nd aaaaaaaaaaaaaaaaaaaaaaaaaaaa...aaaa...aaaa...
aaaaaaaaaaaaaaaaaaaaaaaaaabb...bbbc...ccdd...
ghijklmnopqrstuvwxyzabcdefgh...cdef...defg...
The two tests can be distinguished: in the first case, the absence of overlap
yields a IC of around 4%, whereas in the second case (overlap), a IC of 8% is
expected.
A complete exampleA complete keyI am creating an Enigma key to generate the following examples.
Two messagesPlain-texts:$ cat MSGS/mA.txt DIEXABENTEUERXTOMXSAWYERSVONMARKXTWAINDEUTSCHXVONXHXHELLWAGVORWOR TXDESXAUTORSDIEXMEISTENXDERXHIERXERZAEHLTENXABENTEUERXHABENXSICHX TATSAECHLICHXZUGETRAGENDASXEINEXODERXDASXANDEREXHABEXICHXSELBSTXE RLEBTXDIEXANDERENXMEINESCHULKAMERADENXHUCK $ cat MSGS/mC.txt ELASSENXWERDEXHABEXICHXDOCHXDARINXVERSUCHTXIHNENXAUFANGENEHMEXWEI SEXZUXZEIGENXWASXSIEXEINSTXSELBSTXWARENXWIEXSIEXFUEHLTENDACHTENXS PRACHENXUNDXWELCHERXARTXIHRXEHRGEIZXUNDXIHREXUNTERNEHMUNGENWARENE RSTESXKAPITELTOMKEINEXANTWORTTOMACryptograms (message keys: AAA for the 1st message and AAF for the second) $ python3 M3.py B III I II "AQ:ED:RF:TE:YH:OL" DVK AAA < MSGS/mA.txt \ | python3 groupe.py RXISM JCAQJ RNGAF JEFNB YGQMO LZCJS AICRK QRCGO GHQBO QBRAS EOFZJ ZMNUY YCECE SJOHZ RZIZT TREJX TSAVZ ERQWQ OIICX QOYJG YJSKO WZZLV EMQLO OPXUP IQJEF TZPIV NCBWB FOXVF BUHRZ UYFCP JLBGS QGIQP VKJKL IKFIW ATSHS JXWGY VGLCO EVJJA TPCYM WCBGJ MFSPW NTLMM ULFTF VUGCU GKPSS OWMVY OESEA ZH $ python3 M3.py B III I II "AQ:ED:RF:TE:YH:OL" DVK AAF < MSGS/mB.txt \ | python3 groupe.py RZHUN TPCSN JEFTG FLGRQ NLIEP OGZEI TYEKW IYBCE QIQFE GYIEF VBSFN VCPOE OYYWG JAREJ SQWYB VJVER RHKAE EENEU YRQAR IHXRY MPCTJ PXRKE XOKAY TVFEJ PGJUK GVSAM QMPEX OMCVS WJXJG KFQQB SXICC EBBVU UALSR QGRFM UOESZ EBPIP PVOLJ MXCKP JZMSF QVGYM QOHEC IHKKE BWFHU MENLW SEXRZ IOM The messages are superimposedThe two messages are superimposed so that they are "in phase"; a) It is assumed that the right-hand rotor is rotor I or III. Key abcde fghij klmno pqrst uvwxy zabcd efghi jklmn opqrs tuvwx yz 1st RXIS MJCAQ JRNGA FJEFN BYGQM OLZCJ SAICR KQRCG OGHQB OQBRA SE 2nd RZHU NTPCS NJEFT GFLGR QNLIE POGZE ITYEK WIYBC EQIQF EG Coi. ** * Key abcde fghij klmno pqrst uvwxy zabcd efghi jklmn opqrs tuvwx yz 1st OFZJZ MNUYY CECES JOHZR ZIZTT REJXT SAVZE RQWQO IICXQ OYJGY JS 2nd YIEFV BSFNV CPOEO YYWGJ AREJS QWYBV JVERR HKAEE ENEUY RQARI HX Coi. * * Key abcde fghij klmno pqrst uvwxy zabcd efghi jklmn opqrs tuvwx yz 1st KOWZZ LVEMQ LOOPX UPIQJ EFTZP IVNCB WBFOX VFBUH RZUYF CPJLB GS 2nd RYMPC TJPXR KEXOK AYTVF EJPGJ UKGVS AMQMP EXOMC VSWJX JGKFQ QB Coi. * Key abcde fghij klmno pqrst uvwxy zabcd efghi jklmn opqrs tuvwx yz 1st QGIQP VKJKL IKFIW ATSHS JXWGY VGLCO EVJJA TPCYM WCBGJ MFSPW NT 2nd SXICC EBBVU UALSR QGRFM UOESZ EBPIP PVOLJ MXCKP JZMSF QVGYM QO Coi. * * Key abcde fghij klmno pqrst uvwxy zabcd efghi jklmn opqrs tuvwx yz 1st LMMUL FTFVU GCUGK PSSOW MVYOE SEAZH 2nd HECIH KKEBW FHUME NLWSE XRZIO M Coi. *b) Assume that the right-hand rotor is rotor II. Key abcde fghij klmno pqrst uvwxy zabcd efghi jklmn opqrs tuvwx yz 1st 2nd RZH UNTPC SNJEF TGFLG RQ Coi. Key abcde fghij klmno pqrst uvwxy zabcd efghi jklmn opqrs tuvwx yz 1st RXIS MJCAQ JRNGA FJEFN BYGQM OLZCJ SAICR KQRCG OGHQB OQBRA SE 2nd NLIEP OGZEI TYEKW IYBCE QIQFE GYIEF VBSFN VCPOE OYYWG JAREJ SQ Coi. * * Key abcde fghij klmno pqrst uvwxy zabcd efghi jklmn opqrs tuvwx yz 1st OFZJZ MNUYY CECES JOHZR ZIZTT REJXT SAVZE RQWQO IICXQ OYJGY JS 2nd WYBVJ VERRH KAEEE NEUYR QARIH XRYMP CTJPX RKEXO KAYTV FEJPG JU Coi. * * * * * * Key abcde fghij klmno pqrst uvwxy zabcd efghi jklmn opqrs tuvwx yz 1st KOWZZ LVEMQ LOOPX UPIQJ EFTZP IVNCB WBFOX VFBUH RZUYF CPJLB GS 2nd KGVSA MQMPE XOMCV SWJXJ GKFQQ BSXIC CEBBV UUALS RQGRF MUOES ZE Coi.* * * * * Key abcde fghij klmno pqrst uvwxy zabcd efghi jklmn opqrs tuvwx yz 1st QGIQP VKJKL IKFIW ATSHS JXWGY VGLCO EVJJA TPCYM WCBGJ MFSPW NT 2nd BPIPP VOLJM XCKPJ ZMSFQ VGYMQ OHECI HKKEB WFHUM ENLWS EXRZI OM Coi. * * * * * * Key abcde fghij klmno pqrst uvwxy zabcd efghi jklmn opqrs tuvwx yz 1st LMMUL FTFVU GCUGK PSSOW MVYOE SEAZH 2nd Coi.In the first trial, there are 9 coincidences out of 228 letters, representing an IC of 3.9%. In the second trial, there are 19 coincidences out of 237 letters, representing an IC of 8.0%. The presence of rotor II on the right is a near-certainty. Determining the other rotorsThe method just described can be used to identify the middle rotor. Admittedly, there will be fewer messages exhibiting "double stepping," but they will eventually appear if one waits long enough. It should be remembered that the rotor order is changed only every three months. Then, since there are only three rotors, only one possibility remains for the left-hand rotor. Without waiting for double stepping to occur, one can search for the plugboard settings by making two hypotheses regarding the positions of the other two rotors (the left and middle ones). Ultimately, the Poles found a faster solution by using a catalog (The F-catalog). References
|