Diffie-Hellman and RSA

Diffie-Hellman: Opening the Framework

The previous pages built the public-key idea as a specification and then named the hardness assumptions that might fill it, but exhibited no working system. The first system to realize the idea historically did not encrypt messages at all. It solved a narrower and, at the time, more urgent problem: how two parties who share no secret can agree on one over a channel an adversary is reading. This is the key-distribution problem that symmetric cryptography could not escape on its own, and the construction that broke it opened the public-key era.

The mechanism rests on a single asymmetry already in hand. In a finite cyclic group with generator \(\alpha\), raising \(\alpha\) to a power is cheap, while recovering the exponent from the result is the discrete logarithm problem, believed intractable in suitable groups. Two parties exploit this by each choosing a private exponent, publishing only the corresponding power, and combining what they receive with what they kept.

The structural novelty is that the shared secret is never transmitted and never chosen by either party alone. It emerges from the two private exponents jointly, and the commutativity \((\alpha^x)^y = (\alpha^y)^x\) is exactly what lets the parties arrive at the same value from opposite sides. This is a sharper departure from the trapdoor picture than it first appears. Knowing \(x\) reverses no public operation the adversary faces. The exponent \(x\) is simply the private contribution \(A\) holds back. Key agreement asks only that the parties reach a common value an eavesdropper cannot, and achieves this with a one-way function and the commutativity of exponentiation, with no trapdoor at all.

What stops the eavesdropper is precisely the problem named on the previous page. The adversary sees \(\alpha\), \(\alpha^x\), and \(\alpha^y\), and wants \(\alpha^{xy}\), which is exactly the Diffie-Hellman problem. The security of the agreement is the conjectured intractability of that problem, and the reduction established there bounds it from above. Since the Diffie-Hellman problem is no harder than the discrete logarithm, anyone who can take discrete logarithms in \(G\) recovers \(x\) from \(\alpha^x\) and computes the secret directly. The agreement is therefore secure only in groups where the discrete logarithm itself resists computation. The choice of group is not cosmetic but the entire basis of the guarantee.

That guarantee is also bounded in a second way, and naming the boundary now prevents a misreading later. Diffie-Hellman protects the secret against an adversary who only listens. It offers nothing against one who sits in the middle and substitutes messages. Such an adversary can run a separate agreement with each party, holding one shared secret with \(A\) and another with \(B\), and can relay and re-encrypt traffic while reading all of it. Neither party can detect the interposition from the protocol alone. The exchanged values carry no evidence of who sent them.

The same gap arises for public keys in general. Publishing a value removes the need to keep it secret but not the need to know whose it is. Closing the gap requires binding each transmitted value to an identity, a matter of authentication taken up on a later page. Against a passive adversary, the agreement solves key distribution completely.

Nothing in the construction used the integers modulo a prime specifically. It required only a finite cyclic group in which exponentiation is efficient and the discrete logarithm is hard, and any such group serves. The choice among them is a choice of where the hardness is most concentrated per unit of key length. Cryptographic practice favors the groups whose discrete logarithm resists attack most stubbornly for their size.

For now the framework has its first inhabitant: a working public-key construction, resting on a named hard problem, that establishes a secret with no secret shared in advance. What it does not yet do is encrypt. Supplying that is the contribution of the construction taken up next.

RSA: Filling in Encryption

Key agreement establishes a shared secret but transmits no message of the sender's choosing. The construction that followed closed that gap, realizing the other half of the public-key idea: encryption of an arbitrary plaintext under a published key. Where the previous construction needed no trapdoor, this one is built on a trapdoor one-way function in the literal sense, and it is the first concrete candidate for one. The forward map is easy for anyone, and the inverse is believed infeasible without a secret and is easy with it. The secret is precisely the private key. The hardness it draws on is the integer factorization problem.

The scheme is assembled from modular exponentiation in a way that makes the exponents undo one another exactly when the modulus is a product of two primes. We state the construction, then prove it decrypts correctly.

The trapdoor structure is visible in the keys. The forward map \(m \mapsto m^e \bmod n\) is published in full as \((n, e)\), while the inverse \(c \mapsto c^d \bmod n\) requires \(d\). An adversary holding only \((n, e)\) cannot compute \(d\) without, in effect, factoring \(n\), and the next section makes this dependence precise. That the two exponentiations genuinely invert one another is not assumed but follows from the choice of \(d\), which we now prove.

The proof exposes why the modulus must be a product of distinct primes rather than an arbitrary integer. The exponent arithmetic that makes \(e\) and \(d\) inverse runs in each prime factor separately, and the recombination is exactly the splitting of the modulus into coprime parts. What an attacker would exploit by factoring is the same splitting that makes correctness work, so the structure serving the legitimate user and the structure exposed to the adversary are one and the same. The next section examines this tension.

One caution carries over from the framework and must not be skipped. The map \(m \mapsto m^e \bmod n\) is a fixed function, so a given plaintext always produces the same ciphertext. Applied directly, it is a deterministic encryption, and the page defining security ruled out deterministic public-key encryption. Equal plaintexts yield equal ciphertexts, and an adversary who can encrypt candidate plaintexts can match them against an observed ciphertext. That failure is what randomized encryption exists to repair.

The trapdoor function is the primitive. A secure scheme wraps it with fresh randomness at encryption time, so that the hard-to-invert core is preserved while the plaintext-to-ciphertext map becomes one-to-many. Textbook RSA, the bare exponentiation above, is the trapdoor, not yet the scheme deployed in practice, and the gap between the two is filled by structured randomized padding rather than by any change to the arithmetic just proved.

What RSA's Security Rests On

A passive adversary against RSA holds the public key \((n, e)\) and a ciphertext \(c = m^e \bmod n\), and wants the plaintext \(m\). Recovering \(m\) from \(c\) under \((n, e)\) is the RSA problem, and no efficient algorithm for it is known. The question this section settles is how that problem relates to the factoring of \(n\), since the scheme was introduced as resting on factoring and the precise nature of that dependence is easy to overstate.

One direction is clear and complete. If an adversary can factor \(n\), it recovers \(p\) and \(q\), forms \(\phi = (p-1)(q-1)\) exactly as the key generator did, and computes \(d\) from \(e\) by the same modular inversion. With \(d\) in hand it decrypts every ciphertext. So the ability to factor breaks the scheme outright, and RSA can be no harder to break than \(n\) is to factor.

The reverse direction is the subtle one, and it must be stated in two steps that are often collapsed into one. The first step concerns not the plaintext but the private exponent. Recovering \(d\) from the public key is exactly as hard as factoring \(n\).

This equivalence is exact, but it is an equivalence about \(d\), not about \(m\). The second step, relating the recovery of a plaintext to factoring, is where the honest account must stop short. It is not known whether the RSA problem is as hard as factoring. An adversary might conceivably recover \(m\) from \(c\) without ever computing \(d\) or factoring \(n\), by some route that exploits the specific structure of the map \(m \mapsto m^e\). No such route has been found, but none has been ruled out. The scheme's security therefore rests on the hardness of factoring without being equivalent to it. Factoring breaks RSA, and recovering \(d\) is exactly factoring, but whether breaking RSA requires either remains open. Stating the dependence as an equivalence would claim a theorem that does not exist.

Granting that the core problem is hard, a scheme can still be defeated through how it is used rather than through the problem it rests on. These usage failures do not contradict the hardness of factoring. What they show is that hardness of the underlying problem is necessary but not sufficient for a secure deployment. Each identifies a discipline that correct use must observe, and the disciplines are permanent even as the individual attacks are refined.

Small-exponent and small-message exposure. A small encryption exponent such as \(e = 3\) speeds up encryption but creates two exposures. If the message is small enough that \(m^e \lt n\), the modular reduction does nothing and \(m\) is recovered by an ordinary integer root of the ciphertext. If the same message is sent to \(e\) recipients under the same exponent and pairwise coprime moduli, the splitting used in the correctness proof combines their ciphertexts into \(m^e\) modulo the product of the moduli, which exceeds \(m^e\), and the same integer root recovers \(m\). The fix is not a larger exponent but the randomized padding already required for semantic security, since padding destroys the algebraic relationships these attacks exploit.

Forward search over a small message space. Because the encryption map is public, an adversary facing a message drawn from a small or guessable set can encrypt every candidate and compare against the observed ciphertext. This is the deterministic-encryption failure in its starkest form, and randomized padding again answers it, since re-encrypting a guessed plaintext then almost never reproduces the target ciphertext.

The multiplicative structure. RSA respects multiplication. The product of the encryptions of \(m_1\) and \(m_2\) is the encryption of \(m_1 m_2\), since \((m_1 m_2)^e \equiv m_1^e m_2^e \pmod{n}\). An adversary can exploit this to have a disguised ciphertext decrypted and then strip the disguise, an adaptive chosen-ciphertext attack that the bare scheme does not withstand. The defense is to require plaintexts to carry a rigid structure that a tampered ciphertext will almost surely fail to produce, so that malformed decryptions are rejected. That rigidity is once more a property supplied by structured padding, not by the arithmetic.

A shared modulus. If several parties were issued distinct exponent pairs under one common modulus \(n\), the equivalence just proved would be fatal. Any single party, knowing its own \((e_i, d_i)\), could factor \(n\) and then compute every other party's private exponent. A modulus can belong to exactly one party. This is a direct corollary of the equivalence theorem rather than a separate phenomenon, and it is why key generation produces a fresh modulus per user.

None of these failures touches the hardness of factoring. Each is a requirement on construction around a core that is assumed hard. And that assumption carries a qualification that earlier pages have already attached to it. The hardness of factoring is hardness against classical computation, the model under which every algorithm in this section was reckoned. The padding disciplines above secure RSA against an adversary confined to that model. No choice of key length secures it against a model in which factoring itself becomes easy. What such a model does to RSA and to the key agreement of the first section, and why the two fall together, is the final matter.

Built on Factoring and Logarithms

The two constructions of this page descend from the two oldest hardness assumptions, one each. Key agreement rests on the discrete logarithm, since an eavesdropper who could take logarithms would read every shared secret. Encryption rests on factoring, since an adversary who could factor would recover every private exponent. The abstract problems named on the previous page have become two working systems, and the systems inherit not only the hardness of those problems but their fragility.

That fragility is shared, and the sharing is not a coincidence of history but a fact about the algebra. Both problems live in finite abelian groups: a finite cyclic group for the discrete logarithm, the multiplicative structure modulo \(n\) for factoring. The difficulty in each case is that of recovering hidden information about a periodicity in that group. A quantum computer running Shor's algorithm finds such periods efficiently, and so solves both problems in time polynomial in the input size, the discrete logarithm in any cyclic group whose operation can be computed efficiently. The single algorithmic advance that breaks the one breaks the other, because they were never as different as their statements suggest. Both are faces of one underlying structure, and a method that exploits that structure does not distinguish between them.

For the constructions of this page the consequence is immediate and total. Against an adversary with a large-scale quantum computer, factoring \(n\) becomes feasible, so the private exponent \(d\) is recovered by the equivalence proved above and RSA is decrypted at will. In the same setting the discrete logarithm becomes feasible, so the private exponents in a key agreement are recovered and the shared secret with them.

Moreover, the collapse does not stop at the discrete logarithm. The reduction of the previous page runs the difficulty downward, so an algorithm that takes logarithms also solves the Diffie-Hellman problem directly. Every construction resting anywhere in that chain of hardness falls at once. None of the padding disciplines of the previous section helps, because none of them touches the hardness of the core problem. The disciplines guard the construction within the classical model and have nothing to say once the model itself changes.

The reach of this attack is sharp but bounded. What Shor's algorithm exploits is the hidden abelian structure these two problems share. Cryptographic constructions that do not rest on that structure are not broken by it. Symmetric-key ciphers and hash functions face only a generic quantum search that halves the effective key length. That erosion is answered by doubling keys, not by abandoning the design. So the event on the horizon is not the end of cryptography but the obsolescence of one family within it: the public-key constructions of this page, and the number-theoretic assumptions beneath them, whose security has a known expiry condition rather than an indefinite future.

This is why the search for a successor does not look for a better factoring-based scheme or a harder instance of the discrete logarithm. A harder instance of the same problem is still an instance of the same problem, and falls to the same algorithm. The replacement must rest on a hardness that does not reduce to a hidden abelian period. It needs a problem for which no efficient quantum algorithm is known and to which factoring and the discrete logarithm do not connect by any known reduction.

One family of candidates comes from the geometry of high-dimensional lattices, where finding a shortest or nearest vector appears to resist classical and quantum attack alike. Moving there means leaving the arithmetic of primes and exponents that has carried public-key cryptography from its first key agreement to its first cipher, and rebuilding key agreement and encryption on ground a quantum computer does not level. The framework of the earlier pages carries over unchanged, including what it means to encrypt, to agree on a key, and to be secure against a bounded adversary. Only the hard problem at the center is exchanged.