Public-key encryption: two keys, two modes, six requirements

Two keys, and only one of them is a secret

Until 1976 every cipher in practical use was symmetric: one key, shared in advance, used to both lock and unlock. Diffie and Hellman's paper broke that assumption by proposing algorithms built on mathematical functions — properties of large integers — rather than on the substitution and permutation of bit patterns that symmetric ciphers are made of. That change of foundation is what makes the rest of this module possible.

A public-key scheme has five moving parts: the plaintext, the encryption algorithm, a matched pair of keys, the ciphertext, and the decryption algorithm. (You will see the ingredients counted as five or as six depending on whether the key pair is listed as one item or two — say which counting you are using and no marker can fault you.) The pair is the whole idea. Each user runs a generation procedure locally, publishes one key of the pair openly and never lets the other one leave the machine. Nothing secret is ever transmitted during setup, which is exactly what symmetric encryption cannot manage.

The four steps of the scheme, in order: (1) each user generates a key pair; (2) each user publishes one key — the public key — in an accessible register and keeps the other — the private key — private; (3) a sender who wants to reach Bob encrypts under Bob's public key; (4) Bob decrypts with his own private key, which nobody else has.

Worked example — Rina sends one message twice

Rina has a short message for Naseem: an account number. She sends it twice, once in each mode, and the two results behave completely differently.

Mode (a) — confidentiality. Rina looks up Naseem's public key and encrypts under it. The ciphertext can be reversed only by whoever holds the matching private key, and that is Naseem alone. So the message is confidential. What has Naseem learned about who sent it? Nothing at all. His public key is public; anyone in the world could have produced that ciphertext. Mode (a) gives confidentiality and no authentication whatsoever.

Mode (b) — authentication and integrity. Rina encrypts the same message under her own private key. Now anybody holding Rina's public key — that is, everybody — can reverse the transformation and read it. Mode (b) provides no confidentiality at all; the message might as well be in the clear. What it does provide is proof: the ciphertext reverses cleanly under Rina's public key only if it was produced with Rina's private key, and only Rina has that. And it would stop reversing cleanly if a single bit had been altered in transit. So mode (b) gives origin authentication and data integrity — this is the mechanism a digital signature is built on, and L5.6 picks it up there. In practice mode (b) is applied to a short hash of the message rather than the whole message, because public-key operations are expensive and the hash is enough to bind the content.

Both at once. Rina can compose the two: sign first with her private key, then encrypt the result under Naseem's public key. Naseem strips the outer layer with his private key and the inner layer with Rina's public key. That is four public-key operations for one message, and the cost is the reason nobody encrypts bulk data this way — see the digital envelope in L5.6.

The six requirements

Diffie and Hellman set out the conditions any candidate algorithm must satisfy:

1. It is computationally easy for a party to generate a matched key pair.
2. It is easy for a sender knowing the public key to produce the ciphertext.
3. It is easy for the receiver holding the private key to recover the plaintext.
4. It is computationally infeasible for an opponent who knows the public key to determine the private key.
5. It is computationally infeasible for an opponent who knows the public key and a ciphertext to recover the plaintext.
6. (Useful, not universal.) Either of the two keys can be applied first and the other one reverses it, in both directions.

Requirement 6 is the one that is optional, and it is precisely what makes signing-by-private-key possible. RSA has it. DSA does not — DSA can sign but cannot be run in the other direction to encrypt. That single asymmetry is why the capability grid in L5.5 is not all ticks.

Three things that are widely believed and all three are false

The textbook states these as errors because each one is the intuitive guess. First, public-key encryption is not inherently more resistant to cryptanalysis than symmetric encryption: security in both families is a function of key length and the work factor of the best known attack, and there is nothing about having two keys that raises that bar. Second, public-key encryption has not made symmetric encryption obsolete: the arithmetic is orders of magnitude more expensive per byte, so real systems use public-key crypto to move a symmetric key and symmetric crypto to move the data. Third, key distribution with public keys is not trivial: publishing a key openly invites anyone to publish a key claiming to be yours, so a protocol and a trusted third party are still required. That third misconception is the entire reason certificates and PKI exist.