\documentstyle[12pt,spanish]{article}

\textwidth=6in
\oddsidemargin=0.25in
\evensidemargin=0.25in
\topmargin=-0.1in
\footskip=0.8in
\parindent=0.0cm
\parskip=0.3cm
\textheight=8.00in
\setcounter{tocdepth} {3}
\setcounter{secnumdepth} {2}
\newtheorem{theorem}{Teorema}
\newtheorem{exercise}{Ejercicio}
\newtheorem{corollary}{Corolario}
\newtheorem{lemma}{Lema}
\newtheorem{observation}{Observaci\'on}
\newtheorem{comentary}{Comentario}
\newtheorem{proposition}{Proposici\'on}
\newtheorem{definition}{Definici\'on}
\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\newcommand{\qedbox}{\vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}}
\newcommand{\qed}{\nopagebreak\mbox{}\hfill\qedbox\smallskip}
\newcommand{\startproof}{\noindent{\em Dem:}\hspace{1em}}
\newenvironment{dem}{\startproof}{\qed}
\newenvironment{proof}{{\bf Dem:}\hspace{1em}}{\qed\newline}


\newcommand{\catedra}[4]{
   \pagestyle{headings}
   \thispagestyle{plain}
   \newpage
   \noindent
   \begin{center}
   \makebox[0in]{\framebox{
      \vbox{
    \hbox to 6in { {\bf MA-53G Intr. a la Criptograf\'{\i}a
                        \hfill Semestre Primavera, 1996}  }
       \vspace{4mm}
       \hbox to 6in { {\Large \hfill C\'atedra No. #1 : #2 \hfill} }
       \vspace{2mm}
       \hbox to 6in { {\it Transcriptor: #3 \hfill} }
      }
   }}
   \end{center}
   \markboth{C\'atedra No. #1 : #2}{C\'atedra No. #1 : #2}
   \vspace*{4mm}
}
       
% LISTA DE MACROS PERSONALES COMIENZA AQUI
       
\renewcommand{\emph}[1]{{\em #1}}
\newcommand{\plain}{{\cal P}}
\newcommand{\cipher}{{\cal C}}
\newcommand{\key}{{\cal K}}
\newcommand{\encrip}{{\cal E}}
\newcommand{\decrip}{{\cal D}}
 
\newcommand{\modulo}{{\cal Z}}

\newcommand{\kernel}{\mbox{\rm Ker}}
\newcommand{\determ}[1]{\mbox{\rm det}(#1)}
\newcommand{\mcd}[2]{\mbox{\rm mcd}(#1,#2)}
\newcommand{\mcm}[2]{\mbox{\rm mcm}(#1,#2)}
\newcommand{\set}[2]{\{#1\,|\,#2\}}
\newcommand{\smidge}{{\kern .05em}}
\newcommand{\Colon}{{\smidge\colon\;\:}}
\newcommand{\eqdef}{\stackrel{\rm def}{=}}
 
\newcommand{\chapref}[1]{\mbox{Capitulo~\ref{#1}}}
\newcommand{\secref}[1]{\mbox{Secci\'on~\ref{#1}}}
\newcommand{\ssecref}[1]{\mbox{Secci\'on~\ref{#1}}}
\newcommand{\apref}[1]{\mbox{Ap\'endice~\ref{#1}}}
\newcommand{\thref}[1]{\mbox{Teorema~\ref{#1}}}
\newcommand{\defref}[1]{\mbox{Definici\'on~\ref{#1}}}
\newcommand{\corref}[1]{\mbox{Corolario~\ref{#1}}}
\newcommand{\lemref}[1]{\mbox{Lema~\ref{#1}}}
\newcommand{\propref}[1]{\mbox{Proposici\'on~\ref{#1}}}
\newcommand{\figref}[1]{\mbox{Figura~\ref{#1}}}
\newcommand{\tablref}[1]{\mbox{Tabla~\ref{#1}}}   
\newcommand{\eqref}[1]{\mbox{(\ref{#1})}}
\newcommand{\ineqref}[1]{\mbox{(\ref{#1})}}
\newcommand{\comref}[1]{\mbox{Comentario~\ref{#1}}}
\newcommand{\EE}{{I\!\! E}}
\newcommand{\PP}{{I\!\! Pr}}

% FIN LISTA DE MACROS PERSONALES

\begin{document}
% LOS DATOS IDENTIFICATORIOS DE LA CATEDRA TRANSCRITA VAN AQUI
% (modificar los parametros en invocacion de la siguiente macro:
%       primer parametro: No. de catedra transcrita
%       segundo parametro: fecha de catedra transcrita
%       tercer parametro: Nombre del transcriptor
\catedra{13}{8 de Octubre}{Gregorio Gonz\'alez}

% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI

\section{Ataques a RSA}

\subsection{Calcular el Exponente de Decripci\'on (Continuaci\'on)}

En la clase anterior se discuti\'o que un algoritmo que pudiese calcular
el exponente de decripci\'on de RSA podr\'{\i}a utilizarse como subrutina
para factorizar el m\'odulo de RSA. A continuaci\'on mostraremos
cu\'al es este algoritmo de factorizaci\'on.

La idea de este algoritmo es utilizar la subrutina para encontrar una
ra\'{\i}z cuadrada no trivial de $1$ m\'odulo $n$, $ n = pq $, lo cual ya
vimos que es equivalente a factorizar $n$.

Sea $A$ el algoritmo que toma la clave p\'ublica de RSA, $(e,n)$, donde
$e$
es el exponente de decripci\'on y $n=pq$, $p$ y $q$ primos, y entrega el
exponente de decripci\'on $d$, i.e.
$$
x^{ed} \equiv x \pmod n , \, \, \, \, \, \, \, \forall x \in Z\!\!\!
Z_{n} .
$$
A continuaci\'on describiremos un algoritmo probabilista que utiliza el
algoritmo $A$ como or\'aculo para factorizar $n$ con probabilidad mayor o
igual que $1/2$.  Luego, si este procedimiento se repite $m$ veces,
factorizaremos $n$ con probabilidad mayor o igual que $1-1/2^{m}$.

El algoritmo es el siguiente:

\begin{enumerate}
  \item Se elige $w \in \{1,\ldots,n-1\}$ al azar.
  \item $ x = \mcd w n $
  \item Si $1 < x < n$ parar, pues $x = p$ o $x = q$.
  \item $d = A((e,n))$.
  \item Calcular $s$ tal que $ed - 1 = 2^{s}r$, donde $r$ es impar.
  \item Calcular $v = w^{r} \pmod n.$
  \item Si $v \equiv 1 \pmod n$ parar, el algoritmo fracasa.
  \item Mientras $v \equiv\!\!\!\!\! / 1 \, \, \pmod n$ $\{v_{0} = v,  v
=
v^{2} \pmod n\}$.
  \item SI $v_{0}\equiv -1 \pmod n$ parar, fracas\'o el algoritmo.  En
caso contrario, ${\mcd {(v_{0}+1)} n = p}$ o $q$. 
\end {enumerate}

Analicemos brevemente el algoritmo.  Primero que nada, si tenemos la
suerte de elegir $w$ m\'ultiplo de $p$ o $q$, entonces podemos factorizar
$n$ inmediatamente (paso 2).  Si $w$ es primo relativo con $n$, entonces
calculamos $w^{r}$, $w^{2r}$, $w^{4r}$,\ldots, elevando al cuadrado
sucesivamente, hasta que:
$$
w^{2^{t}r} \equiv 1 \pmod n
$$
para alg\'un $t$. Como:
$$
ed - 1 \equiv 2^{s}r \equiv 0 \pmod \phi (n),
$$
sabemos (por el lema de Euler) que $w^{2^{s}r} \equiv 1 \pmod n$ (paso 5).
Luego, el ciclo
"mientras" se acaba en a lo m\'as $s$ iteraciones.  Al final de dicho
ciclo hemos encontrado un valor de $v_{0}$ tal que $v_{0}^{2} \equiv 1
\pmod n$ pero $v_{0}^{2} \equiv\!\!\!\!\! / 1 (mod n)$.  Si $v_{0}^{2}
\equiv -1 \pmod n$ el algoritmo fall\'o.  En caso contrario $v_{0}$ es
una
ra\'{\i}z no trivial de 1 m\'odulo $n$ y podemos factorizar $n$.

No probaremos que el algoritmo tiene \'exito con probabilidad al menos
$1/2$.  Para ver dicha demostraci\'on, referirse al libro
de Douglas R. Stinson\footnote{{\em``Cryptography, Theory and
Practice''\/}, CRC Press, 1995, p'agina 149.}.

\subsection{Informaci\'on Parcial}

El otro ataque que discutiremos se basa en informaci\'on parcial sobre el
texto plano que podr\'{\i}a "filtrarse" a trav\'es de una encripci\'on RSA.

Si un criptosistema permite encontrar informaci\'on parcial sobre el texto
plano encriptado, esto representa una debilidad en nuestro sistema, ya que
si se quisiera utilizar el criptosistema con alguna modificaci\'on se corre
el riesgo de perder toda seguridad.  Por ejemplo, si un sistema permite
hallar el tercer bit del texto plano encriptado, no podr\'{\i}amos usar el
sistema para enviar s\'olo dos mensajes, s\'{\i} y no, como un uno o un cero en
el tercer bit y el resto con bits aleatorios "para despistar".  En este
caso un criptosistema que era muy seguro pasa a ser in'util.  No siempre
es tan significativo lo que se puede ganar con un s\'olo bit, pero
definitivamente es un factor limitante al utilizar el criptosistema.  

Los dos ejemplos de informaci\'on parcial de RSA que consideraremos son:

\begin {enumerate}
 \item Dado $y=e_{k}(x)$, calcular $paridad(y)$, donde $paridad(y)$
entrega el bit menos significativo de $x$.
 \item Dado $y=e_{k}(x)$, calcular $mitad(y)$, donde $mitad(y)=0$ si
$0\leq x < n/2$ y $mitad(y)=1$ si $n/2 < x \leq n$.
\end {enumerate}
  
 Probaremos que, dada $e_{k}(\cdot)$ la funci\'on de encripci\'on de RSA,
cualquier algoritmo que calcule $paridad(y)$ o $mitad(y)$ puede
ser usado como or\'aculo para constru\'{\i}r un algoritmo que
obtenga el texto plano $x$.  Lo que esto significa es que, dado
un texto cifrado, calcular el bit menos significativo del texto
plano es polinomialmente equivalente a calcular el texto plano
completo.  Con ello probamos que no se puede obtener dicha informaci\'on
parcial (bajo el supuesto que RSA es seguro).

Primero que nada, probaremos que calcular $paridad(y)$ es polinomialmente
equivalente a calcular $mitad(y)$.  En efecto, se tiene que:

\begin{enumerate}
 \item $paridad(y) = mitad( y \cdot e_{k}(2^{-1}) \pmod n)$
 \item $mitad(y) = paridad( y \cdot e_{k}(2) \pmod n)$
\end{enumerate}

Probemos la segunda identidad.  
\begin{eqnarray*}
 paridad( y \cdot e_{k}(2) (mod n)) & = & paridad(e_{k}(x) \cdot
e_{k}(2))\\
                                    & = & paridad(e_{k}(2x\pmod n))\\
\end{eqnarray*}
Esto es porque RSA es multiplicativa, i.e. $e_{k}(x_{1})\cdot
e_{k}(x_{2}) = e_{k}(x_{1}\cdot x_{2} \pmod n)$.
Ahora bien, si $0\leq x < n/2$ entonces $0\leq 2x < n$, luego
$2x\pmod n$ es par y $paridad(e_{k}(2x\pmod n))=0$.
Si $n/2 < x \leq n$ entonces $n < 2x \leq 2n$, luego $2x\pmod n = 2x -
n$,
y como $n$ es impar y $2x$ par, $2x\pmod n$ es impar.  Entonces
$paridad(e_{k}(2x\pmod n))=1$.  Pero esto coincide con $mitad(y)$, luego
se tiene la igualdad.

La otra identidad se prueba de manera an\'aloga.  Es posible 
calcular $x = d_{k}(y)$, dado un algoritmo que calcule $mitad(y)$.
Observemos que:
\begin{eqnarray*}
 mitad( e_{k}(x) )=0 &\leftrightarrow& x \in [0,n/2)\\
 mitad( e_{k}(2x) )=0 &\leftrightarrow& x \in [0,n/4) \cup [n/2,3n/4)\\
 mitad( e_{k}(4x) )=0 &\leftrightarrow& x \in [0,n/8) \cup [n/4,3n/8) \cup
[n/2,5n/8) \cup [3n/4,7n/8)
\end{eqnarray*}
y as\'{\i} sucesivamente. Luego es posible encontrar $x$ mediante una
b\'usqueda binaria si podemos calcular $paridad(y)$ o $mitad(y)$.

\section{Otros Criptosistemas}

\subsection{Criptosistema de Rabin}

Ahora presentaremos el Criptosistema de Rabin, el cual es
computacionalmente seguro contra todo ataque de texto plano elegido bajo
el supuesto que es computacionalmente infactible factorizar n'umeros de la
forma $n=p\cdot q$, donde $p$ y $q$ son primos.

Sea $n$ el producto de dos primos distintos $p$ y $q$, con $p,q \equiv
3(mod 4)$.  Sea $ \plain = \cipher = Z\!\!\! Z_{n}$, y definamos
$$
\key = \{(n,p,q,B) : 0 \leq B \leq n-1\}.
$$
Para $K=(n,p,q,B)$ definimos 
$$
e_{K}(x) = x(x+B) \pmod n
$$
y 
$$
d_{K}(y) = \sqrt{\frac{B^{2}}{4}+y} - \frac{B}{2}.
$$
La clave p\'ublica es $(n,B)$, y $p$ y $q$ se mantienen secretos.

La funci\'on de encripci\'on no es inyectiva, as\'{\i} que la decripci\'on es
ambigua.  En efecto, si $w$ es una ra\'{\i}z cuadrada no trivial de $1$,
entonces para todo texto plano $x$ hay tres valores distintos que
producen el mismo texto cifrado, y son:
$$
x,\, -x -B,\, w\left(x+\frac{B}{2}\right)-\frac{B}{2},\,
-w\left(x+\frac{B}{2}\right)-\frac{B}{2}.
$$
Por ejemplo:
\begin{eqnarray*}
 e_{K}\left(w\left(x+\frac{B}{2}\right)-\frac{B}{2}\right) &=&
\left(w\left(x+\frac{B}{2}\right)-\frac{B}{2}\right)
\cdot\left(w\left(x+\frac{B}{2}\right)+\frac{B}{2}\right)\\
    &=& w^{2}\left(x+\frac{B}{2}\right)^{2}-\frac{B^{2}}{4}\\
    &=& x(x-B) \pmod n\\
    &=& e_{K}(x)
\end{eqnarray*}
En general, el receptor del mensaje no tiene forma de distinguir entre
estos
cuatro textos planos posibles, a menos que el texto plano contenga
suficiente redundancia como para eliminar tres de las cuatro
posibilidades.  

Para decriptar debemos resolver:
$$
x^{2}+Bx \equiv y \pmod n.
$$
o equivalentemente,
$$
x_{1}^{2} \equiv y + \frac{B^{2}}{4} \pmod n
$$
donde $x_{1} = x+\frac{B}{2}$.

Sea entonces $C=y+\frac{B^{2}}{4}$.  Observemos que $C$ es un residuo
cuadr\'atico si la encripci\'on se hizo correctamente.  Las soluciones de
la ecuaci\'on $x_{1}^{2} \equiv C \pmod n$ se pueden obtener mediante el
Teorema Chino del Resto a partir de las soluciones de las ecuaciones:
\begin{eqnarray*}
 x_{1}^{2} &\equiv& C \pmod p\\
 x_{1}^{2} &\equiv& C \pmod q
\end{eqnarray*}
Cada una de estas ecuaciones tiene dos ra\'{\i}ces.  Estas se pueden combinar
para obtener las cuatro soluciones de la ecuaci\'on original (por el TCR).
Por el criterio de Euler sabemos que si se encript\'o correctamente $C$ es
un residuo cuadr\'atico m\'odulo $p$ y m\'odulo $q$.  Pero esto no basta
para poder resolver las ecuaciones.  En realidad el elemento clave para
esto es el hecho que $p \equiv 3 \pmod 4$ y $q \equiv 3 \pmod 4$, pues
en
este caso tenemos un algoritmo determinista polinomial que nos permite
calcular las
ra\'{\i}ces cuadradas de residuos cuadr\'aticos m\'odulo $p$ o $q$.  Las
ra\'{\i}ces de la primera ecuaci\'on vienen dadas por:
$\pm C^{\frac{p+1}{4}} (mod p)$.  En efecto:
\begin{eqnarray*}
\left(\pm C^{\frac{p+1}{4}} \right)^{2} & \equiv & C^{\frac{p+1}{2}} \pmod
p\\
             & \equiv & C^{\frac{p-1}{2}}\cdot C \pmod p\\
             & \equiv & C \pmod p.
\end{eqnarray*}
esto debido a que C es residuo cuadr\'atico, luego por el criterio de
Euler se tiene que: $C^{\frac{p-1}{2}} \equiv 1 \pmod p$.
An\'alogamente, las ra\'{\i}ces de la segunda ecuaci\'on son:
$\pm C^{\frac{q+1}{4}} \pmod q.$
Teniendo las soluciones de ambas ecuaciones se obtienen directamente las
cuatro ra\'{\i}ces de $C$ m\'odulo $n$ usando el Teorema Chino del Resto.

Cabe hacer dos observaciones:

\begin{enumerate}
 \item El adversario no sabe cu\'al de las cuatro es la decripci\'on
correcta, pero el receptor tampoco.  Esto se resuelve acordando ciertas
reglas de redundancia en el mensaje (i.e. el mensaje se transmite como dos
copias concatenadas, el tercer bit se repite tres veces, etc.) para poder
distinguir cu\'al de las cuatro ra\'{\i}ces corresponde al mensaje original.
 \item Es interesante el hecho que para el caso en que un primo $p$ es
congruente a $1$ m\'odulo $4$ no se conoce ning\'un algoritmo polinomial
determinista para determinar las ra\'{\i}ces cuadradas de residuos
cuadr\'aticos m\'odulo $p$, i.e. el hecho que $p\equiv 3\pmod 4$ y
$q\equiv 3\pmod 4$ es vital para el algoritmo de decripci\'on (Sin
embargo, se conoce un algoritmo probabilista de tiempo polinomial que
cumple este prop\'osito).
\end{enumerate}

\end{document}


