Computer Science › Section M · Theory of computation › Topic M.6
Public-key cryptography
Hard problems are usually obstacles, but cryptography turns one into a shield. RSA lets anyone lock a message with a published key while only the owner can unlock it, because multiplying two primes is easy and undoing the multiplication, as far as anyone knows, is not.
Turning hardness into an asset
"Cybersecurity: encryption and authentication" introduced the idea of public-key encryption: anyone may encrypt with the public key, but only the matching private key decrypts. This topic shows how the RSA system, described publicly in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman, actually does it. Its security rests on a gap in complexity. Multiplying two large primes takes a computer a fraction of a second, but no known method running on ordinary computers can recover the primes from their product in any practical time when the primes are hundreds of digits long.
Modular arithmetic
RSA calculates with remainders. The value \(x \bmod m\), read "x mod m", is the remainder when x is divided by m, written x % m in Python: 23 % 7 is 2, 40 % 8 is 0 and 5 % 9 is 5. The result always lies between 0 and \(m - 1\). A key property is that remainders can be taken after every multiplication without changing the final answer. That lets Python's pow(m, e, n) compute \(m^e \bmod n\) quickly even when \(m^e\) itself would have millions of digits. The method, repeated squaring, is worked by hand in "Cryptography: number theory at work" in Discrete Mathematics.
Setting up RSA keys
1. Choose two different primes p and q, and compute \(n = pq\). 2. Compute \(\varphi = (p - 1)(q - 1)\). 3. Choose an encryption exponent e greater than 1 that shares no factor with \(\varphi\). 4. Find the decryption exponent d with \(ed \bmod \varphi = 1\); in Python 3.8 or later, pow(e, -1, phi) gives it. The public key is the pair n and e, which can be handed to anyone. The private key is d. The primes p and q and the value \(\varphi\) must also stay secret, because anyone who knows them can compute d.
Encrypting and decrypting
A message is first encoded as a whole number m with \(0 \le m < n\), for instance using a character's code; longer messages are split into blocks. The sender, using only the public key, computes the ciphertext
The owner, using the private key, recovers the message:
The sender never needs d, and an eavesdropper who sees c, n and e cannot simply run the decryption step, because d is not public.
Worked example: building keys and sending a letter
1. Take p = 13 and q = 19, so n = 247 and \(\varphi = 12 \times 18 = 216\). 2. Choose e = 5, which shares no factor with 216. 3. Then d = 173, because \(5 \times 173 = 865 = 4 \times 216 + 1\). The public key is (247, 5) and the private key is 173. 4. Send the letter H, ASCII code 72: \(72^5 = 1{,}934{,}917{,}632\), which is \(247 \times 7{,}833{,}674 + 154\), so c = 154. 5. The owner computes pow(154, 173, 247), which returns 72, the letter H. Check: the letter I, code 73, encrypts to 99, and pow(99, 173, 247) returns 73.
Why decryption works
Because \(ed \bmod \varphi = 1\), we can write \(ed = 1 + k\varphi\) for some whole number k. Decrypting therefore computes \(m^{ed} = m^{1 + k\varphi}\), reduced mod n. A result from number theory, built on Fermat's little theorem, shows that \(m^{1 + k\varphi} \bmod n = m\) for every m from 0 to \(n - 1\), whenever p and q are different primes. Beware a tempting shortcut: \(m^{k\varphi} \bmod n = 1\) holds only when m shares no factor with n. With n = 15 and \(\varphi = 8\), \(3^8 \bmod 15 = 6\), yet \(3^9 \bmod 15 = 3\), just as RSA needs.
Worked example: breaking a small key
Eve intercepts c = 16, sent with the public key n = 299 and e = 5. 1. She factors n by trial division, testing primes up to \(\sqrt{299} \approx 17.3\): 2, 3, 5, 7 and 11 fail, and 13 works, so \(299 = 13 \times 23\). 2. Then \(\varphi = 12 \times 22 = 264\). 3. The inverse of 5 is d = 53, since \(5 \times 53 = 265 = 264 + 1\). 4. Decrypting, pow(16, 53, 299) returns 100. Check: pow(100, 5, 299) returns 16, the intercepted value. Every step after the factoring was quick; factoring was the only obstacle, and for 299 it was tiny.
Why big keys are safe
Current guidance calls for an n of at least 2,048 bits, about 617 decimal digits. Trial division would test candidates up to \(\sqrt{n}\), about \(10^{308}\) of them. The best known factoring methods are vastly faster than that, but still far from polynomial in the number of digits, and the largest RSA challenge numbers factored in public have about 250 digits. The owner's work, by contrast, is easy: finding large primes, multiplying them and running pow are all polynomial-time tasks. That lopsided difficulty, quick to build and use, infeasible to break, is exactly what a public-key system needs.
What the security rests on
Factoring is in NP, since a claimed factor is checked by one division, but as "Complexity of problems: P and NP" explained, no polynomial-time algorithm for it is known on ordinary computers, and it is not believed to be NP-complete. No one has proved factoring is hard, or even that breaking RSA requires factoring. So RSA's security is a well-tested assumption, not a theorem: a proof that P = NP with a practical algorithm would break it, but a proof that P ≠ NP would not by itself guarantee it. A large quantum computer running Shor's algorithm, published in 1994, could factor efficiently, which is why post-quantum standards are being adopted.
Signatures and real-world use
RSA also signs. The owner computes \(s = h^d \bmod n\), where h is a hash of the message, and anyone checks that \(s^e \bmod n\) gives h back. With the keys from the first worked example, h = 42 gives s = 35, and pow(35, 5, 247) returns 42. In practice, plain RSA as shown here is not secure: the same message always gives the same ciphertext, so real systems add random padding before encrypting. Because RSA is slow, it usually protects only a short symmetric key or a signature, as in HTTPS, and many systems now prefer elliptic-curve methods for key exchange.
Common mistakes to avoid
First, computing d modulo n instead of modulo \(\varphi\): for p = 5, q = 11 and e = 3, the inverse of 3 mod 55 is 37, but the correct d, mod 40, is 27. Second, choosing an e that shares a factor with \(\varphi\), so no d exists. Third, publishing p, q or \(\varphi\), which hands over d. Fourth, encrypting a number m that is not less than n. Fifth, thinking the public key can decrypt. Sixth, believing \(m^{\varphi} \bmod n = 1\) for every m. Seventh, treating unpadded textbook RSA, or a toy n, as secure.
Key takeaways
RSA picks primes p and q, sets \(n = pq\) and \(\varphi = (p - 1)(q - 1)\), chooses e sharing no factor with \(\varphi\), and finds d with \(ed \bmod \varphi = 1\). The public key is n and e; d, p, q and \(\varphi\) stay private. Encrypt with \(c = m^e \bmod n\) and decrypt with \(m = c^d \bmod n\), using pow for speed. Anyone who factors n can compute d, so security rests on factoring being infeasible for numbers of hundreds of digits, an unproved but well-tested assumption that large quantum computers would undo. Signatures swap the roles of e and d, and real systems add padding.
Flashcards
Flashcard
The remainder when x is divided by m
Test your understanding
Question 1 of 5
What is 47 mod 6, written 47 % 6 in Python?
Question 2 of 5
RSA keys are built from p = 5 and q = 11, with e = 3. What is d?
Question 3 of 5
With the public key n = 55 and e = 3, what is the ciphertext for the message m = 9?
Question 4 of 5
Why is it safe for an RSA key owner to publish n and e?
Question 5 of 5
How does an RSA owner sign a message whose hash is h?
