|
The history of cryptography dates back thousands of years. Until recent decades, it has been a history of classic cryptography — 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. The evolution of cryptography has been paralleled by the evolution of cryptanalysis — of 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 Allied reading of Nazi Germany's ciphers may have shortened World War II by as much as two years. Until the 1970s, 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. Classical cryptography
Medieval cryptography It was probably religiously motivated textual analysis of the Qur'an which led to the invention of the frequency analysis technique for breaking monoalphabetic substitution ciphers sometime around 1000 CE. It was the most fundamental cryptanalytic advance until WWII. Essentially all ciphers remained vulnerable to this cryptanalytic technique until the invention of the polyalphabetic cipher by Alberti (ca 1465), and many remained so thereafter. Cryptography became (secretly) still 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 advance. 'Advanced ciphers', even after Alberti, weren't as advanced as their inventors / developers / users claimed (and probably even themselves believed); this over-optimism may be inherent in cryptography for it was then, and remains today, fundamentally difficult to really know how vulnerable your system actually is. In the absence of knowledge, guesses and hopes, as may be expected, are 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. 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. Cryptography, and its misuse, were involved in the plotting which led to the execution of Mata Hari and in the conniving which led to the travesty of Dreyfus' conviction and imprisonment, both in the early 20th century. Fortunately, cryptographers were also involved in exposing the machinations which had led to Dreyfus' problems; Mata Hari, in contrast, was shot. Outside of Middle East and Europe, cryptography remained comparatively undeveloped. Cryptography in Japan was not used until 1510, and advanced techniques were not known until after the opening of the country to the West in the 1860s. See also: Voynich Manuscript Cryptography from 1800 to World War II 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, rediscovered 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 developed systematic methods solving 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, which he proceeded to solve. His success created a public stir for some months. He later wrote an essay on methods of cryptography which proved useful in deciphering the German codes employed during World War I. Mathematical methods proliferated in the time leading up to World War II (notably in William F. Friedman's application of statistical techniques to cryptanalysis and cipher development and in Marian Rejewski's initial break into the German Army's version of the Enigma system). Both cryptography and cryptanalysis have become far more mathematical since WWII. Even so, it has taken the wide availability of computers, and the Internet as a communications medium, to bring effective cryptography into common use by anyone other than national governments or similarly large enterprises. World War II cryptography
Shannon The era of modern cryptography really begins with Claude Shannon, arguably the father of mathematical cryptography. In 1949 he published the paper Communication Theory of Secrecy Systems in the Bell System Technical Journal and a little later the book, Mathematical Theory of Communication, with Warren Weaver. These, in addition to his other works on information and communication theory established a solid theoretical basis for cryptography and for cryptanalysis. And with that, cryptography more or less disappeared into secret government communications organizations such as the NSA. Very little work was again made public until the mid '70s, when everything changed. An encryption standard The mid-1970s saw two major public (i.e., non-secret) advances. First was the publication of the draft Data Encryption Standard in the U.S. Federal Register on 17 March 1975. The proposed DES was submitted by IBM, at the invitation of the National Bureau of Standards (now NIST), in an effort to develop secure electronic communication facilities for businesses such as banks and other large financial organizations. After 'advice' and modification by the NSA, it was adopted and published as a Federal Information Processing Standard Publication in 1977 (currently at FIPS 46-3). DES was the first publicly accessible cipher to be 'blessed' by a national agency such as NSA. The release of its specification by NBS stimulated an explosion of public and academic interest in cryptography. DES was officially supplanted by the Advanced Encryption Standard (AES) in 2001 when NIST announced FIPS 197. After an open competition, NIST selected Rijndael, submitted by two Belgian cryptographers, to be the AES. DES, and more secure variants of it (such as Triple DES; see FIPS 46-3), are still used today, having been incorporated into many national and organizational standards. However, its 56-bit key-size has been shown to be insufficient to guard against brute force attacks (one such attack, undertaken by the cyber civil-rights group Electronic Frontier Foundation in 1997, succeeded in 56 hours -- the story is in Cracking DES, published by O'Reilly and Associates). As a result, use of straight DES encryption is now without doubt insecure for use in new cryptosystem designs, and messages protected by older cryptosystems using DES, and indeed all messages sent since 1976 using DES, are also at risk. Regardless of its inherent quality, the DES key size (56-bits) was thought to be too small by some even in 1976, perhaps most publicly by Whitfield Diffie. There was suspicion that government organizations even then had sufficient computing power to break DES messages; clearly others have achieved this capability. Public key The second development, in 1976, was perhaps even more important, for it fundamentally changed the way cryptosystems might work. This was the publication of the paper New Directions in Cryptography by Whitfield Diffie and Martin Hellman. It introduced a radically new method of distributing cryptographic keys, which went far toward solving one of the fundamental problems of cryptography, key distribution, and has become known as Diffie-Hellman key exchange. The article also stimulated the almost immediate public development of a new class of enciphering algorithms, the asymmetric key algorithms. Prior to that time, all useful modern encryption algorithms had been symmetric key algorithms, in which the same cryptographic key is used with the underlying algorithm by both the sender and the recipient, who must both keep it secret. All of the electromechanical machines used in WWII were of this logical class, as were the Caesar and Atbash ciphers and essentially all cipher and code systems throughout history. The 'key' for a code is, of course, the codebook, which must likewise be distributed and kept secret. Of necessity, the key in every such system had to be exchanged between the communicating parties in some secure way prior to any use of the system (the term usually used is 'via a secure channel') such as a trustworthy courier with a briefcase handcuffed to a wrist, or face-to-face contact, or a loyal carrier pigeon. This requirement is never trivial and rapidly becomes unmanageable as the number of participants increases, or when secure channels aren't available for key exchange, or when, as is sensible cryptographic practice, keys are frequently changed. In particular, if messages are meant to be secure from other users, a separate key is required for each possible pair of users. A system of this kind is known as a secret key, or symmetric key cryptosystem. D-H key exchange (and succeeding improvements and variants) made operation of these systems much easier, and more secure, than had ever been possible before. In contrast, asymmetric key encryption uses a pair of mathematically related keys, each of which decrypts the encryption performed using the other. Some, but not all, of these algorithms have the additional property that one of the paired keys cannot be deduced from the other by any known method other than trial and error. An algorithm of this kind is known as a public key or asymmetric key system. Using such an algorithm, only one key pair is needed per user. By designating one key of the pair as private (always secret), and the other as public (often visible), no secure channel is needed for key exchange. So long as the private key stays secret, the public key can be widely known for a very long time without compromising security, making it safe to reuse the same key pair indefinitely. For two users of an asymmetric key algorithm to communicate securely over an insecure channel, each user will need to know their own public and private keys as well as the other user's public key. Take this basic scenario: Alice and Bob each have a pair of keys they've been using for years with many other users. At the start of their message, they exchange public keys, unencrypted over an insecure line. Alice then encrypts a message using her private key, and then re-encrypts that result using Bob's public key. The double-encrypted message is then sent as digital data over a wire from Alice to Bob. Bob receives the bit stream and decrypts it using his own private key, and then decrypts that bit stream using Alice's public key. If the final result is recognizable as a message, Bob can be confident that the message actually came from someone who knows Alice's private key, and that anyone eavesdropping on the channel will need both Alice's and Bob's private keys in order to understand the message. Asymmetric algorithms rely for their effectiveness on a class of problems in mathematics called one-way functions, which require relatively little computational power to execute, but vast amounts of power to reverse. A classic example of a one-way function is multiplication of large prime numbers. It's fairly quick to multiply two large primes, but very difficult to factor the product of two large primes. Because of the mathematics of one-way functions, most possible keys are poor choices for cryptography; only a small fraction of possible keys of a given length are ideal candidates, and so asymetric algorithms require very long keys to reach the same level of security provided by relatively shorter symmetric keys. The demands of both generating the key pairs, and performing the encryption/decryption make asymmetric algorithms computatonally expensive. Since symmetric algorithms can often use any series of pseudorandom bits as a key, a disposable session key can be quickly generated for short-term use. Consequently, it is common practice to use a long asymetric key to exchange a disposable, much shorter (but just as strong) symmetric key. The slower asymmetric algorithm securely sends a symmetric session key, and the faster symmetric algorithm takes over for the remainder of the message. Asymmetric key cryptography, Diffie-Hellman key exchange, and the best known of the public key / private key algorithms (i.e., what is usually called the RSA algorithm), all seem to have been independently developed at a UK intelligence agency before the public announcement by Diffie and Hellman in '76. GCHQ has released documents claiming that they had developed public key cryptography before the publication of Diffie and Hellman's paper. Various classified papers were written at GCHQ during the 1960s and 1970s which eventually led to schemes essentially identical to RSA encryption and to Diffie-Hellman key exchange in 1973 and 1974. Some of these have now been published, and the inventors (James H. Ellis, Clifford Cocks, and Malcolm Williamson) have made public (some of) their work. Cryptography politics This in turn broke the near monopoly on cryptography held by government organizations worldwide (see S Levy's Crypto for a journalistic account of the policy controversy in the US). For the first time ever, those outside government organizations had access to cryptography not readily breakable by government. Considerable controversy, and conflict, both public and private, began immediately. It has not yet subsided. In many countries, for example, export of cryptography is subject to restrictions. Until 1996 export from the U.S. of cryptography using keys longer than 40 bits was sharply limited. As recently as 2004, former FBI Director Louis Freeh, testifying before the 9/11 Commission, called for new laws against public use of encryption. The most notable player in the advocacy of strong encryption for public use was Phil Zimmermann with his release of PGP (Pretty Good Privacy) in 1991. He distributed a freeware version of PGP when he felt threatened by legislation then under consideration by the US Government that would require back doors to be created in all cryptographic solutions developed within the US. His efforts in releasing PGP worldwide earned him a long battle with the Justice Department for the alleged violation of export restrictions. The Justice Department eventually dropped its case against Zimmermann, and the freeware distribution of PGP made its way around the world and eventually became an open standard. (RFC2440 or OpenPGP) Modern cryptanalysis
See also | |||||||||||||
|
| ||||||||||||||
 |
|
| |