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 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 1024 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.
- 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 very fast to calculate. 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.
- RSA
RSA is a well-known public key cryptography system developed in 1977 by three professors then 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 may be any length, depending on the particular implementation used.
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 only be decrypted 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.
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 only be decrypted 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 are almost always 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. 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.
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-----
For detailed information about digital signatures, see Chapter 6. Additional information about public keys, digital signatures, and encrypted messaging can be found in the book PGP: Pretty Good Privacy, by Simson Garfinkel.
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.
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 [email protected].
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.
It is worth noting that there may always be a difference between the best known methods and the best published methods. If a major mathematical breakthrough in factoring were discovered, it might not be published for all to see. For example, if a new method were developed by a government agency, it might be kept secret to be used against encrypted messages sent by officials of other countries. Alternatively, if a new method were developed by someone with criminal tendencies, it might be kept secret to be used in future economic crimes involving existing encryption methods.
[45] For more information on cryptographic key sizes, see “Selecting Cryptographic Key Sizes,” by Arjen K. Lenstra and Eric R. Verheul, available from http://www.cryptosavvy.com/cryptosizes.pdf.