HISTORY OF CRYPTOGRAPHY

A Brief History of Cryptography & Cryptanalysis

Early Cryptographic Systems

It seems reasonable to assume that people have tried to conceal information in written form since writing was developed and examples survive in stone inscriptions and papyruses showing that many ancient civilisations including the Egyptians, Hebrews and Assyrians all developed cryptographic systems. The first recorded use of cryptography for correspondence was by the Spartans who (as early as 400 BC) employed a cipher device called a "scytale" to send secret communications between military commanders. The scytale consisted of a tapered baton around which was wrapped a piece of parchment inscribed with the message. Once unwrapped the parchment appeared to contain an incomprehensible set of letters, however when wrapped around another baton of identical size the original text appears.

The Greeks were therefore the inventors of the first transposition cipher and in the fourth century BC the earliest treatise on the subject was written by a Greek, Aeneas Tacticus, as part of a work entitled On the Defence of Fortifications. Another Greek, Polybius later devised a means of encoding letters into pairs of symbols using a device known as the Polybius checkerboard which contains many elements common to later encryption systems. In addition to the Greeks there are similar examples of primitive substitution or transposition ciphers in use by other civilisations including the Romans.

The Polybius checkerboard consists of a five by five grid containing all the letters of the alphabet. Each letter is converted into two numbers, the first is the row in which the letter can be found and the second is the column. Hence the letter A becomes 11, the letter B 12 and so forth.

The Arabs were the first people to clearly understand the principles of cryptography and to elucidate the beginning of cryptanalysis. They devised and used both substitution and transposition ciphers and discovered the use of letter frequency distributions in cryptanalysis. As a result of this by approximately 1412 al-Kalka-shandi could include in his encyclopaedia Subh al-a’sha a respectable if elementary treatment of several cryptographic systems. He also gave explicit instructions on how to cryptanalyze ciphertext using letter frequency counts including examples illustrating the technique.

European cryptography dates from the Middle Ages during which it was developed by the Papal and Italian city states. The earliest ciphers involved only vowel substitution (leaving the consonants unchanged). Circa 1379 the first European manual on cryptography, consisting of a compilation of ciphers, was produced by Gabriele de Lavinde of Parma, who served Pope Clement VII. This manual contains a set of keys for correspondents and uses symbols for letters and nulls with several two character code equivalents for words and names. The first brief code vocabularies, called nomenclators, were expanded gradually and for several centuries were the mainstay of diplomatic communications for nearly all European governments. In 1470 Leon Battista Alberti described the first cipher disk in Trattati in cifra and the Traicté de chiffres, published in 1586 by Blaise de Vigernère contained a square table commonly attributed to him as well as descriptions of the first plaintext and ciphertext autokey systems.

By 1860 large codes were in common use for diplomatic communications and cipher systems had become a rarity for this application however cipher systems prevailed for military communications (except for high-command communications because of the difficulty of protecting codebooks from capture or compromise). During the US Civil War the Federal Army extensively used transposition ciphers. The Confederate Army primarily used the Vigenère cipher and on occasional monoalphabetic substitution. While the Union cryptanalysts solved most of the intercepted Confederate ciphers, the Confederacy in desperation, sometimes published Union ciphers in newspapers, appealing for help from readers in cryptanalysing them.

Cryptography During The Two World Wars

During the first world war both sides employed cipher systems almost exclusively for tactical communications while code systems were still used mainly for high-command and diplomatic communications. Although field cipher systems such as the U.S. Signal Corps cipher disk lacked sophistication some complicated cipher systems were used for high-level communications by the end of the war. The most famous of these was the German ADFGVX fractionation cipher.

In the 1920s the maturing of mechanical and electromechanical technology came together with the needs of telegraphy and radio to bring about a revolution in cryptodevices - the development of rotor cipher machines. The concept of the rotor had been anticipated in the older mechanical cipher disks however it was an American, Edward Hebern, who recognised that by hardwiring a monoalphabetic substitution in the connections from the contacts on one side of an electrical rotor to those on the other side and cascading a collection of such rotors, polyalphabetic substitutions of almost any complexity could be produced. From 1921 and continuing through the next decade, Hebern constructed a series of steadily improving rotor machines that were evaluated by the U.S. Navy. It was undoubtedly this work which led to the United States’ superior position in cryptology during the second world war. At almost the same time as Hebern was inventing the rotor cipher machine in the United States, European engineers such as Hugo Koch (Netherlands) and Arthur Scherbius (Germany) independently discovered the rotor concept and designed the precursors to the most famous cipher machine in history - the German Enigma machine which was used during World War 2. These machines were also the stimulus for the TYPEX, the cipher machine employed by the British during World War 2.

The United States introduced the M-134-C (SIGABA) cipher machine during World War 2. The Japanese cipher machines of World War 2 have an interesting history linking them to both the Hebern and the Enigma machines. After Herbert Yardley, an American cryptographer who organised and directed the U.S. government’s first formal code-breaking efforts during and after the first world war, published The American Black Chamber in which he outlined details of the American successes in cryptanalysing the Japanese ciphers, the Japanese government set out to develop the best cryptomachines possible. With this in mind, it purchased the rotor machines of Hebern and the commercial Enigmas, as well as several other contemporary machines, for study. In 1930 the Japanese’s first rotor machine, code named RED by U.S. cryptanalysts, was put into service by the Japanese Foreign Office. However, drawing on experience gained from cryptanalysing the ciphers produced by the Hebern rotor machines the U.S. Army Signal Intelligence Service team of cryptanalysts succeeded in cryptanalysing the RED ciphers. In 1939 the Japanese introduced a new cipher machine, code-named PURPLE by U.S. cryptanalysts, in which the rotors were replaced by telephone stepping switches.

The greatest triumphs of cryptanalysis occurred during the second world war - the Polish and British cracking of the Enigma ciphers and the American cryptanalysis of the Japanese RED, ORANGE and PURPLE ciphers. These developments played a major role in the Allies’ conduct of World War 2.

Cryptography In The Modern Age

After World War 2 the electronics that had been developed in support of radar were adapted to cryptomachines. The first electrical cryptomachines were little more than rotor machines where the rotors had been replaced by electronic substitutions. The only advantage of these electronic rotor machines was their speed of operation and they inherited the inherent weaknesses of the mechanical rotor machines.

There is little information available regarding the secret cipher machines of the 1960s and it is likely that this subject will remain the shrouded in rumour until the relevant information is de-classified.

The era of computers and electronics has meant an unprecedented freedom for cipher designers to use elaborate designs which would be far too prone to error if handled by pencil and paper, or far to expensive to implement in the form of an electromechanical cipher machine. The main thrust of development has been in the development of block ciphers, beginning with the LUCIFER project at IBM, a direct ancestor of DES (Data Encryption Standard).