Key Size Equivalence Across RSA, Diffie-Hellman, and Curves

A 256-bit elliptic curve key and a 3072-bit RSA key are commonly described as offering the same security. The claim is not a marketing simplification; it follows from the asymptotic cost of the best known algorithm against each family. Understanding where the numbers come from makes it possible to judge when they apply and when a table is being misread.

Two different hard problems with two different best algorithms

RSA and finite-field Diffie-Hellman both rest on problems in multiplicative groups of integers modulo a composite or a prime. Elliptic curve cryptography rests on the discrete logarithm in a group of points. All three are believed hard, but the best algorithms differ.

Integer factorization and finite-field discrete log. The number field sieve has subexponential complexity. Its cost for a modulus of $N$ bits is commonly written as

$$L_N\left[\tfrac{1}{3}, 1.923\right] = \exp\left(1.923 , N^{1/3} (\ln N)^{2/3}\right)$$

with the constants depending on the variant and on whether the problem is factoring or discrete log. The expression is not a clean power of $N$, so the security does not double when the key length doubles; it grows faster than any polynomial and slower than exponential. This is why RSA key sizes increase in steps of roughly a factor of two in bits for each increment of security: 1024, 2048, 3072, 7680, 15360.

Elliptic curve discrete log. No subexponential algorithm is known for a generic elliptic curve group. The best general-purpose attacks are the generic ones — Pollard’s rho and its parallel variant — with cost about $\sqrt{q}$ for a subgroup of prime order $q$. A 256-bit curve with prime order therefore costs about $2^{128}$ group operations, and that is the security level.

The comparison follows: an RSA modulus needs enough bits that the number field sieve costs $2^{128}$, and that turns out to be around 3072 bits. The equivalence is between the cost of the best attack, not between key lengths.

The table, and how to read it

Security level (bits)	RSA / finite-field DH modulus	Elliptic curve group order
80	1024	160
112	2048	224
128	3072	256
192	7680	384
256	15360	512

The pattern is close to a constant ratio of about 12:1 for RSA bits to curve bits at the 128-bit level, but the ratio is not constant — it grows slowly as the level increases, because the sieve’s subexponential cost means each added bit of RSA security costs more RSA bits than the previous one. A table read as “RSA keys are always twelve times longer” is wrong at the high end.

Two caveats on the table. First, the finite-field Diffie-Hellman column assumes a prime of the given size with a large prime-order subgroup. A 2048-bit prime whose order is smooth offers nothing like 112 bits, as described in Discrete Logarithms and Why Group Order Decides Their Difficulty. Second, the elliptic curve column assumes a curve with prime order, or a prime-order subgroup, and no special structure. A curve of the right size but with a smooth order is broken by Pohlig-Hellman.

There is also a class of finite-field groups where the number field sieve does not apply and the situation is different: the multiplicative group of a field of small characteristic, where the function field sieve is dramatically faster. Those groups are avoided entirely in standards, and the reason is that the equivalence table’s finite-field column does not hold for them. The table is a statement about prime-field groups, not about all groups of that size.

Why elliptic curves win on more than size

The key-size advantage is the headline, but three other differences matter operationally.

Bandwidth. A 256-bit curve public key is 64 bytes encoded uncompressed (32 for the x-coordinate, 32 for the y) or 33 bytes compressed. A 3072-bit RSA public key is 384 bytes plus encoding overhead. For a protocol that carries certificates in every handshake, the difference is paid on every connection, and it matters most where bandwidth is scarce or where the handshake must fit in a small number of packets.

Computation. The scalar multiplication for a 256-bit curve is a few thousand field multiplications over 4-limb numbers. The 3072-bit modular exponentiation is thousands of multiplications over 48-limb numbers. The per-operation gap is large, and it is the reason a server can handle more ephemeral key exchanges per second with curves than with finite-field groups. The arithmetic is laid out in Elliptic Curve Point Arithmetic and Validation.

Key generation. Generating an RSA key requires finding two large primes and running primality tests, which takes noticeable time and needs a good random source throughout. Generating an elliptic curve key is drawing a random scalar and multiplying the base point, which is a single scalar multiplication. The cost difference matters for protocols that generate keys frequently, and it removes the temptation to cache keys that should be fresh.

The counterweights are real too. RSA verification is cheaper than a curve scalar multiplication because the public exponent is sparse — a few thousand times cheaper in limb operations — so for a workload dominated by signature verification with a fixed key, RSA has an edge on the public side. Curves have no equivalent sparse-scalar trick that is safe; a small scalar would be as insecure as a small RSA private exponent.

Where the numbers stop being the whole story

Key size equivalence compares the cost of the best known classical algorithm. It says nothing about implementation quality, and in practice implementations fail more often than the mathematics does.

A curve implementation that uses a non-constant-time scalar multiplication leaks the key regardless of the curve size. An RSA implementation with a faulty CRT recombination leaks the factorization. A protocol that accepts an unvalidated group element is broken at any key size. The equivalence table is a statement about the primitive; it is not a statement about a system.

There is also the question of what happens if the underlying problem turns out to be easier than believed. The number field sieve’s complexity is not proven optimal, and improvements to it have reduced the effective key sizes over time: the 512-bit RSA challenge was factored in 1999, and the estimates for 1024-bit RSA have moved downward since. The elliptic curve discrete logarithm has no such history of incremental improvement — the generic bound has stood — but that is evidence of absence rather than absence of evidence.

Migration in practice

The transition from 1024-bit RSA to 2048-bit was driven by the 80-bit level becoming uncomfortable, and the transition to 3072-bit or to curves is driven by the 112-bit level reaching the same status. Because the equivalence is between attack costs, a system can move along the table without changing its security target: the target stays at 128 bits, and the key type changes.

The migration that is not on this table is the move to post-quantum schemes, where the hardness assumption is different entirely and the key sizes are larger than either column — kilobytes rather than hundreds of bytes for some schemes. That migration is not a matter of moving along the table; it is a change of family, and the sizes are not comparable to the classical ones at all. Hybrid constructions that combine a classical and a post-quantum exchange are the transitional answer, and their structure is described in Hybrid Encryption and the Cost of Encrypting Long Messages.

One more column belongs beside the table even though it is not a public-key family: the symmetric keys that the public-key layer protects. A 128-bit symmetric key is treated as the 128-bit security level, and the mapping is direct because the best generic attack on a block cipher is exhaustive search. That directness is why the table’s rows are indexed by security level rather than by key length. The public-key columns are translations of the symmetric level into the size a different problem needs, and the translation factor is a property of the algorithm family, not a constant of nature.