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 xed alphabetic substitution cipher. The ciphers for the rst ve 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 oset 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 rst 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 reector 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

reector

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

reector

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 rst 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 nd 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 didnt 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 Turings 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.