Public Key Cryptography (Jan, 1983)
Public Key Cryptography
An introduction to a powerful cryptographic system for use on microcomputers.
21505 Evalyn Ave.
Torrance, CA 90503
Cryptography, the art of concealing the meaning of messages, has been practiced for at least 3000 years. In the past few centuries, it has become an indispensable tool in the military affairs, diplomacy, and commerce of most major nations. During that time there have been many innovations, and cryptography has changed and grown to accommodate the increasingly complex needs of its users. Present techniques are very sophisticated and provide excellent message protection. Current developments in computer technology and information theory, however, are on the verge of revolutionizing cryptography. New kinds of cryptographic systems are emerging that have incredible properties, which appear to eliminate completely some problems that have plagued cryptography users for centuries. One of these new systems is public key cryptography.
In public key systems, as in most forms of cryptography, a piece of information called a key is used to transform a message into cryptic form. In conventional cryptography this key must be kept secret, for it can also be used to decrypt the message. In public key cryptography, however, a message remains secure even if its encryption key is publicly revealed. This unique feature gives public key systems great advantages over conventional systems.
This article deals with the theory and application of public key cryptography. It reviews the methods and problems of traditional cryptography and describes the remarkable concept and advantages of public keys. It also describes a real public key cryptosystem, showing examples of the encryption and decryption operations; and it attempts to clarify the concept of trap-door one-way functions, upon which public key systems are based.
Computers are essential for implementing many modern cryptosystems, including the one described here. Several BASIC-language programs (TRS-80) are included to illustrate algorithms used in this system. These can be used to experiment with the encryption, decryption, and derivation of small keys.
A cryptosystem must have two methods for transforming messages: a method of encryption, which renders messages unintelligible; and a method of decryption, for restoring them to their original forms. For simplicity, normal message text shall be called plaintext, and the encrypted form, ciphertext. Ciphertext messages may also be called cryptograms, or may just be called messages when it is clear that the encrypted form is meant.
To appreciate the significance of a public key system, we need to know some of the methods and problems of conventional cryptosystems. In a conventional system (see figure 1), a plaintext message is converted to a cryptogram by an encryptor and sent over a communication channel. While in transit, the cryptogram may be intercepted by someone other than the intended recipient. If it is encrypted well, it will be meaningless to the interceptor. At the receiving end, the cryptogram is converted back into plaintext by a decryptor. The encryptor and decryptor may be procedures executed by people or computers or may be specially constructed devices. In any case, they are both supplied with keys from a key source.
Cryptographic keys are analogous to the house and car keys we carry in our daily lives and serve a similar purpose. In many modern systems, each key is a string of digits. For example, keys defined by the Data Encryption Standard of the National Bureau of Standards consist of 64 binary digits, 56 of which are significant. To encrypt a message, a key and the message are somehow inserted into an encryptor, and the cryptogram that emerges is a jumble of characters that depends on both the message and the key. To decrypt the message, the correct key and the cryptogram are inserted into a decryptor, and the plaintext message emerges. In conventional systems, the correct key for decrypting a message is the same one used to encrypt it. Obviously, the keys used must be closely guarded secrets.
In a good system the number of possible keys should be very large, and decryption of any cryptogram should be possible with only very few of the keys, often with only one. These conditions make it impractical to try decrypting a message with one key after another until the one that reveals plaintext is found. The Data Encryption Standard provides more than 7 X 1016 keys (a 7 followed by 16 zeros), and there is some controversy over whether this number is sufficient!
The keys to be used are obtained from a key source, which selects them, perhaps randomly, from the large set of all usable keys. The key source may be located near the encryptor, near the decryptor, or elsewhere. But each key to be used must be made available to both the encryptor and the decryptor. Therein lies the most serious problem of conventional cryptosystems: some safe method must exist for distributing secret keys to the encryptor and the decryptor.
This problem is illustrated with a simple example: let’s say you want to communicate privately with a friend named Mary. Many communication channels are available to you, none of which may be completely private: telephone, mail, and computer networks, for examples. You could send encrypted messages, but Mary could not read them without the keys. And you dare not send secret keys over these public channels. One of you must visit the other, so that you could agree on a key to use for future correspondence. But if your communication need was for only one private message exchange, it could be transacted during the visit, rendering the conventional cryptosystem unnecessary. Or if your communication need were immediate, a personal visit could cause an unacceptable delay. And if you need to communicate with several people, all the necessary visits could entail considerable expense.
Most conventional cryptosystems, including the Data Encryption Standard system, have this problem. Public key cryptosystems, however, can avoid this problem entirely.
Public Key Systems.
The concept of public keys may be one of the most significant cryptographic ideas of all time. A public key system has two kinds of keys: encryption keys and decryption keys. It may seem that having two kinds would make the key distribution problem worse, or at least no better. These keys, however, have remarkable, almost magical, properties:
• for each encryption key there is a decryption key, which is not the same as the encryption key
• it is feasible to compute a pair of keys, consisting of an encryption key and a corresponding decryption key
• it is not feasible to compute the decryption key from knowledge of the encryption key
Because of these properties, Mary and you can use a public key system to communicate privately without transmitting any secret keys. To set it up, you generate a pair of keys, and send the encryption key to Mary by any convenient means. It need not be kept secret. It can only encrypt messages—not decrypt them. Revealing it discloses nothing useful about the decryption key. Mary can use it to encrypt messages and send them to you. No one but you, however, can decrypt the messages (not even Mary!), as long as you do not reveal the decryption key. Figure 2 illustrates the flow of information in this situation, with Mary on the left and you on the right. To allow you to send private messages to her, Mary must similarly create a pair of keys, and send her encryption key to you. You can also go a step further. Since your encryption key need not be kept secret, you can make it public, for example, by placing it in a computer network public file. Once you have done so, anyone who wants to send you a private message can look up your public key and use it to encrypt a message. Since you need not transmit the decryption key, and since it cannot be computed from your public key, the message is secure. Only you can decrypt it. Other people can place their encryption keys in the same public file, which would thus become a directory of public keys. Any two people with directory entries could then communicate privately, even if they had no previous contact. It would be necessary, however, to protect the keys in such a file so that no one could change someone else’s encryption key, for example, by substituting another encryption key. Fortunately, there is a way to protect the keys themselves with a public key cryptosystem, but that is another topic.
The RSA Cryptosystem.
Now that the general concepts of public key cryptography have been examined, the next problem is how to design an actual working system. Indeed, when Whitfield Diffie and Martin Hellman conceived the basic properties of this cryptosystem in 1976, no one knew how to make a system that could employ them. The situation was similar to that of space travel in 1950. It was conceivable, but no one had accomplished it. In 1977, three researchers at the Massachusetts Institute of Technology, Ron Rivest, Adi Shamir, and Len Adleman, published an elegant method for creating and using public keys.
In the Rivest-Shamir-Adleman (or RSA) cryptosystem, the keys are 200-digit numbers. The encryption key is the product of two secret prime numbers, having approximately 100 digits each, selected by the person creating the keys. The corresponding decryption key is computed from the same two prime numbers, using a nonsecret formula.
Anyone who knows the secret prime numbers can compute the decryption key, but the primes are hidden because only their product, the encryption key, is revealed. Of course, the primes may be discovered by factoring the key, but factoring such a number is about as easy as traveling to Alpha Centauri, especially if the person who constructs the number has done it in a way that discourages factoring. Rivest, Shamir, and Adleman estimated that a fast computer would require 3.8 billion years (nearly the estimated age of the earth) to factor a 200-digit key. Estimates of the time required to factor keys of several other lengths are shown in table 1.
Before encryption, a message is converted into a string of numbers. This step is common in cryptosystems, as it is in computers and communication systems. Next, the message is subdivided into blocks, much as computer text files are subdivided into records or sectors. Each block contains the same number of digits, and is treated as one large number during encryption. To encrypt the message, an arithmetic operation involving the encryption key is performed on each block, resulting in a cryptogram containing as many blocks as the original message. The arithmetic operation, described below, is the same for all blocks. To decrypt, the inverse arithmetic operation, which requires the decryption key, is performed on each block of the cryptogram. The result is the original message in its numerical form.
As you can imagine, it would be cumbersome to illustrate these operations with 200-digit numbers, so the detailed descriptions below use small keys and messages; otherwise, the operations shown are the same as those used in a full-size RSA system. Also, the encryption method described here is actually a subset of the original RSA method. This modification, which is due to Donald Knuth (see reference 3), uses the basic RSA technique, while lessening somewhat the number of computations involved. (For more detailed information, the reader should refer to the original Rivest-Shamir-Adleman paper, shown as reference 5.)
How to Encrypt.
While the encryption and decryption operations are normally performed by a computer program, I will describe them as if you were performing them by hand. Normally, the only manual operation required is entering the message to be encrypted.
Suppose you wish to encrypt the message
MARY HAD A LITTLE LAMB.
Once entered into a computer, the message will be in numerical form, frequently in ASCII (American Standard Code for Information Interchange). In ASCII, this message is
77 65 82 89 32 72 65 68 32
65 32 76 73 84 84 76 69 32 76 65 77 66 46
This is not yet encrypted, of course. It is merely written as a computer might represent it (all the numbers in this article are decimal). Group the message into blocks with six digits each:
776582 893272 656832 653276 738484 766932 766577 664600
Each block except the last consists of three consecutive characters from the ASCII representation above. The last block consists of the last two characters plus two zeros added at the right to make the final block as long as the rest. Digits added for this purpose may have any value.
Suppose that the encryption key, usually called n, is 94815109. This is the product of two prime numbers. To encrypt the message, treat each block as a number, and cube it modulo n (see the text box “Arithmetic with a Modulus”). For example, to encrypt the first block of the message:
(776582 X 776582 X 776582) mod 94815109 = 71611947
Performing the cubing operation on all eight blocks produces the cryptogram
71611947 48484364 03944704 03741778 61544362 35331577 88278091 50439554
Arithmetic modulo n is a fundamental part of the RSA system. It is also used in decryption and creating keys. Most of us have used arithmetic modulo n, although perhaps we didn’t call it that. For instance, arithmetic modulo 12 is frequently used in calculations related to keeping time. The text box “Arithmetic with a Modulus” reviews the mechanics.
Almost any method may be used to convert the text to numbers. It would have worked just as well to use A = l, B=2, . . . Z = 26, but the ASCII code is already in wide use, and it includes numbers for spaces and punctuation. The block length should be almost equal to the key length, because making it long minimizes the number of blocks per message. When considered as a number, however, no block should be as large as the key. For the above key, no block should be larger than 94815108. Making the block length slightly less than the key length ensures that this requirement is met. Of course, with full-length keys, there will be about 100 characters per block.
Listing 1 is a BASIC program that uses the above key to encrypt a line of text. Two lines of the program (670 and 680) perform the encryption. The rest deal with input, formatting, and printing. If desired, the encryption key in line 220 may be changed; use a key with seven or eight digits, or reduce the number of characters per block (line 210).
The programs in listings 1 through 4 were written for the TRS-80 BASIC interpreter, which is capable of 16-digit precision. They may be adapted for use with other interpreters, and I have tried to structure and annotate them well enough to make them easy to modify.
How to Decrypt.
Since the RSA system is a public key system, the decryption key, usually called d, differs from the public encryption key. For the above encryption key, d is 63196467. Knowing the value of d, you can decrypt the message by raising each cryptogram block to the power d, modulo n. That is, if a cryptogram block is C, you must compute (C) mod n. For example, to decrypt the first block of the above cryptogram:
(71611947^63196467) mod 94815109 = 776582
converts this block back to the first three ASCII codes of the original message. Each of the remaining blocks is decrypted in the same way. Fortunately, raising a number to a large power does not require performing a comparable number of multiplications. One efficient algorithm is a variation of the “Russian Peasant Method” of multiplication (see reference 4). It computes M = (C^d) mod n, as follows:
1. Let M = 1.
2. If d is odd, let M = (MXC) mod n.
3. Let C = (CXC) mod n.
4. Let d = integer part of d/2.
5. If d is not zero, repeat from step 2; otherwise, terminate with M as the answer.
To raise a number to the power 63196467, this algorithm executes its loop (steps 2 through 5) 26 times. It is employed as a subroutine in the BASIC-language decryption program of listing 2. Line 200 contains the keys, which may be changed, if desired. Lines 340 through 380 execute the algorithm.
How to Derive Keys.
Earlier, I said that it is feasible to derive a pair of keys, n and d, for encryption and decryption, but not feasible to calculate d from n. That seems incredible, but experts believe it is true when n and d are constructed in the following way.
The encryption key, n, is the product of two large prime numbers, p and q:
n = pq (1)
The decryption key, d, is calculated from p and q by
d = [ 2(p-l)(q-l) + 1 ]/3 (2)
Although n is made public, p and q remain secret. If n is sufficiently large, say 200 digits, it is practically impossible for anyone to factor it and discover the values of p and q; and without knowing p and q, it is equally difficult to compute d.
For the encryption and decryption examples given earlier, the keys were constructed as follows:
prime number, p = 7151 prime number, q = 13259 encryption key, n = 7151X13259
= 94815109 decryption key, d = (2X7150X 13258 + l)/3
Because p and q may have 100 or more digits in an operational RSA system, their selection requires computer assistance. The following three restrictions apply to how they should be chosen. First, neither p — 1 nor q — 1 must be divisible by 3, or the decryption operation will not work correctly. Second, p — 1 and q — 1 should both contain at least one large prime factor. Third, the ratio p/q should not approximate a simple fraction, e.g., 2/3, 3/4, etc., etc. These last two restrictions help ensure that n will be difficult to factor. Donald Knuth, in the second edition of his book (see reference 3), gives a detailed procedure for selecting p and q, which ensures that these restrictions are met. While the procedure described is for constructing 250-digit keys, it is applicable to other key lengths.
Enough keys are available for everyone. The number of 250-digit keys constructible with Knuth’s procedure is much greater than 10^200. For comparison, the number of atoms in the known universe is about 10^80.
To create a different pair of seven-or eight-digit keys, find primes p and q such that neither p — 1 nor q— 1 is divisible by 3, and the product n=pq is a seven- or eight-digit number. Then calculate d from formula (2). Divisibility by 3 is easily checked by casting out 3s, and the BASIC programs described below are helpful in finding prime numbers.
How to Find Large Prime Numbers.
To find a large prime number, select a random odd number of the required size and determine whether it is prime. If it is not, increase it (or decrease it) by 2 and try again, repeating until finding a prime. It is not necessary, however, to attempt to factor a number to determine whether it is prime.
To test whether a number n is prime, select any number greater than 1 and smaller than n, say x, and calculate
y = (x^n-1) mod n
If y is not equal to 1, n is not prime. But if y = 1, n may be prime, and further testing is required. Repeat the test using another value of x. If this test is performed with many different values of x, and if y = 1 for all the test cases, n is probably prime. Listing 3 is a BASIC program that uses 10 values of x to test a number for primality. If the program says the number is not prime, it is not prime. But if the program says the number is probably prime, there is a small chance that it is not.
What is the probability that this program will make an error? I don’t know, but it illustrates a class of programs, some of which are very good. Knuth (reference 3, page 375) presents one that is slightly more complicated, for which the odds against an error are a million to one when 10 values of x are used for testing, and are a million million to one when 20 values are used. For serious work I would use the more complicated program, but the one presented here illustrates the process of testing without factoring—and it doesn’t seem bad. It has not made an error in several hundred trials.
Listing 4 is a BASIC program that searches for a prime number using the same test method as the previous program. The program will begin with the number you enter and search downward until it finds a probable prime, which it will identify. If you enter 99999999, it will find the largest eight-digit prime. This program helps to find primes for constructing small keys like the ones above.
One-Way Functions and Trap-Doors.
Public key cryptosystems derive their unusual properties from mathematical functions called trap-door one-way functions, which are useful because they can act as ordinary functions or as one-way functions.
One-way functions are like oneway streets. The ordinary cube function, B = A3, resembles a one-way function in that it is easier to calculate B, given A, than it is to calculate A, given B. The latter calculation, the cube-root function, is called the inverse of the cube function. The inverse of an automobile would convert smog to gasoline. A mathematical function is said to be one-way if it is much more difficult to compute the inverse than to compute the function itself. To qualify as a one-way function, the inverse must be very difficult to compute, even by machine.
A function that could be computed in a few seconds, for which computing an inverse required thousands of years, would fit the definition.
To create a public key cryptosystem, a trap-door one-way function is used. It is easy to compute an inverse of a trap-door one-way function, but it can be very difficult to determine how. Computing an inverse can take millions of years because finding out how to do it can take that long. If the method is known, computing an inverse may take only a few seconds. This is a completely different situation than that created by a one-way function, for which there is no easy way to compute an inverse. When a trap-door one-way function is being constructed, the person constructing it has access to information, called trap-door information, that reveals how to compute inverses. Once the function is constructed, the trap-door information is hidden so well that it can take millions of years to find.
The Knuth modification of the RSA system encryption function, cubing a number modulo n, is a trapdoor one-way function. Its inverse function is the cube root modulo n. In arithmetic modulo n, “cube root” is defined as in ordinary arithmetic: if B is the cube of A, then A is the cube root of B. Notice that this definition does not say how to compute cube roots (in either kind of arithmetic). If you know how to compute cube roots modulo n, you know how to decrypt messages. In modulo n arithmetic, the cube root of B is computed by raising B to some power d, modulo n. But knowing this doesn’t help unless you know the value of d. And d can be computed by formula (2) if n has two factors (p and q), and p — 1 and q — 1 are not divisible by 3. If you construct the modulus, n, you know p and q, and can therefore calculate the value of d. Knowing d, you can compute cube roots; in other words, decrypt cryptograms. The values of p and q are hidden from other people by the difficulty of factoring n. They are deprived of the value of d, and therefore cannot compute cube roots. Hence, they cannot decrypt cryptograms created by cubing modulo n. In the RSA system, the value of d is the trap-door information that reveals how to compute inverses (cube roots). You might think of p and q as comprising a trap-door through which the value of d is obtained. Factoring n is analogous to finding the trap-door, but it is very difficult to do.
Other trap-door one-way functions undoubtedly exist, and these could be the foundations for other public key cryptosystems. For each of these systems, the same principles would apply. The creator of the system parameters would have access to certain trap-door information, which would reveal how to compute inverses. For everyone else, the trapdoor would be hidden, and for them the encryption function would be, in effect, a one-way function.
Is the RSA System Unbreakable?.
Successfully analyzing a cryptosystem, and being able to read its cryptograms without authorization, is called breaking the system. Theoretically, the RSA system can be broken by a determined analyst. Factoring the encryption key, or modulus, would do the trick, for then the decryption key could be easily calculated from formula (2), after which any message could easily be decrypted. However, factoring a key of the recommended length and construction does not seem feasible. Knuth gives a procedure for constructing a 250-digit key and considers it inconceivable at this time that such a key could be factored. Experts acknowledge that a breakthrough in the art of factoring large numbers would render the RSA system worthless but consider such a breakthrough extremely unlikely. Apparently, factoring large numbers is not a new problem, but one that expert mathematicians have attacked for centuries, and it is known to be very difficult.
Another way to break the system is to determine the value of d without factoring n. Although you can approach this problem in several ways, experts believe that none of them are likely to be fruitful.
Yet another method of breaking the system is to learn how to compute cube roots modulo n without knowing the value of d. Less seems to be known about the difficulty of doing this than is known about the difficulty of factoring n. At this time, no one knows how to compute such cube roots in a reasonable time without knowing d.
Any new cryptosystem should be viewed with suspicion. The accepted method of demonstrating the adequacy of a new system is to subject it to prolonged, concerted attack by people with experience in breaking other systems. If the new system proves resistant to such an attack, it may tentatively be considered secure. The process of validation is continuing, but a fairly large number of preliminary studies done so far indicate that the system is quite secure.
Very closely related to public key cryptography is the concept of digital signatures. One problem with corresponding electronically, such as via a computer network, is that messages can be easily forged—you usually cannot be certain that the sender of a received message is actually the person claimed in the message. A public key cryptosystem, however, can be used to provide positive identification of any sender who has a public key on record. If, for example, Mary has filed a public key in some public access file, she can digitally sign a message to you by decrypting it with her private key before transmitting it. After receiving the message, you (or anyone else) can read the message by encrypting it with Mary’s public encryption key. The process is essentially the reverse of the cryptosystem: the message is first decrypted and then encrypted, and anyone can reveal the message, but only Mary with her secret decryption key can create it.
In addition, messages using digital signatures can be subsequently encrypted with another key. After Mary decrypts her message to you with her secret decryption key, she can then encrypt it with your public encryption key. The result is a message that only Mary could have created, and only you can read!
Messages with digital signatures have other interesting and useful properties and may be used to advantage with other (non-PKC) cryptosystems. These properties and applications might easily justify an article on digital signatures alone.
This article has described the principles of public key cryptosystems. One example has been given, the Rivest-Shamir-Adleman system. We have seen how keys are constructed and used, and have at our disposal four BASIC programs for further experimentation. These programs may also be useful as models for assembly-language programs that could manipulate larger numbers and run faster. We have seen that the RSA cryptosystem provides public keys in more than astronomical quantities and that it is believed to be unbreakable.
Several questions come to mind: Is a personal computer powerful enough to run a full-size RSA system? How long would a small computer take to construct a 200-digit key? Or even a 100-digit key? How long would it take to decrypt a medium-length message?
Regardless of the answers to these questions, the prospects are good for using public key systems with small computers. New computer models appear almost monthly, and their performance is improving rapidly. The theoretical work that gave birth to the RSA system is also proceeding at a rapid pace, and we can expect new and different public key systems to result from that work. Some of these may be suitable, perhaps even optimized, for small machines, and the prospects are exciting.