Cryptography: number theory at work
Modern secure communication rests on number theory: easy calculations in one direction that are infeasible to reverse.
Why encryption needs mathematics
Encryption scrambles a message so that only someone with a key can read it. Classical ciphers, like shifting letters by a fixed amount (the Caesar cipher, arithmetic mod 26), are easy to break. Modern systems use number-theoretic problems believed to be extremely hard to solve without a secret key.
Public-key cryptography
In public-key systems, each person has a public key that anyone can use to encrypt messages to them and a private key that only they use to decrypt. This solves the problem of sharing a secret key in advance, and it makes secure online shopping and messaging possible.
RSA: key generation
Choose two large primes \(p\) and \(q\) and compute \(n = pq\). Compute \(\varphi(n) = (p-1)(q-1)\). Choose \(e\) coprime to \(\varphi(n)\), and find \(d\) with \(ed \equiv 1 \pmod{\varphi(n)}\) using the extended Euclidean algorithm. The public key is \((n, e)\); the private key is \(d\).
ed \equiv 1 \pmod{\varphi(n)}RSA: encryption and decryption
To encrypt a message number \(m\), compute \(c = m^e \bmod n\). To decrypt, compute \(m = c^d \bmod n\). Fermat's little theorem, extended by Euler, guarantees that decryption recovers the original message. Fast modular exponentiation makes both steps quick.
c = m^e \bmod n,\quad m = c^d \bmod nWorked example with small numbers
Take \(p = 5\), \(q = 11\), so \(n = 55\) and \(\varphi(n) = 40\). Choose \(e = 3\); then \(d = 27\), since \(3 \cdot 27 = 81 \equiv 1 \pmod{40}\). Encrypt \(m = 7\): \(7^3 = 343 \equiv 13 \pmod{55}\). Decrypting \(13^{27} \bmod 55\) returns 7. Real RSA uses primes hundreds of digits long.
Why RSA is secure
Anyone knows \(n\) and \(e\), but finding \(d\) requires \(\varphi(n)\), which requires factoring \(n\) into \(p\) and \(q\). Multiplying primes is easy; factoring a 2048-bit product is believed to be infeasible with current computers. Security rests on this one-way difficulty.
Digital signatures and hashing
Running RSA in reverse creates digital signatures: signing with the private key lets anyone verify with the public key that a message came from you and was not altered. Combined with cryptographic hash functions, signatures secure software updates and website certificates.
The future: quantum computing
Shor's algorithm would let a large quantum computer factor numbers efficiently, breaking RSA. Cryptographers are therefore developing post-quantum algorithms based on other hard problems, such as lattice problems, and standards bodies have begun adopting them.
Key takeaways
Public-key cryptography uses a public key to encrypt and a private key to decrypt. RSA chooses \(n = pq\) and exponents with \(ed \equiv 1 \pmod{\varphi(n)}\), encrypting by \(m^e\) and decrypting by \(c^d\) mod \(n\). Its security relies on the difficulty of factoring, which quantum computers could threaten.
Flashcard
Shift letters by a fixed amount
Check your understanding
In RSA, why can't an attacker who knows the public key (n, e) easily find the private key d?