Cryptography, the science of encoding communications so that only the intended recipient can understand them, is ancient. In almost every civilization, cryptography appeared almost as soon as there was writing. For example, in 1500 B.C.E. a Mesopotamian scribe, using cuneiform signs that had different syllabic interpretations (akin to spelling "sh" as "ti," as in nation), disguised a formula for pottery glazes. According to the Greek historian Herodotus, in the fifth century B.C.E. a Greek at the Persian court used steganography, or hiding one message within another, to send a letter urging revolt against the Persians. In the fourth century B.C.E. the Spartans developed a transposition algorithm that relied on wrapping a sheet of papyrus around a wooden staff; in the same period, the Indian political classic the Arthasastra urged cryptanalysis as a means of obtaining intelligence. In the fifteenth century C.E., the Arabic encyclopedia, the Subh al-a 'sha, included a sophisticated discussion of cryptanalysis using frequency distributions.
The increasing use of digitized information and the rise of the Internet has made cryptography a daily tool for millions of people today. People use cryptography when they purchase an item via the World Wide Web, when they call on a European (GSM) cell phone, or when they make a withdrawal from a bank machine. Cryptography provides confidentiality (assurance that an eavesdropper will not be able to understand the communication), authenticity (proof of the message's origin), and integrity (guarantee that the message has not been tampered with in transit). Modern communications— phone, fax, or e-mail—are frequently in digital form (0's and 1's), and the unencrypted string of bits, or plaintext, is transformed into ciphertext by an encryption algorithm.
There are two parts to any encryption system: the algorithm for doing the transformation and a secret piece of information that specifies the particular transformation (called the key). (In the Spartan system described earlier, the key is the width of the wooden staff. If someone were to intercept an encrypted message, unless the interceptor had a staff of the correct width, all the spy would see would be a confused jumble of letters.) Each user has a personal key. This private chunk of information enables many people to use the same cryptosystem, yet each individual's communications are confidential.
Cryptography plays an important role in government, business, and military communications. Here, a soldier uses a cryptograph machine in Afghanistan while checking a code book for further information.
In modern cryptography the encryption algorithm is public and all secrecy resides in the key. Researchers can study the cryptosystem, and if they are unable to break the system, this helps establish confidence in the algorithm's security.
In theory an eavesdropper should be unable to determine significant information from an intercepted ciphertext. The Caesar cipher, developed by the Roman general Julius Caesar (c. 100–44 B.C.E., shifts each letter three to the right ("a" is encrypted as "D," "b" becomes "E," "z" becomes "C," and so on), and fails this test. Indeed, systems which replace letters of the alphabet by others in a fixed way—called simple substitution ciphers—do not produce random-looking output. As any Scrabble player knows, letters do not appear equally often in English text. For example, "e" occurs 13 percent of the time, "t" 9 percent, and so on. If "W" crops up as 13 percent of the ciphertext, it is a likely bet that W is substituting for e. The complex patterns of a language provide grist for the cryptanalyst, who studies such characteristics as the frequency of each letter's appearance at the beginning and end of a word and the frequency of occurrence of pairs of letters, triples, etc. If a message is encrypted under a simple substitution cipher, a trained cryptanalyst can usually crack the message with only twenty-five letters of the ciphertext.
The development of polyalphabetic ciphers in fifteenth-and sixteenth- century Europe signified a major advancement in encryption. These ciphersemploy several substitution alphabets and the key is a codeword that indicates which alphabet to use for each letter of the plaintext. Both polyalphabetic ciphers and transposition ciphers, in which the letters of the plaintext trade positions with one another, also fall prey to frequency analysis.
Despite its fame, for 4,000 years cryptography remained relatively unimportant in the context of wartime communications. The advent of radio changed that. Radio technology gave military commanders an unparalleled means to communicate with their troops, but this ability to command at a distance came at a cost: transmissions could be easily intercepted. Encrypted versions of a general's orders, troops' positions, and location and speed of ships at sea were available for friend and foe alike, and cryptanalysis became a critical wartime tool. However, errors made by cipher clerks were cryptography's greatest weakness. A single error, by substantially simplying the breaking of a cryptosystem, could endanger all communications encrypted under that system. This led to the development of automatic cryptography, a part of the mechanized warfare that characterized World War I.
American Gilbert Vernam developed encryption done directly on the telegraph wire, eliminating error-prone cipher clerks. This was done using "one-time" pads, a string of bits that is added, bit by bit, to the numeric version of the message, giving a completely secure cryptosystem. One-time pads can be used only once; if a key is ever reused, the system becomes highly vulnerable. The constant need for fresh keys, therefore, eliminates much of the advantage of one-time pads.
After the war inventors designed automated polyalphabetic substitution systems. Instead of looking up the substitutions in a paper table, they could be found by electric currents passing through wires. Rotor machines, in which the plaintext and ciphertext alphabets are on opposite sides of an insulated disk and wires connect each letter on one side to a letter on the other, were simultaneously developed in Europe and the United States. A single rotor is a simple substitution cipher. Automation can provide more. After encrypting a single letter, the rotor can shift, so that the letters of the plaintext alphabet are connected to new letters of the ciphertext alphabet. More rotors can be added and these can shift at different intervals. Such a system provides far more complex encryption than simple polyalphabetic substitution. These were also the principles behind the most famous rotor machine, the Enigma, used by the Germans during World War II. The Allies' ability to decode the Japanese cryptosystem Purple and the German Enigma dispatches during World War II played crucial roles in the battles of the Pacific and control of the Atlantic. The Colossus, a precursor of the first electronic, general-purpose computer, was built by the British during the war to decode German communications.
While substitution and transposition used by themselves result in weak cryptosystems, combining them properly with the key can result in a strong system. These were the operations used in the design of the U.S. Data Encryption Standard (DES), an algorithm with a 56-bit key that became a U.S. cryptography standard in 1977. With the exception of web-browser encryption and relatively insecure cable-TV signal encryption, DES was the most widely used cryptosystem in the world in the late 1990s. It was used for electronic funds transfer, for the protection of civilian satellite communications, and—with a small variation—for protecting passwords on computer systems.
For a cryptosystem to be secure, the difficulty of breaking it should be roughly the time it takes to do an exhaustive search of the keys. In the case of DES, this would be the time it takes to perform 256 DES encryptions. By 1998, however, the speed of computing had caught up with DES, and a $250,000 computer built by the Electronic Frontier Foundation decrypted a DES-encoded message in 56 hours. In 2001 the National Institute of Standards and Technology, whose predecessor (the National Bureau of Standards) certified DES, chose a successor: the Advanced Encryption Standard algorithm Rijndael (pronounced "Rhine Dahl"). This algorithm, which works in three key lengths (128, 192, and 256 bits), was developed by two Belgian researchers. Used even at its shortest key length, a message encrypted by Rijndael is expected to remain secure for many billions of years.
DES and Rijndael are "symmetric," or "private-key," systems; the same key is used for encryption and decryption and is known to both sender and receiver. But electronic commerce requires a different solution. What happens when a shopper tries to buy an item from an Internet merchant? The parties may not share a private key. How can the customer securely transmit credit information? The answer is public-key cryptography.
Public-Key Cryptography
Public-key cryptography operates on the seemingly paradoxical idea that one can publish the encryption algorithm and the key, and yet decryption remains computationally unfeasible for anyone but the correct recipient of the message. The concept, invented by Whitfield Diffie and Martin Hellman in 1975, relies on the existence of mathematical functions that are fast to compute but which take an extremely long time to invert. Multiplication and factoring are one such pair. Using processors available in 2001, the product of two 200-digit primes can be determined in under a second. Even with the world's fastest computers in 2002, factoring a 400-digit integer is estimated to take trillions of years. The well-known public-key algorithm RSA, named after its inventors Ronald Rivest, Adi Shamir, and Leonard Adleman, relies on the difficulty of factoring for its security.
Public-key cryptography is sometimes called "two-key" cryptography, since the public encryption key is different from the decryption key. By enabling two parties communicating over an insecure network to establish a private piece of information, public-key cryptography simplifies the problem of key distribution. Public-key systems run much slower than private-key ones, and so they are primarily used to establish an encryption key. This key is then used by a private-key system to encode the communication. Public-key cryptography also enables digital signatures, which verify the identity of the sender of an electronic document.
Although cryptography has been studied and used for thousands of years by mathematicians, politicians, linguists, and lovers, it became the province of national security in the half century following World War I. And while humans have always sought to keep information from prying eyes, the Information Age has intensified that need. Despite controversy, cryptography has returned from being a tool used solely by governments to one that is used by ordinary people, everyday.
Buchmann, Johannes. Introduction to Cryptography. New York: Springer Verlag, 2000.
Dam, Kenneth, and Herbert Lin. Cryptography's Role in Securing the Information Society. Washington, DC: National Academy Press, 1996.
Diffie, Whitfield, and Susan Landau. Privacy on the Line: The Politics of Wiretapping and Encryption. Cambridge, MA: MIT Press, 1998.
Kahn, David. The Codebreakers: The Story of Secret Writing. New York: Macmillan Company, 1967.
Schneier, Bruce. Applied Cryptography. New York: John Wiley and Sons, 1996.
Sinkov, Abraham. Elementary Cryptanalysis: A Mathematical Approach. Washington, DC: Mathematical Association of America, New Mathematical Library, 1966.
This complete Cryptography contains 1,789 words. This
article contains 1,884 words (approx. 6 pages at 300
words per page).
