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

\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{\nodiv}{\!\!\not|}

\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{\mypmod}[1]{\,(\mbox{\rm mod}\,#1)}

\newcommand{\chapref}[1]{\mbox{Cap\'{\i}tulo~\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
\catedra{2}{7 de Agosto}{Marcos Kiwi}

% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI

\section{Cifrados de Chorro}
%
En los criptosistemas que hemos estudiado hasta ahora, hemos encriptado
  el texto plano utilizando la misma clave $K$ de forma que
  el texto cifrado $y=y_{1}y_{2}\ldots= e_{K}(x_{1})e_{K}(x_{2})\ldots$.
Los criptosistemas que se obtienen utilizando esta forma de encriptar
  se conocen como \emph{cifrados en bloque}.\footnote{\ {\it Block chiphers}.}
En este curso nos remitiremos principalmente al estudio de este tipo
  de criptosistemas. 
Sin embargo hay otras alternativas.
Por completitud discutiremos una de ellas en esta secci\'on, los 
  \emph{cifrados de chorro}.\footnote{\ {\it Stream ciphers}.}

La idea b\'asica de este tipo de cifrados es generar una secuencia de 
  claves $K=z_{1}z_{2}\ldots$, y usarla para encriptar el texto plano
  $x=x_{1}x_{2}\ldots$, como sigue:
\begin{eqnarray*}
y \; = \; y_{1}y_{2}\ldots & = & e_{z_1}(x_{1})e_{z_2}(x_{2})\ldots
\end{eqnarray*}
Formalmente,
\begin{definition}
Un cifrado de chorro es una tupla $(\plain, \cipher, \key, {\cal L}, 
  {\cal F}, \encrip, \decrip)$
  tal que:
\begin{itemize}
\item $\plain$ es un conjunto de posibles textos planos.

\item $\cipher$ es un conjunto de posibles textos cifrados.

\item $\key$ es un conjunto de posibles claves.

\item ${\cal L}$ es un conjunto denominado alfabeto de claves de chorro.

\item ${\cal F}=(f_{1},f_{2},\ldots)$ es tal que $\forall\,i\geq 1$,
  $f_{i}\Colon \key\times \plain^{i-1} \to {\cal L}$.

\item Para cada  $z\in {\cal L}$, hay una \emph{funci\'on de
  encripci\'on} $e_{z}\in \encrip$ y una correspondiente
  \emph{funci\'on de decripci\'on} $d_{z}\in \decrip$, donde
  $e_{z}\Colon \plain \to \cipher$, $d_{z}\Colon \cipher \to \plain$ y 
  $d_{z}(e_{z}(x))=x$, cualquiera sea $x\in \plain$.
\end{itemize}
\end{definition}
A continuaci\'on discutimos la forma en que Alicia y Roberto emplean un 
  crip\-to\-sis\-te\-ma como el anterior. 
Primero eligen una clave $K\in \key$ (cuando no pueden ser observados
  por Eva).
M\'as tarde, cuando Alicia quiere enviar a Roberto el texto
  plano $x=x_{1}x_{2}\ldots$,  $x_{i}\in \plain$, $i=1,2,\ldots$,
  esta determina $z_{i}=f_{i}(K,x_{1},\ldots,x_{i-1})$, 
  y env\'{\i}a $y_{i}=e_{z_{i}}(x_{i})$.
En general, Alicia determinar\'a $z_{1},y_{1},z_{2},y_{2},\ldots$
  secuencialmente.
(Es importante notar, que la encripci\'on de $x_{i}$ depende no s\'olo
  de $K$ sino que tambi\'en de $x_{1}x_{2}\ldots x_{i-1}$.)
Una vez que Roberto recibe el texto cifrado $y=y_{1}y_{2}\ldots$, 
  este obtiene el texto plano calculando secuencialmente 
  $z_{1},x_{1},z_{2},x_{2},\ldots$ determinando primero
  $z_{i}=f_{i}(K,x_{1},\ldots,x_{i-1})$ y luego $x_{i}=d_{z_{i}}(y_{i})$.

Claramente, los cifrados en bloque son un caso especial de los cifrados 
  de chorro donde $z_{i}=K$, para todo $i\geq 1$.

La utilidad de los cifrados de chorro radica en que usualmente se
  pueden implementar a nivel de hardware en forma muy eficiente.

Veamos un ejemplo de este tipo de cifrados. 
Consideremos $\plain = \cipher = {\cal L} = \modulo_{2}$ y 
  $\key = (\modulo_{2})^{m}\setminus \{(0,\ldots,0)\}$.
Supongamos que 
  comenzamos con $K=(z_{1},\ldots,z_{m})\in \key$ y
  hacemos que
\begin{eqnarray*}
z_{i+m} & = & (\sum_{j=0}^{m-1} c_{j}\,z_{i+j}) \bmod 2\,,
\end{eqnarray*}
donde $c_{0},\ldots,c_{m-1}\in \modulo_{2}$ estan fijos. 
Finalmente hacemos
\begin{eqnarray*}
e_{z}(x) & = & (x+z)\bmod 2\,, \\
d_{z}(y) & = & (y-z)\bmod 2\,.
\end{eqnarray*}

M\'as adelante en el curso, 
  cuando estudiemos DES ({\it Data Encryption Standard}), 
  veremos otros ejemplos del tipo de encripci\'on discutido
  en esta secci\'on.

\section{Divisibilidad y el Algoritmo de Euclides}
%
En esta secci\'on recordaremos algunas definiciones y repasaremos
  algunos resultados que conciernen a los n\'umeros enteros.

Dados dos enteros $a$ y $b$ decimos que $a$ \emph{divide a} $b$, o $b$
  \emph{es divisible por} $a$, y escribimos $a|b$ si existe un entero
  $k$ tal que $b=ak$. 
En este caso decimos que $a$ es un divisor de $b$.
Si $a$ no es un divisor de $b$ escribimos $a\nodiv b$.

Se tienen las siguientes propiedades:
\begin{itemize}
\item Si $a|b$ y $c$ es un entero, entonces $a|b\,c$.
\item Si $a|b$ y $b|c$, entonces $a|c$.
\item Si $a|b$ y $a|c$, entonces $a|(b \pm c)$.
\end{itemize}

Cada entero mayor que $1$ tiene al menos dos divisores; $1$ y $b$.
Un divisor no trivial de $b$ es un divisor de $b$ distinto a $1$ y a $b$.
Un n\'umero \emph{primo} es, por definici\'on, un n\'umero mayor que $1$
  que no tiene divisores no triviales.
Un n\'umero es \emph{compuesto} si es mayor que $1$ y 
  tiene al menos un divisor no trivial.

Por el Teorema Fundamental de la Aritm\'etica se tiene que cualquier n\'umero
  entero positivo se puede expresar de manera \'unica (salvo el orden 
  de los factores) como un producto de primos.
Dos consecuencias de este importante teorema son:
\begin{itemize}
\item Si $p$ es primo y $p|(ab)$, entonces $p|a$ o $p|b$.
\item Si $m|a$ y $n|a$, y $m$, $n$ 
  no tienen divisores comunes mayores que $1$,
  entonces $(mn)|a$.
\end{itemize}

El \emph{maximo com\'un divisor} de dos enteros $a$ y $b$ no ambos
  nulos, se denota por $\mcd{a}{b}$, y es el mayor entero $d$ tal que
  $d|a$ y $d|b$.
Equivalentemente, $d=\mcd{a}{b}$ si cualquiera sea el entero positivo $c$
  tal que $c|a$ y $c|b$ se tiene que $c|d$.

El \emph{minimo com\'un multiplo} de dos enteros no nulos $a$ y $b$,
  denotado $\mcm{a}{b}$, es el menor entero positivo divisible por $a$ y $b$.
No es dificil probar que $\mcm{a}{b} = |a\,b|/\mcd{a}{b}$. 

Si se conoce la factorizaci\'on de $a$ y $b$ es relativamente simple
  calcular $\mcd{a}{b}$ y $\mcm{a}{b}$.
Si $a$ y $b$ son grandes lo m\'as probable es que no conozcamos 
  su factorizaci\'on.
A continuaci\'on veremos un algoritmo eficiente para calcular el
  m\'aximo com\'un divisor de dos n\'umeros desconocida su 
  factorizaci\'on.

\subsection{Algoritmo de Euclides}
%
Sean $a$ y $b$ dos enteros no ambos nulos, $a>b$, y sea $r_{0}=a$,
  $r_{1}=b$. 
El algoritmo de Euclides consiste en calcular
\begin{eqnarray*}
r_{0} & = & q_{1}\,r_{1} + r_{2}\,, \qquad 0 < r_{2} < r_{1} \\
r_{1} & = & q_{2}\,r_{2} + r_{3}\,, \qquad 0 < r_{3} < r_{2} \\
& \vdots & \\
r_{m-2} & = & q_{m-1}\,r_{m-1} + r_{m}\,, \qquad 0 < r_{m} < r_{m-1} \\
r_{m-1} & = & q_{m}\,r_{m}\,.\\
\end{eqnarray*}
En cursos anteriores se demuestra que $r_{m}=\mcd{a}{b}$.

\begin{exercise}
El objetivo de este ejercicio es encontrar una cota para el n\'umero
  de divisiones que requiere el algoritmo de Euclides.\newline
{\it (i)} Pruebe que si $a>b>0$, y al algoritmo de Euclides le toma $k$
  divisiones encontrar $\mcd{a}{b}$ entonces $a\geq f_{k+2}$ (donde 
  $f_{n}$ es el $n$-\'esimo n\'umero de Fibonacci, i.e. $f_{1}=1$,
  $f_{2}=1$, $f_{n+1}=f_{n}+f_{n-1}$ para todo $n\geq 2$.) \newline
{\it (ii)} Pruebe que 
\begin{eqnarray*}
f_{n} & = & \frac{1}{\sqrt{5}}\,(\phi^{n}-\varphi^{n})\,,
\qquad \mbox{ donde } \phi = \frac{1}{\sqrt{2}}\,(1+\sqrt{5})\,,
\ \ \varphi = \frac{1}{\sqrt{2}}\,(1-\sqrt{5})\,.
\end{eqnarray*}
Luego, para $n$ suficientemente grande $f_{n}$ es el entero m\'as cercano
  a $\phi^{n}/\sqrt{5}$. \newline
\end{exercise}
Sigue que el n\'umero de iteraciones, $k$, que le toma al algoritmo de Euclides
  determinar $\mcd{a}{b}$, donde $a>b$, es tal que 
  $a\geq \phi^{k+2}/\sqrt{5}-1$ (si $k$ es suficientemente grande 
  como para que $|\varphi|^{k+2}/\sqrt{5}<1$), i.e. $k=O(\log{a})$. 

\begin{proposition}
Sea $d=\mcd{a}{b}$, Entonces, existen enteros $u$ y $v$
  tales que $d=u\,a+v\,b$. 
Los valores $u$ y $v$ se puden determinar en el tiempo que toma
  calcular el m\'aximo com\'un divisor de $a$ y $b$ mediante el
  algoritmo de Euclides.
\end{proposition} 
\begin{proof}
Observar que re-ordenando las igualdades del algoritmo de Euclides 
  obtenemos que 
\begin{eqnarray*}
d & = & r_{m-2} - q_{m-1}\,r_{m-1}\,, \\
r_{m-1} & = & r_{m-3} - q_{m-2}\,r_{m-2}\,, \\
& \vdots & \\
r_{3} & = & r_{1} - q_{2}\,r_{2}\,, \\
r_{2} & = & r_{0} - q_{1}\,r_{1}\,.
\end{eqnarray*}
Recordando que $r_{0}=a$ y $r_{1}=b$ las identidades anteriores proveen
  una forma de expresar $d$ como una combinaci\'on lineal de $a$ y
  $b$, puesto que cada $r_{i}$, $i\in\{2,\ldots,m-1\}$,
  es una combinaci\'on lineal de $r_{i-1}$ y $r_{i-2}$. 
\end{proof}

Decimos que dos enteros $a$ y $b$ son \emph{primos relativos} si
  $\mcd{a}{b}=1$, i.e. si no tienen divisores comunes mayores que $1$.
\begin{corollary}\label{cor:euclid}
Si $a$ y $b$ son primos relativos, entonces existen enteros $u$ y $v$
  tales que $1=u\,a+v\,b$.
\end{corollary}

\section{Congruencias}
%
En esta secci\'on repasaremos algunos resultados b\'asicos que conciernen
  a las congruencias.

Dados tres enteros $a, b$ y $m$, decimos que \emph{$a$ es congruente a $b$
  m\'odulo $m$}, y escribimos $a\equiv b \mypmod{b}$, si $m|(a-b)$.
Se puede verificar que congruencia m\'odulo $m$ es una relaci\'on 
  de equivalencia.

Sea $\modulo_{m}$ el conjunto $\{0,\ldots,m-1\}$ dotado de dos 
  leyes de composici\'on interna: suma ($+$) y 
  multiplicaci\'on ($\cdot$), donde la suma y multiplicaci\'on son 
  exactamente iguales a la suma y multiplicaci\'on de enteros pero
  donde los resultados son reducidos m\'odulo $m$.
Se verifica que $\modulo_{m}$ as\'{\i} definido forma un anillo conmutativo
  con unidad.

A continuaci\'on enumeramos algunas propiedades de las congruencias.
\begin{itemize}
\item Si $a\equiv b \mypmod{m}$ y $c\equiv d \mypmod{m}$, entonces
  $a\pm c \equiv b\pm d \mypmod{m}$ y $ac \equiv bd \mypmod{m}$.
\item Si $a\equiv b \mypmod{m}$ entonces $a\equiv b \mypmod{d}$ para cualquier
  divisor $d$ de $m$.
\item 
Si $a\equiv b \mypmod{m}$ y $a\equiv b \mypmod{n}$ y $m$,  $n$ son relativamente
  primos, entonces $a\equiv b \mypmod{mn}$.
\end{itemize}

\begin{proposition}\label{prop:inversos}
Los elementos de $\modulo_{m}$ que tienen inversos multiplicativos son
  a\-que\-llos que son relativamente primos a $m$. 
De hecho, de existir el inverso de $a\in \modulo_{m}$ este se puede
  calcular en el tiempo que toma el algoritmo de Euclides en
  determinar $\mcd{a}{m}$.
\end{proposition}
\begin{proof}
Si $a\in \modulo_{m}$ no es relativamente primo a $m$ entonces 
  $d=\mcd{a}{m}>1$. 
Supongamos que existe un $b\in \modulo_{m}$ 
  tal que $ab\equiv 1 \mypmod{m}$.
Luego $ab-1$ es divisible por $d$, pero $d|a$, 
  por lo tanto concluimos que $1$ es divisible por $d$, contradicci\'on.

Si $a\in \modulo_{m}$ es relativamente primo a $m$ entonces 
  por el \corref{cor:euclid} existen enteros $u$ y $v$ tales que 
  $1=au+mv$.
Eligiendo $b=u$, sigue que $m|(1-ab)$, i.e.
  $ab \equiv 1 \mypmod{m}$.
Luego, $b \bmod m\in\modulo_{m}$ es inverso multiplicativo de $a$.
\end{proof}

\begin{corollary}
La ecuaci\'on $ax\equiv b \mypmod{m}$ en la indeterminada $x$
  tiene soluci\'on en $\modulo_{m}$ si $a$ y $m$ son primos relativos y
  el tiempo que toma calcular sus soluciones esta dominado por el
  tiempo que toma encontrar inversos en $\modulo_{m}$.
Si $d=\mcd{a}{m}>1$  entonces $ax\equiv b \mypmod{m}$ tiene soluci\'on 
  en $\modulo_{m}$ ssi $d|b$ y sus soluciones son las mismas que las
  de la ecuaci\'on $a^{\prime}x\equiv b^{\prime} \mypmod{m^{\prime}}$ donde
  $a^{\prime}=a/d$, $b^{\prime}=b/d$ y $m^{\prime}=m/d$.
\end{corollary}
\begin{proof}
Claramente la soluci\'on en $\modulo_{m}$ de la ecuaci\'on  
  $ax\equiv b \mypmod{m}$ es $x=a^{-1}b \bmod m$ donde $a$ es el
  inverso multiplicativo de $a\in\modulo_{m}$ que existe puesto
  que $a$ y $m$ son primos relativos y por la \propref{prop:inversos}.

Si $x$ es soluci\'on de $ax\equiv b \mypmod{m}$ y $d=\mcd{a}{b}$ entonces
  $ax\equiv b\mypmod{d}$.
Luego $d|(ax-b)$.
Pero como adem\'as $d|a$ se concluye que $d|b$.
Por otro lado, $ax\equiv b\mypmod{m}$ implica que $ax=b+km$ para alg\'n entero
  $k$.
Luego, $a^\prime x = b^\prime - km^\prime$, i.e. 
  $a^\prime x\equiv b^\prime\mypmod{m^\prime}$.
En el sentido inverso, tenemos que si $d|b$ entonces $b^\prime$ es un entero
  y como $a^\prime$ y $m^\prime$ son primos relativos existe
  un $x$ soluci\'on de 
  $a^\prime x\equiv b^\prime\mypmod{m^\prime}$.
Luego, $a^\prime x = b^\prime - km^\prime$ para alg\'un entero $k$.
Sigue que $ax=b-km$, i.e. $ax\equiv b\mypmod{m}$.
\end{proof}

\end{document}
