Clarisse Bonang

Nov 10, 20206 min read

Breaking the Enigma Code with Rewrite Rules Part I

Let's crack some code. Turing's computability processes and Turing Machine(TM), Bombe, played a key role in breaking the "Enigma" code in World War II. The Enigma was an encryption machine that translated coded messages in a secure fashion. Perhaps we can break the "Enigma" code by formulating TM to rewrite rules.

A Brief History of Bombe and Enigma

Enigma - mysterious, puzzling, and difficult to understand. What an apropos name for an encryption machine.

Enigma machine

Built in the mid-to-early 20th century, the Enigma machine encrypted coded messages for military communication and diplomatic missions (Wiki, Enigma machine). Used heavily during WWII by the German military, troops were able to communicate securely with ease.

This was a huge advantage in the war and mitigated the Allies certainty of anticipating German forces' next movements.

Essentially, the security of the Enigma code was dependent on the machine settings. The receiver would need to know the exact settings by the sender to decrypt a message. A helpful way to visualize this is by the Alice, Bob, and Eve problem.

Alice is the transmitting station and Bob is the receiving station, whereas Eve is the attempting to decrypt the message. Allied forced had to play the part of Eve; however, it appears futile for Eve to decrypt the message. So, how did the Allies figure it out?

I promise, you will find this interesting.

First, we have to discover how the Bombe broke the Enigma code. Ask yourself a few questions. How was Alan Turing's machine, known as the Bombe, able to crack the Enigma code without knowing the Enigma machine's instructions? For any code breaker, wouldn't you have to know how both the machine and code operate? Time to play Sherlock.

Records declassified 30 years later, reveal information on how the Enigma machine was compromised by Allied spies. On November 8, 1931, Hans-Thilo Schmidt allowed a French secret agent (codenamed Rex) to photograph two documents: "Gerbrauchsanweisung fur die Enigma" and Schlusselanleitung fur die Chiffriermaschine Enigma." for 10,000 marks (or $30,000 dollars).

Hans-Thilo Schimdt was the second son of an aristocratic family. As a German soldier in World War I, he took pride in being part of a greater cause. Although, after the Treaty of Versailles, the Germany army took drastic cuts and deemed him unworthy to remain in the army. After failed attempts of preserving his position in the army, he tried to redeem his reputation by becoming a business man. Because of the postwar depression and hyperinflation, his soap factory was forced to shutdown (Schmidt, p. 144). After the collapse of his business, his brother arranged a job for him at Enigma's command center, where he had access to the two documents mentioned earlier.

These documents contained information for using the Enigma machine. Although, there was no explicit description of the writings inside each scrambler, they contained the information needed to deduce those writings (Singh, The Code Book p. 145).

Although the information allowed one to create a replica of the Enigma machine, any attempt to decipher a message encrypted with it would still need to find which among millions and billions of possible keys was used.

Now, Alan Turing and the Bombe machine enter the stage.

Alan Turing's Bombe machine was tasked with discovering the daily key. It's ability to decipher enigma messages allowed the Allies to read messages at nearly the same time as the Axis forces. With the huge amount of intercepted Enigma messages and the Bombe's ability to decipher encrypted messages, the tide of the war shifted in the Allies favor.

(The Bombe machine, World War II)

According to Dr James Grime, mathematician and public speaker, Grime describes how the Bombe machine cracked the Enigma Code in about 20 minutes. The below is a dialogue from Dr. James Grime's discussing Enigma, the Bombe and Alan Turing. https://www.youtube.com/watch?v=V4V2bpZlqx8 :

"Bombe applied electrical current to our assumption. Then the electrical current flows through the machine. If it flows through T-G, it's wrong but it also flows through these other deductions. Which means that I can find all my deductions, which are all wrong. I can do it instantaneously with electrical circuits. Then, it goes through all the rotor positions in about 20 minutes.

The Bombe machine is flipped backwards. It's a process of elimination. Bombe machine was named in honor of Polish code named Bomda. Although Bomba had a completely different approach, it wasn't a huge machine. It exploited a flaw in German procedures. Able to break Army and Air Force enigma codes but they couldn't break naval enigma codes.

So Alan Turing's machine had to break army, air force, and navy enigma codes. Also, it had to be a bit more robust. So, if the Germans choose to change their procedures this method will still work.

What was the Navy was doing differently? The rotor starter positions were actually sent at the beginning at each message. But they were sent in another code entirely. So, there was a completely different code sent at the rotor's starting position. You needed to work out how that worked out as well before you could even start breaking the Enigma machine."

Now that you have a solid understanding of the Enigma and the Bombe, we'll examine their relation to Turing Machines and Rewrite Rules.

Formulating Turing Machines to Rewrite Rules

What we've covered so far:

✅ 1. Proposed a definition of the Turing Machine          
✅ 2. Preliminaries for Turing Machines and Rewrite Rules

From the diagrams in the previous section, "Turing Machines and Rewrite Rules", we observed how a machine progressively computes the 0s and 1s and prints sequentially from left to right. As well as how rewrite rules are able to simplify expressions. At first glance, the congruency between Turing Machines and rewrite rules is not apparent. Much less formulating a Turing machine to rewrite rules. Perhaps the examples below will change your mind.

Example 1 (Kurz, Exercises on Rewriting) :

Let M be a Turing machine where the six variables of the rules are:

q, S, S′, q′, M

Such that M ∊ {L, R} . Recall that "L" means that the machine moves left of its current position. "R" means that the machine moves right of its current position.

Given our set of rules of the form:

(q, S, S′, M, q′)

The above form tells us the following (here's some pseudo code for your convenience ) :

if (reading from state q reads S on the tape) 
      then replace S with S' 
      move in the direction of M ∊ {L, R}. 
      Go to state q'

The visuals below demonstrate the above:

Given: (q, S, S′, R, q′)

Step 1: In state q, read the current scanned square. The current square has an S.

Step 2: Replace S with S'

Step 3: Move blue pointer or head in direction of R (right). Then the state changes to q'

How does this relate to rewrite systems?

Given: (q, S, S′, M, q′), it denotes a computation step. As described in Max Dauchet's Simulation of Turing Machines by a regular rewrite rule, let ID represent M moving from state q then replaces S on the tape by the symbol S'. Then, let ID2 represent M moving to state q' when the current tape position has an S'. Hence, it is a computation step because M moves from ID to ID2 by application of instruction ( Dauchet, p. 411). Although Turing doesn't refer to the transition from one state to another by means of instruction, to mitigate confusion we will temporarily call it that. So we can safely assume that the transition from ID -> ID2 by instruction corresponds to a computation. Means of computation implies a pattern. This is helpful because rewrite rules encapsulate patterns or rules that reduce the expression by replacement. We know that a system of computations can be carried out as a series of rewrite rules. So, matching the rewrite rules with m-configuration and behavior of the machine can be attempted.

Let's try it!

For instance, given our set of rules of the form:

(q,S,S,R,q′)

We know:

When in state q and the current scanned square is S
Then, replace S to S', move right by one, and change the state to q'

By these set of rules we know that it can be rewritten by the following rewrite rule:

qS -> S'q'

As Dauchet said, "we can identify ID of Turing Machines with ID substitutions." The rewrite rules above implies that qS reduces to S'q'. However, we can also see it as a substitution for the current term. Yet again, some may argue that this is speculative. I've come prepared.

In the next blog, we will cover Dauchet's Lemma 6.2, "For any Turing machine M, we can associate an infinite M computation with any infinite Rᴍ rewriting." and examines Dauchet's proof. Futhermore, we'll cover the most exciting part this blog series, how to crack the Enigma code. Till next time fellow readers!