Clarisse Bonang

Nov 3, 20205 min read

Breaking the Enigma Code with Rewrite Rules Part II

I promised that we would crack some code and we shall. Last we covered a French spy, the Enigma machine, Alan Turing's Bombe machine, and introductions on how to formulate Turing Machines to rewrite rules. Quite Exciting! What's next? Today's blog will cover Dauchet's proof to justify our claim that formulating Turing machines to rewrite rules is agreeable. Then, we'll relate rewriting rules' applications to cracking the Enigma code like Alan Turing's Bombe machine.

Here's a quick recap of "Breaking the Enigma Code with Rewrite Rules Part I" :

✅ 1. We travelled back to WWII and covered a brief introduction on the inner-workings of the Enigma machine.

✅ 2. How Alan Turing's machine, the Bombe, was able to decipher Enigma encoded messages.

✅ 3. The beginning of how to formulate Turing machines to rewrite rules

As promised, I will reveal how to crack the Enigma code with relation to rewrite rules.

Although, first we need to assert that any Turing machine can formulate to a Rewrite rule through Dauchet's proof.

Dauchet's Proves Us Right

From part I, we assumed that Example 1 justifies our case for the congruency between Turing machines and rewrite rules. However, some may argue that it's purely speculation. Luckily, I've come prepared.

Recall the Example 1 from part I:

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.

Dauchet proposes Lemma 6.2, "For any Turing machine M, we can associate an infinite M computation with any infinite Rᴍ rewriting." His proposal makes sense, given that a TM's tape infinitely goes towards the right (Petzold, Annotated Turing) so the rewrite rules must also associate with an infinite computation. Second, we must note that termination problems and halting problems are undecidable for the class of Turing machines (Dauchet, p.418). Dauchet's description of the halting problem and the termination problem is posted below.

Dauchet proves that Lemma 6.2 is indeed true (Dauchet, p. 419-421):

In short, the above proof demonstrates the association of Turing machines given an infinite M computation with any Rᴍ rewriting. Lemma 6.2 allows us to formulate TM in terms of rewrite rules.

Example 2:

To better our understanding of formulating TM in terms of rewrite rules, we'll try another example.

Cracking the "Enigma" Code

We've asserted that TMs can formulate to rewrite rules, then let's crack some code with rewrite rules. Like any code breaker, we must understand how the "Enigma" machine operates. This information is vital for deciphering secret coded messages.

Here is a brief description of the 4 main parts to an "Enigma" machine.

ROTORS

Translates a letter to another letter

LAMPBOARD

Lights up each time the keyboard is pressed by the user with a new letter

KEYBOARD

I'm sure you know what it is. It's just like a typewriter or a computer keyboard but with just the letters (capitals only).

PLUGBOARD

Allows letter to be swapped.

To better understand how the Enigma Machine works and the flaws of the Enigma code, I highly recommend the video below. The video features Dr James Grime discussing Enigma, the Bombe and Alan Turing.

Now that you have a grasp of how the "Enigma" machine works. Let's explore some simple examples.

The rotor translates a letter to another letter, we can view the rotor as a substitution cipher. In a sense, it's similar to rewrite rules. If we looked at the example below,

ab -> ba
ba -> ab

ab maps to ba and ba maps back to ab. This highlights a similarity between the two.

If we were to look at the alphabet, there are 26 letters, each letter would map to a different order. That's essentially what the Enigma machine does. The Enigma machine substitutes to another set and maps it back. We could translate what Turing did to decipher the code by studying the behavior of the Enigma Code.

Again, consider 26 letters in the alphabet and it maps onto 26 different letters.

This would be the rewrite rule for the "Enigma" code. The Bombe machine had to determine these rewrite rules given a string of enciphered letters, the "cipher text". Essentially Bombe had candidate solutions (rewrite rules) that mapped to each other. But what if these mappings are incorrect?

Attempting other candidate mappings and determining if that would decipher to valid German language text, called the "plain text", was the key to the code breaking.

Plaintext: wetternullsechs
Ciphertext: I P R E N L W K M J J S X C P L E J W Q

Figure 1.1

Figure 1.1 illustrates the translation from cipher text to plain text. The plain text is on top in German. It is three words run together, "wetter null sechs." The text means, weather zero six, presumably the weather on the 6th day of the month.

(Singh, The Code Book p. 178)

Of course, the actual messages were typically longer and contained operational information. For example, the following is a decrypt of a German Enigma message sent to U-boats on May 2, 1945, announcing Hitler's death.

(BudianSky, The Battle of Wits p.181)

A simple example of the above would be the mapping to produce "hello" back. However, if you got a rewrite rule that failed to produce the correct word then you know it's not the right one

Another loophole that Turing and fellow codebreakers found was that the "Enigma" machine would never let a letter map to itself.

For instance, the following rules were not allowed:

b -> b 
a -> a

This was consider the "backdoor" to breaking the "Enigma" code. The "Enigma" code was no longer impenetrable. Knowing that a letter could not map to itself helped in testing a possible crib, or shortcut. A crib is a section of plain text thought to correspond to the cipher text. If you suspect the word "hello" as the plain text, your crib, and your decryption produces the word "hello", then you likely have the correct rewrite rule.

In reality, it is much more complex. The rotors turn so there is a different rewrite rule for each rotor turn. But ultimately, you have some complex rewrite rule. The rewrite would be dependent on the initial setting of the rotors and plugboard. In order to crack the code, the decoders would have to know the machine's complex setting. What the rewrite rule really is, is the position of the rotors and plugboard settings. With both, we can crack the "Enigma" Code.