Discrete Math › Section G · Additional topics › Topic G.4

Cryptography: number theory at work

Every secure website relies on calculations that are easy to do and believed to be infeasible to undo. This topic shows how the modular arithmetic of the previous topics becomes RSA, a public-key system in which anyone can lock a message but only one person can unlock it.

Why secrecy needs mathematics

Encryption turns a readable message, the plaintext, into scrambled ciphertext that only someone holding the right key can turn back. The oldest schemes hid the method; modern ones publish the method and keep only the key secret, so their safety must rest on mathematics rather than on nobody guessing the trick. Number theory supplies the mathematics: problems such as factoring a large number are easy to set up but, as far as anyone knows, extremely slow to solve. This topic uses the gcd, inverses and Fermat's little theorem from "GCD, congruences, and modular arithmetic".

Shift ciphers: arithmetic mod 26

Number the letters A = 0, B = 1, …, Z = 25. A shift cipher with key \(k\) encrypts letter \(x\) as \(x + k \bmod 26\) and decrypts by subtracting \(k\). With \(k = 3\), the Caesar cipher, MATH becomes PDWK: M is 12 and \(12 + 3 = 15\), which is P, while T is 19 and \(19 + 3 = 22\), which is W. The scheme is hopeless: there are only 25 useful keys, so an attacker simply tries them all. Worse, each letter always maps to the same letter, so letter frequencies show through. A secure system needs an enormous key space and no such patterns.

The idea of public-key cryptography

Shift ciphers, like every classical scheme, are symmetric: the same key locks and unlocks, so the two parties must somehow share it secretly first. Public-key cryptography removes that problem. Each user has a public key, published openly and used by anyone to encrypt messages to them, and a private key, kept secret and needed to decrypt. It works like a padlock that anyone can snap shut but only the keyholder can open. The public and private keys are mathematically linked, but working out the private key from the public one must be infeasible. RSA, publicly described in 1977 by Rivest, Shamir and Adleman, was the first widely used system of this kind.

RSA key generation

To build an RSA key pair: 1. Choose two large primes \(p\) and \(q\), and compute \(n = pq\). 2. Compute \(\varphi(n) = (p - 1)(q - 1)\), the number of integers from 1 to \(n\) that are coprime to \(n\). 3. Choose an exponent \(e\) with \(\gcd(e, \varphi(n)) = 1\). 4. Find \(d\), the inverse of \(e\) modulo \(\varphi(n)\), so that \(ed \equiv 1 \pmod{\varphi(n)}\), using the extended Euclidean algorithm. The public key is the pair \((n, e)\); the private key is \(d\). The primes \(p\) and \(q\) and the value \(\varphi(n)\) must stay secret too, since anyone who knows them can compute \(d\).

Encrypting and decrypting

A message is first encoded as a number \(m\) with \(0 \le m < n\). To encrypt, compute

c = m^e \bmod n

To decrypt, the key holder computes \(c^d \bmod n\), which returns \(m\). Why does it work? Since \(ed = 1 + t\varphi(n)\) for some integer \(t\), we have \(c^d \equiv m^{ed} = m \cdot (m^{\varphi(n)})^t\). Euler's theorem, the extension of Fermat's little theorem to any modulus, says \(m^{\varphi(n)} \equiv 1 \pmod n\) whenever \(\gcd(m, n) = 1\), so \(c^d \equiv m\). A short extra argument covers the rare messages sharing a factor with \(n\).

Worked example: fast modular exponentiation

Real exponents have hundreds of digits, so \(m^e\) is never computed in full. Instead, square repeatedly, reducing each time, and multiply the powers matching the binary digits of the exponent. Find \(3^{45} \bmod 17\). 1. Write the exponent in binary: \(45 = 32 + 8 + 4 + 1\). 2. Square and reduce: \(3^2 \equiv 9\), \(3^4 \equiv 81 \equiv 13\), \(3^8 \equiv 169 \equiv 16\), \(3^{16} \equiv 256 \equiv 1\), \(3^{32} \equiv 1\). 3. Multiply the needed powers: \(3^{45} \equiv 1 \cdot 16 \cdot 13 \cdot 3 = 624 \equiv 12 \pmod{17}\). 4. Cross-check with Fermat: \(3^{16} \equiv 1\), so \(3^{45} \equiv 3^{13}\), which also reduces to 12. An exponent \(k\) needs only about \(2\log_2 k\) multiplications.

Worked example: a toy RSA system

Build keys from \(p = 11\) and \(q = 17\), then send \(m = 20\). 1. \(n = 187\) and \(\varphi(n) = 10 \cdot 16 = 160\). 2. Choose \(e = 7\); \(\gcd(7, 160) = 1\). Then \(d = 23\), because \(7 \cdot 23 = 161 = 160 + 1\). 3. Encrypt with square and multiply: \(20^2 = 400 \equiv 26\) and \(20^4 \equiv 26^2 = 676 \equiv 115\). So \(20^7 = 20^4 \cdot 20^2 \cdot 20 \equiv 115 \cdot 26 \cdot 20\). 4. \(115 \cdot 26 = 2990 \equiv 185\), and \(185 \cdot 20 = 3700 \equiv 147\). The ciphertext is \(c = 147\). 5. Decrypting, \(147^{23} \bmod 187 = 20\), the original message. Real keys use primes of hundreds of digits.

Why RSA is believed secure

An attacker sees \(n\), \(e\) and \(c\). Finding \(d\) directly would need \(\varphi(n)\), and computing \(\varphi(n) = (p - 1)(q - 1)\) needs the factors \(p\) and \(q\). So the security rests on factoring: multiplying two primes is quick, but no known method running on ordinary computers can factor a well-chosen 2048-bit \(n\), about 617 digits, in any practical time. Public factoring records are far smaller: the 250-digit challenge number RSA-250 fell in 2020, and every record is still well under 300 digits. Nobody has proved that factoring is hard, so the security is a well-tested belief, not a theorem. Careless choices, such as primes that are too close together, can also break it.

Signatures, hashing and the quantum threat

RSA also signs. The sender computes \(s = h^d \bmod n\), where \(h\) is a short hash, a numerical fingerprint of the message, and anyone checks that \(s^e \equiv h \pmod n\) using the public key. Only the private key could have produced \(s\), so the signature proves who sent the message and that it was not altered; signatures of this kind are how software updates and website certificates are checked. A large quantum computer running Shor's algorithm could factor efficiently and break RSA. In 2024 the US National Institute of Standards and Technology published its first post-quantum standards, built mainly on lattice problems.

Common mistakes to avoid

First, computing \(d\) modulo \(n\) instead of modulo \(\varphi(n)\). Second, choosing \(e\) that shares a factor with \(\varphi(n)\), so no inverse \(d\) exists. Third, computing \(m^e\) in full before reducing, which is impossible for real sizes; reduce after every multiplication. Fourth, thinking the public key reveals the private one: that would require factoring \(n\). Fifth, confusing the roles: encrypt to someone with their public key; sign with your own private key. Sixth, assuming a toy example is secure: \(n = 187\) factors instantly.

Key takeaways

Shift ciphers are arithmetic mod 26 and are trivially broken. Public-key systems publish a key for locking and keep a private key for unlocking. RSA takes \(n = pq\), \(\varphi(n) = (p-1)(q-1)\), \(e\) coprime to \(\varphi(n)\), and \(d = e^{-1} \bmod \varphi(n)\); it encrypts by \(c = m^e \bmod n\) and decrypts by \(m = c^d \bmod n\), which Euler's theorem justifies. Repeated squaring keeps the work small. Security rests on the belief that factoring is hard, which large quantum computers would undo, prompting post-quantum standards.

Flashcards

Flashcard

Shift cipher

x ↦ x + k (mod 26)

Caesar uses k = 3: MATH becomes PDWK.

Test your understanding

Question 1 of 5

What does the Caesar cipher (shift 3) turn the word DOG into?

Question 2 of 5

An RSA key uses p = 3, q = 11 and e = 3. What is the private exponent d?

Question 3 of 5

With the RSA public key (n, e) = (33, 3), what is the ciphertext for the message m = 4?

Question 4 of 5

Why can an attacker who knows the public key (n, e) not simply compute the private key d?

Question 5 of 5

How is an RSA digital signature made and checked?

← Previous topic