\documentclass[11pt, letterpaper]{article}
\usepackage{amssymb,amsmath,amsthm,algorithmic}
\addtolength{\hoffset}{-0.45in}
\addtolength{\textwidth}{0.6in}
\addtolength{\voffset}{-0.35in}
\addtolength{\textheight}{0.5in}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{obs}{Observation}[section]
\newcommand{\gap}{\par\vspace{5pt}}
\newcommand{\Gap}{\par\vspace{10pt}}
\newcommand{\tab}{\par\hspace{5pt}}
\newcommand{\Tab}{\par\hspace{10pt}}
\newcommand{\TAB}{\par\hspace{20pt}}
\begin{document}
\bibliographystyle{plain}
\title{RSA Review}
\author{Amir Hossein Jabbari}
\maketitle
\section{Public-Key Cryptography}
To avoid assigning a key to each pair of individuals in private-key cryptography, while maintaining network confidentiality, public-key cryptography was introduced. The idea behind a {\em public-key} system is that it might be possible to find a cryptosystem where it is computationally infeasible to decypher, yet not impossible.
Since encrypting and decrypting in public-key cryptosystems require excessive time and memory on regular computers, they are not extensively used for general-purpose encryption. Therefore they are used to encrypt keys for symmetric cryptosystems such as DES\footnote{Data Encryption Standard}, to transmit these keys securely through the network.
\section{The RSA Cryptosystem}
The {\em RSA Cryptosystem}\cite{rivest77method}, invented by {\em R. Rivest, A. Shamir, and L. Adleman} in the 1970's is a public key cryptosystem based on modular exponentiation, where the public keys are pairs $(e,n)$, consisting of an exponent {\em e} and a modulus {\em n} that is the product of two large primes; that is, \(n=pq\), where {\em p} and {\em q} are large primes, so that $(e,\phi(n))= 1$. To form a cypher text {\em C} from a given message block {\em M}:\[C = M^{e}\pmod n\]where $0\leq C \leq n$.
To decrypt the cyphertext {\em C}, knowledge of the inverse of {\em e} modulo $\phi(n)$ is required. This inverse, which is usually known as {\em d}, exists because $(e,\phi(n)) = 1$. Therefore:
\[
\begin{array}{ll}
ed \equiv 1 \pmod {\phi(n)}\\
ed = k\phi(n)+1
\end{array}
\]
Now by using {\em p} we can form the plaintext block from it's cypher.
\[
\begin{array}{ll}
D(C)\equiv C^{d}\pmod n\\
D(C)\equiv (M^{e})^{d}\pmod n\\
D(C)\equiv M^{ed}\pmod n\\
D(C)\equiv M^{k\phi(n)+1}\equiv(M^{\phi(n)})^{k}M \pmod n
\end{array}
\]
\begin{theorem} Fermat's Little Theorem\cite{rosen00elementary}.
If $p$ is prime and $a$ is a positive integer with $p\not{|}a$, then \(a^{p-1} \equiv 1 \pmod{p}\).
\end{theorem}
\begin{theorem} The Chinese Remainder Theorem\cite{rosen00elementary}.
Suppose $m_{1}, \ldots ,m_{r}$ are pairwise relatively prime positive integers, and suppose $a_{1}, \ldots, a_{r}$ are integers. Then, the system of $r$ congruences $x \equiv a_{i} \pmod {m_{i}} (1 \leq i \leq r)$ has a unique solution modulo $M = m_{1}\times \cdots \times m_{r},$ which is given by\[x = \sum_{i=1}^{r} a_{i}M_{i}y_{i}\bmod M,\] where \(M_{i} = M/m_{i}\) and \(y_{i}=M_{i}^{-1}\bmod m_{i}\), for $1\leq i \leq r$.
\end{theorem}
Now by taking {\em Fermat's Little Theorem} into consideration, it can be concluded:
\[
\left.
\begin{array}{ll}
M^{p-1}\equiv 1 \pmod p\\
(p-1)|\phi(n)
\end{array}
\right\}\Rightarrow M^{k\phi(n)+1}\equiv M \pmod p
\]
Likewise:
\[
\left.
\begin{array}{ll}
M^{q-1}\equiv 1 \pmod q\\
(q-1)|\phi(n)
\end{array}
\right\}\Rightarrow M^{k\phi(n)+1}\equiv M \pmod q
\]
Together these last two equations and {\em Chinese Remainder Theorem} imply:
\[D(C)\equiv (M^{\phi(n)})^{k}M \equiv M \pmod n\]
\subsection{How to choose a private key and compute a public key}
Private key {\em d} should be first, a large number that a cryptanalyst cannot find by direct search and second, relatively prime to $\phi(n)$. One way of finding a private key, relatively prime to $\phi(n)$ is to choose any prime number greater than $max(p,q)$.
To find public key {\em e}, we use Euclid's algorithm, since
\[ed \equiv 1 \pmod {\phi(n)}\]
\begin{theorem}The Euclidean Algorithm\cite{rosen00elementary}.
Let $r_{0} = a$ and $r_{1} =b$ be integers such that $a\geq b > 0$. If the division algorithm is successively applied to obtain $r_{j} = r_{j+1}q_{j+1}+r_{j+2}$, with $0