Enigma Machine

An Enigma machine is a famous encryption machine used by the Germans during WWII to transmit coded messages. An Enigma machine allows for billions and billions of ways to encode a message, making it incredibly difficult for other nations to crack German codes during the war — for a time the code seemed unbreakable. Alan Turing and other researchers exploited a few weaknesses in the implementation of the Enigma code and gained access to German codebooks, and this allowed them to design a machine called a Bombe machine, which helped to crack the most challenging versions of Enigma. Some historians believe that the cracking of Enigma was the single most important victory by the Allied powers during WWII. Using information that they decoded from the Germans, the Allies were able to prevent many attacks. However, to avoid Nazi suspicion that they had insight to German communications, the Allies had to allow some attacks to be carried out despite the fact that they had the knowledge to stop them.

Military Enigma machine, model "Enigma 1", used during the late 1930s and during the war ^[1]

Enigma machines use a form of substitution encryption.

Substitution encryption is a straightforward way of encoding messages, but these codes are fairly easy to break. A simple example of a substitution encryption scheme is a Caesar cipher. A Caesar cipher shifts each letter of the alphabet some number of places. A Caesar cipher with a shift of $1$ would encode an A as a B, an M as an N, and a Z as an A, and so on.

Below is an image of a Caesar cipher with a shift of $3$.

^[2]

Using a Caesar cipher with a shift of 5, encode the message “math is fun”. Hint: it might be useful to construct a table showing the encoding.

---

Solution:

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

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

a

b

c

d

e

“Math is fun” can be encrypted by this scheme as “rfym nx kzs”.

But Enigma machines are much more powerful than a simple Caesar cipher.

Imagine that each time a letter was mapped to another, the entire encoding scheme changed. After each button press, the rotors move and repressing that same button routes current along a different path to a different revealed letter.

So for the first press of a key, one encoding (like the table in the example above) is generated, and when the second key is pressed, another encoding is generated, and so on. This greatly increases the number of possible encoding configurations. Each time a key is pressed on an Enigma machine, the rotors turn, and the code changes. This means that the message “AA” could be encoded as something like “TU” even though the same key was pressed twice.

An Enigma machine is made up of several parts including a keyboard, a lamp board, rotors, and internal electronic circuitry. Some machines, such as the ones used by the military, have additional features such as a plugboard.

Enigma Machine at the Imperial War Museum, London. ^[3]

Encoded messages would be a particular scramble of letters on a given day that would would translate to a comprehendible sentence when unscrambled.

When a key on the keyboard is pressed, one or more rotors move to form a new rotor configuration which will encode one letter as another. Current flows through the machine and lights up one display lamp on the lamp board, which shows the output letter. So if the "K" key is pressed, and the Enigma machine encodes that letter as a "P," the "P" would light up on the lamp board.

Each month, Enigma operators received codebooks which specified which settings the machine would use each day. Every morning the code would change.

For example, one one day, the codebook may list the settings described in the day-key below:

$1.$ Plugboard settings: A/L – P/R – T/D – B/W – K/F – O/Y

A plugboard is similar to an old-fashioned telephone switch board that has ten wires, each wire having two ends that can be plugged into a slot. Each plug wire can connect two letters to be a pair (by plugging one end of the wire to one letter’s slot and the other end to another letter). The two letters in a pair will swap over, so if “A” is connected to “Z,” “A” becomes “Z” and “Z” becomes “A.” This provides an extra level of scrambling for the military.

To implement this day-key first you would have to swap the letters A and L by connecting them on the plugboard, swap P and R by connecting them on the plugboard, and then the same with the other letter pairs listed above. Essentially, a one end of a cable would be plugged into the "A" slot and the other end would be plugged into the L slot. Before any further scrambling happens by the rotors, this adds a first layer of scrambling where the letters connected by the cable are encoded as each other. For example, if I were to encode the message APPLE after connecting only the "A" to the "L", this would be encoded as LPPAE.

The plugboard is positioned at the front of an Enigma machine, below the keys.^[4]

$2.$ Rotor (or scrambler) arrangement: 2 — 3 —1

The Enigma machines came with several different rotors, each rotor providing a different encoding scheme. In order to encode a message, the Enigma machines took three rotors at a time, one in each of three slots. Each different combination of rotors would produce a different encoding scheme. Note: most military Enigma machines had three rotor slots though some had more.

To accomplish the configuration above, place rotor #2 in the 1st slot of the enigma, rotor #3 in the 2nd slot, and rotor #1 in the 3rd slot.

$3.$ Rotor orientations: D – K –P

On each rotor, there is an alphabet along the rim, so the operator can set in a particular orientation. For this example, the operator would turn the rotor in slot 1 so that D is displayed, rotate the second slot so that K is displayed, and rotate the third slot so that P is displayed.

^[5]

Enigma wheels within alphabet rings in position in an Enigma scrambler^[6]

As mentioned in above sections, Enigma uses a form of substitution ciphers.

Each of the three rotors will display a number or letter (the rotors in the image above have letters), and when the rotors turn, a new set of three numbers/letters appears. With the initial set of three numbers/letters (meaning the numbers/letters on the sender’s machine when they began to type the message), a message recipient can decode the message by setting their (identical) Enigma machine to the initial settings of the sender’s Enigma machine. Each rotor has $26$ numbers/letters on it. An Enigma machine takes three rotors at a time, and the Germans could interchange rotors, choosing from a set of five, resulting in thousands of possible configurations. For example, one configuration of rotors could be: rotor #5 in slot one, rotor #2 in slot two, and rotor #1 in slot three.

How many configurations are possible with an Enigma machine with these specifications?

In the first slot, there are $5$ rotors to pick from, in the second there are $4$ rotors to pick from, and in the third slot there are $3$ rotors to pick from. So there are $$5 \times 4 \times 3 = 60$$ ways to configure the five rotors.

There are $26$ starting positions for each rotor, so there are $$26 \times 26 \times 26 = 17,576$$ choices for initial configurations of the rotors’ numbers/letters.

The features above describe the components of commercial Enigma machines, but military-grade machines have additional features, such as a plugboard, which allow for even more configuration possibilities.

Since there are $26$ letters in the alphabet, there are $26!$ ways to arrange the letters, but the plugboard can only make $10$ pairs, so there are $20$ letters involved with the pairings, and $6$ leftover that must be divided out. Furthermore, there are $10$ pairs of letters, and it does not matter what order the pairs are in, so divide also by $10!$, and the order of the letters in the pair does not matter, so divide also by $2^10$. The resulting number of combinations yielded by the plugboard is as follows: $$\frac{26!}{6! \times 10! \times 2^{10}} = 150,738,274,937,250.$$

All of the components put together yields: $60 \times 17576 \times 150,738,274,937,250 = 158,962,555,217,826,360,000$ total number of ways to set a military-grade Enigma machine. ^[7]

A major flaw with the Enigma code was that a letter could never be encoded as itself. In other words, an “M” would never be encoded as an “M.” This was a huge flaw in the Enigma code because it gave codebreakers a piece of information they could use to decrypt messages. If the codebreakers could guess a word or phrase that would probably appear in the message, they could use this information to start breaking the code. Because the Germans always sent a weather report at the beginning of the message, and usually included the phrase “Heil Hitler” at the end of the message, there were phrases decrypters knew to look for. ^[8]Decoders could compare a given phrase to the letters in the code, and if a letter in the phrase matched up with a letter in the code, they knew that that part of the code did not contain the phrase. The decoders could then begin cracking the code with a process of elimination approach.

Find possible contenders for the encoding of the word “RAIN” in the coded string below. (The symbol % is used to denote unknown letters).

Coded Message

E

R

W

N

I

K

O

L

K

M

M

M

M

Phrase

R

A

I

N

%

%

%

%

%

%

%

%

%

RAIN cannot be encoded as ERWN because the N in RAIN and the N in ERWN match up. Since N cannot be encoded as itself, this isn’t the encoding.

Let’s shift our message one slot to the right, and see if the result is a valid encoding.

Coded Message

E

R

W

N

I

K

O

L

K

M

M

M

M

Phrase

%

R

A

I

N

%

%

%

%

%

%

%

%

RAIN cannot be encoded as RWNI because the R in RAIN matches with the R in RWNI. Let’s shift again.

Coded Message

E

R

W

N

I

K

O

L

K

M

M

M

M

Phrase

%

%

R

A

I

N

%

%

%

%

%

%

%

RAIN cannot be encoded as WNIK because the I in RAIN matches with the I in WNIK.

Coded Message

E

R

W

N

I

K

O

L

K

M

M

M

M

Phrase

%

%

%

R

A

I

N

%

%

%

%

%

%

RAIN can be encoded as NIKO because the two phrases have no letters that match up. So NIKO is a possible encoding of RAIN.

If we repeat this process, we will find that NIKO, IKOL, KOLK, OLKM, LKMM, KMMM, and MMMM are all possible encodings of RAIN since no letters match up between RAIN and the encoding. It is okay that MMMM could encode RAIN even though this means that M would encode R, A, I, and N because remember that at each key press, the letter mapping in an Enigma machine changes.

It is not guaranteed that RAIN is encoded in this string at all, though, but it gave decoders a good starting point for decrypting messages.

Alan Turing and Gordon Welchman designed a machine called the Bombe machine which used electric circuits to solve an Enigma encoded message in under 20 minutes. The Bombe machine would try to determine the settings of the rotors and the plugboard of the Enigma machine used to send a given coded message.

The standard British Bombe machine was essentially 36 Enigma machines wired together, this way, the Bombe machine would simulate several Enigma machines at once. Most Enigma machines had three rotors and to represent this in the Bombe, each of the Enigma simulators in the Bombe had three drums, one for each rotor.

Bombe machine drums^[9]

The Bombe's drums were color coded to correspond with which rotor they were simulating. While an 3-rotor Enigma machine only used three rotors at a time, there are more to choose from. The drums were arranged so that the top one of the three simulated the left-hand rotor of the Enigma scrambler, the middle one simulated the middle rotor, and the bottom one simulated the right-hand rotor. The drums would turn to try out a new configuration. For each full rotation of the top drums, the middle drums were incremented by one position, and likewise for the middle and bottom drums, giving the total of 26 × 26 × 26 = 17,576 positions of the 3-rotor Enigma scrambler.^[10]

Then, for a given rotor configuration (at each turn of the drums), the Bombe machine would make a guess about a plugboard setting, say “A is connected to Z.” It then ran through and determined what all of the other letters must be set to on the plugboard. If any contradictions arose, say, it deduced that “A was connected to W,” then it must be that A is not connected to Z on the plugboard, a contradiction arises. Since the other letter mappings the machine just figured out were determined based off of a false assumption (namely the assumption that A is connected to Z), all of those combinations are invalid, and the Bombe machine knows not to waste time checking any of those combinations later. So, say that the machine guessed that A is connected to Z, and then the machine deduces that if A is connected to Z, then B must be connected to E. If it later determines that A is not connected to Z, it knows that B is not connected to E. After such a contradiction arises, the Bombe machine will not guess that A is connected to Z again, and it knows not to guess that B is connected to E, and so on. The Bombe machine shifts the rotor positions, and chooses a new guess and repeats this process until a satisfying arrangement of settings appears. Because electric circuits can perform computations very quickly, the Bombe machine can go through all the rotor combinations in about 20 minutes.

At each position of the drums, the configuration would be tested to see if the configuration lead to a logical contradiction, ruling out that setting. If the test did not lead to a contradiction, the machine would stop and the decoder would note that configuration as a candidate solution. Then, the machine is restarted and more configurations are tested. These tests would narrow down the list of possible configurations and the candidate solutions would be tested further to eliminate ones that wouldn't work. There were usually many unsuccessful candidate solutions before the correct one was found.^[10]

Caesar Cipher

Bombe machine

Vigenere Cipher

1. Nassiri, A. Enigma (crittografia) - Museo scienza e tecnologia Milano. Retrieved April 30, 2016, from https://en.wikipedia.org/wiki/File:Enigma_(crittografia)_-_Museo_scienza_e_tecnologia_Milano.jpg
2. , C. Caesar3. Retrieved April 30, 2016, from https://commons.wikimedia.org/wiki/File:Caesar3.svg
3. Sperling, K. EnigmaMachineLabeled. Retrieved April 30, 2016, from https://en.wikipedia.org/wiki/File:EnigmaMachineLabeled.jpg
4. Lord, B. Enigma-plugboard. Retrieved April 30, 2016, from https://en.wikipedia.org/wiki/File:Enigma-plugboard.jpg
5. , M. File:Enigma-rotor-windows.jpg. Retrieved July 20, 2016, from https://commons.wikimedia.org/wiki/File:Enigma-rotor-windows.jpg
6. , T. Enigma rotors with alphabet rings. Retrieved April 30, 2016, from https://en.wikipedia.org/wiki/File:Enigma_rotors_with_alphabet_rings.jpg
7. , N. 158,962,555,217,826,360,000 (Enigma Machine). Retrieved April 28, 2016, from https://www.youtube.com/watch?v=G2_Q9FoD-oQ
8. , N. Flaw in the Enigma Code. Retrieved April 28, 2016, from https://www.youtube.com/watch?annotation_id=annotation_786414&feature=iv&src_vid=G2_Q9FoD-oQ&v=V4V2bpZlqx8
9. , T. File:Rotating upper bombe drum.jpg. Retrieved July 21, 2016, from https://en.wikipedia.org/wiki/File:Rotating_upper_bombe_drum.jpg
10. , . Bombe. Retrieved July 21, 2016, from https://en.wikipedia.org/wiki/Bombe