RSA

RSA key generation, encryption and decryption, worked in full for both of the lecture's own examples, and why the scheme is fast to use but hard to break.

Generate an RSA key pair by hand: choose p and q, compute n and phi(n), pick e, and derive d.
Encrypt and decrypt a message with RSA, reproducing every intermediate value.
Explain why computing C = M^e mod n is fast while recovering M without d is believed infeasible.
State the message-size constraint M < n and what happens if it is violated.

22 min read

Intuition

The previous page defined a trapdoor one-way function in the abstract. RSA is the concrete instance built from the RSA problem: multiply two primes to get a modulus $n$ , and factoring $n$ back into those primes is believed infeasible once they are large enough. Everything below is one algorithm, worked twice, with every intermediate value shown so you can check your own working against it.

Mechanism

Key generation. Four steps, in order:

Choose two distinct primes $p$ and $q$ . In practice these are very large; the examples below use small ones so the arithmetic stays checkable by hand.
Compute the modulus $n = pq$ .
Compute $\varphi(n) = (p-1)(q-1)$ — Euler’s totient of $n$ , using the shortcut that applies when $n$ is a product of two distinct primes (see primes, Fermat, Euler and fast exponentiation for the general definition).
Choose a public exponent $e$ with $1 < e < \varphi(n)$ and $\gcd(e, \varphi(n)) = 1$ , then compute the private exponent $d$ as the modular inverse of $e$ modulo $\varphi(n)$ : $d \equiv e^{-1} \pmod{\varphi(n)}$ . The method is the extended Euclidean algorithm — see extended Euclid and modular inverses.

The public key is $PU = \{e, n\}$ ; the private key is $PR = \{d, n\}$ . $p$ , $q$ and $\varphi(n)$ can be discarded once $d$ is computed — they are never needed again, and keeping them around only gives an attacker more to steal.

Encryption, by anyone holding the public key: $C = M^e \bmod n$ , where the plaintext satisfies $M < n$ .

Decryption, only by the holder of the private key: $M = C^d \bmod n$ .

RSA is a function from $\mathbb{Z}/n\mathbb{Z}$ to $\mathbb{Z}/n\mathbb{Z}$ , and that choice is deliberate. Exponentiation in $\mathbb{Z}/n\mathbb{Z}$ is fast — repeated squaring computes $M^e \bmod n$ in about $\log_2 e$ multiplications, never $e$ of them — so encryption and decryption are both cheap once you know the exponent you are raising to. Recovering $M$ from $C$ without knowing $d$ means finding an $e$ -th root modulo $n$ instead: the RSA problem, believed infeasible for large enough $n$ . The entire scheme rests on that gap between “fast if you know the exponent” and “hard if you don’t.”

The public key {e, n} and private key{d, n} both use the same modulus n, butd depends on φ(n), which depends on the two prime factors of n — recovering d from the public key alone means factoring n, believed infeasible for large enough primes. Anyone with the public key can encrypt; only the holder of d can decrypt. Numbers throughout are the lecture's own worked example, not illustrative round figures.

Worked example

Answerp=17, q=11, e=7 gives n=187, phi(n)=160, d=23. M=88 encrypts to C=11 and decrypts back to 88.

This is the lecture’s main worked example.

Choose $p = 17$ , $q = 11$ .
$n = pq = 17 \times 11 = 187$ .
$\varphi(n) = (p-1)(q-1) = 16 \times 10 = 160$ .
Choose $e = 7$ . Check $\gcd(7, 160) = 1$ — 7 is prime and does not divide 160, so this holds.
Find $d \equiv 7^{-1} \pmod{160}$ by the extended Euclidean algorithm on $160$ and $7$ :
$160 = 22 \times 7 + 6$
$7 = 1 \times 6 + 1$
$6 = 6 \times 1 + 0$ — remainder 0, so $\gcd(160, 7) = 1$ , the last non-zero remainder.
Back-substitute to write $1$ as a combination of $160$ and $7$ :
$1 = 7 - 1 \times 6$
substitute $6 = 160 - 22 \times 7$ :
$1 = 7 - 1 \times (160 - 22 \times 7) = 23 \times 7 - 1 \times 160$
So $23 \times 7 \equiv 1 \pmod{160}$ , which the lecture confirms directly: $23 \times 7 = 161 = (1 \times 160) + 1$ . Since $0 \le 23 < 160$ , $d = 23$ .
$PU = \{7, 187\}$ , $PR = \{23, 187\}$ .
Encrypt $M = 88$ : compute $C = 88^7 \bmod 187$ by repeated squaring.
$88^1 \bmod 187 = 88$
$88^2 \bmod 187 = 7744 \bmod 187 = 77$
$88^4 \bmod 187 = 77^2 \bmod 187 = 5929 \bmod 187 = 132$
$7 = 4 + 2 + 1$ , so $88^7 = 88^4 \times 88^2 \times 88^1 \bmod 187$ : $132 \times 77 \bmod 187 = 10164 \bmod 187 = 66$ , then $66 \times 88 \bmod 187 = 5808 \bmod 187 = 11$ .
$C = 11$ .
Decrypt $C = 11$ : compute $M = 11^{23} \bmod 187$ by repeated squaring.
$11^1 = 11$ , $11^2 = 121$ , $11^4 = 121^2 \bmod 187 = 14641 \bmod 187 = 55$ , $11^8 = 55^2 \bmod 187 = 3025 \bmod 187 = 33$ , $11^{16} = 33^2 \bmod 187 = 1089 \bmod 187 = 154$ .
$23 = 16 + 4 + 2 + 1$ , so $11^{23} = 11^{16} \times 11^4 \times 11^2 \times 11^1 \bmod 187$ : $154 \times 55 \bmod 187 = 55$ , then $55 \times 121 \bmod 187 = 110$ , then $110 \times 11 \bmod 187 = 1210 \bmod 187 = 88$ .
$M = 88$ — recovered exactly.

Worked example

Answerp=7, q=11, e=13 gives n=77, phi(n)=60, d=37. M=3 encrypts to C=38 and decrypts back to 3.

This is the lecture’s toy example, from the slides.

Choose $p = 7$ , $q = 11$ .
$n = pq = 7 \times 11 = 77$ .
$\varphi(n) = (p-1)(q-1) = 6 \times 10 = 60$ .
Choose $e = 13$ . It is less than 60 and coprime to it.
Find $d \equiv 13^{-1} \pmod{60}$ by the extended Euclidean algorithm on $60$ and $13$ :
$60 = 4 \times 13 + 8$
$13 = 1 \times 8 + 5$
$8 = 1 \times 5 + 3$
$5 = 1 \times 3 + 2$
$3 = 1 \times 2 + 1$
$2 = 2 \times 1 + 0$ — remainder 0, so $\gcd(60, 13) = 1$ .
Back-substitute from the bottom up:
$1 = 3 - 1 \times 2$
$2 = 5 - 1 \times 3 \implies 1 = 2 \times 3 - 1 \times 5$
$3 = 8 - 1 \times 5 \implies 1 = 2 \times 8 - 3 \times 5$
$5 = 13 - 1 \times 8 \implies 1 = 5 \times 8 - 3 \times 13$
$8 = 60 - 4 \times 13 \implies 1 = 5 \times 60 - 23 \times 13$
So $-23 \times 13 \equiv 1 \pmod{60}$ , and the least non-negative residue of $-23$ modulo $60$ is $60 - 23 = 37$ . $d = 37$ , matching the lecture’s stated value directly.
$PU = \{13, 77\}$ , $PR = \{37, 77\}$ .
Encrypt $M = 3$ : compute $C = 3^{13} \bmod 77$ .
$3^1 = 3$ , $3^2 = 9$ , $3^4 = 81 \bmod 77 = 4$ , $3^8 = 4^2 = 16$ .
$13 = 8 + 4 + 1$ , so $3^{13} = 3^8 \times 3^4 \times 3^1 \bmod 77 = 16 \times 4 \times 3 = 192$ , and $192 \bmod 77 = 38$ .
$C = 38$ .
Decrypt $C = 38$ : compute $M = 38^{37} \bmod 77$ .
$38^1 = 38$ , $38^2 = 1444 \bmod 77 = 58$ , $38^4 = 58^2 \bmod 77 = 3364 \bmod 77 = 53$ , $38^8 = 53^2 \bmod 77 = 2809 \bmod 77 = 37$ , $38^{16} = 37^2 \bmod 77 = 1369 \bmod 77 = 60$ , $38^{32} = 60^2 \bmod 77 = 3600 \bmod 77 = 58$ .
$37 = 32 + 4 + 1$ , so $38^{37} = 38^{32} \times 38^4 \times 38^1 \bmod 77$ : $58 \times 53 \bmod 77 = 71$ , then $71 \times 38 \bmod 77 = 2698 \bmod 77 = 3$ .
$M = 3$ — recovered exactly.

Pick two small primes and a public exponent, derive the key, then encrypt and decrypt a message with it.

How d was derived (extended Euclid of e and φ(n))

i	q	r	s	t

Message m

Exam detail

Non-numerical messages have to be mapped to numbers before RSA can touch them — the algorithm only encrypts integers in $\mathbb{Z}/n\mathbb{Z}$ . A common convention maps letters to numbers ( $a \to 1$ , $b \to 2, \dots$ ), but any fixed, invertible mapping works; the lecture does not test a specific one.

Pitfall

$d$ is the modular inverse of $e$ modulo $\varphi(n)$ , not modulo $n$ . It is easy to mix these up because both moduli appear on the same page — $\varphi(n)$ only exists during key generation and is never used again once $d$ is derived, while $n$ appears in both the public and private key and is used in every encryption and decryption.

Recall

For p=7, q=11, phi(n)=60. Why must e=13 be checked against phi(n), and not against n=77?

Because $d$ is defined as the inverse of $e$ modulo $\varphi(n)$ , not modulo $n$ — a modular inverse only exists when $\gcd(e, \varphi(n)) = 1$ . Checking $e$ against $n$ instead would test the wrong condition entirely; a modulus of $\varphi(n) = 60$ is what matters here, not $n = 77$ .

Source

Week 5 notes PDF