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.
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:
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.
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:
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.
We can borrow a physical analogy (from The Code Book) to better understand the principles underlining Diffie-Hellman key exchange. Consider the following:
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.
A adds to her 1 liter of yellow paint a secret color S_{A}. B also adds to his 1 liter of yellow paint a secret color S_{B}.
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 + S_{A} + S_{B} (Y:Y:S_{A}:S_{B}).
A adds S_{A} to B's pot. The result
(Y:S_{A}:S_{B}) is the key.
B adds S_{B} to A's pot. The result
(Y:S_{B}:S_{A}) is the key.
Notice: A and B have computed the same key, but E gets a different one.
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".
(United States)
(United Kingdom)
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:
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.".
We will now examine a few examples of public key cryptography systems.
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.
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.
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.