Enigma 2: Encrypting characters
Each rotor in the Enigma machine performs a simple character substitution for each letter A-Z. The substitution is described by a string, like "EKMFLGDQVZNTOWYHXUSPAIBRCJ". This means that, with the rotor in position 0, the first letter, A is changed to E, B to K, C to M, and on up to Z to J.
What happens when the rotor advances to a new position? I found it useful to see the letters in the substitution string as relative offsets: A to E is +4, B to K is +9. C to M is +10. So when the rotor advances to position 1, A is changed with the second offset, +9, to J, B +10 to L, etc. Z wraps around to the first offset, +4, and changes to D.
With a couple of helper functions, we define a function
make-offsets that converts a rotor substitution string into a list of offsets.
(deftest substitutes-to-offsets (is (= (concat (range 1 14) (range 13 26)) (make-offsets "BDFHJLNPRTVXZACEGIKMOQSUWY")))) (defn letter-to-int [letter] (-> letter int (- (int \A)))) (defn decrease [position change] (-> position (- change) (mod 26))) (defn make-offsets [substitutes] (map-indexed (fn [i letter] (-> letter letter-to-int (decrease i))) substitutes))
Now we can define a function
apply-offset that uses the offsets and a rotor position to encrypt an input. (We use integers 0-25 instead of characters A-Z, so we don't have to keep converting between integers and characters.)
(deftest encrypt-no-wrap (let [offsets (make-offsets "ABXCDEFGHIJKLMNOPQRSTUVWYZ")] (is (= 22 (apply-offset 1 1 offsets))))) (deftest encrypt-wrap (let [offsets (make-offsets "AXBCDEFGHIJKLMNOPQRSTUVWYZ")] (is (= 24 (apply-offset 2 25 offsets))))) (defn increase [position change] (-> position (+ change) (mod 26))) (defn apply-offset [input position offsets] (-> offsets (nth (increase position input)) (increase input)))
The Enigma machine uses the output of each rotor as input to the next rotor. The last rotor is a "reflector" that sends its output back to the previous rotor. This is passed backwards through each rotor, ending with the first. How do we perform a "backwards" substitution? We find the letter that is changed into our current value. Using our sample rotor substitution string "EKMFLGDQVZNTOWYHXUSPAIBRCJ" in position 0, U is changed to A, so the backwards substitution of A is U, B is W, C is Y, etc. Once again, to handle rotation of the rotor, it's useful to create a list of offsets.
We rename our previous function to
make-forward-offsets and add a function
(deftest substitutes-to-backward-offsets (is (= (mapcat (fn [i] (list i (+ i 12))) (range 13 0 -1)) (make-backward-offsets "BDFHJLNPRTVXZACEGIKMOQSUWY")))) (defn int-to-letter [input] (-> input (+ (int \A)) char)) (defn make-backward-offsets [substitutes] (map (fn [i] (decrease (index-of substitutes (int-to-letter i)) i)) (range 0 26)))
Now we can re-use
apply-offset to do backward encryption.
(deftest backward-encrypt-no-wrap (let [offsets (make-backward-offsets "ABYCDEFGHIJKLMNOPQRSTUVWXZ")] (is (= 1 (apply-offset 23 1 offsets)))) ) (deftest backward-encrypt-wrap (let [offsets (make-backward-offsets "AWBCDEFGHIJKLMNOPQRSTUVXYZ")] (is (= 2 (apply-offset 23 25 offsets)))) )
Next: Putting the pieces together to encrypt and decrypt strings.