Friday, April 10, 2015

Enigma Cipher

While there are dozens of Enigma machine simulators available on the net, I decided to do the research into the German M3 and M4 Enigma machines and implement an C++ class that would perform the Enigma cipher of either machine. 

This was really just a mental exercise for fun and to keep on building things while I am looking for work.  No attempt will be made here to describe the operation of the German Enigma machine.

There are dozens of excellent write-ups on the functioning of Enigma machines and entire web sites dedicated to all of the Enigma versions that were produced.  I will not endeavor to replicate that history here as it is quite extensive.  I would recommend in particular the excellent site here as an invaluable resource for the curious about such things.

My implementation will by default, if no settings are changed, emulate an M3 machine with rotors set to A A A, rings set to 0 0 0 and rotors installed (left to right) are I, II, and III.  Methods are available to fully configure the Enigma engine as desired.

The class is implemented as two files (enigma.h and enigma.cpp).  I have built these using Visual Studio 2013 and written a short test application to exercise the class which I include below, should you find it useful.  I will verify the functionality of the class on Arduino, but have not yet accomplished that task.  I will post the entire sketch when I have verified the functionality on Arduino.  If you don't wish to wait, you will need port and test the implementation yourself.

It is unlikely that you will be able to copy/paste the code below as is without any changes into an arbitrary development environment.  The code is provided as an example of how to implement the engine.  A fully working Arduino implementation will be the subject of a subsequent post.

Here is the class definition file enigma.h:

// Enigma M3/M4 engine
// Copyright (c) 2015 Jeff Whitlatch - ko7m - All rights reserved.
//

#pragma once

enum EnigmaTypes    { EnigmaTypeM3, EnigmaTypeM4 };

enum RotorPositions { RotorPosG, RotorPosL, RotorPosM, RotorPosR };

enum Rotors         { RotorI, RotorII, RotorIII, RotorIV, RotorV, 
                      RotorVI, RotorVII, RotorVIII, RotorB, RotorG,
                      RotorNone };

enum Reflectors     { ReflectorB, ReflectorC, ReflectorThinB, ReflectorThinG };

enum Letters        { LetterA, LetterB, LetterC, LetterD, LetterE, LetterF, LetterG,
                      LetterH, LetterI, LetterJ, LetterK, LetterL, LetterM, LetterN,
                      LetterO, LetterP, LetterQ, LetterR, LetterS, LetterT, LetterU,
                      LetterV, LetterW, LetterX, LetterY, LetterZ };

enum Direction      { dirRightToLeft, dirLeftToRight };

// Rotor Wiring
//
//             1111111111222222
//   01234567890123456789012345
//   ABCDEFGHIJKLMNOPQRSTUVWXYZ
const static char *rgRotors[10] =
{
    "EKMFLGDQVZNTOWYHXUSPAIBRCJ",   // Rotor I
    "AJDKSIRUXBLHWTMCQGZNPYFVOE",   // Rotor II
    "BDFHJLCPRTXVZNYEIWGAKMUSQO",   // Rotor III
    "ESOVPZJAYQUIRHXLNFTGKDCMWB",   // Rotor IV
    "VZBRGITYUPSDNHLXAWMJQOFECK",   // Rotor V
    "JPGVOUMFYQBENHZRDKASXLICTW",   // Rotor VI
    "NZJHGRCXMYSWBOUFAIVLPEKQDT",   // Rotor VII
    "FKQHTLXOCBJSPDZRAMEWNIUYGV",   // Rotor VIII
    "LEYJVCNIXWPBQMDRTAKZGFUHOS",   // M4 Greek Rotor "b" (beta)
    "FSOKANUERHMBTIYCWLQPZXVGJD"    // M4 Greek Rotor "g" (gama)
};

// Reflectors "B" and "C" (including M4 thin reflectors) wiring
const static char *rgReflectors[4] =
{
    "YRUHQSLDPXNGOKMIEBFZCWVJAT",   // M3 B
    "FVPJIAOYEDRZXWGCTKUQSBNMHL",   // M3 C
    "ENKQAUYWJICOPBLMDXZVFTHRGS",   // M4 thin B (beta)
    "RDOBJNTKVEHMLFCWZAXGYIPSUQ"    // M4 thin G (gamma)
};

// The rotor wheel notch definitions
// Determines when the wheel to the right moves the wheel to the left.
const static int rgNotches[8][2] =
{
    { LetterQ, LetterQ },       //   Q - one notch  (Rotor I)
    { LetterE, LetterE },       //   E - one notch  (Rotor II)
    { LetterV, LetterV },       //   V - one notch  (Rotor III)
    { LetterJ, LetterJ },       //   J - one notch  (Rotor IV)
    { LetterZ, LetterZ },       //   Z - one notch  (Rotor V)
    { LetterZ, LetterM },       // Z/M - two notches (Rotor VI)
    { LetterZ, LetterM },       // Z/M - two notches (Rotor VII)
    { LetterZ, LetterM }        // Z/M - two notches (Rotor VIII)
};

class Enigma
{
public:
    Enigma();
    ~Enigma();

    void rotateDials();
    void doCipher(char *szClear, char *szCipher, int len);
    int swapPlugs(int value);
    int mapLetter(int value, int pos, int dir);
    int reflectLetter(int value);
    int adjustValue(int value);

    void setType(EnigmaTypes T);
    void setRotors(Rotors G, Rotors L, Rotors M, Rotors R);
    void setRotorPos(int G, int L, int M, int R);
    void setRingPos(int G, int L, int M, int R);
    void setPlug(int A, int B);

    EnigmaTypes type;       // Type of Enigma machine defaults to M3

    Rotors rgRotorSet[4];   // The set of rotors currently in use
    int rgRotorPos[4];      // The current position of each rotor in use
    int rgRingPos[4];       // Current ring position offset of each rotor in use

    Reflectors reflector;   // The reflector in use

    int plugBoard[26];      // Plugboard (steckerbrett) mapping

};

The implementation of the class is straightforward.  The class constructor sets the defaults already described.  Methods are provided to change any of the operational parameters.  the Enigma::doCipher method is then called passing in the text to be encoded or decoded and a buffer in which to put the results.

Don't beat me up too much on the code style as it is quite raw.  I am sure it will evolve over time to a cleaner implementation.  There is precious little error checking, so check your random parameter tendencies at the door...  :)

Here is the class implementation file enigma.cpp:

// Enigma M3/M4 engine
// Copyright (c) 2015 Jeff Whitlatch - ko7m - All rights reserved.
//

#include "stdafx.h"

// Enigma M3/M4 class constructor initializes the machine to
// M3 with rotors I, II and III, rotor values A A A and rings A A A
// The plugboard is self steckered on all plugs
//
Enigma::Enigma()
{
    // By default, assume M3
    setType(EnigmaTypeM3);

    // By default use rotors I, II, III
    setRotors(RotorNone, RotorI, RotorII, RotorIII);

    // Initial rotor positions are A A A
    setRotorPos(LetterA, LetterA, LetterA, LetterA);

    // Initial ring position A A A
    setRingPos(LetterA, LetterA, LetterA, LetterA);

    // Self stecker each plugboard position
    for (int i = LetterA; i <= LetterZ; i++)
        plugBoard[i] = i;
}

// Class destructor
Enigma::~Enigma()
{
}

// Set the Enigma machine type
void Enigma::setType(EnigmaTypes T)
{
    type = T;
}

// Select the rotor set
void Enigma::setRotors(Rotors G, Rotors L, Rotors M, Rotors R)
{
    rgRotorSet[RotorPosG] = G;
    rgRotorSet[RotorPosL] = L;
    rgRotorSet[RotorPosM] = M;
    rgRotorSet[RotorPosR] = R;
}

// Set the initial rotor positions
void Enigma::setRotorPos(int G, int L, int M, int R)
{
    rgRotorPos[RotorPosG] = G;
    rgRotorPos[RotorPosL] = L;
    rgRotorPos[RotorPosM] = M;
    rgRotorPos[RotorPosR] = R;
}

// Set the initial ring positions
void Enigma::setRingPos(int G, int L, int M, int R)
{
    rgRingPos[RotorPosG] = G;
    rgRingPos[RotorPosL] = L;
    rgRingPos[RotorPosM] = M;
    rgRingPos[RotorPosR] = R;
}

// Set a stecker pair
void Enigma::setPlug(int A, int B)
{
    // Remove any previous steckers of either plug
    for (int i = LetterA; i <= LetterZ; i++)
        if (plugBoard[i] == A || plugBoard[i] == B) plugBoard[i] = i;

    plugBoard[A] = B;
    plugBoard[B] = A;
}

// Adjust the passed value to be LetterA..LetterZ (0..25)
int Enigma::adjustValue(int value)
{
    if (value < LetterA)
    {
        // If negative number, count backwards from Z
        // Emulates wheel rotating backwards
        value += (LetterZ + 1);
    }
    else if (value > LetterZ)
    {
        // If number greater than Z, count forward from A
        // Emulates wheel rotating forwards
        value -= (LetterZ + 1);
    }

    return value;
}


// Perform rotation of the encoding rotors taking into account single and double stepping
// If we are simulating an M4 machine, the greek wheel (RotorG) does not rotate once installed.
//
void Enigma::rotateDials()
{
    // Check if the right rotor is at a notch position
    if (rgRotorPos[RotorPosR] == rgNotches[rgRotorSet[RotorPosR]][0] || 
        rgRotorPos[RotorPosR] == rgNotches[rgRotorSet[RotorPosR]][1])
    {
        // If the notch on the right wheel is reached rotate middle wheel
        // But first check if it too is a notch
        if (rgRotorPos[RotorPosM] == rgNotches[rgRotorSet[RotorPosM]][0] || 
            rgRotorPos[RotorPosM] == rgNotches[rgRotorSet[RotorPosM]][1])
        {
            // If the notch on the middle wheel is reached rotate left wheel
            rgRotorPos[RotorPosL]++;
        }
        rgRotorPos[RotorPosM]++;
    }
    else 
    {
        if (rgRotorPos[RotorPosM] == rgNotches[rgRotorSet[RotorPosM]][0] || 
            rgRotorPos[RotorPosM] == rgNotches[rgRotorSet[RotorPosM]][1])
        {
            // If the notch on the middle wheel is reached rotate left AND middle wheels
            // (the double stepping mechanism)
            rgRotorPos[RotorPosL]++;
            rgRotorPos[RotorPosM]++;
        }
    }

    // Rotate right wheel (this wheel is always rotated).
    rgRotorPos[RotorPosR]++;

    // All rotor positions are modulo 26
    rgRotorPos[RotorPosL] %= 26;
    rgRotorPos[RotorPosM] %= 26;
    rgRotorPos[RotorPosR] %= 26;
}

// Swap plugboard characters.  Assumes initialized to self steckered
//
int Enigma::swapPlugs(int value)
{
    return plugBoard[value];
}

// Map a letter through a particular rotor in either direction
//
int Enigma::mapLetter(int value, int rp, int direction)
{
    char chIn = value + 'A';

    // Wheels rotation is anti-clockwise when viewed from the right
    value = adjustValue(value - rgRingPos[rp]);     // Adjust character by ring position
    value = adjustValue(value + rgRotorPos[rp]);    // and by amount of rotation

    // Map letter either right to left or left to right according to direction
    if (direction == dirRightToLeft)
    {
        value = *(rgRotors[rgRotorSet[rp]] + value) - 'A';
    }
    else
    {
        const char *pch = strchr(rgRotors[rgRotorSet[rp]], value + 'A');
        value = pch - rgRotors[rgRotorSet[rp]];
    }

    value = adjustValue(value - rgRotorPos[rp]);
    value = adjustValue(value + rgRingPos[rp]);

    return value;
}

// Reflect a letter through the current reflector
//
int Enigma::reflectLetter(int value)
{
    const char *pch = strchr(rgReflectors[reflector], value + 'A');
    value = pch - rgReflectors[reflector];
    return value;
}

// Perform the Enigma cypher
// Caller must provide sufficient buffer space for ciphertext output
//
void Enigma::doCipher(char *szClear, char *szCipher, int len)
{
    char *pch = szClear;
    char *pchOut = szCipher;
    char ch;
    unsigned cchOut = 0;

    memset(szCipher, 0, len);           // Clear the cipher text

    // If using M4 Enigma, make sure the thin reflectors are in use.
    if (type == EnigmaTypeM4 && reflector != ReflectorThinB && reflector != ReflectorThinG)
    {
        // If we don't have a thin reflector, force thin reflector B
        reflector = ReflectorThinB;
    }
    else 
    {
        // If we don't have a thick reflector, force reflector B
        if (reflector != ReflectorB && reflector != ReflectorC)
            reflector = ReflectorB;
    }

    // Walk through each character to be encrypted or decrypted and perform the transformation
    while (ch = *pch++)
    {
        // Convert to upper case as a convenience
        if (ch >= 'a' && ch <= 'z')
        {
            ch -= 'a';
            ch += 'A';
        }

        // Skip anything that is not A-Z
        if (ch < 'A' || ch > 'Z')
            continue;

        // Rotors always turn before performing the encryption of each letter
        //
        rotateDials();

        // Convert input character to LetterA..LetterZ (0..25)
        int value = (ch - 'A'); 

        // Run the value through the plugboard and perform any swaps and route to ETW
        value = swapPlugs(value);

        // From ETW, value goes to right-most rotor
        value = mapLetter(value, RotorPosR, dirRightToLeft);

        // Then to the middle rotor
        value = mapLetter(value, RotorPosM, dirRightToLeft);

        // And then the left rotor
        value = mapLetter(value, RotorPosL, dirRightToLeft);

        // Now, if simulating M4 Enigma, use the greek wheel
        if (type == EnigmaTypeM4)
            value = mapLetter(value, RotorPosG, dirRightToLeft);

        // Next is the reflector
        value = reflectLetter(value);

        // Pass back through rotors and ETW
        if (type == EnigmaTypeM4)
            value = mapLetter(value, RotorPosG, dirLeftToRight);

        value = mapLetter(value, RotorPosL, dirLeftToRight);
        value = mapLetter(value, RotorPosM, dirLeftToRight);
        value = mapLetter(value, RotorPosR, dirLeftToRight);

        // And again back through the plugboard
        value = swapPlugs(value);

        // Convert the value to text and insert in output buffer
        *pchOut++ = value + 'A';

        // Break into 5 character words
        if (++cchOut % 5 == 0) *pchOut++ = ' ';

        // Terminate the string after each character is inserted
        *pchOut = '\0';
    }

}

Finally, a simple example program that uses the class to encode a cleartext string and then decode it back to the original string.

Remember that the cipher uses only 26 symbols for the text of a message.  The output of the engine is cipher text that is devoid of numbers, punctuation and even spaces.  The text is all smashed together and then broken into 5 character words as was typical during the war.

// Navy M3/M4 Enigma emulator
// Copyright (c) 2015 Jeff Whitlatch - ko7m - All rights reserved.
//
// Version history:
//
// Version 1.0:  Initial code
//

#include "stdafx.h"

// Example use of Enigma engine
//
int _tmain(int argc, _TCHAR* argv[])
{
    // Clear and cipher text buffers
    char *szClearText = "Now is the time for all good men to come to the aid of thier country.";
    char rgbBuf1[512];
    char rgbBuf2[512];

    // Create a couple of instances of the engine to easily reset to default state 
    Enigma e1;      // Encode instance of engine
    Enigma e2;      // Decode instance of engine

    // Set up desired rotor set
    e1.setRotors(RotorNone, RotorI, RotorIV, RotorV);
    e2.setRotors(RotorNone, RotorI, RotorIV, RotorV);

    // Set the ring offset for each rotor in the set
    e1.setRingPos(LetterA, LetterT, LetterF, LetterS);
    e2.setRingPos(LetterA, LetterT, LetterF, LetterS);

    // Set plugboard (steckerbrett) letter pairs
    e1.setPlug(LetterA, LetterT);    // Swap A and T
    e1.setPlug(LetterB, LetterJ);    // Swap B and J
    e1.setPlug(LetterD, LetterL);    // etc...
    e1.setPlug(LetterF, LetterP);
    e1.setPlug(LetterG, LetterI);
    e1.setPlug(LetterH, LetterY);
    e1.setPlug(LetterK, LetterZ);
    e1.setPlug(LetterM, LetterR);
    e1.setPlug(LetterN, LetterW);
    e1.setPlug(LetterQ, LetterX);

    e2.setPlug(LetterA, LetterT);
    e2.setPlug(LetterB, LetterJ);
    e2.setPlug(LetterD, LetterL);
    e2.setPlug(LetterF, LetterP);
    e2.setPlug(LetterG, LetterI);
    e2.setPlug(LetterH, LetterY);
    e2.setPlug(LetterK, LetterZ);
    e2.setPlug(LetterM, LetterR);
    e2.setPlug(LetterN, LetterW);
    e2.setPlug(LetterQ, LetterX);

    // Run the cipher to encode the cleartext to produce the cipher text
    e1.doCipher(szClearText, &rgbBuf1[0], 512);
    printf("Clear:  <%s>\n", szClearText);
    printf("Cipher: <%s>\n", &rgbBuf1[0]);  
    
    // Take the ciphertext just produced and run thru again to decode back to cleartext
    e2.doCipher(&rgbBuf1[0], &rgbBuf2[0], 512);
    printf("Cipher: <%s>\n", &rgbBuf1[0]);
    printf("Clear:  <%s>\n", &rgbBuf2[0]);
    return 0;

}

The example code above produces the following output:

Clear:  <Now is the time for all good men to come to the aid of thier country.>
Cipher: <ODLKP BMQHG CGAHP XNXYY TIRLS KWPGG ZVTYG GQBWY NWREK EZTOS WZM>
Cipher: <ODLKP BMQHG CGAHP XNXYY TIRLS KWPGG ZVTYG GQBWY NWREK EZTOS WZM>
Clear:  <NOWIS THETI MEFOR ALLGO ODMEN TOCOM ETOTH EAIDO FTHIE RCOUN TRY>

The input cleartext will have lower case converted to upper case and everything that is not A..Z discarded.  The text is then encoded and output as a series of 5 character words.  No attempt is made to make the last word exactly 5 characters.

I hope you enjoy fiddling around with this example and if you stand by a just a little, I will provide a full listing for an Arduino port of this code.

As always, I am happy to help anyone who has questions or comments.  Post a comment here or drop me at note at ko7m at arrl dot net and I will be delighted to help.

No comments:

Post a Comment