Hardness Is Not a Single Assumption: What the Problems Behind RSA and Diffie-Hellman Really Promise

Ask an engineer why RSA is secure and the answer is usually one word: factoring. Ask about Diffie-Hellman and the answer is discrete logarithms. Both answers are true in the way a building's address is true: they tell you where to look, not what holds the roof up. The security of a deployed RSA or Diffie-Hellman system is a stack of separate claims. There is the mathematical problem an attacker would need to solve, and there are usually several candidate problems, related in ways that are only partly understood. There is the cost of the best known algorithm for that problem, which depends on structure the attacker can exploit and on whether work can be shared across targets. There is a security reduction that connects the problem to the scheme, valid only inside a model with its own idealisations. And there is the implementation and deployment, which must actually behave like the object the proof described. This article takes that stack apart. Its claim is simple and, once stated, hard to unsee: the phrase 'hardness assumption' names at least five different things, and the history of classical public-key failures is mostly a history of attacks on the layers that are not the hard problem at all.

Two families of problems, not two problems

Begin with definitions. An RSA public key consists of a modulus, the product of two secret primes, and a public exponent; the private exponent inverts exponentiation by the public one on the clock of that modulus (Rivest, Shamir and Adleman, 1978). Four problems live near this construction. The factoring problem asks for the primes given the modulus. The RSA problem asks, given the modulus, the public exponent and a target value, for the number that raised to the public exponent gives the target, that is, an inversion of the public operation on one value without necessarily learning the private key. The strong RSA problem lets the solver choose the exponent as well as the root, and is used in some signature constructions. Finally there is the decisional question of whether a value is an RSA image of some structured input, which matters for certain encryption proofs.

The Diffie-Hellman side has its own family (Diffie and Hellman, 1976). Fix a cyclic group, for example a prime-order subgroup of the nonzero numbers modulo a prime, and a generator of it. The discrete logarithm problem asks for the exponent behind a given group element. The computational Diffie-Hellman problem asks, given the generator raised to two unknown exponents, for the generator raised to their product, which is the shared secret of a key exchange. The decisional Diffie-Hellman problem asks only to distinguish that shared secret from a uniformly random group element. Variants such as the gap Diffie-Hellman problem give the solver a decisional oracle and ask it to solve the computational problem.

The relationships between members of each family are asymmetric. Anyone who can factor can invert RSA, because factoring yields the private exponent. Whether the converse holds, whether inverting RSA is as hard as factoring for the exponents used in practice, has never been proved, and the question has remained open since the scheme was published. Likewise, solving discrete logarithms solves the computational problem, and solving the computational problem solves the decisional one, but the reverse implications are known only under additional conditions on the group, and in some groups the decisional problem is easy while the computational problem is believed hard. A statement such as 'RSA is as hard as factoring' is therefore not a theorem; it is shorthand for an unproved and probably non-uniform belief.

The practical consequence, in this article's synthesis, is that every security claim should name its problem precisely. A key-encapsulation argument that needs the shared secret to be indistinguishable from random is resting on the decisional problem, the most fragile member of its family, not on discrete logarithms.

A worked gap between the computational and decisional problems

The distance between neighbouring problems is easiest to see in a toy group. Take arithmetic modulo the prime 23 with generator 5, which generates all 22 nonzero residues. Exactly half of those residues are quadratic residues, meaning squares of something, and a power of the generator is a square exactly when its exponent is even. Squareness is efficiently testable by anyone using Euler's criterion. Every public value in a key exchange in this group therefore leaks the parity of its secret exponent, and an observer can predict whether the shared secret is a square: it is, unless both secret exponents are odd. The shared secret is consequently distinguishable from a uniformly random element, so the decisional problem is easy, while computing the shared secret, and recovering the exponents, remain exactly as hard as they were.

The general mechanism is that every small factor of the group order supplies a homomorphism onto a small group, and each such map leaks the secret exponent modulo that factor. In the toy group the factor is 2. The established cure is to work in a subgroup of large prime order; in the same toy setting, the generator 2 produces a subgroup of order 11 in which every element is a square and the leak disappears. This is the reason for the safe-prime and prime-order-subgroup constructions in key-establishment standards such as NIST SP 800-56A.

Protocol design offers a second, complementary escape. When the raw shared secret is passed through a key derivation function before use, the resulting keys can be argued secure from the computational problem, under an idealised model of the hash, rather than from the decisional one. This article reads that as one of the quieter reasons modern protocols never use a Diffie-Hellman output directly as key material: hashing moves the argument down one rung, to a sturdier assumption.

Attack cost: generic algorithms versus structure

The second layer is how expensive the best attack is, and that depends on what structure the attacker can exploit. Generic algorithms treat the group as a black box that can only multiply and compare elements. For any such algorithm, the cost of a discrete logarithm grows roughly with the square root of the size of the largest prime-order subgroup involved; Pollard's rho method attains this bound with negligible memory. If the group order factors into small primes, the problem splits into independent subproblems, one per factor, and the cost collapses to that of the largest factor. That is why parameter standards demand a large prime-order subgroup and not merely a large modulus.

Groups built from the integers modulo a prime have far more structure than a black box. Their elements can be lifted to ordinary integers, tested for smoothness, meaning whether they factor into small primes, and related to one another through those factorisations. The number field sieve exploits that structure (Lenstra, Lenstra, Manasse and Pollard; developed through the early 1990s). It is the fastest known classical method both for factoring RSA moduli and for discrete logarithms in finite fields, and its running time is subexponential in the bit length: faster than any generic method, slower than polynomial. The same sieve underlies both families, which is why RSA and finite-field Diffie-Hellman share the same parameter curve, roughly 3,072 bits for 128-bit security.

Well-chosen elliptic curves are the counterexample. No algorithm better than the generic square-root bound is known for the discrete logarithm on curves without special structure, so a curve of about 256 bits gives about 128-bit security. This is a statement about the current state of cryptanalysis, not a proof of hardness, but it has held for curves such as those in RFC 7748 and the NIST curves since their adoption.

Precomputation: when a per-target cost becomes a shared one

Attack cost is usually quoted per target. For finite-field discrete logarithms that framing is misleading, because the expensive stages of the number field sieve depend only on the prime modulus. Once an attacker has completed them for a given prime, each individual logarithm in that group, and therefore each key exchange that used it, requires only a comparatively short descent step. Adrian and colleagues made this concrete in their 2015 analysis of Diffie-Hellman in practice. They demonstrated the full computation for 512-bit export-grade primes, showed that an active attacker could downgrade some connections to those primes, and observed that a large fraction of servers relied on a small number of shared 1,024-bit primes, estimating that a precomputation for one such prime, though far beyond academic resources, could be within reach of a nation-state.

The structural lesson, in this article's reading, is that a hardness estimate must state its amortisation model. A parameter that is adequate against an attacker who must start from scratch for each victim can be inadequate against one who pays once and harvests many. Factoring offers no comparable per-prime sharing across different RSA moduli, since each modulus is a separate problem; the RSA analogue of shared structure arises instead from flawed key generation, a separate failure class with its own population evidence. Elliptic-curve discrete logarithms, attacked only generically, likewise lack a known reusable precomputation of this kind at standard sizes.

Named groups are not thereby discredited. They remove the much larger risk of weak or malformed custom parameters. The correct response is to size named finite-field groups for the amortised adversary, which is part of why 2,048 bits became the minimum, and to prefer elliptic-curve key agreement where the ecosystem allows.

What a reduction certifies, and what it cannot

The third layer is the security reduction. A reduction is a conditional statement with a precise shape: if some adversary breaks the scheme with a given advantage, in a given amount of time and with a given set of oracles, then an algorithm built from it solves the hard problem with a related advantage and time. Three properties of that statement matter. Its tightness, the ratio between the two advantages and times, determines how much of the problem's hardness actually transfers; a loose reduction may require far larger parameters than the scheme is deployed with before it says anything at all. Its model may include idealisations, most prominently the random oracle model, in which a hash function is treated as a truly random function; the RSA-OAEP and RSA-PSS security arguments referenced in RFC 8017 are stated in that model. And its oracle set defines exactly which interactions with the honest party the adversary is assumed to have.

The oracle set is where this article locates most of the gap between proofs and practice. A proof of chosen-ciphertext security grants the adversary a decryption oracle that answers in a particular way; it says nothing about an implementation that additionally reveals why a decryption failed. Bleichenbacher's 1998 attack and its 2018 resurgence documented by Böck, Somorovsky and Young both arose from such extra signals in deployments of RSA encryption padding. Kocher's 1996 timing attacks and the fault analysis of Boneh, DeMillo and Lipton (1997) likewise exploit signals, time and erroneous outputs, that no reduction in the standard model accounts for. None of these attacks touched the hardness of factoring.

A reduction is therefore best read as a certificate with an explicit scope: under this assumption, in this model, against an adversary who sees only these interfaces, at this loss. Everything outside the scope has to be argued separately, usually by implementation evidence rather than mathematics.

CLAIM  scheme S is secure against adversary class C
GIVEN  any adversary A in C that breaks S
       with advantage eps, time t, using oracles O
BUILD  algorithm B that runs A as a subroutine
       and solves problem P with advantage eps', time t'
READ   tightness  = how eps', t' compare to eps, t
       model      = standard, or random oracle, or other idealisation
       scope      = exactly the oracles in O; nothing else
ASK    does the deployed system expose anything outside O?

A five-layer model of a classical security claim

Putting the layers together yields the main contribution of this article: a five-layer model for stating, and reviewing, any classical public-key security claim. Layer one is the named hardness assumption, chosen precisely from its family. Layer two is the concrete attack cost under the best known algorithm, stated together with its amortisation model. Layer three is the reduction, with its tightness, model and oracle scope. Layer four is implementation conformance: evidence that the code exposes no interface beyond that scope, which covers error uniformity, timing behaviour, fault handling and input validation. Layer five is deployment: parameter selection, negotiation and downgrade resistance, key generation and key handling.

Each layer can fail independently, and a failure at any layer voids the claim regardless of the others. Read against that model, the historical record is striking. Export-grade and shared-prime weaknesses were layer two and five failures. Padding oracles, timing leaks and fault-induced key recovery were layer four failures, outside every reduction's scope. Weak key generation is a layer five failure. Cases in which the named hard problem itself was solved at deployed sizes are rare by comparison. This is a synthesis of the public record rather than a measurement, but its direction is consistent across the incidents cited here.

The model also clarifies what quantum computing changes and what it does not: a large-scale quantum computer would collapse layer one for all of these problems at once, but every other layer would carry over unchanged to post-quantum replacements, which is why the discipline matters beyond the classical era.

1. Assumption: which member of which family, in which group.
2. Cost: best known algorithm and whether its work is shared across targets.
3. Reduction: tightness, idealised model, and the oracles the adversary is granted.
4. Implementation: evidence that nothing beyond those oracles is exposed.
5. Deployment: parameters, negotiation and key lifecycle as actually configured.

Implications for AI agent platforms

An AI agent platform inherits every layer of this stack many times over. Each call from an agent to a tool server, model endpoint or peer agent begins with a key agreement and usually a signature verification, each with its own assumption, parameters, proof scope and implementation. The agent's own identity is often an RSA or elliptic-curve key whose security claim is no stronger than its weakest layer. Platforms that treat 'uses TLS' or 'uses RSA-2048' as the whole security statement are, in the terms of this article, asserting layer one and silently assuming the other four.

Two agent-specific pressures make the lower layers more fragile. Agents and the code assistants that build their integrations generate cryptographic glue code at scale, and such code tends to expose exactly the out-of-scope interfaces that reductions ignore: detailed error messages, unvalidated inputs and non-constant-time comparisons. And agents operate at machine speed and volume, which turns marginal oracles, the kind that require many queries, into practical ones. The defensive implication is to make the five-layer record an explicit artefact for every cryptographic dependency an agent platform relies on, and to review generated code against layer four rather than against the name of the algorithm it calls.

Limitations and open questions

This article offers a structured synthesis, not new cryptanalysis or measurement. Statements about attack costs reflect the published state of the art and may change with algorithmic progress. The equivalence questions it describes, between factoring and RSA inversion and between the discrete-logarithm problems, are genuinely open in general, and the article does not claim more than that. The five-layer model is a review aid; it does not replace formal analysis of composite protocols, whose security proofs involve many interacting assumptions beyond those discussed here.

Two questions remain open in a practical sense. The first is how to express amortisation honestly in published security levels, so that a parameter's rating states the adversary model it assumes. The second is how to produce machine-checkable evidence for layer four, so that conformance to a reduction's oracle scope can be verified for generated code at the speed that agent ecosystems produce it.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

key_agreement:
  allow: [X25519, P-256, ffdhe3072, ffdhe4096]
  deny:  [custom_groups, export_grade, groups_below_2048_bits]
  require: [full_transcript_signature, peer_value_validation]
signatures:
  allow: [Ed25519, ECDSA-P256-deterministic, RSA-PSS-3072]
  deny:  [RSA_below_2048, unpadded_RSA]
review:
  record_five_layers: true
  generated_crypto_code: vetted_library_calls_only

Glossary

RSA problem

Given an RSA public key and a target value, find the root whose public-exponent power equals the target.

Computational Diffie-Hellman

Given a generator raised to two secret exponents, compute the generator raised to their product.

Decisional Diffie-Hellman

Distinguish the true Diffie-Hellman shared value from a uniformly random group element.

Generic algorithm

An algorithm that uses only group operations and equality tests, with no knowledge of how elements are represented.

Number field sieve

The fastest known classical algorithm for factoring and finite-field discrete logarithms, with subexponential running time.

Amortisation

Spreading a large one-time cost across many targets so that each additional target is cheap.

Security reduction

A proof that any adversary breaking a scheme yields an algorithm solving an underlying hard problem.

Tightness

How closely a reduction preserves the adversary's advantage and running time.

Random oracle model

An idealised proof setting in which a hash function is treated as a truly random function.

References

1. R. L. Rivest, A. Shamir, L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, 1978
2. W. Diffie, M. Hellman, New Directions in Cryptography, IEEE Transactions on Information Theory, 1976
3. A. K. Lenstra, H. W. Lenstra Jr. (eds.), The Development of the Number Field Sieve, Lecture Notes in Mathematics 1554, Springer, 1993
4. D. Adrian et al., Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice, ACM CCS 2015
5. RFC 8017: PKCS #1: RSA Cryptography Specifications Version 2.2 (IETF)
6. NIST SP 800-56A Rev. 3: Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography
7. RFC 7748: Elliptic Curves for Security (IETF)
8. P. C. Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, CRYPTO 1996
9. D. Boneh, R. A. DeMillo, R. J. Lipton, On the Importance of Checking Cryptographic Protocols for Faults, EUROCRYPT 1997