Cryptology – Cryptography | Britannica.com

The easiest way to describe the techniques on which cryptography depends is first to examine some simple cipher systems and then 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.

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 letters of the plaintext are written alternating 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 would be written

Simple frequency counts on the ciphertext would reveal to the cryptanalyst that letters occur with precisely the same frequency in the cipher as in an average plaintext and, hence, that a simple rearrangement of the letters is probable.

The rail fence is the simplest example of a class of transposition ciphers, known as route ciphers, that 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)typically a rectangleagreed upon in advance by the transmitter and receiver and then read off by following another prescribed route through the matrix to produce the cipher. The key in a route cipher consists of keeping secret the geometric array, the starting point, and the routes. Clearly, both the matrix and the routes can be much more complex than in this example; but even so, they provide little security. One form of transposition (permutation) that was widely used depends on an easily remembered key word for identifying the 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

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. 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 simple mnemonic. (See Product ciphers, below.)

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 older books on cryptography. In contemporary cryptography, transpositions serve principally as one of several encryption steps in forming a compound or product cipher.

In substitution ciphers, units of the plaintext (generally single letters or pairs of letters) are replaced with other symbols or groups of symbols, which need not be the same as those used in the plaintext. For instance, in Sir Arthur Conan Doyles Adventure of the Dancing Men (1903), Sherlock Holmes solves a monoalphabetic substitution cipher in which the ciphertext symbols are stick figures of a human in various dancelike poses.

The simplest of all substitution ciphers are those in which the cipher alphabet is merely a cyclical shift of the plaintext alphabet. Of these, the best-known is the Caesar cipher, used by Julius Caesar, in which A is encrypted as D, B as E, and so forth. As many a schoolboy has discovered to his embarrassment, cyclical-shift substitution ciphers are not secure. And as is pointed out in the section Cryptanalysis, neither is any other monoalphabetic substitution cipher in which a given plaintext symbol is always encrypted into the same ciphertext symbol. Because of the redundancy of the English language, only about 25 symbols of ciphertext are required to permit the cryptanalysis of monoalphabetic substitution ciphers, which makes them a popular source for recreational cryptograms. The explanation for this weakness is that the frequency distributions of symbols in the plaintext and in the ciphertext are identical, only the symbols having been relabeled. In fact, any structure or pattern in the plaintext is preserved intact in the ciphertext, so that the cryptanalysts task is an easy one.

There are two main approaches that have been employed with substitution ciphers to lessen the extent to which structure in the plaintextprimarily single-letter frequenciessurvives in the ciphertext. One approach is to encrypt elements of plaintext consisting of two or more symbols; e.g., digraphs and trigraphs. The other is to use several cipher alphabets. When this approach of polyalphabetic substitution is carried to its limit, it results in onetime keys, or pads.

In cryptosystems for manually encrypting units of plaintext made up of more than a single letter, only digraphs were ever used. By treating digraphs in the plaintext as units rather than as single letters, the extent to which the raw frequency distribution survives the encryption process can be lessened but not eliminated, as letter pairs are themselves highly correlated. The best-known digraph substitution cipher is the Playfair, invented by Sir Charles Wheatstone but championed at the British Foreign Office by Lyon Playfair, the first Baron Playfair of St. Andrews. Below is an example of a Playfair cipher, solved by Lord Peter Wimsey in Dorothy L. Sayerss Have His Carcase (1932). Here, the mnemonic aid used to carry out the encryption is a 5 5-square matrix containing the letters of the alphabet (I and J are treated as the same letter). A key word, MONARCHY in this example, is filled in first, and the remaining unused letters of the alphabet are entered in their lexicographic order:

Plaintext digraphs are encrypted with the matrix by first locating the two plaintext letters in the matrix. They are (1) in different rows and columns; (2) in the same row; (3) in the same column; or (4) alike. The corresponding encryption (replacement) rules are the following:

When the two letters are in different rows and columns, each is replaced by the letter that is in the same row but in the other column; i.e., to encrypt WE, W is replaced by U and E by G.

When A and R are in the same row, A is encrypted as R and R (reading the row cyclically) as M.

When I and S are in the same column, I is encrypted as S and S as X.

When a double letter occurs, a spurious symbol, say Q, is introduced so that the MM in SUMMER is encrypted as NL for MQ and CL for ME.

An X is appended to the end of the plaintext if necessary to give the plaintext an even number of letters.

Encrypting the familiar plaintext example using Sayerss Playfair array yields:

If the frequency distribution information were totally concealed in the encryption process, the ciphertext plot of letter frequencies in Playfair ciphers would be flat. It is not. The deviation from this ideal is a measure of the tendency of some letter pairs to occur more frequently than others and of the Playfairs row-and-column correlation of symbols in the ciphertextthe essential structure exploited by a cryptanalyst in solving Playfair ciphers. The loss of a significant part of the plaintext frequency distribution, however, makes a Playfair cipher harder to cryptanalyze than a monoalphabetic cipher.

The other approach to concealing plaintext structure in the ciphertext involves using several different monoalphabetic substitution ciphers rather than just one; the key specifies which particular substitution is to be employed for encrypting each plaintext symbol. The resulting ciphers, known generically as polyalphabetics, have a long history of usage. The systems differ mainly in the way in which the key is used to choose among the collection of monoalphabetic substitution rules.

The best-known polyalphabetics are the simple Vigenre ciphers, named for the 16th-century French cryptographer Blaise de Vigenre. For many years this type of cipher was thought to be impregnable and was known as le chiffre indchiffrable, literally the unbreakable cipher. The procedure for encrypting and decrypting Vigenre ciphers is illustrated in the figure.

In the simplest systems of the Vigenre type, the key is a word or phrase that is repeated as many times as required to encipher a message. If the key is DECEPTIVE and the message is WE ARE DISCOVERED SAVE YOURSELF, then the resulting cipher will be

The graph shows the extent to which the raw frequency of occurrence pattern is obscured by encrypting the text of this article using the repeating key DECEPTIVE. Nevertheless, in 1861 Friedrich W. Kasiski, formerly a German army officer and cryptanalyst, published a solution of repeated-key Vigenre ciphers based on the fact that identical pairings of message and key symbols generate the same cipher symbols. Cryptanalysts look for precisely such repetitions. In the example given above, the group VTW appears twice, separated by six letters, suggesting that the key (i.e., word) length is either three or nine. Consequently, the cryptanalyst would partition the cipher symbols into three and nine monoalphabets and attempt to solve each of these as a simple substitution cipher. With sufficient ciphertext, it would be easy to solve for the unknown key word.

The periodicity of a repeating key exploited by Kasiski can be eliminated by means of a running-key Vigenre cipher. Such a cipher is produced when a nonrepeating text is used for the key. Vigenre actually proposed concatenating the plaintext itself to follow a secret key word in order to provide a running key in what is known as an autokey.

Even though running-key or autokey ciphers eliminate periodicity, two methods exist to cryptanalyze them. In one, the cryptanalyst proceeds under the assumption that both the ciphertext and the key share the same frequency distribution of symbols and applies statistical analysis. For example, E occurs in English plaintext with a frequency of 0.0169, and T occurs only half as often. The cryptanalyst would, of course, need a much larger segment of ciphertext to solve a running-key Vigenre cipher, but the basic principle is essentially the same as beforei.e., the recurrence of like events yields identical effects in the ciphertext. The second method of solving running-key ciphers is commonly known as the probable-word method. In this approach, words that are thought most likely to occur in the text are subtracted from the cipher. For example, suppose that an encrypted message to President Jefferson Davis of the Confederate States of America was intercepted. Based on a statistical analysis of the letter frequencies in the ciphertext, and the Souths encryption habits, it appears to employ a running-key Vigenre cipher. A reasonable choice for a probable word in the plaintext might be PRESIDENT. For simplicity a space will be encoded as a 0. PRESIDENT would then be encodednot encryptedas 16, 18, 5, 19, 9, 4, 5, 14, 20 using the rule A = 1, B = 2, and so forth. Now these nine numbers are added modulo 27 (for the 26 letters plus a space symbol) to each successive block of nine symbols of ciphertextshifting one letter each time to form a new block. Almost all such additions will produce random-like groups of nine symbols as a result, but some may produce a block that contains meaningful English fragments. These fragments can then be extended with either of the two techniques described above. If provided with enough ciphertext, the cryptanalyst can ultimately decrypt the cipher. What is important to bear in mind here is that the redundancy of the English language is high enough that the amount of information conveyed by every ciphertext component is greater than the rate at which equivocation (i.e., the uncertainty about the plaintext that the cryptanalyst must resolve to cryptanalyze the cipher) is introduced by the running key. In principle, when the equivocation is reduced to zero, the cipher can be solved. The number of symbols needed to reach this point is called the unicity distanceand is only about 25 symbols, on average, for simple substitution ciphers.

In 1918 Gilbert S. Vernam, an engineer for the American Telephone & Telegraph Company (AT&T), introduced the most important key variant to the Vigenre system. At that time all messages transmitted over AT&Ts teleprinter system were encoded in the Baudot Code, a binary code in which a combination of marks and spaces represents a letter, number, or other symbol. Vernam suggested a means of introducing equivocation at the same rate at which it was reduced by redundancy among symbols of the message, thereby safeguarding communications against cryptanalytic attack. He saw that periodicity (as well as frequency information and intersymbol correlation), on which earlier methods of decryption of different Vigenre systems had relied, could be eliminated if a random series of marks and spaces (a running key) were mingled with the message during encryption to produce what is known as a stream or streaming cipher.

There was one serious weakness in Vernams system, however. It required one key symbol for each message symbol, which meant that communicants would have to exchange an impractically large key in advancei.e., they had to securely exchange a key as large as the message they would eventually send. The key itself consisted of a punched paper tape that could be read automatically while symbols were typed at the teletypewriter keyboard and encrypted for transmission. This operation was performed in reverse using a copy of the paper tape at the receiving teletypewriter to decrypt the cipher. Vernam initially believed that a short random key could safely be reused many times, thus justifying the effort to deliver such a large key, but reuse of the key turned out to be vulnerable to attack by methods of the type devised by Kasiski. Vernam offered an alternative solution: a key generated by combining two shorter key tapes of m and n binary digits, or bits, where m and n share no common factor other than 1 (they are relatively prime). A bit stream so computed does not repeat until mn bits of key have been produced. This version of the Vernam cipher system was adopted and employed by the U.S. Army until Major Joseph O. Mauborgne of the Army Signal Corps demonstrated during World War I that a cipher constructed from a key produced by linearly combining two or more short tapes could be decrypted by methods of the sort employed to cryptanalyze running-key ciphers. Mauborgnes work led to the realization that neither the repeating single-key nor the two-tape Vernam-Vigenre cipher system was cryptosecure. Of far greater consequence to modern cryptologyin fact, an idea that remains its cornerstonewas the conclusion drawn by Mauborgne and William F. Friedman that the only type of cryptosystem that is unconditionally secure uses a random onetime key. The proof of this, however, was provided almost 30 years later by another AT&T researcher, Claude Shannon, the father of modern information theory.

In a streaming cipher the key is incoherenti.e., the uncertainty that the cryptanalyst has about each successive key symbol must be no less than the average information content of a message symbol. The dotted curve in the figure indicates that the raw frequency of occurrence pattern is lost when the draft text of this article is encrypted with a random onetime key. The same would be true if digraph or trigraph frequencies were plotted for a sufficiently long ciphertext. In other words, the system is unconditionally secure, not because of any failure on the part of the cryptanalyst to find the right cryptanalytic technique but rather because he is faced with an irresolvable number of choices for the key or plaintext message.

In the discussion of transposition ciphers it was pointed out that by combining two or more simple transpositions, a more secure encryption may result. In the days of manual cryptography this was a useful device for the cryptographer, and in fact double transposition or product ciphers on key word-based rectangular matrices were widely used. There was also some use of a class of product ciphers known as fractionation systems, wherein a substitution was first made from symbols in the plaintext to multiple symbols (usually pairs, in which case the cipher is called a biliteral cipher) in the ciphertext, which was then encrypted by a final transposition, known as superencryption. One of the most famous field ciphers of all time was a fractionation system, the ADFGVX cipher employed by the German army during World War I. This system used a 6 6 matrix to substitution-encrypt the 26 letters and 10 digits into pairs of the symbols A, D, F, G, V, and X. The resulting biliteral cipher was then written into a rectangular array and route encrypted by reading the columns in the order indicated by a key word, as illustrated in the figure.

The great French cryptanalyst Georges J. Painvin succeeded in cryptanalyzing critical ADFGVX ciphers in 1918, with devastating effect for the German army in the battle for Paris.

View post:
Cryptology - Cryptography | Britannica.com