\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
\catedra{1}{6 de Agosto}{Marcos Kiwi}

% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI

Tradicionalmente, la criptograf\'{\i}a ha consistido en el estudio de 
  m\'etodos que permitan el env\'{\i}o de mensajes entre dos partes 
  interesadas, a trav\'es de un canal inseguro mo\-ni\-to\-reado por un
  adversario o esp\'{\i}a, y de forma que s\'olo aquellos a los cuales los
  mensajes van dirijidos puedan entender lo que se esta diciendo. 

El dram\'atico aumento en la capacidad y la interconectividad de los
  computadores modernos ha llevado a una redefinici\'on de los objetivos
  y el \'ambito de la criptograf\'{\i}a. 
La criptograf\'{\i}a moderna aborda temas como la autentificaci\'on,
  verificaci\'on de integridad, no-repudiaci\'on, 
  firmas digitales, dinero electr\'onico, etc.

Comenzamos este curso presentando, brevemente,
  nociones b\'asicas de criptograf\'{\i}a cl\'asica. 
Esto lo hacemos por razones hist\'oricas, y porque nos permitir\'a
  introducir ciertos conceptos importantes sin entrar en mayores 
  complicaciones t\'ecnicas.


\section{Criptograf\'{\i}a Cl\'asica}
%
La criptograf\'{\i}a cl\'asica tipicamente considera el escenario
  en que dos partes interesadas, que llamaremos Alicia y Roberto,
  quieren comunicarse a trav\'es de un canal inseguro.
Este canal inseguro esta monitoriado por un adversario o esp\'{\i}a 
  que llamaremos Eva.
Ejemplos t\'{\i}picos de canales inseguros son: una l\'{\i}nea 
  telef\'onica, una red computacional, el correo, etc.

La informaci\'on que Alicia quiere enviarle a Roberto la llamaremos
  \emph{texto plano}. 
Para evitar que Eva comprenda lo que Alicia le quiere decir a Roberto, Alicia
  encripta el texto plano, utilizando una clave, y obtiene el \emph{texto
  cifrado} el cual envia a Roberto.
Roberto, que asumimos conoce la clave que se us\'o en la encripci\'on, puede 
  descifrar el mensaje, pero Eva que s\'olo ve el texto cifrado
  no deber\'{\i}a ser capaz de determinar el texto plano.

Formalmente tenemos la siguiente
\begin{definition}
Un criptosistema es una tupla $(\plain, \cipher, \key, \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 Para toda clave $K\in \key$, hay una \emph{funci\'on de
  encripci\'on} $e_{K}\in \encrip$ y una correspondiente
  \emph{funci\'on de decripci\'on} $d_{K}\in \decrip$, donde
  $e_{K}\Colon \plain \to \cipher$, $d_{K}\Colon \cipher \to \plain$ y 
  $d_{K}(e_{K}(x))=x$, cualquiera sea $x\in \plain$.
\end{itemize}
\end{definition}
A continuaci\'on discutimos la forma en que Alicia y Roberto emplean un 
  criptosistema. 
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}\ldots x_{n}$,  $x_{i}\in \plain$, $i=1,\ldots,n$,
  esta determina $y_{i}=e_{K}(x_{i})$, $i=1,\ldots,n$
  y env\'{\i}a $y=y_{1},\ldots,y_{n}$.
Una vez que Roberto recibe el texto cifrado $y$, este obtiene el texto
  plano $x$ utilizando la funci\'on de decripci\'on $d_{K}$,
  i.e. calcula $x_{i}=d_{K}(y_{i})$, $i=1,\ldots,n$.

Para que la decripci\'on no sea ambigua, 
  se debe tener que $e_{K}$ debe ser 
  una funci\'on inyectiva cualquiera sea $K\in \key$. 
M\'as aun, en el caso que $\plain=\cipher$ (como usualmente se da), 
  se tiene que $e_{K}$ debe ser una permutaci\'on de $\plain$,
  para todo $K\in \key$.

Si un criptosistema ha de ser de alguna utilidad, entonces debe 
  satisfacer ciertas propiedades b\'asicas.
Entre ellas:
\begin{itemize}
\item Las funciones de encripci\'on $e_{K}$ y decripci\'on $d_{K}$
  deben poder calcularse en forma computacionalmente 
  eficiente.\footnote{\ Formalmente, deben poder ser calculadas 
  por una m\'aquina de Turing probabilista en tiempo polinomial.}

\item A un adversario que conoce el texto cifrado y desconoce la
  clave $K$ le debe ser dif\'{\i}cil determinar
  $K$ o el texto plano $x$ tal que $e_{K}(x)=y$.
\end{itemize}
La segunda de estas propiedades intenta capturar de forma muy vaga 
  la noci\'on de \emph{seguridad}. 
A medida que el curso progrese iremos precisando este concepto.


En las secciones que siguen veremos algunos ejemplos concretos de 
  criptosistemas cuyo inter\'es es m\'as que nada de 
  caracter hist\'orico.


\section{Criptosistemas Mono-alfab\'eticos}
%
En este caso las funciones de encripci\'on 
  corresponden a transformaciones de los caracteres 
  alfab\'eticos de los cuales puede consistir el texto plano.

\subsection{Cifrados de Sustituci\'on}
%
En estos casos $|\plain|=|\cipher|$. 
De hecho, a menudo $\plain=\cipher$.
Tipicamente $\plain$, $\cipher$ corresponden al alfabeto, a un conjunto 
  de n\'umeros, un conjunto de s\'{\i}mbolos, etc.
En estos criptosistemas cada funci\'on de encripci\'on $e_{K}$ corresponde
  a una biyecci\'on entre $\plain$ y $\cipher$, y la correspondiente
  funci\'on de decripci\'on $d_{K}$ es la inversa de $e_{K}$ (que
  existe pues $e_{K}$ es biyecci\'on).

Ejemplos de c\'odigos de sustituci\'on son algunos de los criptosistemas
  utilizados por la masoner\'{\i}a, uno de los cuales se ilustra en
  la \figref{fig:masoneria}. 

\begin{figure}\label{fig:masoneria}
\begin{center}
\input{c1-f1}
\end{center}
\caption{Cifrado de la masoner\'{\i}a.}
\end{figure}

A continuaci\'on estudiaremos otros dos c\'odigos de sustituci\'on.

\subsection{Cifrado por Corrimiento}
%
En el cifrado por corrimiento\footnote{\ {\it Shift cipher}.}
  $\plain = \cipher = \key = \modulo_{m}$, y 
  para todo $x\in \plain$, $y\in \cipher$
\begin{eqnarray*}
e_{K}(x) & = & (x + K) \bmod m\,, \\
d_{K}(y) & = & (y - K) \bmod m\,,
\end{eqnarray*}
donde $a \bmod b$, $|b|\geq 1$,
   denota el \'unico n\'umero $r\in\{0,\ldots,|b|-1\}$
   tal que $a=kb+r$ para algun entero $k$ (i.e. si $a$ y $b$ son
   positivos, $a\bmod b$ es el resto que se obtiene de dividir
   $a$ por $b$).

Tipicamente $m=27$ y $j\in \modulo_{m}$ representa la $j$-\'esima
  letra del alfabeto (es decir $0$ representa $A$, $1$ representa $B$,
  ..., $26$ representa $Z$).
ROT13 es un ejemplo de este tipo de criptosistemas
  el cual es a menudo utilizado
  para obscurecer el contenido de mensajes enviados a 
  newsgroups y que pueden ser ofensivos para algunas personas.


\subsection{Cifrado Af\'{\i}n}
%
En este caso $\plain = \cipher = \modulo_{m}$, y
\begin{eqnarray*}
\key & = & \set{(a,b) \in \modulo_{m}\times \modulo_{m}}{ \mcd{a}{m}=1 }\,. 
\end{eqnarray*}
Equivalentemente, $\key$ es el conjunto de tuplas $(a,b)$ de n\'umeros en 
  $\modulo_{m}$ tales que $a$ y $m$ son primos relativos.
Luego, de un resultado b\'asico de la aritm\'etica modular\footnote{\ 
  La pr\'oxima c\'atedra repasaremos conceptos relacionados
  con aritm\'etica modular y discutiremos la complejidad de c\'alculo
  de algunas operaciones en $\modulo_{m}$.}
  sigue que $a$ tiene un inverso multiplicativo, denotado
  $a^{-1}$, en $\modulo_{m}$.
Si $K=(a,b)\in \key$, para todo $x\in \plain$, $y\in \cipher$
\begin{eqnarray*}
e_{K}(x) & = & (a\,x + b) \bmod m\,, \\
d_{K}(y) & = & a^{-1}\,(y - b) \bmod m\,.
\end{eqnarray*}

Tipicamente $m=27$ y $j\in \modulo_{m}$ representa la $j$-\'esima
  letra del alfabeto (es decir $0$ representa $A$, $1$ representa $B$,
  etc.).
 
La seguridad de un criptosistema radica, en parte, en el tama\~no del 
  conjunto de claves $\key$.
Si la cardinalidad de $\key$ es demasiado peque\~na entonces es posible
  ciclar sobre todo $\key$ y determinar $d_{K}(y)$ para todas las claves
  $K\in \key$.
Muchas veces, por contexto, podemos determinar cual texto plano $d_{K}(y)$
  es el \'unico que tiene sentido.  
A continuaci\'on determinaremos $|\key|$ para el cifrado af\'{\i}n.
\begin{definition}
El n\'umero de enteros en $\modulo_{m}$ que son relativamente primos
  a $m$ es $\phi(m)$ donde $\phi$ es la funci\'on-phi de Euler.
\end{definition} 
M\'as adelante probaremos que la funci\'on-phi de Euler es 
  multiplicativa, es decir, 
\begin{proposition}
  $\phi(m\,n) =\phi(m)\,\phi(n)$,
  si $m, n$ son enteros positivos relativamente primos.
\end{proposition}

Luego podemos concluir el siguiente 
\begin{lemma}
Si $m$ es tal que $\displaystyle m = \prod_{i=1}^{n} p_{i}^{e_{i}}$,
  donde los $p_{i}$ son n\'umeros primos distintos, y los $e_{i}$ son
  enteros positivos, entonces
\begin{eqnarray*}
\phi(m) & = & \prod_{i=1}^{n} ( p_{i}^{e_{i}}-p_{i}^{e_{i}-1})\,.
\end{eqnarray*}
\end{lemma}
\begin{proof}
Por la propieda multiplicativa de $\phi$ sigue que 
  $\displaystyle \phi(m) = \prod_{i=1}^{n} \phi(p_{i}^{e_{i}})$.
Pero si $p$ es primo, y $e$ es un entero positivo es f\'acil ver
  que los \'unicos n\'umeros en $\{1,\ldots, p^{e}-1\}$ que no son
  primos relativos con $p^{e}$ son los m\'ultiplos de $p$, de los 
  cuales hay $p^{e-1}$.
Luego, $\phi(p^{e})=p^{e}-p^{e-1}$, de donde se conluye el
 resultado buscado.
\end{proof}
Luego, el n\'umero de claves del cifrado af\'{\i}n sobre $\modulo_{m}$ es
  $(m\,\phi(m))$.
Observar que conocida la factorizaci\'on de $m$ es f\'acil calcular
  $\phi(m)$.
De hecho no se conoce un algoritmo eficiente para determinar 
  $\phi(m)$ desconocida la factorizaci\'on de $m$.
El siguiente resultado sugiere que de existir dicho algoritmo no 
  va a ser f\'acil encontrarlo.
\begin{proposition}
Si $m$ es el producto de dos primos $p$ y $q$ distintos, entonces 
  la determinaci\'on de $p$ y $q$ es equivalente a la determinaci\'on 
  de $\phi(m)$.
M\'as precisamente, uno puede calcular eficientemente $\phi(m)$
  conocidos $p$ y $q$, y conocido $\phi(m)$ se puede determinar 
  eficientement $p$ y $q$.
\end{proposition} 
\begin{proof}
Como $\phi(m)=(p-1)(q-1)=m+1-(p+q)$, si $p$ y $q$ son conocidos entonces
  $\phi(m)$ se obtiene como el resultado de un par de sumas.

Si $\phi(m)$ es conocido, $p$ y $q$ se obtienen resolviendo el sistema
  $pq=m$ y $\phi(m)=m+1-(p+q)$, lo que requiere el c\'alculo de una 
  raiz cuadrada.
El c\'alculo de la raiz cuadrada es la operaci\'on m\'as costosa y 
  domina el tiempo involucrado en la ejecuci\'on de las otras operaciones
  requeridas.
\end{proof}

\section{Criptosistemas Poli-alfab\'eticos}
%
En estos criptosistemas cada caracter alfab\'etico del que esta compuesto el 
  texto plano puede ser encriptado de distintas maneras. 
%En general criptoanalisar este tipo de criptosistemas es m\'as 
%  dificil que criptanalisar cifrados mono-alfab\'eticos.

\subsection{Cifrado de Hill}
%
En este caso $\plain = \cipher = (\modulo_{m})^{n}$, y
  $\key$ es el conjunto de matrices invertibles de $m\times m$ 
  cuyas coordenadas estan en $\modulo_{m}$, es decir
\begin{eqnarray*}
\key & = & \set{K \in M_{n}(\modulo_{m})}{ K \mbox{ es invertible }}\,.
\end{eqnarray*}
Adem\'as, para todo $x\in \plain$, $y\in \cipher$
\begin{eqnarray*}
e_{K}(x) & = & Kx, \\
d_{K}(y) & = & K^{-1}y\,.
\end{eqnarray*}
donde todas las operaciones se realizan sobre $\modulo_{m}$.

Tipicamente $m=27$, $j\in \modulo_{m}$ representa la $j$-\'esima
  letra del alfabeto (es decir $0$ representa $A$, $1$ representa $B$,
  etc.), y cada elemento de $\plain$ representa una secuencia de 
  $n$ letras.

Ponemos t\'ermino a esta secci\'on dando algunas caracterizaciones
  equivalentes de invertivilidad.
\begin{proposition} Sea $A\in M_{n}(\modulo_{m})$, las siguientes 
afirmaciones son equivalentes:
\begin{itemize}
\item $\mcd{\determ{A}}{m}=1$,
\item $A$ es invertible,
\item la transformaci\'on que a  $x\in (\modulo_{m})^{n}$ le 
  asocia  $A\,x\in (\modulo_{m})^{n}$ es inyectiva.
\item si $x\in (\modulo_{m})^{n}$ es tal que $x \neq \vec{0}$ entonces
  $A\,x\neq \vec{0}$,
\end{itemize}
\end{proposition}
\begin{proof}
Si $D=\mcd{\determ{A}}{m}=1$, entonces $D$ tiene inverso multiplicativo
  en $\modulo_{m}$ y la inversa de la matriz $A$ exise y esta dada por
  $B\in M_{n}(\modulo_{m})$ tal que 
  $B_{j,i} = D^{-1}\,(-1)^{i+j}\,\determ{A_{i,j}}$
  (observar que los \'{\i}ndices se invierten), y donde
  $A_{i,j}\in M_{n-1}(\modulo_{m})$ es la matriz que se obtiene de 
  $A$ al eliminar la $i$-\'esima fila y la $j$-\'esima columna.

Si $A$ es invertible entonces $A\Colon  (\modulo_{m})^{n} \to 
   (\modulo_{m})^{n}$ es una biyecci\'on, en particular es
   inyectiva.

Si $A\Colon  (\modulo_{m})^{n} \to (\modulo_{m})^{n}$ es inyectiva
  entonces, de un resultado b\'asico del \'algebra lineal,
  se tiene que 
  $\kernel(A)\eqdef\set{x\in \modulo_{m}}{Ax=0}
	=\{(0,\ldots,0)\}\subseteq (\modulo_{m})^{n}$.

Demostraremos que la \'ultima afirmaci\'on implica la primera
  para el caso en que $n=2$. 
La generalizaci\'on es directa pero tediosa.
Sea entonces 
\begin{eqnarray*}
A & = & \left( \begin{array}{cc} a & b \\ c & d \end{array}\right)\,.
\end{eqnarray*}
Supongamos que $D=\det{A}$ y $m$ no son primos relativos, i.e.
  $d=\mcd{D}{m}>1$.
Sea $m^{\prime}=m/d$.
La demostraci\'on se descompone en tres casos. 
(En lo que sigue todas las operaciones aritm\'eticas son sobre 
  $\modulo_{m}$.)
  \newline
{\bf Caso 1:} \ Si todas las componentes de $A$ son divisibles por 
  $d$ y 
  $x=\left(\begin{array}{c}m^{\prime} \\ m^{\prime}\end{array}\right)$ 
  sigue que $Ax=0$ lo que constituye una contradicci\'on. \newline
{\bf Caso 2:} \ Si $a$ y $b$ no son ambos divisibles por $d$. 
  Haciendo
  $x=\left(\begin{array}{c}-bm^{\prime} \\ am^{\prime}\end{array}\right)$ 
  y dado que $D=ac-bd$ sigue que 
  $Ax=\left(\begin{array}{c} 0 \\ Dm^{\prime}\end{array}\right)$, 
  contradicci\'on. \newline
{\bf Caso 3:} \ Si $c$ y $d$ no son ambos divisibles por $d$ se procede
  como en el caso anterior. \newline
\end{proof}
\end{document}




