Time Limit: Java: 10000 ms / Others: 10000 ms
Memory Limit: Java: 32768 KB / Others: 32768 KB
During the Second World War, the German military forces mainly used one special machine to secure their communication: the Enigma (see Figure 4). Breaking the Enigma cipher is one of the main success stories of Allied cryptanalysis and the triumph was mainly attributed to the emergence of digital computation and the genius of the people working at Bletchley Park, the secret cryptanalysis headquarters in England. The reason for this is that, while Enigma is certainly secure against pen and paper attacks, it is quite easily breakable using digital computers.
Figure 4: An Enigma machine (picture source: http://www.nsa.gov/museum/enigma.html).
The Enigma was a rotor machine, a cipher method which was popular at that time. A rotor is an insulated disk on which electrical contacts, one for each letter of the alphabet, are placed uniformly around the periphery and on each side. An internal conduction path through the insulating material connects contacts in pairs, one on each side of the disk. An electric current entering on one side travels on an internal path through the rotor cross-section, emerging at one of the contacts on the other side (see Figure 5 for a 3D visualisation of two rotors). Figure 6 shows a schematic side view of the complete rotor system. It shows that the Enigma has three rotors 0, 2 plus an additional reflecting rotor R.
Figure 5: 3D view of two rotors.
Figure 6: Side view of the Enigma��s rotor system.
The input to Enigma is a stream of alphabetic characters without
blanks. Every character is subject to the following steps:
1. The plaintext is subject to an initial permutation IP which is implemented by a plugboard.
2. The character resulting from step 1 is sent through the three rotors 0, 2.
3. The resulting character is then sent through the reflecting rotor R.
4. The character from step 3 is passed back through the rotors 2, 0 (i.e., in the opposite direction).
5. The character from step 4 is subject to the inverse IP-1 of the initial permutation IP.
The interesting point about the use of rotors is that after processing each character, every rotor might be rotated by a certain angle (i.e., a certain amount of letters) before processing the next character. With the Enigma, rotor 0 is rotated by one in anti-clockwise direction with every new character. When 0 has finished one round (i.e., after processing 26 characters), rotor 1 moves by one character. Similarly, rotor 2 is rotated by one character when 1 has finished one revolution, and the reflecting rotor R moves when 2 has finished its rotation. Obviously, R is the slowest of the four rotors.
The process described above can be used both for encryption and decryption, provided that the permutation R implemented by the reflecting rotor is an involution. That means R = R-1, or, equivalently, whenever . You may assume that this condition holds.
The secret key of the Enigma consists of (1) the rotors 0, 2, and R, (2) the plugboard permutation IP, and (3) the initial rotational displacements k0, k1, k2, kR of 0, 2, and R (see below). The rotors were changed infrequently and were selected from a set of four possible rotors in the Wehrmacht model.
You are time-warped to Bletchley Park together with your laptop and should help to decipher some messages which have been intercepted over the day. You are given the entire ciphertext, parts of the plaintext, and parts of the Enigma key. Your task is to determine the correct key and finally complete the plaintext by decoding the ciphertext.
2 wfbtiznuvcqejpokshxgmadyrl hmrgnqpkjcaivwluebfzsyxtdo druahlbfzvgmwckxpiqysontje owtvskypjifmluahrqecndbzgx ?bcdefghijklmnopqrstuvwxyz aaaa manyorganizationsrelyoncom??ters grsuztldsznkwnerdpfbovvqnobkyiqn oqzunvhtxwryfebicmjpklsgda zupogrskynxtwdfqvbliejcmha kzvlyjuodmscewxtfbphriqgna gbcnylaztwkfmdspqvoiurjxeh rfyhkxbuvplgtqmdiewjosznca dmeo ??? ave