Back to the on-screen lesson ·
How a key pair is built out of Euler's theorem, what a primality test settles and what it does not, and why two strangers can agree on a number over an open line.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to build a key pair from two primes and a public exponent, prove that raising to the public exponent and then to the private one returns the original residue, say what a failed and a passed primality test each establish, explain why a Carmichael number defeats the Fermat test and how Miller-Rabin answers that, and compute a shared secret from a key exchange.
Euler's theorem says $a^{\varphi(n)} \equiv 1$ for a unit $a$, so exponents reduce modulo $\varphi(n)$. The extended Euclidean algorithm inverts anything coprime to a modulus, quickly. Square-and-multiply raises to a huge exponent cheaply. The Chinese remainder theorem splits a composite modulus into its prime parts.
Each has been used for its own sake. Assembled, they give a system in which one person can publish a rule for computing something and keep the rule for undoing it — and the whole of this lesson is that assembly, done with numbers small enough to check by hand.
A key pair for RSA is a modulus $n = pq$ with $p, q$ distinct primes, a public exponent $e$ coprime to $\varphi(n)$, and a private exponent $d$ with $ed \equiv 1 \pmod{\varphi(n)}$. The pair $(n, e)$ is published; $d$, $p$, $q$ and $\varphi(n)$ are kept.
A witness to the compositeness of $n$ is a base for which a primality test fails, proving $n$ composite without producing a factor.
The discrete logarithm problem is: given a prime $p$, a base $g$ and a value $y \equiv g^{x} \pmod p$, find $x$. Exponentiating is cheap; going back is not known to be.
Key generation. Pick distinct primes $p$ and $q$; set $n = pq$ and $\varphi(n) = (p-1)(q-1)$. Pick $e$ with $\gcd(e, \varphi(n)) = 1$; compute $d = e^{-1} \bmod \varphi(n)$ by the extended algorithm. Publish $(n, e)$; keep $d$, and discard $p$ and $q$ or guard them.
Why it inverts. Encryption sends $m \mapsto m^{e} \bmod n$; the private step sends $c \mapsto c^{d} \bmod n$. Since $ed = 1 + k\varphi(n)$, $$m^{ed} = m \cdot \left(m^{\varphi(n)}\right)^{k} \equiv m \pmod n$$ for any $m$ coprime to $n$ — and for the remaining $m$ too, by working modulo $p$ and modulo $q$ separately and recombining with the Chinese remainder theorem.
Finding the primes. Test random odd numbers of the right size until one passes. The Fermat test computes $a^{n-1} \bmod n$: if it is not $1$, $n$ is composite, proved — with no factor found. If it is $1$, nothing is proved: $341 = 11 \cdot 31$ passes for base $2$, and Carmichael numbers such as $561$ pass for every coprime base.
Miller–Rabin repairs this using a second fact: modulo a prime, the only square roots of $1$ are $\pm 1$. Write $n - 1 = 2^{s}d$ with $d$ odd and examine $a^{d}, a^{2d}, a^{4d}, \ldots$; a composite fails for at least three quarters of the bases, so $k$ random rounds leave a chance of at most $4^{-k}$ of a wrong report. It bounds the error; it does not eliminate it.
Key exchange. Diffie–Hellman is a different problem with the same arithmetic. Two parties agree publicly on a prime $p$ and a base $g$; one picks $a$ and sends $g^{a}$, the other picks $b$ and sends $g^{b}$; each raises what they received to their own exponent and both hold $g^{ab}$. Nothing secret was transmitted.
Where the assumption is. Recovering $d$ from $(n, e)$ would follow from factorising $n$; recovering $a$ from $g^{a}$ is the discrete logarithm. Neither is known to be feasible at the sizes used, and neither is known to be infeasible. That is an assumption, and it is where it sits.
Another way: steps
Another way: example
$p = 5$, $q = 11$: $n = 55$, $\varphi(n) = 40$. Take $e = 3$, which is coprime to $40$; then $d = 27$, since $3 \cdot 27 = 81 = 2 \cdot 40 + 1$. Encrypt $m = 2$: $2^{3} = 8$. Recover: $8^{27} \bmod 55$, which by reducing the exponent modulo $40$ stays $8^{27}$, and by square-and-multiply comes to $2$.
This lesson teaches the arithmetic. It is worth being exact about how much of a working system that arithmetic is, because the gap is large and is where real failures happen.
What is established. The map $m \mapsto m^{e} \bmod n$ is a bijection on the residues modulo $n$, and $m \mapsto m^{d}$ inverts it. That is a theorem, proved above, with no assumptions in it.
What is assumed. That recovering $d$ from $(n, e)$ is infeasible at the sizes used. No proof of this exists. It would follow from factorising $n$, and no published method factorises a two-thousand-bit semiprime — but no published method is a statement about the literature, not about mathematics. If an efficient factoring algorithm were found, or a sufficiently large quantum computer built (Shor's algorithm factors in polynomial time), the assumption would fail.
What is not addressed at all. Textbook RSA as described is not a usable encryption scheme, and the reasons are not about the number theory.
Real systems address these with padding schemes (OAEP), and the padding is not decoration — it is load-bearing, and implementations that omitted it have been broken.
And the arithmetic is not where systems usually fail. Keys are recovered through timing differences in the exponentiation, through weak sources of randomness producing primes that repeat across devices, through reused parameters, and through people. The number theory in this lesson is the part that is understood; it is the surrounding engineering that decides whether a deployment holds.
Inverting the public exponent modulo the wrong number. $d$ is $e^{-1}$ modulo $\varphi(n)$, never modulo $n$. Exponents live modulo the totient.
Thinking the primes may be kept for later use. They are the most sensitive quantity in the scheme: from them the totient follows in one multiplication and $d$ in one run of Euclid. Anything from which $d$ can be rebuilt is as private as $d$.
Reading a passed primality test as a proof. Miller–Rabin reports a bound on the chance of error. Repeating it lowers that bound and never reaches zero. A number used as an RSA prime is a probable prime, and that is the accepted standard.
Expecting a test to produce a factor. None of these does. Knowing $n$ composite and factorising $n$ are different problems, and the whole scheme depends on the difference.
Treating the discrete logarithm as the same problem as factoring. They are different problems with different algorithms; neither is known to reduce to the other. A break in one would not automatically break the other.
$p = 7$, $q = 11$, so $n = 77$ and $\varphi(n) = 6 \cdot 10 = 60$.
The totient needs both primes, and nothing else does.
Choose $e = 7$: $\gcd(7, 60) = 1$, so it has an inverse. The extended algorithm gives $d = 43$, since $7 \cdot 43 = 301 = 5 \cdot 60 + 1$.
One run of Euclid on the exponent and the totient.
Check the round trip on $m = 5$: $5^{7} \bmod 77 = 47$, and $47^{43} \bmod 77 = 5$. The exponent $43$ is handled by square-and-multiply, not by computing $47^{43}$.
The bijection, verified on one value.
Is $561$ prime? Fermat with base $2$: $2^{560} \equiv 1 \pmod{561}$, so the test passes and nothing is learned. $561$ is in fact the smallest Carmichael number, and every coprime base passes.
The case the Fermat test cannot handle.
Miller–Rabin with base $2$: $560 = 2^{4} \cdot 35$. Compute $2^{35} \bmod 561 = 263$; squaring gives $166$, then $67$, then $1$ — and the step before that $1$ was $67$, which is neither $1$ nor $560$.
A square root of $1$ that is not $\pm 1$.
Modulo a prime that is impossible, so $561$ is composite — proved, and with no factor of $561$ produced by the argument.
Compositeness established without a factorisation.
$n = 33$ and $\varphi(n) = 2 \cdot 10 = 20$.
The totient from the two primes.
$\gcd(3, 20) = 1$, so an inverse exists; $3 \cdot 7 = 21 = 20 + 1$, so $d = 7$.
Inverted modulo the totient, not the modulus.
Check on $m = 2$: $2^{3} = 8$, and $8^{7} = 2097152 = 63550 \cdot 33 + 2$, so the round trip returns $2$.
Put the steps of building a key pair into the order they are carried out. In this example the primes are $5$ and $13$.
Number the steps in order (write the number in the box):
A key pair uses the primes $7$ and $11$ and the public exponent $7$. What is the private exponent? Give the least positive value.
Answer:
From the primes $5$ and $11$ and the public exponent $3$, give the modulus, the totient and the private exponent.
| Value | |
|---|---|
| Modulus | |
| Totient of the modulus | |
| Private exponent |
Is this true: Wilson's theorem gives a practical primality test?
For the key pair with modulus $33$ and public exponent $3$, match each quantity to whether it is published or kept.
| published | kept private | |
|---|---|---|
| the modulus $33$ | ||
| the public exponent $3$ | ||
| the two primes $3$ and $11$ | ||
| the private exponent $7$ |
Two people agree publicly on the prime $19$ and the base $2$. One sends $16$ and the other sends $7$. Your private exponent is $6$, and $16$ is what the other person sent you. What shared secret do you compute?
shared secret a
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Put the steps of building a key pair into the order they are carried out. In this example the primes are $3$ and $17$.
Number the steps in order (write the number in the box):
You can build and check a key pair, and you can say which of its numbers are published and why the rest are not. Say in your own words what a passed primality test establishes and what it does not. Next: which residues generate all the others by taking powers.
9. Your turn: with $p = 3$, $q = 11$ and $e = 3$, find the private exponent, step 3