% Hi,
%
% I got connected after all...
%
% So here's the hopefully final version of the handout. Don't forget
% to latex it twice, because of the references to the equations.
%
% Sasa.
%
\documentclass[10pt]{article}
\newcommand{\RSA}{\emph{RSA}\ }
\newcommand{\mod}{\ \mathrm{mod}\ }
\setlength{\parindent}{0pt}
\addtolength{\textwidth}{1in}
\addtolength{\hoffset}{-0.5in}
\begin{document}
\title{An introduction to RSA}
\author{Sa\v{s}a Radomirovi\'{c}}
\date{February 29, 2000}
\maketitle
\section{What is \RSA?}
\RSA is a crypto system developed by Rivest, Shamir, and
Adleman in 1977. It allows Alice to \emph{publicly}\/ announce or
distribute a key which Bob or anybody else can use to send a secret
message to Alice. Nobody but Alice will be able to decipher the secret
message.
\section{What is the difference between \RSA and Diffie--Hellman (DH)?}
DH allowed Alice and Bob, who might have never met before, to
establish a secret in order to communicate securely. The whole
communication including the generation of the secret takes place while
Eve is listening.
In order to establish the secret, both Alice and Bob had to perform
some calculations and they had to talk to each other while doing
this.
In \RSA only the receiver of the message, who will be Alice in our
case, needs to perform calculations to establish what is called a
\emph{secret key}\/ and a \emph{public key}. She doesn't need to know
from whom she will receive secret messages. All she has to do is
prepare \emph{one}\/ secret key and \emph{one}\/ public key and then
distribute the public key. She can even give her public key to Eve!
Everybody who has Alice's public key can send secret messages to
Alice, but only Alice can decipher the messages and nobody else.
\section{How does this work?}
\subsection{Background}
The most important thing to remember is Euler's equation: For distinct
primes $p$ and $q$,
\begin{equation}\label{eq:mostimportant}
m^{(p-1)(q-1)}=1 \mod pq
\end{equation}
Furthermore, for any numbers $d$ and $e$ (and regardless of any ``mod''),
\begin{equation}\label{eq:multexp}
(m^d)^e=(m^e)^d=m^{d\cdot e}.
\end{equation}
Please don't confuse this with another very important equality
\begin{equation}\label{eq:addexp}
m^d\cdot m^e=m^{d+e}.
\end{equation}
Remember that equations like $2\cdot x = 1 \mod N$, or more generally
\begin{equation}\label{eq:easy}
e\cdot x = 1 \mod N
\end{equation}
can be solved easily and rapidly. We will assume this. If you are
interested in how such equations can be solved, a description
of the process is in your text (pages 108--111).
\subsection{Alice's preparation}
%\begin{enumerate}
\smallskip
{\bf Alice's first step} Alice chooses two large different prime numbers $p$ and $q$
and computes $n=pq$.
\smallskip
{\bf Alice's second step} She chooses an $e$ and computes a $d$ by solving the
equation
$$\fbox{\ensuremath{e\cdot x = 1 \mod (p-1)(q-1)}}$$
which is easy to solve according to (\ref{eq:easy}). Her $d$ will be
the $x$ which solves this equation.
%\end{enumerate}
\smallskip
{\bf Question} Why does she do that?
\emph{Answer}\/ As the homework showed, for any
number $m$ %to the $e$-th, to the $d$-th power equals $m$, i.e.
$$(m^e)^d=m \mod n$$
{\bf Question} Why is that so?
\emph{Answer}\/ First look at what $1 \mod (p-1)(q-1)$ means.
Since at this point there's nothing special about the $(p-1)(q-1)$ we
can write $1 \mod N$ for more convenience. Notice now, that
\begin{eqnarray*}
1 &=& 1 \mod N\\
N+1 &=& 1 \mod N\\
N+N+1 &=& 1 \mod N\\
\vdots & & \vdots\\
N+\ldots+N+1 & = & 1 \mod N
\end{eqnarray*}
If we plug in $(p-1)(q-1)$ for $N$, we get
$$\underbrace{(p-1)(q-1)+\ldots+ (p-1)(q-1)}_{\textrm{Any \# of
times}} +1 = 1\mod (p-1)(q-1)$$
On the other hand, Alice has found out in step A2 that
$$e\cdot d=1\mod (p-1)(q-1)$$
so
$$e\cdot d =
\underbrace{(p-1)(q-1)+\ldots+(p-1)(q-1)}_{\textrm{some \# of
times}} + 1.$$
We don't know how many times $(p-1)(q-1)$ appears, but we shall see
that won't matter.
Euler's equation tells us that
$$m^{(p-1)(q-1)}=1 \mod pq$$
and from the homework we know
$$m^{(p-1)(q-1)+1}=m \mod pq.$$
We can keep multiplying by ``1'' any number of times mod $pq$. That's
exactly the same as multiplying by $m^{(p-1)(q-1)}$, so
$$m^{(p-1)(q-1)+\ldots+(p-1)(q-1)+1}=m \mod pq.$$
But the left hand side is just $m^{e\cdot d}$ and from
equation~(\ref{eq:multexp}) we know that that is equal to $(m^e)^d$.
So Alice has found two numbers $e$ and $d$ satisfying the equation
which follows.
$$\fbox{\ensuremath{(m^e)^d = m \mod n}}$$
Now Alice is prepared.
\subsection{Alice's announcement}
What Alice has prepared in the last step are a so called \emph{secret
key}\/ and a \emph{public key}:
\smallskip
\hspace{2in}{\bf Alice's secret key} $n$ and $d$.
\smallskip
\hspace{2in}{\bf Alice's public key} $n$ and $e$
\smallskip
%\begin{enumerate}
{\bf Alice's third step} She gives the numbers $n$ and $e$ to everybody she knows.
%\end{enumerate}
\smallskip
\subsection{Bob's encryption}
So Bob got $n$ and $e$ from Alice. Suppose $m$ is Bob's message.
\smallskip
%\begin{enumerate}
{\bf Bob encrypts} Bob computes $m^e \mod n$ and calls this
result, $r$.
\smallskip
{\bf Bob transmits} Bob sends the result $r$ to Alice.
%\end{enumerate}
\subsection{Alice's decryption}
Alice gets $m^e \mod n$ from Bob. What Alice wants is $m$.
\smallskip
%\begin{enumerate}
{\bf Alice decrypts} In order to recover the message $m$ Alice computes
$$r^d=(m^e)^d = m \mod n.$$
%\end{enumerate}
\smallskip
$r$ is Bob's encryption of his message. Let's try to be cryptanalysts
now, and attack the system.
\subsection{What Eve might try to do}
{\bf Question} What does Eve know?
\emph{Answer}\/ She knows $n, e$ \underline{and} $r=m^e$. She even knows
that $r$ \underbar{is} $m^e$ mod $n$ because we will assume Eve knows
not only the specific numbers she can observe but also knows the
general idea of the system: she knows that Alice and Bob are using
\RSA. This is a generous assumption, but it is one which has been
shown historically to be useful. Generally it is assumed that an
attacker knows the cryptosystem, but does not know the key. This
assumption, formulated explicitly about a century ago, is called
``Kerckhoff's maxim'' and is named after a Dutch cryptographer who
spent most of his life in France. (You can see {\tt
http://www.cl.cam.ac.uk/$\tilde{\hphantom{a}}$fapp2/kerckhoffs/}.) \\
{\bf Question} What does Eve want to find out?
\emph{Answer}\/ What Eve wants is $m$.
\\
%\\
{\bf Question} What does Alice know that Eve doesn't know?
\emph{Answer}\/ Alice knows $d$.
\\
\\
{\bf Question} How did Alice compute $d$?
\emph{Answer}\/ With the equation
$$e\cdot x = 1 \mod (p-1)(q-1).$$
So \emph{one}\/ thing Eve could try is to discover $p$ and $q$ from
$n$. If she had $p$ and $q$, then she could then compute $(p-1)(q-1)$
and get $d$ just as Alice did. If Eve could find the factors of $n$,
breaking the system is quite easy. But
$$\fbox{\textbf{Factoring seems to be very hard}}$$
when numbers are very large, that is
if the primes $p$ and $q$ are very large. That's an obstacle Eve faces
when she tries to discover the message $m$.
%\subsection{Questions}
%\begin{enumerate}
%\item Say Bob and Cleve have Alice's Public Key. Say Bob encrypted a
%message. Can Cleve decrypt Bob's message?
%\item What else?
%\end{enumerate}
\section{An Example}
In ``the real world'' nobody would ever use numbers as small as those
we use here. This is just for instructional purposes.
\smallskip
%\begin{enumerate}
{\bf Alice's first step} Alice chooses $11$ and $5$ as her primes, and
computes $n=11\cdot 5=55$.
\smallskip
{\bf Alice's second step} She chooses $e=3$ and finds that $d=27$.
\smallskip
{\bf Question} How does she find the $d$?
\emph{Answer}\/ She solves the equation
$3\cdot x=1 \mod 10\cdot 4$.
In \texttt{Maple} she would type: \texttt{msolve(3*x=1,10*4);}
What she gets is $x=27$, so she sets $d=27$.
\smallskip
{\bf Alice's third step} She gives $n=55$ and $e=3$ to Bob.
\medskip
\hrule
\medskip
Bob's got $n=55$ and $e=3$ from Alice. Suppose Bob's message is $m=9$.
\smallskip
{\bf Bob computes} He computes $m^e \mod n$, which is $9^3 \mod 55=14$.
\smallskip
{\bf Bob transmits} He sends $14$ to Alice.
\medskip
\hrule
\medskip
Alice gets $14$ from Bob.
\smallskip
{\bf Alice decrypts} She computes $(m^e)^d \mod n$, which is $14^{27} \mod 55$.
What she gets is $m=9$, Bob's message!
%\end{enumerate}
\smallskip
What about Eve? What has Eve heard?
$n=55$, $e=3$, and secret message: $r=14$. She should know $d$ to decrypt
this easily. But to find $d$ efficiently, she has to know $p$ and
$q$! In this case, Eve has no problems factoring $n$. Everybody knows
that $5\cdot 11=55$. So Eve sits at her computer, runs \texttt{Maple} and
types:
\texttt{msolve(3*x=1,4*10);}. Rapidly \texttt{Maple} tells her that $x=27$.
Now Eve knows Alice's secret key and can decrypt every message Alice gets the
same way that Alice does.
\section{The Real World}
In the real world now the primes $p$ and $q$ each have about 170 digits.
\smallskip
Lots of people are trying to factor
numbers which are the product of two big primes.
\smallskip
The largest such number factored so far is a product of two 78 digit
primes and is known as RSA-155. This result was announced August 22,
1999 by Dr.~H.~J.~J.~te~Riele at the CWI in Amsterdam (which is the national
research institute for mathematics and computer science in the
Netherlands) and was a result of
joint work involving many organizations and people.
\smallskip
The number
\smallskip
109417386415705274218097073220403576120037329454492059909138421314763499842889\\
34784717997257891267332497625752899781833797076537244027146743531593354333897
\smallskip
can be written as the product of the two 78-digit primes:
\smallskip
102639592829741105772054196573991675900716567808038066803341933521790711307779
\smallskip
and
\smallskip
106603488380168454820927220360012878679207958575989291522270608237193062808643
\smallskip
The factoring process for RSA-155 took about 7 months,
more than 300 workstations were involved, and in the end even a huge Cray
supercomputer was needed.
\smallskip
I've estimated that the amount of computer time spent on this new
factoring world record is the equivalent of over 100 years on a
standard PC. This is really not a useful comparison, because the
amount of memory needed was almost 20 times as much as a standard PC
has. Some details: 2048 MB of RAM and up to 3.7 GB of hard disk space
were needed.
\smallskip
The factoring process had various stages. At the end a huge system of
linear equations had to be solved. This is the part that required the
enormous amount of memory, because there were about 6,700,000 equations
with 6,700,000 unknowns to be solved.
\medskip
The original paper on \RSA was {\it A method for obtaining digital
signatures and public-key cryptosystems} by R.~Rivest, A.~Shamir, and
L.~Adleman. It appeared in the February 1978 issue of the
Communications of the ACM (this is the Association for Computing
Machinery), volume 21, pages 120--126.
%\smallskip
The original paper on the factorization of RSA-155 can be obtained
from\\ \texttt{ftp://ftp.cwi.nl/pub/herman/NFSrecords/RSA-155}.
You can read about it on the web page
\\
\texttt{http://www.rsasecurity.com/rsalabs/challenges/factoring/rsa155.html}.
\subsection*{Acknowledgment}
Professor Greenfield is kindly acknowledged for discussions, answering
questions, proofreading, and editing the manuscript.
\end{document}
%. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital
%signatures and public-key cryptosystems. Communications of the ACM,
%21(2): 120-126, February 1978.