My ENIGMAtic Java Ring

Using the model of an old wartime encryption machine, find out how to fashion your own secret encoder ring

1 2 3 4 Page 2
Page 2 of 4

The reflector is also significant because in one step it converts the set's substitution from an asymmetric mapping to a symmetric mapping! Thus, if you were to input the letter D by typing it on the keyboard of the machine with the rotors shown in Figure 1, the machine would output the letter F by illuminating the lamp under the letter F. Then, if you typed the letter F on the keyboard, it would illuminate the lamp under the letter D. This means you need only one arrangement of the rotors, which becomes the key, to encrypt a message. That same setting of the rotors will take an encrypted message and output the original message. Of course, the story isn't over quite yet.

With this arrangement of three rotors and a reflector, the input character would undergo seven remappings (three inbound, reflection, and then three outbound) before a lamp was illuminated. However, assuming the substitutions remained the same for every character, even if a character went through ten thousand mappings, the end result would be a simple substitution cipher. This is where the rotating part enters the picture.

As their name implies, one or more of the ENIGMA rotors rotate during the encryption process. When a rotor is rotated by one position, all of the characters in that rotor's character map are shifted by one position. I've created an example of this in Table 3 below.

Input characterABCDEFG
Before rotationBGEDFCA
After rotationABGEDFC
Table 3: The effect of rotation on the character substitution map

In the above table, the rotation has shifted the character map by one position such that the input letter C would map to the letter E before the rotation, but to the letter G after the rotation.

Each ENIGMA rotor has a notch on it that causes the next rotor in the series to move by one position whenever the notch passes by the index character.

The effect of this rotation is that after each character is encrypted, an entirely new character map is used to map the next character. This makes the ENIGMA a composite of both an algorithmic substitution cipher and a mapping substitution cipher. Each character in the output message has its own map associated with it, and because the rotors are moved with each character, the character mapping depends on not only the character value, but its position in the input message as well. This combination makes the ENIGMA cipher much stronger than a simple substitution cipher.

To make the ENIGMA cipher even stronger, the Germans issued their code clerks a total of eight separate rotors, each with its own character mapping. When a message was to be encrypted, the key consisted of the numbers the three rotors should use and the initial rotor position for the selected rotors. No amount of simple cryptanalysis would reveal the message hidden by ENIGMA. The weakness of the ENIGMA was that the rotors were fixed and limited in number. Once the allies had stolen a couple of ENIGMA machines and had a full set of rotors, cracking the code became a matter of trying different combinations of the available rotors until the correct ones were found. Nonetheless, the ENIGMA's clever design was the basis of the strongest level of encryption available for many years after the war ended.

Building an ENIGMA machine in Java

The mechanical design of the ENIGMA machine lends itself to creating an object-oriented version of it in software. The modular nature of rotors connected to each other in series suggests that a good starting point in the design would be to simulate rotors as objects and the ENIGMA machine as an object. The behavior of the rotors is described well -- so the design process will start with the design of a Rotor class.

Rotor design and implementation

Each rotor in the ENIGMA machine is an implementation, in hardware, of a translation table for 26 characters. The rotor consisted of 26 contacts representing the 26 letters, which are wired internally to 26 output contacts that represent the translated characters. Of course, with the rotor limited to 26 characters, there were some difficulties with the messages that were encrypted with the machine.

The design of the original ENIGMA required the person who was using it to decode a message to reformat the text once it was decoded back into individual words. Further, all of the characters were represented as uppercase. Of course, in my ringlet version I didn't want to have to reinsert the spaces, nor recover the original type case of the message, so I decided to "improve" things a bit and have my Rotor class contain both uppercase and lowercase characters, as well as numbers and some punctuation.

The decision to widen the character set led to another problem -- that of generality. Do I limit the character set and only get messages through that contain English, or do I use the full ISO Latin 1 character set, thus enabling encryption of a wider variety of messages? The solution to this problem appeared somewhat unexpectedly in the character set I had chosen initially for my test case. When I initially prototyped my Rotor class, I had the character set defined as follows:

     static final char char_set[] = {
    'A', 'B', 'C', 'D', 'E', 'F', 'G'. 'H', 'I', 'J', 'K', 'L', 'M',
    'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
    'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', ' ', '.', '!',
    '?', ',', '(', ')' };

Now, there isn't anything special about the code above; it's a basic character array. However, the code was nearly identical to some I had put in a class to encode mail messages.

The current Internet standard for mail messages is called MIME. The MIME protocol contains a specification for encoding messages that have non-ASCII data, which is called BASE64 encoding. The encoding protocol uses 64 characters to represent binary data. The protocol works by specifying a 6-bit pattern of binary digits to each character. Streams of 8-bit octets (bytes) are specified by using a series of characters. It sounds complicated but it really isn't.

BASE64 encoding solved the problem of how to encode arbitrarily complex data so that it could be sent through an electronic mail system with a limited number of characters. This was the same problem I wanted to solve with my ENIGMA simulator, except that in my case the limited character set was in my rotors. BASE64 encoding would give me a way to encrypt arbitrary messages with my ring. My rotors then became BASE64-based rotors.

With the character set issue decided, I began to build my Rotor class. My first pass at code to encrypt characters is shown below.

// An array to map an input character to a value between 0 and 63 static char char_map[] = {'A', 'B', 'C', 'D', 'E', ... '+', '/'};

// An array of 64 characters in the rotor map char rotor_data[] = { 'Z', 'Q', 'E', 'D', ... ')' };

char encrypt(char a) { int index; for (int i = 0; i < 64; i++) { if (char_map[i] == a) { index = i; break; } } if (next_rotor != null) return next_rotor.encrypt(rotor_data[index]); return rotor_data[index]; }

The code above raised a couple of issues. The first was that the iButton with Java is not very fast, and there was a lot of looping going on. The second issue was that the storage for the character arrays was larger than it needed to be. Instead of 64 bytes, I was using what appeared to be 128 bytes per array, with three rotors and a character map, all which added up to .75 KB just for the rotor data! That was more than 10 percent of the 6.5 KB of space available on the ring.

So I started looking for ways to tighten up the code in order to reduce time and minimize the space required. My thought was to use a String object to hold the rotor data. The advantages of a String object are that the implementation can be optimized for the platform, and there are two methods indexOf and charAt that would let me get to the individual characters and the character's position in the string. Unfortunately, I found out that the Java Card specification doesn't include String in its base class set!

The lack of a String class left me with only one option, which was to use byte arrays. So the Rotor class implements a method, indexOf, that does what String's method does.

The final implementation of the Rotor class is available in the Resources below, but let's look at a the more salient methods from the class.

The first method was an implementation of indexOf, which does what the same method in String does. It's shown below.

   
    private short indexOf(byte v[], byte b) {
        for (short i = 0; i < v.length; i++) {
            if (b == v[i]) return i;
        }
        return 0;
    }

As you can see in the code above, the method indexOf scans a byte array for a given byte. If the routine finds the matching byte, it returns the index of that byte in the passed-in array. If the byte isn't found, the routine returns 0.

Originally, I hadn't intended to return 0. I initially designed the routine to return -1, which is an invalid array index. When I went to debug the code, I found that I had a lot of problems, so I changed it to return a valid index instead.

The next routine implements the reflector mechanism in the rotor.

    
    byte reflect(byte c) {
        short xi;
        xi = indexOf(char_map, c);
        return (reflector[xi]);
    }

The first step maps the character passed in as byte c into an index between 0 and 63. This represents the character code as defined by the BASE64 character set. The next step returns the reflected character from a byte array named reflector. The next two methods implement the forward character translation and the reverse character translation functions of the rotor.

    
    byte reverse(byte c) {
        byte x;
        short xi;
        xi = indexOf(contents, c);
        return (char_map[(xi-index)&0x3f]);
    }
    byte forward(byte c) {
        short xi;
        xi = indexOf(char_map, c);
        return (contents[(xi + index) & 0x3f]);
    }

Both methods accomplish the same mapping from the input character to the BASE64 character value. The next step maps from the contents array instead of from the reflector array. The contents array contains the rotor's character mapping, which defines the encrypting table for the current rotor. Further, the method doesn't use a simple one-to-one mapping; instead it combines the resulting character code with a variable named index, which indicates how many times the rotor has been rotated. Finally, the computed character array is masked with the hex constant 0x3f. This forces the value to be between 0 and 63.

The final method of interest in the Rotor class is the rotate method. This method adjusts the index variable in the Rotor object and then, if the index value is equal to the notch value, the rotate method of the next rotor in the link list is invoked. This is shown in the code below.

   
    public void rotate() {
        if (notch == 0)
            return;
        index = (short)((index + 1) & 0x3f);
        if ((index % notch == 0) && (next != null)) {
            next.rotate();
        }
    }

The variable notch indicates when the rotor should rotate. The Rotor class contains pointers that form a linked list of rotors. When the rotate method is invoked, the variable index is incremented, and if it matches the notch value, the next rotor in the linked list also is rotated.

Finally, in the Rotor class, there are two arrays of bytes -- one named char_map and one named reflector. Originally, I had initialized them with static initializer code, as shown below.

    static byte char_map[] = {
      'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P',
      'Q','R','S','T','U','V','W','X','Y','Z','a','b','c','d','e','f',
      'g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v',
      'w','x','y','z','0','1','2','3','4','5','6','7','8','9','+','/'
    };

The above code was the single biggest headache of the whole design. While it's perfectly legal Java code, I discovered after a lot of debugging that the static initialization of the Rotor class wasn't actually running when my ring applet was loaded. That meant that attempting to access these arrays resulted in ArrayIndexOutOfBoundsException.

Of course, it took many hours of debugging to figure out this problem. What I needed to do then was to manually initialize these arrays -- a major pain. The final class has a method InitCharMap, which is full of lines like

    char_map[0] = 'A';
    char_map[1] = 'B';
    ...
    char_map[63] = '/';

It isn't very good looking but it does get the job done. With the Rotor class designed and working, I then turned to designing the main Enigma class.

Enigma design and implementation

The actual ENIGMA machine provided slots for the rotors it was using to encrypt a message. My Enigma class would contain object references for the Rotor objects in the simulated machine. Further, the Enigma class is the actual ring applet. Therefore, like the applets you would run in a browser, the Enigma class is a subclass of Applet. However, unlike a browser applet, the class is a subclass of javacard.framework.Applet.

The Java Card applets communicate with the client applications on your computer via those APDUs I discussed earlier. Further, the contents of those APDUs have to be defined by you, the programmer. Fortunately, for something like the ENIGMA machine simulator they don't have to be too complicated.

The ADPU has four bytes that are passed to your applet in the APDU header. These are labeled the Class, Instruction, Parameter1, and Parameter2 bytes. For the Enigma class I use only the Class and Instruction bytes. They have been defined as follows:

Related:
1 2 3 4 Page 2
Page 2 of 4