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.

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