Discrete Mathematics and Proof

RSA public-key encryption

Can someone publish the instructions for locking a message to them, so that anyone at all can send them a secret, and still be the only person able to unlock it?

You need

Modular inverses and linear congruencesDiscrete Mathematics and Proof Fermat's little theoremDiscrete Mathematics and Proof

Where you are 7 in Modular arithmetic

Logic, proof and discrete math6

Introductory number theory8

Modular arithmetic7

▴ 2 above Where the divisibility tests come from Fermat's little theorem Modular inverses and linear congruences

RSA public-key encryption

The Chinese remainder theorem

Why this exists

A classical cipher uses one key to lock and the same key to unlock. Two people who want to write in secret must first agree on that key, and agreeing on it in secret is the very problem the cipher was meant to solve. A public-key system splits the key in two. The locking key is published, so anyone can lock a message; the unlocking key is held by one person, and knowing how to lock does not reveal how to unlock.

Number theory supplies such a pair. Raising to a power modulo n is fast even for numbers hundreds of digits long (Powers modulo n). Undoing the power is easy for whoever knows the prime factors of n, and as far as anyone knows it is hopelessly slow for everyone else. The scheme built on this is named RSA, after Rivest, Shamir and Adleman, who published it in 1977.

Definition

Day 1: the keys, locking and unlocking

Making the keys. Choose two different primes p and q and put

n = pq, \qquad \varphi(n) = (p - 1)(q - 1).

Choose an integer e with 1 < e < \varphi(n) and \gcd(e, \varphi(n)) = 1. Let d be the inverse of e modulo \varphi(n) with 1 < d < \varphi(n), so

ed \equiv 1 \pmod{\varphi(n)}.

It exists because \gcd(e, \varphi(n)) = 1 (Theorem 1 of Modular inverses and linear congruences) and the Bezout's identity and the extended Euclidean algorithm finds it. The public key is the pair (n, e). The private key is d; the numbers p, q and \varphi(n) are kept secret too.

Locking and unlocking. A message is an integer m with 0 \le m < n. Its ciphertext is

c = m^e \bmod n,

which anyone holding the public key can compute. The key holder recovers the message as c^d \bmod n. Theorem 2 below proves that this returns m.

Words as numbers. Write each letter as two digits, \mathrm{A} = 01, \mathrm{B} = 02, up to \mathrm{Z} = 26, and run the digits of a short block of letters together. The word IT becomes 0920, the number 920. Two letters give at most 2626, so for any n > 2626 a two-letter block is a valid message, and a longer text is cut into such blocks. This code is public. The secret lies only in d.

Day 2: what is public and what is secret

Someone listening in sees n, e and c. To unlock they need d; d comes from \varphi(n) by the extended Euclidean algorithm; and \varphi(n) comes from p and q. Day 2 shows that the chain also runs backward: \varphi(n) gives away p and q. So the whole scheme stands on how hard it is to factor n.

The same keys also sign a message. The key holder publishes s = m^d \bmod n with m, and anyone can check that s^e \bmod n = m. No one is known to be able to produce such an s without d or the factors of n.

Intuition

Think of (n, e) as an open padlock that its owner hands out freely. Anyone can snap it shut on a message; only the owner has the key that opens it.

Figure 1Locking uses only the public numbers 2773 and 17. Unlocking needs the private exponent 157.

Why the two powers undo each other: ed is one more than a multiple of (p-1)(q-1). By Fermat's little theorem a power of m whose exponent is a multiple of p - 1 is 1 modulo p (when p \nmid m), so m^{ed} is m times such a power, which is m modulo p. The same holds modulo q, and two different primes together pin down the remainder modulo pq.

Results

Throughout, p and q are different primes, n = pq, and e, d are positive integers with ed \equiv 1 \pmod{(p-1)(q-1)}.

Theorem 1. \varphi(pq) = (p - 1)(q - 1), where \varphi(n) counts the integers from 1 to n that share no factor greater than 1 with n.

Theorem 2 (unlocking works). For every integer m, m^{ed} \equiv m \pmod{n}. So for 0 \le m < n, \left(m^e \bmod n\right)^d \bmod n = m.

Theorem 3 (\varphi(n) gives the factors). p and q are the two roots of

x^2 - \bigl(n - \varphi(n) + 1\bigr)x + n = 0.

Theorem 4 (signatures). If 0 \le m < n and s = m^d \bmod n, then s^e \bmod n = m.

Lemma 5 (trial division). A composite n has a prime factor at most \displaystyle \sqrt{n}.

Stated without proof. (a) From n, e and any working d, there is a known fast method, using random choices, that factors n; so finding d is as hard as factoring n, and by Theorem 3 as hard as finding \varphi(n). (b) No fast method is known for factoring a product of two large primes, and none has been proved impossible. RSA is believed safe because of (b): it is a belief about factoring, not a theorem.

Why it is true

Euclid’s lemma and the coprime factor lemma (a \mid m, b \mid m and \gcd(a, b) = 1 give ab \mid m) are proved in Bezout's identity and the extended Euclidean algorithm.

Proof of Theorem 1. Let 1 \le k \le n. If \gcd(k, n) > 1, some prime r divides both, and r \mid pq gives r = p or r = q by Euclid’s lemma. So k shares a factor with n exactly when p \mid k or q \mid k. From 1 to pq there are q multiples of p, p multiples of q, and one multiple of both (a multiple of both is a multiple of pq by the coprime factor lemma, and only pq itself is in range). By inclusion and exclusion, p + q - 1 numbers share a factor with n, and

\varphi(n) = pq - p - q + 1 = (p - 1)(q - 1). \qquad \square

Proof of Theorem 2. Since ed \ge 1 and ed \equiv 1, write ed = 1 + k(p-1)(q-1) with k a nonnegative integer. Work modulo p. If p \mid m, both m^{ed} and m are 0 modulo p. If p \nmid m, Fermat’s little theorem gives m^{p-1} \equiv 1 \pmod{p}, so

\begin{aligned} m^{ed} &= m \cdot \bigl(m^{p-1}\bigr)^{k(q-1)} \\ &\equiv m \cdot 1 = m \pmod{p}. \end{aligned}

Either way p \mid m^{ed} - m. The same argument with the roles of p and q exchanged gives q \mid m^{ed} - m. As p \ne q are primes, \gcd(p, q) = 1, and the coprime factor lemma gives pq \mid m^{ed} - m. (This is the uniqueness half of the The Chinese remainder theorem: the remainders modulo p and modulo q pin down the remainder modulo pq.)

For the second sentence, c = m^e \bmod n has c \equiv m^e, so c^d \equiv m^{ed} \equiv m. The remainder c^d \bmod n is the one number in \{0, 1, \dots, n - 1\} congruent to c^d, and m is such a number, so it is m. \square

Euler’s theorem (Fermat's little theorem, Theorem 7) would only cover \gcd(m, n) = 1. Working one prime at a time covers every m, including the few that share a factor with n.

Proof of Theorem 3. By Theorem 1, n - \varphi(n) + 1 = pq - (pq - p - q + 1) + 1 = p + q. And (x - p)(x - q) = x^2 - (p + q)x + pq, whose roots are p and q. \square

Proof of Theorem 4. s^e \equiv m^{de} = m^{ed} \equiv m \pmod{n} by Theorem 2, and m is the remainder because 0 \le m < n. \square

Proof of Lemma 5. Write n = ab with 1 < a \le b. Then a^2 \le ab = n, so \displaystyle a \le \sqrt{n}, and any prime factor of a is at most a and divides n. \square

Worked examples

Example 1

Day 1, Example 1: building Laszlo’s keys

Laszlo picks the primes p = 47 and q = 59 and the public exponent e = 17. Find n and \varphi(n), check that e is allowed, and find d.

Solution

n = 47 \cdot 59 = 2773, and by Theorem 1, \varphi(n) = 46 \cdot 58 = 2668. Run the Euclidean algorithm on 2668 and 17:

2668 = 156 \cdot 17 + 16, \qquad 17 = 1 \cdot 16 + 1.

The last nonzero remainder is 1, so \gcd(17, 2668) = 1 and e is allowed. Substituting back,

\begin{aligned} 1 &= 17 - 16 = 17 - (2668 - 156 \cdot 17) \\ &= 157 \cdot 17 - 2668. \end{aligned}

So 17 \cdot 157 \equiv 1 \pmod{2668} and d = 157. Check: 17 \cdot 157 = 2669 = 2668 + 1. Laszlo publishes (2773, 17) and keeps 157, 47, 59 and 2668 to himself.

Example 2

Day 1, Example 2: locking and unlocking a word

A friend sends Laszlo the word IT. Lock it with his public key, then unlock the result with d.

Solution

IT is 0920, so m = 920 < 2773. To lock, 17 = 16 + 1, so square four times modulo 2773 (Powers modulo n): the powers 920^{2^k} for k = 0, 1, 2, 3, 4 are 920, 635, 1140, 1836, 1701. Then c \equiv 920^{16} \cdot 920 \equiv 1701 \cdot 920, and 1701 \cdot 920 = 1{,}564{,}920, which is 564 \cdot 2773 + 948. So c = 948. The friend sends 948.

To unlock, 157 = 128 + 16 + 8 + 4 + 1, so Laszlo squares 948 seven times. The powers 948^{2^k} for k = 0, 1, \dots, 7 are 948, 252, 2498, 754, 51, 2601, 1854, 1569. Multiplying those for k = 0, 2, 3, 4, 7 and reducing after each product,

\begin{aligned} 948 \cdot 2498 &\equiv 2735, & 2735 \cdot 754 &\equiv 1851, \\ 1851 \cdot 51 &\equiv 119, & 119 \cdot 1569 &\equiv 920. \end{aligned}

So 948^{157} \bmod 2773 = 920, which reads IT. The friend never needed 157; Laszlo never needed anything but 157 and 2773.

Example 3

Day 1, Example 3: a message that shares a factor with n

Show, without computing the power, that the message m = 188 comes back unchanged under Laszlo’s keys, that is 188^{2669} \equiv 188 \pmod{2773}, even though \gcd(188, 2773) = 47.

Solution

Here ed = 2669. Follow the proof of Theorem 2 one prime at a time.

Modulo 47: 188 = 4 \cdot 47, so both 188^{2669} and 188 are 0.

Modulo 59: 188 = 3 \cdot 59 + 11, so 188 \equiv 11, and 59 \nmid 11. Fermat’s little theorem gives 11^{58} \equiv 1 \pmod{59}, and 2669 = 46 \cdot 58 + 1, so

\begin{aligned} 188^{2669} &\equiv 11^{2669} = \bigl(11^{58}\bigr)^{46} \cdot 11 \\ &\equiv 11 \equiv 188 \pmod{59}. \end{aligned}

So 47 and 59 both divide 188^{2669} - 188. They are different primes, so by the coprime factor lemma 2773 divides it. Euler’s theorem alone could not have said this, since 188 is not coprime to 2773.

Example 4

Day 2, Example 4: phi of n gives away the primes

Suppose the number \varphi(n) = 2668 leaked along with Laszlo’s public n = 2773. Recover p and q.

Solution

By Theorem 3, p + q = 2773 - 2668 + 1 = 106 and pq = 2773, so p and q are the roots of x^2 - 106x + 2773 = 0. The discriminant is

\begin{aligned} 106^2 - 4 \cdot 2773 &= 11{,}236 - 11{,}092 \\ &= 144 = 12^2, \end{aligned}

so \displaystyle x = \frac{106 \pm 12}{2}, which is 59 or 47. Check: 47 \cdot 59 = 2773. Knowing \varphi(n) is worth exactly as much as knowing the factors; and from \varphi(n), Example 1 gives d at once.

Example 5

Day 2, Example 5: breaking a small key by trial division

For practice Laszlo also publishes the small key (1909, 5). Someone sends him c = 972. Find the message using only the public key.

Solution

Factor n. Since 43^2 = 1849 < 1909 < 1936 = 44^2, Lemma 5 says that if 1909 is composite it has a prime factor at most 43. Dividing by 2, 3, 5, 7, 11, 13, 17, 19 leaves remainders 1, 1, 4, 5, 6, 11, 5, 9, and then 1909 = 23 \cdot 83. So \varphi(n) = 22 \cdot 82 = 1804. For d:

\begin{aligned} 1804 &= 360 \cdot 5 + 4, \qquad 5 = 1 \cdot 4 + 1, \\ 1 &= 5 - (1804 - 360 \cdot 5) \\ &= 361 \cdot 5 - 1804, \end{aligned}

so d = 361. Now 361 = 256 + 64 + 32 + 8 + 1, and the powers 972^{2^k} modulo 1909 for k = 0, 1, \dots, 8 are 972, 1738, 606, 708, 1106, 1476, 407, 1475, 1274. Those for k = 0, 3, 5, 6, 8 multiply to

\begin{aligned} 972 \cdot 708 &\equiv 936, & 936 \cdot 1476 &\equiv 1329, \\ 1329 \cdot 407 &\equiv 656, & 656 \cdot 1274 &\equiv 1511. \end{aligned}

So m = 1511, the letters 15, 11: OK. Check by locking again: 1511^5 \bmod 1909 = 972. The attack took at most 14 trial divisions. For a modulus of 617 digits, Lemma 5 points to the primes below about 10^{308}, and there are more than 10^{300} of them.

Example 6

Day 2, Example 6: a signature anyone can check

Laszlo signs the word TO with his key (2773, 17), d = 157. Find what anyone does to check the signature s = 2672, and say why only Laszlo could have made it.

Solution

TO is m = 2015. Laszlo computed s = 2015^{157} \bmod 2773 = 2672 by repeated squaring, as in Example 2. A reader checks with the public e = 17 = 16 + 1: the powers 2672^{2^k} for k = 0, 1, 2, 3, 4 are 2672, 1882, 803, 1473, 1243. Then s^{17} \equiv 1243 \cdot 2672, and 1243 \cdot 2672 = 3{,}321{,}296, which is 1197 \cdot 2773 + 2015. So s^{17} \bmod 2773 = 2015, which is TO, and the signature checks (Theorem 4). Producing a number whose seventeenth power is 2015 modulo 2773 means taking a 17th root modulo 2773, which is exactly unlocking; no way to do that without d or the factors of 2773 is known.

Boundaries

p and q must be different. With p = q the coprime factor step fails and (p-1)^2 \ne \varphi(p^2); Exercise 7 shows decryption failing.
e must be coprime to \varphi(n). Otherwise there is no d. For Laszlo’s key, 2668 = 2^2 \cdot 23 \cdot 29, so e = 23 cannot be used.
The message must satisfy 0 \le m < n. The messages m and m + n give the same ciphertext, and unlocking returns the one below n.
The bare scheme gives the same ciphertext every time. Anyone can lock a guessed message and compare, and if m^e < n there is no wrap-around at all and an ordinary root recovers m. (Real systems pad a message with random digits first and mostly use RSA to lock a short key for a faster cipher.)
Safety is not proved. It rests on fact (b): no fast factoring method is known.

Real keys are large. The modulus n is commonly 2048 or 3072 binary digits long (617 or 925 decimal digits), p and q each about half that length, and e is very often 65{,}537 = 2^{16} + 1.

Where this goes next

The The Chinese remainder theorem lets the key holder unlock modulo p and modulo q separately, with exponents and numbers half the size, and combine the two remainders, which is how unlocking is sped up in practice. Finding primes hundreds of digits long uses the Fermat test of Fermat's little theorem in a strengthened form. And the question behind fact (b), how fast an integer can be factored, is one of the central open problems connecting number theory to computing.

Exercises

Day 1: keys and computing

Take p = 23 and q = 41. Find n and \varphi(n), and say which of e = 3, 5, 7, 11 may be used.
For the key of Exercise 1 with e = 7, find d.
Laszlo’s \varphi(n) is 2668. Which of e = 3, 23, 29, 31 could he have chosen?
Take n = 91 = 7 \cdot 13 and e = 5. Find d, lock m = 10, and unlock the result.
Lock the word NO with Laszlo’s key (2773, 17).
With n = 943, e = 7 and d = 503, show that 46^{3521} \equiv 46 \pmod{943} by working modulo 23 and modulo 41, without computing the power.

Day 1: reasoning

Use p = q = 5, n = 25, (p-1)(q-1) = 16, e = 3 and d = 11. Show that m = 2 does not come back, and name the step of the proof of Theorem 2 that fails.
Lock m = 118 with Laszlo’s key and find \gcd(c, 2773). Then prove: if \gcd(m, n) = p and c = m^e \bmod n, then \gcd(c, n) = p.
Prove that locking leaves 0, 1 and n - 1 unchanged. (First show e is odd.)
Let L be the least common multiple of p - 1 and q - 1. Prove that Theorem 2 still holds when only ed \equiv 1 \pmod{L} is assumed.
Prove that locking, m \mapsto m^e \bmod n, is a bijection of \{0, 1, \dots, n - 1\} to itself.

Day 2: breaking small keys

A key has n = 5183, and \varphi(n) = 5040 has leaked. Find p and q.
Break the public key (1679, 5): factor n by trial division and find d.
The key (1927, 3) has private exponent d = 1227, which has leaked. Use ed - 1 = k\,\varphi(n) with k < e (Exercise 21) to find \varphi(n), p and q.
Two keys have n_1 = 2773 and n_2 = 3901. Use the Euclidean algorithm to show they share a prime, and factor n_2.
A key (2773, 3) is used, and c = 2197 is sent. Check that e = 3 is allowed, and find m without d.
A key (943, 7) signs m = 100 with s = 625. Check the signature.
Show that every 2048-bit modulus, 2^{2047} \le n < 2^{2048}, has exactly 617 decimal digits.

Day 2: reasoning

Anyone can pick a number s', compute m' = s'^e \bmod n, and claim s' is a signature on m'. Explain why this does not let them sign a message of their own choosing.
Someone knows that a friend sent Laszlo either OK or NO under the key (2773, 17), and sees c = 884 go by. Explain how they learn which, without d.
With 1 < d < \varphi(n) and ed = 1 + k\,\varphi(n), prove that 1 \le k < e.

Answers

n = 943, \varphi(n) = 22 \cdot 40 = 880 = 2^4 \cdot 5 \cdot 11. Allowed: e = 3 and e = 7. Not allowed: 5 and 11, which divide 880.
d = 503. 880 = 125 \cdot 7 + 5, 7 = 5 + 2, 5 = 2 \cdot 2 + 1, so 1 = 3 \cdot 5 - 2 \cdot 7 = 3 \cdot 880 - 377 \cdot 7, and -377 \equiv 503. Check: 7 \cdot 503 = 3521 = 4 \cdot 880 + 1.
e = 3 and e = 31. Since 2668 = 2^2 \cdot 23 \cdot 29, the values 23 and 29 share a factor with it; 3 and 31 are primes not dividing it.
\varphi(91) = 72; 72 = 14 \cdot 5 + 2, 5 = 2 \cdot 2 + 1 give 1 = 29 \cdot 5 - 2 \cdot 72, so d = 29. Lock: 10^2 \equiv 9, 10^4 \equiv 81, 10^5 \equiv 810 \equiv 82, so c = 82. Unlock: 82 \equiv -9 squares to 81, 9, 81, 9; with 29 = 16 + 8 + 4 + 1, 82^{29} \equiv 9 \cdot 81 \cdot 9 \cdot 82, and 9 \cdot 81 = 729 \equiv 1, 9 \cdot 82 = 738 \equiv 10.
c = 884. NO is 1415; its squares modulo 2773 are 1415, 119, 296, 1653, 1004, and 1004 \cdot 1415 = 1{,}420{,}660 \equiv 884.
Modulo 23: 46 \equiv 0, both sides 0. Modulo 41: 46 \equiv 5 and 3521 = 88 \cdot 40 + 1, so 5^{3521} = (5^{40})^{88} \cdot 5 \equiv 5 by Fermat. Both primes divide 46^{3521} - 46, so 943 does.
ed = 33 and 2^{10} = 1024 \equiv -1 \pmod{25}, so 2^{33} \equiv -8 \equiv 17. Unlocking gives 17, not 2. The step that fails is the last: working modulo p and modulo q gives the same fact 5 \mid m^{ed} - m twice, and since \gcd(5, 5) \ne 1 the coprime factor lemma cannot turn it into 25 \mid m^{ed} - m. Indeed 17 \equiv 2 \pmod 5 but not modulo 25, and (p-1)(q-1) = 16 \ne 20 = \varphi(25).
c = 1239 = 21 \cdot 59 and \gcd(1239, 2773) = 59, the factor 118 = 2 \cdot 59 shares. Proof: p \mid m, so c \equiv m^e \equiv 0 \pmod{p}. And q \nmid m (else n \mid m and \gcd(m, n) = n), so by Euclid’s lemma q \nmid m^e, hence c \not\equiv 0 \pmod{q}. The divisors of n are 1, p, q, n; p divides c and q does not, so \gcd(c, n) = p.
One of p, q is odd, so one factor of (p-1)(q-1) is even and \varphi(n) is even; \gcd(e, \varphi(n)) = 1 forces e odd. Then 0^e = 0, 1^e = 1, and (n - 1)^e \equiv (-1)^e = -1 \equiv n - 1.
Write ed = 1 + kL, k \ge 0. As (p - 1) \mid L, m^{ed} = m \cdot (m^{p-1})^{kL/(p-1)} \equiv m \pmod{p} when p \nmid m, and trivially when p \mid m. The same modulo q, and the coprime factor lemma finishes as before.
By Theorem 2, unlocking undoes locking, so two messages with the same ciphertext are equal: locking is one-to-one. A one-to-one map of a finite set to itself is onto (One-to-one, onto and bijective functions), so it is a bijection, with unlocking as its inverse.
p + q = 5183 - 5040 + 1 = 144; 144^2 - 4 \cdot 5183 = 20{,}736 - 20{,}732 = 4, so x = (144 \pm 2)/2: p, q = 71, 73.
40^2 = 1600 < 1679 < 41^2. Remainders on division by 2, 3, 5, 7, 11, 13, 17, 19 are 1, 2, 4, 6, 7, 2, 13, 7, and 1679 = 23 \cdot 73. \varphi = 22 \cdot 72 = 1584; 1584 = 316 \cdot 5 + 4 gives 1 = 317 \cdot 5 - 1584, so d = 317.
ed - 1 = 3680 and k \in \{1, 2\}. k = 1 gives 3680 > n, impossible as \varphi(n) < n. k = 2 gives \varphi(n) = 1840, p + q = 1927 - 1840 + 1 = 88, discriminant 7744 - 7708 = 36, so p, q = 41, 47.
3901 = 2773 + 1128, 2773 = 2 \cdot 1128 + 517, 1128 = 2 \cdot 517 + 94, 517 = 5 \cdot 94 + 47, 94 = 2 \cdot 47. So \gcd = 47 and 3901 = 47 \cdot 83.
2668 is not a multiple of 3 (digit sum 22), so e = 3 is allowed. 2197 = 13^3 < 2773, so if m^3 < 2773 then c = m^3 exactly; m = 13, and only m = 13 locks to 2197 (Exercise 11).
Squares of 625 modulo 943: 625, 223, 693. With 7 = 4 + 2 + 1, 625 \cdot 223 = 139{,}375 \equiv 754 and 754 \cdot 693 = 522{,}522 = 554 \cdot 943 + 100. So s^7 \bmod 943 = 100: valid.
\log_{10} 2^{2047} \approx 616.2 and \log_{10} 2^{2048} \approx 616.5, so 10^{616} < 2^{2047} \le n < 2^{2048} < 10^{617}, which is exactly 617 digits.
They choose s' and get whatever m' falls out, which is a meaningless number. To sign a chosen m they need s with s^e \equiv m, an eth root modulo n; that is unlocking m, and no way to do it without d or the factors of n is known.
Locking uses only the public key and gives the same c every time. They lock OK and NO themselves; NO gives 884 (Exercise 5), so the message was NO.
ed - 1 > 0 because e, d > 1, so k \ge 1. And d < \varphi(n) gives k\,\varphi(n) = ed - 1 < e\,\varphi(n), so k < e.