Grill_(cryptology)
Grill (cryptology)
Cryptology method
The grill method (Polish: metoda rusztu),[1] in cryptology, was a method used chiefly early on, before the advent of the cyclometer, by the mathematician-cryptologists of the Polish Cipher Bureau (Biuro Szyfrów) in decrypting German Enigma machine ciphers.[2] The Enigma rotor cipher machine changes plaintext characters into cipher text using a different permutation for each character, and so implements a polyalphabetic substitution cipher.
The German navy started using Enigma machines in 1926; it was called Funkschlüssel C ("Radio cipher C").[3] By 15 July 1928,[4] the German Army (Reichswehr) had introduced their own version of the Enigma—the Enigma G; a revised Enigma I (with plugboard) appeared in June 1930.[5] The Enigma I used by the German military in the 1930s was a 3-rotor machine. Initially, there were only three rotors labeled I, II, and III, but they could be arranged in any order when placed in the machine. Rejewski identified the rotor permutations by L, M, and N; the encipherment produced by the rotors altered as each character was encrypted. The rightmost permutation (N) changed with each character. In addition, there was a plugboard that did some additional scrambling.
The number of possible different rotor wirings is:
The number of possible different reflector wirings is:[6]
A perhaps more intuitive way of arriving at this figure is to consider that 1 letter can be wired to any of 25. That leaves 24 letters to connect. The next chosen letter can connect to any of 23. And so on.
The number of possible different plugboard wirings (for six cables) is:[7]
To encrypt or decrypt, the operator made the following machine key settings:[8]
- the rotor order (Walzenlage)
- the ring settings (Ringstellung)
- the plugboard connections (Steckerverbindung)
- an initial rotor position (Grundstellung)
In the early 1930s, the Germans distributed a secret monthly list of all the daily machine settings. The Germans knew that it would be foolish to encrypt the day's traffic using the same key, so each message had its own "message key". This message key was the sender-chosen initial rotor positions (e.g., YEK). The message key had to be conveyed to the recipient operator, so the Germans decided to encrypt it using the day's pre-specified daily ground setting (Grundstellung). The recipient would use the daily machine settings for all messages. He would set the Enigma's initial rotor position to the ground setting and decrypt the message key. The recipient would then set the initial rotor position to the message key and decrypt the body of the message.
The Enigma was used with radio communications, so letters were occasionally corrupted during transmission or reception. If the recipient did not have the correct message key, then the recipient could not decipher the message. The Germans decided to send the three-letter message key twice to guard against transmission errors. Instead of encrypting the message key "YEK" once and sending the encrypted key twice, the Germans doubled the message key to "YEKYEK" ("doubled key"), encrypted the doubled key with the ground setting, and sent the encrypted doubled key. The recipient could then recognize a garbled message key and still decrypt the message. For example, if the recipient received and decrypted the doubled key as "YEKYEN", then the recipient could try both message keys "YEK" and "YEN"; one would produce the desired message and the other would produce gibberish.
The encrypted doubled key was a huge cryptographic mistake because it allowed cryptanalysts to know two encipherments of the same letter, three places apart, for each of the three letters. The Polish codebreakers exploited this mistake in many ways. Marian Rejewski used the doubled key and some known daily keys obtained by a spy, to determine the wiring of the three rotors and the reflector. In addition, code clerks often did not choose secure random keys, but instead chose weak keys such as "AAA", "ABC", and "SSS". The Poles later used the doubled weak keys to find the unknown daily keys. The grill method was an early exploitation of the doubled key to recover part of the daily settings. The cyclometer and the bomba kryptologiczna were later exploitations of the doubled key.
Example message
Frode Weierud provides the procedure, secret settings, and results that were used in a 1930 German technical manual.[9][10]
Daily settings (shared secret): Wheel Order : II I III Ringstellung : 24 13 22 (XMV) Reflector : A Plugboard : A-M, F-I, N-V, P-S, T-U, W-Z Grundstellung: 06 15 12 (FOL) Operator chosen message key : ABL Enciphered starting with FOL: PKPJXI Message to send and resulting 5-letter groups of clear text: Feindliche Infanteriekolonne beobachtet. Anfang Südausgang Bärwalde. Ende 3 km ostwärts Neustadt. FEIND LIQEI NFANT ERIEK OLONN EBEOB AQTET XANFA NGSUE DAUSG ANGBA ERWAL DEXEN DEDRE IKMOS TWAER TSNEU STADT Resulting message: 1035 – 90 – 341 – PKPJX IGCDS EAHUG WTQGR KVLFG XUCAL XVYMI GMMNM FDXTG NVHVR MMEVO UYFZS LRHDR RXFJW CFHUH MUNZE FRDIS IKBGP MYVXU Z
The first line of the message is not encrypted. The "1035" is the time, "90" is number of characters encrypted under the message key, and "341" is a system indicator that tells the recipient how the message was encrypted (i.e., using Enigma with a certain daily key). The first six letters in the body ("PKPJXI") are the doubled key ("ABLABL") encrypted using the daily key settings and starting the encryption at the ground setting/Grundstellung "FOL". The recipient would decipher the first six letters to recover the message key ("ABL"); he would then set the machine's rotors to "ABL" and decipher the remaining 90 characters. Notice that the Enigma does not have numerals, punctuation, or umlauts. Numbers were spelled out. Most spaces were ignored; an "X" was used for a period. Umlauts used their alternative spelling with a trailing "e". Some abbreviations were used: a "Q" was used for "CH".
When Rejewski started his attack in 1932, he found it obvious that the first six letters were the enciphered doubled key.[11]
Key encryption
The daily key settings and ground setting will permute the message key characters in different ways. That can be shown by encrypting six of the same letter for all 26 letters:
AAAAAA -> PUUJJN BBBBBB -> TKYWXV CCCCCC -> KZMVVY DDDDDD -> XMSRQK EEEEEE -> RYZOLZ FFFFFF -> ZXNSTU GGGGGG -> QRQUNT HHHHHH -> SSWYYS IIIIII -> WNOZPL JJJJJJ -> MQVAAX KKKKKK -> CBTTSD LLLLLL -> OWPQEI MMMMMM -> JDCXUO NNNNNN -> YIFPGA OOOOOO -> LPIEZM PPPPPP -> AOLNIW QQQQQQ -> GJGLDR RRRRRR -> EGXDWQ SSSSSS -> HHDFKH TTTTTT -> BVKKFG UUUUUU -> VAAGMF VVVVVV -> UTJCCB WWWWWW -> ILHBRP XXXXXX -> DFRMBJ YYYYYY -> NEBHHC ZZZZZZ -> FCEIOE
From this information, the permutations for each of the six message keys can be found. Label each permutation A B C D E F. These permutations are secret: the enemy should not know them.
Notice the permutations are disjoint transpositions.[further explanation needed] For the A permutation, it not only changes "A" into "P" but it also changes "P" into "A". That allows the machine to both encrypt and decrypt messages.
Augustin-Louis Cauchy introduced two-line notation in 1815 and cycle notation in 1844.[12][13][14]
Rejewski made an incredible discovery. Without knowing the plugboard settings, the rotor positions, the ring settings, or the ground setting, he could solve for all the daily message keys. All he needed were enough messages and some code clerks using non-random message keys.
The message key is three characters long, so the doubled key is six characters long. Rejewski labeled the permutations for the successive message-key characters A B C D E F. He did not know what those permutations were, but he did know that A and D permutations encrypted the same message key letter, that B and E encrypted the same letter, and that C and F encrypted the same letter. If pi are the (unknown) plaintext letters of the message key and ci are the corresponding (known) ciphertext letters, then
The equations can be post multiplied by D, E, and F respectively to simplify the right hand sides:
The plaintext values are unknown, so those terms are just dropped to leave:
The above equations describe a path through the permutations. If c1 is passed through the inverse of A, then it produces p1. If that character passes through D, then the result is c4.
Rejewski also knew that the Enigma permutations were self inverses: Enigma encryption and decryption were identical. That means that A A = I where I is the identity permutation. Consequently, A=A−1. Thus:
The above equations show the relationship between the doubled key characters. Although Rejewski did not know the individual permutations A B C D E F, a single message told him how specific characters were permuted by the composed permutations AD, BE, and CF.
From many messages, Rejewski could determine the composed permutations completely. In practice, about 60 messages were needed to determine the permutations.[15]
Rejewski recorded the three permutations with a cyclic notation he called the characteristic. Rejewski (1981, p. 217) gives an example:
In this notation, the first cycle of permutation AD would map d to v, v to p, p to f, ..., y to o, and o would wrap around to d.
Marks and Weierud give an example from Alan Turing that shows these cycles can be completed when some information is incomplete.[16]
Furthermore, Enigma permutations were simple transpositions, which meant that each permutation A B C D E F only transposed pairs of characters. Those character pairs had to come from different cycles of the same length. Moreover, any one pairing between two cycles determined all the other pairs in those cycles. Consequently, permutations A and D both had to transpose a and s because (a) and (s) are the only cycles of length one and there is only one way to pair them. There are two ways to match (bc) and (rw) because b must pair with either r or w. Similarly, there are ten ways to match the remaining ten-character cycles. In other words, Rejewski now knew that there were only twenty possibilities for the permutations A and D. Similarly, there were 27 candidates for B and E, and 13 candidates for C and F.[17]
Weak keys
At this point, the Poles would exploit weaknesses in the code clerks' selection of message keys to determine which candidates were the correct ones. If the Poles could correctly guess the key for a particular message, then that guess would anchor two cycles in each of the three characteristics.
The Poles intercepted many messages; they would need about 60 messages in the same daily key to determine the characteristic, but they may have many more. Early on, Rejewski had identified the six characters that made up the message key.[18] If the code clerks were choosing random message keys, then one would not expect to see much correlation in the encrypted six characters. However, some code clerks were lazy. What if, out of a hundred messages, there were five messages from five different stations (meaning five different code clerks) that all used the same message key "PUUJJN"?[19] That they all came up with the same key suggests they used a very simple or very common key. The Poles kept track of different stations and how those stations would choose message keys. Early on, clerks often used simple keys such as "AAA" or "BBB".[20]
The end result was that without knowing the Enigma's plugboard settings, the rotor positions, or the ring settings, Rejewski determined each of the permutations A B C D E F, and hence all of the day's message keys.[21][22]
Initially, Rejewski used the knowledge of permutations A B C D E F (and a manual obtained by a French spy) to determine the rotor wirings. After learning the rotor wirings, the Poles used the permutations to determine the rotor order, plugboard connections, and ring settings through further steps of the grill method.
Continuing the 1930 example
Using the daily key in the 1930 technical manual above, then (with enough messages) Rejewski could find the following characteristics:
Although there are theoretically 7 trillion possibilities for each of the A B C D E F permutations, the characteristics above have narrowed the A and D permutations to just 13 possibilities, B and E to just 30 possibilities, and C and F to just 20 possibilities. The characteristic for CF has two singleton cycles, (e) and (z).[23] Those singleton cycles must pair in the individual permutations, so the characteristic for CF implies that the "E" and "Z" exchange in both the C and F permutations.
The pairing of "E" and "Z" can be checked in the original (secret) permutations given above.
Rejewski would now know that indicators with the pattern "..E..E" were from a message key of "..Z"; similarly an indicator of "..Z..Z" were from a message key of "..E". In the day's traffic, he might find indicators such as "PKZJXZ" or "RYZOLZ"; might one of these indicators be the common (lazy) message key "EEE"? The characteristic limits the number of possible permutations to a small number, and that allows some simple checks. "PKZJXZ" cannot be "EEE" because it requires "K" and "E" to interchange in B, but both "K" and "E" are part of the same cycle in BE: (kxtcoigweh).[24] Interchanging letters must come from distinct cycles of the same length. The repeating key could also be confirmed because it could uncover other repeating keys.[24]
The indicator "RYZOLZ" is a good candidate for the message key "EEE", and it would immediately determine both permutations A and D. For example, in AD, the assumed message key "EEE" requires that "E" and "R" interchange in A and that "E" and "O" interchange in D.
If "E" interchanges with "R" in A (notice one character came from the first cycle in AD and the other character came from the second cycle), then the letter following "E" (i.e. "D") will interchange with the letter preceding "R" (i.e. "X") .
That can be continued to get all the characters for both permutations.
This characteristic notation is equivalent to the expressions given for the 1930 permutations A and D given above by sorting the cycles so that the earliest letter is first.
The guessed message key of "EEE" producing indicator "RYZOLZ" would also determine the pairing of the 10-long cycles in permutation BE.
That determines most of B and E, and there would only be three possible variations left that pair (ujd) and (mqa). There are still 20 possible variations for C and F. At this point, the Poles could decrypt all of the first and fourth letters of the daily keys; they could also decrypt 20 out 26 of the second and fifth letters. The Poles' belief in these permutations could be checked by looking at other keys and seeing if they were typical keys used by code clerks.
With that information, they could go looking for and find other likely weak message keys that would determine the rest of the A B C D E F permutations. For example, if the Poles had an indicator "TKYWXV", they could decrypt it as "BB.BB."; checking the cycles for CF would reveal that the indicator is consistent with message key "BBB".
Rejewski modeled the machine as permutation made from permutations of plugboard (S), the wiring from the keyboard/lamps to the rotors (H), the three rotors (LMN), and the reflector (R). The permutation for each position of the doubled key was different, but they were related by a permutation P that represented a single step of a rotor (P is known). Rejewski assumed that the left and middle rotors did not move while encrypting the doubled key. The six letters of the doubled key consequently see the permutations A B C D E F:[25]
Rejewski simplified these equations by creating Q as a composite reflector made from the real reflector and two leftmost rotors:
Substitution produces:
The result is six equations in four unknowns (S H N Q).[26] Rejewski had a commercial Enigma machine, and he initially thought that H would be the same. In other words, Rejewski guessed that
Later, Rejewski realized that guess was wrong. Rejewski then guessed (correctly) that H was just the identity permutation:
That still left three unknowns. Rejewski comments:
- So I had a set of six equations in three unknowns, S, N, and Q. While I puzzled over how to solve that set of equations, on December 9, 1932, completely unexpectedly and at the most opportune moment, a photocopy of two tables of daily keys for September and October 1932 was delivered to me.[26]
Having the daily keys meant that S was now known. The known permutations were moved to the left side in the equations by premultiplying and post multiplying.
The leftmost and rightmost P permutations on the right-hand side (which were also known) were moved to the left; the results were given the variable names U V W X Y Z:
Rejewski then multiplied each equation with the next:
Next, Rejewski eliminated the common subexpression (Q P−1 Q P) by substituting its value obtained from the previous product.[27]
The result is a set of four equations in just one unknown: NPN−1.
Back to 1930 example
For the 1930 example above,
ABCDEFGHIJKLMNOPQRSTUVWXYZ A ptkxrzqswmcojylagehbvuidnf B ukzmyxrsnqbwdipojghvatlfec C uymsznqwovtpcfilgxdkajhrbe D jwvrosuyzatqxpenldfkgcbmhi E jxvqltnypaseugzidwkfmcrbho F nvykzutslxdioamwrqhgfbpjce
are transformed to the U V W X Y Z permutations:
ABCDEFGHIJKLMNOPQRSTUVWXYZ U gkvlysarqxbdptumihfnoczjew V gnfmycaxtrzsdbvwujliqophek W uekfbdszrtcyqxvwmigjaopnlh X jelfbdrvsaxctqyungimphzkow Y ltgmwycsvqxadzrujohbpiekfn Z mskpiyuteqcravzdjlbhgnxwfo
and then multiplied to produce the five successive products:
ABCDEFGHIJKLMNOPQRSTUVWXYZ UV = azoselgjuhnmwiqdtxcbvfkryp = (a)(e)(g)(y)(hj)(rx)(bzpdscoqt)(flmwkniuv) VW = sxdqlkunjihgfeopatyrmvwzbc = (o)(p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn) WX = pbxdefiwgmlonkhztsrajyuqcv = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)(hwujmnklo) XY = qwaytmoihlkgbjfpzcvdusnxre = (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)(bwnjlgofm) YZ = rhuaxfkbnjwmpolgqztsdeicyv = (f)(j)(q)(y)(bh)(st)(arzvexcud)(gkwinolmp)
Now the goal is to find the single structure preserving map that transforms UV to VW, VW to WX, WX to XY, and XY to YZ. Found by subscription of cycle notation.[clarification needed] When UV maps to VW, the map must mate cycles of the same length. That means that (a) in UV must map to one of (o)(p)(v)(w) in VW. In other words, a must map to one of opvw. These can be tried in turn.
UV = (a)(e)(g)(y)(hj)(rx)(bzpdscoqt)(flmwkniuv) VW = (o) (p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn) VW = (o)(p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn) WX = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)(hwujmnklo) WX = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)(hwujmnklo) XY = (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)(bwnjlgofm) XY = (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)(bwnjlgofm) YZ = (f)(j)(q)(y)(bh)(st)(arzvexcud)(gkwinolmp)
But a must map the same to o in each pairing, so other character mappings are also determined:
UV = (a)(e)(g)(y)(hj)(rx)(bzpdscoqt)(flmwkniuv) VW = (o) (p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn) VW = (o)(p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn) WX = (ohwujmnkl) (b)(d)(e)(f)(gi)(rs)(apzvycxqt) WX = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)(hwujmnklo) XY = (ofmbwnjlg) (k)(p)(u)(x)(hi)(sv)(aqzetdyrc) XY = (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)(bwnjlgofm) YZ = (olmpgkwin) (f)(j)(q)(y)(bh)(st)(arzvexcud)
Consequently, the character maps for sybxzcdq, pzvycxqt, and qzetdyrc are discovered and consistent. Those mappings can be exploited:
UV = (a)(e)(g)(y)(hj)(rx)(bzpdscoqt)(flmwkniuv) VW = (o)(p) (w) (ij)(umfkhnelg)(xzcdqasyb) (v)(rt) VW = (o)(p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn) WX = (f)(b) (ig)(ohwujmnkl)(pzvycxqta) (d)(e)(rs) WX = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)(hwujmnklo) XY = (u)(k)(p) (ih)(ofmbwnjlg) (x)(sv)(aqzetdyrc) XY = (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)(bwnjlgofm) YZ = (f) (j) (hb)(olmpgkwin)(udarzvexc) (q)(y)(st)
Which determines the rest of the map and consistently subscribes:
UV = (a)(e)(g)(y)(hj)(rx)(bzpdscoqt)(flmwkniuv) VW = (o)(p)(v)(w)(tr)(ij)(umfkhnelg)(xzcdqasyb) VW = (o)(p)(v)(w)(ij)(rt)(asybxzcdq)(elgumfkhn) WX = (e)(f)(b)(d)(sr)(ig)(ohwujmnkl)(pzvycxqta) WX = (b)(d)(e)(f)(gi)(rs)(apzvycxqt)(hwujmnklo) XY = (u)(k)(p)(x)(vs)(ih)(ofmbwnjlg)(tdyrcaqze) XY = (k)(p)(u)(x)(hi)(sv)(aqzetdyrc)(bwnjlgofm) YZ = (q)(f)(y)(j)(ts)(hb)(olmpgkwin)(udarzvexc)
The resulting map with successive subscriptions:
resulting map: ABCDEFGHIJKLMNOPQRSTUVWXYZ
ounkpxvtsrqzcaeflihgybdjwm = (aoepfxjrishtgvbuywdkqlzmcn)
UV = (a)(e)(g)(y)(hj)(rx)(bzpdscoqt)(flmwkniuv)
VW = (o)(p)(v)(w)(tr)(ij)(umfkhnelg)(xzcdqasyb)
WX = (e)(f)(b)(d)(gi)(sr)(ycxqtapzv)(jmnklohwu)
XY = (p)(x)(u)(k)(vs)(hi)(wnjlgofmb)(rcaqzetdy)
YZ = (f)(j)(y)(q)(bh)(ts)(darzvexcu)(inolmpgkw)
The map gives us NPN−1, but that is also congugate (structure preserving). Consequently, the 26 possible values for N are found by subscribing P in 26 possible ways.
The model above ignored the right rotor's ring setting (22) and ground setting (12), both of which were known because Rejewski had the daily keys. The ring setting has the effect of counterrotating the drum by 21; the ground setting advances it by 11. Consequently, the rotor rotation is -10, which is also 16.
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Straight ounkpxvtsrqzcaeflihgybdjwm
Shifted gpsquvbyxwortzmcekdafnljih = (agbpcsdqeufvnzhyixjwlrkomt)
subscribe P in different ways: (abcdefghijklmnopqrstuvwxyz)
(bcdefghijklmnopqrstuvwxyza) * actual rotor wiring
(cdefghijklmnopqrstuvwxyzab)
...
(zabcdefghijklmnopqrstuvwxy)
rotor * ABCDEFGHIJKLMNOPQRSTUVWXYZ
bdfhjlcprtxvznyeiwgakmusqo
The physical grill[clarification needed] was used to determine both the rightmost rotor, its initial position, and the plugboard settings.
Bottom sheet
Rejewsky observed that S is close to the identity permutation (in the early 1930s, only 12 of 26 letters were affected by the plugboard). He moved everything but Q to the left side of the equations by premultiplying or postmultiplying. The resulting system of equations is:
At his point, Q is unknown, but it is the same for each equation. Rejewski does not know N, but he knows it is one of the rotors (I, II, and III), and he knows the wiring for each of those rotors. There were only three rotors and 26 possible initial rotations. Consequently, there are only 84 possible values for N. Rejewski can look at each possible value to see if the Q permutation is consistent. If there were no steckers (S were the identity), then each equation would produce the same Q.
Consequently, he made one bottom sheet for each possible rotor (three sheets). Each bottom sheet consisted of 31 lines (26 + 5 to make six lines contiguous). Each line contained the stepped permutation of a known rotor.[28] For example, a suitable bottom sheet for rotor III is,
In the early 1930s, the rotor order was the same for a month or more, so the Poles usually knew which rotor was in the rightmost position and only needed to use one bottom sheet. After 1 November 1936, the rotor order changed every day. The Poles could use the clock method to determine the rightmost rotor, so the grill would only need to examine that rotor's bottom sheet.[29]
Top sheet
For the top sheet, Rejewski wrote the six permutations A through F.
A: abcdefghijklmnopqrstuvwxyz srwivhnfdolkygjtxbapzecqmu (..slit......................) ... F: abcdefghijklmnopqrstuvwxyz wxofkduihzevqscymtnrglabpj (..slit......................)
There were six slits so the permutations on the bottom sheet would show through at the proper place.
The top sheet would then be slid through all possible positions of rotor N, and the cryptanalyst would look for consistency with some unknown but constant permutation Q. If there is not a consistent Q, then the next position is tried.
Here's what the grill would show for the above permutations at its consistent alignment:
A: abcdefghijklmnopqrstuvwxyz ptkxrzqswmcojylagehbvuidnf 17 fpjtvdbzxkmoqsulyacgeiwhnr (visible through slit) B: abcdefghijklmnopqrstuvwxyz ukzmyxrsnqbwdipojghvatlfec 18 oisucaywjlnprtkxzbfdhvgmqe (visible through slit) C: abcdefghijklmnopqrstuvwxyz uymsznqwovtpcfilgxdkajhrbe 19 hrtbzxvikmoqsjwyaecguflpdn (visible through slit) D: abcdefghijklmnopqrstuvwxyz jwvrosuyzatqxpenldfkgcbmhi 20 qsaywuhjlnprivxzdbftekocmg (visible through slit) E: abcdefghijklmnopqrstuvwxyz jxvqltnypaseugzidwkfmcrbho 21 rzxvtgikmoqhuwycaesdjnblfp (visible through slit) F: abcdefghijklmnopqrstuvwxyz nvykzutslxdioamwrqhgfbpjce 22 ywusfhjlnpgtvxbzdrcimakeoq (visible through slit)
In permutation A, the cryptanalyst knows that (c k) interchange. He can see how rotor III would scramble those letters by looking at the first line (the alphabet in order) and the line visible through the slit. The rotor maps c into j and it maps k into m. If we ignore steckers for the moment, that means permutation Q would interchange (j m). For Q to be consistent, it must be the same for all six A B C D E F permutations.
Look at the grill near permutation D to check if its Q also interchanges (j m). Through the slit, find the letter j and look in the same column two lines above it to find h. That tells us the rotor, when it has advanced three positions, now maps h into j. Similarly, the advanced rotor will map y into m. Looking at permutation D, it interchanges (h y), so the two tests are consistent.
Similarly, in permutation A, the (d x) interchange and imply that (t h) interchange in Q. Looking at permutation E, (e l) interchange and also imply that (t h) interchange in Q.
All such tests would be consistent if there were no steckers, but the steckers confuse the issue by hiding such matches. If any of the letters involved in the test is steckered, then it will not look like a match.
The effect of the rotor permutation can be removed to leave the Q implied by the A B C D E F permutations. The result (along with the actual value of Q) is:
-: ABCDEFGHIJKLMNOPQRSTUVWXYZ Q(A): vyzrilptemqfjsugkdnhoaxwbc Q(B): myqvswpontxzaihgcuejrdfkbl Q(C): vcbrpmoulxwifzgeydtshakjqn Q(D): kyirhulecmagjqstndopfzxwbv Q(E): vemgbkdtwufzcxrysoqhjainpl Q(F): wvlrpqsmjizchtuefdgnobayxk Q : vyqrpkstnmfzjiuecdghoaxwbl (this actual Q is unknown to the cryptanalyst)
Most of the letters in an implied permutation are incorrect. An exchange in an implied permutation is correct if two letters are not steckered. About one half the letters are steckered, so the expectation is only one fourth of the letters in an implied permutation are correct. Several columns show correlations; column A has three v characters, and (a v) interchange in the actual Q; column D has four r characters, and (d r) interchange in Q.[30]
Rejewski (1981, p. 222) describes the possibility of writing down the six implied Qs for all 26 possible rotor positions. Rejewski states, "If permutation S actually were the identity, then ... for a particular [initial position] we would obtain the same value for all expressions Q and in this way we would find the setting of drum N. Permutation S does exist, however, so for no [initial position] will the expression Q be equal to each other, but among them will be a certain similarity for a particular [initial position], since permutation S does not change all the letters."
Rejewski states that writing down all the possible Q "would be too laborious", so he developed the grill (grid) method.[28] "Next, the grid is moved along the paper on which the drum connections are written until it hits upon a position where some similarities show up among the several expression Q. ... In this way the setting of drum N and the changes resulting from permutation S are found simultaneously. This process requires considerable concentration since the similarities I mentioned do not always manifest themselves distinctly and can be very easily overlooked."[28] The reference does not describe what techniques were used. Rejewski did state that the grill method required unsteckered pairs of letters.[31]
Permutation A has the exchanges (ap)(bt)(ck).... If we assume the exchange (ap) is unsteckered, that implies Q exchanges (fl). The other five permutations B C D E F can be quickly checked for an unsteckered pair that is consistent with Q interchanging (fl) — essentially checking column F for other rows with l without computing the entire table. None are found, so (ap) would have at least one stecker so the assumption it is unsteckered is abandoned. The next pair can be guessed as unsteckered. The exchange (bt) implies Q exchanges (pg); that is consistent with (lw) in B, but that guess fails to pan out because t and w are steckered.
A: b↔t B: l↔w C: k←t D: x→m E: m→u F: j←x ↓ ↓ ↓ ↓ * ↑ ↑ * ↑ * * ↑ b t l w x t k z z f j k ↓ ↓ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ Q: p↔g p↔g p↔g p↔g p↔g p↔g guessing (b)(t) unsteckered in S leads to the guess (l)(w) unsteckered in S C finds stecker (k x) D finds stecker (z m) E finds stecker (f u) F finds (j)
Following those guesses ultimately leads to a contradiction:
A: f↔z B: m→d C: p←l D: f→s E: p!x F: ↓ ↓ ↑ * * ↑ ↑ * ↑ ↑ u m z y r l u a r k ↓ ↓ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ Q: e↔q e↔q e↔q e↔q e↔q e↔q exploit (f z) in A leads to (e q) exchange in Q B finds (d y) steckered C finds (p r) steckered D finds (a s) steckered E finds (p x) steckered - but p is already steckered to r! failure
The third exchange (ck) implies Q exchanges (jm); this time permutation D with an unsteckered (hy) would be consistent with Q exchanging (jm).
A: c↔k B: C: D: h↔y E: F: ↓ ↓ ↑ ↑ c k i x n j h y u i g u ↓ ↓ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ Q: j↔m j↔m j↔m j↔m j↔m j↔m guessing (c)(y) unsteckered in S leads to the guess (h)(y) unsteckered in S
At this point, the guess is that the letters chky are unsteckered. From that guess, all the steckers can be solved for this particular problem. The known (assumed) exchanges in S are used to find exchanges in Q, and those exchanges are used to extend what is known about S.
Using those unsteckered letters as seeds finds (hy) interchange in E and implies (kf) is in Q; similarly (cy) interchange in F and implies (uo) is in Q. Examining (uo) in the other permutations finds (tu) is a stecker.
A: B: C: D: E: h↔y F:
↓ ↓
j a o s i v v s h y w e
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑
Q: k↔f k↔f k↔f k↔f k↔f k↔f
exploit (hy) in E
A: B: C: t←k D: E: F: c↔y
* ↑ ↓ ↓
o l d a u k f w m j c y
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑
Q: u↔o u↔o u↔o u↔o u↔o u↔o
exploit (cy) in F shows (tu) are in S
That adds letters tu to the seeds. Those letters were also unknown above, so further information can be gleaned by revisiting: S also has (g)(if)(x).
A: c↔k B: f→x C: D: h↔y E: t→f F: g←t ↓ ↓ ↑ * ↑ ↑ ↑ * * ↑ c k i x n j h y u i g u ↓ ↓ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ Q: j↔m j↔m j↔m j↔m j↔m j↔m knowing (tu) in S leads to (g)(if) in S then (if) in S can be used to find (x) in S
Revisit (kf)(uo) in Q gives more information:
A: B: o←p C: f→n D: n→p E: h↔y F: z→e
* ↑ ↑ * ↑ * ↓ ↓ ↑ *
j a o s i v v s h y w e
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑
Q: k↔f k↔f k↔f k↔f k↔f k↔f
exploit (if) in S leads to (nv) in S
(nv) in S leads to stecker (ps)
(ps) in S leads to (o)
(wz) in S leads to (e)
A: o→l B: C: t←k D: i→z E: F: c↔y
↑ * * ↑ ↑ * ↓ ↓
o l d a u k f w m j c y
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑
Q: u↔o u↔o u↔o u↔o u↔o u↔o
exploit (if) in S leads to stecker (wz) in S
(o) in S leads to (l) in S
Another revisit fully exploits (jm):
A: c↔k B: f x C: v→j D: h↔y E: t→f F: g←t ↓ ↓ ↑ * ↑ * ↑ ↑ ↑ * * ↑ c k i x n j h y u i g u ↓ ↓ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ Q: j↔m j↔m j↔m j↔m j↔m j↔m knowing (nv) in S leads to (j) in S
That addition fills out even more:
A: j→m B: o←p C: f→n D: n→p E: h↔y F: z→e ↑ * * ↑ ↑ * ↑ * ↓ ↓ ↑ * j a o s i v v s h y w e ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑ Q: k↔f k↔f k↔f k↔f k↔f k↔f exploit (j) in S leads to (am) in S A: o→l B: d←m C: t←k D: i→z E: a↔j F: c↔y ↑ * * ↑ * ↑ ↑ * ↑ ↑ ↓ ↓ o l d a u k f w m j c y ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↓ ↓ ↑ ↑ Q: u↔o u↔o u↔o u↔o u↔o u↔o exploit (j)(am) in S leads to (d) in S Q = ( (fk)(jm)(ou)... ) missing 10 pairings S = ( (am)(c)(d)(fi)(g)(h)(j)(k)(l)(nv)(o)(ps)(tu)(wz)(x)(y)... ) 22 characters so far: missing beqr have found all 6 steckers, so (b)(e)(q)(r)
All of S is now known after examining 3 exchanges in Q. The rest of Q can be found easily.
When a match is found, then the cryptanalyst would learn both the initial rotation of N and the plugboard (Stecker) permutation S.[28]
At this point, the rotor positions for the Q permutation is not known. That is, the initial positions (and possibly the order) of rotors L and M are not known. The Poles applied brute force by trying all possible initial positions (262 = 676) of the two rotors.[28] With three rotors, knowing which rotor was at position N meant there were only two possible ways to load the other two rotors.
Later, the Poles developed a catalog of all the Q permutations. The catalog was not large: there were six possible combinations of two left rotors with 262=676 initial settings, so the catalog had 4,056 entries. After using the grill, the Poles would look up Q in the catalog to learn the order and initial positions of the other two rotors.[29]
Initially, the Germans changed the rotor order infrequently, so the Poles would often know the rotor order before they began working. The rotor order changed every quarter until 1 February 1936. Then it changed every month until 1 November 1936, when it was changed daily.[29]
The cryptanalyst now knew the plugboard, the rotor order, and the absolute setting of the rotors for the doubled key, but he did not know the ring setting. He also knew what the message key setting should be, but that setting was useless without knowing the ring setting. The ring setting could be anything, and that meant the Poles did not know how to position the rotors for the message body. All the work up to this point had focussed on exploiting the doubled key. To determine the ring setting, the attention now shifted to the actual message.
Here, the Germans had made another mistake. Each message usually started with the text "ANX", which was German an meaning "to:" with the "X" meaning space. The Poles applied brute force here, too. They would go through up to 263 = 17,576 settings to find settings that produced "ANX". Once found, the cryptanalyst would use the absolute setting of the rotors to determine the ring setting. The entire daily key was thus recovered.
Later, the Poles refined the brute force search technique. By examining some messages, they could determine the position of the rightmost rotor; consequently, only 676 rotor positions would have to be tried. Rejewski no longer remembers how this trick worked.[32]
The grill method is described by Marian Rejewski as being "manual and tedious"[2] and, like the later cryptologic bomb, as being "based... on the fact that the plug connections [in the Enigma's commutator, or "plugboard"] did not change all the letters." Unlike the bomb, however, "the grill method required unchanged pairs of letters [rather than] only unchanged letters."[31]
Initially, the plugboard only swapped six pairs of letters. That left more than half of the alphabet unaffected by permutation S. The number of steckers changed 1 August 1936; then it could be from five to eight pairs of letters were swapped.[33] The extra swapped characters reduced the effectiveness of the grid method, so the Poles started looking for other methods. The result was the cyclometer and corresponding card catalog; that method was immune to steckers.
The grill method found application as late as December 1938 in working out the wiring in two Enigma rotors newly introduced by the Germans. (This was made possible by the fact that a Sicherheitsdienst net, while it had introduced the new drums IV and V, continued using the old system for enciphering the individual message keys.)[34]
On 15 September 1938, most German nets stopped encrypting the doubled key with a common setting (the ground setting). The Poles had been able to take advantage of all messages in a net using the same machine settings to encrypt the doubled key. Now most nets stopped doing that; instead, the operator would choose his own ground setting and send it in the clear to the recipient.[35] This change frustrated the grill method and the cyclometer card catalog. One net, the Sicherheitsdienst (SD) net, continued to use a common ground setting, and that net was used to reverse engineer new rotors (IV and V) that were introduced.[36] The SD net traffic was doubly encoded, so the ANX method would not work.[37] The grill method would sometimes fail after the Germans increased the number of plugboard connections to ten on 1 January 1939. When the SD net switched to the new message-key protocol on 1 July 1939, the grill method (and the cyclometer method) were no longer useful.[36]
Here's an example of the new message procedure for a message on 21 September 1938.[38]
2109 -1750 - 3 TLE - FRX FRX - 1TL -172= HCALN UQKRQ AXPWT WUQTZ KFXZO MJFOY RHYZW VBXYS IWMMV WBLEB DMWUW BTVHM RFLKS DCCEX IYPAH RMPZI OVBBR VLNHZ UPOSY EIPWJ TUGYO SLAOX RHKVC HQOSV DTRBP DJEUK SBBXH TYGVH GFICA CVGUV OQFAQ WBKXZ JSQJF ZPEVJ RO -
The "3 TLE" (German Teile, parts) says it is a 3-part message; the "1TL" (German Teil, part) says this is the first part; the "172" says there are 172 characters in the message (including the message key). For this message, the ground setting "FRX" is transmitted twice in the clear; the ground setting would/should be different for every message on net. Consequently, the Poles could not find the needed sixty message keys encrypted under the same ground setting. Without the same-key message volume, they could not determine the characteristic, so they could not determine the permutations A B C D E F or use the grill. For this message, the daily settings (rotor order, plugboard, and ring settings) were used with "FRX" to decrypt the first six characters ("HCALN U") to obtain the doubled message key ("AGIAGI").
To decrypt these messages, the Poles used other techniques to exploit the doubled message key.
- Marian Rejewski, Mathematical Solution of the Enigma Cipher, trans Christopher Kasparek, Cryptologia, Vol 6, Number 1, pp 1–18 at 17, January 1982
- Rejewski 1984e, p. 290
- Kruh & Deavours 2002, p. 97.
- Rejewski 1981, p. 215 Take the number of ways to arrange 26 distinct letters (26!) and pair the selected letters. The paired letters interchange, so divide by 213 to account for the two orderings of each pair. The order the pairs are enumerated does not matter, so divide by the number of ways to order the 13 pairs (13!).
- Rejewski 1981, p. 216 Take the number of ways to arrange 26 distinct letters and pair off the first 12 letters; divide by 26 because the pairs can be swapped (AB is same as BA), divide by 6! because the order of the pairs does not matter, and divide by 14! because the order of the trailing 14 characters does not matter.
- Lisicki 1979, p. 68, Bild 1, Beispiel (Example)
- "Frode Weierud's CryptoCellar | Enigma Test Message from 1930". Archived from the original on 2014-10-30. Retrieved 2014-10-07., citing 1930 "Schlüsselanleitung zur Chiffriermachine Enigma I" ["Directions for use of Keys on the Cypher Machine 'Enigma I'"]
- Rejewski 1981, p. 217 stating, "The fact that the first six letters of each message formed its three-letter key, twice enciphered, was obvious, and I will not dwell on the matter."
- Wussing, Hans (2007), The Genesis of the Abstract Group Concept: A Contribution to the History of the Origin of Abstract Group Theory, Courier Dover Publications, p. 94, ISBN 9780486458687,
Cauchy used his permutation notation—in which the arrangements are written one below the other and both are enclosed in parentheses—for the first time in 1815.
- Harkin, Anthony A.; Harkin, Joseph B. (April 2004), "Geometry of Generalized Complex Numbers" (PDF), Mathematics Magazine, 77 (2): 118–129, doi:10.1080/0025570X.2004.11953236, S2CID 7837108 at page 129 implies both notations used in 1815.
- Cauchy, Augustin-Louis (1987), "Augustin Louis Cauchy on the Theory of Permutations", in Fauvel, John; Gray, Jeremy (eds.), The History of Mathematics: A Reader, Macmillan Press in association with The Open University, pp. 506–507, ISBN 9780333427910
- Rejewski 1981, p. ??
- Marks, Philip; Weierud, Frode (January 2000), "Recovering the Wiring of Enigma's Umkehrwalze A" (PDF), Cryptologia, 24 (1): 55–66, CiteSeerX 10.1.1.622.1584, doi:10.1080/0161-110091888781, S2CID 4473786 (page 3 in PDF)
- Tuma, Jirí (2003), Permutation Groups and the Solution of German Enigma Cipher (PDF), Frode Weierud, p. 51, archived from the original (PDF) on 2014-10-30, retrieved 2014-09-12
- Rejewski 1981, p. ?
- Lisicki (1979, pp. 72–74) gives an example table of 65 message keys, but only 40 of those keys were distinct. Sixteen keys were repeated at least once. The encrypted key "SYX SCV" was used five times; it corresponded to the message key "AAA". The encrypted message key "RJL WPX" was used four times; it corresponded to "BBB".
- Rejewski (1981, p. 218) states, "When I first assumed that there would be many keys of the sort aaa, bbb, etc., it was only a hypothesis that luckily turned out to be true. The changing tastes of cryptographers were very carefully followed, and other predilictions were uncovered."
- Rejewski 1981, p. 218 stating, "Thus, one of the mysteries of the Enigma cipher, the secret of the message key, was solved. It is interesting that knowledge of neither of the positions of the drums nor the daily keys – in other words, none of the remaining secrets of the Enigma cipher – was needed to attain the result."
- Rejewski, Marian (1980), "An Application of the Theory of Permutations in Breaking the Enigma Cipher" (PDF), Applicaciones Mathematicae, 16 (4), archived from the original (PDF) on 2014-10-30,
In this way, an accurate knowledge of preferences of the cryptographers together with the theorem on the product of transpositions enables us to find the only actual solution.
- Later known as a "female".
- Rejewski 1981, p. 218
- Rejewski 1981, p. 219 equation 3 with H removed
- Rejewski 1981, p. 219
- Rejewski 1981, p. 220
- Rejewski 1981, p. 222
- Rejewski 1981, p. 223
- One of the
Dinterchanges is accidental due to a double stecker mapping a different interchange. - Rejewski 1984c, p. 242
- Rejewski 1981, p. 223: "...we soon noticed that if some part of the message was to begin with ANX, several positions of drum N would be impossible and should no longer be considered. Since there were a dozen or so messages every day in which one could expect to find the letters ANX at the beginning, it was usually possible to reject, purely by calculation, all impossible positions of drum N leaving just one or two to consider. (I no longer remember which calculations had to be performed and on which theoretical principles they were based.)"
- Rejewski 1981, p. 224
- Rejewski 1984d, p. 268
- Rejewski 1981, pp. 225–226
- Rejewski 1981, p. 227
- Rejewski 1981, p. 225
- Archived 2014-10-30 at the Wayback Machine transcribed from Cryptologia, C. A. Deavours and Louis Kruh, "The Turing Bombe: Was It Enough?", Cryptologia, Vol. XIV, No.4, October 1990, pp. 331-349, at page 342.
- Kahn, David (1991). Seizing the Enigma: The Race to Break the German U-Boats Codes, 1939–1943. ISBN 978-0-395-42739-2.
- Kozaczuk, Władysław (1984), Enigma: How the German Machine Cipher was Broken, and how it was Read by the Allies in World War Two, edited and translated by Christopher Kasparek [a revised and augmented translation of W kręgu enigmy, Warsaw, Książka i Wiedza, 1979, supplemented with appendices by Marian Rejewski], Frederick, MD, University Publications of America, ISBN 978-0-89093-547-7.
- Kruh, L.; Deavours, C. (2002). "The Commercial Enigma: Beginnings of Machine Cryptography". Cryptologia. 26: 1–16. doi:10.1080/0161-110291890731. S2CID 41446859.
- Lisicki, Tadeusz (1979), "Die Leistung des polnischen Entzifferungsdienstes bei der Lösung des Verfahrens der deutschen »Enigma«-Funkschlüsselmachine" [The Methods the Polish Cipher Bureau used to solve the German Enigma Cipher Machine] (PDF), in Rohwer, J.; Jäkel, E. (eds.), Die Funkaufklärung und ihre Rolle im Zweiten Weltkrieg [Radio Intelligence and its Role in World War II] (in German), Stuttgart: Motorbuch Verlag, pp. 66–81, archived from the original (PDF) on 2014-10-19, retrieved 2014-10-12
- Rejewski, Marian (July 1981), "How Polish Mathematicians Deciphered the Enigma" (PDF), Annals of the History of Computing, 3 (3): 213–234, doi:10.1109/MAHC.1981.10033, S2CID 15748167
- Rejewski, Marian (1984c), Summary of Our Methods for Reconstructing ENIGMA and Reconstructing Daily Keys, and of German Efforts to Frustrate Those Methods: Appendix C of Kozaczuk 1984, pp. 241–45
- Rejewski, Marian (1984d), How the Polish Mathematicians Broke Enigma: Appendix D of Kozaczuk 1984, pp. 246–71
- Rejewski, Marian (1984e), The Mathematical Solution of the Enigma Cipher: Appendix E of Kozaczuk 1984, pp. 272–291
- Polish Contributions to Computing, http://chc60.fgcu.edu/EN/HistoryDetail.aspx?c=1 Archived 2014-07-13 at the Wayback Machine
- Gaj, Kris; Orlowski, Arkadiusz (May 2003), "Facts and Myths of Enigma: Breaking Stereotypes", in Biham, Eli (ed.), Advances in Cryptology — EUROCRYPT 2003: International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland: Springer-Verlag, pp. 106–122, ISBN 978-3-540-14039-9, LNCS 2656 Also https://www.iacr.org/archive/eurocrypt2003/26560106/26560106.doc
- Casselman, Bill (November 2009), Marian Rejewski and the First Break into Enigma, Feature Column, American Mathematical Society, retrieved 2014-11-15
- Casselman, Bill (December 2013), The Polish Attack on Enigma II: Zygalski sheets, Feature Column, American Mathematical Society, retrieved 2014-11-15
- European Axis Signal Intelligence in World War II as Revealed by "TICOM" Investigations and by other Prisoner of War Interrogations and Captured Material, Principally German: Volume 2 — Notes on German High Level Cryptography and Cryptanalysis; see page 76: Swiss changed rotor wirings every 3 months, but Germans figured out the wirings because some messages were sent twice during the tri-monthly changeover. Germans were told new Croat rotor wirings by the company that manufactured the rotors.
- Bauer p 419