The Math Behind RSA #4: Breaking RSA and the Rise of Elliptic Curve Cryptography

This article has a more math-focused version with formal proofs on Folio.

In the previous three parts, we built RSA from the ground up: modular arithmetic, Euler's theorem, and a working Python implementation. Now we tear it all down. This final article explores why RSA is showing its age, how elliptic curve cryptography (ECC) offers a compelling alternative, and what the quantum future holds.

Part I: Attacks on RSA

The Factoring Arms Race

RSA's security rests on a single assumption: factoring the product of two large primes is computationally hard. But "hard" is a moving target.

Trial Division — The naive approach tests every integer up to $\sqrt{n}$ . For a 2048-bit modulus, that means checking roughly $2^{1024}$ candidates. Completely infeasible.

Fermat's Factorization — If $p$ and $q$ are close together, we can write $n = a^2 - b^2 = (a+b)(a-b)$ and search for $a$ near $\sqrt{n}$ . This is why good RSA implementations ensure $|p - q|$ is large.

Quadratic Sieve (QS) — Introduced in 1981, QS was the fastest general-purpose factoring algorithm for decades. Its sub-exponential runtime is approximately:

$$L_n!\left[\tfrac{1}{2},\, 1\right] = e^{(1+o(1))\sqrt{\ln n \cdot \ln \ln n}}$$

General Number Field Sieve (GNFS) — The current champion, with heuristic complexity:

$$L_n!\left[\tfrac{1}{3},\, \left(\tfrac{64}{9}\right)^{1/3}\right] = e^{\left(\left(\frac{64}{9}\right)^{1/3}+o(1)\right)(\ln n)^{1/3}(\ln \ln n)^{2/3}}$$

In 2020, a team factored RSA-250 (829 bits) using GNFS. The trend is clear: factoring records keep falling.

Year	Record	Bits
1999	RSA-155	512
2005	RSA-200	663
2009	RSA-768	768
2020	RSA-250	829

Side-Channel Attacks

Even with a large key, the implementation can leak secrets:

• Timing attacks: Measuring how long decryption takes can reveal bits of the private key. If a 1 bit in the exponent triggers an extra multiplication, the time difference is measurable.
• Power analysis: Monitoring a hardware device's power consumption during RSA operations can expose the exponent bit by bit.
• Fault injection: Inducing a computational error during signing and comparing the faulty signature with a correct one can factor $n$ directly (Boneh-DeMillo-Lipton attack).

Padding Oracle Attacks

Raw textbook RSA ( $c = m^e \bmod n$ ) is deterministic — the same plaintext always produces the same ciphertext. This enables:

• Bleichenbacher's attack (1998): Against PKCS#1 v1.5 padding. By sending thousands of crafted ciphertexts and observing which ones the server accepts as "correctly padded," an attacker can decrypt any message. This motivated the move to OAEP padding.
• Chosen-ciphertext malleability: Given $c = m^e \bmod n$ , an attacker computes $c' = c \cdot s^e \bmod n$ , which decrypts to $m \cdot s \bmod n$ .

Part II: The Key Length Problem

As factoring algorithms improve, RSA keys must grow. Here is what NIST recommends for equivalent security levels:

Security (bits)	RSA key size	ECC key size	Ratio
80	1024	160	6.4x
112	2048	224	9.1x
128	3072	256	12x
192	7680	384	20x
256	15360	512	30x

At the 256-bit security level, RSA needs a 15,360-bit key. That is 1,920 bytes just for the modulus. Key generation, signing, and decryption all slow to a crawl. This is the fundamental scaling problem that drives the shift to elliptic curves.

Part III: Introduction to Elliptic Curves

An elliptic curve over a field $\mathbb{F}_p$ (where $p$ is a large prime) is the set of points $(x, y)$ satisfying:

$$y^2 \equiv x^3 + ax + b \pmod{p}$$

together with a special "point at infinity" $\mathcal{O}$ , provided the discriminant $4a^3 + 27b^2 \not\equiv 0 \pmod{p}$ (which ensures no singularities).

Group Structure

The remarkable fact: the points on an elliptic curve form an abelian group under a geometric addition law.

• Identity: The point at infinity $\mathcal{O}$ serves as the identity element.
• Inverse: The inverse of $(x, y)$ is $(x, -y)$ .
• Addition: For two distinct points $P = (x_1, y_1)$ and $Q = (x_2, y_2)$ , the sum $R = P + Q = (x_3, y_3)$ is computed by drawing a line through $P$ and $Q$ , finding the third intersection with the curve, and reflecting over the x-axis.

The formulas (mod $p$ ):

$$\lambda = \frac{y_2 - y_1}{x_2 - x_1}, \quad x_3 = \lambda^2 - x_1 - x_2, \quad y_3 = \lambda(x_1 - x_3) - y_1$$

For point doubling ( $P = Q$ ):

$$\lambda = \frac{3x_1^2 + a}{2y_1}$$

Part IV: Python Implementation

Let's implement elliptic curve arithmetic from scratch.

class EllipticCurve:
    """An elliptic curve y^2 = x^3 + ax + b over F_p."""

    def __init__(self, a, b, p):
        self.a = a
        self.b = b
        self.p = p
        assert (4 * a**3 + 27 * b**2) % p != 0, "Singular curve"

    def is_on_curve(self, point):
        if point is None:  # Point at infinity
            return True
        x, y = point
        return (y * y - (x**3 + self.a * x + self.b)) % self.p == 0

    def point_add(self, P, Q):
        """Add two points on the curve."""
        if P is None:
            return Q
        if Q is None:
            return P

        x1, y1 = P
        x2, y2 = Q

        if x1 == x2 and (y1 + y2) % self.p == 0:
            return None  # P + (-P) = O

        if P == Q:
            # Point doubling
            lam = (3 * x1 * x1 + self.a) * pow(2 * y1, -1, self.p) % self.p
        else:
            # Point addition
            lam = (y2 - y1) * pow(x2 - x1, -1, self.p) % self.p

        x3 = (lam * lam - x1 - x2) % self.p
        y3 = (lam * (x1 - x3) - y1) % self.p
        return (x3, y3)

    def scalar_mult(self, k, P):
        """Compute k * P using double-and-add."""
        result = None  # Point at infinity
        addend = P

        while k:
            if k & 1:
                result = self.point_add(result, addend)
            addend = self.point_add(addend, addend)
            k >>= 1

        return result

The scalar_mult method uses the double-and-add algorithm — the elliptic curve analog of fast modular exponentiation. Computing $k \cdot P$ takes $O(\log k)$ group operations.

A Quick Test

# secp256k1 parameters (used in Bitcoin)
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
G = (
    0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
    0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8,
)

curve = EllipticCurve(a, b, p)
assert curve.is_on_curve(G)

# Compute 2G
G2 = curve.scalar_mult(2, G)
print(f"2G = ({hex(G2[0])}, {hex(G2[1])})")
assert curve.is_on_curve(G2)

Part V: ECDH Key Exchange

Elliptic Curve Diffie-Hellman lets two parties agree on a shared secret over an insecure channel. It is the ECC counterpart to classical Diffie-Hellman.

import secrets

def ecdh_keygen(curve, G, n):
    """Generate an ECDH key pair."""
    private_key = secrets.randbelow(n - 1) + 1  # random in [1, n-1]
    public_key = curve.scalar_mult(private_key, G)
    return private_key, public_key

# Curve order for secp256k1
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

# Alice generates her key pair
alice_priv, alice_pub = ecdh_keygen(curve, G, n)

# Bob generates his key pair
bob_priv, bob_pub = ecdh_keygen(curve, G, n)

# Both compute the shared secret
shared_alice = curve.scalar_mult(alice_priv, bob_pub)   # alice_priv * bob_pub
shared_bob   = curve.scalar_mult(bob_priv, alice_pub)   # bob_priv * alice_pub

assert shared_alice == shared_bob
print("Shared secret established!")
print(f"  x = {hex(shared_alice[0])}")

Alice computes $a \cdot (bG) = abG$ . Bob computes $b \cdot (aG) = abG$ . They arrive at the same point. An eavesdropper sees $aG$ and $bG$ but cannot compute $abG$ without solving the Elliptic Curve Discrete Logarithm Problem (ECDLP).

Part VI: Why ECDLP Is Harder Than Factoring

The best known classical algorithms for the two problems scale very differently:

	Integer Factoring (RSA)	ECDLP (ECC)
Best algorithm	GNFS	Pollard's rho
Complexity class	Sub-exponential	Fully exponential
Time ( $n$ -bit key)	$e^{O(n^{1/3} \log^{2/3} n)}$	$O(2^{n/2})$
128-bit security	3072-bit key	256-bit key
Index calculus	Applies	No known analog

The critical difference is that index calculus methods — the family of techniques behind QS and GNFS — have no known efficient analog for elliptic curves over prime fields. Transferring the discrete logarithm from an elliptic curve to a finite field where index calculus works requires solving the ECDLP itself (outside of special weak-curve cases).

This means that for elliptic curves, we are stuck with generic algorithms like Pollard's rho, which run in $O(\sqrt{n})$ where $n$ is the group order. A 256-bit curve provides roughly 128 bits of security — matching AES-128 — with dramatically smaller keys.

Part VII: The Quantum Threat

Shor's Algorithm

In 1994, Peter Shor showed that a sufficiently large quantum computer can factor integers and compute discrete logarithms in polynomial time:

$$O((\log n)^2 (\log \log n)(\log \log \log n))$$

This breaks both RSA and ECC. The algorithm works by reducing factoring to period-finding, which quantum computers solve efficiently via the Quantum Fourier Transform. For ECC, a variant of Shor's algorithm solves the ECDLP with similar efficiency.

Current status: As of 2025, the largest number factored by a quantum computer using Shor's algorithm is 21. We are far from threatening RSA-2048. But the field is advancing rapidly, and the "harvest now, decrypt later" threat is real — adversaries can store encrypted traffic today and decrypt it once quantum computers mature.

Post-Quantum Cryptography

NIST finalized its first post-quantum standards in 2024:

• ML-KEM (CRYSTALS-Kyber): A lattice-based key encapsulation mechanism. Its security rests on the hardness of the Module Learning With Errors (MLWE) problem.
• ML-DSA (CRYSTALS-Dilithium): A lattice-based digital signature scheme.
• SLH-DSA (SPHINCS+): A hash-based signature scheme — conservative, stateless, and relying only on hash function security.

The core idea behind lattice-based cryptography: given a "noisy" system of linear equations over a lattice, finding the secret vector is believed hard even for quantum computers.

$$\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e} \pmod{q}$$

where $\mathbf{e}$ is a small error vector. Without the error, this is simple linear algebra. With it, the problem becomes intractable.

Part VIII: RSA vs ECC — Full Comparison

Feature	RSA	ECC
Hard problem	Integer factoring	ECDLP
Key size (128-bit security)	3072 bits	256 bits
Signature size	3072 bits	512 bits
Key generation speed	Slow (primality testing)	Fast
Signing speed	Moderate	Fast
Verification speed	Fast (small $e$ )	Moderate
Bandwidth efficiency	Poor	Excellent
Quantum resistance	None	None
Standardization maturity	Decades	~15 years in TLS
Patent concerns	Expired	Mostly resolved
IoT / embedded suitability	Poor	Excellent

The bottom line: for new systems, ECC is the default choice. RSA remains widespread in legacy systems and in contexts where its simplicity and fast verification are valued (e.g., certificate chains). Neither survives a quantum computer, so the long-term future belongs to post-quantum schemes.

Folio: The Full Mathematical Treatment

I wrote this series on Dev.to for the code-focused approach, but for the rigorous math — formal proofs, theorem environments, cross-references — I've published a more detailed version on Folio's number theory series. There you'll find complete proofs of Euler's theorem, the Chinese Remainder Theorem, formal security reductions, and the algebraic geometry behind elliptic curves — all typeset with proper LaTeX.

Series Summary

Over four articles, we've traced the full arc of public-key cryptography:

1. #1 — Modular Arithmetic: The foundation. We built intuition for congruences, modular inverses, and the structure of $\mathbb{Z}/n\mathbb{Z}$ .

2. #2 — Euler's Theorem and Key Generation: We proved why RSA works — that $m^{ed} \equiv m \pmod{n}$ — and implemented key generation in Python.

3. #3 — Encryption, Signatures, and Attacks: We built a complete RSA system with OAEP padding, digital signatures, and explored common implementation pitfalls.

4. #4 — Breaking RSA and Elliptic Curves (this article): We examined RSA's weaknesses, implemented elliptic curve cryptography from scratch, and looked ahead to the post-quantum era.

The story of RSA is ultimately a story about the relationship between mathematics and computation. What is "hard" today may not be tomorrow. The algorithms we trust are only as strong as the problems they hide behind — and finding those problems, understanding their difficulty, and building systems around them is one of the most fascinating intersections of pure math and engineering.

Thanks for reading the series. If you have questions or spot errors, drop a comment below.

---

Enjoyed this series? Follow me for more articles on the mathematics of computer science. The full version with formal proofs is available on Folio.