Bruce has an MS in computer science and has worked in cryptography and data security for a number of public and private concerns. He can be reached at Counterpane Systems, 730 Fair Oaks Ave., Oak Park, IL 60302.
Complex systems have been used throughout history to protect secret messages from prying eyes. From Roman times to today, these systems have been based on some sort of cryptographic algorithm and a key. People with the key can use the algorithm to encrypt messages into some unintelligible garble, then to decrypt that garble back into the message. People without the key can only read garble. The sophistication of the algorithm has increased over the years, particularly with the invention of computers, but the basic idea remains unchanged. The algorithm is like a safe. Someone opens the safe with a key, puts a message in, and slams the door shut. Only someone else with a key can open the safe and read the message.
Whit Diffie and Martin Hellman changed all this in 1976 in a paper entitled "New Directions in Cryptography" where they described Public-Key Cryptography (PKC). Instead of one key, PKC has two keys, one public and the other private. Moreover, it is impossible to deduce the private key from the public key. A person with the public key can encrypt a message but not decrypt it--only someone with the private key can decrypt the message. It's as if someone welded a mail slot onto the cryptographic safe. Anyone can slip messages into the slot, but only someone with the private key can open the safe and read the messages.
PKC algorithms are complicated protocols, not ideally suited to encrypt long messages. A common implementation is to use PKC to transfer the key for another cryptographic algorithm and then use that algorithm to encrypt and decrypt messages. The Digital Encryption Standard (DES) algorithm is ideal for this sort of application. For example, if Alice and Bob want to exchange data securely, they first agree to set up a DES system, Alice then generates a random DES key, encrypts it using Bob's public key, and sends it to him. Bob could send her his public key directly, or if this were a large network his key might be posted on some central bulletin board. Bob then decrypts Alice's message using his private key, and then both of them encrypt their communications using DES with the same key.
How does PKC address the problem of key distribution and key management? Well, if Alice and Bob want to set up a secure communications channel using DES, they both need the same key. Alice could choose one at random, but she still has to get it to Bob. She could hand it to him sometime beforehand, but that requires foresight. She could send it to him via registered mail, but that takes time and is no real guarantee of security. With PKC, there is no problem. Without prior arrangements, they can both have the same DES key, and no adversary listening in on the communications channel has anything except a public key, an encrypted DES key, and a day's worth of DES-encrypted traffic.
PKC has implications far beyond simple data encryption. It allows people to do things securely over computer networks that are impossible any other way. In this section, I'll discuss applications such as password protection, digital signatures, and simultaneous contract signing. Other applications might include fair coin tosses, mental poker, and bit commitment.
Password Protection. Conventional password protection schemes, where the host computer stores the password in encrypted form, have serious security problems. For one, when the user types his password into the system, anyone who has access to his data path can read it. He might be accessing his computer through a convoluted transmission path that passes through four industrial competitors, three foreign countries, and two forward-thinking universities, any one of which can look at his login sequence as it passes through its machine. Two, anyone with access to the processor memory of the system can see the password before the system encrypts and compare it with the encrypted password in the password file.
PKC solves the problem by allowing the host computer to keep a file of every user's public key; each user keeps his own private key. This private key is both long and nonmnemonic, and will probably be processed automatically by the user's hardware or communications software. This requires an intelligent and "trusted" terminal, but neither the host nor the communications path needs to be secure. When logging in, the host sends the user some random string. The user encrypts the string with his private key and sends it back to the host. The host then decrypts the message using the user's public key. If the decrypted string matches what the host sent the user in the first place, the computer allows the user access to the system. No one else has access to the user's private key, so no one else can impersonate the user. And more importantly, the user never sends his private key over the transmission line to the host. No one listening in on the interaction can get any information that would enable him to deduce the private key and impersonate the user.
Digital Signatures. One of the properties of PKC is that either key can be used for encryption. Encrypt a document using your private key, and you have a secure digital signature. Anyone with the public key can decrypt the document, so anyone can read it. Only you have access to your private key, so no one else could have signed it. And finally, any modification to the encrypted document will produce gibberish when decrypted, so no one can modify the signed document. In reality, the problem with this protocol is that it will take a lot of time to generate a PKC digital signature on an entire document. It is easier to hash the document using a one-way hash function (MD5, as described in the September 1991 DDJ, for example), producing a small fingerprint, and then sign the fingerprint with a private key.
Improved Key Exchange. Implementing digital signatures during a DES-key exchange protocol circumvents a potential security problem. What if an adversary sits in the middle of the communications channel and sends data to and receives data from both Alice and Bob? He could pretend to be Alice and send Bob a different DES key. Bob's public key is public, so he would have no trouble getting it. Bob, who would be fooled, would complete the protocol and then encrypt all of his data using this different key and then send it back to "Alice." The adversary would then be able to read all of the data Bob sent. And then on the other end, the adversary could send Alice a different public key in which to encrypt the DES key. Alice, who would also be fooled, would encrypt the DES key such that the adversary could read it. Now the adversary could read all of Alice's data as well. If the adversary were fast enough, he could decrypt Bob's data and then reencrypt it for Alice, and then decrypt Alice's data and then reencrypt it for Bob. The two of them would have no idea that someone sitting between them was reading all of their supposedly secure data.
With digital signatures, a central trusted authority can sign both Alice's and Bob's public keys. The signed keys would include a signed certification of who they belonged to. Now both know that the public key they received over the communications link (or downloaded from a central BBS) actually belongs to the other person. The DES key exchange can then proceed. Finally, to ensure that Alice and Bob are not impostors, both Alice and Bob initiate the challenge and reply protocol in the password protection example. If both protocols are successfully completed, each knows that the person they are communicating with is actually the other person.
Fair Coin Tosses. Using PKC, Alice and Bob can flip a coin over some communications media, even if they don't trust each other; see Figure 1. The protocol, which assumes that the PKC algorithm commutes, is as follows:
1. Alice and Bob both generate a public/private key pair.
2. Alice generates two messages, one indicating heads and the other indicating tails. These messages should contain some unique random string, so that she can verify their authenticity later on in the protocol. Alice encrypts both messages with her public key and sends them to Bob.
3. Bob, who cannot read either message, chooses one at random. He encrypts it with his public key and sends it back to Alice.
4. Alice, who can not read the message sent back to her, decrypts it with her private key and then sends it back to Bob.
5. Bob decrypts the message with his private key to reveal the results of the coin toss. He sends the decrypted message to Alice.
6. Alice reads the result of the coin toss and verifies that the random string is correct.
7. Both Alice and Bob reveal the public and private keys so that both can verify that the other did not cheat.
Figure 1: Fair coin tosses using PKC
This protocol is self-enforcing. Either party can immediately detect cheating on the part of the other party, and no trusted third-party is required to participate in either the actual protocol or any adjudication after the protocol has been completed. To see how this works, let's try to cheat.
If Alice wanted to cheat and force heads, she has three potential ways of affecting the outcome. One, she could encrypt two "heads" messages in step #2. Bob would discover this when Alice revealed her key pair at step #7. Two, she could incorrectly decrypt the message in step #4. However, she could not figure out how to decrypt the message to force another message, only gibberish. Bob would discover this in step #5. Three, she could lie about the validity of the message in step #6. Bob would discover this also in step #7, when Alice could not prove that the message was not valid. Of course, Alice could refuse to participate in the protocol at any step, at which point Alice's attempted deception would be immediately obvious to Bob.
If Bob wanted to cheat and force tails, his options are just as poor. He could incorrectly encrypt a message at step #3, but Alice would discover this when she looked at the final message at step #6. He could improperly perform step #5, but this would also result in gibberish, which Alice would discover at step #6. He could claim that he could not properly perform step #5 because of some cheating on the part of Alice, but this form of cheating would be discovered at step #7. Finally, he could send a tails message to Alice at step #5 regardless of the message he decrypted, but Alice would immediately be able to check the message for authenticity at step #6.
Mental Poker. A similar protocol allows Alice and Bob to play poker with each other. Instead of Alice making and encrypting two messages. one for heads and one for tails, she makes 52 messages, one for each card in the deck. Bob chooses five messages at random, encrypts them with his public key, and then sends them back to Alice. Alice decrypts the messages and sends them back to Bob, who decrypts them to determine his hand. He then sends five more messages to Alice, who decrypts them to determine her hand. During the game, additional cards can be dealt to either player by repeating the same procedure. At the end of the game. Alice and Bob both reveal their key pairs so that both can be assured that the other did not cheat.
Bit Commitment. Let's say Alice wants to commit to a prediction, but does not want to reveal that prediction to Bob until sometime later. Bob, on the other hand, wants to make sure that Alice cannot change her mind after she has committed to her prediction. Magicians like to use sealed envelopes handed to random members of the audience, but PKC can provide a method immune from any sleight of hand. First, both Alice and Bob each generate some random bit strings. Bob hands Alice his string. Alice creates a message consisting of her random string, the bit (or number of bits) she wishes to commit to, and Bob's random string. She then encrypts it with her public key and sends the result back to Bob. Bob cannot decrypt the message, so he does not know what the bit is. If the message did not contain Alice's random string, he would be able to encrypt all possible messages with Alice's public key and compare them with what Alice handed him. Alice's secret random string prevents him from using this attack to determine her bit. When it comes time for Alice to reveal her bit, she decrypts it using her private key. Bob then ensures himself that the bit is valid by checking that his random string is accurate. If the message did not contain Bob's random string, Alice could secretly decrypt the message she handed Bob with a variety of keys until she found one that gave her a bit other than the one she committed to. Bob's random string prevents her from using this trick to change her mind.
Oblivious Transfer. Imagine a situation in which Alice sends Bob two messages. Bob has a 50 percent chance of receiving either one message or the other (but not both), and Alice has no way of knowing which message he received. This may not sound very useful at first glance, but bear with me for a moment. First, the protocol:
1. Alice generates two public-key key pairs, or four keys in all. She sends both public keys to Bob.
2. Bob chooses a key in a conventional cryptographic algorithm (DES, for example). He picks one of Alice's public keys at random and encrypts his DES key with it. He sends the encrypted key to Alice without telling her which of her public keys he used to encrypt it.
3. Alice decrypts Bob's key with both of her private keys. In one of the cases, she uses the correct key and successfully decrypts Bob's DES key. In the other case, she uses the wrong key and only manages to generate a meaningless pile of bits that nonetheless looks like a random DES key. She has no idea which is which.
4. Alice encrypts one message with each of the DES keys she generated in the previous step (one real and one meaningless) and sends them to Bob.
5. Bob attempts to decrypt both of Alice's messages, but successfully decrypts only one of them. At this point the oblivious transfer is complete. Bob has received one of the two messages (the one encrypted in his DES key), and Alice has no way of knowing which.
6. After the protocol is complete and the results of the transfer can be made public, Alice must give Bob her private keys so that he can verify that she did not cheat. After all, she could have encrypted the same message with both keys in step #4.
The protocol is secure against an attack by Alice because she has no way of knowing which of the two DES keys is the real one. It is secure against an attack by Bob because there is no way he can get Alice's private keys to determine the DES key with which the other message was encrypted. This may still seem like nothing more than a more complicated way to flip coins over a modem, but it has some far reaching implications when used in more complicated protocols.
Simultaneous Contract Signing. Alice and Bob want to enter into a contract. They've agreed on the wording, but neither wishes to sign without making sure the other signs as well. This would be no problem face to face, but doing the same thing over a communications channel requires an intricate protocol:
1. Alice and Bob both randomly select 100 pairs of DES keys. There is nothing special about the pairs; they are just grouped in sets of two for the protocol.
2. Alice and Bob both generate a pair of messages. "This is the left half of my signature" and "This is the right half of my signature," for example. The messages will probably also include a digital signature of the contract, as defined previously, and a time stamp. The contract is considered signed if the other party can produce both halves of this signature pair.
3. Alice and Bob both encrypt their message pairs in each of the DES key pairs, the left message with the left key in the pair and the right message with the right key in the pair.
4. Alice and Bob send each other their pile of 200 encrypted messages, making sure the other knows which messages are which halves of which pairs.
5. Alice and Bob send each other every key pair using the oblivious transfer protocol. That is, Alice sends Bob either the left key or the right key of each of the 100 pairs, and Bob does the same. Now both Alice and Bob have the encrypted half of each signature pair, but neither he nor she knows which halves the other one has.
6. Alice and Bob both decrypt the halves they can, and make sure that the decrypted messages are valid.
7. Alice and Bob each send each other the first bits of all 200 DES keys.
8. Alice and Bob repeat step #7 for the second bits of all 200 DES keys, then for the third bits, and so on until all the bits of all the DES keys have been transferred.
9. Alice and Bob decrypt the remaining halves of the message pairs and the contract is signed.
Why does all this work? Let's assume Alice wants to cheat and see what happens. In steps #4 and #5, Alice could disrupt the protocol by sending Bob nonsense bit strings. Bob would catch this in step #7, when he tried to decrypt whatever half he received. Bob could then stop safely, because Alice could not decrypt the encrypted halves that Bob sent her. If Alice were very clever, she could disrupt only half the protocol. She could send the left half of each pair correctly, but send a gibberish string for the right half. Bob has only a 50 percent chance of receiving the right half, so half the time she could get away with it. However, this only works if there is one key pair. If there were only two pairs, she could get away with this sort of deception 25 percent of the time. That is why there are 100 key pairs in this protocol. Alice has to correctly guess the outcome of 100 oblivious transfer protocols. She only has a 1 in 2100 chance of doing this, so Bob can safely assume that if he didn't catch her deception in step #7, then there was none.
Alice could also send Bob random bits in step #8. Bob won't know that she is sending him random bits until he receives the whole key and tries to decrypt the message halves. But again Bob has probability on his side. He has already received half of the keys, and Alice does not know which half. Alice is sure to send him a nonsense bit to a key he has already received, and he will immediately know that Alice is trying to deceive him.
Maybe Alice will just go along with step #8 until she has enough bits of the keys to break the DES messages, and then stop transmitting bits. DES has a 56-bit-long key. If she receives 40 of the bits, she only has to try 65,536 keys in order to read the message--certainly within the realm of a computer. But Bob will have exactly the same number of bits of her keys (or one less bit at the most), so he can do the same thing. Alice has no real choice but to continue the protocol.
Certified Mail. The same simultaneous oblivious transfer protocol used for contract signing could also be used for computer certified mail. Alice sends Bob the decryption key for some document, which she does not want to release unless Bob sends her some message indicating receipt. Bob, on the other hand, does not want to give Alice a receipt without getting the document. Oblivious transfer can solve this problem without having to resort to a trusted third party to enforce the protocol.
There are a number of approaches to implementing PKC, some of which I'll describe in this section. However, I'll play fast and loose with complexity theory, but only in the interest of comprehensibllity. For those of you who want the whole story, check the references. For everyone else, if the newspapers ever report that P = NP, ignore most of this section.
MerkLe-Hellman Knapsacks. The knapsack problem was one of the first proposed candidates for a public-key algorithm. The problem is simply stated: Given a list of different weights and the total weight of a closed knapsack, determine which particular weights are in the knapsack. For example, the list of different weights might be (9, 13, 15, 16, 18). If the total weight of the knapsack is 43, then the weights in the knapsack would be (9, 16, 18). In general, this problem cannot be solved except by brute force analysis. However, a certain subclass of the problem can be solved easily. Called "superincreasing knapsacks," they are knapsack problems where the list of different weights are such that each weight is greater than the sum of all previous weights: for example (1, 3, 6, 12, 25). Ralph Merkle and Martin Hellman designed a public-key algorithm around a method of transforming a superincreasing knapsack problem, which is easy to solve, into a conventional knapsack problem, which is hard to solve. The public key uses the conventional knapsack problem, and the private key uses the transformation method. This protocol has been broken.
The RSA Algorithm. Of all the public-key algorithms proposed over the years, RSA is by far the easiest to understand and implement and the most popular. (See the accompanying text box entitled "Public-Key Cryptography Meets the Real World.") Named after the three inventors, Ron Rivest, Adi Shamir, and Leonard Adelman, who first introduced the algorithm in 1978, it has since withstood years of extensive cryptoanalysis. Although the analysis neither proved or disproved security, it does indicate a confidence level in the theoretical underpinnings of the algorithm.
RSA gets its security from the difficulty of factoring large numbers. The public and private keys are functions of a pair of very large (100 to 200 digits or even larger) prime numbers. The algorithm calculates both keys from the prime numbers, and determining one key from the other is conjectured to be equivalent to factoring the product of the two primes.
To generate the two keys, choose two large prime numbers, p and q. Compute the product n=p*q. Then randomly choose the public key, e, such that e has no factors in common with (p-1)*(q-1). The easiest way to do this is to select another prime number for e, one larger than either (p-1) or (q-1). Finally, compute the private key, d, such that e*d=1(mod(p-11)*(q-1)). In other words, d=e-1(mod(p-1)*(q-1)). An algorithm for this computation, developed by Euclid, is given in Figure 2. The numbers e and n are the public key; the numbers d and n are the private key. The two primes, p and q, are no longer needed, but should not be revealed.
(a)
inverse (a, n)
{
g[0] = n;
g[1] = a;
v[0] = 0;
v[1] = 1;
i = 1;
do {
g[i]+1 = g[i]-1 mod gi;
v[i]+1 = v[i]-1 - (g[i]-1 div g[i]) * g[i];
i ++;
}
while (g != 0);
if (v[i]-1 >= 0) return v[i]-1;
else return v[i]-1 + n;
}
(b)
i g[i] v[i]
0 3220 0
1 79
1 2
60 -40
3 19
41 4
3 -163
5 1 1019
6 0
To encrypt a message m, first divide it into numerical blocks such that each block has a unique representation modulo n (with binary data, choose the largest power of 2 less than n). That is, if both p and q are hundred-digit primes, then n will have about 200 digits, and each message block, rm, should be 200 digits long. The encrypted message, c, will be made up of similarly sized message blocks c of about the same length. The encryption formula is simply ci = m1e (mod n).
To decrypt a message, take each encrypted block ci and compute mi = cid (mod n). Because cd = (mie)d = mied = mi(k(p-1)*(q-1)+1) = mi*mi(k(p-1)*(q-1)) = mi*1 = mi, all (mod n), the formula recovers the message. The message could just as easily have been encrypted with d and decrypted with e: the choice is arbitrary. I'll spare you the number theory as to why this works; most any current text on cryptography will go into it in detail.
A short example will probably go a long way to making this clearer. If p = 47 and q = 71, then n = p*q=3337. The encryption key e must have no factors in common with (p-1)*(q-1) = 46*70 = 3220. Choose e (at random) to be 79. In that case, d = 71-1 (mod 3220) = 1019. Figure 1 shows how this number was calculated. Publish e and n, and keep d secret. Discard p and q.
To encrypt the message m = "DRDOBBS" = 6882326879666683, first break it into small blocks. Three-digit blocks work nicely in this case. The message will be encrypted in six blocks, mi, where, m1 = 688, m2 = 232, m3 = 687, m4 = 966, m5 = 668 and m6 = 3. The first block is encrypted as 68879 (mod 3337) = 1570 = c1. Performing the same operation on the subsequent blocks generates an encrypted message c = 1570 2756 2714 2276 2423 158.
Decrypting the message requires performing the same exponentiation using the decryption key of 1019. So, 15701019 (mod 3337) 688 = m1. The rest of the message can be recovered in this manner.
If factoring a 200-digit number takes forever, how much easier can it be to find 100 digit prime numbers? Not much, if you use factoring methods to find these primes. However, there are a number of tests that can determine if a number is prime with a confidence of over 50 percent (possibly more). If a number n passes two of these tests, then the confidence rises to 75 percent. The chances of the number failing 10 tests are less than 1 in 1024. Here is the algorithm with the number of tests set at 100:
1. Choose a random number, n, to test.
2. Make sure that n is not divisible by any small primes. Testing 2, 3, 5, 7, and 11 will speed up the algorithm significantly.
3. Choose 100 random numbers, a1, a2 ... a100 from the interval [1..n-1].
4. Calculate ai(n-1)/2 = 1 (mod n) for all ai = ai..a100.
5. If ai(n-1)/2 = 1 (mod n) for all i, then n is composite.
If ai(n-1)/2! = 1 or -1 (mod n) for all i, then n is composite.
If ai(n-1)/2 = 1 or -1 (mod n) for all i, then n is prime.
This test will fail to accurately determine if a number is either prime or composite 1 in 2100 tries, or about 1 in 1030. If for some reason you need more confidence that the number is prime, choose a larger number of random numbers to test against. On the other hand, if you consider that the odds of the number being composite are less than the odds of you getting killed the next time you drive your car, you might not worry about it so much.
It is conjectured that the security of RSA depends wholly on the problem of factoring large numbers. Certainly that is the most obvious means of attack. Any adversary will have the public key, c, and the modulo, n. In order to find the decryption key, d, he has to factor n. Right now the best factoring algorithms take on the order of O(esqrt(ln n*ln(ln n))) steps to solve. If n is a 200-bit number, factoring will take on the order 2.7*1011 steps; for a 664-bit (200-digit) n, on the order or 1.2*1023 steps. Assuming a computer can perform a million steps per second (a generous assumption, considering some of the steps include long division with these monster numbers), it will take 3.8* 109 years to factor a 664-bit number. If someone discovers a faster factoring algorithm or if someone finds another way to break RSA, then the whole scheme will fall apart. However, people have been working on factoring algorithms since the invention of mathematics, and it is unlikely that any such algorithms are waiting to be discovered. Even if computing power increased a million-fold, factoring a 664-bit number will still take almost four thousand years. If you need more security, increase the length of n by a couple dozen bits.
El Gamal. A variant of the El Gamal public-key algorithm has been proposed as a digital signature standard. (See "Public-Key Cryptography Meets the Real World.") To generate a key pair, first choose a prime p, and q = a prime divisor of p-1. Compute g = h(p-1)/q mod p, where h is any integer 0<h<p such that h(p-1)/q mod p>1. The three numbers, p, q, and g are public, and can be common to an entire group of users. The private key, x, is a random integer less than q. The public key, y, is gx mod p.
To sign a message m, first generate a random integer, k, less than q. This integer must be different for each different signature. The digital signature consists of two numbers: r = (gk mod p) mod q, and s = (k-1(m+xr)) mod q. In reality, m will more likely be the hash of a much longer message.
To verify a signature, compute v = ((g(m(s-1 mod q) mod q)*y(r(s-1 mod q) mod 1)) mod p) mod q. If v = r, then the signature is verified. Enough math for today; check the references if you need proof that this works.
PKC implementations are becoming increasingly important in the electronic world about us. Software implementations of PKC have been adopted by Microsoft, Lotus, Apple, Novell, and many other companies and it can efficiently be implemented in some of the newer hardware architectures as well. For example, a Japanese manufacturer of an encrypting fax machine has demonstrated an RSA protocol for key exchange. A European company has developed a smart card that performs RSA encryption by itself, allowing RSA protocols to be implemented at money machines. A system of verifiable but untraceable messages has been developed that would allow secret balloting over the telephone. Another company is working on a digital cash system. Conventional electronic money will never completely replace cash because both drug dealers and congressmen have the objection to it: There is always an audit trail. Using PKC protocols, a system of electronic money can be implemented that is untraceable until someone tries to cheat. It is currently in use on a public transportation system in Europe. PKC has the potential of restoring the individual security and privacy that the electronic age has taken away.
Denning, D. Cryptography and Data Security. Reading, Mass.: Addison-Wesley, 1982.
Diffie, W., and M. Hellman. "New Directions tn Cryptography." IEEE Transactions on Information Theory (November, 1976).
El Gamal, T. "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithm." IEEE Transactions on Information Theory (July, 1985).
Federal Information Processing Standards Publication, August 19, 1991. "Digital Signature Standard." DRAFT, National Institute of Standards and Technology.
Federal Information Processing Standards Publication, January 22, 1992, "Secure Hash Standard." DRAFT, National Institute of Standards and Technology.
Patterson, W. Mathematical Cryptology. Totowa, NJ.: Rowman & Littlefield, 1987.
Rivest, R.L., A. Shamir, and L. Adelman. "A Method for Obtaining Digital Signatures and Public Key Cryptosystems." Communications of the ACM (February, 1978).
Salomaa, A. Public-key Cryptography. Berlin, Germany: Springer-Verlag, 1990.
DDJ
Ever since the Digital Encryption Standard (DES) was approved by the National Bureau of Standards, it's been the subject of intense criticism and debate. Based on an algorithm developed by IBM, DFS was inexpliciably modified by the National Security Agency in ways that seemed to make it weaker. Did the National Security Agency (NSA) put a "trap door" into the algorithm, allowing only themselves to break it? Did they deliberately weaken the algorith so that only they would have the resources to build a massive parallel machine to break it? And why was it designed the way it was, anyway? The government classified IBM's design notes, so no one knows.
DES can be broken by trying all of the 2[56] possible keys. This is a "brute force" attack; there are only 2[56] keys, so the correct key has to be one of them. And until last year, that was the best that could be achieved. Using a technique they developed called "differential cryptanalysis," Eli Biham and Adi Shamir have now succeeded in breaking certain implementations of DES using only 2[47] encryption steps. This is a significant blow to the security of DES, but there are some caveats. This is a chosen plaintext attack. The 2[47] steps use special predetermined plaintext blocks. If the cryptanalyst cannot introduce those particular plaintext blocks (that is, he or she has to listen to both the plaintext messages and the encrypted traffic until those particular blocks happen to appear), the attack will fail. Also, this is an attack against the electronic-codebook implementation of DES. Any feedback schemes will render this attack more complicated than brute force.
So, while Biham and Shamir are making great strides against DES, this does not mean that all of the DES equipment already fielded is suddenly worthless. I wouldn't use DES for long-term security (such as diplomatic information that needs to remain secure for 40 years or more), but for short-term secret data (like electronic funds transfers), DES is still as secure as it always was.
Whatever that means.
On September 20, 1983, U.S. patent number 4,405,829, titled "Cryptographic Communication System and Method"--informally known as the RSA algorithm--was awarded to the Massachusetts Institute of Technology. In 1984, RSA Data Security Inc. was formed to develop, license, and market the RSA algorithm. Lotus has since integrated RSA encryption and authentication in Notes, Digital Equipment Corp. uses RSA a part of their Distributed Systems Security Architecture, Novell uses RSA authentication as part of Netware, and Apple has licensed RSA for use in its Open Collaboration Environment (OCE) to provide both privacy and authentication. And Microsoft, Sun Microsystems, and IBM have licensed RSA for use in future versions of their operating systems and other products.
RSA, isn't the only public-key patent that's been awarded. Both Merkle-Hellman knapsacks (patent number 4,218,582) and an exponentiation public-key algorithm (4,424,414) are patented until around the turn of the century. The first public-key patent, which some people claim covers all of public-key cryptography, (4,200,770) was issued April 29, 1980. These patents, along with the RSA patent, are controlled by Public Key Partners, a group that includes RSA Data Security Inc.
These patents don't mean that excellent, although unauthorized, RSA software packages are not available. In 1991, Phil Zimmerman released a public-domain program called Pretty Good Privacy (PGP), which includes an RSA digital-signature scheme. Written for the IBM PC, it has since been ported to UNIX, VMS, Atari, and Amiga. After legal threats by RSA Data Security, Zimmerman agreed not to distribute or update the program, although programmers from other countries have worked on improvements, and a major update of PGP was released in April from New Zealand, beyond the reach of the RSA patent. It is available on computer bulletin boards worldwide.
Internet has been working with RSA Data Security on its own version of a personal public-key security program, called Privacy Enhanced Mail (PEM). This standard, which will be approved sometime this year, will provide protocols for RSA encryption and authentication for Internet mail users. RSA will release a Toolkit for Interoperable Privacy-Enhanced Messaging (TIPEM) to assist developers in writing applications which implement PEM protocols. TIPEM is a highly efficient set of routines written in C, and portable to most platforms. RSA Data Security will also provide a hardware-independent reference implementation of the PEM protocols, which the company plans to license free for academic and laboratory use. Distributed products will require proper licenses.
There are significant differences between PGP and the PEM prototols. PEM, for example, has centralized key management using a trusted Certification Authority. This forces all key generation to involve a central point, forces transference of trust, and is generally tailored for large organizations. PGP is more of a grass roots program. It has a decentralized, yet secure, key-management scheme--anyone can generate their own RSA key pair. Each pair of users communicates regardless of anyone else in the network. PGP is designed with guerilla-style key management for the masses.
The PEM header files are somewhat worrisome. According to the standard, each encrypted message has an unencrypted header file which contains quite a lot of information about the message. The header contains who sent the message, who the message is for, which encryption algorithm was used, which message-digest algorithm was used, and when the message was encrypted. This information is available to anyone listening on the communications channel, allowing for some pretty lucrative traffic analysis. Even if no one knows what you are saying, they know who you are talking to, when you are talking to them, and the amount of things you are saying. PEM actually requires you to sign your messages, precluding anonymous messages. PGP, on the other hand, keeps as much information secret as possible, and signatures are optional. The only thing unencrypted in the header file is the ID of the receiver. If the receiver has the appropriate private key and decrypts the message, only then does he learn who sent the message and when or if it was signed. As little information is sent unencrypted as possible.
Although free, PGP is well-designed, with possibly the most sophisticated key management features available. PGP supports IDEA file encryptions, the MD5 Message Digest algorithm, and RSA digital signatures. Data compression is automatically provided before encryption to reduce file lengths and eliminate redundancy. Complete source code for PGP is available.
Meanwhile, the National Institute of Standards and Technology (NIST), with the help of the National Security Agency (NSA), has proposed their own public-key Digital Signature Standard (DSS): an algorithm based on an unpatented variant of the El Gamal algorithm and a Secure Hash Algorithm (SHA) modeled after the MD4 Message Digest algorithm. (Various patent-infringement suits have been threatened by Public-Key Partners, however.) DSS is slower than RSA, slightly slower generating signatures and significantly slower in verifying signatures. Still, hardware is getting faster all the time, and precomputation can make DSS faster than RSA in certain implementations. The standard fixes the key length at 512 bits, which most cryptographers consider too small for long-term security. Some cryptographers argued that the use of a common modulus among a group of users makes for an easier target than the RSA algorithm, where the modulus is different for each individual user. But it is possible to use an individual modulus for each user, so this is not a problem. Other cryptographers, claiming to have found a "trap door," pointed out a tiny subset of moduli that are easy to break; this can be protected against with minimal effort. And finally, the standard addresses digital signatures but makes no mention of encryption. The comment period was supposed to end in November 1991, but NIST extended it through February. Last December, the NIST advisory board recommended that DSS as written had grave problems. While significant, this action was mostly political, as the advisory board consists primarily of industry representatives (many of whom have already licensed the RSA algorithm). Anything could happen next.
Information Security Corp. (ISC), of Deerfield. Ill., has already released an IBM PC program called "Secret Agent" that, uses public-key cryptography. Secret Agent supports DES file encryption (in Cipher Block Chaining mode), DSS digital signatures (and the SHA), and El Gamal for key management. Secret Agent's key management isn't as sophisicated as PGP's, but if you trust NIST's algorithms, Secret Agent has the advantage of being available today and perfectly legal.
Next Inc, entered the fray in February 1992 with their own public-key encryption system. Their "Fast Elliptic Encryption" (FEE) algorithm is an implementation of a well documented, elliptic-curve public-key algorithm, the details of which are incredibly complicated. While elliptic curve encryption appears to be, key bit for key bit, more secure than RSA, there is still some skepticism among researchers that a mathematical breakthrough will render the scheme useless. In any case, Next scientists invented a series of mathematical speedups that make the algorithm fast enough to actually use. Pending NSA approval, Next plans for FEE to provide both security and authentication in future versions of the Next operating system. They are also attempting to patent their mathematical speedups, although potential legal complications with at least two other elliptic-curve patent applications and a similar mathematical speedup patent application will make this an interesting exercise. And there's always the specter of a lawsuit from Public-Key Partners, based on their claim that patent 4,200,770 covers all of public-key cryptography. Finally, there are indications from Next that they will allow others to implement FEE without paying royalties.
This all will become moot on September 20, 2000, when the RSA patent expires and the algorithm enters the public domain. Unless the Next scheme turns out to be secure and royalty-free, we will be caught between a federal agency that no one trusts and a company that many do not like.
--B.S.
Copyright © 1992, Dr. Dobb's Journal