Page133

Asymmetric Encryption

For thousands of years, cryptographic ciphers suffered from a chicken-and-egg problem: in order to securely communicate with someone, you had to first (securely) share a key or device. Asymmetric encryption was a mathematical breakthrough of the 1970s, finally solving the age-old challenge of pre-shared keys. Asymmetric pioneers include Whitfield Diffie and Martin Hellman, who created the Diffie-Hellman key exchange in 1976. The RSA algorithm was invented in 1977 (RSA stands for “Rivest, Shamir, and Adleman,” the authors’ names).

Asymmetric encryption uses two keys: if you encrypt with one key, you may decrypt with the other. One key may be made public (called the public key); asymmetric encryption is also called public key encryption for this reason. Anyone who wants to communicate with you may simply download your publicly posted public key and use it to encrypt their plaintext. Once encrypted, your public key cannot decrypt the plaintext: only your private key can do so. As the name implies, your private key must be kept private and secure.

Additionally, any message encrypted with the private key may be decrypted with the public key. This is typically used for digital signatures, as we will see shortly.

Asymmetric Methods

Math lies behind the asymmetric breakthrough. These methods use “one-way functions,” which are easy to compute “one way,” and difficult to compute in the reverse direction.

Factoring Prime Numbers

An example of a one-way function is factoring a composite number into its primes. A prime number is a number evenly divisible only by one and itself; a composite number is evenly divisible by numbers other than 1 and itself.

Multiplying the prime number 6269 by the prime number 7883 results in the composite number 49,418,527. That “way” is quite easy to compute, taking milliseconds on a calculator. Answering the question “which prime number times which prime number equals 49,418,527” is much more difficult. That problem is called factoring, and no shortcut has been found for hundreds of years. This is the basis of the RSA algorithm.

Factoring a large composite number (thousands of bits long) is so difficult that the composite number can be safely publicly posted (this is the public key). The primes that are multiplied to create the public key must be kept private (they are the private key).

Exam Warning
Do not confuse “one-way function” with “one-way hash.” The former describes asymmetric algorithms; the latter describes hash algorithms.

Discrete Logarithm

A logarithm is the opposite of exponentiation. Computing 7 to the 13th power (exponentiation) is easy on a modern calculator: 96,889,010,407. Asking the question “96,889,010,407 is 7 to what power” (finding the logarithm) is more difficult. Discrete logarithms apply logarithms to groups, which is a much harder problem to solve. This one-way function is the basis of the Diffie-Hellman and ElGamal asymmetric algorithms.

Diffie-Hellman Key Agreement Protocol

Key agreement allows two parties to securely agree on a symmetric key via a public channel, such as the Internet, with no prior key exchange. An attacker who can sniff the entire conversation is unable to derive the exchanged key. Whitfield Diffie and Martin Hellman created the Diffie-Hellman Key Agreement Protocol (also called the Diffie-Hellman Key Exchange) in 1976. Diffie-Hellman uses discrete logarithms to provide security.