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, and the shape - not 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:

λ(n) = lcm(p − 1, q − 1)          Carmichael function
d    = e⁻¹ mod λ(n)               extended Euclid

Signing is s = m^d mod n; verification is m = s^e mod n. Correctness comes from Carmichael's theorem - not Euler's, since we reduced modulo λ(n) rather than φ(n): m^(ed) ≡ m (mod n) because ed ≡ 1 (mod λ(n)). (Using λ gives a smaller d than the textbook φ formulation, and because n = p·q is squarefree the congruence holds for every m, not just those coprime to n.)

Why the keys are enormous

Factoring is not exponential. The general number field sieve runs in L_n[1/3, ∛(64/9)], where the L-notation is defined as

L_n[α, c] = exp( (c + o(1)) · (ln n)^α · (ln ln n)^(1−α) )

so with α = 1/3  and  c = ∛(64/9) ≈ 1.923 :

  exp( (1.923 + o(1)) · (ln n)^(1/3) · (ln ln n)^(2/3) )

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 sub-exponentially 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 ½ - a 256-bit curve costs 2¹²⁸ operations. GNFS against RSA crawls: you need a 3072-bit modulus for the same 2¹²⁸. 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 roughly 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¹⁵³⁶ 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 ship with pre-generated keys 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² = x³ + ax + b (with 4a³ + 27b² ≠ 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:

λ  = (y₂ − y₁)/(x₂ − x₁)        chord   (or (3x₁²+a)/2y₁ for doubling)
x₃ = λ² − x₁ − x₂
y₃ = λ(x₁ − x₃) − y₁

The figure above is computed from those formulas, not 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 𝔽_p, where the algebra is identical but the picture is not:

That is the same equation. Every one of those 126 points satisfies y² = x³ − 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 and an addition; 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, and the best known classical attack - Pollard's rho - is a birthday collision needing about √(πN/4) group operations, where N is the order of the base point. For an n-bit curve N ≈ 2ⁿ, so that is √(π/4) · 2^(n/2) ≈ 2^(n/2) - the constant 0.886 costs the attacker about a fifth of a bit and is conventionally dropped.

Exponential, with no sub-exponential 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 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: every 32-byte string is a valid seed. Nothing can be rejected; nothing can loop.

Part III - Lattices: hardness from geometry in high dimensions

What a lattice is

Given linearly independent basis vectors b₁ … bₙ, the lattice is every integer combination:

L = { Σ zᵢ·bᵢ  :  zᵢ ∈ ℤ }

A discrete grid of points, infinite in extent. Two problems on it are believed hard in high dimension: SVP (find the shortest non-zero vector) and CVP (given an arbitrary target, find the nearest lattice point).

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, return that lattice point:

• Good basis (short, near-orthogonal): rounds (1.48, 1.55) -> (1, 2), landing at (4, 4), distance 1.03. That is genuinely the closest point.
• Bad basis (long, skewed): rounds (4.35, −2.88) -> (4, −3), landing at (2, 0), 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 dimension 256 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 equivalent to finding a close vector in a lattice.

Regev's 2005 reduction is what makes this trustworthy: solving average-case LWE would let you solve worst-case lattice problems. Break a random instance and you have broken every instance, which is a far stronger guarantee than factoring offers.

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

Plain LWE needs an n × n public matrix - for n = 256 that is 65,536 coefficients. Kyber and Dilithium use the module variant, where entries are polynomials in ℤ_q[X]/(X²⁵⁶ + 1) and the matrix is only k × k with k ∈ {2,3,4}. A single seed ρ regenerates Â 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,ℓ) = (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²). 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 is visible in the factorisations of q − 1:

ML-DSA:  8380416 = 2¹³ · 1023   ->  512 | q−1, so X²⁵⁶+1 splits completely
                                    -> full NTT, 256 pointwise products
ML-KEM:     3328 = 2⁸  · 13     ->  256 | q−1 but 512 ∤ q−1
                                    -> X²⁵⁶+1 only splits into 128 quadratics
                                    -> "incomplete" NTT, 128 products in ℤq[X]/(X²−ζ)

Kyber's smaller modulus buys tighter ciphertexts at the cost of stopping one level short in the transform. It is a deliberate trade, not 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 - 72× an Ed25519 signature. That is enough to change how you design a token format, but not whether you can have one. Our UCAN capability tokens carry exactly this signature and land around 6 KB; the practical consequence is "put it in a header or body, not a URL", not "impossible".

Speed, roughly

Note the shape: RSA verification is fast (small exponent), signing is slow. Lattice verification beats everything. The post-quantum penalty is bandwidth, not 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. Not faster - polynomial, a different complexity class. RSA and ECC do not get weaker; they stop existing as security assumptions.

The ordering surprises people: 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.

Grover's algorithm, meanwhile, gives only a quadratic speed-up against symmetric primitives - 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, not 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 - clinical trials, genomic cohorts, 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. Re-signing an archive later is feasible in a way that re-encrypting 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: an attacker who breaks the weaker one forges freely.

This is the reasoning behind our own stack: ML-DSA-87 for signing capability tokens and DID assertions, ML-KEM-1024 wrapping AES-256-GCM content keys, and Ed25519 retained where a chain's consensus rules require it - documented honestly, including what is not yet post-quantum.

The one paragraph version

RSA is hard because factoring is sub-exponential, 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 - crucially - 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.