7.3 Public Key Algorithms
The existence of public key cryptography
was first postulated in print in the fall of 1975 by Whitfield
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.
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 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
y2 = x3 + 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.
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.
7.3.1 Uses for Public Key Encryption
Two of the most common uses for public key
cryptography are encrypted messaging and
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
In the following two sections we'll show examples of
220.127.116.11 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:
-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: PGP 6.5.8
-----END PGP PUBLIC KEY BLOCK-----
We can use the encryption key to encrypt the small message. Here is
-----BEGIN PGP MESSAGE-----
Version: PGP 6.5.8
-----END PGP MESSAGE-----
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.
18.104.22.168 Digital signatures
Instead of encrypting a
message, we can use public key cryptography to digitally sign a
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:
-----BEGIN PGP SIGNED MESSAGE-----
this is a test message
-----BEGIN PGP SIGNATURE-----
Version: PGP 6.5.8
-----END PGP SIGNATURE-----
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.
22.214.171.124 Key search attacks
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
at Bellcore (the research arm of the U.S. local telephone companies),
Michael Graff, and Paul
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 firstname.lastname@example.org.
126.96.36.199 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.
188.8.131.52 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.
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/.