7.3 Public Key Algorithms

The existence of public key cryptography was first postulated in print in the fall of 1975 by Whitfield Diffie and Martin Hellman. The two researchers, then at Stanford University, wrote a paper in which they presupposed the existence of an encryption technique in which information encrypted with one key (the public key) could be decrypted by a second, apparently unrelated key (the private key). Robert Merkle, then a graduate student at Berkeley, had similar ideas at the same time, but because of the vagaries of the academic publication process, Merkle's papers were not published until the underlying principles and mathematics of the Diffie-Hellman algorithm were widely known.

Since that time, a variety of public key encryption systems have been developed. Unfortunately, there have been significantly fewer developments in public key algorithms than in symmetric key algorithms. The reason has to do with how these algorithms are created. Good symmetric key algorithms simply scramble their input depending on the input key; developing a new symmetric key algorithm requires coming up with new ways for performing that scrambling reliably. Public key algorithms tend to be based on number theory. Developing new public key algorithms requires identifying new mathematical equations with particular properties.

The following list summarizes the public key systems in common use today:

Diffie-Hellman key exchange: A system for exchanging cryptographic keys between active parties. Diffie-Hellman is not actually a method of encryption and decryption, but a method of developing and exchanging a shared private key over a public communications channel. In effect, the two parties agree to some common numerical values, and then each party creates a key. Mathematical transformations of the keys are exchanged. Each party can then calculate a third session key that cannot easily be derived by an attacker who knows both exchanged values.
DSA/DSS: The Digital Signature Standard (DSS) was developed by the U.S. National Security Agency and adopted as a Federal Information Processing Standard (FIPS) by the National Institute for Standards and Technology. DSS is based on the Digital Signature Algorithm (DSA). Although DSA allows keys of any length, only keys between 512 and 1,024 bits are permitted under the DSS FIPS. As specified, DSS can be used only for digital signatures, although it is possible to use some DSA implementations for encryption as well.
RSA: RSA is a well-known public key cryptography system developed in 1977 by three professors at MIT: Ronald Rivest, Adi Shamir, and Leonard Adleman. RSA can be used both for encrypting information and as the basis of a digital signature system. Digital signatures can be used to prove the authorship and authenticity of digital information. The key can be any length, depending on the particular implementation used.
Elliptic curves: Public key systems have traditionally been based on factoring (RSA), discrete logarithms (Diffie-Helman), and the knapsack problem. Elliptic curve cryptosystems are public key encryption systems that are based on an elliptic curve rather than on a traditional logarithmic function; that is, they are based on solutions to the equation y² = x³ + ax + b. The advantage to using elliptic curve systems stems from the fact that there are no known subexponential algorithms for computing discrete logarithms of elliptic curves. Thus, short keys in elliptic curve cryptosystems can offer a high degree of privacy and security, while remaining easily calculatable. Elliptic curves can be computed very efficiently in hardware. Certicom (http://www.certicom.com) has attempted to commercialize implementations of elliptic curve cryptosystems for use in mobile computing.

When Is 128 Bigger than 512?

Because the keys of symmetric and asymmetric encryption algorithms are used in fundamentally different ways, it is not possible to infer the relative cryptographic strength of these algorithms by comparing the length of their keys.

Traditionally, Internet-based cryptographic software has used 512-bit RSA keys to encrypt 40-bit RC2 keys, and 1,024-bit RSA keys have been used with 128-bit RC2. But this does not mean that 512-bit RSA keys offer roughly the same strength as 40-bit RC2 keys, or that 1,024-bit RSA keys offer roughly the same strength as 128-bit RC2 keys.

As this book goes to press, 40-bit RC2 keys can be readily cracked using a small network of high-performance personal computers; there is even software that is commercially available for networking PCs together for the purpose of cracking 40-bit RC2 keys. At the same time, 512-bit RSA keys are right at the edge of the size of numbers that can be factored by large Internet-based factoring projects that employ tens of thousands of individual computers. Thus, a 512-bit RSA key offers considerably more security than the 40-bit RC2 key.

It is likely that within the next 20 years there will be many breakthroughs in the science of factoring large numbers. It is also clear that computers in 20 years' time will be dramatically faster than the computers of today. Thus, it might be reasonable to assume that it will be quite possible to factor a 1,024-bit RSA key in the year 2020.

But as we have seen in this chapter, even if there are dramatic advances in the field of quantum computing, it is unlikely that it will be possible to do a brute force attack on a 128-bit RC2 key within the course of human existence on the planet Earth. The reason that these numbers are so different from the 512-bit/40-bit numbers is that each increased bit of key for the RC2 algorithm doubles the difficulty of finding a new key, but each additional bit of key for the RSA algorithm only nominally increases the difficulty of factoring the composite number used by the algorithm, assuming that there are some advances in our ability to identify prime numbers.

It's possible that a 128-bit RC2 key is impossibly stronger than a 1024-bit RSA key.^[16]

^[16] For more information on cryptographic key sizes, see "Selecting Cryptographic Key Sizes," by Arjen K. Lenstra and Eric R. Verheul, available from http://cryptosavvy.com/cryptosizes.pdf and http://cryptosavvy.com/toc.pdf.

7.3.1 Uses for Public Key Encryption

Two of the most common uses for public key cryptography are encrypted messaging and digital signatures:

With encrypted messaging, a person who wishes to send an encrypted message to a particular recipient encrypts that message with the individual's public key. The message can then be decrypted only by the authorized recipient.
With digital signatures, the sender of the message uses the public key algorithm and a private key to digitally sign a message. Anyone who receives the message can then validate the authenticity of the message by verifying the signature with the sender's public key.

In the following two sections we'll show examples of each.

7.3.1.1 Encrypted messaging

Encrypted messaging is a general term that is used to describe the sending and receiving of encrypted email and instant messages. In general, these systems use a public key to transform a message into an encrypted message. This message can be decrypted only by someone (or something) that has the public key's corresponding private key.

For example, here is a message:

this is a test message

and here is a small PGP public key:

We can use the encryption key to encrypt the small message. Here is the result:

Notice that the encrypted message is considerably longer than the original plaintext. Encrypted messages can be longer than the original plaintext because they usually contain header information and other details that are useful for the decryption process. This overhead is most noticeable when short messages are encrypted because PGP compresses the plaintext before encrypting it. In the case of PGP messages, the encrypted message contains (among other things) the ID code for each of the keys that can decipher the message.

7.3.1.2 Digital signatures

Instead of encrypting a message, we can use public key cryptography to digitally sign a message.

Consider the message from the previous example:

this is a test message

This message can be signed with a private key that corresponds to the public key shown. The result is a signed message:

Additional information about public keys, digital signatures, and encrypted messaging can be found in the books Web Security, Privacy & Commerce, by Simson Garfinkel with Gene Spafford, and PGP: Pretty Good Privacy, by Simson Garfinkel (both by O'Reilly).

7.3.2 Attacks on Public Key Algorithms

Public key algorithms are theoretically easier to attack than symmetric key algorithms because the attacker (presumably) has a copy of the public key that was used to encrypt the message. The job of the attacker is further simplified because the message presumably identifies which public key encryption algorithm was used to encrypt the message.

Public key algorithm attacks generally fall into two categories: key search attacks and analytic attacks.

7.3.2.1 Key search attacks

Key search attacks are the most popular kind of attacks to mount on public key encrypted messages because they are the most easily understood. These attacks attempt to derive a private key from its corresponding public key.

In the case of the RSA public key system, key search attacks are performed by attempting to factor a large number that is associated with the public key. The number is the product of two prime numbers. Once the large composite number is factored, the private key can be readily derived from the public key.

Because of the widespread use of the RSA system, techniques for rapidly factoring large composite numbers have become of great interest to many mathematicians. But while there have been steady improvements in factoring techniques, mathematicians have not yet discovered a fast, general-purpose technique for factoring arbitrarily large numbers. Of course, the fact that no such factoring algorithm has been discovered should not be taken as proof that no such algorithm exists: there may come a time when factoring becomes a trivial problem, and the world needs to discard RSA in favor of some other public key encryption algorithm.

The most famous factoring attack at the time of this writing was the factoring of the RSA-129 challenge number. The number, named "RSA-129" because it consisted of 129 decimal digits, was first published as a challenge to readers in the September 1977 issue of Popular Science. The number was factored in 1994 by an international team of volunteers coordinated by Arjen Lenstra, then at Bellcore (the research arm of the U.S. local telephone companies), Derek Atkins, Michael Graff, and Paul Leyland.

RSA Data Security publishes a list of additional factoring challenges, with cash rewards for people who are the first to factor the numbers. You can get a complete list of the RSA challenge numbers by sending a message to challenge-rsa-list@rsa.com.

7.3.2.2 Analytic attacks

The other way of attacking a public key encryption system is to find a fundamental flaw or weakness in the mathematical problem on which the encryption system is based. Don't scoff�this has been done at least once before. The first public key encryption system to be patented was based on a mathematical problem called the Superincreasing Knapsack Problem. A few years after this technique was suggested, a way was found to mathematically derive the secret key from the public key in a very short amount of time.

7.3.2.3 Known versus published methods

It is worth noting that it is always possible that there is a difference between the best known methods and the best published methods. If a major mathematical breakthrough in factoring is discovered, it might not be published for all to see. For example, if a new method is developed by a government agency, it might be kept secret to be used against encrypted messages sent by officials of other countries. Likewise, if a new method is developed by someone with criminal tendencies, it might be kept secret to be used in future economic crimes involving existing encryption methods.

Implementation Strength

We would be remiss not to note that strong algorithms and good choices for keys are not sufficient to assure cryptographic strength. It is also vital that the implementation of the algorithm, along with any key generation and storage, be correct and carefully tested. A buggy implementation, poor random number generation, or sloppy handling of keys may all increase the exposure of your information.

It is also the case that the implementations are points of attack. Law enforcement, criminals, or members of your family may all be interested in what you are encrypting. If they gain access to your software or hardware, they may be able to alter the system to capture your keys to decrypt your messages, or capture the unencrypted traffic. For one example of a hardware device used to capture keys and text, take a look at the KeyGhost at http://www.keyghost.com/.