Cryptography

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.

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 ciphers employ 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 2⁵⁶ 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.

see also Internet: Applications; Security; World Wide Web.

Susan Landau

Bibliography

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.

Cryptology

Cryptology is the study of encoding and decoding messages and the study of the mathematical foundations of cryptographic messages. The processes involved in cryptology rely on the principles of mathematics and statistics, and encompass areas such as probability theory , number theory , abstract algebra , and formula analysis .

Cryptography is the art of creating a code for a secret message, and is also known as encryption, or encrypting a message. Cryptanalysis is the art of breaking, or decrypting, the message without the use of the appropriate key. In other words, code-breakers are individuals who intercept or retrieve information not intended for them.

Historic Overview

The word "cryptology" comes from the Greek word kryptos, which means hidden. Cryptology dates back at least 4,000 years to its earliest recorded use in Egyptian hieroglyphics. Historically, the primary motivation for secure communications has been military: namely to keep the enemy from learning of plans even if they captured messages.

For example, when Julius Caesar (100 b.c.e.–44 b.c.e.) sent messages, he used a method that replaced every A with a D, every B with an E, and so on. Only those with whom Caesar entrusted his "shift by three" method could decrypt his messages.

Throughout the centuries, cryptology has continued to play a major role in military applications. For example, the success of mathematicians and cryptanalysts in breaking the seemingly unbreakable Nazi Enigma code greatly influenced the outcome of World War II. The German Enigma machine was a complex electromechanical encoding apparatus whose invention in 1918 for banking purposes quickly led to use by the German military. To solve the Enigma machine cipher, analysts had to determine which of the 15 billion billion (15 × 10¹⁸) settings were used.

Three young Polish mathematicians first broke the Enigma code in 1933. In 1939 they passed along their knowledge to Great Britain and France, who—with American support—went on to break the ever-changing versions of the wartime Enigma. British mathematician Alan Turing further developed an idea originally proposed by the Poles: namely, an electro-mechanical machine (later known as The Bombe) that greatly reduced the odds, and therefore the time required, to break the daily-changing Enigma keys.

In today's world of e-commerce and global concerns, secure communications are an ever-increasing necessity. Diplomatic codes are now common. And the importance of information in everyday transactions has increased interest in both business and personal security.

Encryption and Security

Most encryption involves a key and a set of steps or a procedure known as an algorithm . The key is an item of information used repeatedly in the algorithm while the message (called plaintext, even if it is sound or pictures) is being encrypted. The key customizes the algorithm. It is used with the algorithm for encoding and again later for decoding an entire message. If one knows the algorithm and the key, retrieving the plaintext from an encoded message is easy.

Encryption systems fall into one of two main categories. In symmetrickey encryption, the key is the same for the encryption of the message as for the decryption: that is, both the encoder and the decoder know and use the same key. In asymmetric or "public-key" encryption, the key provided to the decoder is not the same as the encoder's key.

The transmission of symmetric-key encryptions is safe provided that nobody besides the sender and intended receiver obtains the key. However, the problem in security arises from the difficulty of securely transferring the key so that those receiving the encrypted message are able to decrypt it. Asymmetric keys minimize this problem because a public-key cryptosystem uses a pair of keys—a private key that remains with the encryptor, and a public key that is openly available to all users, thus eliminating the need to transfer a key in secrecy.

Levels of Security. Systems that involve transmitting or storing the key with each message are very insecure. If an unauthorized person can recognize the key, then the next step is to recognize, guess at, or figure out the algorithm. Even without the key, the codebreaker can guess the algorithm, and then, by trying all the possible keys in succession, can conceivably recover the plaintext. For example, in Caesar's alphabetical cryptosystem discussed earlier, the cryptanalyst could simply try each of the 25 possible values of the key.

The security of transmissions can therefore be increased by increasing the number of possible keys and by increasing the amount of time it takes to try each key. If the same key is used for multiple messages, the cryptanalyst only has to figure out one key; but by varying the key from one message to another, the encryptor has essentially used a different procedure for encoding each one. With a complicated algorithm that may have a very large number of possible keys, even if the basic algorithm is known or guessed, the time and effort required to try all possible keys would take years, making decryption wholly impractical.

An example of a more secure algorithm is a book code. Both the sender and the receiver each have a copy of the same edition of some book. During encoding, each word in the plaintext is replaced with a code group that indicates where that same word appears in the book. Different occurrences of the same word in the plaintext may be represented by different code groups in the encoded message. With this method, the key is the book itself. Although a person who intercepts a message may guess that a book code is being used, the messages cannot be decoded unless the interceptor can determine what edition of what book is being used. The number of possible keys (books) is huge.

Before electronic computers became available, the most secure encryption method known was the one-time pad. The pad is a long list of different randomly chosen keys. Two (and only two) identical copies of the list of keys exist—one for the person encoding each message and another for whoever is decoding it. After being used for one message, a key is discarded and never used again. The next message will use the next key on the list. If the algorithm is even moderately complicated and the keys are long enough, cryptanalysis is practically impossible.

Cryptology and Computers

Electronic computing has revolutionized cryptology. Computers make it practical to use mathematical and logical algorithms that otherwise are much too complicated and time consuming. Encryption and decryption algorithms can be put into integrated circuit chips so that this technology can be economically applied anywhere. Yet governments are concerned that this will allow criminals to use modern communication and data storage methods without any fear of revealing their activities. Hence, consideration is being given to requiring that manufacturers include in encryption chips some facility for allowing authorized agents of the law to read messages encoded with them.

Computers have also brought cryptology into the home. As more and more everyday business transactions and personal communications are made at home by computer, personal privacy and transmission security have become everyone's concern. Present-day problems of security in transmission are compounded not only by the increased number of users but also by the users themselves—and a cryptosystem can be only as good as its users. Many attacks on private systems are inside jobs, and even honest users weaken the security of cryptosystems simply through careless use, such as failure to log off.

Because of the Internet, huge quantities of highly personal information are sent through a network of communications all over the world. Transmitted data includes credit card and bank account information and e-mail correspondence, as well as sensitive company, military, and government information. Computer encryption systems provide the level of security that permits such large-scale transmission of data to be reasonably safe. Computer encryption programs use mathematical formulas to scramble data so that the code is extremely difficult to crack, thereby making cryptanalysis very time-consuming, expensive, and, in the end, often unsuccessful.

Toward an Unbreakable Code

The Data Encryption Standard (DES), developed by IBM and adopted in 1976 as the federal standard, remains today as America's official standard symmetric cryptosystem, although ongoing work on an advanced system may soon replace it. The DES is considered secure because it has a sufficiently large number of keys and encryption is done in eighteen steps, in each of which the bits are permuted and scrambled. Decryption basically involves running the entire eighteen-step process in reverse. An attacker would have to try so great a number of keys to crack the code as to make cryptanalysis infeasible.*

*When a message is encrypted according to the U.S. Data Encryption Standard, the coding relies on 72 quadrillion (10¹⁵) keys.

Despite advances in cryptology, a known unbreakable code has yet to be discovered. From time to time, mathematicians and cryptographers have derived methods that they believed to be—or that actually were for a period of time—secure, but none has remained unbroken. However, as reported in newspapers across the country in March 2001, Harvard professor Michael Rabin has advanced a claim that he, along with his student Yangzhong Ding, has developed a mathematical proof that can be used to create a code unbreakable even by the most powerful computers.

In Rabin's method, a stream of random characters generated by a computer disappears after it is decoded by Rabin's mathematical proof, leaving nothing for a hacker to break and the method safe to repeat. Some professors have expressed reservations about the security of Rabin's method, and even his supporters remark that no code will remain unbreakable for very long.

On the technological horizon, however, looms the eventual advent of quantum and DNA computers, which will be capable of performing multiple tasks at a speed not possible for today's serial computers. Perhaps then cryptology will be able to boast of the discovery of a truly unbreakable code.

see also Analog and Digital; Communication Methods; Computers, Evolution of Electronic; Computers, Future of; Randomness; Turing, Alan.

Paula C. Davis and

F. Arnold Romberg

Bibliography

Kahn, David. The Codebreakers: The Story of Secret Writing, rev. ed. New York: Scribner, 1996.

Internet Resources

Cohen, Frank. "A Short History of Cryptography." <http://al.net/books/ip/Chap2-1.html>.

"How Encryption and Digital Signatures Work." Bionic Buffalo Corporation. <http://www.tatanka.com/doc/technote/tn0035.htm>.

"Introduction to Cryptography." SSH Communications Security. <http://www.ssh.fi/tech/crypto/intro.html>.

Kozaczuk, Wladyslaw. The Origins of the Enigma-Ultra Operation. <http://home.us.net/~encore/Enigma>.

Sale, Tony. The Principle of the Enigma. <http://www.codesandciphers.org.uk/enigma>.

DEVILISH SECRETS?

Because the science dealing with the transfer of secret messages hidden within codes is often associated with espionage, classified military information, secret meetings and activities, and other covert activities, cryptology has at times had a dark and mysterious reputation. Although early cryptographers were actually scientists, many common people thought they were engaged in the dark arts, and perhaps were even followers of the devil.

CRYPTOLOGY

CRYPTOLOGY, the technology of making and breaking codes and ciphers, has furnished America with excellent protection for its transmitted documents and with its best intelligence.

Revolution to World War I

James Lovell, a member of the Continental Congress who may be considered America's first cryptanalyst, solved British cryptograms for the rebels. One of them enabled Washington to alert the French admiral Comte de Grasse to blockade Yorktown, which then surrendered. Edgar Allan Poe popularized cryptology in 1843 with his story "The Gold Bug." During the Civil War, the Union utilized a word-transposition cipher; the South, a letter-substitution. The State Department printed its first cable code in 1867. In 1878, the New York Tribune solved and published encrypted telegrams showing that Democrats had bought electoral votes for Samuel J. Tilden in 1876. Though the Republican candidate, Rutherford B. Hayes, had nevertheless won the presidency, the disclosures helped lead to Republican gains in the midterm elections and to a Republican president, James A. Garfield, in 1880.

Code Breaking

Though some army officers investigated cryptology, the United States had no official cryptanalytic bureau until World War I. U.S. involvement in the war came about in part through codebreaking: Britain had cryptanalyzed a German offer to Mexico to make joint war on the United States; five weeks after newspapers headlined this, Congress declared war on Germany. In the spring of 1917, the Army's Military Intelligence Section established a codebreaking agency, called MI-8, placing a charismatic former State Department code clerk, Herbert O. Yardley, in charge. One of its solutions convicted a German spy. The American Expeditionary Forces had its own codebreaking unit, G.2 A.6, to solve German front-line codes, and its own Code Compilation Section, which printed and distributed new codes every few weeks. In 1919, MI-8 evolved into the joint Army-State Cipher Bureau under Yardley. During the Washington naval disarmament conference of 1921–1922, it solved Japanese diplomatic messages that helped America compel Tokyo to accept the equivalent of a battleship-and-a-half less than it wanted. America, Japan, and other nations saved millions that would otherwise have been spent on warships.

In 1929, Secretary of State Henry L. Stimson withdrew the Bureau's funds, on the ground that "gentlemen do not read each other's mail." Yardley, jobless in the Depression, awoke America to the importance of cryptology in his best-selling The American Black Chamber (1931). His bureau's work was assumed by the army's tiny Signal Intelligence Service (SIS) under the brilliant cryptologist William F. Friedman. During World War I, Friedman, at the Riverbank Laboratories, a think tank near Chicago, had broken new paths for cryptanalysis; soon after he joined the War Department as a civilian employee in 1921, he reconstructed the locations and starting positions of the rotors in a cipher machine. His work placed the United States at the forefront of world cryptology. Beginning in 1931, he expanded the SIS, hiring mathematicians first. By 1940, a team under the cryptanalyst Frank B. Rowlett had reconstructed the chief Japanese diplomatic cipher machine, which the Americans called purple. These solutions could not prevent Pearl Harbor because no messages saying anything like "We will attack Pearl Harbor" were ever transmitted; the Japanese diplomats themselves were not told of the attack. Later in the war, however, the solutions of the radiograms of the Japanese ambassador in Berlin, enciphered in purple, provided the Allies with what Army Chief of Staff General George C. Marshall called "our main basis of information regarding Hitler's intentions in Europe." One revealed details of Hitler's Atlantic Wall defenses.

The U.S. Navy's OP-20-G, established in 1924 under Lieutenant Laurence F. Safford, solved Japanese naval codes. This work flowered when the solutions of its branch in Hawaii made possible the American victory at Midway in 1942, the midair shootdown of Admiral Isoroku Yamamoto in 1943, and the sinking of Japanese freighters throughout the Pacific war, strangling Japan. Its headquarters in Washington cooperated with the British code breaking agency, the Government Code and Cypher School, at Bletchley Park, northwest of London, to solve U-boat messages encrypted in the Enigma rotor cipher machine. This enabled Allied convoys to dodge wolf packs and so help win the Battle of the Atlantic. Teams of American cryptanalysts and tabulating machine engineers went to the British agency to cooperate in solving German Enigma and other cipher systems, shortening the land war in Europe. No other source of information—not spies, aerial photographs, or prisoner interrogations—provided such trustworthy, high-level, voluminous, detailed, and prompt intelligence as code breaking.

At the San Francisco conference of 1945, which created the United Nations, the United States used information from code breaking to get its way on important matters, such as its desire, despite French opposition, for a veto procedure in the Security Council. In the 1940s, the United States began solving Soviet spy messages. Disclosed in 1995, these solutions, codenamed venona, showed that the Soviet Union had conducted massive espionage in America, including espionage related to nuclear armament.

Code Making

Dramatic though code breaking is, more important than getting other people's secrets is keeping one's own. America has excelled in this as well. The first law specifying the duties of the Post Office, 20 February 1792 made it a crime for its employees to open mail, thus protecting privacy before European countries did. Thomas Jefferson invented an ingenious cipher system but filed and forgot it; the U.S. Army adopted an independent invention of it in 1922 that was used until World War II. In 1917, an engineer at the American Telephone & Telegraph Company, Gilbert S. Vernam, devised the first online cipher machine. Based on a teletypewriter, it electromechanically added the on-off impulses of the plain-text message to those of a key tape and transmitted the resultant ciphertext. This mechanism, the first binary device in cryptology, was perfected by Major Joseph O. Mauborgne, who, by making the key tape random and prohibiting more than a single use of it, created the only theoretically unbreakable cipher, the one-time tape. Also in 1917, an amateur inventor, Edward H. Hebern of California, devised the first rotor cipher machine before three Europeans independently had the same idea. In the 1930s, Rowlett and Friedman irregularized the turning of rotors. Their cipher machine, the sigaba, armored U.S. Army and Navy communications against the technology of the time; none of its messages were broken by Axis powers. During World War II, Navajos in the Marine Corps translated English-language orders into their language for walkie-talkie transmission; the Japanese never understood them. In 1943, AT&T engineers built a radiotelephone scrambler, sigsaly, that used a one-time key and proved invulnerable to German eavesdropping. Another AT&T employee, Claude E. Shannon, the conceiver of information theory, provided cryptology with a theoretical underpinning in his article "Communication Theory of Secrecy Systems," published in 1949.

In 1976, the National Institute of Standards and Technology promulgated a Data Encryption Standard so computers could intercommunicate securely; it was replaced on 26 May 2002 by the Advanced Encryption Standard. Also in 1976, an electrical engineering student, Whitfield Diffie, aided by Professor Martin Hellman, both of Stanford University, devised the most important advance in cryptography since the invention of cryptography itself: public-key cryptography. This permitted people to communicate in secret without prearrangement and ultimately opened the way to online electronic commerce.

BIBLIOGRAPHY

Alvarez, David. Secret Messages: Codebreaking and American Diplomacy, 1930–1945. Lawrence: University Press of Kansas, 2000.

Haynes, John Earl, and Harvey Klehr. VENONA: Decoding Soviet Espionage in America. New Haven, Conn.: Yale University Press, 1999.

Kahn, David. The Codebreakers: The Story of Secret Writing. 2nd ed. New York: Scribner, 1996.

Rosenheim, Shawn James. The Cryptographic Imagination: Secret Writing from Edgar Poe to the Internet. Baltimore: Johns Hopkins University Press, 1997. A literary essay.

Rowlett, Frank B. The Story of Magic: Memoirs of an American Cryptologic Pioneer. Laguna Hills, Calif.: Aegean Park Press, 1998.

Schlesinger, Stephen. "Cryptanalysis for Peacetime: Codebreaking and the Birth and Structure of the United Nations." Cryptologia 19 (July 1995): 217–235.

DavidKahn

See alsoIntelligence, Military and Strategic .

Cryptology and Number Theory

Forensic analyses can be concerned with unraveling the true meaning of deliberately convoluted communications. Forensic accounting can involve the search of seized financial and other paper and computer records. An examiner may encounter information that has been altered so as to be indecipherable. Understanding the nature of the informational alteration can permit descrambling strategies to be applied, rendering the information understandable.

Cryptography is a division of applied mathematics concerned with developing schemes and formula to enhance the privacy of communications through the use of codes . More specifically, cryptography is the study of procedures that allow messages or information to be encoded (obscured) in such a way that it is extremely difficult to read or understand encoded information without having a specific key (i.e., procedures to decode) that can be used to reverse the encoding procedure.

Cryptography allows its users, whether governments, military, businesses or individuals, to maintain privacy and confidentiality in their communications. The goal of every cryptographic scheme is to be "crack proof" (i.e., only able to be decoded and understood by authorized recipients). Cryptography is also a means to ensure the integrity and preservation of data from tampering. Modern cryptographic systems rely on functions associated with advanced mathematics, number theory that explores the properties of numbers and the relationships between numbers.

Encryption systems can involve the simplistic replacement of letters with numbers, or they can involve the use of highly secure "one-time pads" (also known as Vernam ciphers ). Because one-time pads are based upon codes and keys that can only be used once, they offer the only "crack proof" method of cryptography known. The vast number of codes and keys required, however, makes one-time pads impractical for general use.

Many wars and diplomatic negotiations have turned on the ability of one combatant or country to read the supposedly secret messages of its enemies. The use of cryptography has broadened from its core diplomatic and military uses to become of routine use by companies and individuals seeking privacy in their communications. Governments, companies, and individuals require more secure systems to protect their databases and e-mail.

In addition to improvements made to cryptologic systems based on information made public from classified government research programs, international scientific research organizations devoted exclusively to the advancement of cryptography, such as the International Association for Cryptologic Research (IACR), began to apply applications of mathematical number theory to enhance privacy, confidentiality, and the security of data. Applications of number theory were used to develop increasingly involved algorithms (i.e., step-by-step procedures for solving a mathematical problems). In addition, as commercial and personal use of the Internet grew, it became increasingly important, not only to keep information secret, but also to be able to verify the identity of message sender. Cryptographic use of certain types of algorithms called "keys" allow information to be restricted to a specific and limited audience whose identities can be authenticated.

In some cryptologic systems, encryption is accomplished, for example, by choosing certain prime numbers and then products of those prime numbers as the basis for further mathematical operations. In addition to developing such mathematical keys, the data itself is divided into blocks of specific and limited length so that the information that can be obtained, even from the form of the message, is limited. Decryption is usually accomplished by following an elaborate reconstruction process that itself involves unique mathematical operations. In other cases, decryption is accomplished by performing the inverse mathematical operations performed during encryption.

In the late 1970s, government intelligence agencies, and Ronald Rivest, Adi Shamir, and Leonard Adleman, published an algorithm (the RSA algorithm) destined to become a major advancement in cryptology. The RSA algorithm underlying the system derives its security from the difficulty in factoring very large composite numbers. The RSA algorithm was the mathematical foundation for the development of a public two-key cryptographic system called Pretty Good Privacy (PGP).

Applications of number theory allow the development of mathematical algorithms that can make information (data) unintelligible to everyone except for intended users. In addition, mathematical algorithms can provide real physical security to data—allowing only authorized users to delete or update data. One of the problems in developing tools to crack encryption codes involves finding ways to factor very large numbers. Advances in applications of number theory, along with significant improvements in the power of computers, have made factoring large numbers less daunting.

In general, the larger the key size used in a system, the longer it will take computers to factor the composite numbers used in the keys.

Specialized mathematical derivations of number theory such as theory and equations dealing with elliptical curves are also making an increasing impact on cryptology. Although, in general, larger keys provide increasing security, applications of number theory and elliptical curves to cryptological algorithms allow the use smaller keys without any loss of security.

Advancements in number theory are also used to crack important cryptologic systems. Attempting to crack encryption codes (the encryption procedures) often requires use of advanced number theories that allow, for instance, an unauthorized user to determine the product of the prime numbers used to start the encryption process. Factoring this product is, at best, a time consuming process to determine the underlying prime numbers. An unsophisticated approach, for example, might be to simply to attempt or apply all prime numbers. Other more elegant attempts involve algorithms termed quadratic sieves, a method of factoring integers, developed by Carl Pomerance, that is used to attack smaller numbers, and field sieves, algorithms that are used in attempts to determine larger integers. Advances in number theory allowed factoring of large numbers to move from procedures that, by manual manipulation, could take billions of years, to procedures that—with the use of advanced computing—can be accomplished in weeks or months. Further advances in number theory may lead to the discovery of a polynomial time factoring algorithm that can accomplish in hours what now takes months or years of computer time.

Advances in factoring techniques and the expanding availability of computing hardware (both in terms of speed and low cost) make the security of the algorithms underlying cryptologic systems increasingly vulnerable.

These threats to the security of cryptologic systems are, in some regard, offset by continuing advances in design of powerful computers that have the ability to generate larger keys by multiplying very large primes. Despite the advances in number theory, it remains easier to generate larger composite numbers than it is to factor those numbers.

Other improvements related to applications of number theory involve the development of "nonreputable" transactions. Non-reputable means that parties cannot later deny involvement in authorizing certain transactions (e.g., entering into a contract or agreement). Many cryptologists and communication specialists assert that a global electronic economy is dependent on the development of verifiable and nonreputable transactions that carry the legal weight of paper contracts. Legal courts around the world are increasingly being faced with cases based on disputes regarding electronic communications.

see also Codes and ciphers; Computer forensics; Computer hardware security; Computer security and computer crime investigation; Computer software security; Decryption.

Cryptology and Number Theory

█ K. LEE LERNER

Cryptography is a division of applied mathematics concerned with developing schemes and formula to enhance the privacy of communications through the use of codes. More specifically, cryptography is the study of procedures that allow messages or information to be encoded (obscured) in such a way that it is extremely difficult to read or understand encoded information without having a specific key (i.e., procedures to decode) that can be used to reverse the encoding procedure.

Cryptography allows its users, whether governments, military, businesses or individuals, to maintain privacy and confidentiality in their communications. The goal of every cryptographic scheme is to be "crack proof" (i.e, only able to be decoded and understood by authorized recipients). Cryptography is also a means to ensure the integrity and preservation of data from tampering. Modern cryptographic systems rely on functions associated with advanced mathematics, number theory that explores the properties of numbers and the relationships between numbers.

Encryption systems can involve the simplistic replacement of letters with numbers, or they can involve the use of highly secure "one-time pads" (also known as Vernam ciphers). Because one-time pads are based upon codes and keys that can only be used once, they offer the only "crack proof" method of cryptography known. The vast number of codes and keys required, however, makes one-time pads impractical for general use.

Many wars and diplomatic negotiations have turned in the ability of one combatant or country to read the supposedly secret messages of its enemies. The use of cryptography has broadened from its core diplomatic and military users to become of routine use by companies and individuals seeking privacy in their communications. Governments, companies and individuals required more secure systems to protect their databases and email.

In addition to improvements made to cryptologic systems based on information made public from classified government research programs, international scientific research organizations devoted exclusively to the advancement of cryptography (e.g., the International Association for Cryptologic Research (IACR)), began to apply applications of mathematical number theory to enhance privacy, confidentiality, and the security of data. Applications of number theory were used to develop increasingly involved algorithms (i.e., step-by-step procedures for solving a mathematical problems). In addition, as commercial and personal use of the Internet grew, it became increasingly important, not only to keep information secret, but also to be able to verify the identity of message sender. Cryptographic use of certain types of algorithms called "keys" allow information to be restricted to a specific and limited audiences whose identities can be authenticated.

Mathematical Operations

In some cryptologic systems, encryption is accomplished, for example, by choosing certain prime numbers and then products of those prime numbers as a basis for further mathematical operations. In addition to developing such mathematical keys, the data itself is divided into blocks of specific and limited length so that the information that can be obtained even from the form of the message is limited. Decryption is usually accomplished by following an elaborate reconstruction process that itself involves unique mathematical operations. In other cases, decryption is accomplished by performing the inverse mathematical operations performed during encryption.

In the late 1970s, government intelligence agencies and Ronald Rivest, Adi Shamir, and Leonard Adleman published an algorithm (the RSA algorithm) destined to become a major advancement in cryptology. The RSA algorithm underlying the system derives its security from the difficulty in factoring very large composite numbers. The RSA algorithm was the mathematical foundation for the development of a public two-key cryptographic system called Pretty Good Privacy (PGP).

Applications of number theory allow the development of mathematical algorithms which can make information (data) unintelligible to everyone except for intended users. In addition, mathematical algorithms can provide real physical security to data—allowing only authorized users to delete or update data. One of the problems in developing tools to crack encryption codes involves finding ways to factor very large numbers. Advances in applications of number theory, along with significant improvements in the power of computers, have made factoring large numbers less daunting.

In general, the larger the key size used in a system systems, the longer it will take computers to factor the composite numbers used in the keys.

Specialized mathematical derivations of number theory such as theory and equations dealing with elliptical curves are also making an increasing impact on cryptology. Although, in general, larger keys provide increasing security, applications of number theory and elliptical curves to cryptological algorithms allow the use smaller keys with any loss of security.

Advancements in number theory are also used to crack important cryptologic systems. Attempting to crack encryoption codes (the encryption procedures) often requires use of advanced number theories that allow, for instance, an unauthorized user to determine the product of the prime numbers used to start the encryption process. Factoring this product is, at best, a time consuming process to determine the underlying prime numbers. An unsophisticated approach, for example, might be to simply attempt or apply all prime numbers. Other more elegant attempts involve algorithms termed quadratic sieves, a method of factoring integers, developed by Carl Pomerance, that is used to attack smaller numbers, and field sieves algorithms that are used in attempts to determine larger integers. Advances in number theory allowed factoring of large numbers to move from procedures that, by manual manipulation, could take billions of years, to procedures that—with the use of advanced computing—can be accomplished in weeks or months. Further advances in numbertheory may lead to the discovery of a polynomial time factoring algorithm that can accomplish in hours what now takes months or years of computer time.

Advances in factoring techniques and the expanding availability of computing hardware (both in terms of speed and low cost) make the security of the algorithms underlying cryptologic systems increasingly vulnerable.

These threats to the security of cryptologic systems are, in some regard, offset by continuing advances in design of powerful computers that have the ability to generate larger keys by multiplying very large primes. Despite the advances in number theory, it remains easier to generate larger composite numbers than it is to factor those numbers.

Other improvements related to applications of number theory involve the development of "non-reputable" transactions. Non-reputable means that parties can not later deny involvement in authorizing certain transactions (e.g., entering into a contract or agreement). Many cryptologists and communication specialists assert that a global electronic economy is dependent on the development of verifiable and non-reputable transactions that carry the legal weight of paper contracts. Legal courts around the world are increasingly faced with cases based on disputes regarding electronic communications.

█ FURTHER READING:

BOOKS:

Burn R. P. A Pathway into Number Theory, 2nd. ed. New York: Cambridge University Press, 1997.

Niederreiter, Harald. Mathematical Foundations of Coding and Cryptology. Singapore: World Scientific Press, 2003.

Wagstaff, Samuel S., Jr., Cryptanalysis of Number Theoretic Cyphers Boca Raton, FL: CRC Press, 2002.

SEE ALSO

Cryptology, History
Cryptonym