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 .
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.
Key cryptosystems
Single-key cryptography
Single-key cryptography is limited in practice by what is known as the key distribution problem. Since all participants must possess the same secret key, if they are physically separated—as is usually the case—there is the problem of how they get the key in the first place. Diplomatic and military organizations traditionally use couriers to distribute keys for the highest-level communications systems, which are then used to superencrypt and distribute keys for lower-level systems. This is impractical, though, for most business and private needs. In addition, key holders are compelled to trust each other unconditionally to protect the keys in their possession and not to misuse them. Again, while this may be a tolerable condition in diplomatic and military organizations, it is almost never acceptable in the commercial realm.
Another key distribution problem is the sheer number of keys required for flexible, secure communications among even a modest number of users. While only a single key is needed for secure communication between two parties, every potential pair of participants in a larger group needs a unique key. To illustrate this point, consider an organization with only 1,000 users: each individual would need a different private key for each of the other 999 users. Such a system would require 499,500 different keys in all, with each user having to protect 999 keys. The number of different keys increases in proportion to the square of the number of users. Secure distribution for so many keys is simply insolvable, as are the demands on the users for the secure storage of their keys. In other words, symmetric key cryptography is impractical in a network in which all participants are equals in all respects. One “solution” is to create a trusted authority—unconditionally trusted by all users—with whom each user can communicate securely to generate and distribute temporary session keys as needed. Each user then has only to protect one key, while the burden for the protection of all of the keys in the network is shifted to the central authority.
Two-key cryptography
Public-key cryptography
In 1976, in one of the most inspired insights in the history of cryptology, Sun Microsystems, Inc., computer engineer Whitfield Diffie and Stanford University electrical engineer Martin Hellman realized that the key distribution problem could be almost completely solved if a cryptosystem, T (and perhaps an inverse system, T′), could be devised that used two keys and satisfied the following conditions:
- It must be easy for the cryptographer to calculate a matched pair of keys, e (encryption) and d (decryption), for which TeT′d = I. Although not essential, it is desirable that T′dTe = I and that T = T′. Since most of the systems devised to meet points 1–4 satisfy these conditions as well, we will assume they hold hereafter—but that is not necessary.
- The encryption and decryption operation, T, should be (computationally) easy to carry out.
- At least one of the keys must be computationally infeasible for the cryptanalyst to recover even when he knows T, the other key, and arbitrarily many matching plaintext and ciphertext pairs.
- It should not be computationally feasible to recover x given y, where y = Tk(x) for almost all keys k and messages x.
Given such a system, Diffie and Hellman proposed that each user keep his decryption key secret and publish his encryption key in a public directory. Secrecy was not required, either in distributing or in storing this directory of “public” keys. Anyone wishing to communicate privately with a user whose key is in the directory only has to look up the recipient’s public key to encrypt a message that only the intended receiver can decrypt. The total number of keys involved is just twice the number of users, with each user having a key in the public directory and his own secret key, which he must protect in his own self-interest. Obviously, the public directory must be authenticated, otherwise A could be tricked into communicating with C when he thinks he is communicating with B simply by substituting C’s key for B’s in A’s copy of the directory. Since they were focused on the key distribution problem, Diffie and Hellman called their discovery public-key cryptography. This was the first discussion of two-key cryptography in the open literature. However, Admiral Bobby Inman, while director of the U.S. National Security Agency (NSA) from 1977 to 1981, revealed that two-key cryptography had been known to the agency almost a decade earlier, having been discovered by James Ellis, Clifford Cocks, and Malcolm Williamson at the British Government Code Headquarters (GCHQ).
In this system, ciphers created with a secret key can be decrypted by anyone using the corresponding public key—thereby providing a means to identify the originator at the expense of completely giving up secrecy. Ciphers generated using the public key can only be decrypted by users holding the secret key, not by others holding the public key—however, the secret-key holder receives no information concerning the sender. In other words, the system provides secrecy at the expense of completely giving up any capability of authentication. What Diffie and Hellman had done was to separate the secrecy channel from the authentication channel—a striking example of the sum of the parts being greater than the whole. Single-key cryptography is called symmetric for obvious reasons. A cryptosystem satisfying conditions 1–4 above is called asymmetric for equally obvious reasons. There are symmetric cryptosystems in which the encryption and decryption keys are not the same—for example, matrix transforms of the text in which one key is a nonsingular (invertible) matrix and the other its inverse. Even though this is a two-key cryptosystem, since it is easy to calculate the inverse to a non-singular matrix, it does not satisfy condition 3 and is not considered to be asymmetric.
Since in an asymmetric cryptosystem each user has a secrecy channel from every other user to him (using his public key) and an authentication channel from him to all other users (using his secret key), it is possible to achieve both secrecy and authentication using superencryption. Say A wishes to communicate a message in secret to B, but B wants to be sure the message was sent by A. A first encrypts the message with his secret key and then superencrypts the resulting cipher with B’s public key. The resulting outer cipher can only be decrypted by B, thus guaranteeing to A that only B can recover the inner cipher. When B opens the inner cipher using A’s public key he is certain the message came from someone knowing A’s key, presumably A. Simple as it is, this protocol is a paradigm for many contemporary applications.
Cryptographers have constructed several cryptographic schemes of this sort by starting with a “hard” mathematical problem—such as factoring a number that is the product of two very large primes—and attempting to make the cryptanalysis of the scheme be equivalent to solving the hard problem. If this can be done, the cryptosecurity of the scheme will be at least as good as the underlying mathematical problem is hard to solve. This has not been proven for any of the candidate schemes thus far, although it is believed to hold in each instance.
However, a simple and secure proof of identity is possible based on such computational asymmetry. A user first secretly selects two large primes and then openly publishes their product. Although it is easy to compute a modular square root (a number whose square leaves a designated remainder when divided by the product) if the prime factors are known, it is just as hard as factoring (in fact equivalent to factoring) the product if the primes are unknown. A user can therefore prove his identity, i.e., that he knows the original primes, by demonstrating that he can extract modular square roots. The user can be confident that no one can impersonate him since to do so they would have to be able to factor his product. There are some subtleties to the protocol that must be observed, but this illustrates how modern computational cryptography depends on hard problems.
Secret-sharing
To understand public-key cryptography fully, one must first understand the essentials of one of the basic tools in contemporary cryptology: secret-sharing. There is only one way to design systems whose overall reliability must be greater than that of some critical components—as is the case for aircraft, nuclear weapons, and communications systems—and that is by the appropriate use of redundancy so the system can continue to function even though some components fail. The same is true for information-based systems in which the probability of the security functions being realized must be greater than the probability that some of the participants will not cheat. Secret-sharing, which requires a combination of information held by each participant in order to decipher the key, is a means to enforce concurrence of several participants in the expectation that it is less likely that many will cheat than that one will.
The RSA cryptoalgorithm described in the next section is a two-out-of-two secret-sharing scheme in which each key individually provides no information. Other security functions, such as digital notarization or certification of origination or receipt, depend on more complex sharing of information related to a concealed secret.
RSA encryption
The best-known public-key scheme is the Rivest–Shamir–Adleman (RSA) cryptoalgorithm. In this system a user secretly chooses a pair of prime numbers p and q so large that factoring the product n = pq is well beyond projected computing capabilities for the lifetime of the ciphers. At the beginning of the 21st century, U.S. government security standards called for the modulus to be 1,024 bits in size—i.e., p and q each were to be about 155 decimal digits in size, with n roughly a 310-digit number. However, over the following decade, as processor speeds grew and computing techniques became more sophisticated, numbers approaching this size were factored, making it likely that, sooner rather than later, 1,024-bit moduli would no longer be safe, so the U.S. government recommended shifting in 2011 to 2,048-bit moduli.
Having chosen p and q, the user selects an arbitrary integer e less than n and relatively prime to p − 1 and q − 1, that is, so that 1 is the only factor in common between e and the product (p − 1)(q − 1). This assures that there is another number d for which the product ed will leave a remainder of 1 when divided by the least common multiple of p − 1 and q − 1. With knowledge of p and q, the number d can easily be calculated using the Euclidean algorithm. If one does not know p and q, it is equally difficult to find either e or d given the other as to factor n, which is the basis for the cryptosecurity of the RSA algorithm.
We will use the labels d and e to denote the function to which a key is put, but as keys are completely interchangeable, this is only a convenience for exposition. To implement a secrecy channel using the standard two-key version of the RSA cryptosystem, user A would publish e and n in an authenticated public directory but keep d secret. Anyone wishing to send a private message to A would encode it into numbers less than n and then encrypt it using a special formula based on e and n. A can decrypt such a message based on knowing d, but the presumption—and evidence thus far—is that for almost all ciphers no one else can decrypt the message unless he can also factor n.
Similarly, to implement an authentication channel, A would publish d and n and keep e secret. In the simplest use of this channel for identity verification, B can verify that he is in communication with A by looking in the directory to find A’s decryption key d and sending him a message to be encrypted. If he gets back a cipher that decrypts to his challenge message using d to decrypt it, he will know that it was in all probability created by someone knowing e and hence that the other communicant is probably A. Digitally signing a message is a more complex operation and requires a cryptosecure “hashing” function. This is a publicly known function that maps any message into a smaller message—called a digest—in which each bit of the digest is dependent on every bit of the message in such a way that changing even one bit in the message is apt to change, in a cryptosecure way, half of the bits in the digest. By cryptosecure is meant that it is computationally infeasible for anyone to find a message that will produce a preassigned digest and equally hard to find another message with the same digest as a known one. To sign a message—which may not even need to be kept secret—A encrypts the digest with the secret e, which he appends to the message. Anyone can then decrypt the message using the public key d to recover the digest, which he can also compute independently from the message. If the two agree, he must conclude that A originated the cipher, since only A knew e and hence could have encrypted the message.
Thus far, all proposed two-key cryptosystems exact a very high price for the separation of the privacy or secrecy channel from the authentication or signature channel. The greatly increased amount of computation involved in the asymmetric encryption/decryption process significantly cuts the channel capacity (bits per second of message information communicated). As a result, the main application of two-key cryptography is in hybrid systems. In such a system a two-key algorithm is used for authentication and digital signatures or to exchange a randomly generated session key to be used with a single-key algorithm at high speed for the main communication. At the end of the session this key is discarded.
Block and stream ciphers
In general, cipher systems transform fixed-size pieces of plaintext into ciphertext. In older manual systems these pieces were usually single letters or characters—or occasionally, as in the Playfair cipher, digraphs, since this was as large a unit as could feasibly be encrypted and decrypted by hand. Systems that operated on trigrams or larger groups of letters were proposed and understood to be potentially more secure, but they were never implemented because of the difficulty in manual encryption and decryption. In modern single-key cryptography the units of information are often as large as 64 bits, or about 131/2 alphabetic characters, whereas two-key cryptography based on the RSA algorithm appears to have settled on 1,024 to 2,048 bits, or between 310 and 620 alphabetic characters, as the unit of encryption.
A block cipher breaks the plaintext into blocks of the same size for encryption using a common key: the block size for a Playfair cipher is two letters, and for the DES (described in the section History of cryptology: The Data Encryption Standard and the Advanced Encryption Standard) used in electronic codebook mode it is 64 bits of binary-encoded plaintext. Although a block could consist of a single symbol, normally it is larger.
A stream cipher also breaks the plaintext into units, normally of a single character, and then encrypts the ith unit of the plaintext with the ith unit of a key stream. Vernam encryption with a onetime key is an example of such a system, as are rotor cipher machines and the DES used in the output feedback mode (in which the ciphertext from one encryption is fed back in as the plaintext for the next encryption) to generate a key stream. Stream ciphers depend on the receiver’s using precisely the same part of the key stream to decrypt the cipher that was employed to encrypt the plaintext. They thus require that the transmitter’s and receiver’s key-stream generators be synchronized. This means that they must be synchronized initially and stay in sync thereafter, or else the cipher will be decrypted into a garbled form until synchrony can be reestablished. This latter property of self-synchronizing cipher systems results in what is known as error propagation, an important parameter in any stream-cipher system.
