Demystifying the Enigma machine with F#

I had a couple of evenings free this week so decided to see if I could implement the Enigma machine, used during WW2 by the Nazis (and famously decrypted by the Polish, French and ultimately the British in Bletchley Park via some of the first programmable computers) in F#.

An overview of Enigma

The initial work around doing this involved gaining an understanding of how it worked. I’d actually already visited Bletchley Park a few years back as well as read up on the Enigma machine anyway, so had a limited understanding of how it worked. However, actually implementing it in code taught me quite a few things about it that I didn’t know!

At a high level, you can think of the Enigma as a machine that performs a number of substitution cyphers in a fixed pattern, with the substitutions changing after every letter. Although the shifts in substitution are relatively simple, I do wonder at just how individuals were able to crack these codes without detailed knowledge of the machines. Even with them, and even if you knew the rotors that were used, without the keys, there are still many permutations to consider. Apparently one of the main reasons that the Enigmas were eventually broken was down to human error e.g. many messages were initiated (or signed off) with the same common text, or some same messages were sent multiple times but with different encryption settings, thus enabling their decryption.

The Enigma we’re modelling was comprised of several components each with unique (and here, slightly simplified) behaviours: –

• Three rotors. Each rotor linked to another rotor, and acted as a substitution matrix e.g. The 1st character on one rotor connected to 5th character on the adjacent rotor. Before each key press, the first rotor would cycle to the next position. After passing a specific letter (known as a “Knock On”), the next rotor would also cycle forward one notch.
• A reflector. This took a signal from a rotor, performed a simple substitution that was guaranteed not to substitute any letter to itself, and sent it back to the rotors. These rotors would then process backwards, performing another set of three substitutions, but using the reverse cypher.
• A plugboard. This acted as an additional substitution layer for mapping letters bi-directionally e.g. A <-> B, C <-> D etc.

Here’s how a single character would flow through the machine to be encoded: –

After each “stage” in the pipeline, the character would be substituted for another one, so by the time you finish, there have been nine separate substitutions and you end up with the letter “I”. Because of the nature of the rotors, of which at least one of them moves after every keypress, sending the same letter again immediately afterwards would not generate the same output.

You could also configure the Enigma in several ways: –

• There were nine rotors, each hard coded with different substitutions, and three rotor sockets on an Enigma; thus many combinations existed for permutations depending on which rotors were inserted.
• There were two reflectors in wide operation, one of which would be used.
• The plugboard would be used to perform an initial substitution from the letters on the keyboard.
• Each rotor could be given an arbitrary starting position (1-26).
• Each rotor could be given a specific offset (ring setting) which would also apply to the substitution.

Mapping the problem into code

So, enough about the Enigma itself – how do we map this into F#! Well, to start with, here’s a simple set of types to model our (slightly dumbed down) domain: –

	namespace Enigma
	open System
	type AlphabetMapping = string
	type RingSetting = RingSetting of char
	type WheelPosition = WheelPosition of char
	type KnockOn = WheelPosition list
	type PlugBoard = PlugBoard of string list
	type Reflector = Reflector of AlphabetMapping
	type Rotor =
	{ Mapping : AlphabetMapping
	KnockOns : KnockOn
	RingSetting : RingSetting }
	type Enigma =
	{ Left : Rotor * WheelPosition
	Middle : Rotor * WheelPosition
	Right : Rotor * WheelPosition
	Reflector : Reflector
	Plugboard : PlugBoard }
	// Example usage
	let rotor1 =
	{ Mapping = "EKMFLGDQVZNTOWYHXUSPAIBRCJ" // map these to ABCDEF…XYZ
	KnockOns = [ WheelPosition 'E' ] // flip adjecent rotor whenever this one reaches "E"
	RingSetting = RingSetting 'A' } // default ring setting
	let reflectorA = Reflector "EJMZALYXVBWFCRQUONTSPIKHGD"
	let myEnigma = { Left = rotor1, WheelPosition 'A'
	Middle = rotor2, WheelPosition 'A'
	Right = rotor3, WheelPosition 'A'
	Reflector = reflectorA
	Plugboard = Plugboard "AB VS DG CL HU FZ KN IM RW OX" }

view raw

enigma1.fs

hosted with ❤ by GitHub

And that’s all we need to model the system. Note the use of single-case Discriminated Unions to provide a way to easily wrap around primitive types that are used in multiple places e.g. RingSetting and WheelPosition. Using these not only guides the compiler, but also allow us to infer usage based solely on the type being used – we don’t need to rely on variable names.

Composing functionality together

What’s interesting is how in F# you can get good results very quickly by simply starting with small functions and not necessarily worrying too much about the big picture. Once you have these small bits of functionality, you can compose them together to build much more powerful systems. Look at the pipeline diagram above, and then map that to this code below: –

	let translateLetter (left : Rotor, middle : Rotor, right : Rotor, reflector : Reflector, plugboard : Plugboard) : char -> char =
	substituteUsing plugboard
	>> translateUsing right Forward
	>> translateUsing middle Forward
	>> translateUsing left Forward
	>> reflectUsing reflector
	>> translateUsing left Inverse
	>> translateUsing middle Inverse
	>> translateUsing right Inverse
	>> substituteUsing plugboard
	// translate the character 'a'.
	let answer:char = 'a' |> translateLetter (rotor1, rotor2, rotor3, reflectorA, myPlugboard)

view raw

enigma2.fs

hosted with ❤ by GitHub

Notice how closely the code above and the previous diagram map to one another. Indeed, all of these functions have identical signatures i.e. char -> char. This makes perfect sense when you consider the task of each stage of the pipeline – give me a char, and I’ll give you another one back out. You could even view the pipeline as list of (char -> char) functions that you can fold with a single character to get a result out.

Having created this simple function to translate a single character, we can now compose this function into one that can translate a whole string of characters: –

	let translate (text:String) (enigma:Enigma) =
	let(translated:char array =
	(enigma, text |> Seq.toList)
	||> Seq.unfold(fun (enigma, letters) ->
	match letters with
	| letter :: remainder ->
	// Translate the head letter, and generate a new Enigma machine with the latest wheel positions
	let translatedLetter, updatedEnigma = letter |> translateChar enigma
	// Return back the translated letter and repeat with the remainder until nothing is left
	Some(translatedLetter, (updatedEnigma, remainder))
	| _ -> None)
	// Convert the char array back into a string
	String (translated |> Seq.toArray)

view raw

enigma3.fs

hosted with ❤ by GitHub

Notice how although we need to track state of the Enigma (to manage wheel rotations after each translated character) that we don’t mutate the actual enigma that was provided; rather, internally we create copies with the required changes on each pass. Once we’ve completed the capability for encrypting an entire string, we can easily build up into an easy-to-consume API: –

Authentic WW2 Enigma encryption with #fsharp. Can anyone solve this? http://t.co/YvmJaImn4y

—
Isaac Abraham (@isaac_abraham) December 24, 2014

Conclusion

Please feel free to have a look at the full source code here. Things to take away: –

• Problems can often easily be solved through a bottom-up approach, naturally allowing a higher-level design and API to present itself.
• Composition and partial function application are key enablers to easily manipulate functions together.
• A large part of the Enigma process can essentially be seen as an ordered set of pure char -> char functions.
• F# has a concise type system that allows us to express our domain in just a few lines of code.

Also check out the use of fscheck within the set of unit tests as a way of testing specific properties of the Enigma machine with a large set of data!

Advertisement