| Table of contents |
|
2 Mechanization 3 History |
Most practical encrypherment has long been based on the substitution of one or more letters from the original message, known as the plaintext, to one or more letters in the encoded version, the cyphertext. The library of such substitutions is known as the substitution alphabet. Early systems used very simple systems for such substitutions, typically replacing any instance of a particular letter, say A, with another, say X. There are other possible cyphers, as for instance transposition cyphers.
By about 1000 CE the increasing sophistication of mathematics during the Golden Age of Islam led to the development of the frequency counting technique, which looked for patterns in the cyphertext that invariably results from the characteristic relative frequency of letters in various languages. For instance, in the English language the letter E is most common, so if a particular message contained a number of D's in it, it was likely that D was being used to replace E. And so on with less frequent plaintext letters. As familiarity with the technique spread, European cryptographers became adept at recovering the original message with relative ease.
New systems of substitution encrypherment were soon developed to hide these plaintext patterns by using a different letter substitution. In this way there would be no (or less) high-frequency occurrences of letters corresponding to E for instance. These methods generally used an algorithm that had the user construct a number of different substitution alphabets, and then select which one to use for every letter to be encoded. Most used a limited number of these substitution alphabets and if the rotation could be detected, each could be cryptanalyzed by treating the cryphertext as a combination of many monoalphabetic substitution cyphers.
Although these methods were far more secure, they had problems of their own. Since the encryption was based on some sort of algorithm, if the details of that algorithm could be discovered, decrypting the message would be easy. Most systems thus used a shared secret key, a string of letters used to 'customize' the algorithm. As it turns out, the very existence of a key creates a pattern that can be used to attack it.
The solution to this problem is to use a key of infinite length – although in practice a key that is longer than the message will do. Of course transmitting such a key would be troublesome, and easy to intercept. But perhaps the key could be generated by an algorithm? One that itself was based on some small key? Such a concept seemed foolish, since, if one can attack the "complex" algorithm's key today, why can't one attack the simple algorithm and recover the key?
Furthermore any such system is very tedious to use in practice, with even short messages taking hours to encode and decode. Adding another layer to the system would simply make this worse.
In the early part of the 20th century a solution to the problem was found. Both the problem of providing a complex algorithm and the task of encoding and decoding it could be solved mechanically.
Imagine an electrical system with 26 switches attached to 26 light bulbs. When you turn on any one of the switches, the corresponding light bulb lights up. Now replace the switches with the keys on a typewriter attached to those switches, and label the bulbs with letters. Typing the letter "A" makes the bulb labeled "A" light up, and typing a message makes the bulbs light up in turn as the keys are pressed.
To turn this system into an encryption system, all one has to do is change the wiring. Instead of the typewriter key for "A" running to the bulb labeled "A", run it to X for instance. Now typing in a message encrypts it, with zero effort on the operator's part.
The system just described is identical to the original single-alphabet substitution system, and just as insecure. The new idea in these machines was to place this scrambled wiring on the rotor, and then rotate it with a gear every time a letter was pressed. So while pressing "A" the first time would generate an "X", the next time it would generate a "J". Every letter pressed on the keyboard would spin the rotor and get a new substitution.
In effect, the rotors are generating a key from a simple algorithm, "use the next alphabet with every key press". Most of the key is hidden in the wiring of the disk. All that is needed to communicate the key between two parties is to say where to set the rotor before pressing the first key. A single letter (or number) now generates a huge key mechanically – the problem is solved.
Well almost. Depending on the size of the rotor, this may or may not be more secure than hand cyphers. If the rotor has only 26 positions on it, one for each letter, then all messages will have a (repeating) key 26 letters long. Although the key itself (mostly hidden in the wiring of the rotor) might not be known the systems for attacking these types of codes don't need that information. So while such a single rotor machine is certainly easy to use, it's less secure than most other polyalphabetic systems.
But this too is easy to correct. Simply stack more rotors next to each other, and gear them together. After the first rotor spins "all the way", make the rotor beside it spin one position. Now you would have to type 26 x 26 = 676 letters (for English) before the key repeats, and yet it still only requires you to communicate a key of two letters to set things up. A key of 676 length isn't enough? Add another rotor, now you have a key 17,576 letters long. And so forth.
In order to be as easy to decipher as encypher, rotor machines were symmetrical. This makes sense if you consider how they work, if the current is sent from the battery (eventually) to the lamp, putting the current back in at the lamp end would reverse the circuit. Of course one cannot cause a typewriter key to "light up" (at least until recently), and in practice the rotors had to be reversed instead, thereby reversing the scrambling. Note that modern cryptography uses 'symmetrical' to mean that both cypher users must use the same key, not that the encyphering algorithm is run backwards to decrypt.
The concept outlined above occurred to no less than four different inventors at almost exactly the same time.
In the United States Edward Hugh Hebern built the first rotor machine using a single rotor in 1917. He became convinced he would get rich selling such a system to the military, the Hebern Rotor Machine, and produced a series of different machines with one to five rotors. Instead of becoming rich he instead went bankrupt in the 1920s, although he sold a small number of machines to the US Navy in 1931.
In Hebern's machines the rotors could be opened up and the wiring changed in a few minutes, so a single mass-produced system could be sold to a number of users who would then produce their own keying. Decryption consisted of taking out the rotor(s) and turning them around to reverse the circuitry. Unknown to Herbern, William F. Friedman of the US Army's SIS promptly demonstrated a flaw in the system that allowed the cyphers from it, and from any machine with a few similar design features, to be cracked with enough work.
Another inventor was a Dutchman, Hugo Koch, who also filed a patent in 1919.
IN Sweden, A van Damm invented and patented still another rotor design about the same time.
The rotor machine was made famous by Arthur Scherbius, who built his first Enigma (Greek for riddle) machine in 1918. Enigma machines used three rotors, but added a unique feature, the reflector. At the end of the stack of three rotors was an additional rotor-like disk, this one wired such that the inputs were wired back out to some other contact on the same side – like half of a normal rotor. When current was sent into most of these machines it would travel through the rotors and out the other side to the lamps, but in the Enigma it was "reflected" back through the disks before going to the lamps. The advantage to this system was that there was nothing that had to be done to the setup in order to decrypt a message, the machine was symetrical at all times.
Scherbius joined forces with a mechanical engineer and formed Chiffriermaschinen AG in Berlin before demonstrating Enigma to the public in Bern in 1923, and then in 1924 at the World Postal Congress in Stockholm. In 1927 Scherbius bought Koch's patents, and in 1928 they added a plugboard, essentially a non-rotating manually-rewireable fourth rotor, on the front of the machine. After the death of Scherbius in 1929, Willi Korn was in charge of further technical development of Enigma.
As with earlier rotor machine efforts, Scherbius had limited commercial success. However in 1932 the British published a fateful historical text about World War I, in which they revealed that they had been routinely reading German messages. The Germans were determined to make sure that this didn't happen again, and the German military accelerated the experiments already underway to change to rotor machines. The German Navy had been using an Enigma variant for some years, and the German Army began to use a different variant about 1932. The Scherbius design had won the competition.
he rotor machines it, and its successor, Heimsoth & Reinke supplied to the German military and others such as assorted civilian agencies such as Nazi party organizations. They were the Enigmas which the Poles, and then the British/French, managed to break starting in the early '30s when the German Army first used Enigmas.
A software implementation of the rotor machine was used in the crypt command that was part of early UNIX operating systems. It was among the first software components to run afoul of U.S. export regulations that classified cryptographic devices as munitions.Background
Mechanization
History