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 DiffieHellman 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:
 DiffieHellman key exchange

A system for exchanging cryptographic keys between active parties.
DiffieHellman 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
wellknown 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
(DiffieHelman), 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^{2} = x^{3} + 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, Internetbased cryptographic software has used 512bit
RSA keys to encrypt 40bit RC2 keys, and 1,024bit RSA keys have been
used with 128bit RC2. But this does not mean that 512bit RSA keys
offer roughly the same strength as 40bit RC2 keys, or that 1,024bit
RSA keys offer roughly the same strength as 128bit RC2 keys.
As this book goes to press, 40bit RC2 keys can be readily cracked
using a small network of highperformance personal computers; there
is even software that is commercially available for networking PCs
together for the purpose of cracking 40bit RC2 keys. At the same
time, 512bit RSA keys are right at the edge of the size of numbers
that can be factored by large Internetbased factoring projects that
employ tens of thousands of individual computers. Thus, a 512bit RSA
key offers considerably more security than the 40bit 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,024bit 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 128bit RC2 key
within the course of human existence on the planet Earth. The reason
that these numbers are so different from the 512bit/40bit 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 128bit RC2 key is impossibly
stronger than a 1024bit RSA key.

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:
BEGIN PGP PUBLIC KEY BLOCK
Version: PGP 6.5.8
mQGiBDqX9jwRBADakcIMfMhgvHCge0JOXWqv7Lo8CtbqNpkvpRc98Z7dqjkhhcqC
4xol6rAv4zoZipMtCKOvR2jA0uqQI05GGSnDd0FXeIXH7tW9oquljjwlRBUqWbTb
zAcZC0qyNCdStiKTOSZCFzdDGVHiomSYQ7Om0QP77ipjFnNwyQk5hmTBhQCg/1JE
sSl504X8tSf9vTglF5Tvpy0D/1HtVqrrebkK7zPG2AKDoIO0dgtGv0PeJSJ76EWB
FHMKFm6h0BQjq4NSHUsxuCy0/mpLa31Hm57FHAY/4IbQ1RkFNdDAnpqXe0HWcAT2
0y10L/dMSy20FOvlx/WUKEgz869CaxPBlq14C1R68P+eMp5t8FG8mPXMFyAyMBcA
rTLBA/9p6xZA0rxLha0aPbQpNFSb78J89bs3Wb8dDzJONkUB2dpGUPy7YfAHoZR1
8G0kGk5+8CuhQ8xb0t5jr11/aCjSs2kzrORYpYiDJXprSTvVUHhLjqttXoBCMlsj
TlUNXvc5w+0NVD6Dq6HMN0HQldDcvGjeCCGBvF5kfYsyJEQGkrQbTXIuIFRlc3Qg
S2V5IDx0ZXN0QGtleS5jb20+iQBOBBARAgAOBQI6l/Y8BAsDAgECGQEACgkQGQai
QpjjHCxWlACbBw1H9gYMIuu6FZyXC+n8GcbiOzUAnjuE/UeTtKTWa+1U+cU6xRRR
2YxMuQENBDqX9j0QBADvKZeABrS2KagG6cDOmiUWiG4Y7VIq4CjsC9cdeQtbZ+FV
0oxAb9vz1pSmqdf8/RcvS5Tr5Wby+oBxlXRy33R72FO3J4wT0dfstzdnMEA87p/n
kIla4Quo4j5XoWCycMWAZ1w5/SHw+N2ES0CyvITY19dDjh2sJ8zs0g9rp4rNAwAC
AgP9F6N+z2baqrm/Wi2tTVoEpDL8Y+BF6Wz3FI7pdLZxOojEGI6ELfChH3P3VDoh
LjduRMt9VUyhD/9Sl7BmFJOlUczLuQICv3toOINtHlY6gH8KM2nh1dfcB80Gwg9V
oGE71lXO6T6wMNy6KmFxLYLscFh592ThpXsvn8GBPOfIZTCJAEYEGBECAAYFAjqX
9j0ACgkQGQaiQpjjHCwJ1ACfWjQlxRaS+Xj/qv5z3cceMevCetgAoJFbuuMHXl/X
NTFrAkXTg0J1MYVH
=Wx2A
END PGP PUBLIC KEY BLOCK
We can use the encryption key to encrypt the small message. Here is
the result:
BEGIN PGP MESSAGE
Version: PGP 6.5.8
qANQR1DBwE4DZuAgjgADrN4QBADoJ9piyd0c9fLS25Cya6NrtR1PrY4h0k7aZzlN
p1fZbOWptzb8Pn3gkrtY3H20MWc2hhl3ER68CFwyC8BAB6EJqHwtpldB258D43iu
NffuB4vKTdu1caoT4AHSZgo2zX/Ao/JuEa0mwzhnxFGYhuvR26y2hVk7IlWyDJ6d
ZRfN3QQAx9opTjQRSjA3YJUKism8t+ba8VYEvIeRI7sukblzVF50jG6vQW3m368V
udCWwfPDbC7XM3Hwfvuw054ImYGsz3BWWGPXjQfOeOBJzKVPXArUUDv+oKfVdp7w
V/sGEErhnly7s9Q2IqyeXPc7ug99zLhXb5FRtmPf3mASwwuhrQHJLRm3eWUfKn8z
IMehG2KU3kJrNQXEU0RdWJ9gV72tQlyB6AD2tJK33tNk7gV+lw==
=5h+G
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.
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:
BEGIN PGP SIGNED MESSAGE
Hash: SHA1
this is a test message
BEGIN PGP SIGNATURE
Version: PGP 6.5.8
iQA/AwUBOpf3DRkGokKY4xwsEQKQvQCg291aRcMYyjsdeTdI0QZ2dZOHpdkAn3z8
gT7Vd/0Wadj1j+OnXLysXK+E
=CcHl
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.
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, generalpurpose 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 RSA129 challenge number. The
number, named "RSA129" 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 challengersalist@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.
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/.

