## Reading

These notes and
closely review

Unit 3
Section 6.

## Quiz questions

## Encryption review

Talked about Alice and Bob.

## RSA - encryption & decryption

If $M$ is the message, RSA encryption and decryption are:
\[
\text{encrypt}(M) = M^e \text{mod } n = M'
\text{ and decrypt}(M') = M'^d \text{mod } n = M
\]
Here, the public key is $(e,n)$ and the private key is $(d,n)$.
## RSA - Fermat's little theorem

Fermat's little theorem is covered in the notes.
To show that $\phi(pq) = (p-1)(q-1)$ we wrote out the elements
of $Z_{35}$ (i.e. $p = 5$, $q = 7$) and put an X under each
number that has no multiplicitive inverse mod 35.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
X X X X X X X X X X X

So, here's the pattern: the $q-1$ multiples of $p$ have X's, as
do the $p-1$ multiples of $q$, and of course zero. So, out of the
$pq$ elements of $Z_{35}$, $(q - 1) + (p-1) + 1$ of them are
X'd out, leaving
\[
pq - (q-1) - (p-1) - 1 = (p-1)(q-1)
\]
left over as having inverses.

## RSA- here's where the magic happens

We want $(M^e)^d = M \mod n$. So
\[
\begin{array}{r}
(M^e)^d = M \mod n\\
M^{ed} = M \mod n\\
M^{c(p-1)(q-1) + r} = M \mod n\\
\left(M^{(p-1)(q-1)}\right)^c \cdot M^r = M \mod n\\
1^c \cdot M^r = M \mod n
\end{array}
\]
... and we end up with this: if $r=1$, decryption works! So we
need $ed = c(p-1)(q-1) + 1$, which means $d = e^{-1} \mod n$.
So now we know how to generate keys!
## RSA- how to generate keys

Assume that your "messages" are $k$-bit numbers.

- generate two distinct random $\lfloor k/1 \rfloor + 1$ bit prime
numbers, call them $p$ and $q$, and set $n = pq$
- choose $e$ in $Z_n$ (and not super small) such that
$\text{gcd}(e,n) = 1$
- compute $d = e^{-1} \mod (p-1)(q-1)$

**public key:** $(e,n)$

**private key:** $(d,n)$