Grill (cryptology)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 machine changes plaintext characters into cipher text using a different permutation for each character, and so implements a polyalphabetic cipher.

Background[edit]

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:[6]

 26! = 403,291,461,126,605,635,584,000,000

The number of possible different reflector wirings is:[7]

\frac{26!}{2^{13} \, 13!} = 7,905,853,580,025

The number of possible different plugboard wirings (for six cables) is:[8]

\frac{26!}{2^6 \, 6! \, 14!} = 100,391,791,500

To encrypt or decrypt, the operator made the following machine key settings:[9]

  • 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[edit]

The Enigma machine was an electro-mechanical rotor machine with a scrambler consisting of (from right to left) an entry drum, three rotors and a reflector. It was available commercially from the early 1920s and was modified for use by the German military who adopted it later in the decade.

Frode Weierud provides the procedure, secret settings, and results that were used in a 1930 German technical manual.[10][11]

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

Cleartext message to send and resulting cleartext:
  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, it was obvious that the first six letters were the enciphered doubled key.[12]

Key encryption[edit]

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.

\begin{align}
A = &\binom\texttt{abcdefghijklmnopqrstuvwxyz}
           \texttt{ptkxrzqswmcojylagehbvuidnf} &= \texttt{(ap)(bt)(ck)(dx)(er)(fz)(gq)(hs)(iw)(jm)(lo)(ny)(uv)} \\
B = &\binom\texttt{abcdefghijklmnopqrstuvwxyz}
           \texttt{ukzmyxrsnqbwdipojghvatlfec} &= \texttt{(au)(bk)(cz)(dm)(ey)(fx)(gr)(hs)(in)(jq)(lw)(op)(tv)} \\
C = &\binom\texttt{abcdefghijklmnopqrstuvwxyz}
           \texttt{uymsznqwovtpcfilgxdkajhrbe} &= \texttt{(au)(by)(cm)(ds)(ez)(fn)(gq)(hw)(io)(jv)(kt)(lp)(rx)} \\
D = &\binom\texttt{abcdefghijklmnopqrstuvwxyz}
           \texttt{jwvrosuyzatqxpenldfkgcbmhi} &= \texttt{(aj)(bw)(cv)(dr)(eo)(fs)(gu)(hy)(iz)(kt)(lq)(mx)(np)} \\
E = &\binom\texttt{abcdefghijklmnopqrstuvwxyz}
           \texttt{jxvqltnypaseugzidwkfmcrbho} &= \texttt{(aj)(bx)(cv)(dq)(el)(ft)(gn)(hy)(ip)(ks)(mu)(oz)(rw)} \\
F = &\binom\texttt{abcdefghijklmnopqrstuvwxyz}
           \texttt{nvykzutslxdioamwrqhgfbpjce} &= \texttt{(an)(bv)(cy)(dk)(ez)(fu)(gt)(hs)(il)(jx)(mo)(pw)(qr)} \\
\end{align}

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.[13][14][15]

Rejewski's characteristic[edit]

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 was enough messages, the two left rotors to stay still while the message keys were encrypted, 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

\begin{align}
p_1 &= c_1 A^{-1}&= p_4 &= c_4 D^{-1} \\
p_2 &= c_2 B^{-1}&= p_5 &= c_5 E^{-1} \\
p_3 &= c_3 C^{-1}&= p_6 &= c_6 F^{-1} \\
\end{align}

The equations can be post multiplied by D, E, and F respectively to simplify the right hand sides:

\begin{align}
p_1 D &= c_1 A^{-1}D &= p_4 D &= c_4 \\
p_2 E &= c_2 B^{-1}E &= p_5 E &= c_5 \\
p_3 F &= c_3 C^{-1}F &= p_6 F &= c_6 \\
\end{align}

The plaintext values are unknown, so those terms are just dropped to leave:

\begin{align}
c_1 A^{-1}D&= c_4 \\
c_2 B^{-1}E&= c_5 \\
c_3 C^{-1}F&= c_6 \\
\end{align}

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:

\begin{align}
c_1 AD &= c_4 \\
c_2 BE &= c_5 \\
c_3 CF &= c_6 \\
\end{align}

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.[16]

Rejewski recorded the three permutations with a cyclic notation he called the characteristic. Rejewski (1981, p. 217) gives an example:

\begin{align}
AD &= \texttt{(dvpfkxgzyo)(eijmunglht)(bc)(rw)(a)(s)} \\
BE &= \texttt{(blfqveoum)(hjpswizrn)(axt)(cgy)(d)(k)} \\
CF &= \texttt{(abviktjgfcqny)(duzrehlxwpsmo)} \\
\end{align}

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.

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[edit]

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 6 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]

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[edit]

Using the daily key in the 1930 technical manual above, then (with enough messages) Rejewski could find the following characteristics:

\begin{align}
AD &= \texttt{(pjxroquctwzsy)(kvgledmanhfib)} \\
BE &= \texttt{(kxtcoigweh)(zvfbsylrnp)(ujd)(mqa)} \\
CF &= \texttt{(yvxqtdhpim)(skgrjbcolw)(un)(fa)(e)(z)} \\
\end{align}

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).[22] 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.

\begin{align}
C &= \texttt{(ez)...} \\
F &= \texttt{(ez)...} \\
\end{align}

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).[23] 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.[23]

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.

\begin{align}
A &= \texttt{(er)...} \\
D &= \texttt{(eo)...} \\
\end{align}

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") .

\begin{align}
A &= \texttt{(er)(dx)...} \\
D &= \texttt{(eo)...} \\
\end{align}

That can be continued to get all the characters for both permutations.

\begin{align}
A &= \texttt{(er)(dx)(jm)(ap)(ny)(hs)(fz)(iw)(bt)(ck)(uv)(gq)(lo)} \\
D &= \texttt{(eo)(lq)(gu)(cv)(kt)(bw)(iz)(fs)(hy)(np)(ag)(mx)(dr)} \\
\end{align}

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.

\begin{align}
A &= \texttt{(ap)(bt)(ck)(dx)(er)(fz)(gq)(hs)(iw)(jm)(lo)(ny)(uv)} \\
D &= \texttt{(aj)(bw)(cv)(dr)(eo)(fs)(gu)(hy)(iz)(kt)(lq)(mx)(np)} \\
\end{align}

The guessed message key of "EEE" producing indicator "RYZOLZ" would also determine the pairing of the 10-long cycles in permutation BE.

\begin{align}
B &= \texttt{(ey)(hs)(kb)(xf)(tv)(cz)(op)(in)(gr)(wl)...} \\
E &= \texttt{(le)(rw)(ng)(pi)(zo)(vc)(ft)(bx)(sk)(yh)...} \\
\end{align}

That determines most of B and E, and there would only be 3 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".

Grill[edit]

The physical grill[clarification needed] was used to determine both the rightmost rotor, its initial position, and the plugboard settings.

Rejewski's model[edit]

Rejewski modeled the machine as permutation made from permutations of plugboard (S), 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:[24]

\begin{align}
A &= S (P^{1}NP^{-1}) L M R M^{-1} L^{-1} (P^{1}N^{-1}P^{-1}) S^{-1} \\
B &= S (P^{2}NP^{-2}) L M R M^{-1} L^{-1} (P^{2}N^{-1}P^{-2}) S^{-1} \\
C &= S (P^{3}NP^{-3}) L M R M^{-1} L^{-1} (P^{3}N^{-1}P^{-3}) S^{-1} \\
D &= S (P^{4}NP^{-4}) L M R M^{-1} L^{-1} (P^{4}N^{-1}P^{-4}) S^{-1} \\
E &= S (P^{5}NP^{-5}) L M R M^{-1} L^{-1} (P^{5}N^{-1}P^{-5}) S^{-1} \\
F &= S (P^{6}NP^{-6}) L M R M^{-1} L^{-1} (P^{6}N^{-1}P^{-6}) S^{-1} \\
\end{align}

Rejewski simplied these equations by creating Q as a composite reflector made from the real reflector and two leftmost rotors:

Q = L M R M^{-1} L^{-1}

Substitution produces:

\begin{align}
A &= S (P^{1}NP^{-1}) Q (P^{1}N^{-1}P^{-1}) S^{-1} \\
B &= S (P^{2}NP^{-2}) Q (P^{2}N^{-1}P^{-2}) S^{-1} \\
C &= S (P^{3}NP^{-3}) Q (P^{3}N^{-1}P^{-3}) S^{-1} \\
D &= S (P^{4}NP^{-4}) Q (P^{4}N^{-1}P^{-4}) S^{-1} \\
E &= S (P^{5}NP^{-5}) Q (P^{5}N^{-1}P^{-5}) S^{-1} \\
F &= S (P^{6}NP^{-6}) Q (P^{6}N^{-1}P^{-6}) S^{-1} \\
\end{align}

Bottom sheet[edit]

Rejewsky observed that S is close to the identity permutation (initially, 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:

\begin{align}
(P^{1}N^{-1}P^{-1}) S^{-1} A S (P^{1}NP^{-1}) &= Q \\
(P^{2}N^{-1}P^{-2}) S^{-1} B S (P^{2}NP^{-2}) &= Q \\
(P^{3}N^{-1}P^{-3}) S^{-1} C S (P^{3}NP^{-3}) &= Q \\
(P^{4}N^{-1}P^{-4}) S^{-1} D S (P^{4}NP^{-4}) &= Q \\
(P^{5}N^{-1}P^{-5}) S^{-1} E S (P^{5}NP^{-5}) &= Q \\
(P^{6}N^{-1}P^{-6}) S^{-1} F S (P^{6}NP^{-6}) &= Q \\
\end{align}

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 (3 sheets). Each bottom sheet consisted of 31 lines (26 + 5 to make 6 lines contiguous). Each line contained the stepped permutation of a known rotor.[25] For example,

\begin{align}
P^{0}&NP^{-0}   &\ \texttt{kjpzydtiohxcsgubrnwfmveqla} \\
P^{1}&NP^{-1}   &\ \texttt{ioyxcshngwbrftaqmveludpkzj} \\
P^{2}&NP^{-2}   &\ \texttt{nxwbrgmfvaqeszpludktcojyih} \\
&... &... \\
P^{25}&NP^{-25} &\ \texttt{blkqazeujpiydthvcsoxgnwfrm} \\
P^{0}&NP^{-0}   &\ \texttt{kjpzydtiohxcsgubrnwfmveqla} \\
P^{1}&NP^{-1}   &\ \texttt{ioyxcshngwbrftaqmveludpkzj} \\
P^{2}&NP^{-2}   &\ \texttt{nxwbrgmfvaqeszpludktcojyih} \\
P^{3}&NP^{-3}   &\ \texttt{wvaqfleuzpdryoktcjsbnixhgm} \\
P^{4}&NP^{-4}   &\ \texttt{uzpekdtyocqxnjsbiramhwgflv} \\
\end{align}

Early on, 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 bottom sheet.[26]

Top sheet[edit]

For the top sheet, Rejewski wrote the six permutations A through F.

A: abcdefghijklmnopqrstuvwxyz
   srwivhnfdolkygjtxbapzecqmu

...

F: abcdefghijklmnopqrstuvwxyz
   wxofkduihzevqscymtnrglabpj

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 an Q. When a match is found, then the cryptanalyst would learn both the initial rotation of N and the plugboard (Stecker) permutation S.[27]

Recovering absolute rotor positions for the message key[edit]

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. 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.[28]

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]

Recovering the ring setting[edit]

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 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.[30]

Decline[edit]

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 5 to 8 pairs of letters were swapped.[32] 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.)[33]

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.[34] 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.[35] The SD net traffic was doubly encoded, so the ANX method would not work.[36] 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.[35]

Here's an example of the new message procedure for a message on 21 September 1938.[37]

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.

See also[edit]

Notes[edit]

  1. ^ Marian Rejewski, Mathematical Solution of the Enigma Cipher, trans Christopher Kasparek, Cryptologia, Vol 6, Number 1, pp 1–18 at 17, January 1982
  2. ^ a b Rejewski 1984e, p. 290
  3. ^ Kahn 1991, pp. 39–41, 299.
  4. ^ Kahn 1991, pp. 41, 299.
  5. ^ Kruh & Deavours 2002, p. 97.
  6. ^ Rejewski 1981, p. 215 This is the number of ways to arrange 26 distinct objects.
  7. ^ 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!).
  8. ^ 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.
  9. ^ Lisicki 1979, p. 68, Bild 1, Beispiel (Example)
  10. ^ http://cryptocellar.web.cern.ch/cryptocellar/Enigma/EMsg1930.html, citing 1930 "Schlüsselanleitung zur Chiffriermachine Enigma I" ["Directions for use of Keys on the Cypher Machine 'Enigma I'"]
  11. ^ Can be checked with a simulator. For example, http://people.physik.hu-berlin.de/~palloks/js/enigma/enigma-u_v20_en.html Select Enigma I, choose reflector A (at the time, the Germans only had one reflector), set the wheel order (II, I, III), set the rings (24, 13, 22), set the plugs (AM, FI, NV, PS, TU, WZ), activate the plugboard, and set the wheels to the ground setting ("FOL"). Typing ABLABL in the input box should produce PKPJXI as the output.
  12. ^ 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."
  13. ^ 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. 
  14. ^ Harkin, Anthony A.; Harkin, Joseph B. (April 2004), "Geometry of Generalized Complex Numbers", Mathematics Magazine 77 (2): 118–129  at page 129 implies both notations used in 1815.
  15. ^ Cauchy, Augustin-Louis (1987), "Augustin Louis Cauchy on the Theory of Permutations", in Fauvel, John; Gray, Jeremy, The History of Mathematics: A Reader, Macmillan Press in association with The Open University, pp. 506–507, ISBN 9780333427910 
  16. ^ Rejewski 1981, p. ??
  17. ^ Tuma, Jirí (2003), Permutation Groups and the Solution of German Enigma Cipher, Frode Weierud, p. 51 
  18. ^ Rejewski 1981, p. ?
  19. ^ 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".
  20. ^ 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."
  21. ^ Rejewski, Marian (1980), "An Application of the Theory of Permutations in Breaking the Enigma Cipher", Applicaciones Mathematicae (Warsaw) 16 (4), 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. 
  22. ^ Later known as a "female".
  23. ^ a b Rejewski 1981, p. 218
  24. ^ Rejewski 1981, p. 219 equation 3 with H removed
  25. ^ Rejewski 1981, p. 222
  26. ^ Rejewski 1981, p. 223
  27. ^ Rejewski 1981, p. 222
  28. ^ Rejewski 1981, p. 223
  29. ^ Rejewski 1981, p. 223
  30. ^ Rejewski 1981, p. 223
  31. ^ Rejewski 1984c, p. 242
  32. ^ Rejewski 1981, p. 224
  33. ^ Rejewski 1984d, p. 268
  34. ^ Rejewski 1981, pp. 225–226
  35. ^ a b Rejewski 1981, p. 227
  36. ^ Rejewski 1981, p. 225
  37. ^ http://cryptocellar.web.cern.ch/cryptocellar/Enigma/tbombe.html 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.

References[edit]

External links[edit]