CS 513 System Security -- Lecture Notes for April 23, 1998

Public Key Cryptography

CS 513 -- System Security -- April 23, 1998 -- Lecture 26
Lecturer: Professor Fred B. Schneider

Lecture notes by Lynette I. Millett
We have been discussing secret key (also known as symmetric) cryptography along with related cryptosystems and possible attacks. Last time we discussed the problem of key distribution and looked at an example system (Kerberos) for key management. Today we discuss another approach to cryptography known as public key or asymmetric cryptography.

In public key cryptography, some keys are known to everyone, so it would seem that the key distribution problem vanishes. The approach was first published in the open literature in 1975. (Recently declassified documents in Great Britain suggest that public key cryptography was known there before 1975. See Further Reading above.)

The basic idea of a public key cryptosystem is to have two keys: a private (secret) key and a public key. Anyone can know the public key. Plaintext to a principal B is encrypted using B's public key. B decrypts the enciphered text using its private key. As long as B is the only one who knows the private key, then only B can decrypt messages encrypted under B's public key.

Some public key cryptography schemes also allow plaintext to be run through the decryption algorithm (using the private key). What is produced is referred to as signed text and it can be "deciphered" using the public key. Only the possessor of a private key can create text that is decipherable using the public key. The functionality of signed text cannot be replicated using secret key/symmetric cryptography.

Public key cryptography is usually much slower than secret key cryptography, so it is rarely used to encrypt an entire message. Typically a message is encrypted with a secret key. The secret key is then encrypted using public key cryptography, and the encrypted message and key are sent. Uses of public key cryptography include secrecy, authentication, and digital signatures.

Secrecy is obtained when principal A encrypts a message m using B's public key. Thereafter, the only way to decrypt m is to know the private key of B. In secret key cryptography, doing authentication requires having a different key for each pair of principals; in public key cryptography, each principal needs to know just its own private key. An example of a public-key authentication protocol is:

Digital signatures are used to prove that a message was generated by a particular principal. Assume that the cryptosystem has the optional property described above wherein a message m "decrypted" under a private key, and then "encrypted" using the corresponding public key produces m. To create a signed message, A will encrypt a message using its own private key and send that encrypted message to B. B looks up A's public key and uses it to decrypt the message. This is not completely practical since it requires running the decryption on an entire message, which can be expensive. A solution is to compute a hash of the message and sign that.

A hash is a function that digests information. It takes a message as input and outputs a short bit string (say, 128 bits). An example of a 1-bit hash would be a function that returns the parity of the message. Think of a hash as a succinct summary of a message that has two properties:

Changing the message slightly causes a change in the hash value. That is, if m is slightly different from m', then hash(m) is not equal to hash(m').
Given a message m and hash(m), it is very difficult to find a message m' where hash(m) = hash(m').

These properties make a message-text substitution attack difficult given a hash. Specifically, suppose that message m is sent along with a signed hash value for m. The properties of the hash function would make it difficult for an attacker to substitute another meaningful message that has the same hash value as the original.

We will now examine a few examples of public key cryptography systems.

Merkle's Puzzles

Merkle's Puzzles was one of the first public key cryptographic systems to be described. It allows A and B to agree on a secret key. Principal A invents a million keys and a million puzzles, where each puzzle encodes a different one of the keys. Each puzzle is assumed to take at least two minutes to solve and fit into 96 bits. A sends these puzzles to B. B then picks a puzzle at random and solves it. B encrypts a pre-arranged string (say 0000) with the key from the puzzle it solved. B sends this encrypted string back to A. A trys each of the million keys on the message it receives from B. The one that decrypts the message and obtains the pre-arranged string is the secret key that A will use henceforth to communicate with B.

A wiretapper C could steal the million puzzles. However, C would need to crack all million of the puzzles in order to discover the secret key. (If the wiretapper didn't know the pre-arranged string, then it can't even use a known-plaintext attack.) Since cracking each puzzle requires at least 2 minutes, the wiretapper would need on average 330 days to find the key.

Diffie-Hellman Key Exchange

Diffie-Hellman Key Exchange allows two principals to agree on a shared key even though they exchange messages in public. However, there is no authentication, so either side could be be spoofed by an active wiretapper. The first step is to choose a large prime number p (around 512 bits). The second is to choose an integer g where g < p (with some other technical restrictions.) The protocol works as follows:

At this point, A can compute:

^S_A

^S_B

^S_A

^S_B

^S_A

^S_BS_A

Similarly B can compute :

^S_B

^S_AS_B

Therefore, ((g^S_AS_B) mod p) = ((g^S_BS_A) mod p) is the final shared key.

A wiretapper can see all the messages that are sent, but can't do anything without having a fast way to compute logs in finite fields, which is assumed to be hard. One problem with Diffie-Hellman is that it does not generalize to send arbitrary messages.

RSA

RSA (Rivest Shamir Adelman) is the third public key system we examine. RSA is usually used to encrypt a private key and then send that with along with a message encrypted by the private key. It uses a variable key length (usually 512 bits) and a variable block size that is not greater than the key length. RSA works as follows:

Choose two large primes (say, 256 bits each) p and q. These must be kept secret.
Compute n = p*q. The number n is not secret. This systems works under the assumption that factoring n is computationally intractable.
Chose e such that e is relatively prime to (has no common factors other than 1 with) (p-1)*(q-1). The number e is usually chosen to be small. 3 and 64437 are popular.
The public key is the pair (e, n). Note that e doesn't have to be secret. The private key is (d, n) where d is the multiplicative inverse of e mod (p-1)(q-1).

To encrypt a message m, compute m^e mod n and send the result as ciphertext. To decrypt ciphertext c: m = c^d mod n. RSA can also be used for digital signatures. To sign a message m: s = m^d mod n. To check a signature: m = s^e mod n.

A lot of number theory is needed to prove that this technique works. One necessary theorem is: m = (m^e mod n)^d mod n.

Certification Authorities (Public Key Infrastructure)

It would seem that an advantage to public key cryptography is that a KDC is no longer necessary. However, how can one principal learn the public key another? How does one principal know they have the right public key and haven't been spoofed by an intruder? It turns out that some sort of server is still needed to certify which public keys belong to whom.

A certification authority (CA) is a trusted server that generates certificates of the form {name, public key}_CA where CA is the certification authority's signature (private) key. All hosts are preconfigured with the certification authority's public key, therefore any host can check the signature on these certificates. Note that a CA is more attractive than a KDC because a CA it doesn't need to be on-line. Certificates can be stored anyplace and forwarded anywhere as they are needed.

One problem is that if a principal's private key is compromised, then all those certificates (wherever they are) will cause the wrong public key to be used. Since there isn't a single authority that everyone trusts, updating all those certificates is not feasible. A solution is to require that certificates have expiration dates. This will limit damage but not rule it out entirely. Next lecture we will discuss the issues in somewhat more detail.