From modular arithmetic to post-quantum lattices — the complete mathematical foundation of modern cryptography, with worked examples for every major algorithm.
Every public-key cryptosystem runs on modular arithmetic — computation inside a finite ring of integers. The notation a ≡ b (mod n) means n divides (a - b), i.e., a and b have the same remainder after division by n. The set {0, 1, 2, ..., n-1} with addition and multiplication mod n forms the ring Z/nZ.
The multiplicative inverse of a mod n exists if and only if gcd(a, n) = 1. When it exists, it is the unique x such that ax ≡ 1 (mod n). Finding it uses the Extended Euclidean Algorithm — the same tool that backs RSA key generation.
Worked Example — Inverse of 3 mod 7
We need x such that 3x ≡ 1 (mod 7).
Extended Euclidean on gcd(7, 3):
7 = 2 * 3 + 1 → 1 = 7 - 2 * 3
So 3 * (-2) ≡ 1 (mod 7)
-2 mod 7 = 5
Answer: 3^(-1) ≡ 5 (mod 7) Check: 3 * 5 = 15 = 2*7 + 1 ✓
Computing a^e mod n naively requires e multiplications. The square-and-multiply (binary exponentiation) algorithm reduces this to O(log e) multiplications by repeatedly squaring. This is essential for RSA — encrypting with a 65537-bit exponent would be impossibly slow without it.
Algorithm — Square and Multiply
To compute a^e mod n:
1. Write e in binary: e = (b_k b_(k-1) ... b_1 b_0)_2
2. result = 1, base = a mod n
3. For each bit from LSB to MSB:
if bit == 1: result = result * base mod n
base = base^2 mod n
4. Return result
Worked Example — 3^13 mod 17
13 = 1101 in binary (bits 3,2,0 set)
Step 0 (bit 1): result = 1*3 = 3, base = 3^2 = 9
Step 1 (bit 0): result = 3, base = 9^2 = 81 ≡ 13 (mod 17)
Step 2 (bit 1): result = 3*13 = 39 ≡ 5 (mod 17), base = 13^2 = 169 ≡ 16
Step 3 (bit 1): result = 5*16 = 80 ≡ 12 (mod 17)
Answer: 3^13 mod 17 = 12 Verify: 3^13 = 1594323, 1594323 mod 17 = 12 ✓
phi(n) counts integers from 1 to n that are coprime to n. Key formulas:
Euler's Theorem
If gcd(a, n) = 1, then a^phi(n) ≡ 1 (mod n).
Example: a = 5, n = 6. phi(6) = phi(2)*phi(3) = 1*2 = 2. 5^2 = 25 = 4*6 + 1, so 5^2 ≡ 1 (mod 6) ✓
Fermat's Little Theorem is the special case of Euler's theorem when n = p (prime): if p is prime and p does not divide a, then a^(p-1) ≡ 1 (mod p). Equivalently, a^p ≡ a (mod p) for all integers a.
Worked Example — Fermat's Little Theorem
Compute 7^100 mod 13.
13 is prime, so 7^12 ≡ 1 (mod 13) by Fermat.
100 = 8*12 + 4, so 7^100 = (7^12)^8 * 7^4 ≡ 1^8 * 7^4 (mod 13)
7^2 = 49 ≡ 10 (mod 13)
7^4 = 10^2 = 100 ≡ 9 (mod 13)
Answer: 7^100 mod 13 = 9
Generating RSA primes requires testing large candidates for primality. Trial division up to sqrt(n) is infeasible for 1024-bit numbers. The Miller-Rabin test uses Fermat's theorem probabilistically: if n is prime, then for any base a, either a^d ≡ 1 (mod n) or a^(2^r * d) ≡ -1 (mod n) for some r, where n-1 = 2^s * d with d odd. A composite will fail this for at least 3/4 of all bases, so running the test with 40 random bases gives error probability below 4^(-40) — astronomically small.
RSA (Rivest-Shamir-Adleman, 1977) was the first practical public-key cryptosystem. Its security rests on the integer factorization assumption: given n = pq (product of two large primes), computing p and q from n alone is computationally infeasible for sufficiently large n.
Step 1. Choose two large distinct primes p and q (each 1024+ bits for RSA-2048).
Step 2. Compute modulus n = p * q. The bit length of n is the key size.
Step 3. Compute phi(n) = (p-1)(q-1). This must be kept secret.
Step 4. Choose public exponent e with 1 < e < phi(n) and gcd(e, phi(n)) = 1. Standard choice: e = 65537 = 2^16 + 1 (prime, has few 1-bits for fast exponentiation).
Step 5. Compute private exponent d = e^(-1) mod phi(n) using Extended Euclidean Algorithm, so ed ≡ 1 (mod phi(n)).
Public key: (n, e). Private key: (n, d). Destroy p, q, phi(n).
Encryption: Given message m (integer with 0 <= m < n), compute ciphertext c = m^e mod n.
Decryption: Given ciphertext c, compute m = c^d mod n.
Why it works: c^d = (m^e)^d = m^(ed). Since ed = 1 + k*phi(n), we get m^(ed) = m * (m^phi(n))^k ≡ m * 1^k = m (mod n) by Euler's theorem.
RSA with small primes (illustrative only — far too small for real use)
Choose p = 61, q = 53
n = 61 * 53 = 3233
phi(n) = 60 * 52 = 3120
Choose e = 17 (gcd(17, 3120) = 1 ✓)
d = 17^(-1) mod 3120 = 2753 (since 17*2753 = 46801 = 15*3120 + 1 ✓)
Public key: (3233, 17). Private key: (3233, 2753)
Encrypt m = 65: c = 65^17 mod 3233 = 2790
Decrypt c = 2790: m = 2790^2753 mod 3233 = 65 ✓
RSA security depends on multiple layered assumptions. The strongest needed is the RSA assumption: given (n, e, c), finding m = c^(1/e) without factoring n is hard. The factoring assumption (integer factorization is hard) implies the RSA assumption. The best classical factoring algorithm, the General Number Field Sieve, runs in roughly exp(c * n^(1/3) * (log n)^(2/3)) time — sub-exponential but still infeasible for n > 2048 bits. Shor's quantum algorithm factors in polynomial time O((log n)^3), which would break RSA on a sufficiently large quantum computer.
Common RSA Vulnerabilities
Diffie-Hellman (1976) solved a fundamental problem: two parties communicating over an insecure channel can agree on a shared secret without ever sending that secret. This was revolutionary — before DH, key exchange required a secure channel.
DH Protocol (Finite Field)
Public parameters: Large prime p and generator g (a primitive root mod p). These are published to everyone.
Alice: Chooses secret a at random. Computes A = g^a mod p. Sends A to Bob.
Bob: Chooses secret b at random. Computes B = g^b mod p. Sends B to Alice.
Alice computes: s = B^a mod p = (g^b)^a mod p = g^(ab) mod p
Bob computes: s = A^b mod p = (g^a)^b mod p = g^(ab) mod p
Shared secret: s = g^(ab) mod p. An eavesdropper sees p, g, A=g^a, B=g^b but cannot compute g^(ab) without solving the DH problem.
Small Numerical Example
Public: p = 23, g = 5
Alice picks a = 6: A = 5^6 mod 23 = 15625 mod 23 = 8
Bob picks b = 15: B = 5^15 mod 23 = 30517578125 mod 23 = 19
Alice: s = 19^6 mod 23 = 47045881 mod 23 = 2
Bob: s = 8^15 mod 23 = 35184372088832 mod 23 = 2 ✓
Shared secret: 2
The Computational Diffie-Hellman (CDH) assumption: given (g, g^a, g^b), computing g^(ab) is hard. The Decisional Diffie-Hellman (DDH) assumption is stronger: given (g, g^a, g^b, g^c), it is hard to decide whether c = ab (mod p-1) or c is random. DDH fails in some groups (e.g., quadratic residues mod p are transparent to the Legendre symbol) but holds for well-chosen groups. Note: DH without authentication is vulnerable to man-in-the-middle attacks — always combine with digital signatures or certificates (as in TLS).
For classical DH security, p must be chosen so p-1 has a large prime factor q (ideally p = 2q + 1, a safe prime). This prevents the Pohlig-Hellman algorithm from solving DLP in subgroups of small order. The prime should be at least 2048 bits for 112-bit security. RFC 3526 and RFC 7919 standardize well-vetted groups.
The discrete logarithm problem (DLP): given a cyclic group G of order q, generator g, and element h = g^x, find the integer x in [0, q-1]. It underlies the security of Diffie-Hellman, ElGamal encryption, DSA, and elliptic curve variants.
The baby-step giant-step (BSGS) algorithm solves DLP in O(sqrt(q)) time and space — a dramatic improvement over brute force O(q), but exponential in the key size. Let m = ceil(sqrt(q)). Write x = im + j. Then g^x = h becomes g^(im+j) = h, so g^j = h * (g^(-m))^i. Precompute {g^j mod p : j = 0,...,m-1} (baby steps), then for each i compute h*(g^(-m))^i and look up in the table (giant steps).
If the group order q = p1^e1 * p2^e2 * ... * pk^ek (smooth — factors are small), Pohlig-Hellman decomposes the DLP into smaller DLPs modulo each pi^ei, then combines via CRT. Running time is O(sum_i ei*(sqrt(pi) + log q)). This is why cryptographic groups must have a large prime-order subgroup — to block this attack.
For DLP in (Z/pZ)*, the index calculus algorithm achieves sub-exponential time L[1/3, c] = exp(c * (log p)^(1/3) * (log log p)^(2/3)), the same asymptotic complexity as the Number Field Sieve for factoring. This is why finite-field DH needs 2048+ bit primes to maintain 112-bit security, while ECC needs only 224+ bits — no sub-exponential algorithm is known for ECDLP.
An elliptic curve over a field F is the set of points (x, y) satisfying the Weierstrass equation y^2 = x^3 + ax + b (in characteristic not 2 or 3), together with a special point at infinity O. The discriminant 4a^3 + 27b^2 must be nonzero to ensure no singular points (cusps or self-intersections), which would break the group structure.
The set of curve points forms an abelian group under a geometric addition rule. Given two points P and Q on the curve:
Algebraic Formulas for Point Addition (P != Q)
P = (x1, y1), Q = (x2, y2)
slope lambda = (y2 - y1) / (x2 - x1)
x3 = lambda^2 - x1 - x2
y3 = lambda*(x1 - x3) - y1
Result: R = (x3, y3)
Algebraic Formulas for Point Doubling (P = Q)
P = (x1, y1)
slope lambda = (3*x1^2 + a) / (2*y1)
x3 = lambda^2 - 2*x1
y3 = lambda*(x1 - x3) - y1
Result: 2P = (x3, y3)
The primary operation in ECC is scalar multiplication: given point P and integer k, compute Q = kP = P + P + ... + P (k times). Like RSA's modular exponentiation, this uses double-and-add (analogous to square-and-multiply) in O(log k) point additions. Given P and Q = kP, recovering k is the Elliptic Curve Discrete Logarithm Problem (ECDLP) — believed to have no sub-exponential solution.
Curve: y^2 = x^3 + 2x + 2 over F_17
Points P = (5, 1), Q = (6, 3)
lambda = (3 - 1) * (6 - 5)^(-1) mod 17
= 2 * 1^(-1) mod 17 = 2
x3 = 2^2 - 5 - 6 mod 17 = 4 - 11 mod 17 = -7 mod 17 = 10
y3 = 2*(5 - 10) - 1 mod 17 = 2*(-5) - 1 mod 17 = -11 mod 17 = 6
P + Q = (10, 6)
Most deployed ECC uses standardized curves with precomputed parameters:
Elliptic Curve Diffie-Hellman (ECDH) replaces the finite field in DH with an elliptic curve group, achieving the same key exchange with much smaller keys. The structure is identical — the group operation is point addition instead of modular multiplication.
ECDH Protocol
Public parameters: Elliptic curve E, prime p, base point G of order n. Published to everyone.
Alice: Picks secret scalar a in [1, n-1]. Computes A = aG. Sends A to Bob.
Bob: Picks secret scalar b in [1, n-1]. Computes B = bG. Sends B to Alice.
Alice computes: S = aB = a(bG) = abG
Bob computes: S = bA = b(aG) = abG
Shared secret: The x-coordinate of S is used as the shared key material.
X25519 is the Curve25519-based ECDH function standardized in RFC 7748. It uses a Montgomery curve y^2 = x^3 + 486662*x^2 + x over the prime field F_(2^255 - 19). Montgomery form enables extremely efficient and constant-time scalar multiplication, resistant to timing side-channel attacks. X25519 is the default key exchange in TLS 1.3, OpenSSH, Signal Protocol, and WireGuard.
The Advanced Encryption Standard (AES, standardized 2001) is a symmetric block cipher operating on 128-bit blocks with 128, 192, or 256-bit keys. Its algebraic structure relies entirely on the finite field GF(2^8), the field of 256 elements.
Each byte (8 bits) represents a polynomial over GF(2) — coefficients are 0 or 1, and the byte b7b6b5b4b3b2b1b0 represents b7*x^7 + ... + b1*x + b0. The field GF(2^8) uses polynomial arithmetic modulo the irreducible polynomial m(x) = x^8 + x^4 + x^3 + x + 1 (0x11B in hex).
Multiplication Example in GF(2^8)
Multiply 0x57 * 0x83 in GF(2^8):
0x57 = x^6 + x^4 + x^2 + x + 1
0x83 = x^7 + x + 1
Product = x^13 + x^11 + x^9 + x^8 + x^7 + ... (expand, reduce mod m(x))
Result = 0xC1 (standard AES reference result)
AES-128 performs 10 rounds (AES-192: 12, AES-256: 14). Each round (except the last) applies four transformations to the 4x4 byte state matrix:
SubBytes
Each byte is replaced by its S-box value. The S-box computes the multiplicative inverse in GF(2^8) followed by an affine transformation over GF(2). This provides nonlinearity — without it, AES would be a linear cipher breakable by linear algebra. The inverse of 0x00 is defined as 0x00 itself.
ShiftRows
Row 0 is not shifted. Row 1 is cyclically shifted left by 1. Row 2 by 2. Row 3 by 3. This ensures bytes from different columns mix together in subsequent MixColumns steps.
MixColumns
Each column is treated as a 4-element vector over GF(2^8) and multiplied by a fixed 4x4 matrix. The matrix entries are {2, 3, 1, 1} (cyclic). Multiplication by 2 in GF(2^8) is a left shift plus conditional XOR with 0x1B (if the high bit was set). This step provides diffusion — each output byte depends on all four input bytes.
AddRoundKey
XOR the state with the round subkey derived by the key schedule. This is the only step that uses the key material. Without it, the cipher would be independent of the key.
For AES-128, the 128-bit key is expanded into eleven 128-bit round keys. Each word (32 bits) of the expanded key is derived by XOR of the previous word and a function of the word four positions back. The function applies SubBytes to the word, rotates it, and XORs with a round constant (powers of x in GF(2^8)). The non-trivial key schedule ensures that related keys produce unrelated subkeys, preventing related-key attacks.
A cryptographic hash function H: {0,1}* → {0,1}^n must satisfy three properties:
SHA-256, SHA-1, and MD5 use the Merkle-Damgard construction: pad the message, divide into fixed-size blocks M1, M2, ..., Mk, and iterate a compression function f: H0 = IV (fixed initial value), H_i = f(H_(i-1), M_i), output H_k. Security reduction: if f is collision-resistant, then the full hash is collision-resistant. Weakness: length extension attacks — given H(m), an attacker can compute H(m || pad || m') without knowing m. This is why HMAC wraps the hash with keys on both inside and outside.
SHA-256 produces a 256-bit digest. The message schedule expands each 512-bit block into 64 words of 32 bits using the recurrence:
W[i] = W[i-16] + sigma0(W[i-15]) + W[i-7] + sigma1(W[i-2]) (for i in 16..63)
where sigma0(x) = ROTR(x, 7) XOR ROTR(x, 18) XOR SHR(x, 3)
sigma1(x) = ROTR(x, 17) XOR ROTR(x, 19) XOR SHR(x, 10)
The 64-round compression loop updates eight 32-bit working variables (a..h):
T1 = h + Sigma1(e) + Ch(e,f,g) + K[i] + W[i]
T2 = Sigma0(a) + Maj(a,b,c)
where Ch(e,f,g) = (e AND f) XOR ((NOT e) AND g) -- choice
Maj(a,b,c) = (a AND b) XOR (a AND c) XOR (b AND c) -- majority
Sigma0(a) = ROTR(a,2) XOR ROTR(a,13) XOR ROTR(a,22)
Sigma1(e) = ROTR(e,6) XOR ROTR(e,11) XOR ROTR(e,25)
The 64 round constants K[0..63] are the fractional parts of the cube roots of the first 64 primes, providing pseudo-random bit patterns with no hidden structure (nothing-up-my-sleeve numbers). After all blocks are processed, the final eight working variables are concatenated as the 256-bit hash output.
SHA-3 (Keccak, standardized 2015) uses a sponge construction instead of Merkle-Damgard. The state is a 5x5x64 bit array (1600 bits). Absorb phase: XOR message blocks into part of the state, then apply the Keccak-f permutation (5 sub-steps: theta, rho, pi, chi, iota) for 24 rounds. Squeeze phase: output bits from the rate portion of the state, applying more permutations as needed. Sponge construction is immune to length-extension attacks by design.
The birthday paradox: in a group of n people, the probability that at least two share a birthday (among 365 days) exceeds 50% when n is just 23. The math: probability of NO collision among k people is 365/365 * 364/365 * ... * (365-k+1)/365. When k = 23, this product falls below 0.5.
For a hash function with N = 2^n possible outputs, the expected number of hashes before finding a collision is approximately sqrt(pi * N / 2) ≈ 1.25 * 2^(n/2). More precisely, after q queries, the collision probability is approximately 1 - e^(-q^2 / (2N)) by the birthday approximation. This means:
Birthday Attack on Digital Signatures
An attacker wanting to forge a signature exploits the birthday bound as follows: generate ~2^(n/2) variations of a legitimate message m and ~2^(n/2) variations of a fraudulent message m'. By the birthday bound, with high probability some m_i and m_j' will collide: H(m_i) = H(m_j'). If the victim signs m_i, the signature also verifies m_j'. This motivates using hash functions with n >= 256 bits for signature schemes requiring 128-bit security.
Pollard's rho algorithm applies the birthday idea to solve ECDLP. Define a sequence of curve points using a pseudo-random walk: X_(i+1) = f(X_i) where f is a simple partition-based function. Floyd's cycle detection finds a collision X_i = X_j with i != j using O(sqrt(n)) point additions and O(1) memory. This is the best known algorithm against ECDLP, confirming that a 256-bit curve (order ~2^256) provides about 128-bit security against this attack.
Digital signatures provide authentication, integrity, and non-repudiation. Unlike symmetric MACs, signatures are publicly verifiable — anyone with the public key can verify, but only the private key holder can sign.
Key Generation
Choose curve E, base point G of prime order n. Pick private key d in [1, n-1]. Compute public key Q = dG.
Signing message m
1. Compute hash e = H(m) (e.g., SHA-256), then z = the leftmost min(bit_length(e), bit_length(n)) bits.
2. Pick cryptographically random k in [1, n-1].
3. Compute curve point (x1, y1) = kG.
4. Compute r = x1 mod n. If r = 0, pick new k.
5. Compute s = k^(-1) * (z + r*d) mod n. If s = 0, pick new k.
6. Signature = (r, s).
Verification
1. Compute z from H(m) as above.
2. Compute u1 = z*s^(-1) mod n and u2 = r*s^(-1) mod n.
3. Compute point (x1, y1) = u1*G + u2*Q.
4. Signature is valid if r ≡ x1 (mod n).
Critical Security Requirement
If the nonce k is reused for two different messages m1 and m2, an attacker can recover the private key d. From signatures (r, s1) and (r, s2) on messages with hashes z1 and z2:
s1 - s2 = k^(-1) * (z1 - z2) (mod n)
k = (z1 - z2) * (s1 - s2)^(-1) (mod n)
d = (s1*k - z1) * r^(-1) (mod n)
This exact vulnerability broke the Sony PlayStation 3's signing key in 2010 — Sony used a constant k. It also compromised Bitcoin wallets with broken random number generators. Deterministic ECDSA (RFC 6979) derives k = HMAC(d, z) to eliminate RNG dependence.
EdDSA (Edwards-curve Digital Signature Algorithm) uses twisted Edwards curves ax^2 + y^2 = 1 + dx^2y^2 and is deterministic by design. Ed25519 uses the twisted Edwards form of Curve25519 with SHA-512 as hash. It is faster than ECDSA, immune to nonce reuse attacks (k is deterministically derived), and provides 128-bit security. Ed25519 is used in OpenSSH, Signal, Tor, and TLS 1.3.
A zero-knowledge proof (ZKP) is an interactive protocol between a prover P and a verifier V where P convinces V that a statement is true without revealing any information beyond the validity of the statement. The concept was introduced by Goldwasser, Micali, and Rackoff in 1985.
Peggy knows x such that y = g^x mod p. She wants to prove this without revealing x.
Commit: Peggy picks random r, computes t = g^r mod p. Sends t to Victor.
Challenge: Victor picks random c and sends it to Peggy.
Response: Peggy computes s = r + cx (mod q) and sends s to Victor.
Verify: Victor checks g^s ≡ t * y^c (mod p).
Why it works: g^s = g^(r+cx) = g^r * g^(cx) = t * (g^x)^c = t * y^c ✓
Zero-knowledge: the simulator picks s and c first, computes t = g^s * y^(-c), producing a valid-looking transcript without knowing x.
The Fiat-Shamir transform converts an interactive ZKP to a non-interactive one by replacing the verifier's random challenge with a hash of the commitment: c = H(t). The prover can now generate a proof offline. This is the foundation of Schnorr signatures and zk-SNARKs. Security relies on modeling H as a random oracle.
Succinct Non-interactive Arguments of Knowledge (SNARKs) allow proving arbitrary NP statements with constant-size proofs (a few hundred bytes) verifiable in milliseconds, regardless of witness size. They rely on polynomial commitments (e.g., KZG commitments using elliptic curve pairings) and the random oracle model. Applications: Zcash (private transactions), Ethereum L2 rollups (zkSync, StarkNet), anonymous credentials, and verifiable computation.
A lattice L in R^n is the set of all integer linear combinations of a basis {b1, b2, ..., bm}: L = {a1*b1 + a2*b2 + ... + am*bm : ai in Z}. The same lattice has infinitely many bases — some good (short, nearly orthogonal) and some bad (long, nearly parallel). Lattice problems ask about the geometry of these point sets.
Learning With Errors, introduced by Regev (2005), is the workhorse of modern lattice cryptography. Given a random matrix A and secret s, samples are (A, As + e) where e is a small error vector drawn from a Gaussian distribution. The LWE problem: distinguish (A, As + e) from (A, uniform). Solving LWE implies solving SVP in worst case, providing strong security guarantees. The parameters are: modulus q (typically ~10000 for 128-bit security), dimension n (~1000), and error standard deviation ~3.
Simple LWE-Based Encryption
Setup: Public matrix A in Z_q^(m x n), secret s in Z_q^n.
Public key: (A, b = As + e) where e is small error.
Encrypt bit mu in {0,1}: Pick random r, output (u = A^T * r, v = b^T * r + mu * floor(q/2)).
Decrypt: Compute v - s^T * u = mu * floor(q/2) + small error. Round to recover mu.
Plain LWE has large public keys (matrix A requires n^2 elements). Ring-LWE replaces Z_q with the polynomial ring Z_q[x]/(x^n + 1) for n a power of 2. This reduces key sizes from O(n^2) to O(n) and enables fast NTT (Number Theoretic Transform) for polynomial multiplication. CRYSTALS-Kyber and CRYSTALS-Dilithium are based on module-LWE (a generalization of Ring-LWE) and are the NIST post-quantum standards for key encapsulation and digital signatures respectively.
Shor's algorithm (1994) runs in polynomial time O((log N)^3) on a quantum computer and factors integers and solves discrete logarithms. A sufficiently powerful quantum computer would break RSA, Diffie-Hellman, and all elliptic curve systems in practical time. The threat is real enough that NIST ran a multi-year competition to standardize post-quantum algorithms, completing in 2024.
Grover's algorithm provides a quadratic speedup for unstructured search, reducing brute-force attacks on symmetric ciphers from O(2^n) to O(2^(n/2)). This means AES-128 would effectively have 64-bit security on a quantum computer. The mitigation is simple: use AES-256 (128-bit quantum security) and SHA-256 (128-bit quantum collision security, since Brassard-Hoyer-Tapp algorithm gives sqrt speedup for birthday attacks too).
CRYSTALS-Kyber (ML-KEM, FIPS 203)
Key encapsulation mechanism based on module-LWE over polynomial rings. Public keys ~800 bytes for 128-bit security. Ciphertexts ~768 bytes. Very fast with NTT-accelerated polynomial multiplication.
CRYSTALS-Dilithium (ML-DSA, FIPS 204)
Digital signature scheme based on module-LWE and module-SIS (Short Integer Solution). Public keys ~1312 bytes, signatures ~2420 bytes for 128-bit security. Strongly recommended for general use.
SPHINCS+ (SLH-DSA, FIPS 205)
Stateless hash-based signature scheme. Security based only on hash function security — minimal assumptions, very conservative. Larger signatures (~8 KB) but no algebraic structure to attack.
FALCON (FN-DSA, FIPS 206)
Signature scheme based on NTRU lattices and Fast Fourier sampling. Compact signatures (~666 bytes), but more complex to implement correctly. Requires careful floating-point arithmetic.
Hash-based signatures (Lamport, Merkle, XMSS, LMS) predate lattice cryptography and have the most conservative security proofs — security reduces to the one-wayness of the hash function alone. One-time Lamport signatures: to sign bit 0, reveal one preimage; to sign bit 1, reveal the other. A Merkle tree combines many one-time keys into a single public key. Stateful variants (XMSS, LMS) are already standardized in RFC 8391 and RFC 8554 for use cases like firmware signing.
McEliece (1978) is based on the hardness of decoding random linear error-correcting codes — a problem with no known quantum speedup. The original system has never been broken despite 45 years of cryptanalysis, though it has large public keys (~1 MB). Modern variants (BIKE, HQC, Classic McEliece) reduce key sizes using quasi-cyclic codes. Classic McEliece is a NIST alternate KEM standard.
SIKE (Supersingular Isogeny Key Encapsulation) was a promising post-quantum candidate with tiny keys (~197 bytes). An isogeny is a structure-preserving map between elliptic curves. Unfortunately, SIKE was completely broken in 2022 by Castryck and Decru using a classical algorithm exploiting auxiliary torsion point information. This highlighted the importance of diverse security assumptions and rigorous public cryptanalysis in standardization.
A critical threat model: adversaries are recording encrypted traffic today with the intention of decrypting it once quantum computers become available. Data with long-term secrecy requirements (government secrets, medical records, intellectual property) is already at risk. This motivates transitioning to post-quantum cryptography now, even before quantum computers are practical. TLS 1.3 already supports hybrid key exchange (e.g., X25519+Kyber) as a transitional measure.
RSA relies on the difficulty of factoring large integers. Key generation: choose two large primes p and q, compute n = pq and phi(n) = (p-1)(q-1). Pick public exponent e with gcd(e, phi(n)) = 1, then compute private exponent d = e^(-1) mod phi(n). Encryption: c = m^e mod n. Decryption: m = c^d mod n. Security rests on the RSA assumption — that computing m from c and (n, e) without knowing d is infeasible because factoring n is hard for large n.
Given prime p, generator g, and value h = g^x mod p, the DLP asks for x. Computing h from x is easy (fast modular exponentiation runs in O(log e) steps), but reversing it has no known polynomial-time algorithm for large primes. The best classical algorithms (GNFS, index calculus) run in sub-exponential time but are infeasible for 2048-bit primes. This asymmetry makes Diffie-Hellman and ElGamal secure.
ECC achieves equivalent security with much smaller key sizes. A 256-bit ECC key gives roughly the same security as a 3072-bit RSA key. This is because the elliptic curve discrete logarithm problem has no sub-exponential algorithm analogous to the Number Field Sieve used against RSA and finite-field DH. Smaller keys mean faster operations, lower bandwidth, and less power consumption — ideal for mobile and embedded systems.
Euler's theorem: if gcd(a, n) = 1, then a^phi(n) ≡ 1 (mod n). For RSA, since ed ≡ 1 (mod phi(n)), we write ed = 1 + k*phi(n). Then c^d = (m^e)^d = m^(ed) = m^(1+k*phi(n)) = m*(m^phi(n))^k ≡ m*1 = m (mod n). This proves decryption recovers m. The argument extends via CRT to the edge case when gcd(m,n) != 1.
The birthday paradox shows that collisions happen much earlier than expected. For a hash with 2^n possible outputs, a collision can be found in about 2^(n/2) trials — not 2^n. This means SHA-256 provides 128 bits of collision security (not 256), which is why 256-bit hashes are standard for 128-bit security targets. MD5 (128-bit outputs, 64-bit collision security) is now broken. SHA-1 (160-bit, 80-bit collision security) was broken in practice by the SHAttered attack.
A zero-knowledge proof lets a prover convince a verifier of a fact without revealing the witness. The Schnorr protocol is the cleanest example: to prove knowledge of x where y = g^x, Peggy sends t = g^r (random r), receives challenge c, responds with s = r + cx. Victor checks g^s = t*y^c. Peggy convinces Victor she knows x, but Victor learns nothing about x because every transcript (t, c, s) can be simulated. ZKPs underpin zk-SNARKs used in privacy-preserving blockchains.
Lattice cryptography builds security on hard geometric problems like Learning With Errors (LWE) and the Shortest Vector Problem (SVP). A lattice is a periodic grid of points in high-dimensional space. Finding the shortest vector or solving LWE has no known efficient quantum algorithm — Shor's algorithm, which breaks RSA and ECC in polynomial time on a quantum computer, does not apply. CRYSTALS-Kyber and CRYSTALS-Dilithium (NIST standards 2024) are lattice-based.
AES operates on bytes as elements of GF(2^8): polynomials over GF(2) reduced modulo x^8 + x^4 + x^3 + x + 1. Addition is XOR. Multiplication is polynomial multiplication then reduction mod the irreducible polynomial. SubBytes applies the GF(2^8) multiplicative inverse plus an affine transformation — this nonlinear step prevents linear algebraic attacks. MixColumns multiplies column vectors by a fixed matrix over GF(2^8), providing diffusion where every output byte depends on all four input bytes.
Number Theory
Primes, GCD, modular arithmetic foundations
Advanced Number Theory
Quadratic reciprocity, p-adic numbers, algebraic integers
Abstract Algebra
Groups, rings, fields — the algebraic structures behind crypto
Information Theory
Entropy, channel capacity, perfect secrecy
Probability Theory
Random variables, distributions, birthday paradox
Linear Algebra
Matrices, vector spaces — lattice geometry foundations
Test your understanding with step-by-step practice problems on modular arithmetic, RSA key generation, elliptic curve operations, and more.
Start Practicing Free