## Public Key Encryption

24feb12 revised 8mar16 typos 12feb18

\begin{document} \maketitle \section{Introduction} Here we continue and conclude our lesson on modular arithmetic, culminating in a proof of the RSA public key encryption algorithm. We also take the opportunity to review the mathematics you learned in the past two weeks. But because rote repetition is boring, each of the three chief topics are reviewed by considering a different proof, sharpening the result, and finding an extension of the theorem respectively. Sections 2 and 3 are elaborations not strictly necessary to understand how the RSA public key encryption works. Section 2 takes another look at the Prime Factorization Theorem, and how it was well known before the rigorous proof by strong induction we studied was developed. Section 3 deals with a more explicit algorithm, suitable for a computer, to solve this the Diophantine equations, $ex - my=1$, given $1 < e < m $ and $gcd(e,m)=1$ , so that $1 < x < m$ and $y > 1 $. From what we have learned from the form of all solutions to a Diophantine equation we can deduce that such a solution can always be found. But, one wants more than an existence proof when dealing with a computer. However, once we accept this and Fermat's Little Theorem (FLT) treated in the previous lesson (which we quote using the current notation for the convenience of the reader) we can tackle the RSA concept directly. For this purpose, you can skip directly to Section 4. \section{Prime Factorization and the Sieve of Eratosthenes} The Greeks certainly know the prime decomposition theorem but they did not know (or care about about) the principle of strong induction. They used this argument dure to Eratosthenes of Cyrene, 276-195 BC. He was a mathematician, poet, athlete, geographer, astronomer and music theorist. He measured the circumference of the earth, the tilt of the earth's axis, the distance to the sun, and he invented the leapyear. Note that no educated person (until the Dark Ages) ever doubted that the earth was a sphere! Eratosthenes also enumerated the primes in the following ingenious way. His \textit{ Sieve} may be remembered by this ditty from Pohl and Kornbluth's \textit{ Drunkard's Walk} \begin{quote} Strike the twos, and strike the threes; The Sieve of Eratosthenes. And when the multiples sublime, The numbers that are left are prime. \end{quote} The word "sublime" is used here to mean "evaporate" or go away. The concept is this. Imagine all numbers in a row, $ 2,3,4,.....$. We start with the prime $2$ because $1$ is neither a prime nor a composite. Now "strike" every multiple of two. We shall also remember that it is a multiple of two, maybe by writing a $2$ under it. For typographical reasons, I won't strike the composites but overline them, I will boldface the primes already found. \begin{itemize} \item $ \mathbf{2}, 3, \bar{4}_2, 5, \bar{6}_2, 7, \bar{8}_2, 9, \bar{10}_2, 11, \bar{12}_2, ... $ \item $ \mathbf{2}, \mathbf{3}, \bar{4}_2, 5, \bar{6}_{23}, 7, \bar{8}_2, 9_3, \bar{10}_2, 11, \bar{12}_{23} ... $ \item $ \mathbf{2}, \mathbf{3}, \bar{4}_2, \mathbf{5}, \bar{6}_{23}, 7, \bar{8}_2, 9_3, \bar{10}_{25}, 11, \bar{12}_{23} ... $ \item $ \mathbf{2}, \mathbf{3}, \bar{4}_2, \mathbf{5}, \bar{6}_{23}, \mathbf{7}, \bar{8}_2, 9_3, \bar{10}_{25}, 11, \bar{12}_{23} ... $ \item ... \end{itemize} As you see, the \textit{ next prime} is always the first number not yet struck out. Also, by remembering the prime that struck, we get the prime factors. But we don't get the repeats. I suppose we could ammend the Sieve by insisting on finding how many time $2|4$, and $2|8$ etc. So the Sieve not only finds the primes but also the prime decomposition of the composite numbers. \section{Euclid's Algorithm and back substitution} This time we specify that $a > b > 1$ before we apply long division. \subsection{Reduction to solving ax-by=1 for coprime coefficients} Let start over by writing the Diophantine equation we want to solve as a difference. \begin{eqnarray*} ax - by &=& c \mbox{ where } (a,b)|c \mbox{ of course }\\ \frac{a}{d}x - \frac{b}{d}y &=& \frac{c}{d} \mbox{ where } d = (a,b)\\ a'x - b'y &=& c' \mbox{ where } (a,b)=1, \mbox{ this is solved by solving }\\ a'x' - b'y' &=& 1 \mbox{ and multiplying } x=cx', y= cy' \\ \end{eqnarray*} \subsection{Recursive long division with back substitution} \begin{eqnarray*} \mbox{For } a>b>1 & solve & ax - by = 1 \mbox{ for positive } x, y:\\ a= bq + r&\mbox{ substitute }& (bq+r)x - by = 1\\ &\mbox{ rearrange } & -b(y-qx) + rx = 1 \\ &\mbox{ relabel } & -bu + rv = 1 \\ &\mbox{ where } & u=y-qx \\ &\mbox{ and } & v =x \\ &\mbox{ so } & x = v \\ &\mbox{ and } & y = u + qv \\ \end{eqnarray*} Let's check that all the hypotheses are satisfied for $b,r$ replacing $a,b$. \begin{itemize} \item We have that $b > r$ like $ a > b$ \item Iff $r=1$ then Euclid's algorithm ends with $1=gcd(a,b)$. \item If $b > r > 1$ we are tempted to just "do it again", but.... \item We must also check the last hypothesis, that $(b,r)=1 \item $gcd(b,r)=gcd(b,a-bq) = gcd(b,a) = 1 $ proved earlier. \end{itemize} We have reduced the problem of solving the special Diophantine equation to a similar equation, but with both coefficients smaller than before: \begin{eqnarray*} \mbox{For } b>r>1 & solve & -bu + rv = 1 \mbox{ for positive } u, v:\\ \end{eqnarray*} There is an additional important observation. If $u,v$ are both positive then so are $x,y$. But note that the signs have changed from $+-$ to $-+$. They change back in the next step. So, depending whether there are an even number of steps or not, we may end up having solved $-ax_0 + by_0 = 1$ with positive solutions. Recall that, by another theorem we proved, all other soliutions have the form $ x_t=x_0 - tb, y_t=y_0 - ta.$ By successively subtracting $b$ from $x_0$ we reach a negative $x_t$, and so $ x = -x_t, y= -y_t $ solve the original problem with positive solutions.Questions 1: Why must $y_t$ also be negative as soon as $x_t$ is?\section{Fermat's Little Theorem generalized} Recall the FLT, which says that if $gcd(w,p)=1$ then $w^{p-1} \equiv_p 1$. We next generalize Fermat's Little Theorem by applying it with two different primes $p,q$ and $gcd(w,pq)=1$, so that neither $p$ nor $q$ divides $w$. Here is the line of reasoning that proves that $w^{(p-1)(q-1)}\equiv_{pq} 1 $. \begin{eqnarray*} w^{p-1}&\equiv_p& 1 \mbox{ applying FLT to } (w,p) \\ \therefore w^{(p-1)(q-1)}&\equiv_p& 1^{q-1} = 1 \\ \mbox{ But } (w^{p-1})^{q-1} &\equiv_q& 1 \mbox{ applying FLT to } (w^{p-1}, q) \\ \therefore p | (w^{(p-1)(q-1)}-1) & \mbox{ and }& q | (w^{(p-1)(q-1)}-1) \\ \mbox{ both being prime }& & pq | (w^{(p-1)(q-1)}-1) \\ \therefore w^{(p-1)(q-1)}&\equiv_{pq}1 \\ \end{eqnarray*} This is the same conclusion as FLT for a composite modulus $m=pq$ which has just two prime factors.Question 2: State a further generalization for the case that $w$ is relatively prime to a modulus $m$ whose prime decomposition has no repeated primes.\section{Application to the RSA encryption } In 1978, Ron Rivest, Adi Shamir, and Leonard Adleman of MIt published an ingenious method of encrypting messages sent over the internet. It is named \textit{ The RSA Public Key Encryption }. It works like this. Suppose you want to receive messages sent to you securely from whoever wishes to do so, so that no one but you can decipher them. Thus only you and your (possibly anonymous) correspondent knows what secrets she is sending you. Morever, everyone who wishes can read the encrypted message and not be able to do anything with it. Amazing, isn't it? Say you are collecting sensitive information from anyone willing to send some to you. As Snowden might have done if you worked for the newspapers. But you don't want the NSA, or the CIA, or anyone else to be able to decipher them, except you. And, you do this by publishing a \textit{ public key} consisting of three numbers $N,e,\ell$ where your correspondents (and any anybody else) can read them. \begin{itemize} \item $N$ is the product of the two largest primes you can afford to buy or generate: $N = pq$. \item The exponent $e$, which you have chosen to be relatively prime to $m = (p-1)(q-1)$ \item The bitlength $\ell$ of the words in the transmission, which you chose so that $2^\ell < \mbox{ both } p,q $. \end{itemize} Note that unless the third party can factor $N$ to find the $p,q$, they also cannot gain any useful information from the other two public numbers. For the exponent, you calculate a solution to this Diophantine equation \[ ed - mk = 1 \] with positive $d,k$. Note that $d,k$ and both $e,d < m$ are known only to you. You can forget $k$, but don't misplace $d$. Note that \[ d \equiv_m} e^{-1} \], the multiplicative inverse of $e$ modulo $m$.Question 3: How would you find such a $d$ ?\subsection{The encryption} To encode each word $w$ in stream of words, your correspondent's computer calculates \[s = w^e\%N \mbox{ i.e. the smallest } s \equiv_N w^e \mbox{ (encryption) }\], and sends you $s$, not $w$ which is supposed to be secret. This can safely be public because without more information, even the NSA supercomputers are powerless. Still, $s$ it encodes the secret $w$. Note, there are many potential solutions for $s$ because the same integer is congruent to many other integers for a given modulus $N$. But there is only one of them which is between $1 < s < N$. Why, and how would you find it? \subsection{The decryption} When you receive $s$, your computer calculates that \[ w = s^d \% N \mbox{ (decryption)} \], again choosing the only number congruent to $s^d$ between $1$ and $N$. Recall that s $s^d \equiv_N w$. But why should this be exactly $w$ and not something else congruent to it? (Duh, you want to know $w$ not some other number differing from it by a multiple of $N$.) \subsection{How does this work?} Recall that $e$ was choses relatively prime to $m=(p-1)(q-1)$. By the sharpened (computer friendly) version of Euclid's algorithm above, \begin{eqnarray*} s &\equiv_N& w^d \mbox{ as received }\\ \therefore s^d &\equiv_N& w^{ed} \\ &=& w^{ 1 + mk}\\ &=& w w^{mk}\\ &=& w (w^{(p-1)(q-1)})^k\\ &\equiv_{pq} &w (1)^k \mbox{ ..............by FLT++ }\\ &= &w \\ \therefore s^d &\equiv_N& w \\ \end{eqnarray*} Bingo. This whole procedure can be automated. Your correspondent writes a stream of ascii whose numerical equivalents are collected into a stream of numbers. Chopped into $\ell$ sized words $w$, her computer encrypts the $w$'s using your public key. She sends them to you, and your computer decrypts, knowing the secret powers to raise them to modulo $N$, that magical product of two huge primes $p,q$. But beware. Even if your Social Security number happens to be a prime, don't use it along with another prime whose product is your public N. Once both factors $p, q$ are known, the game is over, and you land in jail. \end{document}