8.2RSA.tex

\input{main.tex}

\title{RSA Problem and Encryption}

\begin{document}
\maketitle
\begin{frame}
\frametitle{Outline}
\tableofcontents
\end{frame}
\section{RSA Problem}
\begin{frame}\frametitle{RSA Overview}
\begin{itemize}
\item \textbf{RSA}: Ron Rivest, Adi Shamir and Leonard Adleman, in 1977
\item \textbf{RSA problem}: Given $N = pq$ (two distinct big prime numbers) and $y \in \mathbb{Z}^*_N$, compute $y^{-e}$, $e^{\text{th}}$-root of $y$ modulo $N$
\item \alert{Open problem}:RSA problem is easier than factoring $N$?
\item \textbf{Certification}: PKCS\#1 (RFC3447), ANSI X9.31, IEEE 1363
\item \textbf{Key sizes}: 1,024 to 4,096 bit
\item \textbf{Best public cryptanalysis}: a 768 bit key has been broken
\item \textbf{RSA Challenge}: break RSA-2048 to win \$200,000 USD
\end{itemize}
\textbf{Key lengths} with comparable security :
\begin{center}
\begin{tabular}{|c|c|} \hline
Symmetric & RSA  \\ \hline
80 bits & 1024 bits   \\
128 bits & 3072 bits  \\
256 bits & 15360 bits \\ \hline
\end{tabular}	
\end{center}
\end{frame}
\begin{frame}\frametitle{``Textbook RSA''}
\begin{construction}
\begin{itemize}
\item $\mathsf{Gen}$: on input $1^n$ run $\mathsf{GenRSA}(1^n)$ to obtain $N,e,d$. $pk = \langle N,e \rangle$ and $sk = \langle N,d \rangle$.
\item $\mathsf{Enc}$: on input $pk$ and $m \in \mathbb{Z}^*_N$, $c:= [m^e \bmod N]$.
\item $\mathsf{Dec}$: on input $sk$ and $m \in \mathbb{Z}^*_N$, $m:= [c^d \bmod N]$.
\end{itemize}
\end{construction}
\begin{alertblock}{Insecurity}
Since the ``textbook RSA'' is deterministic, it is insecure with respect to any of the definitions of security we have proposed. 
\end{alertblock}
\alert{Q: How to generate $N,e,d$? What's $\mathbb{Z}^*_N$? How to compute $m^e \bmod N$? Is it TDP? Why is it hard?}
\begin{block}{Textbook}
``\emph{A Computational Introduction to Number Theory and Algebra}''
(Version 2) by Victor Shoup
\end{block}
\end{frame}
\begin{frame}\frametitle{Primes and Modular Arithmetic}
\begin{itemize}
\item The set of \textbf{integers} $\mathbb{Z}$, $a,b,c \in \mathbb{Z}$.
%\item $a$ \textbf{divides} $b$: $a \mid b$ if $\exists c, ac=b$ (otherwise $a \nmid b$). \\$b$ is a \textbf{multiple} of $a$. If $a \notin \{1,b\}$, then $a$ is a \textbf{factor} of $b$. 
\item $p > 1$ is \textbf{prime} if it has no factors; otherwise, \textbf{composite}.
%\item $\forall a,b$, $\exists$ \textbf{quotient} $q$, \textbf{remainder} $r$: $a=qb+r$, and $0\le r < b$.
\item \textbf{Greatest common divisor} $\gcd(a,b)$ is the largest integer $c$ such that $c\mid a$ and $c\mid b$. $\gcd(0,b)=b$, $\gcd(0,0)$ undefined.
%\item $a$ and $b$ are \textbf{relatively prime (coprime)} if $\gcd(a,b)=1$.
%\item \textbf{Euclid's theorem}: there are infinitely many prime numbers.
\item Remainder $r= [a\bmod N] = a - b\lfloor a/b\rfloor $  and $r<N$. $N$ is called \textbf{modulus}.
\item $\mathbb{Z}_N = \{0,1,\dots,N-1\} = \{a \bmod N | a \in \mathbb{Z}\}$.
\item $a$ is \textbf{invertible modulo} $N$ $\iff \gcd(a,N) = 1$. If $ab \equiv 1 \pmod N$, then $b=a^{-1}$ is \textbf{multiple inverse} of $a$ \textbf{modulo} $N$.
\end{itemize}
\end{frame}
%\begin{frame}\frametitle{Fundamental Theorem of Arithmetic}
%\begin{itemize}
%\item \textbf{B\'{e}zout's lemma}: $\forall a,b,\;\exists\;X,Y:\;Xa+Yb=\gcd(a,b)$. $\gcd(a,b)$ is the smallest positive integer that can be expressed in this way.
%\item \textbf{Euclid's lemma}: If $c \mid ab$ and $\gcd(a,c)=1$, then $c \mid b$. \\
%If $p$ is prime and $p\mid ab$, then either $p \mid a$ or $p \mid b$.
%\item \textbf{Fundamental theorem of arithmetic}: $\forall N >1$, $N = \prod _i p_i^{e_i}$, $\{p_i\}$ are distinct primes and $e_i \ge 1$. This expression is unique.
%\end{itemize}
%\end{frame}
%\begin{frame}\frametitle{Modular Arithmetic}
%\begin{itemize}
%\item Remainder $r= [a\bmod N] = a - b\lfloor a/b\rfloor $  and $r<N$. $N$ is called \textbf{modulus}.
%%\item \textbf{Reduction modulo} $N$: mapping $a$ to $[a \bmod N]$.
%\item $\mathbb{Z}_N = \{0,1,\dots,N-1\} = \{a \bmod N | a \in \mathbb{Z}\}$.
%\item $a$ and $b$ are \textbf{congruent modulo} $N$: $a \equiv b \pmod N$ if $[a \bmod N] = [b \bmod N]$.
%\item $a$ is \textbf{invertible modulo} $N$ $\iff \gcd(a,N) = 1$. If $ab \equiv 1 \pmod N$, then $b=a^{-1}$ is \textbf{multiple inverse} of $a$ \textbf{modulo} $N$.
%\item \textbf{Cancellation law}: If $\gcd(a,N)=1$ and $ab \equiv ac \pmod N$, then $b \equiv c \pmod N$.
%\item \textbf{Euclidean algorithm}: $\gcd(a,b) = \gcd(b, [a \bmod b]).$
%\item \textbf{Extended Euclidean algorithm}: Given $a,N$, find $X,Y$ with $Xa+YN = \gcd(a,N)$.
%\end{itemize}
%\end{frame}
\begin{frame}\frametitle{Examples of Modular Arithmetic}
\textbf{Euclidean algorithm}: $\gcd(a,b) = \gcd(b, [a \bmod b]).$
\begin{exampleblock}{Find $\gcd(12, 27)$}
%$(-3)\cdot 11 + 2\cdot 17 = 1$, so 14 is the inverse of 11.
\end{exampleblock}
\textbf{Extended Euclidean algorithm}: Given $a,N$, find $X,Y$ with $Xa+YN = \gcd(a,N)$\footnote{B\'{e}zout's lemma}.
\begin{exampleblock}{Find the inverse of $11 \pmod {17}$}
%$(-3)\cdot 11 + 2\cdot 17 = 1$, so 14 is the inverse of 11.
\end{exampleblock}
Reduce and then add/multiply
\begin{exampleblock}{Compute $193028 \cdot 190301 \bmod 100$}
%[193028 \bmod 100] \cdot [190301 \bmod 100] \bmod 100 = ?$
%$= 28\cdot 1 \equiv 28 \bmod 100.$
\end{exampleblock}
\textbf{Cancellation law}: If $\gcd(a,N)=1$ and $ab \equiv ac \pmod N$, then $b \equiv c \pmod N$.
\begin{exampleblock}{$a=3, c=10, b=2, N=24$}
%$3\cdot 2 = 6 \equiv 3 \cdot 10 \pmod{24}$, but $2 \not \equiv 10 \pmod{24}$.
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{$\mathbb{Z}_N^*$ Group}
\[ \mathbb{Z}_N^* \overset{\text{def}}{=} \{a \in \{1,\dotsc,N-1 \} | \gcd(a,N) = 1\} \]
A \textbf{group} is a set $\mathbb{G}$ with a binary operation $\circ$:
\begin{itemize}
\item (\textbf{Closure}:) $\forall g,h \in \mathbb{G}$, $g \circ h \in \mathbb{G}$.
\item (\textbf{Existence of an Identity}:) $\exists$ \textbf{identity} $e\in \mathbb{G}$ such that $\forall g\in \mathbb{G}, e \circ g = g = g \circ e$.
\item (\textbf{Existence of Inverses}:) $\forall g \in G$, $\exists\; h \in \mathbb{G}$ such that $g \circ h =e = h \circ g$. $h$ is an \textbf{inverse} of $g$.
\item (\textbf{Associativity}:) $\forall g_1,g_2,g_3 \in \mathbb{G}$, $(g_1\circ g_2)\circ g_3 = g_1 \circ (g_2 \circ g_3)$.
\end{itemize}
$\mathbb{G}$ with $\circ$ is \textbf{abelian} if
\begin{itemize}
\item (\textbf{Commutativity}:) $\forall g,h \in \mathbb{G}, g\circ h = h\circ g$.
\end{itemize}
Existence of inverses implies \textbf{cancellation law}.\\
When $\mathbb{G}$ is a \textbf{finite group} and $\abs{\mathbb{G}}$ is the \textbf{order} of group.
\begin{exampleblock}{
Is $\mathbb{Z}_N^*$ a group under `$\cdot$'? How about $\mathbb{Z}_N$ under `$\cdot$'?\\
$\mathbb{Z}_{15}^* = ?$ $\mathbb{Z}_{13}^* = ?$}
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{Group Exponentiation}
%\[mg = m\cdot g \overset{\text{def}}{=} \underbrace{g+\cdots +g}_{m\; \text{times}}.\]
\[ g^m \overset{\text{def}}{=} \underbrace{g\circ g\circ \cdots \circ g}_{m\; \text{times}}. \]
\begin{theorem}
$\mathbb{G}$ is a finite group. Then $\forall g \in \mathbb{G}, g^{\abs{\mathbb{G}}}=1$.
\end{theorem}
\begin{exampleblock}{Calculate all exponentiation of $3 \in \mathbb{Z}_{7}^*$}
\end{exampleblock}
\begin{corollary}
$\forall g \in \mathbb{G}$ and $i$, $g^i \equiv g^{[i \bmod {\abs{\mathbb{G}}}]}$.
\end{corollary}
\begin{exampleblock}{Calculate $3^{78} \in \mathbb{Z}_{7}^*$}
\end{exampleblock}
%\begin{corollary}
%Define function $f_e\;:$ $\mathbb{G} \to \mathbb{G}$ by $f_e(g) =g^e$. \\
%If $\gcd(e,\abs{\mathbb{G}})=1$, then $f_e$ is a permutation. \\
%Let $d = [e^{-1} \bmod {\abs{\mathbb{G}}}]$, then $f_d$ is the inverse of $f_e$. ($f_d(f_e(g))=g$)\\
%\textbf{$e$'th root of $c$}: $g^e = c$, $g = c^{1/e} = c^{d}$. 
%\end{corollary}
\end{frame}
\begin{frame}\frametitle{Arithmetic algorithms}
\begin{itemize}
\item \textbf{Addition/subtraction}: linear time $O(n)$.
\item \textbf{Mulplication}: naively $O(n^2)$. Karatsuba (1960): $O(n^{\log_2 3})$\\
Basic idea: $(2^bx_1+x_0) \times (2^by_1+ y_0)$ with 3 mults.\\
Best (asymptotic) algorithm: about $O(n\log n)$.
\item \textbf{Division with remainder}: $O(n^2)$.
\item \textbf{Exponentiation}: $O(n^3)$.
\end{itemize}
\begin{algorithm}[H]
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\SetKw{KwB}{break}
\SetKw{KwH}{halt}
\DontPrintSemicolon
\caption{Exponentiating by Squaring}
\Input{$g \in G$; exponent $x=[x_nx_{n-1}\dots x_2x_1x_0]_2$}
\Output{$g^x$}
\BlankLine
$y \gets g; z \gets 1$\;
\For{$i = 0$ \KwTo $n$}{
  \lIf{$x_i == 1$}{$z \gets z \times y$}\;
  $y \gets y^2$\;
}
\Return $z$
\end{algorithm}
\end{frame}
\begin{frame}\frametitle{Euler's Phi Function}
%\[ \mathbb{Z}_N^* \overset{\text{def}}{=} \{a \in \{1,\dotsc,N-1 \} | \gcd(a,N) = 1\} \]
\textbf{Euler's phi function}: $\phi(N) \overset{\text{def}}{=} \abs{\mathbb{Z}_N^*}$.
\begin{theorem}
$N = \prod_ip_i^{e_i}$ \footnote{Fundamental theorem of arithmetic}, $\{p_i\}$ are distinct primes, $\phi(N) = \prod_ip_i^{e_i-1}(p_i-1)$.
\end{theorem}
\begin{exampleblock}{$N=pq$ where $p,q$ are distinct primes. $\phi(N)=?$ $\phi(12)=?\quad \phi(30)=?$}
\end{exampleblock}
\begin{corollary}[Euler's theorem \& Fermat's little theorem]
$a \in \mathbb{Z}_N^*$. $a^{\phi (N)} \equiv 1 \pmod N$.\\
If $p$ is prime and $a \in \{1,\dotsc,p-1\}$, then $a^{p-1} \equiv 1 \pmod p$.
\end{corollary}
\begin{exampleblock}{$3^{43} \bmod 49 = ?$}
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{Permutation by Group Exponentiation Function}
\textbf{Exponentiation function} $f_e\;:$ $\mathbb{Z}^*_N \to \mathbb{Z}^*_N$ by $f_e(x) =[x^e \bmod N]$.\\
\textbf{$e$'th root of $y$}: $x^e \equiv y$, $x \equiv y^{1/e}$. 
\begin{corollary}
If $\gcd(e,\phi(N))=1$, then $f_e$ is a permutation.
\end{corollary}
\begin{proof}
Let $d = [e^{-1} \bmod \phi(N)]$, then $f_d$ is the inverse of $f_e$.\\
$y \equiv x^{e};\quad f_{d}(y) \equiv y^d \equiv x^{ed} \equiv x$. 
\end{proof}
\begin{exampleblock}{In $\mathbb{Z}^*_{10}$,\ $e = 3,\ d = ?,\ f_{e}(3) = ?,\ f_{d}(f_{e}(3)) = ?,\ 9^{\frac{1}{3}} = ?$}
\end{exampleblock}
\begin{alertblock}{What if we cannot get $\phi(N)$ for some `special' $N$?\\
What if we cannot factorize these `special' $N$?}
\end{alertblock}
\end{frame}
\begin{frame}\frametitle{Factoring Is Hard}
\begin{itemize}
\item \textbf{Factoring} $N=pq$. $p,q$ are of the same length $n$.
\item \textbf{Trial division}: $\mathcal{O}(\sqrt{N}\cdot \mathsf{polylog}(N))$.
\item \textbf{Pollard's $p-1$} method: effective when $p-1$ has ``small'' prime factors.
\item \textbf{Pollard's rho} method: $\mathcal{O}(N^{1/4}\cdot \mathsf{polylog}(N))$.
\item \textbf{Quadratic sieve} algorithm [Carl Pomerance]: sub-exponential time $\mathcal{O}(\exp(\sqrt{n\cdot \log n}))$.
\item The best-known algorithm is the \textbf{general number field sieve} [Pollard] with time $\mathcal{O}(\exp(n^{1/3}\cdot(\log n)^{2/3}))$.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{The RSA Problem Is Hard}
\textbf{Idea}: factoring is hard\\ $\implies$ for $N=pq$, finding $p,q$ is hard\\ $\implies$ computing $\phi(N)=(p-1)(q-1)$ is hard\\ 
%$\implies$ computations modulo $\phi(N)$ is not available\\ 
$\implies$ computing $e^{-1} \bmod \phi(N)$ is hard\\
\alert{\textbf{There is a gap.}}\\
$\implies$ RSA problem is hard:\\
Given $y \in \mathbb{Z}^*_N$, compute $y^{-e}$ modulo $N$.
\begin{alertblock}{Open problem}
RSA problem is easier than factoring?
\end{alertblock}
\end{frame}
\begin{comment}
\begin{frame}\frametitle{Subgroups}
If $\mathbb{G}$ is a group, a set $\mathbb{H} \subseteq \mathbb{G}$ is a \textbf{subgroup} of $\mathbb{G}$ if $\mathbb{H}$ itself forms a group under the same operation associated with $\mathbb{G}$. $\mathbb{H}$ is a \textbf{strict subgroup} if $\mathbb{H} \neq \mathbb{G}$.
\begin{itemize}
\item If $\mathbb{H} \subseteq \mathbb{G}$, $\mathbb{H}$ contains the identity element of $\mathbb{G}$, and $\mathbb{H}$ is closed, then $\mathbb{H}$ is a subgroup of $\mathbb{G}$.
\item \textbf{Lagrange's theorem}: For a finite group $\mathbb{G}$ and its subgroup $\mathbb{H}$,  $\abs{\mathbb{H}} \mid \abs{\mathbb{G}}$.
\item $\mathbb{H}$ is a strict subgroup of a finite group $\mathbb{G}$, then $\abs{\mathbb{H}} \le \abs{\mathbb{G}}/2$.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Examples on Groups}
\begin{exampleblock}{}
\begin{itemize}
\item $\mathbb{Z}$ is an abelian group under `$+$', not a group under `$\cdot$'.
\item The set of real numbers $\mathbb{R}$ is not a group under `$\cdot$'.
\item $\mathbb{R}\setminus \{0\}$ is an abelian group under `$\cdot$'.
\item $\mathbb{Z}_N$ is an abelian group under `$+$' modulo $N$.
\item If $p$ is prime, then $\mathbb{Z}_p^*$ is an abelian group under `$\cdot$' modulo $p$. 
\item $\mathbb{Z}_{15}^*= \{1,2,4,7,8,11,13,14\}$, $\abs{\mathbb{Z}_{15}^*}=8$.
\item $\mathbb{Z}_{3}^*$ is a subgroup of $\mathbb{Z}_{15}^*$, but $\mathbb{Z}_{5}^*$ is not.
\item $2^{1/3} \bmod 5 = 2^{3} \bmod 5 = 3$. ($3^{-1} = 3 \pmod 4$)
\item $g^3$ is a permutation on $\mathbb{Z}_{15}^*$, but $g^2$ is not (e.g., $8^2 \equiv 2^2\equiv 4$). 
\end{itemize}
\end{exampleblock}
\begin{exampleblock}{$N=pq$ where $p,q$ are distinct primes. $\phi(N)=?$}
$\phi(N)=(N-1)-(q-1)-(p-1)=(p-1)(q-1)$.
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{Isomorphism and Cross Product}
A bijection function $f : \mathbb{G} \to \mathbb{H}$ is an \textbf{isomorphism from} $\mathbb{G}$ \textbf{to} $\mathbb{H}$:
\[ \forall g_1,g_2 \in \mathbb{G}, f(g_1 \circ_{\mathbb{G}} g_2) = f(g_1) \circ_{\mathbb{H}} f(g_2).\]
If $\exists$ such $f$, $\mathbb{G} \simeq \mathbb{H}$.\newline

The \textbf{cross product} of $\mathbb{G}$ and $\mathbb{H}$: $\mathbb{G} \times \mathbb{H}$. The elements are $(g,h)$ with $g \in \mathbb{G}$ and $h \in \mathbb{H}$, the operation $\circ$,
\[ (g,h)\circ (g',h') \overset{\text{def}}{=} (g \circ_{\mathbb{G}} g', h \circ_{\mathbb{H}} h')\]
\end{frame}
\begin{frame}\frametitle{Chinese Remainder Theorem}
\begin{theorem}[Chinese remainder theorem]
$N = pq$ where $\gcd(p,q)=1$.
\[\mathbb{Z}_N \simeq \mathbb{Z}_p \times \mathbb{Z}_q\;\;\text{and}\;\;\mathbb{Z}_N^* \simeq \mathbb{Z}_p^* \times \mathbb{Z}_q^* .\]
$f$ maps $x \in \{0,\dotsc,N-1\}$ to pairs $(x_p,x_q):$
\[ f(x) \overset{\text{def}}{=} ([x \bmod p],[x \bmod q]). \]
$f$ is an isomorphism from $\mathbb{Z}_N$ to $\mathbb{Z}_p \times \mathbb{Z}_q$ and 
$\mathbb{Z}_N^*$ to $\mathbb{Z}_p^* \times \mathbb{Z}_q^*$.
\end{theorem}
If $f(x)=(x_p,x_q)$, $x \leftrightarrow (x_p,x_q) = ([x \bmod p], [x \bmod q])$.
\end{frame}
\begin{frame}\frametitle{Using the Chinese Remainder Theorem}
Compute $g=g_1\circ_{\mathbb{G}} g_2$ [$g \equiv g_1 \times g_2 \pmod N$]:
\begin{enumerate}
\item Compute $h_1=f(g_1)$ and $h_2=f(g_2)$;
\item Compute $h=h_1 \circ_{\mathbb{H}} h_2$;
\item Compute $g = f^{-1}(h)$.
\end{enumerate}
\begin{exampleblock}{Compute $14\cdot 13 \bmod 15$}
$[14\cdot 13 \bmod 15] \leftrightarrow (4,2)\cdot (3,1) = ([4\cdot 3 \bmod 5],[2\cdot 1 \bmod 3])$ $=(2,2) \leftrightarrow 2$.
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{Using the Chinese Remainder Theorem (Cont.)}
Convert $(x_p,x_q)$ to its representation modulo $N$:
\begin{enumerate}
\item Compute $X,Y$ such that $Xp+Yq=1$.
\item $1_p = [Yq \bmod N]$ and $1_q = [Xp \bmod N]$.
\item Compute $x = [(x_p\cdot 1_p+x_q\cdot 1_q) \bmod N]$.
\end{enumerate}
\begin{exampleblock}{Find the representation of $([4 \bmod 5],[3 \bmod 7])$ modulo $35$.}
Use extended Euclidean algorithm, $3\cdot 5-2\cdot 7 =1$.\\
$1_p = [(-2\cdot 7) \bmod 35]=21$ and $1_q = [3\cdot 5 \bmod 35] = 15$.\\
$(4,3) \leftrightarrow [4\cdot 1_p + 3\cdot 1_q \bmod 35] = 24$.
\end{exampleblock}
\begin{exampleblock}{Compute $[29^{100} \bmod 35]$}
$29 \leftrightarrow ([1 \bmod 5],[-1 \bmod 7])$, $[29^{100} \bmod 35] \leftrightarrow (1,-1)^{100} = (1,1) \leftrightarrow 1$.
\end{exampleblock}
\end{frame}
\end{comment}
\begin{frame}\frametitle{Generating Random Primes}
\begin{algorithm}[H]
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\SetKw{KwB}{break}
\SetKw{KwH}{halt}
\DontPrintSemicolon
\caption{Generating a random prime}
\Input{Length $n$; parameter $t$}
\Output{A random $n$-bit prime}
\BlankLine
\For{$i = 1$ \KwTo $t$}{
  $p' \gets \{0,1\}^{n-1}$\;
  $p := 1\| p'$\;
  \lIf{$p$ is prime}{\Return $p$}\;
}
\Return fail
\end{algorithm}
\begin{itemize}
\item $\exists$ a constant $c$ such that, $\forall n>1$, a randomly selected $n$-bit number is prime with probability at least $c/n$.
\item If $N$ is prime, then the Miller-Rabin test always outputs ``prime''. If $N$ is composite, then the algorithm outputs ``prime'' with probability at most $2^{-t}$.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Generating RSA Problem}
Let $\mathsf{GenModulus}(1^n)$ be a polynomial-time algorithm that, on input $1^n$, outputs $(N,p,q)$ where $N=pq$, and $p,q$ are $n$-bit primes except with probability negligible in $n$.
\begin{algorithm}[H]
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\SetKw{KwF}{find}
\SetKw{KwC}{compute}
\DontPrintSemicolon
\caption{$\mathsf{GenRSA}$}
\Input{Security parameter $1^n$}
\Output{$N,e,d$}
\BlankLine
$(N,p,q) \gets \mathsf{GenModulus}(1^n)$\;
$\phi(N) := (p-1)(q-1)$\;
\KwF $e$ such that $\gcd(e,\phi(N))=1$\;
\KwC $d := [e^{-1} \bmod \phi(N)]$\;
\Return $N,e,d$\;
\end{algorithm}
\begin{exampleblock}{Show an example of RSA problem}
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{The RSA Assumption}
The RSA experiment $\mathsf{RSAinv}_{\mathcal{A},\mathsf{GenRSA}}(n)$:
\begin{enumerate}
\item Run $\mathsf{GenRSA}(1^n)$ to obtain $(N,e,d)$.
\item Choose $y \gets \mathbb{Z}^*_N$.
\item $\mathcal{A}$ is given $N,e,y$, and outputs $x \in \mathbb{Z}^*_N$.
\item $\mathsf{RSAinv}_{\mathcal{A},\mathsf{GenRSA}}(n)=1$ if $x^e \equiv y \pmod N$, and 0 otherwise.
\end{enumerate}
\begin{definition}
\textbf{RSA problem is hard relative to} $\mathsf{GenRSA}$ if $\forall$ \textsc{ppt} algorithms $\mathcal{A}$, $\exists$ $\mathsf{negl}$ such that
\[ \Pr[\mathsf{RSAinv}_{\mathcal{A},\mathsf{GenRSA}}(n) = 1] \le \mathsf{negl}(n).\]
\end{definition}
\end{frame}
\begin{frame}\frametitle{Constructing Trap-Door Permutations}
\begin{construction}
Define a family of permutations with $\mathsf{GenRSA}$:
\begin{itemize}
\item $\mathsf{Gen}$: on input $1^n$, run $\mathsf{GenRSA}(1^n)$ to obtain $(N,e,d)$ and output $I=\langle N,e \rangle, \mathsf{td}=d$, Set $\mathcal{D}_I = \mathcal{D}_{\mathsf{td}} = \mathbb{Z}^*_N$.
\item $\mathsf{Samp}$: on input $I$, choose a random element $x$ of $\mathbb{Z}^*_N$.
\item $f_{I}(x) = [ x^e \bmod N]$.
\item deterministic \textbf{inverting algorithm} $\mathsf{Inv}_{\mathsf{td}}(y) = [ y^d \bmod N]$.
\end{itemize}
\end{construction}
Reduce the RSA problem to the inverting problem.
\end{frame}
\section{Attacks against ``Textbook RSA'' Encryption}
\begin{frame}\frametitle{Recall ``Textbook RSA''}
\begin{construction}
\begin{itemize}
\item $\mathsf{Gen}$: on input $1^n$ run $\mathsf{GenRSA}(1^n)$ to obtain $N,e,d$. $pk = \langle N,e \rangle$ and $sk = \langle N,d \rangle$.
\item $\mathsf{Enc}$: on input $pk$ and $m \in \mathbb{Z}^*_N$, $c:= [m^e \bmod N]$.
\item $\mathsf{Dec}$: on input $sk$ and $m \in \mathbb{Z}^*_N$, $m:= [c^d \bmod N]$.
\end{itemize}
\end{construction}
\begin{alertblock}{Insecurity}
Since the ``textbook RSA'' is deterministic, it is insecure with respect to any of the definitions of security we have proposed. 
\end{alertblock}
\end{frame}
%\begin{frame}\frametitle{Example of ``Textbook RSA''}
%\begin{exampleblock}{$N=253$, $p=11$, $q=23$, $e=3$, $d=147$, $\phi(N)=220$.}
%$m=0111001=57$.\\
%Encryption: $250 := [57^3 \bmod 253]$.\\
%Decryption: $57 := [250^{147} \bmod 253]$.
%\newline
%
%Using CTR,
%\[ [250^{[147 \bmod 10]} \bmod 11] = [8^7 \bmod 11] = 2\]
%\[ [250^{[147 \bmod 22]} \bmod 23] = [20^{15} \bmod 23] = 11\]
%$57 \leftrightarrow (2,11)$.
%\end{exampleblock}
%\end{frame}
\begin{frame}\frametitle{Attacks on ``Textbook RSA'' with a small $e$}
\textbf{Small $e$ and small $m$ make modular arithmetic useless.}
\begin{itemize}
\item If $e=3$ and $m < N^{1/3}$, then $c = m^3$ and \alert{$m=$ \underline{$\quad $} ?} %c^{1/3}
\item In the hybrid encryption, 1024-bit RSA with 128-bit DES.
\end{itemize}
\textbf{A general attack when small $e$ is used:}
\begin{itemize}
\item $e=3$, the same message $m$ is sent to 3 different parties.
\item $c_1= [ m^3 \bmod N_1]$, $c_2= [ m^3 \bmod N_2]$, $c_3= [ m^3 \bmod N_3]$.
\item $N_1,N_2,N_3$ are coprime, and $N^*=N_1N_2N_3$, $\exists$ unique $\hat{c} < N^*$:\\
$\hat{c} \equiv c_1 \pmod{N_1}$, $\hat{c} \equiv c_2 \pmod{N_2}$, $\hat{c} \equiv c_3 \pmod{N_3}$.
\item With Chinese Remainder Theory\footnote{
$N = pq$ where $\gcd(p,q)=1$.
$\mathbb{Z}_N \simeq \mathbb{Z}_p \times \mathbb{Z}_q\;\;\text{and}\;\;\mathbb{Z}_N^* \simeq \mathbb{Z}_p^* \times \mathbb{Z}_q^* .$
}, $\hat{c} \equiv m^3 \pmod{N^*}$. Since $m^3 < N^*$, $m = \hat{c}^{1/3}$.
\end{itemize}
\end{frame}
%\begin{comment}
\begin{frame}\frametitle{A Quadratic Improvement in Recovering $m$}
If $1 \le m < \mathcal{L} = 2^{\ell}$, there is an attack that recovers $m$  in time $\sqrt{\mathcal{L}}$.
\[ \text{Idea}: c \equiv m^e = (r\cdot s)^e = r^e\cdot s^e \pmod N \]
\begin{algorithm}[H]
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\SetKw{KwS}{set}
\SetKw{KwT}{sort}
\DontPrintSemicolon
\caption{An attack on textbook RSA encryption}
\Input{Public key $\langle N,e \rangle$; ciphertext $c$; parameter $\ell$}
\Output{$m < 2^{\ell}$ such that $m^e \equiv c \pmod N$}
\BlankLine

\KwS $T := 2^{\alpha \ell}$ \tcc*[f]{$\frac{1}{2} < \text{constant}\; \alpha <1$}\;
\lFor{$r=1$ \KwTo $T$}{$x_r := [c/r^e \bmod N]$}\;
\KwT the pairs $\{ (r,x_r)\}^T_{r=1}$ by $x_r$\;
\For{$s=1$ \KwTo $T$}{
\If{$[s^e \bmod N] \overset{?}{=} x_r$ for some $r$}{
 \Return $[r\cdot s \bmod N]$\;
}
}
\Return fail\;
\end{algorithm}
It can be shown that with good probability that $m=r\cdot s$:
\end{frame}
%\end{comment}
\begin{frame}\frametitle{Common Modulus Attacks}
\textbf{Common Modulus Attacks}: the same modulus $N$.
\newline

\textbf{Case I}: for multiple users with their own secret keys.\\
Each user can find $\phi(N)$ with his own $e,d$, then find others' $d$.
\newline

\textbf{Case II}: for the same message encrypted with two public keys.\\
Assume $\gcd(e_1,e_2)=1$, $c_1 \equiv m^{e_1}$ and $c_2 \equiv m^{e_2} \pmod N$. $\exists X,Y$ such that $Xe_1 + Ye_2 = 1$\footnote{B\'{e}zout's lemma}.
\[ c_1^X\cdot c_2^Y \equiv m^{Xe_1}m^{Ye_2} \equiv m^1 \pmod N.\]
\begin{exampleblock}{$N = 15, e_{1} = 3, e_{2} = 5, c_{1} = 8, c_{2} = 2, m = ?$ } %m=2
%X = 2, Y = -1, 8^{2} 2^{-1} = 2
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{CCA in ``Textbook RSA'' Encryption}
\begin{exampleblock}{Recovering the message with CCA}
$\mathcal{A}$ choose a random $r \gets \mathbb{Z}^*_N$ and compute $c' = [r^e\cdot c \bmod N]$, and get $m'$ with CCA. Then $m=\ ?$%[m'\cdot r^{-1}\bmod N]$.
%\[ m'\cdot r^{-1} \equiv ? \] %(c')^dr^{-1} \equiv (r^e\cdot m^e)^dr^{-1} \equiv r^{ed}m^{ed}r^{-1} \equiv rmr^{-1} \equiv m.\]	
\end{exampleblock}
\begin{exampleblock}{Doubling the bid at an auction}
The ciphertext of an bid is $c = [m^e \bmod N]$. $c'= [2^ec \bmod N]$.
\[(c')^d \equiv\ ? \]%(2^em^e)^d \equiv 2^{ed}m^{ed}\equiv 2m.\]
\end{exampleblock}
\end{frame}
\section{RSA Encryption in Practice}
\begin{frame}\frametitle{RSA Implementation Issues}
\begin{itemize}
\item \textbf{Encoding binary strings as elements of} $\mathbb{Z}^*_N$: $\ell = \|N\|$. Any binary string $m$ of length $\ell - 1$ can be viewed as an element of $Z_N$. Although $m$ may not be in $Z_N^*$, RSA still works.
\item \textbf{Choice of} $e$: Either $e=3$ or a small $d$ are bad choices. \\
      Recommended value: $e=65537=2^{16}+1$
\item \textbf{Using the Chinese remainder theorem}: to speed up the decryption.\\
\[ [c^d \bmod N] \leftrightarrow ([c^d \bmod p],[c^d \bmod q]). \]
Assume that exponentiation modulo a $v$-bit integer takes $v^3$ operations. RSA decryption takes $(2n)^3=8n^3$, whereas using CRT takes $2n^3$. 
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Padded RSA}
\textbf{Idea}: add randomness to improve security.
\begin{construction}
Let $\ell$ be a function with $\ell(n) \le 2n-2$ for all $n$.
\begin{itemize}
\item $\mathsf{Gen}$: on input $1^n$, run $\mathsf{GenRSA}(1^n)$ to obtain $(N,e,d)$. Output $pk = \langle N,e \rangle$, and $sk = \langle N,d \rangle$.
\item $\mathsf{Enc}$: on input $m \in \{0,1\}^{\ell(n)}$, choose a random string $r \gets \{0,1\}^{\|N\| - \ell(n)-1}$. Output $c:=[(r\|m)^e \bmod N]$.
\item $\mathsf{Dec}$: compute $\hat{m} := [c^d \bmod N]$, and output the $\ell(n)$ low-order bits of $\hat{m}$.
\end{itemize}
\end{construction}
$\ell$ should neither be too large ($r$ is too short in theory) nor be too small ($m$ is too short in practice).
\begin{theorem}
If the RSA problem is hard relative to $\mathsf{GenRSA}$, then Construction with $\ell(n)=\mathcal{O}(\log n)$ is CPA-secure.
\end{theorem}
\end{frame}
\begin{comment}
\begin{frame}\frametitle{PKCS \#1 v1.5 (RSAES-PKCS1-v1\_5)}
\textbf{Public-Key Cryptography Standard (PKCS) \#1 version 1.5}:
\begin{itemize}
\item $N$ has $k$ bytes, $2^{8(k-1)} \le N < 2^{8k}$.
\item Message $m$ has $D (\le k-11)$ bytes.
\item Random pad $r$ has $(k-D-3)$ bytes without $\{0\}^8$.
\item The ciphertext:
\end{itemize}
\[[(\{0\}^8\|\{0\}^610\|r\|\{0\}^8\|m)^e \bmod N]\] 
\textbf{Security}: PKCS \#1 v1.5 is believed to be CPA-secure, although no proof based on the RSA assumption has ever been shown.
\end{frame}
\begin{frame}\frametitle{Attack on PKCS \#1 v1.5}
\textbf{PKCS \#1 v1.5 used in HTTPS}:\\
if the first 16 bits of message is not ``02'' which is standing for ``PKCK \#1'', then the web server returns error.\newline

\textbf{CCA to infer the message $m$ of ciphertext $c$}:
\begin{enumerate}
\item choose a string $r$, compute $c' \gets r^e\cdot c = (r\cdot \mathsf{PKCS1}(m))^e$.
\item send $c'$ to the web server. If the server does not return error, some bits of $m$ can be learned.
\item change $r$ and learn other bits of $m$.
\end{enumerate}

\textbf{HTTPS Defense} [RFC 5246]: if not ``02'', set the message as a random string.
\end{frame}
\end{comment}

\begin{frame}\frametitle{PKCK \#1 v2.1 (RSAES-OAEP)}
\textbf{Optimal Asymmetric Encryption Padding} (OAEP): encode $m$ of length $n/2$ as $\hat{m}$ of length $2n$. $G, H$ are \textbf{Random Oracles}.
\[ \hat{m}_1 := G(r)\oplus (m\| \{0\}^{n/2}), \hat{m} := \hat{m}_1 \| (r \oplus H(\hat{m}_1)).\]
\begin{figure}
\begin{center}
\input{tikz/OAEP}
\end{center}
\end{figure}
\alert{Q: How to decipher?}
\end{frame}

\begin{frame}\frametitle{PKCK \#1 v2.1 (RSAES-OAEP) (Cont.)}
RSA-OAEP is CCA-secure in Random Oracle model. \footnote{It may not be secure when RO is instantiated.} [RFC 3447]
\begin{figure}
\begin{center}
\input{tikz/OAEP}
\end{center}
\end{figure}
CPA: To learn $r$, attacker has to learn $\hat{m}_1$ from $(\hat{m}_1\|\hat{m})^e$\\

CCA: Effective decryption query is disabled by checking "00...0" in the plaintext before the response\\

\end{frame}

\begin{frame}\frametitle{OAEP Improvements}
\begin{columns}
\begin{column}{5cm}
\begin{figure}
\begin{center}
\input{tikz/OAEP-plus}
\input{tikz/SAEP-plus}
\end{center}
\end{figure}
\end{column}
\begin{column}{5cm}
\textbf{OAEP+}: $\forall $ trap-door permutation F, F-OAEP+ is CCA-secure.\newline

\textbf{SAEP+}: RSA (e=3) is a trap-door permutation, RSA-SAEP+ is CCA-secure.\newline

$W, G, H$ are Random Oracles.
\end{column}
\end{columns}
\end{frame}
\begin{frame}\frametitle{Implementation Attacks on RSA}
\begin{exampleblock}{Simplified CCA on PKCS1 v1.5 in HTTPS [Bleichenbacher]}
Server tells if the MSB of plaintext (Version Number) = `1' for a given ciphertext. Attacker sends $c' = (2^{r})^{e}\cdot c$. If receiving $Yes$, then \alert{$(r+1)$-th $MSB(m)$ = ?}
\begin{figure}
\begin{center}
\input{tikz/CCA-PKCS.tex}
\end{center}
\end{figure}
\end{exampleblock}
\textbf{Defense}: treating incorrectly formatted message blocks in a manner indistinguishable from correctly formatted blocks. See [RFC 5246]
\end{frame}
\begin{frame}\frametitle{Implementation Attacks on RSA (Cont.) }
\textbf{Timing attack}: [Kocher et al. 1997] 
The time it takes to compute $c^d$ can expose $d$. (require a high-resolution clock)\\
\textbf{Power attack}: [Kocher et al. 1999]
The power consumption of a smartcard while it is computing $c^d$ can expose $d$.\\
\textbf{Defense}: \textbf{Blinding} by choosing a random $r$ and deciphering $r^{e}\cdot c$. 
\newline

\textbf{Key generation trouble} (in OpenSSL RSA key generation):\\
Same $p$ will be generated by multiple devices (due to poor entropy at startup), but different $q$ (due to additional randomness).\\
\alert{Q: $N_1,N_2$ from different devices, $\gcd(N_1,N_2) = ?$}\\
Experiment result: factor 0.4\% of public HTTPS keys.
\end{frame}
\begin{frame}\frametitle{Faults Attack on RSA}
\textbf{Faults attack}:
A computer error during $c^d\bmod N$ can expose $d$.\newline

Using Chinese Remainder Theory to speed up the decryption:
\[ [c^d \bmod N] \leftrightarrow ([m_p \equiv c^d \pmod p],[m_q \equiv c^d \pmod q]).\]
\textbf{Suppose error occurs when computing $m_q$, but no error in $m_p$.}\newline

Then output $m' \equiv c^d \pmod p$, $m' \not \equiv c^d \pmod q$.\\
So $(m')^e \equiv c \pmod p$, $(m')^e \not \equiv c \pmod q$.\\
\alert{\[\gcd((m')^e-c, N)=\ ?\]}

\textbf{Defense}: check output. (but 10\% slowdown)
\end{frame}
\begin{frame}\frametitle{Summary}
\begin{itemize}
\item RSA, ``textbook RSA'', padded RSA, PKCS
\item small $e$, common modulus attacks, CCA, implementation/faults attack
\end{itemize}
\end{frame}
\end{document}