Elliptic Curve Security Strength

The security of an elliptic-curve system rests on the discrete logarithm problem in the curve's group: given points $P$ and $Q = kP$, recover $k$. For a well-chosen curve the best known generic attack is Pollard's rho, which finds $k$ in about $\sqrt{n}$ group operations for a group of order $n$. A square root halves an exponent, so a group of order $2^{256}$ costs about $2^{128}$ operations to attack — and that is the whole derivation of $s = n/2$.

The standard sizes follow directly. P-256 gives 128 bits, P-384 gives 192, P-521 gives about 260, and the older P-224 gives 112 — the floor NIST SP 800-57 Part 1 Rev. 5 sets for data protected past 2030. Curve25519's 255-bit order gives about 126 bits, and Curve448's gives about 224. Note that this halving is quite different from the symmetric case: an AES-128 key gives 128 bits of strength from 128 bits of key, while a curve needs 256 bits of key for the same 128 bits of strength. Elliptic curves are still far more compact than RSA, which needs roughly a 3072-bit modulus to reach 128 bits, but they are not free.

Why there is no RSA or Diffie-Hellman page here, and why that is a deliberate refusal. The equivalent relation for a finite-field or RSA modulus is not $n/2$, because the number field sieve is subexponential rather than square-root. RFC 3766 / BCP 86 (Orman & Hoffman, 2004) gives a usable estimate: the work is about $\exp\!\big(1.923\,(n\ln 2)^{1/3}(\ln(n\ln 2))^{2/3}\big)$ for an $n$-bit modulus, which converts to bits of strength by dividing the exponent by $\ln 2$. That is computable forward in one line. Its inverse — the modulus size that delivers a wanted strength, which is the question anybody actually brings — has no closed form: $n$ sits inside a cube root and inside a logarithm of itself, and every published RSA size table was built by evaluating the forward expression upward until it crossed the target. This catalog does not ship root-finding brains; industrial.ts refuses an internal-rate-of-return page for exactly the same reason and says so in the file. So rather than ship half a page, the recommendation is the public table: NIST SP 800-57 Part 1 Rev. 5 Table 2, which pairs 112 bits with a 2048-bit modulus, 128 with 3072, 192 with 7680 and 256 with 15360.

Three qualifications on the number this page returns. First, it assumes a curve with no exploitable structure — anomalous curves, curves of small embedding degree, and curves with poorly chosen parameters all fall far below $n/2$, which is what the vetting behind the NIST, Brainpool and SafeCurves work is for. Do not invent a curve. Second, NIST's equivalences are a policy judgement about attack cost, not a theorem: they weigh algorithmic progress, hardware trends and how long the data must live, and they have been revised before. SP 800-57 has been through five revisions and the 80-bit level that was once acceptable is now withdrawn. Third, and most consequentially, this is a classical estimate. Shor's algorithm solves elliptic-curve discrete logarithms in polynomial time, so a cryptographically relevant quantum computer does not halve this number — it removes it entirely, and a larger curve does not help. Symmetric keys degrade gracefully under Grover's algorithm; elliptic curves and RSA do not degrade at all, they stop. For key establishment and signatures that must survive that transition, the references are FIPS 203, FIPS 204 and FIPS 205, and the current practical advice is hybrid key exchange — classical and post-quantum together — so that a break in either one alone is not a break.