\newlec

\ic{ I like to introduce Exponentiation Ciphers first and then tackle RSA - this way students can see the build up and see why one prime is an insecure procedure whereas two primes gives a secure procedure.}

\textbf{Exponentiation Cipher}

We begin describing RSA by first explaining exponentiation ciphers. Suppose Alice and Bob want to share a message but there is an eavesdropper (Eve) watching their communications. 
\ic{Include picture while lecturing.}
In an exponentiation cipher, Alice chooses a (large) prime $p$ and an $e$ satisfying
\[
1 < e < (p-1) \quad\quad \text{ and } \quad\quad \text{gcd}(e,p-1) = 1.
\]
Alice then makes the pair $(e,p)$ public and computes her private key $d$ satisfying
\[
1 < d < (p-1) \quad\quad \text{ and } \quad\quad ed \equiv 1 \mod{p-1}
\]
which can be done quickly using the Euclidean Algorithm (the inverse condition above is why we required that $\text{gcd}(e,p-1)$).
\vskip1em
To send a message $M$ to Alice, an integer between 0 and $p-1$ inclusive, Bob computes a ciphertext (encrypted message) $C$ satisfying
\[
0 \leq C < p \quad\quad \text{ and } \quad\quad C \equiv M^{e} \mod{p}.
\]
Bob then sends $C$ to Alice.
\vskip1em
Alice then computes $R \equiv C^{d} \mod{p}$ with $0 \leq R < p$.
	 \begin{center}
	\includegraphics[scale=0.33]{RSA2.png}
	\end{center}
\ic{Include picture - this is the 10 minute mark}
\newpage
\prop $R \equiv M \mod{p}$.
\vskip1em
\textbf{Proof:} If $p \mid M$, then all of $M$, $C$ and $R$ are $0$ and the claim follows. So we assume that $p \nmid M$. Recall that $ed \equiv 1 \mod{p-1}$ and so we have that there exists an integer $k$ such that $ed = 1 + k(p-1)$. Using this, we have
\begin{align*}
R &\equiv C^{d} \mod{p} \\
&\equiv (M^{e})^{d} \mod{p}  && \text{by definition of $C$}\\
&\equiv M^{ed} \mod{p}  \\
&\equiv M \mod{p} && \text{Corollary to F$\ell$T since $ed \equiv 1 \mod{p-1}$.}
\end{align*}
as required \qed
\vskip1em
\cor $R=M$
\vskip1em
\pf
By the previous proposition, $R \equiv M \mod{p}$. Recall that $0 \leq M, R < p$ and so the values must be equal. \qed
\ic{This is the 20 minute mark.}
The good news is that this scheme works. However, Eve can compute $d$ just as easily as Alice! Eve knows $p$, hence knows $p-1$ and can use the Euclidean algorithm to compute $d$ just like Alice. This means our scheme is not secure. To rectify this problem, we include information about two primes.
\vskip1em 
\textbf{RSA}
Alice chooses two (large) distinct primes $p$ and $q$, computes $n = pq$ and selects any $e$ satisfying
\[
1 < e < (p-1)(q-1) \quad\quad \text{ and } \quad\quad \text{gcd}(e,(p-1)(q-1)) = 1
\]
Alice then makes the pair $(e,n)$ public and compute her private key $d$ satisfying
\[
1 < d < (p-1)(q-1) \quad\quad \text{ and } \quad\quad ed \equiv 1 \mod{(p-1)(q-1)}
\]
again which can be done quickly using the Euclidean Algorithm (Alice knows $p$ and $q$ and hence knows $(p-1)(q-1)$).
\ic{Note that in the textbook $(d,n)$ is the private key pair.}
To send a message $M$ to Alice, an integer between 0 and $n-1$ inclusive, Bob computes a ciphertext $C$ satisfying
\[
0 \leq C < pq \quad\quad \text{ and } \quad\quad C \equiv M^{e} \mod{pq}.
\]
Bob then sends $C$ to Alice. Alice then computes $R \equiv C^{d} \mod{pq}$ with $0 \leq R < pq$. 
	 \begin{center}
	\includegraphics[scale=0.33]{RSA3.png}
	\end{center}
\ic{Include a diagram of what's happening. This is the 30 minute mark.}
\newpage
\prop $R = M$.
\vskip1em
\pf Since $ed \equiv 1 \mod{(p-1)(q-1)}$, transitivity of divisibility tells us that 
$$ed \equiv 1 \mod{p-1} \quad\quad \text{and} \quad\quad ed \equiv 1 \mod{q-1}.$$
 Since $\gcd(e,(p-1)(q-1)) = 1$, GCD Prime Factorization (or by definition) tells us that $\gcd(e,p-1) = 1$ and that  $\gcd(e,q-1)=1$. Next, as $C \equiv M^{e} \mod{pq}$, Splitting the Modulus states that
\[
C \equiv M^{e} \mod{p} \quad\quad \text{ and } \quad\quad C \equiv M^{e} \mod{q}
\]
Similarly, by Splitting the Modulus, we have
\[
R \equiv C^{d} \mod{p} \quad\quad \text{ and } \quad\quad R \equiv C^{d}\mod{q}.
\]
By the previous proposition applied twice, we have that
\[
R \equiv M \mod{p} \quad\quad \text{ and } \quad\quad R \equiv M \mod{q}.
\]
Now, an application of the Chinese Remainder Theorem (or Splitting the Modulus), valid since $p$ and $q$ are distinct, gives us that $R \equiv M \mod{pq}$. Recalling that $0 \leq R,M < pq$, we see that $R=M$. \qed
\vskip1em
Is this scheme more secure? Can Eve compute $d$? If Eve can compute $(p-1)(q-1)$ then Eve could break RSA. To compute this value given only $n$ (which recall is $pq$), Eve would need to factor $n$ (or compute $p+q$). Factoring $n$ is a notoriously hard problem and we know of no quick way of doing so. Eve could also break RSA if she could solve the problem of computing $M$ given $M^{e} \mod{n}$. 
\vskip1em
\note Let $\phi$ be the Euler Phi Function. This function has the valuation $\phi(n) = (p-1)(q-1)$ when $n = pq$ a product of distinct primes.
\ic{This is the 40 minute mark}
\newpage

\hdc

Let $p=2$, $q=11$ and $e=3$
\begin{enumerate}
\item Compute $n$, $\phi(n)$ and $d$.
\item Compute $C \equiv M^{e} \mod{n}$ when $M=8$ (reduce to least nonnegative $C$).
\item Compute $R\equiv C^{d} \mod{n}$ when $C=6$ (reduce to least nonnegative $R$).
\end{enumerate}
\vskip3em
\soln
\begin{enumerate}
\item Note $n=22$, $\phi(n) = (2-1)(11-1) = 10$ and lastly, $3d \equiv 1 \mod{10}$ and multiplying by $7$ gives $d \equiv 7 \mod{10}$. Hence $d=7$.
\item Note that
\begin{align*}
C &\equiv M^{e} \mod{22} \\
&\equiv 8^{3} \mod{22} \\
&\equiv 8\cdot 64 \mod{22} \\
&\equiv 8\cdot (-2) \mod{22} \\
&\equiv -16 \mod{22} \\
&\equiv 6 \mod{22} \\
\end{align*}
\item The quick way to solve this is to recall the RSA theorem and hence $M = 8$. The long way is to do the following:
\begin{align*}
R &\equiv C^{d} \mod{22} \\
&\equiv 6^{7} \mod{22} \\
&\equiv 6\cdot(6^{3})^{2} \mod{22} \\
&\equiv 6\cdot (216)^{2} \mod{22} \\
&\equiv 6 \cdot (-4)^{2}\mod{22} \\
&\equiv 6 \cdot 16 \mod{22} \\
&\equiv 6 \cdot (-6) \mod{22} \\
&\equiv -36 \mod{22} \\
&\equiv 8 \mod{22} 
\end{align*}
\end{enumerate}





%Say Alice chooses $p=17$, $q=5$ and $e=3$ which is coprime to $(p-1)(q-1) = 16\cdot 4 = 64$. Alice then sends the pair $(e,n) = (3,85)$ to Bob and computes the private key $d$ satisfying
%\[
%3d \equiv 1 \mod{64}.
%\] 
%We can now use the Euclidean algorithm or a bit of cleverness. Since $3 \cdot 21 = 63$, we have that 
%\[
%63d \equiv 21 \mod{64} \quad \Rightarrow \quad -d \equiv 21 \mod{64} \quad \Rightarrow \quad  d \equiv -21 \mod{64}
%\] 
%giving that $d = -21 + 64 = 43$
%\vskip1em
%Say Bob wishes to send the message $M = 11$. To do so he computes
%\[
%M^{e} \equiv 11^{3} \equiv 1331 \equiv 56 \mod{85}
%\]
%and sends $C = 56$ to Alice. Alice then computes 
%\[
%C^{d} \equiv 56^{43} \equiv 11 \mod{85}
%\]
%which is the original message.

\newpage

Food for thought: 

\begin{enumerate}
\item How does Alice choose primes $p$ and $q$? (Answer: Randomly choose odd numbers! If $p$ and $q$ are 100 digit primes, then choosing 100 gives you more than a 50\% chance that you have a prime - can check using primality tests).
\item What if Eve wasn't just a passive eavesdropper? What if Eve could change the public key information before it reaches Bob? (This involves using certificates).
\item What are some advantages of RSA? (Believed to be secure, uses the same hardware for encryption and decryption, computations can be done quickly using a square and multiply algorithm).
\end{enumerate}
