\section{Rabin Public-Key scheme}

Rabin's cryptosystem (\cite{Ra79}) was the first example of a provably
secure encryption scheme, it is equivalent to the FACTORING
problem.

\algo{Rabin key generation}{
\step{Pick two large prime numbers $p, q$}
\step{$n \leftarrow pq$}
\step{{\bf RETURN} $K_e = n$, $K_d = (p,q)$}
}

\hspace{-0.6cm}{\bf Encryption:} $c = m^2 \; mod \; n$.\\
{\bf Decryption:} Find the four\footnote{In the unlikely
case where $gcd(m,n) \neq 1$, the ciphertext $c$ has only
one or two square roots.} square roots $m_1, m_2, m_3, m_4$,
and pick the one that makes sens.

\subsection{Crytanalysis}
The task of recovering $m$ from $c$, not knowing the factorisation
of $n$, is exactly the SQROOT problem (\ref{SQROOT}) which is 
polynomialy equivalent to the FACTORING problem (\ref{FACTORING}).

\subsubsection{Chosen-ciphertext attack}
Rabin's scheme is vulnarable to a chosen-ciphertext attack.  The
attack goes as follows:  $Oscar$ picks a random $m \in_R \bbZ^{*}_n$
and computes $c = m^2 \; mod \; n$.  He then gives $c$ to the 
decryption box, wich in turn will give him $y$ that is not necessarily
equal to $m$.  With probability $\frac{1}{2}$, $y \neq \pm m \; mod \; n$,
in which case $gcd(m-y, n)$ is a prime factor of $n$. If $m = \pm y \;
mod \; n$, then $Oscar$ just picks another $m$.

