University of Sheffield Department of Computer Science
COM2001: Advanced Programming Techniques Semester 1 Assessment 2016-17
Assignment 2: The Enigma Coding Machine, Cribs and Menus
This assignment counts as 17.5% of the assessment for COM2001
1. TheEnigmaMachine
Reflector
Rotors
LR MR RR
The Enigma Machine
QWERTYUIOP
Lamps
QWERTYUIOP
Keyboard
Enigma Schematic
The Enigma machine was based on rotors. A rotor implemented a fixed alphabetic substitution cipher. The ciphers for the original five Enigma rotors RI, RII etc were
plain
ABCDEFGHIJKLMNOPQRSTUVWXYZ
RI
EKMFLGDQVZNTOWYHXUSPAIBRCJ
RII
AJDKSIRUXBLHWTMCQGZNPYFVOE
RIII
BDFHJLCPRTXVZNYEIWGAKMUSQO
RIV
ESOVPZJAYQUIRHXLNFTGKDCMWB
RV
VZBRGITYUPSDNHLXAWMJQOFECK
Like the ciphers in assignment 1, a rotor could be offset by a given number of positions (0 to 25), so that if the offset is 0, RI encodes A to E, B to K.. Z to J but it encodes A->J, B->E… Z->C if the offset is 1.
The rotors could also be used in reverse, i.e. RI with offset 0 reverse-encodes E to A, K to B and so on. The standard Enigma had 3 rotors, mounted on a shaft. We’ll refer to them as the left, middle and right rotors, LR, MR and RR.
A codebook given to all Enigma operators specified a different selection for LR, MR & RR for each day from the available rotors RI,RII..RV. These were mounted on the shaft in the correct order. In addition, initial offsets OL, OM and OR were specified for LR, MR and RR. Thus all the Enigmas in use were set to the same starting positions each day. We’ll make the assumption that before sending each message the offsets were reset to OL, OM and OR (in reality it was more complicated).
In the basic Enigma1, a letter was first transmitted to RR, which encoded it and transmitted the result to MR, which encoded that and transmitted it to LR. The encoded letter from LR was passed to a fixed reflector which performed a letter-swap (i.e. the 26 letters were divided into 13 pairs (c1,c2) ; c1 was changed to c2 and c2 to c1. The standard reflector pairings were
(A Y)(B R)(C U)(D H)(E Q)(F S)(G L)(I P)(J X)(K N)(M O)(T Z)(V W)
The output from the reflector was then passed back through LR, MR and RR in turn, by reverse-encoding, to the output lamps, where the lamp encoding the original character was lit.
For example, if RR is RI, RM is R2 and RL is R3, and the offsets were all 0, then if A is input, N will light:
Note that this process is symmetric and reversible, i.e. we have just encoded A to N. If, with the same starting point, we press N we get A:
1 An ‘unsteckered’ Enigma – see later
Input
RR
RM
RL
reflector
RL
RM
RR
Lamp
A
E
S
G
L
F
W
N
N
Key press
RR
RM
RL
reflector
RL
RM
RR
Lamp
N
W
F
L
G
S
E
A
A
1.1 Advancing the rotors
Each key press changed the Enigma encoding:
When a key was pressed, the first action, before encoding the character, was to advance RR by 1 place, i.e. OR->OR+1, unless OR was 25, in which case
OR->0
OM->OM+1
So when RR completed a revolution, OM was advanced. Similarly if OM completed a revolution, OL was
advanced.
Finally, if the rotors were all on 25, the next key press would reset them all to 0. That’s what would happen to generate the example above: if the key A was pressed with the rotors at 25,25,25 they would reset to 0,0,0 and the N lamp would light.
1.2 Decoding
The reversible property means that if the receiver of the message (another Enigma operator) sets her/his Enigma to the same starting point, s/he can decode an incoming message simply by typing it in – the lamps for the original text will appear.
1.3 Simulating a Simple Enigma
The machine as described above was called a Simple Enigma Using your code from assignment 1,
1. Define Haskell data structures for a Rotor, a Reflector and a SimpleEnigma
2. Define enigmaEncode, the function which is given a letter to encode, an Enigma set up with the
rotor settings (LR, MR, RR) and a set of offsets (OL, OM, OR) and returns the encoded letter
3. Define enigmaEncodeMessage, the function which is given a message to transmit, an Enigma set up with the rotor settings (LR, MR, RR) and the initial offsets (OL, OM, OR) and returns the encoded message.
1.4 Steckering2
In wartime use the Enigma was augmented by a ‘Steckerboard’, in which pairs of letters were plugged together. If X was ‘steckered’ to Y then the steckerboard would output Y if given X and vice-versa. Unlike a reflector, the pairings were not complete: there were up to 10 pairs, the remaining letters being transmitted unchanged. The ‘steckering’ i.e. the letter pairs, was changed every day.
A single steckerboard was placed between the keyboard and the Enigma and between the Enigma and the lamps:
Rotors
Reflector LR
MR RR
Q
Steckerboard
WERTYUIOP QWERTYUIOP
Keyboard
Lamps
1.5 Simulating a Steckered Enigma
A Steckered Enigma Machine
4. Define data structures for a Steckerboard and a SteckeredEnigma (you should have an algebraic type Enigma which is either a SimpleEnigma or a SteckeredEnigma.)
5. Define enigmaEncode and enigmaEncodeMessage for a steckeredEnigma.
2 ‘Stecker’ is German for plug
6. Check that you can still decode a message enciphered by a steckeredEnigma with an identical steckeredEnigma.
2. CribsandMenus
Alan Turing’s method for breaking the Enigma code was based on ‘Cribs’. Military messages were highly formulaic and it was possible to make good guesses at phrases they would contain and the points in the message where these phrases might be found, e.g. the sender would be identified early in the message and WETTERVORHERSAGE (weather forecast) followed by a place name might appear near the end. A very short message might well be ‘nothing to report’. Experts at Bletchley Park were capable of making good guesses at the cribs.
This is a real example of a crib.
The code breaking process depended on finding a long chain of letters linking plain and cipher in the crib. A link in this chain between index I and index j means that the cipher character at i is the same as the plain character at j.
e.g. in the above start
Figure 3: A menu
Such a chain ([1,0,5,21,12,7,4…] above) was called a Menu. At Bletchley Park menus were found by hand but we will write a function to find the longest Menu in a Crib. In the above example [13,14,19,22,4,3,6,5,21,12,7,1,0,8,18,16,9] is one of several menus of length 17.
7. Define data structures for a Crib and a Menu
8. Write longestMenu, which is given a Crib and returns the longest menu.
position
0
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
20
1
2
plain
W
E
T
T
E
R
V
O
R
H
E
R
S
A
G
E
B
I
S
K
A
Y
A
cipher
R
W
I
V
T
Y
R
E
S
X
B
F
O
G
K
U
H
Q
B
A
I
S
E
position
0
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
20
1
2
plain
W
E
T
T
E
R
V
O
R
H
E
R
S
A
G
E
B
I
S
K
A
Y
A
cipher
R
W
I
V
T
Y
R
E
S
X
B
F
O
G
K
U
H
Q
B
A
I
S
E
What you must do
Tasks 1 to 9 above
Mark Scheme
Task
Credit (%)
1. Data Structures: Rotor, Reflector, SimpleEnigma
10
2. enigmaEncode for SimpleEnigma
20
3. enigmaEncodeMessage for SimpleEnigma
10
4. Data Structures: SteckerBoard, SteckeredEnigma
10
5. enigmaEncode for SteckeredEnigma
15
6. enigmaEncodeMessage for SteckeredEnigma
10
7. Data Structures: Crib, Menu
5
8. longestMenu
20
About 60% of the credit for each function/datatype is for the code, 20% for documentation and 20% for testing.
What to hand in
Your commented code, as a .hs file ready to run. Give your name in an initial comment.
Test results for the functions you’ve written (cut and paste from the console window)
How to hand in
Hand in by MOLE.
DEADLINE:MidnightonMonday21st November(Week9)