Читать книгу Cryptography, Information Theory, and Error-Correction - Aiden A. Bruen - Страница 53

During World War II, German troops were able to march unopposed through much of Eastern Europe. At the heart of this war machine was an encryption scheme that allowed commanders to transfer crucial planning data with near total secrecy. Before the invasion of Poland, three Polish cryptologists by the names of Marian Rejewski, Henry Zygalski, and Jerzy Róźycki were able to crack the majority of the Enigma code used by the German army. Fearing capture during the German invasion, they escaped to France, bringing with them vital secrets about the Enigma machine.

Mechanically speaking, the Enigma machine consists of three removable rotors, a keyboard, a reflector plate, and a plugboard (see Figure 2.2). Each rotor has 26 electrical contacts on each face (with each one representing a value between 0 and 25), and wires connecting contacts on opposite faces in a variety of ways. The rotors rotate clockwise and are geared in such a way that the settings of the first rotor change with each plain text character that is enciphered and cycles through the values 0 to 25. Upon the transition between 25 back to 0, the second rotor rotates 1/26th of a turn. Following the transition between 25 back to 0 on the second rotor, the third rotor rotates 1/26th of a turn. This ensures that if the same character is sent twice in a row, it will likely be enciphered as two different cipher text letters. To increase the number of possible permutations, the rotors can be interchanged with one another. The reflector plate is a device with 26 contacts on the face adjacent to the last rotor, wired in such a way that the contacts are connected in pairs. Once a signal is sent to the reflector, it is sent through the corresponding wire and back into the third rotor. The plugboard consists of a series of sockets, and the board changes the identity of the input character based on the following conventions: if the given socket contains a plug, the character's identity is changed. If the socket is empty, the character remains unchanged. This device simply provides another set of permutations, meant to increase the complexity of the enciphering scheme. A basic block diagram of the system is depicted in Figure 2.3.

Figure 2.2 The German Enigma machine. (a) the Enigma machine type‐K, (b) the German Enigma machine display at the Naval Museum of Alberta, Canada, (c) the caption on the display at the Naval Museum of Alberta, Canada, (d) the Enigma machine type‐K, power supply, and additional lamp panel.

Source: Used with permission of the Naval Museum of Alberta, Canada.

Figure 2.3 Block diagram of the Enigma machine.

To use the machine, an operator inputs the desired plain text into a keyboard, one character at a time. An electrical signal is passed from the keyboard through the rotors which are connected in series, until the charge reaches the reflector plate. Then, the signal is passed back from the plate through the rotors and back into the keyboard, where a separate panel consisting of light bulbs is illuminated. Each light bulb corresponds to a cipher text letter, which is recorded by the operator. As the signal passes through each rotor, the plain text character is continually substituted, depending on the daily settings of the rotor and the specific wiring between contacts, which govern the permutations of substitutions that are possible. When the enciphering process is complete, the operator sends the cipher text via radio to the intended receiver, who also possesses an Enigma machine. The receiver can then decode the message, given that the initial settings and the permutation sets of the machines are coordinated, by simply typing in the cipher text into the machine. The plain text message then appears on the illuminated keyboard.

It is worth noting some of the deficiencies in the machine design, as they made it possible for Allied cryptanalysts to eventually break the cipher. There is a very nice YouTube video, “Flaw in the Enigma Code ‐ Numberphile,” [Gri13], that talks about flaws in the Enigma machine. They note that a given letter of the alphabet might be mapped to any other letter, i.e. a letter is never encoded as itself. The number of permutations of objects is , but if we insist that no object is mapped to itself, then the number of such permutations, i.e. the number of derangements of objects, is reduced to approximately , (where is the base of the natural logarithm). See Ryser [Rys63, p. 23]. Thus, some information about the encoding is revealed along with a coded message!

We will now investigate the machine from a mathematical standpoint. Each rotor is represented by a set of permutations containing all letter values between 0 and 25. The transition of each set runs left to right, with each bracket representing a wrap‐around or cycle. The first, second, and third rotors have unique permutation sets denoted , , and , respectively (each representing the possible transitions between letters). To aid in our analysis, we introduce the variables , , and to represent the initial rotor settings (taken to be the character currently located at the top of the rotor). For the purposes of this analysis, we will be ignoring the role of the plugboard. Finally, the reflector plate is modeled as a set of permutations between pairs of characters, denoted by . The goal is to track a signal as it leaves the input keyboard, travels though the rotors and reflector, and back to the illuminated display. To determine the appropriate cipher text for each given plain text letter, we will calculate the shift of each rotor, the resulting reflector permutation and reflected signal shifts until we end up with a final cipher text character.

To show how the enciphering process works, consider the modified system shown in Figure 2.4.

The idea is to keep track of each intermediate substitution, in order to determine the final cipher text character. To illustrate the encoding process, consider the following example:

Example 2.1 Suppose the permutation sets of each rotor and reflector are defined as follows:

Figure 2.4 Simplified Enigma model.

So, with , 0 gets moved to 15, 15 gets moved to 6, 11 moves to 0, etc.

Each permutation set possesses an inverse, which “undoes” the action of said permutation, as follows:

The initial settings are defined with (i.e. the letter at the top of roter 1 is ), , .

For the signal traveling toward the reflector plate, the substitutions through the rotors are represented mathematically as follows:

where raising a term to the exponent means locating the term in the permutation set and replacing it with the number to the right of the term. If there is a bracket adjacent to the term, wrap around to the beginning of the subset. For example, with our settings as above, and .

Since the reflector has contacts which are only connected in pairs, we get

Once has been output from the reflector, we follow the signal back to the keyboard:

After the successful completion of the cipher text substitution, we need to update the rotor settings to take into account the rotation(s) that may have taken place:

is redefined as . If and we add 1, the new becomes 0 and is advanced by one.

Similarly, if and we add 1, the new becomes 0 and is advanced by one.

Let us see what happens when we encode the letter “k,” which has numerical value 10.

Reaching the reflector, we get . Now following the signal back through the rotors, we obtain

Therefore, the first cipher text character corresponds to 7, and is thus is “H.”

Now, we must update the rotor settings: .

If the settings were such that was 25, the updating process would proceed as follows: , , .

As mentioned above, an interesting aspect about the Enigma enciphering scheme is the fact that deciphering a message follows the exact same process.