RSA, Elliptic Curves, Lattices?

Three ways to hide a secret in plain sight

Every public key system rests on the same trick: find an operation that is cheap to run forwards and, as far as anyone knows, ruinously expensive to run backwards. The three families that matter differ only in which operation.

That table looks like three arbitrary choices. It is not. Each row has a different shape of hardness. The shape, rather than the cleverness of the construction, is what determines key sizes, derivation cost, and survival against a quantum computer. This post works through all three.

Part I. RSA, multiplication you cannot undo

The construction

Pick primes p and q, set n = p*q, and publish n with a small exponent e (almost always 65537). Compute the private exponent from the group order:

Signing is $s = m^{d} \bmod n$, and verification is $m = s^{e} \bmod n$. Correctness comes from Carmichael's theorem, not Euler's, since we reduced modulo $\lambda(n)$ rather than $\varphi(n)$: we get $m^{ed} \equiv m \pmod{n}$ because $ed \equiv 1 \pmod{\lambda(n)}$. (Using $\lambda$ gives a smaller $d$ than the textbook $\varphi$ formulation, and because $n = p\cdot q$ is squarefree the congruence holds for every $m$ rather than only those coprime to $n$.)

Why the keys are enormous

Factoring is not exponential. The general number field sieve runs in $L_n\bigl[\tfrac{1}{3},\, \sqrt[3]{64/9}\,\bigr]$, where the L notation interpolates between polynomial and exponential growth:

The two endpoints are the point of the notation: $\alpha = 0$ gives something polynomial in $\ln n$, and $\alpha = 1$ gives something exponential in it. Factoring sits strictly between them. Substituting $\alpha = 1/3$ and $c = \sqrt[3]{64/9} \approx 1.923$:

The o(1) is not decoration. It absorbs a real gap. Evaluate the leading term alone and you get 117 bits of work for RSA-2048 where NIST credits 112, and 139 for RSA-3072 where NIST credits 128. The expression gives the growth rate, not a work factor you should quote at a customer.

That cube root in the exponent is the whole story. Because the work grows subexponentially in the bit length, you have to grow the modulus very fast to buy linearly more security:

Read the two solid curves. Pollard's rho against an elliptic curve is a straight line of slope 1/2, so a 256 bit curve costs 2^128 operations. GNFS against RSA crawls. You need a 3072 bit modulus for the same 2^128. Push to 256 bit security and RSA needs 15360 bits, a 1920 byte key.

Doubling elliptic curve security doubles the key. Doubling RSA security multiplies the modulus by about five (3072 to 15360 bits), and the ratio keeps growing toward the asymptotic eight. Two curves, diverging without bound. That divergence is the entire reason new protocols stopped choosing RSA.

Key generation is a search, and that matters

Everything else in this post generates keys by deriving them. RSA has to go looking:

repeat:  sample a random odd 1536-bit integer
         run Miller-Rabin
until:   probably prime

By the prime number theorem, near 2^1536 roughly one odd number in ln(2^1536)/2 ~ 532 is prime, so expect about 532 candidates per prime, and two primes per key. Hundreds of milliseconds, with a tail you cannot bound. On an embedded device it can be seconds.

This has a real consequence: RSA key generation is the one primitive here that can fail to finish on time, which is why smartcards take seconds to generate an RSA key (some are provisioned with one at the factory) and why nobody generates RSA keys per session.

Part II. Elliptic curves, geometry as a group

The group law is literally drawing a line

An elliptic curve over a field is the solution set of y^2 = x^3 + ax + b (with 4a^3 + 27b^2 != 0, which rules out cusps and self intersections). Its points form an abelian group under an operation you can draw:

Draw the chord through P and Q. A cubic meets a line in exactly three points, so there is a third intersection R. Reflect it across the x axis and you have P + Q. Algebraically:

The figure above is computed from those formulas rather than drawn by hand. The plotted P + Q satisfies the curve equation to floating point precision.

From geometry to hardness

Real curves are pretty. Cryptography uses curves over a finite field F_p, where the algebra is identical but the picture is not.

That is the same equation. Every one of those 126 points satisfies y^2 = x^3 - 3x + 5 (mod 127), and the group order is 127 - prime, so every point generates the whole group. The numbered dots are 1G through 8G, computed with exactly the chord and tangent rules from the previous figure.

Look at where they land: (5,49), (9,31), (38,36), (55,90), (98,50)... no drift, no direction, nothing to extrapolate from. The smoothness that makes the group law easy to draw evaporates over a finite field, and with it every geometric shortcut an attacker might hope for. The forward direction is still three doublings, 2G, 4G, 8G. The reverse is a search. Scalar multiplication Q = k*G is repeated addition, done in O(log k) steps by double and add. Recovering k from Q is the elliptic curve discrete logarithm problem. The best known classical attack, Pollard's rho, is a birthday collision needing about sqrt(pi*N/4) group operations, where N is the order of the base point. For an n-bit curve N ~ 2^n, so that is sqrt(pi/4) * 2^(n/2) ~ 2^(n/2). The constant 0.886 costs the attacker about a sixth of a bit and is conventionally dropped.

Exponential, with no subexponential shortcut known. That is why a 256 bit curve matches a 3072 bit RSA modulus.

Curve25519's derivation, and why it never fails

seed  <- 32 random bytes
h     = SHA-512(seed)
a     = clamp(h[0..32])       // clear low 3 bits, set bit 254, clear bit 255
A     = a * G                 // one scalar multiplication

The clamping is the interesting part. Curve25519 has cofactor 8, so the group contains a small order 8 subgroup alongside the prime order one. Clearing the low three bits makes the scalar a multiple of 8, which in X25519 key exchange annihilates any small order component a hostile peer might inject. The attack is neutralised arithmetically rather than by validating the input point. Setting bit 254 fixes the leading bit so a Montgomery ladder runs the same number of iterations for every key, which is what makes it constant time.

The payoff is that every 32 byte string is a valid seed. Nothing can be rejected, and nothing can loop.

Part III. Lattices, hardness from geometry in high dimensions

What a lattice is

Given linearly independent basis vectors b_1 ... b_n, the lattice is every integer combination:

L = { sum z_i*b_i  :  z_i in Z }

A discrete grid of points, infinite in extent. Two problems on it are believed hard in high dimension. SVP asks for the shortest nonzero vector, and CVP asks for the lattice point nearest to an arbitrary target.

The trapdoor is which basis you hold

Here is the insight the whole field rests on, and it is genuinely beautiful: a lattice has infinitely many bases, and they are not equally useful.

Both panels show the identical point set. The bases are related by the unimodular matrix [[1,3],[1,4]] (determinant 1), so they generate exactly the same lattice. Now run Babai's rounding algorithm. Express the target in the basis, round each coordinate, and return that lattice point.

• The good basis is short and near orthogonal. It rounds (1.48, 1.55) to (1, 2), landing at (4, 4) at distance 1.03. That is genuinely the closest point.
• The bad basis is long and skewed. It rounds (4.35, -2.88) to (4, -3), landing at (2, 0) at distance 3.98. Nearly four times worse, same algorithm.

Publish the bad basis, keep the good one. That is a public/private keypair made of nothing but geometry. In two dimensions you could find the good basis by inspection. In the 512 to 1024 dimensions ML-KEM works in, with LLL resistant parameters, nobody knows how.

Learning With Errors

Modern schemes phrase this as noisy linear algebra rather than raw geometry:

Publish A and b = A*s + e (mod q) where s is secret and e is small noise. Set e = 0 and Gaussian elimination recovers s in milliseconds. Add the noise and every equation becomes an approximation. Recovering s is then equivalent to finding a close vector in a lattice.

Regev's 2005 reduction is what makes this trustworthy. An algorithm for average case LWE would give a quantum algorithm for approximate shortest vector problems on every lattice. That worst case guarantee is something factoring has never had, though concrete parameters are still set by cryptanalysis rather than by the reduction.

Module-LWE: why the keys are kilobytes and not megabytes

Plain LWE needs an n x n public matrix. For n = 256 that is 65,536 coefficients. Kyber and Dilithium use the module variant, where entries are polynomials in $\Z_q[X]/(X^{256}+1)$ and the matrix is only $k \times k$ with $k \in \{2,3,4\}$ ($k \times \ell$ for ML-DSA). A single seed $\rho$ regenerates $\hat{A}$ via SHAKE, so the matrix is never transmitted at all.

ML-KEM:  q = 3329,     n = 256,  k = 2/3/4
ML-DSA:  q = 8380417,  n = 256,  (k,l) = (4,4)/(6,5)/(8,7)

Both moduli are chosen so the number theoretic transform applies, making polynomial multiplication $O(n\log n)$ instead of $O(n^{2})$. That is why post quantum operations are fast even though the objects are large.

The two moduli are not equally lucky, though, and the difference falls out of the factorisation of $q-1$. The NTT needs roots of unity, and how many the field contains is decided by which powers of two divide $q-1$:

Kyber's smaller modulus buys tighter ciphertexts at the cost of stopping one level short in the transform. It cannot finish splitting the ring, so its pointwise stage multiplies pairs of linear polynomials rather than plain field elements. It is a deliberate trade rather than an oversight.

Part IV. The comparison, in numbers

Public keys

What actually goes on the wire

An ML-DSA-87 signature is 4,627 bytes - 72x an Ed25519 signature. That is enough to change how you design a token format, but not whether you can have one. The signature is not even the biggest part. A UCAN names its principals as did:key strings, and an ML-DSA-87 did:key embeds the whole 2,592 byte public key. Measured with our pq-ucan crate, a delegation between two ML-DSA-87 principals is about 15 KB of DAG-CBOR and 20 KB once base64url encoded, against 532 bytes for the same token signed with Ed25519. The practical consequence is "put it in a header or body, never a URL, and refer to keys rather than inlining them", not "impossible".

Speed, measured

Mean times from aws-lc-rs on an Apple M4 Pro. Your hardware will differ, and the shape will not.

Note the shape: RSA verification is fast (small exponent), signing is slow. Verification is a three way tie at about 20 us, and ML-DSA signing, while roughly fourteen times Ed25519, still finishes in under a tenth of a millisecond. The post quantum penalty is bandwidth rather than compute, which is the opposite of what most people assume.

Part V. What a quantum computer does

Shor's algorithm solves both factoring and discrete logarithms in polynomial time. That is not merely faster. It is polynomial, a different complexity class. RSA and ECC do not get weaker. They stop existing as security assumptions.

The ordering surprises people. On the classic estimates, elliptic curves fall first. A 256 bit curve needs roughly 2,330 logical qubits against RSA-2048's 2n + 3 = 4,099, because the operands are smaller. The primitive with the better classical security ratio has the worse quantum one. Newer RSA specific constructions (Gidney, 2025) have narrowed that gap considerably, so plan as if both fall together.

Grover's algorithm, meanwhile, gives only a quadratic speedup against symmetric primitives, so AES-256 retains 128 bit security. Symmetric cryptography was never the problem. The entire migration is about public key operations.

For lattices, no polynomial time quantum algorithm is known for SVP or CVP. The best quantum attacks are modest improvements on classical sieving. That is an absence of evidence rather than a proof, and it is the honest reason to prefer hybrids during the transition.

Part VI. Choosing, in practice

Harvest now, decrypt later is the deciding argument. An adversary recording encrypted traffic today can decrypt it whenever a cryptographically relevant quantum computer arrives. For data with a confidentiality horizon measured in decades, such as clinical trials, genomic cohorts, and national security, the transition deadline is not when quantum computers arrive. It is today.

Signatures are different. A signature only needs to resist forgery while it is still being relied upon. Signing an archive again later is feasible in a way that reencrypting intercepted traffic is not.

That asymmetry gives a clean rule:

• Encrypt with post quantum protection now - the risk is retroactive.
• Sign with a hybrid, and migrate on your own schedule.

A hybrid signature concatenates both and accepts only if both verify. The "either" variant you sometimes see proposed is strictly worse than the stronger algorithm alone, because an attacker who breaks the weaker one forges freely.

This is the reasoning behind our own stack, which follows the rule above. Encryption is post quantum today. ML-KEM-1024 wraps the AES-256-GCM content key of every stored file. Signatures are not yet. Capability tokens, DID control and browser session keys are Ed25519, because the wallet that signs them is a Solana wallet. ML-DSA-87 is supported by pq-ucan, is a did:bio verification method type, and is the assertion key the service's own did:bio carries once registered, but it does not sign user tokens - documented honestly, including what is not yet post quantum.

The one paragraph version

RSA is hard because factoring is subexponential, which forces enormous keys and a key generation procedure that searches rather than derives. Elliptic curves are hard because the discrete log is fully exponential, which is why 32 bytes suffices. Lattices are hard because a bad basis makes an easy geometric problem intractable, and that hardness has no known quantum shortcut. The first two are elegant and doomed. The third is bulky and survives. Bandwidth is a cheaper thing to spend than time you do not have.

Further reading: FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), Regev (2005) on LWE, and our Post Quantum Security documentation.