Now the real fun begins, we are going to break Enigma's code !
The commercial Enigma machine is significantly harder to break. It is based on rotors which are rotating transposition tables. An Enigma machine has a keyboard, three rotors, a reflector and a display. When a key is pressed (‘A’ in the example in figure 1), the characters traverses the three rotors once forward, then it is transposed to another character by the reflector (a transposition table that is symmetric and irreflexive), then it traverses the three same rotors backward to finally appear on the display.
However, the characteristic that makes Enigma powerful is that after each such encrytption of a character, the first (fast) rotor rotates (as the name suggests) by one position, thus changing the transposition table. Moreover, when the fast rotor has completed a whole revolution, the medium rotor turns once and when the middle rotor completes a revolution, the slow rotor turns as well. As a result, pressing the same character twice does not yield the same output character (see figure 2).
Observe that thanks to the reflector, pressing the ciphered charcater’s key when the machine is in the same setting as during encryption yields the original plaintext character! This makes the Enigma machine very convenient to use. The sender and the receiver only need to share the rotors initial positions when the encryption began. The receiver therefore simply types the ciphertext to obtain the plaintext. We call the positions of the rotors (in {0,…,25}3) the encryption key, or simply the key.
Write a constraint program which “emulates” a machine with a single rotor (and
no reflector). The array of variables plaintext stands for the message to encrypt,
ciphertext for the encrypted message and the variable key stands for the position
of the rotor when encrypting the first character.
Hint : One way to do it is to compute all the possible positions for the rotor.
We want to decipher the encrypted message “ROOETWKCYDXDKDGOLUIYRVKFLPD” that was obtained by using a single rotor. We have a model of the rotor (perm[0]) that was used because our navy found it when boarding a U-pedal-boat, however we do not know what key was used to encrypt the message.
To give us the edge, our intelligence agency worked day and night and arrived at the following conclusion: the ennemy is devious, yet always very polite, so the message must start with a greeting (“HI” or “HELLO”). This is what is called a crib: we know that the letter ‘H’, when encoded in first position, corresponds to a ‘L’.
Write a constraint program which decipher a message (“ROOETWKCYDXDKDGOLUIYRVKFLPD”) encrypted with a single rotor (perm[0]), given a crib (“H”). You have to define the branching scheme, either you start branching on the plaintext variables, or you start branching on the key variable. There will be several solutions satisfying all the constraints, however there is only one solution which is plain english.
We have intercepted a new ciphered message (“HHWBGGLRDUSPEBBINYGKSGEAMQOSMEEHTGJKNTGCQURVMNEUBCTWGMHBK”), however, the ennemy has used not one but two rotors (a fast perm[0] and a medium rotor perm[1]). Being grossly arrogant, there are good reasons to believe that the ennemy sent a message starting with a demonstrative pronoum (“THE”, “THAT”, “THOSE”, etc.), so the crib is “TH”. Write a constraint program to decipher it. Your program should work with k rotors.
It appears that the machine that our navy found on the earlier U-pedal-boat, and which our expert analyst first classified as a “minitel” (whatever that is) was in fact an Enigma machine. With the knowledge of its mechanism (given by rotors and reflector), we will be able to break the ennemy code! First we should be able to emulate it. Write a constraint program which, given a message plaintext and an array of (3) rotor positions key, computes the encrypted message in the array of variables ciphertext.
Alright, now we can eventually break the ennemy code! We managed to lure an ennemy homming pigeon by skilfully disguising a Sussex cottage into a Bavarian castle. Here’s the message that was tied to its ankle: “NVGSEZEUFBEVTWCLPZARJKLFKNPFMBZYCZSLCKQKOUUZIHFHVAFDHPZOLIQTFSLJROUNGDXYLONQBLWKXZGRAH”. Our expert psychoanalysts tell us that the ennemy is so self-centered (the subsequent dispute about the root cause being mother or father-related hasn't stopped yet, but that's beside the point) that the message is likely to start with “WE”. Write a constraint program to decipher it. In the meantime, our spies discovered that an enemy's special agent has infiltrated our Discord server: the Enigma Bot is working for them ! Our agents thinks that the message you just decoded is in fact a password for it ! Send the password to the bot in a private message(right-click on its name to send it a private message) to see its reaction !