Number Theory in Cryptography
RSA
| Property | Statement |
|---|---|
| Key gen | Choose primes p,q; n=pq; e coprime to φ(n); d=e⁻¹ mod φ(n) |
| Encrypt | c=mᵉ mod n |
| Decrypt | m=cᵈ mod n |
Examples
Example 1. Why is RSA secure?
Solution. Factoring n=pq is computationally hard for large primes.
In Depth
Modern cryptography relies heavily on number theory. RSA encryption uses the difficulty of factoring large semiprimes \(n=pq\). Diffie–Hellman key exchange relies on the discrete logarithm problem in \((\mathbb{Z}/p\mathbb{Z})^*\). Elliptic curve cryptography (ECC) uses the discrete log on elliptic curve groups, achieving equivalent security with smaller keys.
The RSA algorithm: choose primes \(p,q\), set \(n=pq\), pick \(e\) with \(\gcd(e,\phi(n))=1\), compute \(d=e^{-1}\bmod\phi(n)\). Public key: \((n,e)\). Encryption: \(c=m^e\bmod n\). Decryption: \(m=c^d\bmod n\). Security: factoring \(n\) is believed hard for 2048-bit \(n\).
Elliptic curves over finite fields \(\mathbb{F}_p\) form groups under a geometric addition law. The group order is approximately \(p\) (Hasse's theorem: \(|\#E(\mathbb{F}_p)-p-1|\leq2\sqrt{p}\)). The discrete log on these groups has no known subexponential algorithm, making ECC very efficient.
Hash functions, digital signatures, and zero-knowledge proofs also use number-theoretic hardness assumptions. The Schnorr signature scheme uses discrete logs; the Fiat–Shamir transform converts interactive proofs to non-interactive ones; lattice-based cryptography (post-quantum) uses the hardness of the shortest vector problem.
Quantum computers threaten RSA and ECC: Shor's algorithm factors integers and computes discrete logs in polynomial time on a quantum computer. Post-quantum cryptography (NIST standardization ongoing) uses lattices, codes, and hash functions whose hardness is believed to resist quantum attacks.
Key Properties & Applications
The security of RSA depends on the integer factorization problem. The best known classical algorithm, the general number field sieve (GNFS), factors an \(n\)-bit number in \(L[1/3,(64/9)^{1/3}]\) time (subexponential but superpolynomial). For 2048-bit RSA, this is computationally infeasible with current hardware.
Elliptic curve Diffie–Hellman (ECDH) and ECDSA are the elliptic curve analogues of DH and DSA. A 256-bit ECC key provides security equivalent to a 3072-bit RSA key. ECC is preferred for constrained devices (IoT, smart cards) due to smaller key sizes and faster operations.
Post-quantum cryptography (PQC) designs systems secure against quantum computers. NIST standardized CRYSTALS-Kyber (key encapsulation, lattice-based) and CRYSTALS-Dilithium (signatures, lattice-based) in 2024. These rely on the hardness of the Learning With Errors (LWE) problem.
Further Reading & Context
The study of number theory cryptography connects to many areas of mathematics and its applications. Understanding the foundational definitions and theorems provides the basis for advanced work in analysis, algebra, and applied mathematics.
Historical development: most mathematical concepts evolved over centuries, with contributions from mathematicians across many cultures. The modern axiomatic treatment provides rigor, while computational tools enable practical application.
In modern mathematics, this topic appears in graduate courses and research across pure and applied mathematics. Connections to computer science, physics, and engineering make it a versatile and important area of study. Mastery of the core results and techniques opens doors to research in number theory, analysis, geometry, and beyond.
Recommended next steps: work through the standard theorems with full proofs, explore the connections to related topics listed above, and practice with a variety of problems ranging from computational exercises to theoretical proofs. The interplay between different areas of mathematics is one of the subject's greatest rewards.