\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}}}

% 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{8}{28 de Agosto}{Jens Hardings}


% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI

\section{Criptograf\'{\i}a Moderna o de Clave P\'ublica}
%
En los criptosistemas vistos hasta ahora, Alicia
y Roberto eligen la clave $K$ en secreto, comunic\'andola a trav\'es de
un canal seguro. Esta clave permite generar una regla de encripci\'on
$e_{K}$ y una regla de decripci\'on $d_{K}$. En los criptosistemas que
hemos estudiado, $d_{K}$ es f\'acilmente derivable al conocer $e_{K}$.
Los criptosistemas de este tipo se conocen con el nombre de criptosistemas de
clave privada.

Evidentemente, al usar este tipo de sistemas se depende de la existencia previa
(aunque sea temporal) de un canal seguro, en el cual Alicia y Roberto se
comunican la clave, para luego poder mandar informaci\'on a trav\'es de otro
canal inseguro.

En cambio, la criptograf\'{\i}a de clave p\'ublica se basa en la idea que
quiz\'as es posible encontrar un criptosistema en que es computacionalmente
infactible determinar $d_{K}$ dado $e_{K}$. En ese caso, $e_{K}$
puede ser publicada por Roberto, y Alicia o cualquier otro individuo puede
enviar mensajes encriptados a Roberto usando $e_{K}$ y este \'ultimo ser\'a
la \'unica persona capaz de decriptar el texto cifrado usando su regla de
decripci\'on secreta $d_{K}$.

La idea de la criptograf\'{\i}a p\'ublica se debe a Diffie y Hellman [1976],
los cuales no dieron un ejemplo de criptosistema de este tipo. Ellos
propusieron que pod\'{\i}a construirse un criptosistema de este tipo si era
posible encontrar una funci\'on ``f\'acil'' de calcular, pero ``dif\'{\i}cil''
de invertir. La primera realizaci\'on de criptosistema p\'ublico se debe a
Rivest, Shamir y Adleman
[1977].

Es importante notar que un criptosistema de clave p\'ublica no podr\'a jam\'as
ser un criptosistema perfectamente secreto. En efecto, conocido el texto
cifrado, un adversario puede encriptar todos los textos planos y determinar
cual es el \'unico tal que $y=e_{K}(x)$, dado que el adversario conoce $e_{K}$.
Luego, el texto cifrado enviado permite identificar completamente el texto
plano. Por lo tanto, la discusi\'on de la seguridad de los criptosistemas de
clave p\'ublica necesariamente debe hacerse en el \'ambito de la seguridad
computacional, i.e. la dificultad computacional de calcular $d_{K}$ conociendo
$e_{K}$.

\section{Funciones de sentido \'unico y de puerta secreta}

La noci\'on detr\'as de las funciones de sentido \'unico es que se tiene
una funci\'on \\ $f:\plain~\longrightarrow~\cipher$ tal que

\begin{itemize}

\item $f$ es f\'acil de calcular
\item $f^{-1}$ no es tan f\'acil de calcular

\end{itemize}

Esta abstracci\'on es \'util al hablar de criptosistemas de clave p\'ublica.
M\'as adelante formalizamos la noci\'on de funciones de un s\'olo sentido.

No se conoce la existencia de estas funciones, sin embargo existen conjeturas
acerca de posibles candidatos:

\begin{itemize}

\item Factorizaci\'on

$f:N \times N \rightarrow N$

$(m,n) \mapsto m \cdot n$

Si el dominio de esta funci\'on se restringe a los pares $(m,n)$ tales que $m$
y $n$ son primos, $f$ tiene inversa y se supone que es dif\'{\i}cil de
calcular.
La raz\'on por la cual se considera ``dif\'{\i}cil'' de invertir esta
funci\'on es que, despu\'es de mucho tiempo de investigaci\'on, el algoritmo
conocido m\'as eficiente para factorizar (y por ende invertir $f$) se demora
$e^{(1,92+o(1))(lg(n))^{\frac{1}{3}}(lg(lg(n)))^{\frac{2}{3}}}$

\item Logaritmo Discreto

Sea $p$ un primo, $\modulo_{p}^{*} = \modulo_{p} \setminus \{0\}$ es un
grupo multiplicativo y es c\'{\i}clico, i.e.
existe $g$ en $\modulo_{p}^{*}$ tal que
$\modulo_{p}^{*} = \set{g^{i}}{i \in \{1,2,\cdots ,p-1\}}$. Sea
$f(p,g,i) = (g^{i} \bmod p,q,g)$, donde $p$ es primo, $i$ es un entero no
negativo y $g$ es generador de $\modulo_{p}^{*}$.

Se presume que $f(\cdot,\cdot,\cdot)$ es de sentido \'unico, ya que el mejor
algoritmo conocido para calcular la inversa (el \emph{logaritmo discreto})
toma $O(e^{(lg(p)\cdot lg(lg(p)))^{\frac{1}{2}}})$

\underline{Observaci\'on:} $f(\cdot,\cdot,\cdot)$ se puede calcular
eficientemente por el m\'etodo de los cuadrados iterados que veremos m\'as
adelante.

\end{itemize}

Pero la criptograf\'{\i}a de clave p\'ublica requiere m\'as que una funci\'on
de un sentido. La regla de encripci\'on $e_{K}$ debe ser f\'acil de invertir
para quien la publica.

Se requieren funciones de un sentido con puerta secreta, i.e. tales que cierta
informaci\'on (que no se publica) las hagan f\'aciles de invertir.

\section{RSA}

\emph{RSA} es el criptosistema de clave p\'ublica ideado por Rivest, Shamir
y Adleman. En este sistema, $\plain = \cipher = \modulo_{n}$, $n = p \cdot q$
donde $p$ y $q$ son primos impares. Adem\'as $\key =
\set{(p,q,a,b)}{n=p \cdot q$ y $ab \equiv 1(\bmod \varphi (n))}$,
donde $\varphi (n)$ es la funci\'on phi de Euler, y
\begin{eqnarray*}
e_{K} & = & x^{a} \bmod n\\
d_{K} & = & y^{b} \bmod n.
\end{eqnarray*}
La clave p\'ublica es $(n,a)$.

El sistema se basa en la suposici\'on que $f(n,a,x)=(x^{a} \bmod n,n,a)$
es una funci\'on de sentido \'unico.

Adem\'as, la puerta secreta que permite decriptar de manera ``f\'acil'' es el
conocimiento de $p$ y $q$, y luego de $\varphi (n) = (p-1)(q-1)$.
Por lo tanto, si $a$ es primo relativo a $\varphi (n)$, podemos calcular el
exponente de decripci\'on $b$ por el algoritmo de Euclides.
Observar que para que $d_{K}(e_{K}(x)) = x$, se debe tener que
$x = x^{ab} \bmod n, \forall x \in \modulo_{n}$ si $ab \equiv 1 ( \bmod
\varphi(n))$. No estamos en condiciones de probar esto \'ultimo. Para ello
requerimos ahondar en teor\'{\i}a de n\'umeros.

\section{M\'as de teor\'{\i}a de n\'umeros}

\begin{theorem}{El peque\~no teorema de Fermat}

Sea $p$ un primo. Entonces, para todo entero $a$, $a^{p} \equiv a (\bmod p)$
y si $a$ no es divisible por $p$, entonces $a^{p-1} \equiv 1 (\bmod p)$.
\end{theorem}

\begin{proof}
Sea $a$ divisible por $p$. Entonces $a \equiv 0 (\bmod p)$ y $a^{p} \equiv
0(\bmod p)$ por lo que $a^{p} \equiv a(\bmod p)$.

Si $p$ no divide a  $a$ tenemos que $|\set{ia \bmod p}{i \in \{1,...,p-1\}}|
= p-1$. En efecto, si $i$ es distinto de $j$ y $ia \equiv ja (\bmod p)$,
entonces $p$ divide a $a(i-j)$.
Como $p$ es primo, $p$ no divide a $a$, y $p$ es primo relativo con $a$,
tenemos que $p \mid (i-j)$, lo cual contradice el supuesto anterior.

Luego, el conjunto $\set{ia \bmod p}{i \in \{1,...,p-1\}} = \modulo_{p}^{*}$
\begin{eqnarray*}
 \prod_{i=1}^{p-1} i & \equiv & \prod_{i=1}^{p-1}
 (ia)(\bmod p)\\
 a^{p-1} \prod_{i=1}^{p-1} i & \equiv & \prod_{i=1}^{p-1} i
\end{eqnarray*}
Como $\prod_{i=1}^{p-1} i$ es primo relativo con $p$, se puede cancelar en
ambos lados y obtenemos $a^{p-1} \equiv 1 (\bmod p)$

Inmediatamente se ve que $a^{p} \equiv a (\bmod p)$
\end{proof}

\begin{corollary}
Si $a$ no es divisible por $p$ y $n \equiv m(\bmod (p-1))$, entonces\\
$a^{n} \equiv a^{m}(\bmod p)$.
\end{corollary}

\begin{proof}
Si $n \equiv m (\bmod p-1)$, entonces se cumple que existe un entero $b$ tal
que $n = m + b(p-1)$. Por lo tanto, $a^{n} = a^{m+b(p-1)} = a^{m} \cdot
a^{b(p-1)}$ y del teorema anterior se tiene que $a^{b(p-1)} \equiv
{(a^{p-1})}^{b} \equiv 1(\bmod p)$, y entonces $a^{n} \equiv a^{m}(\bmod p)$.
\end{proof}

\begin{theorem}{Euler}

Si $a$ es primo relativo con $n$, entonces $a^{\varphi(n)} \equiv 1(\bmod n)$.
\end{theorem}

\begin{proof}
Primero se demostrar\'a el teorema en el caso de que $n$ es una potencia de
un primo $p$, o sea que $n = p^{\alpha}$. Para ello usaremos inducci\'on
sobre $\alpha$.
El caso $\alpha = 1$ ya se demostr\'o anteriormente (peque\~no Teorema de
Fermat). Suponiendo que $\alpha \ge 2$, y que se cumple el teorema para
$n = p^{\alpha-1}$, entonces $a^{p^{\alpha - 1}-p^{\alpha - 2}} = 1 + p^{\alpha
- 1}b$ para alg\'un entero $b$. Usando el hecho de que los coeficientes
binomiales de $(1+x)^{p}$ son divisibles por $p$, exceptuando $1$ y $x$ en
los extremos\footnote{Al expandir, se ve que los t\'erminos son de la forma
$\big(\stackrel{p}{i}\big)x^{i}$, con $1 < i < p$, los cuales son claramente
divisibles por $p$.}, se puede elevar a $p$ a ambos lados y se llega a
$a^{p^{\alpha}-p^{\alpha - 1}} = 1 + S$, donde $S$ es una suma de t\'erminos
todos divisibles por $p$. Entonces se tiene que $a^{\varphi(p^{\alpha})} - 1$
es divisible por $p$, dado que como hemos visto anterioemante,
$\varphi(p^{\alpha}) = p^{\alpha} - p^{\alpha - 1}$.

Finalmente, como $\varphi$ es multiplicativa, es claro que $a^{\varphi(n)}
\equiv 1 (\bmod p^{\alpha})$.

En el caso general, existen $m$ distintos $p_{i}$ (todos primos) y $e_{i}$,
$m$ un natural, tales que
\begin{eqnarray*}
n & = & \prod_{i = 1}^{m}p_{i}^{e_{i}} \\
\varphi(n) & = & \prod_{i = 1}^{m}\varphi(p_{i}^{e_{i}})
\end{eqnarray*}
Definamos
\[ b_{j} = \prod_{i = 1}^{j}p_{i}^{e_{i}} \ , con \ j = 1,...,m .\]
Como $b_{j-1}$ es primo relativo con $p_{j}^{e_{j}}$, se puede ocupar la parte
anterior de la demostraci\'on para cada $b_{j}$, entonces:
\begin{eqnarray*}
a^{\varphi(b_{1})} = & a^{\varphi(p_{1}^{e_{1}})} & \equiv 1 (\bmod p_{1}^{e_{1}})\\
& \vdots &\\
a^{\varphi(b_{j})} = & (a^{\varphi(b_{j-1})})^{\varphi(p_{j}^{e_{j}})} & \equiv 1 (\bmod p_{j}^{e_{j}}),
\end{eqnarray*}
o sea que $a^{\varphi(n)} \equiv 1 (\bmod p_{j}^{e_{j}})$ para $j = 1,...,m$.
Entonces, podemos afirmar que
\[ a^{\varphi(n)} \equiv 1 (\bmod \prod_{i = 1}^{n} p_{i}^{e_{i}}) \]
y se concluye que $a^{\varphi(n)} \equiv 1 (\bmod n)$.
\end{proof}

\begin{corollary}
Si $a$ es primo relativo con $n$, y $m \equiv m'(\bmod \varphi(n))$, entonces\\
$a^{m} \equiv a^{n}(\bmod n)$.
\end{corollary}

\begin{proof}
Del teorema anterior tenemos que $ a^{\varphi(n)} \equiv 1(\bmod n)$.
Adem\'as, $m \equiv n(\bmod \varphi(n))$, o sea que $m = t\varphi(n)+n$,
para alg\'un entero $t$.
Entonces, $a^{m} \equiv a^{t\varphi(n)+n} \equiv (a^{\varphi(n)})^{t}\cdot
a^{n}\equiv a^{n} (\bmod n)$.
\end{proof}

\begin{theorem}{Teorema chino del resto}

Supongamos que queremos resolver
\begin{eqnarray*}
x & \equiv & a_{1}(\bmod m_{1})\\
x & \equiv & a_{2}(\bmod m_{2})\\
x & \equiv & a_{3}(\bmod m_{3})\\
& \vdots & \\
x & \equiv & a_{r}(\bmod m_{r})
\end{eqnarray*}
donde $m_{i}$ y $m_{j}$ son primos relativos si $i \ne j$.

Entonces, existe una soluci\'on $x$ que satisface todas las ecuaciones
anteriores y cualquiera dos soluciones del sistema anterior son congruentes
m\'odulo $M \equiv m_{1} \cdot m_{2} \cdot \dots \cdot m_{r}$
\end{theorem}

\begin{proof}
\underline{Unicidad}: Sean $x$ y $x'$ dos soluciones, luego
\begin{eqnarray*}
x & \equiv & a_{i}(\bmod m_{i})\\
x' & \equiv & a_{i}(\bmod m_{i})\\
\end{eqnarray*}
donde $i = 1 \dots r$. Luego $(x-x') \equiv 0(\bmod m_{i})$,
donde $i = 1 \dots r$.  Y como $m_{i}$ es primo relativo con $m_{j}$ si
$i \ne j$, sigue que $x \equiv x' (\bmod M)$

\underline{Existencia}: Sea $N_{i} = \frac{M}{m_{i}}$, luego $N_{i}$ y
$m_{i}$ son primos relativos.

Por lo tanto existe un $M_{i}$ tal que $N_{i}M_{i} \equiv 1 (\bmod m_{i})$.
Luego \[x = \sum_{i=1}^{r} a_{i}N_{i}M_{i} \bmod M .\]
Se tiene que $x$ es soluci\'on del sistema de congruencias, puesto que
\begin{eqnarray*}
 x & \equiv & \sum_{j=1}^{r} a_{j}N_{j}M_{j} (\bmod m_{i})\\
   & \equiv & a_{i}N_{i}M_{i} (\bmod m_{i})\\
   & \equiv & a_{i} (\bmod m_{i})\\
\end{eqnarray*}
\end{proof}

\underline{Obs:} Adem\'as de verificar el teorema, la demostraci\'on reci\'en
vista da un algoritmo eficiente para encontrar las soluciones del sistema de
congruencias presentado.

Con esto ya tenemos los elementos necesarios para probar que $d_{K}
(e_{K}(x))=xi$ para cualquier $x \in \plain$ en RSA.

\end{document}



