Public-Key Cryptography

Two Keys Instead of One

Every scheme worked through so far, from the substitution cipher to the one-time pad, has shared one feature. In each, the party who encrypts and the party who decrypts hold the same secret. An encryption scheme pairs each encryption key \(e\) with a decryption key \(d\), and in the schemes seen until now the two are, for practical purposes, the same object. Whoever can lock can also unlock. Such a scheme works whenever the two parties already share a secret, and its security rests entirely on keeping that shared secret from everyone else.

The difficulty is not in the encryption but in arriving at the shared secret. Before any message can be sent, the two parties must agree on a key that no one else knows. That agreement must itself travel over some channel. If they could already send secret messages to each other, they would not need the scheme. The very thing the key is meant to provide is what its establishment seems to require. Two parties who have never met, communicating only over a channel an adversary controls, cannot use a symmetric scheme until they have somehow shared a key in advance. This is the key-distribution problem, and for symmetric cryptography it is unavoidable, because confidential communication presupposes a secret already held in common.

The resolution is to break the symmetry. Suppose the key that encrypts and the key that decrypts are genuinely different. Suppose further, and this is the decisive condition, that knowing the encryption key gives no feasible way to find the decryption key. Then the encryption key need not be secret at all. Its owner can publish it: print it, broadcast it, hand it to the adversary directly. Anyone may use it to encrypt, but only the holder of the matching, undisclosed decryption key can recover what was encrypted. The secret that symmetric cryptography had to transport in advance never needs to travel.

The asymmetry rearranges the assumptions under which symmetric schemes operate. Because it is not secret, the public key travels over an unsecured channel, the same one the ciphertext travels on. Any party who obtains it can send confidential messages to its owner that only the owner can read. The owner publishes one key and receives from many. Once the encryption key needs no protection in transit, the regress that made key distribution circular is cut. Nothing secret has to be distributed in order to begin.

What this demands, in exchange, is a mathematical object that does not obviously exist. It is a transformation easy to apply and infeasible to reverse, yet equipped with a secret that makes reversal easy after all. The next section names that object and states the property it must have.

Trapdoor One-Way Functions

The public-key idea asks for a transformation with two properties that pull against each other. The transformation must be easy to compute in the forward direction, so that anyone holding the public key can encrypt. It must also be infeasible to invert, so that an adversary who holds the same public key, and with it the same forward transformation, still cannot decrypt. A transformation with these two properties alone is called one-way: easy to compute, infeasible to invert.

A one-way function by itself is not yet enough, because the legitimate receiver must be able to invert it. If inversion were infeasible for everyone, the ciphertext would be unreadable even by its intended recipient. What the receiver has that the adversary does not is the private key, and the transformation must be built so that this one extra piece of information collapses the infeasible inversion into an easy one. A one-way function carrying such a secret shortcut is a trapdoor one-way function: infeasible to invert in general, easy to invert for whoever holds the trapdoor.

The trapdoor one-way function is the core from which a public-key scheme is built, supplying the one-way map and the secret that reverses it. The public key \(e\) specifies the forward direction \(f(x)\), easy for anyone to compute, while the private key \(d\) is the trapdoor that makes the otherwise infeasible inversion easy for its holder alone. The previous section's requirement that \(d\) cannot be recovered from \(e\) is a consequence of the one-wayness of the forward map, since whoever recovered \(d\) could invert. One-wayness asks for more. Even an adversary who never learns \(d\) must be unable to compute the inverse from \(e\) alone, for otherwise \(d\) would be redundant and the trapdoor no secret.

The trapdoor function is the primitive, not yet the scheme. Evaluated directly as a fixed map, it is deterministic, so a given input always yields the same output. Deterministic encryption is exactly what the previous page ruled out. Equal plaintexts would produce equal ciphertexts and leak the structure that randomized encryption was introduced to hide.

A secure public-key scheme therefore does not encrypt by applying the trapdoor function to the plaintext alone. It combines the function with fresh randomness at encryption time, so that the trapdoor supplies the hard-to-reverse core while the randomization supplies the one-to-many map that conceals plaintext structure. The trapdoor function makes public-key encryption possible. Randomization is what any secure use of it additionally requires. How that combination is carried out concretely belongs with the specific constructions taken up later. Here it is enough that the primitive and the security requirement of the previous page are not in tension. One is the engine, and the other is the discipline imposed on its use.

Whether trapdoor one-way functions exist at all is not settled by the definition, which only says what such an object would be. Their existence rests on the presumed hardness of specific computational problems. The pages that follow exhibit concrete functions and the number-theoretic problems whose conjectured intractability supplies their one-wayness. For now the framework stands on the assumption that such functions can be built, and the question this page pursues is structural: granted the public-key construction, how does it compare with the symmetric schemes it does not replace?

Symmetric and Public-Key Compared

Public-key cryptography removes the obstacle that defines symmetric cryptography, the need to share a secret before communicating. It does not, however, make symmetric schemes obsolete. The two carry complementary strengths, and a clear account of where each wins explains why a system would use both rather than choose one. The comparison runs along three axes: how the keys are managed, how fast the scheme runs, and how long the keys must be.

Key management. A symmetric scheme requires the key to stay secret at both ends, and a fresh secret for each pair of communicating parties. A network of \(n\) parties who must all communicate confidentially in pairs therefore needs on the order of \(n^2\) separately guarded keys, every one of them a secret that had to be distributed in advance. A public-key scheme requires only the private key to stay secret, and each party holds just one. The matching public keys are published. The number of secrets to guard drops from one per pair to one per party. What public-key management demands instead is the authenticity of the public key rather than its secrecy. The scheme does not supply that authenticity for free, and the end of this section isolates the problem.

Speed. Symmetric schemes are fast. Their operations are simple transformations on blocks of data, and they sustain high throughput in hardware and software alike. Public-key schemes are slow by comparison. Evaluating a trapdoor one-way function is an arithmetic operation on large structured objects, orders of magnitude more costly per unit of data than a symmetric transformation. The gap is not incidental. It follows from the kind of mathematical structure a trapdoor requires, and it decides how the two are combined.

Key length. For a well-designed symmetric scheme the best available attack is exhaustive key search, so the key need only be long enough to put brute force out of reach. A public-key scheme, by contrast, ties its security to a structured computational problem, and that structure tends to open attacks better than trying every key. Such attacks are shortcuts that exploit the very algebraic regularity the trapdoor is built from. Where such a shortcut exists, the keys must be made substantially longer than a symmetric key of equivalent security to absorb it. The key length is set against the best known attack on the underlying problem, not against brute force alone. The richer structure that makes a trapdoor possible is, in general, structure an attacker can also work with, and a longer key is the recurring price of relying on it.

One asymmetry in this comparison needs care, because it is a weakness the public-key idea creates rather than one it dissolves. Publishing a key removes the burden of keeping it secret, but it introduces the burden of being sure whose key it is. An adversary who can intervene actively on the channel may substitute its own public key for the intended recipient's, so that messages a sender believes are encrypted for the recipient are in fact encrypted for the adversary, who decrypts, reads, re-encrypts under the true public key, and forwards them. This deception breaks confidentiality without breaking the encryption at all.

The defense is not secrecy of the public key, which by design it lacks, but assurance of its origin. The sender must be convinced that the published key truly belongs to the intended recipient. Supplying that assurance means binding a public key to an identity. This is a problem of authentication rather than encryption, and the machinery that addresses it is taken up on a later page.

The Hybrid Construction

The complementarity of the two profiles suggests its own resolution. Their weaknesses do not overlap, so used together each supplies exactly what the other lacks. Public-key encryption establishes a key over an open channel. Symmetric encryption then protects the data at high speed.

The combination is direct. To send a large message confidentially, the two parties first use the public-key scheme to establish a shared symmetric key. It is a short secret used only for this exchange, and only the recipient's private key can recover it. The bulk of the message, however long, is then encrypted under the fast symmetric scheme using that key. What travels is the symmetric key, encrypted under the recipient's public key, together with the message body sealed by the symmetric scheme. The recipient recovers the symmetric key with the private key and then decrypts the body.

The slow public-key operation runs only on the short symmetric key, never on the bulk data, so its cost is a fixed overhead independent of message length. The fast symmetric scheme carries the volume. The construction inherits the key-distribution solution of public-key encryption and the throughput of symmetric encryption, and pays the public-key price only once per exchange rather than per byte. This division of labor, in which public-key cryptography establishes a key and symmetric cryptography protects the data, uses each primitive only where its profile is strong.