COM2108: Functional Programming – 2022
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
COM2108: Functional Programming – 2022
Functional Programming Design Case Study
This document sets out the case study for the grading assignment and the tasks that you need to complete for that assignment. It explains the Enigma machine (the machine used extensively by Nazi Germany in World War II to protect sensitive communication) and the Bombe (the machine developed by codebreakers at Bletchly Park to help decode messages that had been encrypted with an Enigma machine). Specifically, the Bombe was designed to discover some of the daily settings of the Enigma machines on the various German mil- itary networks: the set of rotors in use and their positions in the machine, the rotor start positions for the message, and the wirings of the plugboard.
The purpose of the grading assignment is to determine how well you have developed your skills in functional programming. Remember, you will already have achieved 40% in the module by passing the threshold test; any marks you earn here are in addition to that. The grading assignment is meant to be difficult: the average module mark is expected to be about 60%. You would get 60% in the module if you achieve of the marks for the grading assignment – in other words, the average student should expect to receive about of the marks for this assignment. Check the marking scheme carefully, noting that correctness of your solution only contributes a small amount to the mark.
Please note that there is a lot of background reading in this document. The point being, you are being tested on your ability to take a problem and apply a functional approach to solving it. You are being tested not just on your ability to code a solution, but your ability to analyse a problem, develop a solution and test that your solution satisfies the problem.
1 The Enigma Machine
The Enigma machine was an encryption/decryption machine based on rotors. A rotor im- plemented a fixed alphabetic substitution cipher. The ciphers for the first five Enigma ro- tors RI, RII, RIII, RIV and RV were
plain |
ABCDEFGHIJKLMNOPQRSTUVWXYZ |
RI |
EKMFLGDQVZNTOWYHXUSPAIBRCJ |
RII |
AJDKSIRUXBLHWTMCQGZNPYFVOE |
RIII |
BDFHJLCPRTXVZNYEIWGAKMUSQO |
RIV |
ESOVPZJAYQUIRHXLNFTGKDCMWB |
RV |
VZBRGITYUPSDNHLXAWMJQOFECK |
These rotors were internally wired with these mappings, so an input at position A (0) on ro- tor I would always give an output of E, and an input at position Z (25) on rotor II would always give an output of E. Any rotor could be offset by a given number of positions (0 to 25), which has a slightly different effect to the shift in a Cae- sar cypher (that we looked at in a programming exercise). The wiring of the rotor was fixed, so changing the offset shifted the rotor relative to its input/output positions. For example, figure ?? shows rotor I in its “home” position (left) and in position 1 (1 step counter-clockwise) (right), together with the encoding for input ‘A’ in both cases. In other words, the shift changes the in- put letter to the rotor, which forces the signal through a different path internally to the rotor, but also, the output signal is also shifted (again,
look at the right-hand part of the diagram, where in a J).
Figure 2: Wiring of rotor I in its “home” position (left), and with offset 1 (right). The red arrows show the output for an input of ‘A’ in each case.
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 ..RVRI,RII. 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 Enigma (or ‘unsteckered’ Enigma – see later for an explanation of steckering), 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) where c1 was changed to c2, and c2 to c1). The standard reflector pairings (known as reflector B) 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.
Figure 3: Schematic for a simplified Enigma machine
For example, if RR is RI, MR is RII and LR is RIII, and the offsets were all 0i1, then if A is input, N will light:
Key press |
RR |
MR |
LR |
reflector |
LR |
MR |
RR |
Lamp |
A |
E |
S |
G |
L |
F |
W |
N |
N |
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:
Key press |
RR |
MR |
LR |
reflector |
LR |
MR |
RR |
Lamp |
N |
W |
F |
L |
G |
S |
E |
A |
A |
1.1 Advancing the rotors
Every rotor had a pin, at a different position for each rotor, which, when passed, would cause the left-adjacent rotor to advance by one position. The rightmost rotor advanced with every keypress.
The knock-on positions for each of the rotors was as follows:
Rotor |
Knock-on Position |
(Numerically) |
I |
R |
17 |
II |
F |
5 |
III |
W |
22 |
IV |
K |
10 |
V |
A |
0 |
Cryptanalysts at Bletchly Park used the mnemonic Royal Flags Wave Kings Above to re- member these positions.
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 at position R before the key was pressed, in which case
1. OR → (OR+1) mod 26
2. OM → (OM+1) mod 26
So when RR progresses past its knock-on position, OM was advanced. Similarly if OM progresses past its knock-on position, OL was advanced. If either rotor is at the Z position, the next advance takes it to A.
Note that the rotor movement happens before the signal passes through the rotors to gen- erate the encrypted letter. So for the example above, the rotors would be in position 0,0,25 (or A, A, Z) initially: if the key A was pressed with the rotors at this position they would advance to position 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 opera- tor) 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 Steckering
In wartime use the Enigma was augmented by a plugboard, in which pairs of letters were plugged together. If X was ‘steckered’ to Y then the plugboard 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. Here is an example:
A single plugboard was placed between the keyboard and the Enigma and between the Enigma and the lamps:
Figure 4: A “Steckerboard” (plugboard) for an Enigma Machine
School of Mathematics - University of Manchester, CC BY 2.0
https://creativecommons.org/licenses/by/2.0, via Wikimedia Commons
Figure 5: Schematic for a Steckered Enigma Machine
A steckered enigma machine was still symmetrical (that is, you could decode a message from a steckered enigma machine using an identical steckered enigma machine).
2 Breaking the Enigma
2.1 The problem the codebreakers faced.
The Bletchley Park (BP) codebreakers knew how the Enigma machine worked, and they knew that the military version was steckered. They also knew the 5 rotors, with their sub- stitution codes, and the reflector pairs2.
The codebreaker’s daily task was to find the choice of 3 rotors from 5, the initial offsets and
the stecker pairs, on the basis of the messages which were being transmitted on that day. The number of possible solutions was around 1023 . Computers hadn’t been invented...
2.2 Bombes
The codebreakers didn’t have computers but they could build hardware to simulate simple Enigmas, using components adapted from telephone exchanges. These devices were called Bombes (named after an ice cream). A restored Bombe can be seen in Fig. ??, Given a choice of rotors and initial offsets, a bombe could find the encoding for any character at any position in the message.
Each vertical set of 3 dials corresponds to the 3 rotors of an Enigma. So a bombe could run 36 simulations. It took around 20 minutes to go through the 263 offsets.
Over 200 Bombes were built, but the vast majority were destroyed at the end of the war, and the remaining few, shortly thereafter.
2.3 Cribs and Menus
Codebreaking was dependent on having a Crib Figure 6: A Bombe
and a Menu to guide the search through the crib.
Alan Turing’s method for breaking the Enigma sa/2.0, via Wikimedia Commons
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.
2022-11-05