Enigma Machine

Enigma Machine
German Enigma Machine

Monday, February 22, 2010

The German Enigma Machine

With the advent of mechanical technologies, ciphers became more sophisticated. Up until now, we have discussed simple character substitution and permutation ciphers. All of these could be encrypted and decrypted with paper and pencil. During World War II, a number of encryption machines were developed that allowed more sophisticated encryption systems that were far more difficult to break.
One of these is the Enigma machine developed and used by the German military. The machine’s design was brilliant for its time. It provided the ability to set one of 17,576 keys based on the positioning of 3 ‘rotors’.


The machine was composed of a keyboard with 26 keys, a lamp-board with 26 lamps (1 for each letter), a plugboard, and 3 rotors selected from a larger group of rotors.


The rotors mapped a character of the alphabet to a different character. The mappings were different for each rotor and they were not simple alphabet shifts. The Germans developed 5 standard rotors each with its own mapping. There were 3 additional rotors used by the Navy. At any one time, the machine was loaded with 3 of the rotors. The rotors were set to an initial position picked at random. The entire process is described below.


For each character type, an electrical signal passed through the plug-board. Next, the signal would pass through each of the 3 rotors performing 3 separate mappings. It would then be sent back by a ‘reflector’ into the 3rd rotor, 2nd rotor and 1st rotor in the opposite direction. This made a total of 6 separate mappings before illuminating one of the lamps. After each character, the far right rotor would rotate 1 position. Every 26th character, this rotor would force the 2nd rotor to click forward 1 position. This imitates an automobile’s odometer. Thus, the mappings would change for each character typed. Typing a series of the same character ‘AAAA…’ would result in a string of different characters for each input (i.e. ‘CZTBA…’).


Using the set of 5 standard rotors, there were 60 ways to configure a set of 3 out of the 5 rotors in the machine. Using the set of 8 rotores, there were 336 ways to configure 3 rotors. As mentioned above, there are 17,576 positions in which these rotors can be started (26 * 26 * 26). As described above, given the movement of the rotors (like a car odometer), the number of characters that could be encoded before the same ‘mapping’ occurred is 16,900 (26 * 26 * 25) giving the machine a ‘period’ of almost 17,000. Most messages were kept to several hundred characters so there was no chance of a mapping being repeated.


Machine setup involved running several lines (10-13 total) on the plug-board which mapped one letter to a different letter. This plugboard was similar to the old telephone operator’s board. Three rotors were selected from the set and positioned according to a random ‘indicator setting’ (i.e. 3-17-5 or CQE). The operator would also select 3 rotor positions to encode the message (i.e. 20-2-19 or TBS). The operator set the rotors to the indicator setting and encoded two copies of the message setting (TBSTBS). Next, the operator would reset the rotors to the message setting (TBS) and encode the message. The transmission would then include a preamble that contained the senders id, a time of transmission, and the clear text indicator setting (CQE). Following this was the 6 encoded characters representing the message indicator encrypted twice. Finally, the encoded message would be transmitted.


This has been a very quick description of a fairly complex machine. There are many more details and there was more than one version of the machine developed. Follow on enigma machines had 4 and 5 rotors adding to the number of keys and a longer period. There are some excellent resources on the web describing this machine.


Here are a few urls:



Nova online : How the Enigma Works

The Enigma Cipher Machine


And of course, the ‘Paper Enigma machine’

This last resource has a PDF that allows you to cut three ‘strips’ that imitate the rotors and place them in a paper framework. The result is a paper ‘enigma simulation’.

Tuesday, February 16, 2010

Attacking Polyalphabetic Ciphers

Some time ago, I promised an article discussing the cryptanalysis of polyalphabetic ciphers like playfair. This post will talk a little bit about these methods.


Although the approcah to the analysis of polyalphabetic ciphers is similar to that of monoalphabetic ciphers, because of their nature, these ciphers are harder to crack. The main reasons for this are:



  1. There is no longer a 1 to 1 mapping of characters.

  2. Most of these ciphers involve a 'period' where the mapping of characters are 1 to 1 (i.e. every 5th character has the same map)


Looking at ciphers which use multiple character mappings (i.e. Vignere ciphers), a keyword is selected and the amount a character is shifted in the alphabet is dictated by successive letters in the keyword. Thus, with a short key like 'CAB', 3 alphabets are used and every third character is shifted by the same amount. It is pretty easy to see that a longer key would make the cipher text harder to analyze.


For instance, 'PROTECT' has a 7 character period (even though there is a duplicated character 'T'). In order to decrypt a message, the first thing that has to happen is that the period must be determined. This can be done by counting character occurances and matching frequencies with the suspected source language's character frequencies (i.e. English). However, we now have to do several sets of counting.


Start by selecting every other character and doing a monoalphabetic character frequency attack on just those letters. If the percentages of each character closely match the frequency of english characters (you get to define what is meant by 'closely matches'), then the 'period' of the key is likely 2. However, to be sure, you are going to want to try periods from 2 through at least 7 or 8 so continue the same process using every 3rd character, then every 4th character and so on. Once you have done this, look for the set that matches english character frequencies the closest. That is likely the 'period' of the key.


Now that you know the 'period', you partition the characters into groups. Suppose you determine the period of the key is 4 (the keyword is 4 characters long). The 1st group is every 4th character starting with the 1st character in the message (you already have the frequencies for this set). The second group is every 4th character starting with character 2. Repeat this starting at character 3 and then starting at character 4.


Now for each set, sort the letters by frequency and try substituting the most frequent letter in the english language ('e') for the letter in each set (from the ciphertext) that is its most frequent character. Repeat this with the second most frequent letter of each set. If you guessed correctly at the 'period', the plaintext was english, and the plaintext was not designed to avoid such frequency analysis, then you should be seeing patterns of characters that look like english.


From these results, you can determine what the 'shift' is for each of the 4 alphabets used and recover the 'key' that was used to encrypt the plaintext.
Playfair is a bit different. It doesn't really have a period but also does not have a 1 to 1 mapping of characters. Playfair maps pairs of characters to other pairs of characters which become the 'ciphertext'. Thus, analysis must be done on pairs of characters at a time. These pairs are called digraphs.


Digraph anaylsis can be done similar to character frequency analysis. However, you will need more ciphertext to reliably match digraphs to their plaintext equivalents. Similar to the concept of character frequencies, each language has sets of digraphs that occur more frequently than others.
Here is a resource that lists english character, digraph, and trigraph frequencies:
English Character Frequencies


There are about 600 digraphs in the english language but this page shows the most common 26. It should be obvious that playfair, like vignere, will take more ciphertext to get sufficient frequency counts of digraphs to make an attempt at decoding a message.