A SHORT HISTORY OF CRYPTO

Complied by Clement Dupuis, April 1999
DATE
CIVILIAN  or GOVERNMENT
SOURCE
COMMENTS
about 1900 BC Civ Kahn p.71 An Egyptian scribe used non-standard hieroglyphs in an inscription. Kahn lists this as the first documented example of written cryptography. 
1500 BC Civ Kahn p.75 A Mesopotamian tablet contains an enciphered formula for the making of glazes for pottery. 
500-600 BC Civ Kahn p.77 Hebrew scribes writing down the book of Jeremiah used a reversed-alphabet simple substitution cipher known as ATBASH. (Jeremiah started dictating to Baruch in 605 BC but the chapters containing these bits of cipher are attributed to a source labeled ``C'' (believed not to be Baruch) which could be an editor writing after the Babylonian exile in 587 BC, someone contemporaneous with Baruch or even Jeremiah himself.) ATBASH was one of a few Hebrew ciphers of the time. 
487 BC Govt Kahn p.82 The Greeks used a device called the "skytale'' -- a staff around which a long, thin strip of leather was wrapped and written on. The leather was taken off and worn as a belt. Presumably, the recipient would have a matching staff and the encrypting staff would be left home. 

[Note: An article in Cryptologia late in 1998 makes the case that the cryptographic use of the skytale may be a myth.]

50-60 BC Govt Kahn p.83 Julius Caesar (100-44 BC) used a simple substitution with the normal alphabet (just shifting the letters a fixed amount) in government communciations. This cipher was less strong than ATBASH, by a small amount, but in a day when few people read in the first place, it was good enough. He also used tansliteration of Latin into Greek letters and a number of other simple ciphers. 
0-400? Civ Burton The Kama Sutra of Vatsayana lists cryptography as the 44th and 45th of 64 arts (yogas) men and women should know and practice. The date of this work is unclear but is believed to be between the first and fourth centuries, AD. [Another expert, John W. Spellman, will commit only to the range between the 4th century BC and the 5th century AD.] Vatsayana says that his Kama Sutra is a compilation of much earlier works, making the dating of the cryptography references even more uncertain. 

Part I, Chapter III lists the 64 arts and opens with: ``Man should study the Kama Sutra and the arts and sciences subordinate thereto [....] Even young maids should study this Kama Sutra, along with its arts and sciences, before marriage, and after it they should continue to do so with the consent of their husbands.'' These arts are clearly not the province of a government or even of academics, but rather are practices of laymen. 

In this list of arts, the 44th and 45th read: 

  • The art of understanding writing in cipher, and the writing of words in a peculiar way. 
  • The art of speaking by changing the forms of words. It is of various kinds. Some speak by changing the beginning and end of words, others by adding unnecessary letters between every syllable of a word, and so on.
200's Civ Kahn p.91 ``The so-called Leiden papyrus [...] employs cipher to conceal the crucial portions of important [magic] recipes''. 
725-790? Govt/(civ) Kahn p.97 Abu `Abd al-Rahman al-Khalil ibn Ahmad ibn `Amr ibn Tammam al Farahidi al-Zadi al Yahmadi wrote a (now lost) book on cryptography, inspired by his solution of a cryptogram in Greek for the Byzantine emperor. His solution was based on known (correctly guessed) plaintext at the message start -- a standard cryptanalytic method, used even in WW-II against Enigma messages. 
855 Civ Kahn p.93 Abu Bakr Ahmad ben `Ali ben Wahshiyya an-Nabati published several cipher alphabets which were traditionally used for magic. 
--- Govt Kahn p.94 ``A few documents with ciphertext survive from the Ghaznavid government of conquered Persia, and one chronicler reports that high officials were supplied with a personal cipher before setting out for new posts. But the general lack of continuity of Islamic states and the consequent failure to develop a permanent civil service and to set up permanent embassies in other countries militated against cryptography's more widespread use.'' 
1226 Govt Kahn p.106 ``As early as 1226, a faint political cryptography appeared in the archives of Venice, where dots or crosses replaced the vowels in a few scattered words.'' 
about 1250 Civ Kahn p.90 Roger Bacon not only described several ciphers but wrote: ``A man is crazy who writes a secret in any other way than one which will conceal it from the vulgar.'' 
1379 Govt/civ Kahn p.107  Gabrieli di Lavinde at the request of Clement VII, compiled a combination substitution alphabet and small code -- the first example of the nomenclator Kahn has found. This class of code/cipher was to remain in general use among diplomats and some civilians for the next 450 years, in spite of the fact that there were stronger ciphers being invented in the meantime, possibly because of its relative convenience. 
1300's Govt Kahn p.94 Abd al-Rahman Ibn Khaldun wrote "The Muqaddimah", a substantial survey of history which cites the use of ``names of perfumes, fruits, birds, or flowers to indicate the letters, or [...] of forms different from the accepted forms of the letters'' as a cipher among tax and army bureaus. He also includes a reference to cryptanalysis, noting ``Well-known writings on the subject are in the possession of the people.'' [p.97]
1392 Civ Price p.182-7 "The Equatorie of the Planetis", possibly written by Geoffrey Chaucer, contains passages in cipher. The cipher is a simple substitution with a cipher alphabet consisting of letters, digits and symbols. 
1412 Civ Kahn p.95-6 Shihab al-Din abu `l-`Abbas Ahmad ben `Ali ben Ahmad `Abd Allah al-Qalqashandi wrote "Subh al-a `sha", a 14-volume Arabic encyclopedia which included a section on cryptology. This information was attributed to Taj ad-Din `Ali ibn ad-Duraihim ben Muhammad ath-Tha`alibi al-Mausili who lived from 1312 to 1361 but whose writings on cryptology have been lost. The list of ciphers in this work included both substitution and transposition and, for the first time, a cipher with multiple substitutions for each plaintext letter. Also traced to Ibn al-Duraihim is an exposition on and worked example of cryptanalysis, including the use of tables of letter frequencies and sets of letters which can not occur together in one word. 
1466-7 Civ Kahn p.127 Leon Battista Alberti (a friend of Leonardo Dato, a potifical secretary who might have instructed Alberti in the state of the art in cryptology) invented and published the first polyalphabetic cipher, designing a cipher disk (known to us as the Captain Midnight Decoder Badge) to simplify the process. This class of cipher was apparently not broken until the 1800's. Alberti also wrote extensively on the state of the art in ciphers, besides his own invention. Alberti also used his disk for enciphered code. These systems were much stronger than the nomenclator in use by the diplomats of the day and for centuries to come. 
1473-1490 Civ Kahn p.91 ``A manuscript [...] by Arnaldus de Bruxella uses five lines of cipher to conceal the crucial part of the operation of making a philosopher's stone.'' 
1518 Civ Kahn p.130-6 Johannes Trithemius wrote the first printed book on cryptology. He invented a steganographic cipher in which each letter was represented as a word taken from a succession of columns. The resulting series of words would be a legitimate prayer. He also described polyalphabetic ciphers in the now-standard form of rectangular substitution tables. He introduced the notion of changing alphabets with each letter. 
1553 Civ Kahn p.137 Giovan Batista Belaso introduced the notion of using a passphrase as the key for a repeated polyalphabetic cipher. (This is the standard polyalphabetic cipher operation mis-named ``Vigenère'' by most writers to this day.) 
1563 Civ Kahn p.138 Giovanni Battista Porta wrote a text on ciphers, introducing the digraphic cipher. He classified ciphers as transposition, substitution and symbol substitution (use of a strange alphabet). He suggested use of synonyms and misspellings to confuse the cryptanalyst. He apparently introduced the notion of a mixed alphabet in a polyalphabetic tableau. 
1564 Civ Kahn p.144(footnote) Bellaso published an autokey cipher improving on the work of Cardano who appears to have invented the idea. 
1623 Civ Bacon Sir Francis Bacon described a cipher which now bears his name -- a biliteral cipher, known today as a 5-bit binary encoding. He advanced it as a steganographic device -- by using variation in type face to carry each bit of the encoding. [See Bacon's writings on-line.] 
1585 Civ Kahn p.146 Blaise de Vigenère wrote a book on ciphers, including the first authentic plaintext and ciphertext autokey systems (in which previous plaintext or ciphertext letters are used for the current letter's key). [Kahn p.147: both of these were forgotten and re-invented late in the 19th century.] [The autokey idea survives today in the DES CBC and CFB modes.]
1790's civ/govt Kahn p.192, Cryptologia v.5 No.4 pp.193-208 Thomas Jefferson, possibly aided by Dr. Robert Patterson (a mathematician at U. Penn.), invented his wheel cipher. This was re-invented in several forms later and used in WW-II by the US Navy as the Strip Cipher, M-138-A
1817 Govt Kahn p.195 Colonel Decius Wadsworth produced a geared cipher disk with a different number of letters in the plain and cipher alphabets -- resulting in a progressive cipher in which alphabets are used irregularly, depending on the plaintext used. 
1854 Civ Kahn p.198 Charles Wheatstone invented what has become known as the Playfair cipher, having been publicized by his friend Lyon Playfair. This cipher uses a keyed array of letters to make a digraphic cipher which is easy to use in the field. He also re-invented the Wadsworth device and is known for that one. 
1857 Civ Kahn p.202 Admiral Sir Francis Beaufort's cipher (a variant of what's called ``Vigenère'') was published by his brother, after the admiral's death in the form of a 4x5 inch card. 
1859 Civ Kahn p.203 Pliny Earle Chase published the first description of a fractionating (tomographic) cipher. 
1854 Civ Cryptologia v.5 No.4 pp.193-208 Charles Babbage seems to have re-invented the wheel cipher. 
1861-1980 Civ Deavours "A study of United States patents from the issuance of the first cryptographic patent in 1861 through 1980 identified 1,769 patents which are primarily related to cryptography.'' [p.1]
1861 civ/(govt) Kahn p.207 Friedrich W. Kasiski published a book giving the first general solution of a polyalphabetic cipher with repeating passphrase, thus marking the end of several hundred years of strength for the polyalphabetic cipher. 
1861-5 Govt Kahn p.215 During the Civil War, possibly among other ciphers, the Union used substitution of select words followed by word columnar-transposition while the Confederacy used Vigenère (the solution of which had just been published by Kasiski). 
1891 Govt/(civ) Cryptologia v.5 No.4 pp.193-208 Major Etienne Bazeries did his version of the wheel cipher and published the design in 1901 after the French Army rejected it. [Even though he was a military cryptologist, the fact that he published it leads me to rate this as (civ) as well as govt.] 
1913 Govt Cryptologia v.5 No.4 pp.193-208 Captain Parket Hitt reinvented the wheel cipher, in strip form, leading to the M-138-A of WW-II. 
1916 Govt Cryptologia v.5 No.4 pp.193-208 Major Joseph O. Mauborgne put Hitt's strip cipher back in wheel form, strengthened the alphabet construction and produced what led to the M-94 cipher device. 
1917 Civ Kahn p.371 William Frederick Friedman, later to be honored as the father of US cryptanalysis (and the man who coined that term), was employed as a civilian cryptanalyst (along with his wife Elizebeth) at Riverbank Laboratories and performed cryptanalysis for the US Government, which had no cryptanalytic expertise of its own. WFF went on to start a school for military cryptanalysts at Riverbank -- later taking that work to Washington and leaving Riverbank. 
1917 Civ Kahn p.401 Gilbert S. Vernam, working for AT&T, invented a practical polyalphabetic cipher machine capable of using a key which is totally random and never repeats -- a one-time-tape. This is the only provably secure cipher, as far as we know. This machine was offered to the Government for use in WW-I but it was rejected. It was put on the commercial market in 1920. 
1918 Govt Kahn p.340-5 The ADFGVX system was put into service by the Germans near the end of WW-I. This was a cipher which performed a substitution (through a keyed array), fractionation and then transposition of the letter fractions. It was broken by the French cryptanalyst, Lieutenant Georges Painvin
1919 Civ Kahn p.420 Hugo Alexander Koch filed a patent in the Netherlands on a rotor based cipher machine. He assigned these patent rights in 1927 to Arthur Scherbius who invented and had been marketing the Enigma machine since about 1923. 
1919 Civ Kahn p.422 Arvid Gerhard Damm applied for a patent in Sweden for a mechanical rotor cipher machine. This machine grew into a family of cipher machines under the direction of Boris Caesar Wilhelm Hagelin who took over the business and was the only one of the commercial cryptographers of this period to make a thriving business. After the war, a Swedish law which enabled the government to appropriate inventions it felt important to defense caused Hagelin to move the company to Zug Switzerland where it was incorporated as Crypto AG. The company is still in operation, although facing controversy for having allegedly weakened a cipher product for sale to Iran. 
1921 Civ Kahn p.415 Edward Hugh Hebern incorporated ``Hebern Electric Code'', a company making electro-mechanical cipher machines based on rotors which turn, odometer style, with each character enciphered
1923 Civ Kahn p.421 Arthur Scherbius incorporated "Chiffriermaschinen Aktiengesellschaft'' to make and sell his Enigma machine. 
1924 Civ Deavours p.151 Alexander von Kryha produced his ``coding machine'' which was used, even by the German Diplomatic Corps, into the 1950s. However, it was cryptographically weak having a small period. A test cryptogram of 1135 characters was solved by the US cryptanalysts Friedman, Kullback, Rowlett and Sinkov in 2 hours and 41 minutes. Nevertheless, the machine continued to be sold and used -- a triumph of salesmanship and a lesson to consumers of cryptographic devices. 
1927-33 Civ Kahn p.802ff Users of cryptography weren't limited to legitimate bankers, lovers, experimenters, etc. There were also a handful of criminals. ``The greatest era of international smuggling -- Prohibition -- created the greatest era of criminal cryptology.'' [p.817] To this day, the FBI runs a cryptanalytic office to deal with criminal cryptography. [As of Kahn's writing in 1967, that office was located at 215 Pennsylvania Avenue SE, Washington DC.] 

"A retired lieutenant commander of the Royal Navy devised the systems for Consolidated Exporters' Pacific operation, though its Gulf and Atlantic groups made up their own as needed. 
``His name was unknown but his cryptologic expertise was apparent. The smugglers' systems grew increasingly more complicated. "Some of these are of a complexity never even attempted by any government for its most secret communications," wrote Mrs. [Elizebeth Smith] Friedman in a report in mid-1930. "At no time during the World War, when secret methods of communication reached their highest development, were there used such involved ramifications as are to be found in some of the correspondence of West Coast rum running vessels." '' [p.804]

1929 Civ Kahn p.404 Lester S. Hill published ``Cryptography in an Algebraic Alphabet'' in which a block of plaintext is enciphered by a matrix operation. 
1933-45 Govt Kahn p.422 (and many others) The Enigma machine was not a commercial success but it was taken over and improved upon to become the cryptographic workhorse of Nazi Germany. [It was broken by the Polish mathematician, Marian Rejewski, based only on captured ciphertext and one list of three months worth of daily keys obtained through a spy. Continued breaks were based on developments during the war by Alan Turing, Gordon Welchman and others at Bletchley Park in England.] 
1937 Govt Kahn p.18ff. The Japanese Purple machine was invented in response to revelations by Herbert O. Yardley and broken by a team headed by William Frederick Friedman. The Purple machine used telephone stepping relays instead of rotors and thus had a totally different permutation at each step rather than the related permutations of one rotor in different positions. 
1930's Govt Kahn p.510ff., Deavours p.10,89-91 Kahn attributes the American SIGABA (M-134-C) to William F. Friedman while Deavours attributes it to an idea of Frank Rowlett, one of Friedman's first hires. It improved on the rotor inventions of Hebern and Scherbius by using pseudo-random stepping of multiple rotors on each enciphering step rather than have uniform, odometer-like stepping of rotors as in Enigma. It also used 15 rotors (10 for character transformation, 5 probably for controlling stepping) rather than the Enigma's 3 or 4. 
1930's Govt Deavours p.144 The British TYPEX machine was an offshoot of the commercial Enigma purchased by the British for study in the 1920's. It was a 5-rotor machine with the two initial rotors being stators, serving the purpose of the German Enigma's plugboard. 
1970 Civ Feistel Dr. Horst Feistel led a research project at the IBM Watson Research Lab in the 1960's which developed the Lucifer cipher. This later inspired the US DES (below) and other product ciphers, creating a family labeled ``Feistel ciphers''. 
1976 civ/govt FIPS PUB-46 A design by IBM, based on the Lucifer cipher and with changes (including both S-box improvements and reduction of key size) by the US NSA, was chosen to be the U.S. Data Encryption Standard. It has since found worldwide acceptance, largely because it has shown itself strong against 20 years of attacks. Even some who believe it is past its useful life use it as a component -- e.g., of 3-key triple-DES. 
1976 Civ Diffie Whitfield Diffie and Martin Hellman published ``New Directions in Cryptography'', introducing the idea of public key cryptography. They also put forth the idea of authentication by powers of a one way function, now used in the S/Key challenge/response utility. They closed their paper with an observation for which this timeline web page gives detailed evidence: ``Skill in production cryptanalysis has always been heavily on the side of the professionals, but innovation, particularly in the design of new types of cryptographic systems, has come primarily from amateurs.'' 
April 1977 Civ Shamir Inspired by the Diffie-Hellman paper and acting as complete novices in cryptography, Ronald L. Rivest, Adi Shamir and Leonard M. Adleman had been discussing how to make a practical public key system. One night in April, Ron Rivest was laid up with a massive headache and the RSA algorithm came to him. He wrote it up for Shamir and Adleman and sent it to them the next morning. It was a practical public-key cipher for both confidentiality and digital signatures, based on the difficulty of factoring large numbers. They submitted this to Martin Gardner on April 4 for publication in Scientific American. It appeared in the September, 1977 issue. The Scientific American article included an offer to send the full technical report to anyone submitting a self-addressed, stamped envelope. There were thousands of such requests, from all over the world. 

Someone at NSA objected to the distribution of this report to foreign nationals and for a while, RS&A suspended mailings -- but when NSA failed to respond to inquiries asking for the legal basis of their request, RS&A resumed mailings. Adi Shamir believes this is the origin of the current policy [as of August 1995] that technical reports or papers can be freely distributed. [Note: two international journals, ``Cryptologia'' and ``The Journal of Cryptology'' were founded shortly after this attempt by NSA to restrain publication.] 

Contrary to rumor, RS&A apparently had no knowledge of ITAR or patent secrecy orders. They did not publish before applying for international patents because they wanted to avoid such restraints on free expression but rather because they were not thinking about patents for the algorithm. They just wanted to get the idea out. 

1978 Civ RSA The RSA algorithm was published in the Communications of the ACM. 
1984-5? Civ ROT13 The rot13 cipher was introduced into USENET News software to permit the encryption of postings in order to prevent innocent eyes from being assaulted by objectionable text. This is the first example I know of in which a cipher with a key everyone knows actually was effective. 
1990 Civ IACR90 Xuejia Lai and James Massey in Switzerland published ``A Proposal for a New Block Encryption Standard'', a proposed International Data Encryption Algorithm (IDEA) -- to replace DES. IDEA uses a 128-bit key and employs operations which are convenient for general purpose computers, therefore making software implementations more efficient. 
1990 Civ IACR90 Charles H. Bennett, Gilles Brassard et al. published their experimental results on Quantum Cryptography, which uses single photons to communicate a stream of key bits for some later Vernam encipherment of a message (or other uses). Assuming the laws of quantum mechanics hold, Quantum Cryptography provides not only secrecy but a positive indication of eavesdropping and a measurement of the maximum number of bits an eavesdropper might have captured. On the downside, QC currently requires a fiber-optic cable between the two parties. 
1991 Civ Garfinkel Phil Zimmermann released his first version of PGP (Pretty Good Privacy) in response to the threat by the FBI to demand access to the cleartext of the communications of citizens. PGP offered high security to the general citizen and as such could have been seen as a competitor to commercial products like Mailsafe from RSADSI. However, PGP is especially notable because it was released as freeware and has become a worldwide standard as a result while its competitors of the time remain effectively unknown. 
1994 Civ Rivest Professor Ron Rivest, author of the earlier RC2 and RC4 algorithms included in RSADSI's BSAFE cryptographic library, published a proposed algorithm, RC5, on the Internet. This algorithm uses data-dependent rotation as its non-linear operation and is parameterized so that the user can vary the block size, number of rounds and key length. It is still too new to have been analyzed enough to enable one to know what parameters to use for a desired strength -- although an analysis by RSA Labs, reported at CRYPTO'95, suggests that w=32, r=12 gives strength superior to DES. It should be remembered, however, that this is just a first analysis. 

Sources used for above table :


Source: CISSP Study Booklet on Cryptography
              http://cissp.cccure.net/CISSP%20Study%20Booklet%20on%20Cryptography.htm
 


Back To Home Page

Jan 25/01