Tuesday, April 21, 2015

The Kurier System

In the same vein as my previous postings on the Enigma cipher, I have been doing some reading about some of the challenges that faced the Bletchley Park code breakers during WWII, particularly with regard to Kriegsmarine M4 U-Boat message traffic.

A technique employed by the Gernman U-boats involved coordination between multiple U-boats.  Wolfepacks or Rudeltaktik as it was known to the Germans were created as a means to defeat allied ship convoys.  First tested in 1940, the concept is simple.  Gather U-boats in patrole lines to scout for convoys.  Once spotted by the first boat, it was designated as "shadower" and would follow the convoy and report its heading and speed to the U-boat tactical command.  Coordination between U-boats allowed them to form up around the convoy and attack with as many U-boats as possible during night to overwhelm the escorts.  So successful were wolfepacks that in 1942 convoy operations in the North Atlantic were paused for a time.

To combat the wolfepacks the biggest impact was obtained through HF/DF technologies (High Frequency/Direction Finding, known as "Huff Duff" to sailors).  Once a U-boat sighted a convoy, coordination between boats involved Enigma encoded messages being exchanged.  HF/DF was not new having been used for navigation purposes for years.  The Royal Navy designed an apparatus that could take bearings on the transmitters employed by German U-boats.



Shore-based direction finding installations were constructed on both shores of the Atlantic as well as Iceland, Greenland and Bermuda.  Anytime the Germans transmitted , the HF/DF equipment could get bearings on the approximate location of the U-boat.  Note that it was not important to understand the content of the U-boat messages.  It was sufficient to know the general area from which the transmissions were emanating and thus avoid the area.  Ship-borne HF/DF equipment allowed U-boats to be located and sank or at least forced to dive and remain submerged for hours disrupting coordination of wolfepacks.  Thus the HF/DF efforts struck at the very core of wolfepack tactics.  The German Navy needed to minimize exposure to HF/DF by reducing significantly the time required to transmit messages.

The Kurier system was an experimental burst transmission system that was introduced late in 1944.  The goal of the system was to dramatically reduce transmission times required to send Kurzsignalen encoded message.  Unfortunately for the German efforts, Kurier never became operational due to deteriorating late-ware conditions. Entire standard messages were reduced to a series of four-letter codes that were then encrypted using the Naval Enigma machine. The entire message could then be transmitted in a maximum of 454 milliseconds.

Kurzsignalen involved the use of several different codebooks.  The Kurzsignalheft codebook was used for all sorts of operational messages.  The Wetterkurzschlussel was used for weather reports.  The Kurzsignalheft contained tables that converted entire sentences into four letter groups.  A large number of expressions and topics were listed including logistic matters such as refueling, rendezvous with supply ships were able to be accommodated along with tables of dates and times, etc. all reduced to four letter code groups which were then encrypted by Enigma.  Another codebook contained Kenngruppen and Spruchschlussel key identification and message keys (the starting position of the Enigma rotors).  Codebooks were printed on a special paper with red, water soluble ink to allow for easy disposal/destruction by tossing into water.

Once encoded and encrypted a Kurzsignalen message could be sent by an experienced radio operator in Morse code in about 20 seconds.  Still too long...

The Kurier system encodes Morse code dots as a 1 millisecond (ms) pulse followed by a 3 ms pause.  A Morse code dash is encoded as a 1 ms pulse, 1 ms pause, another 1 ms pulse and a 3 ms pause.

The entire signal starts as a timing signal of twenty-five 1 ms long dot signals taking 97 ms to send followed by a 20 ms pause.  After this, the encoded and enciphered message is sent.  The entire message could encode 85 pulses for a total of 337 ms.  Thus the longest message is 454 ms.



The transmission was accomplished by a rotary mechanical device attached to a transmitter.  A receiver produced an optical output that was captured by photosensitive paper.

So, with that bit of history in place, I thought I would  attempt to encode and decode Kurier signals.

More to come...

Monday, April 13, 2015

CNC control

I have had these bits and pieces laying around for quite a while now and decided to drag them out and have a play around with NEMA17 stepper motors.  Not sure what I am doing yet or going to build, but wanted to get a little experience with them.



These are small NEMA17 motors that I obtained from Adafruit that are inexpensive enough for having a play around with the following specifications:

  • 200 steps per revolution, 1.8 degrees
  • Coil #1: Red & Yellow wire pair. Coil #2 Green & Brown/Gray wire pair.
  • Bipolar stepper, requires 2 full H-bridges!
  • 4-wire, 12 inch leads
  • 42mm/1.65" square body
  • 31mm/1.22" square mounting holes, 3mm metric screws (M3)
  • 5mm diameter drive shaft, 24mm long, with a machined flat
  • 12V rated voltage (you can drive it at a lower voltage, but the torque will drop) at 350mA max current
  • 28 oz*in, 20 N*cm, 2 Kg*cm holding torque per phase
  • 35 ohms per winding
So, you are not going to build a world-class CNC milling machine from these little guys, but they are certainly sufficient for having a go at light-weight, low-precision CNC milling, 3d printing and other hobby projects.

The board is a TinyG v8 board from Synthetos.com. It uses an embedded microcontroller (Atmel ATxmega192) and 4 stepper motor drivers (TI DRV8811) on a four inch square board.  It accepts G-code from a USB port and interprets it locally on the board to plan motor movements including acceleration planning.  Constant jerk motion equations (3rd order S curves) are used for very smooth motion transitions for lines and arcs.  Step pulse generation uses phase optimized fractional step DDA running at 50 Khz with < 1 us jitter.

The boards are networkable using RS485 for motion peripherals and for networking multiple boards.  Up to 1000 stepper axes can be supported.

The TI stepper drivers handle 2.5 amps per winding so most motors up through NEMA23 and some NEMA34 motors can be handled.



All-in-all it seems to be a really nice package and an easy one for me to get some experience with G-code, stepper motors and the like.  Now to figure out what to build this into.  I like the idea of a CNC router or engraver, but am a bit put off by the expense to build what amounts to a toy.  Obviously more research is going to be needed to find components that will allow cost cutting.

Saturday, April 11, 2015

Kriegsmarine M4 U-Boat message decryption

To test my M3/M4 Enigma machine code, I have given it the challenge of decoding an actual intercepted M4 message.

The message was intercepted by the British destroyer HMS Hurricane in the North Atlantic on 25 November 1942. This was during the ten months black-out which occurred after the introduction of the four-rotor Enigma M4. During that period, the codebreakers in Bletchley Park were unable to decrypt the Kriegsmarine radio traffic, encrypted with the new Enigma M4.

The original cipher text is show below, stripped of message indicator groups that preceded the message and were repeated at the end:


NCZW VUSX PNYM INHZ XMQX 
SFWX WLKJ AHSH NMCO CCAK 
UQPM KCSM HKSE INJU SBLK 
IOSX CKUB HMLL XCSJ USRR 
DVKO HULX WCCB GVLI YXEO 
AHXR HKKF VDRE WEZL XOBA 
FGYU JQUK GRTV UKAM EURB 
VEKS UHHV OYHA BCJW MAKL 
FKLM YFVN RIZR VVRT KOFD 
ANJM OLBG FFLE OPRG TFLV 
RHOW OPBE KVWM UQFM PWPA 
RMFH AGKX IIBG

The settings for the Enigma machine are as follows:

Enigma model: Kriegsmarine M4
Reflector: B
Rotors: Beta - II - IV - I
Stecker: AT BL DF GJ HM NW OP QY RZ VX
Ring settings: A-A-A-V
Rotor start position: V-J-N-A

I modified my test code to set the machine up with these settings thusly.  I will leave it to the reader to convert this to the Arduino example in my previous post.

int _tmain(int argc, _TCHAR* argv[])
{
// Clear and cipher text
char *szCipherText = 
"NCZW VUSX PNYM INHZ XMQX "
"SFWX WLKJ AHSH NMCO CCAK "
"UQPM KCSM HKSE INJU SBLK "
"IOSX CKUB HMLL XCSJ USRR "
"DVKO HULX WCCB GVLI YXEO "
"AHXR HKKF VDRE WEZL XOBA "
"FGYU JQUK GRTV UKAM EURB "
"VEKS UHHV OYHA BCJW MAKL "
"FKLM YFVN RIZR VVRT KOFD "
"ANJM OLBG FFLE OPRG TFLV "
"RHOW OPBE KVWM UQFM PWPA "
"RMFH AGKX IIBG";

char rgbBuf1[1024];

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

e1.setType(EnigmaTypeM4)
e1.setRotors(RotorB, RotorII, RotorIV, RotorI);
e1.setRingPos(LetterA, LetterA, LetterA, LetterV);
e1.setRotorPos(LetterV, LetterJ, LetterN, LetterA);
e1.setPlug(LetterA, LetterT); 
e1.setPlug(LetterB, LetterL);
e1.setPlug(LetterD, LetterF);
e1.setPlug(LetterG, LetterJ);
e1.setPlug(LetterH, LetterM);
e1.setPlug(LetterN, LetterW);
e1.setPlug(LetterO, LetterP);
e1.setPlug(LetterQ, LetterY);
e1.setPlug(LetterR, LetterZ);
e1.setPlug(LetterV, LetterX);

e1.doCipher(szCipherText, &rgbBuf1[0], 1024);
printf("Cipher: <%s>\n", szCipherText);
printf("Clear:  <%s>\n", &rgbBuf1[0]);
return 0;
}

I modified my Enigma class to output 4 letter code groups rather than the 5 letter groups typical of the M3 if the machine type is set to EnigmaTypeM4.

// Break into 4 or 5 character words\
if (++cchOut % (type == EnigmaTypeM3 ? 5 : 4) == 0) *pchOut++ = ' ';

The program output for this cypher text is as follows:

VONV ONJL OOKS JHFF TTTE 
INSE INSD REIZ WOYY QNNS 
NEUN INHA LTXX BEIA NGRI 
FFUN TERW ASSE RGED RUEC 
KTYW ABOS XLET ZTER GEGN 
ERST ANDN ULAC HTDR EINU 
LUHR MARQ UANT ONJO TANE 
UNAC HTSE YHSD REIY ZWOZ 
WONU LGRA DYAC HTSM YSTO 
SSEN ACHX EKNS VIER MBFA 
ELLT YNNN NNNO OOVI ERYS 
ICHT EINS NULL

When we rearrange the output to insert spaces as appropriate, we get the following:

VON VON JLOOKSJ HFFTTT EINS EINS DREI ZWO YY QNNS NEUN   
 INHALT XX BEI ANGRIFF UNTER WASSER GEDRUECKT Y WABOS X
 LETZTER GEGNERSTAND NUL ACHT DREI NUL UHR
 MARQU ANTON JOTA NEUN ACHT SEYHS DREI Y ZWO ZWO NUL GRAD Y ACHT SM Y STOSSE NACH X  
 EKNS VIER MB FAELLT Y NNN NNN OOO VIER Y SICHT EINS NULL

Now, converting abbreviations, spelled numbers, and so forth, we get the following:

Von Looks: Funktelegramm 1132/19

 Inhalt:

 Bei Angriff unter Wasser gedrueckt, Wasserbomben.  
 Letzter Gegnerstandort 08:30 Uhr,
 Marine Quadrat AJ 9863, 220 Grad, 8 Seemeilen, stosse nach.
 14 Millibar faellt, NNO 4, Sicht 10.
Running this through Google translate, we get the following English:
From Looks: radiogram 1132/19
  content:
  When attacked underwater pressured water bombs.
  Last opponents Location 08:30 clock,
  Marine Square AJ 9863, 220 degrees, 8 nautical miles, according to stumble.
  14 millibar falls, NNO 4, view 10th

Um, yeah...  Automatic translators pretty much suck...  Let's try this version:

From Looks: Radiogram 1132/19
Contents:
Forced to submerge during attack, depth charges,
Last enemy location 08:30h,
Naval Grid AJ 9863, 220 degrees, 8 nautical miles, (I am) following (the enemy).
(Barometer) 1014  Millibar (tendency) falling, North North East 4, visibility 10.

You can read all about this message and its history at this great page.  Have fun! 

Enigma Cipher on Arduino

As a brief follow-up on my previous posting I am posting here a Arduino port of my Enigma cipher engine.  The changes were trivial to deal with the proper include files and to use the Serial class to output the test program results.  But as promised, I am providing the engine class files (enigma.h and enigma.cpp) as well as a test sketch (enigmaTest.ino) that can be copy/pasted and run on the Arduino.

I have chosen to use my new Freetronics Due board, kindly supplied by the good folks down-under at Freetronics for testing.

You are free to use what I post here as you desire, regardless of any copyright notices you may find in my code.  If I posted it in my blog, you are free to use it in any way desired.

Enjoy and don't hesitate to ask if you have any questions or problems.

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
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);

private:     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

};

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

#include <string.h>
#include "enigma.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';
    }

}

enigmaTest.ino:
// Enigma M3/M4 test code
//

#include "enigma.h"

// 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 to easily reset to default state 
Enigma e1;      // Encode instance of engine
Enigma e2;      // Decode instance of engine

void setup()
{
  Serial.begin(115200);

  e1.setRotors(RotorNone, RotorI, RotorIV, RotorV);
  e2.setRotors(RotorNone, RotorI, RotorIV, RotorV);

  e1.setRingPos(LetterA, LetterT, LetterF, LetterS);
  e2.setRingPos(LetterA, LetterT, LetterF, LetterS);

  e1.setPlug(LetterA, LetterT); 
  e1.setPlug(LetterB, LetterJ);
  e1.setPlug(LetterD, LetterL);
  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);

  e1.doCipher(szClearText, &rgbBuf1[0], 512);
  Serial.print("Clear:  <");
  Serial.print(szClearText);
  Serial.println(">");
  Serial.print("Cipher: <");
  Serial.print(&rgbBuf1[0]);
  Serial.println(">");  
  
  e2.doCipher(&rgbBuf1[0], &rgbBuf2[0], 512);
  Serial.print("Cipher: <");
  Serial.print(&rgbBuf1[0]);
  Serial.println(">");
  Serial.print("Clear:  <");
  Serial.print(&rgbBuf2[0]);
  Serial.println(">"); 
}

void loop()
{
   // Nothing to do

}

Here is the output from this sketch on the serial monitor:
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>

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.