Cryptography, the use of codes and ciphers, began thousands of years ago. Until recent decades, it has been the story of what might be called classical cryptography — that is, of methods of encryption that use pen and paper, or perhaps simple mechanical aids. In the early 20th century, the invention of complex mechanical and electromechanical machines, such as the Enigma rotor machine, provided more sophisticated and efficient means of encryption; and the subsequent introduction of electronics and computing has allowed elaborate schemes of still greater complexity, most of which are entirely unsuited to pen and paper.
The development of cryptography has been paralleled by the development of cryptanalysis — the "breaking" of codes and ciphers. The discovery and application, early on, of frequency analysis to the reading of encrypted communications has, on occasion, altered the course of history. Thus the Zimmermann Telegram triggered the United States' entry into World War I; and Allies reading of Nazi Germany's ciphers shortened World War II, in some evaluations by as much as two years.
Until the 1960s, secure cryptography was largely the preserve of governments. Two events have since brought it squarely into the public domain: the creation of a public encryption standard (DES), and the invention of public-key cryptography.
Antiquity
The earliest known deliberate transformation of a text is found in non-standard hieroglyphs carved into the wall of a tomb from the Old Kingdom of Egypt circa 1900 BC. This non-standard script was formed by replacing similar looking pictograms with each other and use of the rebus principle, where pictograms that begin with a sound come to represent that sound. These are not thought to be serious attempts at secret communications, however, but rather to have been attempts at mystery, intrigue, or even amusement for literate onlookers.
Some clay tablets from Mesopotamia somewhat later are clearly meant to protect information—one dated near 1500 BC was found to encrypt a craftsman's recipe for pottery glaze, presumably commercially valuable. It was encoded by replacing cuneiform symbols with other symbols in their least common values (pronunciations). Furthermore, Hebrew scholars made use of simple monoalphabetic substitution ciphers (such as the Atbash cipher) beginning perhaps around 600 to 500 BC.
The Kama Sutra, estimated to have been composed in India between 400 BC to 300 AD, lists 64 arts recommended for a better quality of life, including a reference to Mlecchita vikalpa, "the art of understanding writing in cypher, and the writing of words in a peculiar way." This was recommended for private communication between lovers. As the Kama Sutra only contains a general reference in a list and not a description, it is unclear what precisely it referred to at the time. Later commentaries on the Kama Sutra offer detailed instructions for substitution ciphers, but these were composed between the tenth and thirteenth centuries AD. Parts of the Egyptian demotic Greek Magical Papyri were written in a cypher script.
The ancient Greeks are said to have known of ciphers. The scytale transposition cipher was used by the Spartan military, but it is not definitively known whether the scytale was for encryption, authentication, or avoiding bad omens in speech.Kelly, Thomas. "The Myth of the Skytale." Cryptologia 22.3 (1998): 244–260.Lateiner, D. "Signifying Names and Other Ominous Accidental Utterances in Classical Historiography." Greek, Roman, and Byzantine Studies 45.1 (2010): 35–57. Print. Herodotus tells us of secret messages physically concealed beneath wax on wooden tabletsHerodotus Histories 7.239 or as a tattoo on a slave's head concealed by regrown hairHerodotus, Histories 5.35, although these are not properly examples of cryptography per se as the message, once known, is directly readable; this is known as steganography. Another Greek method was developed by Polybius (now called the "Polybius Square").Polybius Histories 10.43-47 Originally a method of fire signaling over long distances, it later evolved into a method of cryptography. The Greek writer Aeneas Tacticus had also devised an early form of the pinhole cipher, and a method of cryptography where vowels were replaced by dots.Aeneas Tacticus Siege Defence XXXI The Romans were also knowledgeable about cryptography. For instance, the Caesar cipher of Julius Caesar and its variations, used for clandestine communication.Aulus Gellius Attic Nights XVII.9
Medieval cryptography
David Kahn notes in The Codebreakers that modern cryptology originated among the Arabs, the first people to systematically document cryptanalytic methods. Al-Khalil (717–786) wrote the Book of Cryptographic Messages, which contains the first use of permutations and combinations to list all possible Arabic words with and without vowels.
The invention of the frequency analysis technique for breaking monoalphabetic substitution ciphers, by Al-Kindi, an Arab mathematician, sometime around AD 800, proved to be the single most significant cryptanalytic advance until World War II. Al-Kindi wrote a book on cryptography entitled Risalah fi Istikhraj al-Mu'amma (Manuscript for the Deciphering of Cryptographic Messages), in which he described the first cryptanalytic techniques, including some for polyalphabetic ciphers, cipher classification, Arabic phonetics and syntax, and most importantly, gave the first descriptions on frequency analysis.Simon Singh, The Code Book, pp. 14–20 He also covered methods of encipherments, cryptanalysis of certain encipherments, and statistical analysis of letters and letter combinations in Arabic.Ibrahim A. Al-Kadi (April 1992), "The origins of cryptology: The Arab contributions", Cryptologia 16 (2): 97–126 An important contribution of Ibn Adlan (1187–1268) was on sample size for use of frequency analysis.
In early medieval England between the years 800–1100, substitution ciphers were frequently used by scribes as a playful and clever way to encipher notes, solutions to riddles, and colophons. The ciphers tend to be fairly straightforward, but sometimes they deviate from an ordinary pattern, adding to their complexity, and possibly also to their sophistication. This period saw vital and significant cryptographic experimentation in the West.
Ahmad al-Qalqashandi (AD 1355–1418) wrote the Subh al-a 'sha, a 14-volume encyclopedia which included a section on cryptology. This information was attributed to Ibn al-Durayhim who lived from AD 1312 to 1361, but whose writings on cryptography have been lost. The list of ciphers in this work included both substitution and transposition, and for the first time, a polyalphabetic cipher with multiple substitutions for each plaintext letter (later called homophonic substitution). Also traced to Ibn al-Durayhim is an exposition on and a worked example of cryptanalysis, including the use of tables of letter frequencies and sets of letters which cannot occur together in one word.
The earliest example of the homophonic substitution cipher is the one used by Duke of Mantua in the early 1400s.David Salamon Coding for Data and Computer Communications. Springer, 2006.Meister, A. (1902). Die anfänge der modern diplomatischen geheimschrift. Beiträge zur geschichte der italienischen kryptographie des xv jahrhunderts; / von dr. Aloys Meister. F. Schöning. Homophonic cipher replaces each letter with multiple symbols depending on the letter frequency. The cipher is ahead of the time because it combines monoalphabetic and polyalphabetic features.
Essentially all ciphers remained vulnerable to the cryptanalytic technique of frequency analysis until the development of the polyalphabetic cipher, and many remained so thereafter. The polyalphabetic cipher was most clearly explained by Leon Battista Alberti around AD 1467, for which he was called the "father of Western cryptology". Johannes Trithemius, in his work Poligraphia, invented the tabula recta, now known as the Trithemius cipher, a critical component of the Vigenère cipher. He also invented the ave Maria cipher, along with other similar polyalphabetic ciphers. Trithemius also wrote the Steganographia. Giovan Battista Bellaso in 1553 first described the cipher that would become known in the 19th century as the Vigenère cipher, misattributed to Blaise de Vigenère. In Europe, cryptography became (secretly) more important as a consequence of political competition and religious revolution. For instance, in Europe during and after the Renaissance, citizens of the various Italian states—the Papal States and the Roman Catholic Church included—were responsible for rapid proliferation of cryptographic techniques, few of which reflect understanding (or even knowledge) of Alberti's polyalphabetic advance. "Advanced ciphers", even after Alberti, were not as advanced as their inventors/developers/users claimed (and probably even they themselves believed). They were frequently broken. This over-optimism may be inherent in cryptography, for it was then – and remains today – difficult in principle to know how vulnerable one's own system is. In the absence of knowledge, guesses and hopes are predictably common.
Cryptography, cryptanalysis, and secret-agent/courier betrayal featured in the Babington Plot during the reign of Queen Elizabeth I which led to the execution of Mary, Queen of Scots. Robert Hooke suggested in the chapter Of Dr. Dee's Book of Spirits, that John Dee made use of Trithemian steganography, to conceal his communication with Queen Elizabeth I.
The chief cryptographer of King Louis XIV of France was Antoine Rossignol; he and his family created what is known as the Great Cipher because it remained unsolved from its initial use until 1890, when French military cryptanalyst, Étienne Bazeries solved it. An encrypted message from the time of the Man in the Iron Mask (decrypted just prior to 1900 by Étienne Bazeries) has shed some, regrettably non-definitive, light on the identity of that real, if legendary and unfortunate, prisoner.
Outside of Europe, after the Mongols brought about the end of the Islamic Golden Age, cryptography remained comparatively undeveloped. Cryptography in Japan seems not to have been used until about 1510, and advanced techniques were not known until after the opening of the country to the West beginning in the 1860s.
Cryptography from 1800 to World War I
Although cryptography has a long and complex history, it wasn't until the 19th century that it developed anything more than ad hoc approaches to either encryption or cryptanalysis (the science of finding weaknesses in crypto systems). Examples of the latter include Charles Babbage's Crimean War era work on mathematical cryptanalysis of polyalphabetic ciphers, redeveloped and published somewhat later by the Prussian Friedrich Kasiski. Understanding of cryptography at this time typically consisted of hard-won rules of thumb; see, for example, Auguste Kerckhoffs' cryptographic writings in the latter 19th century. Edgar Allan Poe used systematic methods to solve ciphers in the 1840s. In particular he placed a notice of his abilities in the Philadelphia paper Alexander's Weekly (Express) Messenger, inviting submissions of ciphers, most of which he proceeded to solve. His success created a public stir for some months.Silverman, Kenneth. Edgar A. Poe: Mournful and Never-ending Remembrance. New York: Harper Perennial, 1991. p. 152-3 He later wrote an essay on methods of cryptography which proved useful as an introduction for novice British cryptanalysts attempting to break German codes and ciphers during World War I, and a famous story, The Gold-Bug, in which cryptanalysis was a prominent element.