\documentstyle[12pt]{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{14}{9 de Octubre}{Rodrigo Gonz\'alez del Barrio}

% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI

\section{Criptosistema de Rabin}

Ahora probaremos que el criptosistema de Rabin es computacionalmente seguro.
Suponemos entonces que si existe un algoritmo $A$ que conociendo $n$ y $B$
y dada una entrada $y \in \cipher$ entrega un $x \in \plain$ tal que
$e_K(x)=y$.

El siguiente algoritmo toma como entrada $n$ y $B$ y utiliza $A$ como subrutina y factoriza el m\'odulo n
con probabilidad de a lo menos $\frac{1}{2}$.

\begin{center}
   \makebox[0in]{\framebox[3.5in][l]{
      \vbox{
      \begin{enumerate}
      \item Eligir $r \in \{1,\ldots,n-1\}$ al azar.
      \item Calcular $y=r^2-\frac{B^2}{4}$.
      \item Obtener $x=A(y)$.
      \item Calcular $x_1=x+\frac{B}{2}$.
      \item Si $x_1 \equiv \pm r (\bmod \: n)$\\
            \hspace{15mm}   parar(fracaso)\\
      en caso contrario \\
            \hspace{15mm}   $\mcd(x_1+r,n) = p \: o \: q$\\
      \end{enumerate}
      }
   }}
\end{center}

Existen varios puntos a explicar en este algoritmo. Primero observemos que:
$$e_K(r-\frac{B}{2})=y$$
Luego en el paso 3, $A$ retorna un valor $x \in \plain$ tal que:
$$x_1^2 \equiv (x+\frac{B}{2})^2 \equiv x(x+B)+\frac{B^2}{4} \equiv
y+\frac{B^2}{4} \equiv r^2 (\bmod \: n)$$

De esta manera obtenemos que:

$$x_1 \equiv \pm r (\bmod \: n) \:\:\: o \:\:\: x_1 \equiv \pm wr
(\bmod \: n).$$

donde $w$ es una ra\'{\i}z cuadrada no trivial de 1 modulo n. Si $x_1 \:
{/\!\!\!\!\! \equiv} \pm 1 (\bmod \: n)$ entonces como $n | (x_1+r)(x_1-r)$
sigue que, al calcular $\mcd(x_1+r,n)$ se obtiene $p$ o $q$.

Para determinar la probabilidad de \'exito de quebrar el criptosistema
de Rabin, defin\nolinebreak imos en $\modulo_n \verb'\' \{0\}$ la
relaci\'on de equivalencia:

$$r_1 \sim r_2 \Leftrightarrow r_1^2 \equiv r_2^2 (\bmod \: n).$$

Se verifica f\'acilmente que $\sim$ es relaci\'on de equivalencia.
Notar que la clase de equiv\nolinebreak alencia de un elemento $r$
tiene cardinal 4, en efecto:

$$[r] = \{\pm r , \pm wr (\bmod \: n )\}.$$

Pero todo elemento de $[r]$ genera el mismo $y \in \cipher$ para el
paso 2, y luego da lugar al mismo $x_1$ en el paso 4. Luego con
probabilidad de a lo menos $\frac{1}{2}$ en el paso 1 se eligio un
t\'ermino tal que $x_1 \: {/\!\!\!\!\! \equiv} \pm r (\bmod \: n)$, luego
el Criptosistema de Rabin es computacionalmente seguro bajo ataques
de texto plano elegido, bajo el supuesto que no existe un algoritmo
probabilistico eficiente que permita factorizar n\'umeros de la forma
$n=p \cdot q$, $p$ y $q$ primos.

Cabe hacer notar que bajo ataques de texto cifrado conocido el
Criptosistema de Rabin es inseguro, dado que el algoritmo $A$ es
reemplazado por el algoritmo de decripci\'on del Criptosistema
de Rabin conocido por la persona que realiza el ataque.

\newpage
\section{Criptosistema de ElGamal}

El Criptosistema de ElGamal se basa en la premisa que el problema de
Logaritmos Discretos es computacionalment infactible.
A continuaci\'on se plantea el problema de Logaritmos Discretos en el
cuerpo finito $\modulo_p$, donde $p$ es un primo, esto es:

\begin{center}
   \makebox[6in]{\framebox[4.5in]{
      \vbox{
\hbox{{\bf Entrada:}  $I=(p,\alpha,\beta)$, donde $p$ es primo,}
\hbox{            \hspace{13mm}   $\alpha \in \modulo_p$ es un generador, y $\beta \in \modulo_p^*$.}
\hbox{{\bf Salida:}  Encontrar el \'unico $i$, $0 \leq i \leq p-2$, tal que}
\hbox{            \hspace{33mm}   $\alpha^i \equiv \beta (\bmod \: p)$.}
\hbox{            \hspace{13mm}   Denotaremos $i=log_{\alpha}\beta$.}
      }
}}
\end{center}

En el problema de Logaritmos Discretos en $\modulo_P$ su dificultad
radica en como se a elegido p. En particular no se conoce un algoritmo
determinista de tiempo polinomial para el c\'alculo de Logaritmo Discreto.
Para frustrar ataques conocidos, $p$ debe ser de al menos 150 d\'{\i}gitos,
y $p-1$ debe tener a lo menos un factor primo "grande".

El Criptosistema de Elgamal es el siguiente:

\begin{center}
   \makebox[6in]{\framebox[5.5in]{
      \vbox{
\hbox{Sea $p$ un primo tal que el problema de Logaritmos Discretos en
      $\modulo_p$}
\hbox{es computacionalmente infactible. Sea $\plain = \modulo_p^*$, $\cipher=\modulo_p^* \times \modulo_p^*$,
      y}
\hbox{$\key=\{(p,\alpha,i,\beta): \: \alpha \in \modulo_p^*$ un generador,
      $\beta \equiv \alpha^i(\bmod \: p)\}.$}
\hbox{Los valores $p$, $\alpha$ y $\beta$ son p\'ublicos, e $i$ es secreto.}
\hbox{Para $K=(p,\alpha,i,\beta)$, y para un n\'umero secreto aleatorio}
\hbox{$j \in \{0,\ldots,p-2\}$, sea:}
\hbox{\hspace{13mm}   $e_K(x,j)=(y_1,y_2)$}
\hbox{donde}
\hbox{\hspace{13mm}   $y_1=\alpha^j (\bmod \: p)$}
\hbox{y}
\hbox{\hspace{13mm}   $y_2=x \beta^j (\bmod \: p).$}
\hbox{Para $y_1,y_2 \in \modulo_p^*$, sea:}
\hbox{\hspace{13mm}   $d_K(y_1,y_2)=y_2(y_1^i)^{-1} (\bmod \: p).$}
      }
}}
\end{center}

Observemos que:
$$d_K(e_K(x,j))=d_K(\alpha^j (\bmod \: p), x \beta^j (\bmod \: p))=
x \beta^j [(\alpha^j)^i]^{-1}(\bmod \: p) = x \beta^j [\beta^j]^{-1}
(\bmod \: p)$$

El Criptosistema de ElGamal es no determinista, puesto que el texto cifrado
depende a la vez de el texto plano $x$ y del valor aleatorio $j$ elegido.
As\'{\i}, muchos textos cifrados distintos, pueden obtenerse de la encripci\'on
de un mismo texto plano.

Informalmente, se puede decir que el Criptosistema de ElGamal, trabaja
de la sigu\nolinebreak iente manera. Un texto plano $x$ es enmascarado multiplicando
por $\beta^j$, produciendo $y_2$. El valor de $\alpha^j$ es tambi\'en
transmitido como parte del texto cifrado. Bob, quien conoce el exponente
$i$, puede calcular $\beta^j$ de $\alpha^j$. Entonces el puede remover la
m\'ascara dividiendo $y_2$ por $\beta^j$ obtiendo $x$.


\subsection{Algoritmos para el problema de Logaritmo Discreto}

En lo que sigue se asume que $p$ es primo y $\alpha$ es un generador de
$\modulo_p$, ambos fijos.

Claramente, el problema de Logaritmo Discreto puede resolverse mediante
b\'usqueda exhaustiva en O(p) de tiempo y O(1) de espacio (se omitiran los
factores logaritmicos en $p$ de los ordenes), i.e., calcular uno por
uno hasta encontrarlo. Precalculando todos los posibles $\alpha^i$,
y ordenando los pares $(i,\alpha^i (\bmod \: p))$ con respecto a la
segunda coordenada, se puede resolver el problema de Logaritmo Discreto
en O(1) de tiempo con O(p) de precomputaci\'on y O(p) de memoria.

\subsubsection{Algoritmo de Shank}

El algoritmo de Shank logra un compromiso entre los requerimientos de
espacio y tiempo mencionado en el punto anterior. Sea
$m\in \{1,\ldots,p\}$ y $n=\lceil\frac{\sqrt{p-1}}{m}\rceil$,
luego el algoritmo de Shank toma como entrada $p$, $\alpha$ y
$\beta$ y ejecuta los siguientes pasos:

\begin{center}
   \makebox[6in]{\framebox[5in][l]{
      \vbox{
      \begin{enumerate}
\item Calcular $\alpha^{nj} (\bmod \: p)$, $0\leq j \leq m-1$
\item Ordenar los $m$ pares $(j,\alpha^{nj} (\bmod \: p))$ con
      respecto a su\\
segunda coordenada, obteniendo una lista $L_1$
\item Calcular $\beta\alpha^{-i} (\bmod \: p)$, $0\leq i \leq n-1$
\item Ordenar los $n$ pares $(i,\beta\alpha^{-i} (\bmod \: p))$
      con respecto\\
su segunda coordenada, obteniendo una lista $L_2$
\item Encontrar un par $(j,y) \in L_1$ y un par $(i,y) \in L_2$\\
(i.e., un par que tenga su segunda coordenada id\'entica)
\item Definir $log_{\alpha}\beta=nj+i (\bmod \: (p-1))$.
      \end{enumerate}
}
}}
\end{center}
\newpage

Los pasos 1 y 2 pueden ser precomputados. Adem\'as, se observa
que si $(j,y) \in L_1$ y $(i,y) \in L_2$, entonces

$$\alpha^{jn}=y=\beta \alpha^{-i}$$

as\'{\i}

$$\alpha^{jn+i}=\beta$$

como se quer\'{\i}a. Por otro lado, cualquier $\beta$, se puede
escribir como:

$$log_{\alpha}\beta= nj+i.$$
donde  $0\leq j,i \leq n-1$, por lo tanto la b\'usqueda en el paso 5 ser\'a
exitosa (puede ser hecha con una pasada simultanea a trav\'es de cada una de
las dos listas $L_1$ y $L_2$).

Con este algoritmo se resuelve el problema de Logaritmo
Discreto en O($m$) de precomputaci\'on, O($n$) de tiempo y de
O($\max\{n,m\})$ de memoria (omitiendo factores logaritmicos
de los ordenes).

Si el tiempo y el espacio nos "cuesta" lo mismo, se obtiene que, eligiendo
$m=\lceil\sqrt{p-1}\rceil$,  el algoritmo de Shank corre en
O($m$) tanto en tiempo como en memoria. Con esto se logra que el orden
del algoritmo de Shank sea m\'{\i}nimo.

\subsubsection{Algoritmo de Pohlig-Hellman}

Supongamos que:

$$p-1=\prod_{i=1}^{k}p_i^{c_i},$$

donde los $p_i$ son primos distintos. El valor de $a=log_{\alpha}\beta$
es \'unico m\'odulo \nolinebreak $p-1$. Si calculamos $a (\bmod\:p_i^{c_i})$ para cada $i$
con $i\in \{1,\ldots,k\}$, luego podemos calcular $a (\bmod\:(p-1))$ mediante
el teorema Chino del resto, sea $q$ primo,$p-1 \equiv 0 (\bmod \: q^c)$ y
\nolinebreak $p-1{/\!\!\!\!\! \equiv} 0 (\bmod \: q^{c+1})$.

Ahora calculamos $x=a  (\bmod \: q^c)$, donde $x\in \{0,\ldots,q^c-1\}$.
se puede expresar $x$ como sigue:
$$x=\sum_{i=0}^{c-1}a_iq^i$$
donde $a_i\in \{0,\ldots,q-1\}$ para $i\in \{0,\ldots,c-1\}$. Adem\'as
$a$ se puede expresar como $a=x+q^cs$ para alg\'un entero $s$.

El primer paso del algoritmo consiste en calcular $a_0$. Para esto
se observa que:
$$\beta^{(p-1)/q} \equiv  \alpha^{(p-1)a_0/q} (\bmod \: p).
\footnote{Douglas R. Stinson,{\it "Cryptography, Theory and
Practice"},1995,pp. 167}$$

Por lo tanto, primero calculamos $\beta^{(p-1)/q} (\bmod \:p)$.
Si $\beta^{(p-1)/q} \equiv 1 (\bmod \:p)$, entonces $a_0=0$. De
otro modo calculamos en forma sucesiva:
$$\gamma=\alpha^{(p-1)/q} (\bmod \:p), \gamma^2 (\bmod \:p),\ldots,$$
hasta que $\gamma^i \equiv \beta^{(p-1)/q} (\bmod \:p)$ para alg\'un $i$,
luego $a_0=i$

Ahora, si $c=1$, listo. Si $c>1$, debemos calcular $a_1$, se define
$\beta_1=\beta \alpha^{-a_0}$ y denotamos $x_1=log_{\alpha}\beta_1
(\bmod \: q^c)$. Luego
$$x_1=\sum_{i=1}^{c-1}a_iq^i$$
Por lo tanto, se sigue:
$$\beta_1^{(p-1)/q^2} \equiv  \alpha^{(p-1)a_1/q} (\bmod \: p).$$
As\'{\i}, calculamos $\beta_1^{(p-1)/q^2} (\bmod \:p)$, y encontramos
$i$ tal que $\gamma^i \equiv \beta_1^{(p-1)/q^2} (\bmod \:p)$, luego
$a_1=i$.

Si c=2, terminamos. Si $c > 2$ repetimos el proceso para obtener $a_2,
\ldots,a_{c-1}.$

Luego con los $a_0,\ldots,a_{c-1}.$ calculamos:
$$log_\alpha\beta (\bmod \: q^c) = \sum_{i=0}^{c-1}a_iq^i$$

El orden del algoritmo Pohlig-Hellman es de O($q$) tiempo,
donde q es el mayor factor primo de $p-1$, luego el factor $q$
debe ser "grande", al seleccionar el primo $p$.
\newpage
\subsubsection{Algoritmo de C\'alculo de Indices}

Este algoritmo usa una base de factores ${\cal B}$, sea ${\cal B}=
\{p_1,p_2,\ldots,p_B\}$. Primero se precomputan los logaritmos de los $B$
primos en la base de factores. Segundo calcular el Logaritmos Discreto
de un elemento de ${\cal B}$, usando los logaritmos discretos
calculados, en el punto anterior.

En la precomputaci\'on, se construyen $C=B+10$ congruencias m\'odulo $p$
como sigue:
$$\alpha^{x_j} \equiv p_1^{a_{1j}}p_2^{a_{2j}}\cdots p_B^{a_{Bj}}
(\bmod\: p),$$
$j\in \{1,\ldots,C\}$. Que es equivalente a escribir:
$$x_j \equiv a_{1j}log_\alpha p_1+\cdots+a_{Bj}log_\alpha p_B (\bmod\: (p-1)),$$
$j\in \{1,\ldots,C\}$. Dadas C congruencias en los B $log_\alpha p_i$
$i\in \{1,\ldots,B\}$, esperamos que exista una \'unica soluci\'on m\'odulo
$p-1$. En este caso, calculamos el logaritmo de los elementos de la base de
factores.

Ahora bien, se calcula el logaritmo  $log_{\alpha}\beta$ mediante un
algoritmo probabilistico tipo Las Vegas (se ver\'a m\'as adelante,
este tipo de algoritmo).

Se elige un entero $s$ ($s\in \{1,\ldots,p-2\}$) y se calcula
$\gamma=\beta\alpha^s (\bmod \: p)$. Si $\gamma$ se factoriza
en factores de la base ${\cal B}$ se obtiene la congruencia:
$$\beta\alpha^s \equiv p_1^{c_1}p_2^{c_2}\cdots p_B^{c_B} (\bmod\: p).$$
Que es equivalente a:
$$log_\alpha\beta+s \equiv c_1 log_\alpha p_1+\cdots+c_B log_\alpha
p_B (\bmod\: (p-1)).$$
Esta \'ultima congruencia es f\'acil de resolver para $log_\alpha\beta$
\end{document}


