A Brief History of Cryptography

Cryptography, from the Greek root words kryptos and gráphō, together meaning "hidden writing", has existed almost as long as the written word. Down through the ages, the advantage in the battle between cryptologists (code makers) and cryptanalysts (code breakers) has changed hands many times. The following events are some of the most important developments in the history of cryptography.


5th century BC - Spartan generals exchanged secret messages by wrapping narrow ribbons of parchment around a cylindrical staff known as a scytale, then transcribing their messages on the papyrus. The messages could only be read when the papyrus was re-wound around a scytale of the same thickness. This was the earliest recorded use of what is today known as a transposition cipher.


2nd century BC - Greek historian Polybius developed one of the earliest recorded substitution ciphers by replacing the letters of the alphabet, arranged in a Polybius square, with numbers.


1st century BC - Roman generals used a simple shift cipher, where each letter of a plaintext message would be shifted a fixed number of letters down the alphabet to produce the ciphertext. The cipher came to be known as Caesar's cipher after Julius Caesar, who is said to have preferred a shift of three letters.


9th century - Islamic mathematician Abū Yūsuf Yaʻqūb ibn Isḥāq al-Kindī published the first text book on code breaking, A Manuscript on Deciphering Cryptographic Messages. Al-Kindī's book introduced the classification of ciphers, polyalphabetic ciphers, and frequency analysis, an important technique used in breaking substitution ciphers. Frequency analysis uses the relative frequency of symbols in a coded message to reveal what letters of the alphabet they stand for.


1553 - Italian Renaissance man Leon Battista Alberti published the first clear description of what would later come to be known as the Vigenère cipher^* in his book La cifra del. Sig. Giovan Battista Bellaso. The Vigenère cipher is a strong polyalphabetic substitution cipher consisting of several Caesar cipher's in sequence, each with a different shift value.

Enciphering was done with the aid of a table of alphabets, known as a tabula recta, Vigenère square, or Vigenère table (see the image at left), or with a cipher disk. To encode a message, a keyword was chosen and the letters in the keyword determined which rows of the Vigenère table were used to encode each letter of the message. For example, if the keyword ACE were chosen, the A row would be used to encode the first letter of the message, the C row to encode the second letter, and the E row to encode the third. The letters of the keyword would then be repeated to encode the fourth, fifth, sixth, and subsequent letters of the original message. To decode a message, the same process was done in reverse. This required sender and receiver to agree on a secret key before communications could be sent.


1863 - The resistance of the Vigenère cipher to frequency analysis earned it a reputation as an "unbreakable" cipher, but this would prove not to be the case. The cipher was shown to be vulnerable to an attack that would come to be known as Kasiski examination^**.

The weakness of the Vigenère cipher was that certain common words, such as "the" and "and", are used with such frequency that they will occasionally be encrypted as the same sequence of letters in different parts of the encrypted text. By looking for repeating sequences of letters, cryptanalysts could divine the length of the key used to encrypt a message. Once the length of the key was known, the ciphertext message could be partitioned into key-length chunks of text, which were shown to be individually susceptible to frequency analysis.


1917 - U.S. Army Major Joseph Mauborgne developed an encryption system known as a one-time pad. The idea is similar to encrypting a message using a secret key, but in the case of a one-time pad the secret key is a random sequence of numbers as long as the original message, and it is used only once. The one-time pad, if implemented correctly, is the only provably unbreakable encryption algorithm.

The chief weaknesses in implementing a one-time pad are generating a random sequence of digits of sufficient length and randomness, and distributing the keys. Both weaknesses were exploited by both sides during World War II, and during the subsequent cold war between the United States and Soviet Russia.


1926 - After World War I had ended, the German Navy adopted the use of a family of electro-mechanical encryption devices that became collectively known as the Enigma machines. The devices proved to be so effective that by World War II their use had spread to every branch of the German military.

The Enigma machines consisted of a mechanical keyboard, a set of disks attached to a rotating spindle, and a stepping mechanism to turn one or more of the disks each time a key was pressed. When a key was pressed, a set of electrical contacts in the disks would complete a circuit. The arrangement of the disks would provide the encryption for the letter selected. By rotating the disks with each key press, the Enigma generated a different encryption for each letter of a message. Rotors with different encodings could be added or exchanged on some models of the Enigma, and some featured plug-boards that allowed the operator to reconfigure the wiring of the rotors, providing even more combinations of possible ciphers.

The initial arrangement of the rotating disks and the patch cords on the plug board acted as the key to the Enigma machines. A message encoded starting from one unique initial state could only be decoded by an Enigma machine starting in the same configuration. The enormous number of possible initial states, as many as 10¹¹⁴ for some models, made the Enigma extremely difficult to crack. Although still not quite as secure as a one-time pad, the speed with which a skilled operator could encode and decode a message with the Enigma machine made it preferable for field use.


1943 - A group of Allied code breakers working in the town of Bletchley Park in the United Kingdom, built one of the first programmable digital electronic computers, code named Colossus, in an effort to break German codes. Intercepted encrypted messages could be read in by the Colossus at a high rate of speed on a paper tape. These data streams were then compared to various messages generated internally by the Colossus, which was programmed to simulate German code making machines. Any matches in these two data streams were used by Allied code breakers to decipher the intercepted messages.

The Colossus was classified as top secret by the British military, and details about its construction and operation weren't released until decades after its use. The Bletchley Park code breakers, with the aid of Colossus, are estimated to have shortened World War II by several months.


1972 - The U.S. National Bureau of Standards (NBS, known today as the National Institute of Standards and Technology, or NIST) identified the need for a government-wide data encryption standard. The NBS solicited proposals for a cipher that would meet their rigorous requirements, and after several candidate ciphers were refused, a group of cryptographers working out of IBM published what would become known simply as DES in 1975. After much public scrutiny, DES was accepted as a standard in November of 1976.

The chief criticism of DES was the allegation of tampering by the National Security Agency (NSA). DES is a block cipher, and block ciphers work by encrypting a set-length block of bits at a time according to the length of a key. The key length directly influences the level of security of the encryption. On recommendation from the NSA, the IBM researchers agreed to shorten the DES key length to 56 bits and slightly modify the encryption algorithm. The fear at the time was that IBM had allowed the NSA to weaken DES to the point that the NSA (and only the NSA) could break the cipher.

According to security expert Bruce Schneier, fears surrounding the NSA's tampering with DES were unfounded. In his 2004 article The Legacy of DES^*** Schneier wrote:

It took the academic community two decades to figure out that the NSA "tweaks" actually improved the security of DES. This means that back in the '70s, the National Security Agency was two decades ahead of the state of the art.

1976 - Whitfield Diffie and Martin Hellman published a cryptographic protocol that allowed secret key exchange over an unsecured communications channel^****. The protocol, dubbed Diffie-Hellman key exchange, relies on the mathematical properties of one-way functions, specifically in this case the discrete logarithm problem (RSA, a later key exchange algorithm, relies on integer factorization).


1989 - The first working experimental quantum cryptographic prototype was demonstrated by researchers from the U.S. and Canada. A fundamental property of quantum mechanics, known as the Heisenberg uncertainty principle, is that anything that attempts to measure a quantum system disturbs the system. This property can be used to detect eavesdroppers on a specially designed fiber-optic network. A stream of photons representing a cipher key can be sent across a fiber-optic link. If the stream is disturbed by the presence of an eavesdropper, the link can be immediately shut down before any sensitive information is exchanged. If the stream is not disturbed, then the key exchange is complete and the key can be used to encrypt data that can then be transmitted by normal means.


1998 - The Electronic Frontier Foundation demonstrated a computer custom-designed to perform a brute force attack on DES. When DES was accepted in 1976, there were no machines powerful enough to break the algorithm's 56-bit encryption key in a reasonable amount of time, at a reasonable cost to build. The EFF's machine, known as Deep Crack, demonstrated that DES encryption was no longer sufficient. Deep Crack, which cost the EFF $250,000 to build, was able to search the entire 2⁵⁶-bit DES keyspace (about 72 quadrillion possible keys) and decrypt a DES encrypted message in just 56 hours.


2001 - The Advanced Encryption Standard (AES) was announced as a replacement for DES. AES is a collection of block ciphers, each with a 128-bit block size, and with key lengths of 128, 192, and 256 bits. The increased block and key sizes make AES much more secure than its predecessor. AES is the only publicly accessible and open encryption standard approved by the NSA for top secret government use.


2008 - The world's first commercial network using quantum cryptology was demonstrated by participants from twelve European countries. The designers of the 200 km network in and around Vienna, Austria plan for it to be used for secure financial transactions and information exchange.


The future - The advantage in cryptography has shifted in favor of the code makers, but who knows for how long? Advancements in quantum computing or a major breakthrough in mathematics (in the area of quickly factoring large numbers) could provide the means to crack the best codes we use today. Who knows how long our digital communications will remain secure?


Further Reading:
In researching for this article it didn't take me long to happen upon the Wikipedia article History of cryptography. Anyone who enjoys this article will almost certainly enjoy that one as well.

Much of the material covered in this article is discussed in greater detail in Simon Singh's excellent The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography.

For information about the recent (1970's and later) history of cryptography, and the people who created it, read Steven Levy's Crypto:how the code rebels beat the government-saving privacy in the digital age.

More information regarding the European quantum cryptographic network can be found in the BBC News article 'Unbreakable' encryption unveiled.


Notes:
^* The Vigenère cipher got its name from Blaise de Vigenère, who published a stronger version of the cipher in 1586.

^** First published by Friedrich Kasiski in 1863, but independently discovered by Charles Babbage in 1846.

^*** My thanks to Tim Kington for directing me to Schneier's article on DES.

^**** Although Diffie and Hellman were the first to publish a protocol for public key exchange, it was later revealed that GCHQ, the British signals intelligence agency, had developed a similar protocol prior to 1976, but had kept it classified.