Spotlight #34 – Number Theory & Cryptography: Primes, RSA, Elliptic Curves and Post-Quantum Security

Number theory is often called the queen of mathematics: a branch concerned with the integers and their properties that has absorbed brilliant minds for millennia while steadfastly resisting complete understanding. The apparent uselessness of this pure mathematics turned out to be illusory. When public-key cryptography was invented in the 1970s, it relied directly on the difficulty of factoring large integers and, later, on discrete logarithms in finite groups — objects studied by number theorists for purely aesthetic reasons a century earlier. Today’s post-quantum proposals rely on lattice problems whose hardness is itself a number-theoretic statement.

1. The Prime Number Theorem

Primes are the multiplicative atoms of the integers: every positive integer greater than one factors uniquely into primes (the Fundamental Theorem of Arithmetic). Despite this role, primes appear irregular when listed: 2, 3, 5, 7, 11, 13, … The first quantitative question is simply how many primes lie below a given bound.

π(x) = number of primes ≤ x

Prime Number Theorem (Gauss, Hadamard, de la Vallée Poussin):
  π(x) ~ x / ln(x)    as x → ∞

Equivalently, the n-th prime satisfies:
  p_n ~ n ln(n)

Better approximation (logarithmic integral):
  Li(x) = ∫²^x dt/ln(t)   (error << √x · ln(x) under RH)

Mertens’ third theorem:
  ∏_{p ≤ x} (1 − 1/p)¹ ~ e^γ ln(x)    (γ = 0.5772...)
          

The proof of the Prime Number Theorem in 1896 required understanding the Riemann zeta function ζ(s) = ∑_n=1^∞ n^−s, analytically continued to the whole complex plane. Riemann’s 1859 paper connected the distribution of primes to the zeros of ζ(s) through an explicit formula:

ψ(x) = x − ∑_ρ x^ρ / ρ − ln(2π) − ½ ln(1 − x^−²)

where ψ(x) = ∑_{p^k ≤ x} ln(p)  (Chebyshev psi function)
      ρ ranges over non-trivial zeros of ζ(s)

Trivial zeros: s = −2, −4, −6, ...
Non-trivial zeros: Re(ρ) = ½ (Riemann Hypothesis, unproved)

Verified for first 10^13 zeros (Platt & Trudgian 2021)
π(10^23) = 1,925,320,391,606,803,968,923 (exact, 2022)
          

The Riemann Hypothesis states that all non-trivial zeros lie on the critical line Re(s) = ½. It is one of the seven Millennium Prize Problems (Clay Mathematics Institute, $1 million prize). Its truth would imply the sharpest known bounds on the error in π(x) — with direct consequences for the security analysis of randomised primality-testing algorithms used in RSA key generation.

2. Modular Arithmetic

Modular arithmetic wraps the integers around a circle of circumference n: two integers are congruent modulo n if their difference is divisible by n. The notation a ≡ b (mod n) captures this. Modular arithmetic makes finite sets into algebraic structures (rings and, when n is prime, fields) that support fast computation.

Fermat’s Little Theorem (p prime, gcd(a,p)=1):
  a^(p−1) ≡ 1  (mod p)
  ⇒ a^p ≡ a  (mod p)

Euler’s Theorem (gcd(a,n)=1):
  a^φ(n) ≡ 1  (mod n)
  φ(n) = n ∏_{p|n} (1 − 1/p)  (Euler totient)

Chinese Remainder Theorem:
  If n = p·q with gcd(p,q)=1,
  then Z_n ≅ Z_p × Z_q  (ring isomorphism)
  x mod n ↔ (x mod p, x mod q)

Quadratic Residues (p odd prime):
  a is a QR mod p iff a^((p−1)/2) ≡ 1 (mod p)
  Legendre symbol: (a/p) = a^((p−1)/2) mod p ∈ {±1}
          

Modular exponentiation — computing a^e mod n efficiently using repeated squaring — is the core operation of RSA and Diffie-Hellman. It runs in O(log e) multiplications. Without this algorithm, practical public-key cryptography would be infeasible.

3. RSA Cryptography

RSA (Rivest, Shamir, Adleman 1977) was the first practical public-key cryptosystem. Its security rests on the hardness of the integer factorisation problem: given n = p · q where p and q are large primes, find p and q. With n on the order of 2048 bits (≈ 617 decimal digits), no known classical algorithm can factor n in feasible time.

Key generation:
  1. Choose large primes p, q  (each ~1024 bits for RSA-2048)
  2. Compute n = p · q,  φ(n) = (p−1)(q−1)
  3. Choose e with gcd(e, φ(n)) = 1  (commonly e = 65537)
  4. Compute d = e^−¹  (mod φ(n))  via extended Euclidean algorithm
  5. Public key:  (n, e);   Private key: (n, d)  [p, q secret]

Encryption:   c = m^e  mod n        (m < n, padded with OAEP)
Decryption:   m = c^d  mod n

Correctness:  c^d = m^(ed) = m^(1 + kφ(n)) = m  (Euler)

Digital signature (sign with private key d, verify with public e):
  s = hash(msg)^d  mod n
  verify: s^e mod n == hash(msg)
          

The best known classical factoring algorithm is the General Number Field Sieve (GNFS), with sub-exponential complexity L[1/3, 1.923]. The RSA-768 challenge (768-bit modulus) was factored in 2009 using roughly 2000 CPU-years. RSA-2048 would require enormously more. Current practical recommendations: 2048-bit RSA for data confidentiality, 3072-bit for data requiring long-term security past 2030 (NIST SP 800-57).

4. Elliptic Curve Cryptography

An elliptic curve over a field F is the set of points satisfying y² = x³ + ax + b together with a point at infinity O, subject to the non-singularity condition 4a³ + 27b² ≠ 0. These points form an abelian group under a geometric addition law: given two points P, Q, their sum P + Q is defined by reflecting through the x-axis the third intersection of line PQ with the curve.

Curve: E over F_p (prime field),  p > 3

Point addition P + Q = R (P ≠ Q):
  λ = (y_Q − y_P) / (x_Q − x_P)  mod p
  x_R = λ² − x_P − x_Q  mod p
  y_R = λ(x_P − x_R) − y_P  mod p

Point doubling 2P (tangent case):
  λ = (3x_P² + a) / (2y_P)  mod p

Elliptic Curve Discrete Log Problem (ECDLP):
  Given G (generator) and Q = kG, find k
  Best known algorithm: Pollard’s rho, O(√n)

Security comparison:
  256-bit ECC  ≈  3072-bit RSA  ≈  128-bit symmetric AES
  384-bit ECC  ≈  7680-bit RSA  ≈  192-bit symmetric AES
          

ECDSA and ECDH

The Elliptic Curve Diffie-Hellman (ECDH) key exchange allows two parties to derive a shared secret over an insecure channel: Alice publishes aG; Bob publishes bG; both compute abG. ECDSA (Elliptic Curve Digital Signature Algorithm) is the signature scheme used in Bitcoin, Ethereum, and TLS 1.3. The NIST curves P-256 and P-384 and the faster Curve25519 (Bernstein 2006) cover the overwhelming majority of current use.

5. Post-Quantum Cryptography

Peter Shor’s 1994 quantum algorithm factors integers and solves discrete logarithms in polynomial time on a quantum computer. A sufficiently large quantum computer would break RSA and all ECC schemes. Although current quantum hardware cannot factor large integers (NSA/CISA 2022 advisory), the “harvest now, decrypt later” threat is real: adversaries can store encrypted traffic today and decrypt it once quantum computers mature. Cryptographic migration must begin before the threat arrives.

Learning With Errors (LWE):
  Given A (matrix), b = As + e  (mod q)
  Find secret vector s
  Error e drawn from discrete Gaussian χ
  Worst-case hardness reduces to SVP on lattice

Module-LWE (MLWE):
  s, e are vectors of polynomials in R_q = Z_q[x]/(x^n + 1)
  Basis for CRYSTALS-Kyber (KEM) and CRYSTALS-Dilithium (signatures)

NIST PQC Standards (FIPS 2024):
  FIPS 203: ML-KEM (CRYSTALS-Kyber) — key encapsulation
  FIPS 204: ML-DSA (CRYSTALS-Dilithium) — digital signatures
  FIPS 205: SLH-DSA (SPHINCS+) — hash-based signatures, stateless
  FIPS 206: FN-DSA (FALCON) — NTRU lattice signatures

Security category III (AES-192 equivalent): Kyber-768
  Public key: 1184 bytes   Ciphertext: 1088 bytes
  Compared to 256-byte RSA-2048 ciphertext — larger but quantum-safe
          

Hash-based signatures (Lamport 1979, XMSS, SPHINCS+) rely solely on the collision resistance of hash functions and are therefore conservative options with no algebraic structure for quantum attack. SPHINCS+-128s produces 7856-byte signatures — larger than lattice schemes but with minimal security assumptions. The US federal government is requiring migration of all classified systems to PQC algorithms by 2035 (NSA CNSA 2.0, 2022).

6. Zero-Knowledge Proofs

A zero-knowledge proof (ZKP) is a protocol by which a prover convinces a verifier that a statement is true without revealing anything beyond the truth of the statement. Proposed by Goldwasser, Micali and Rackoff in 1985, ZKPs satisfy three properties: completeness (an honest prover always convinces an honest verifier), soundness (a cheating prover cannot convince the verifier of a false statement except with negligible probability), and zero-knowledge (the verifier learns nothing except that the statement is true).

Setup: group G of prime order q, generator g, secret key x, public key y = g^x

Prover:
  1. Choose random r ∈ Z_q;  send commitment R = g^r
  2. Receive challenge c from verifier
  3. Compute response s = r + cx  (mod q);  send s

Verifier:
  4. Check: g^s == R · y^c
     (since g^s = g^(r+cx) = g^r · (g^x)^c = R · y^c  ✓)

Soundness: forking lemma shows extractor can recover x
           if prover answers two different challenges for same R
Zero-knowledge: (R, c, s) can be simulated without x
           choose s, c at random; set R = g^s / y^c
          

zk-SNARKs and Applications

Succinct Non-interactive ARguments of Knowledge (SNARKs) allow a prover to produce a short (constant-size) proof that a general computation was performed correctly. The Groth16 scheme (2016) produces proofs of just 196 bytes verifiable in <1 ms, for arbitrary Boolean circuits. zk-SNARKs underpin Zcash (shielded transactions), zkSync and StarkNet (Ethereum Layer-2 rollups), and are being explored for privacy-preserving machine learning, identity verification and compliance proofs in financial systems.

Try These Simulations