CRYPTOLOGY

science concerned with communications in secure and usually secret form. It encompasses both cryptography and cryptanalysis. The term cryptology is derived from the Greek krypts, hidden, and lgos, word. Security obtains from legitimate users, the transmitter and the receiver, being able to transform information into a cipher by virtue of a keyi.e., a piece of information known only to them. Although the cipher is inscrutable and often unforgeable to anyone without this secret key, the authorized receiver can either decrypt the cipher to recover the hidden information or verify that it was sent in all likelihood by someone possessing the key. Cryptography (from the Greek krypts and grphein, to write) is the study of the principles and techniques by which information can be concealed in ciphers and later revealed by legitimate users employing the secret key, but in which it is either impossible or computationally infeasible for an unauthorized person to do so. Cryptanalysis (from the Greek krypts and analein, to loosen or to untie) is the science (and art) of recovering information from ciphers without knowledge of the key. Cryptology is oftenand mistakenlyconsidered a synonym for cryptography and occasionally for cryptanalysis, as in the popular solution of cryptograms or ciphers, but specialists in the field have for years adopted the convention that cryptology is the more inclusive term encompassing both cryptography and cryptanalysis. Cryptography was concerned initially with providing secrecy for written messages. Its principles apply equally well, however, to securing data flow between computers, to digitized speech, and to encrypting facsimile and television signals. Most communications satellites, for example, routinely encrypt the data flow to and from ground stations to provide both privacy and security for their subscribers. Because of this broadened interpretation of cryptography, the field of cryptanalysis has also been enlarged to include the recovery of information from ciphers concealing any form of data. This article discusses the basic elements of cryptology, delineating the principal systems and techniques of cryptography as well as the general types and procedures of cryptanalysis. It also provides a concise historical survey of the development of cryptosystems and cryptodevices. For additional information on the encoding and encryption of facsimile and television signals and of computer data, see telecommunications system and information processing. science concerned with communications in secure and usually secret form. It encompasses both cryptography and cryptanalysis. The former involves the study and application of the principles and techniques by which information is rendered unintelligible to all but the intended receiver, while the latter is the science and art of solving cryptosystems to recover such information. Cryptography initially developed as a means of disguising written messages. Today, however, its principles are applied to the encryption of facsimile and television signals, as for example those relayed by communications satellites to and from ground stations. More important, cryptography is pivotal for securing data communications between computers and for authenticating such transmissions i.e., providing assurance to the authorized receiver that the message is not a forgery. The latter function is of particular importance in banking and other commercial applications. Transformation of an intelligible message (plaintext) into an encrypted message (cipher, or ciphertext) typically requires the use of an algorithm (set of procedures) and a key. The algorithm may be public knowledge, but some or all of the key information must be kept secret from everyone other than the transmitter of the message and the legitimate receiver. In the transformation process, the algorithm is applied to the plaintext information, and the key employed to control how it is encrypted. The inverse operationi.e., decryptionby which the authorized receiver recovers the concealed information from the cipher is performed in a similar manner. Many varied cipher systems have been developed over the centuries. Fundamental to them is either of two basic mathematical operations, transposition or substitution, or a combination of both. Transposition rearranges the elements of the plaintext without altering the elements themselves. Substitution involves the replacement of plaintext elements such as letters or pairs of letters with other symbols without changing the sequence in which they occur. In more complex systems, both transposition and substitution are cascaded, yielding product ciphers. A highly sophisticated and widely used variation of such a cryptosystem is the Data Encryption Standard (DES), which was developed during the mid-1970s in the United States. The DES is a product block cipher, in which 16 rounds of substitutions and transpositions are cascaded. It encrypts a block of 64 bits of binary encoded plaintext under the control of a 56-bit key, producing a 64-bit ciphertext. The DES is readily implemented through the use of large-scale integrated and very large-scale integrated circuit chips. These miniature electronic devices are able to encrypt and decrypt a wide variety of data at rates ranging from tens of bits per second to tens of millions of bits per second. Cryptosystems may be either symmetric or asymmetric. In a symmetric cryptosystem, encryption and decryption are performed with a single key, so that both the sender and receiver use the same key. In an asymmetric system, by contrast, two different keys are employedone for each function. One-key cryptosystems, including the DES, have been associated with what is commonly referred to as the key-distribution problem. Specifically, the key has to be sent to all authorized users before messages can be exchanged. This results in a time delay and raises the possibility of the key's falling into unauthorized hands. Asymmetric, or two-key, cryptosystems circumvent the key-distribution problem for the most part. A user of this type of system can make one key (e.g., that for encryption) public, while keeping the second (for decryption) secret or private. Even if an unauthorized party were to duplicate the public key, it would not affect signal security, since only the legitimate user with the secret key could unscramble the ciphertext. These two-key (often called public-key) cryptosystems also exhibit considerable flexibility. They can be used to create digital signatures for messages, thereby providing the receiver with a means of readily authenticating transmissions for a third party. This feature lends itself well to certain kinds of computer data communications, most notably electronic funds transfers. Unlike one-key cryptosystems, which have been employed for hundreds of years, two-key systems are a relatively recent development, having received serious consideration since about the mid-1970s. At present, the only viable forms of two-key systems appear to be those whose cryptosecurity derives primarily from the infeasibility of factoring large composite integers. The most publicized example is the RivestShamirAdleman (RSA) cryptoalgorithm. Its major drawback is its limited channel capacityi.e., the number of bits of message information that can be communicated per second. Whereas some single-chip implementations of the DES one-key algorithm can process information at several million bits per second, the throughput of a comparably secure RSA chip is only a few thousand bits per second. Additional reading David Kahn, The Codebreakers (1967), also available in an abridged ed. with the same title (1973), is a comprehensive and meticulously researched history of classical single-key cryptology. A comprehensive treatment of current single-key and two-key, or public-key, cryptography can be found in Gustavus J. Simmons (ed.), Contemporary Cryptology: The Science of Information Integrity (1992), a collection of papers surveying all aspects of current cryptographic practice written by major contributors to the field. Modern texts in cryptology accessible to the general reader include Wladyslaw Kozaczuk, Enigma: How the German Machine Cipher Was Broken, and How It Was Read by the Allies in World War Two (1984; originally published in Polish, 1979), an important contribution covering the role played by a team of Polish cryptologists in breaking Enigma; David Kahn, Seizing the Enigma: The Race to Break the German U-Boat Codes, 19391943 (1991), a well-researched study; Ronald Lewin, The American Magic: Codes, Ciphers, and the Defeat of Japan (also published as The Other Ultra, 1982), the details and history of the Magic code-breaking machine; Dorothy Elizabeth Robling Denning, Cryptography and Data Security (1982); Gilles Brassard, Modern Cryptology (1988), a useful introductory study particularly for those with a background in computer science; and Dominic Welsh, Codes and Cryptography (1988), by a mathematician. Classical literature of the field includes Luigi Sacco, Manual of Cryptography (1938, reissued 1977; originally published in Italian, 2nd ed., rev. and enlarged, 1936), at one time described by Kahn as the world's finest unclassified book on cryptology; Marcel Givierge, Course in Cryptography (1934, reissued 1978; originally published in French, 1925); and most of the manuals written by the great U.S. cryptanalyst William F. Friedman: Elements of Cryptanalysis (1976), and History of the Use of Codes (1977), are representative works. The most recent information about developments in cryptology is found in Journal of Cryptology (3 times/yr.), devoted entirely to the subject; and Advances in Cryptology (annual), which can be highly recommended. Gustavus J. Simmons Cryptanalysis History abounds with examples of the seriousness of the cryptographer's failure and the cryptanalyst's success. In World War II the Battle of Midway, which marked the turning point of the naval war in the Pacific, was won by the United States largely because cryptanalysis had provided Adm. Chester W. Nimitz with information about the Japanese diversionary attack on the Aleutian Islands and of the Japanese order of attack for Midway. Another famous example of the consequences of a cryptanalytic success was the British cryptanalysis during World War I of a telegram from the German foreign minister, Arthur Zimmermann, to the German minister in Mexico City, Heinrich von Eckardt, laying out a plan to reward Mexico for entering the war as an ally of Germany. This breakthrough caused Pres. Woodrow Wilson of the United States to reverse his earlier opposition to U.S. entry into the war on the side of the Allies, thereby causing that momentous action much sooner than it would have occurred otherwise. Basic aspects While cryptography is clearly a science with well-established analytical and synthetic principles, cryptanalysis is as much an art as it is a science. The reason is that success in cryptanalyzing a cipher is as often as not a product of flashes of inspiration, gamelike intuition, and, most importantly, recognition by the cryptanalyst of pattern or structure, at almost the subliminal level, in the cipher. The great U.S. cryptanalyst Herbert O. Yardley described the crucial step in breaking the Japanese ciphers soon after World War I: Finally one night I awakened at midnight, for I had retired early, and out of the darkness came the conviction that a certain series of two-letter codewords absolutely must equal AIRURANDO (Ireland). The other words danced before me in rapid succession: DOKURITSU (independence), DOITSU (Germany), OWARI (stop). It is easy to state and demonstrate the principles on which the scientific part of cryptanalysis depends but nearly impossible to convey an appreciation of the art with which the principles are applied. Cryptanalysis of single-key cryptosystems depends on one simple factnamely, that traces of structure or pattern in the plaintext may survive encryption and be discernible in the ciphertext. Take for example the following: in a monoalphabetic substitution cipher in which each letter is simply replaced by another letter, the frequency distribution with which letters occur in the plaintext alphabet and in the ciphertext alphabet is identical. The cryptanalyst can use this fact in two ways: first, to recognize that he is faced with a monoalphabetic substitution cipher and, second, to aid him in selecting the likeliest equivalences of letters to be tried. The Table shows the number of occurrences of each letter in the text of this article, which approximates the raw frequency distribution for most technical material. The following cipher is the encryption of the first sentence of this paragraph using a monoalphabetic substitution: UFMDHQAQTMGRG BX GRAZTW PWM UFMDHBGMGHWOG VWDWAVG BA BAW GRODTW XQUH AQOWTM HCQH HFQUWG BX GHFIUHIFW BF DQHHWFA RA HCW DTQRAHWLH OQM GIFJRJW WAUFMDHRBA QAV SW VRGUWFARSTW RA HCW URDCWFHWLH. W occurs 20 times in the cipher, H occurs 16, etc. Even the most unskilled cryptanalyst using the frequency data in the Table should have no difficulty in recovering the plaintext and all but four symbols of the key in this case. It is possible to conceal information about raw frequency of occurrence by providing multiple cipher symbols for each plaintext letter in proportion to the relative frequency of occurrence of the letter; i.e., twice as many symbols for E as for S, etc. The collection of cipher symbols representing a given plaintext letter are called homophones. If the homophones are chosen randomly and with uniform probability when used, the cipher symbols will all occur (on average) equally often in the ciphertext. No less a mathematician than Carl Friedrich Gauss believed that he had devised an unbreakable cipher by introducing homophones. Unfortunately for Gauss and other cryptographers such is not the case, since there are many other persistent patterns in the plaintext that may partially or wholly survive encryption. Digraphs, for example, show a strong frequency distribution: TH occurring most often, about 20 times as frequently as HT, and so forth. With the use of tables of digraph frequencies that partially survive even homophonic substitution, it is still an easy matter to cryptanalyze a random substitution cipher, though the amount of ciphertext needed grows to a few hundred instead of a few tens of letters. If the cipher preserves the breaks between words as they existed in the plaintext, the frequency distribution for starting and ending letters and diagrams in words that are all distinct and different from the raw frequency of letter distributions can be used to advantage. Patterns of letters in words such as XYXX where X is the same cipher symbol can only fit a small selection of words such as BIBB, EPEE, LOLL, LULL, and SASS. In the heyday of manual cryptanalysis, volumes of word patterns were compiled. These are only some of the most obvious and easily described patterns whose persistence may provide a clue to the cryptanalyst. In English there are useful correlations between symbols up to eight or nine positions displaced in a word and of course context dependencies over entire sentences, all of which are of potential use to the cryptanalyst. Cryptography Cryptographic systems are generically classified (1) by the mathematical operations through which the plaintext information is concealed using the encryption keynamely, transposition, substitution, or product ciphers in which two such operations are cascaded; (2) according to whether the transmitter and receiver use the same key (symmetric cryptosystem) or different keys (asymmetric [two-key or public-key] cryptosystem); and (3) by whether they produce block or stream ciphers. The easiest way to describe the techniques on which cryptography depends is to first examine some simple cipher systems and abstract from these examples features that apply to more complex systems. There are two basic kinds of mathematical operations used in cipher systems: transpositions and substitutions. Transpositions rearrange the symbols in the plaintext without changing the symbols themselves. Substitutions replace plaintext elements (symbols, pairs of symbols, etc.) with other symbols or groups of symbols without changing the sequence in which they occur. Transposition ciphers In manual systems transpositions are generally carried out with the aid of an easily remembered mnemonic. For example, a popular schoolboy cipher is the rail fence in which the plaintext is staggered between rows and the rows are then read sequentially to give the cipher. In a depth two rail fence (two rows) the message WE ARE DISCOVERED SAVE YOURSELF becomes Simple frequency counts on the ciphertext would reveal to the cryptanalyst that letters occur with precisely the same frequency in the cipher and in the plaintext and, hence, that a simple transposition or rearrangement of the letters is involved. The rail fence is the simplest example of a class of transposition ciphers known as route ciphers, which enjoyed considerable popularity in the early history of cryptology. In general, the elements of the plaintext (usually single letters) are written in a prearranged order (route) into a geometric array (matrix) agreed upon in advance by the transmitter and receivertypically a rectangleand then read off by following another prescribed route through the matrix to produce the cipher. The depth two rail fence is a two-row by n-column matrix in which the plaintext is entered sequentially by columns; the encryption route is to read the top row first and then the lower: Clearly both the matrix and the route can be much more complex than those in this example. One form of transposition (permutation) that has been widely used depends on an easily remembered key word for identifying the order (route) in which the columns of a rectangular matrix are to be read. For example, using the key word AUTHOR and ordering the columns by the lexicographic order of the letters in the key word A significant improvement in cryptosecurity can be achieved by reencrypting the cipher obtained from one transposition with another transposition. Because the result (product) of two transpositions is also a transposition, the effect of multiple transpositions is to define a complex route in the matrix, which in itself would be difficult to describe by any simply remembered mnemonic device. In decrypting a route cipher, the receiver enters the ciphertext symbols into the agreed-upon matrix according to the encryption route and then reads the plaintext according to the original order of entry. The matrix may take the form of a rectangle, trapezoid, hexagon, triangle, or other geometric figure; however, transposition systems in which the keys consist solely in keeping the matrices, starting points, and routes secret are not often employed because of limited security and because manual systems have largely been replaced by automated cipher systems. In the same class also fall systems that make use of perforated cardboard matrices called grilles; descriptions of such systems can be found in most of the older books on cryptography. In contemporary cryptography transpositions serve principally as one of several encryption steps in forming a compound or product cipher. History Early cryptographic systems and applications People have probably tried to conceal information in written form from the time that writing developed. Examples survive in stone inscriptions, cuneiform tablets, and papyruses showing that the ancient Egyptians, Hebrews, Babylonians, and Assyrians all devised protocryptographic systems both to deny information to the uninitiated and to enhance its significance when it was revealed. The first recorded use of cryptography for correspondence, however, was by the Spartans, who as early as 400 BC employed a cipher device called the scytale for secret communications between military commanders. The scytale consisted of a tapered baton, around which was spirally wrapped a strip of parchment or leather on which the message was written. When unwrapped, the letters were scrambled in order and formed the cipher; however, when the strip was wrapped around another baton of identical proportions to the original, the plaintext reappeared. Thus, the Greeks were the inventors of the first transposition cipher. During the 4th century BC Aeneas Tacticus wrote a work entitled On the Defense of Fortifications, one chapter of which was devoted to cryptography, making it the earliest treatise on the subject. Another Greek, Polybius, devised a means of encoding letters into pairs of symbols by a device called the Polybius checkerboard, which is a true biliteral substitution and presages many elements of later cryptographic systems. Similar examples of primitive substitution or transposition ciphers abound in the history of other civilizations. The Romans used monoalphabetic substitution with a simple cyclic displacement of the alphabet. Julius Caesar employed a shift of three positions so that plaintext A was encrypted as D, while Augustus Caesar used a shift of one position so that plaintext A was enciphered as B. The first people to clearly understand the principles of cryptography and to elucidate the beginnings of cryptanalysis were the Arabs. They devised and used both substitution and transposition ciphers and discovered the use of both letter frequency distributions and probable plaintext in cryptanalysis. As a result, by about 1412, al-Kalka-shandi could include a respectable, if elementary, treatment of several cryptographic systems in his encyclopaedia Subh al-a'sha and give explicit instructions on how to cryptanalyze ciphertext using letter frequency counts complete with lengthy examples to illustrate the technique. The Vigenre table. In encrypting plaintext, the cipher letter is found European cryptology dates from the Middle Ages, during which it was developed by the Papal States and the Italian city-states. The earliest ciphers involved only vowel substitution (leaving consonants unchanged). The first European manual on cryptography (c. 1379) was a compilation of ciphers by Gabriele de Lavinde of Parma, who served Pope Clement VII. This manual, now in the Vatican archives, contains a set of keys for 24 correspondents and embraces symbols for letters, nulls, and several two-character code equivalents for words and names. The first brief code vocabularies, called nomenclators, were gradually expanded and became the mainstay for several centuries for diplomatic communications of nearly all European governments. In 1470 Leon Battista Alberti published Trattati in cifra, in which he described the first cipher disk; he prescribed that the setting of the disk should be changed after enciphering three or four words, thus conceiving of the notion of polyalphabeticity. Giambattista della Porta provided a modified form of square table and the earliest example of a digraphic cipher in De furtivis literarum notis (1563). The Traict des chiffres published in 1586 by Blaise de Vigenre contains the square table commonly attributed to him (Figure 2) and descriptions of the first plaintext and ciphertext autokey systems. By 1860 large codes were in common use for diplomatic communications, and cipher systems had become a rarity for this application. Cipher systems prevailed, however, for military communications except for high-command communications because of the difficulty of protecting codebooks from capture or compromise in the field. In the early history of the United States, codes were widely used, as were book ciphers. During the Civil War the Federal Army made extensive use of transposition ciphers, in which a key word indicated the order in which columns of the array were to be read and in which the elements were either plaintext words or code word replacements for plaintext. The Confederate Army primarily used the Vigenre cipher and on occasion monoalphabetic substitution. While the Union cryptanalysts solved most of the intercepted Confederate ciphers, the Confederacy in desperation sometimes published Union ciphers in newspapers, appealing for help from readers in cryptanalyzing them. Developments during World Wars I and II During the first two years of World War I, the belligerents employed cipher systems almost exclusively for tactical communications; code systems were still used mainly for high-command and diplomatic communications. Field cipher systems, however, such as the U.S. Signal Corps cipher disk, lacked sophistication. Nevertheless, some complicated cipher systems were used for high-level communications by the end of the war, the most famous of which was the German ADFGVX fractionation cipher. The communications needs of telegraphy and radio and the maturing of mechanical and electromechanical technology came together in the 1920s to bring about a true revolution in cryptodevices: the development of rotor cipher machines. Although the concept of the rotor had been anticipated in the older mechanical cipher disks, the credit goes to an American, Edward H. Hebern, for first recognizing that by hardwiring a monoalphabetic substitution in the connections from the contacts on one side of an electrical rotor to those on the other side and cascading a collection of such rotors, polyalphabetic substitutions of almost arbitrary complexity could be realized. Hebern also recognized that a permutation in which several letters were shifted by the same amount in the rotor connections, say A to D and B to E, was cryptographically weaker than one in which this partial periodicity was minimized and designed his rotors accordingly. Starting in 1921 and continuing through the next decade, Hebern constructed a series of steadily improving rotor machines that were evaluated by the U.S. Navy and undoubtedly led to the United States' superior position in cryptology as compared to the Axis powers during World War II. The 1920s were marked by a series of challenges by inventors of cipher machines to national cryptologic services and by one service to another, resulting in a steady improvement both of cryptomachines and of cryptanalytic techniques for the analysis of machine ciphers. At almost the same time that Hebern was inventing the rotor cipher machine in the United States, European engineers, notably Hugo A. Koch of The Netherlands and Arthur Scherbius of Germany, independently discovered the rotor concept and designed machines that became the precursors of the best known cipher machine in history, the German Enigma used in World War II. By an indirect path of development, these machines were the stimulus for the TYPEX, the cipher machine employed by the British during World War II. The United States introduced the M-134-C (SIGABA) cipher machine during World War II. The Japanese cipher machines of World War II have an interesting history linking them to both the Hebern machines and the Enigma. The Washington Conference on naval disarmament (192122) had as a primary objective limiting the total tonnage of capital ships (battleships, cruisers, and aircraft carriers) by the major powersthe United States, Great Britain, Japan, France, and Italy. The most difficult problem was the way in which this tonnage was to be allocated among the five countries. The Japanese Foreign Office sent detailed cipher instructions to its ambassador in Washington, D.C., to negotiate for a 10-to-7 U.S.-to-Japanese tonnage ratio, to fall back to 10 to 6.5 if that failed, and only as a last resort to retreat to a lowest acceptable ratio of 10 to 6. In a flash of inspiration Herbert O. Yardley broke the Japanese ciphers (see above Basic aspects), enabling the U.S. representative, Secretary of State Charles Evans Hughes, to press for this lower limit. The Japanese reluctantly accepted the inferior position of 10:10:6:3.3:3.3 (the United States, Britain, Japan, France, and Italy, respectively) laid out in the Five-Powers Treaty. Primarily because of a failure of their cryptography, they had settled for 100,000 tons of shipping less than they might otherwise have obtained, a difference of three capital ships. When Yardley later revealed in 1928 and subsequently published in The American Black Chamber the details of the American successes in cryptanalyzing the Japanese ciphers, with the associated costs to Japan, the Japanese government set out to develop the best cryptomachines possible. With this end in mind, it purchased the rotor machines of Hebern and Hagelin and the commercial Enigmas, as well as several other contemporary machines, for study and analysis. In 1930 the Japanese Foreign Office put into service its first rotor machine, which was code-named RED by U.S. cryptanalysts. In 193536 the U.S. Army Signal Intelligence Service (SIS) team of cryptanalysts, led by William F. Friedman, succeeded in cryptanalyzing RED ciphers, drawing heavily on its previous experience in cryptanalyzing the machine ciphers produced by the Hebern rotor machines. It was an ironic twist of fate that the Hebern machines, which were never commercially successful, played such a pivotal role in the design of two widely used rotor machines and in the evolution of the techniques that were vital to the cryptanalysis of the RED ciphers. In 1939 the Japanese introduced a new cipher machine, code-named PURPLE by U.S. cryptanalysts, in which rotors were replaced by telephone stepping switches. Because the replacement of RED machines by PURPLE machines was gradual, providing an enormous number of cribs between the systems to aid cryptanalysts, and because the Japanese had taken a shortcut to avoid the key distribution problem by generating keys systematically, U.S. cryptanalysts were able not only to cryptanalyze the RED ciphers but also to anticipate keys several days in advance. Functionally equivalent PURPLE cipher machines were constructed by Friedman and his SIS associates and used throughout the war to decrypt Japanese ciphers. Apparently no PURPLE machine survived the war. Another Japanese cipher machine code-named JADE was essentially the same as the PURPLE. It differed from the latter chiefly in that it typed Japanese kana characters directly. The greatest triumphs in the history of cryptanalysis were the Polish and British solution of the German Enigma ciphers and of two teleprinter ciphers, code-named ULTRA, and the American cryptanalysis of the Japanese RED, ORANGE, and PURPLE ciphers, code-named MAGIC. These developments played a major role in the Allies' conduct of World War II. Of the two, the cryptanalysis of the Japanese ciphers is the more impressive technically, because it was a tour de force of cryptanalysis against ciphertext alone. In the case of the Enigma machines, the basic patents had been issued in the United States, commercial machines were widely available, and the rotor designs were known to Allied cryptanalysts from a German code clerk. Although such factors do not diminish the practical importance of the ULTRA intercepts, they did make the cryptanalysis easier.