Tuesday, September 20, 2011

Enigma Machines

I noticed a fun blog post about recreating the Enigma machine in Python. For those who need a refresher, an Enigma machine was an encryption device used before and during World War II. I thought it would be fun to implement this in Factor.

Build It

Our alphabet will be the 26 letters in the English alphabet, indexed from 0 to 25 ("a" to "z"):

: <alphabet> ( -- seq )
    26 iota >array ;

The Enigma machine is made up of a number of "cogs", which contain an encoding. We will create a cog using a randomized alphabet:

: <cog> ( -- cog )
    <alphabet> randomize ;

We need to create a utility function to remove a random element from a sequence:

: remove-random ( seq -- elt seq' )
    [ length random ] keep [ nth ] [ remove-nth ] 2bi ;

A special rotor called a "reflector" connected pairs of outputs, ensuring that encryption and decryption were the same process. It also gave the Enigma machine the property that no letter encrypted to itself (a flaw which was used to help break the code). We can create a reflector by taking the alphabet, and randomly exchanging pairs of elements:

: <reflector> ( -- reflector )
    <alphabet> dup length iota [ dup empty? ] [
        remove-random remove-random [ pick exchange ] dip
    ] until drop ;

We can now create an Enigma machine with a number of cogs and a reflector:

TUPLE: enigma cogs prev-cogs reflector ;

: <enigma> ( num-cogs -- enigma )
    [ <cog> ] replicate dup clone <reflector> enigma boa ;

We need a way to check for special characters (those not in the 26 letter alphabet):

: special? ( n -- ? )
    [ 25 > ] [ 0 < ] bi or ;

We need a utility function to change several elements of a sequence at the same time:

: change-nths ( indices seq quot: ( elt -- elt' ) -- )
    [ change-nth ] 2curry each ; inline

Encoding a piece of text is where all the work is performed. The main strategy is to apply each character (that isn't special) through the cogs and then the reflector to find the encoded character, and then cycle the cogs to prepare for the next character.

:: encode ( text enigma -- cipher-text )
    0 :> ln!
    enigma cogs>> :> cogs
    enigma reflector>> :> reflector
    text >lower [
        CHAR: a mod dup special? [
            ln 1 + ln!
            cogs [ nth ] each reflector nth
            cogs reverse [ index ] each CHAR: a +
            cogs length iota [ 6 * 1 + ln mod zero? ] filter
            cogs [ unclip prefix ] change-nths
        ] unless
    ] map ;
Note: this converts the text to lowercase before encoding. The encode word could be expanded to support uppercase, but its much simpler this way.

If we make a word to reset the cogs back to the original configuration, we can verify that the encrypted text can be decrypted back to the original.

: reset-cogs ( enigma -- enigma )
    dup prev-cogs>> >>cogs ;

Try It

We can experiment with this in the Listener, creating a 4-cog Enigma machine and then encoding, resetting, and encoding again:

( scratchpad ) 4 <enigma>

( scratchpad ) "hello, world" over encode [ print ] keep
luhhn, xnzha

( scratchpad ) over reset-cogs encode print
hello, world

The code for this is on my Github.

No comments: