|
Enigma Home Page
The first methods
|
IntroductionIn late 1932, Rejewski reconstructed the Enigma machine. During 1933, Polish cryptanalysts were able to read Enigma messages by reconstructing the daily key. After identifying the right-hand rotor, the next step is to find the Steckers (plugboard connections). The method used is known as the "Grill" ("Grille" in French, Rost in German and "Rusztu" in Polish). This method was devised by Rejewski himself at a very early stage, even before his colleagues Zygalski and Rozycki joined him. The Grill method is not trivial; it requires great deal of trial and error. According to Rejewski, the method was simple to use only when there were only five Steckers. Principles of the Grid MethodThe PrincipleIt has been observed (see…) that indicators can be extracted from the traffic and used to derive six equations (A[0] to A[5]) corresponding to the substitutions performed by the Enigma for the six positions following the Grundstellung of the daily key.We know the details of the A equations, which involve the plugboard settings (S), the position of the right-hand rotor (P**x), the wiring of the right-hand rotor (C), and a constant (U), which remains constant provided there is no turnover and depends on the substitutions of the other rotors and the reflector. What remains unknown is the substitution S (the plugboard settings, this is what we are looking for), the constant U (though we can ignore it, as explained later), and the position x of the right-hand rotor. To find the position x of the right-hand rotor and validate the plugboard hypothesis, we create six equations F (F[0] to F[5]) derived from the A equations, in which the effect of the right-hand rotor's rotation is neutralized. Since there are only 26 possible positions, we can test them all. In the absence of plugboard settings (or once they have been deduced), the six F equations must yield the same result. This is the success criterion: the plugboard settings and the position of the right-hand rotor have been found. Note: Another advantage of this method is that the resulting F value can be entered into a catalog indexed by the Walzenlage (rotor order) and Grundstellung (once the daily key is fully determined). This catalog (the F-catalog) allows for the immediate identification of the left and middle rotors and their positions after successfully applying the Grill method to the day's traffic. Equations A and F
\( A_0 = S P^x C P^{-x} U P^x C^{-1} P^{-x} S^{-1} \)
If they are no steckers:
\( A_0 = P^x C P^{-x} U P^x C^{-1} P^{-x} \)
\( F_0 = U \) A computer programThe algorithmI wrote a program that calculates the F-equations from the A-substitutions by testing all possible positions of the right-hand rotor. The program reads a file containing the A-substitutions, the Steckers (the identity substitution is used if the Steckers are unknown), and the substitution describing the right-hand rotor (in the present case, rotor III).An example with no steckers$ more data_test.txt (ad)(bv)(cl)(et)(fq)(gu)(hy)(ip)(jx)(ko)(mr)(ns)(wz) (ah)(bt)(cw)(dq)(ek)(fg)(ir)(jv)(lo)(mz)(ns)(pu)(yx) (au)(bg)(cj)(dh)(eq)(fv)(io)(kw)(lr)(mn)(py)(st)(xz) (as)(bf)(cv)(dn)(ew)(gx)(hq)(it)(jo)(kz)(lu)(mp)(ry) (ai)(bj)(ce)(dy)(fm)(gv)(hk)(lp)(nq)(ow)(rs)(tz)(ux) (ar)(bi)(cw)(ds)(eh)(fl)(gp)(jn)(kt)(mo)(qx)(uz)(vy) (a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)(q)(r)(s)(t)(u)(v)(w)(x)(y)(z) (abdhpejt)(cflvmzoyqirwukxsg)(n) $ python permu.py data_test.txt F P (rotation) : [[abcdefghijklmnopqrstuvwxyz]] C: [[abdhpejt][cflvmzoyqirwukxsg][n]] U: [[a][b][c][d][e][f][g][h][i][j][k][l][m][n][o][p][q][r][s][t][u][v][w][x][ A[ 0 ]: [[ad][bv][cl][et][fq][gu][hy][ip][jx][ko][mr][ns][wz]] A[ 1 ]: [[ah][bt][cw][dq][ek][fg][ir][jv][lo][mz][ns][pu][xy]] A[ 2 ]: [[au][bg][cj][dh][eq][fv][io][kw][lr][mn][py][st][xz]] A[ 3 ]: [[as][bf][cv][dn][ew][gx][hq][it][jo][kz][lu][mp][ry]] A[ 4 ]: [[ai][bj][ce][dy][fm][gv][hk][lp][nq][ow][rs][tz][ux]] A[ 5 ]: [[ar][bi][cw][ds][eh][fl][gp][jn][kt][mo][qx][uz][vy]] AD: [[an][bcuxozeimyq][ds][fhrptwkjglv]] BE: [[akcopxdnr][bzfv][ehisqyulw][gmtj]] EF: [[azqhskcnobpvl][dexurfygimjwt]] calculate F for each rotation ==== Rotation x = 0 0 0 == [[aj][bh][ck][dm][er][fv][gn][il][ou][pq][st][wz][xy]] 0 1 == [[am][bo][cq][dy][ej][fs][gr][hl][iv][ku][np][tw][xz]] 0 2 == [[ae][bm][cw][ds][fp][gv][ht][ik][jr][ly][nq][ox][uz]] 0 3 == [[ah][bd][ck][ej][fz][go][in][lm][pv][qy][rs][tw][ux]] 0 4 == [[aw][bl][cx][do][ep][fv][gs][hj][iq][kt][mz][ny][ru]] 0 5 == [[ah][bt][cw][ds][ej][fq][gp][ix][ky][lz][mn][ou][rv]] ... ==== Rotation x = 6 6 0 == [[am][by][ce][dh][fz][gs][ir][jx][ku][lq][nw][op][tv]] 6 1 == [[am][by][ce][dh][fz][gs][ir][jx][ku][lq][nw][op][tv]] 6 2 == [[am][by][ce][dh][fz][gs][ir][jx][ku][lq][nw][op][tv]] 6 3 == [[am][by][ce][dh][fz][gs][ir][jx][ku][lq][nw][op][tv]] 6 4 == [[am][by][ce][dh][fz][gs][ir][jx][ku][lq][nw][op][tv]] 6 5 == [[am][by][ce][dh][fz][gs][ir][jx][ku][lq][nw][op][tv]] ==== Rotation x = 7 ...Note: The value x corresponds to the position of the right-hand rotor after the rotor advances. An example with only one Stecker
$ more data_1stec.txt (ad)(bv)(cl)(et)(fq)(gu)(hy)(ip)(jx)(ko)(mr)(ns)(wz) (ah)(bt)(cw)(dq)(ek)(fg)(ir)(jv)(lo)(mz)(ns)(pu)(yx) (au)(bg)(cj)(dh)(eq)(fv)(io)(kw)(lr)(mn)(py)(st)(xz) (as)(bf)(cv)(dn)(ew)(gx)(hq)(it)(jo)(kz)(lu)(mp)(ry) (ai)(bj)(ce)(dy)(fm)(gv)(hk)(lp)(nq)(ow)(rs)(tz)(ux) (ar)(bi)(cw)(ds)(eh)(fl)(gp)(jn)(kt)(mo)(qx)(uz)(vy) (aq)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)(r)(s)(t)(u)(v)(w)(x)(y)(z) (abdhpejt)(cflvmzoyqirwukxsg)(n) $ python permu.py data_1stec.txt F ... ==== Rotation x = 6 6 0 == [[am][by][ce][dh][fz][gs][ir][jx][ku][lq][no][pw][tv]] 6 1 == [[am][by][ce][dh][fz][gs][iq][jx][ku][lr][nw][op][tv]] 6 2 == [[am][by][ce][dh][fz][gs][ix][jr][ku][lq][nw][op][tv]] 6 3 == [[am][by][ce][dh][fu][gs][ir][jx][kz][lq][nw][op][tv]] 6 4 == [[am][by][ce][dh][fz][gs][in][jx][ku][lq][op][rw][tv]] 6 5 == [[am][by][ce][dh][fz][gk][ir][jx][lq][nw][op][su][tv]] ==== Rotation x = 7 ... Rejewski's manual methodIntroductionTo determine the Steckers, Rejewski does not calculate F directly; instead, he creates two sheets designed to slide over one another, which help him calculate the "F" substitutions by adjusting "A" substitutions until he obtains six identical "F" substitutions.The 1st sheetIt has been observed that one transitions from equations A to equations F using the following formula:\( F_0 = P^y C^{-1} P^{-y} (A_0) P^y C P^{-y} \)
The first sheet will consist of a part of the A substitution:
Ten F becomes: The sheet will contain all the value for this substitution for y = 0 to 25. In fact, the sheet will be duplicated so that the second sheet can be superimposed on the first, including for values greater than 20. The 2nd sheetThe second sheet contains six paragraph, as much as "A" substitutions. For each paragraph, we have:
MethodThe second sheet is slid over the first to test the 26 possible positions of the right-hand rotor. The "A" substitutions are modified to account for the Steckers. Once all Steckers have been accounted for, the six "F" substitutions will be identical. In addition to the Steckers settings, this process reveals the position of the right-hand rotor and the "F" substitution; the latter, when cross-referenced with the "F" catalog, makes it possible to identify the left and middle rotors.Note: The above outlines the description provided by Rejewski (see Rejewski’s report in the Reference section). A Wikipedia article provides a more precise account (see Reference section). Example
\( A_i = S \cdot P^{(x+i)} C P^{-(x+i)} U P^{(x+i)} C^{-1} P^{-(x+i)}
\cdot S^{-1} \)
$ python permu.py data_1stec.txt GRILL ... 5 5 x i w s h l p e b n t f o j m g r q d k z y c a v u A[5] ---------------------------------------------------------- 6 0 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 6 0 w j l n r p t h s y c q a u e g o m k i v x z b d f (in the openings) 6 0 f v l q t a u y p x o c r s k i d m n e g b z j h w A[0] ---------------------------------------------------------- 6 1 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 6 1 i k m q o s g r x b p z t d f n l j h u w y a c e v (in the openings) 6 1 d t w a k g f q r v e o z s l u h i n b p j c y x m A[1] ---------------------------------------------------------- 6 2 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 6 2 j l p n r f q w a o y s c e m k i g t v x z b d u h (in the openings) 6 2 e g j h a v b d o c w r n m i y u l t s q f k z p x A[2] ---------------------------------------------------------- 6 3 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 6 3 k o m q e p v z n x r b d l j h f s u w y a c t g i (in the openings) 6 3 h f v n w b x a t o z u p d j m s y q i l c e g r k A[3] ---------------------------------------------------------- 6 4 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 6 4 n l p d o u y m w q a c k i g e r t v x z b s f h j (in the openings) 6 4 n j e y c m v k q b h p f a w l i s r z x g o u d t A[4] ---------------------------------------------------------- 6 5 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 6 5 k o c n t x l v p z b j h f d q s u w y a r e g i m (in the openings) 6 5 x i w s h l p e b n t f o j m g r q d k z y c a v u A[5] ---------------------------------------------------------- 7 0 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 7 0 i k m q o s g r x b p z t d f n l j h u w y a c e v (in the openings) 7 0 f v l q t a u y p x o c r s k i d m n e g b z j h w A[0] ... The advantage of the Grill is that the F-equations are easy to calculate by hand: For example, let us find the first two transpositions associated with the letters 'a' and 'b', respectively. 1) Letter 'a': locate the letter 'a' in the substitution Z appearing in the opening (inverse rotation) and take the letter above it: M. Then take the letter from equation A (here A[0]) to get the letter 'r'. Locate this letter 'R' in the alphabet and take the letter directly below it (then the direct rotation): 'm'; this gives the transposition (am). a => M => r, R => m 2) Letter 'b': the letter 'b' in the opening is located beneath the letter 'X'. Below 'X' (in row A[0]), we get the letter 'j'. Below the letter 'J' is the letter 'y'; this gives the transposition (by). b => X => j, J => y Note:
StrategyWe have described how to verify that the solution has been found. But more concretely, what are the intermediate steps? I believe the first step is to determine the exact position of the right-hand rotor. Using my program and the 'F' option, I observed that the correct position can be detected even with six Steckers. This is because the redundancy of transpositions is maximized in this scenario; specifically, there are transpositions that remain unaffected by the Steckers. Thus, with six Steckers, at position 6, there are three (am) transpositions and an equal number of (by) transpositions.
$ more data.txt (ar)(bv)(co)(ut)(xj)(lk)(zw)(dg)(ip)(mf)(hy)(eq)(ns) (ae)(hx)(up)(ol)(wc)(dk)(yq)(if)(sn)(zm)(gb)(jv)(tr) (ad)(ye)(sg)(kw)(cj)(nm)(li)(bt)(ph)(vr)(of)(qu)(zx) (ay)(br)(cv)(uo)(xt)(lj)(zk)(dw)(ig)(mp)(hf)(qs)(ne) (an)(he)(ux)(op)(wl)(dc)(yk)(iq)(sf)(jb)(tv)(mr)(gz) (ax)(yd)(se)(kg)(cw)(nj)(lm)(bi)(pt)(vh)(or)(qf)(zu) (a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)(q)(r)(s)(t)(u)(v)(w)(x)(y)(z) (abdhpejt)(cflvmzoyqirwukxsg)(n) $ python permu.py data.txt F ... 5 5 == [[ay][bm][ck][dh][ex][fn][gt][iq][jz][lw][ov][ps][ru]] ==== Rotation x = 6 6 0 == [[ap][by][cq][dh][el][fz][gs][iv][jx][ku][mw][nt][or]] 6 1 == [[am][by][cr][dh][el][fz][gk][io][ju][nw][pq][sx][tv]] 6 2 == [[as][by][ce][dh][fm][gz][ix][jn][kw][lv][op][qt][ru]] 6 3 == [[am][bx][cq][dh][el][fu][gk][ir][jy][nv][os][pz][tw]] 6 4 == [[ah][bx][cs][dp][eg][fz][in][jy][kt][lq][mo][rw][uv]] 6 5 == [[am][bl][ce][du][fz][gk][hj][in][op][qy][rv][sx][tw]] ==== Rotation x = 7 Next, we attempt to add Steckers to obtain these majority transpositions. At each stage, we recalculate the data on "Sheet 2," incorporating the Steckers already identified. As an exercise, the reader can try to identify the single Stecker present in the previous example which illustrates the Grill. References
|