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 make-backward-offsets.

(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.

No Comments Yet