Public Key Cryptography

Lecturer: Professor Fred B. Schneider

Lecture notes by Lynette I. Millett
Revised by Michael Frei

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 will discuss another approach to cryptography known as public key or asymmetric cryptography. But first, lets try to establish an intuition for why we might want to consider an alternative to a secret key system using key distribution, and consequently what we're looking for in public key cryptography.

Problem of Key Distribution

As you may have noticed from the previous lecture on Key Distribution, there is one difficultly inherent in all KDC mechanisms. Specifically, it seems like you must already have agreed on a key in order to securely distribute the next key. This requirement causes problems because it won't work after your system has been compromised (when you have to start over again) and it won't work initially (when you have not yet agreed on a key). Basically, shared key distribution is a sham. You move the vulnerability away from "people trying to figure out a message" to the KDCs.

However, one can imagine a physical solution to the problem "Alice sends a secret to Bob, but they don't share a key", which is identical to the two problems mentioned above. Consider the following example:

  1. Alice puts a secret in a box, which she locks with her own lock. Only Alice has the key to this lock.
  2. Alice then ships the box to Bob.
  3. Bob adds his own lock to this box in parallel, so that now the box has two locks.
  4. Bob then ships the box back to Alice.
  5. Alice, knowing that the box is secure with Bob's lock, then takes her own lock off the box (with her key).
  6. Alice sends the box back to Bob.
  7. Bob then removes his lock and receives the secret (which could have been a new shared key).

We have successfully shared a secret without exposing it, and without possessing a shared key initially. When we look at this mechanism as a whole, we can get an intuition of what exactly we need in a lock. As in the above system, we don't care who is able to actually lock our mechanism, but we want to make sure that only somebody with a key can unlock it. This is essentially the same as saying it should be cheap to unlock our mechanism with the key, but very expensive to try to unlock it without the key.

Let's try to look at this ideal lock in a mathematical sense. What we're looking for is called a 1-way trap-door function. To apply this idea to a cryptosystem, we would want an encryption mechanism that is a 1-way function, in other words, easy to compute but hard to invert. Our decryption of this resulting value should be easy if you know about the trap door. An example of a mathematical function that is very hard to do unless you know something about it is finding factors of numbers.

Diffie - Hellman Key Exchange

Now lets examine an implementation of a 1-way function. Diffie-Hellman Key Exchange allows two principals to agree on a shared key even though they exchange messages in public. In the protocol given below, there is no authentication, so either side could be be spoofed by an active wiretapper. The protocol can easily be extended into one that does also implement the necessary authentication.

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: Similarly B can compute : Therefore, ((gSASB) mod p) = ((gSBSA) 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.

Physical Analogy for Diffie-Hellman Key Exchange

We can borrow a physical analogy (from The Code Book) to better understand the principles underlining Diffie-Hellman key exchange. Consider the following:

  1. We have two principals,A and B, each with a 3-liter paint pot that contains 1-liter of yellow paint. We will use E to denote a passive wiretapper. We can assume that mixed paint cannot be deconstructed into original colors.

  2. A adds to her 1 liter of yellow paint a secret color SA. B also adds to his 1 liter of yellow paint a secret color SB.

  3. A and B swap pots. E is able to observe the 2, 2-liter mixtures be exchanged, but E cannot deduce what color was added to either mixture, E can only deduce the relative color balance in the combined 4 liter mixture: 2 * yellow + SA + SB (Y:Y:SA:SB).

  4. A adds SA to B's pot. The result (Y:SA:SB) is the key. B adds SB to A's pot. The result (Y:SB:SA) is the key.
    Notice: A and B have computed the same key, but E gets a different one.

Public Key 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.)

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 using shared key cryptography (with a secret key). That secret key is then encrypted using public key cryptography, and the encrypted message and key are sent. This is known as hybrid encryption. This method can allow for complex structures in implementing our secrecy requirements (see Figure below) : e.g. "message is readable by A,B,C,D".

History of Public Key Cryptography

(United States)

(United Kingdom)

Uses of Public-Key Cryptography

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. (see Figure below)

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 additional property 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 succint summary of a message that has four properties:

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 can easily have multiple signatures (see Figure 1 below), as well as build up a chain of signatures which establishes a valid history (see Figure 2 below). This chaining of signatures can be used to prove such a claim as "Alice had signed the message when I got it.".

Examples of Public-Key Cryptosystems

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.


RSA (Rivest Shamir Adelman) is the another 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: To encrypt a message m, compute me mod n and send the result as ciphertext. To decrypt ciphertext c: m = cd mod n. RSA can also be used for digital signatures. To sign a message m: s = md mod n. To check a signature: m = se mod n.

A lot of number theory is needed to prove that this technique works. One necessary theorem is: m = (me 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.