\documentclass{article}

\usepackage{amssymb}

\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{proof}{\noindent\par{\bf Dem:}\ }{\(\qed\) \par\medskip}
%\newenvironment{dem}{\startproof}{\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 Oto\~no, 1998}  }
       \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

\newcommand{\ie}{{\em i.e.}}
\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{Ker}}
\newcommand{\determ}[1]{\mbox{det}(#1)}
\newcommand{\mcd}[2]{\mathrm{mcd}(#1,#2)}
\newcommand{\mcm}[2]{\mathrm{mcm}(#1,#2)}
\newcommand{\set}[2]{\{#1\,|\,#2\}}
\newcommand{\smidge}{{\kern .05em}}	
\newcommand{\Colon}{{\smidge\colon\;\:}}

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


\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

% En caso que la transcripcion no este basada en una transcripcion de
% an~os antriores usar:
%\catedra{1}{11 de Marzo}{Marcos Kiwi}

% En caso que la transcripcion ESTE basada en una transcripcion de 
% an~os anteriores usar: 
\catedra{1}{16 de Marzo}{Marcos Kiwi\footnotemark}

\footnotetext{Estos apuntes est\'an basados en la transcripci\'on de Marcos Kiwi (6/8/96)}

% 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.
Estos conceptos los iremos definiendo y estudiando a trav\'es del curso.

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 t\'{\i}picamente 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, ondas radiales, 
  el telegrafo, etc.

La informaci\'on que Alicia quiere enviarle a Roberto la llamaremos
  \emph{texto puro} o \emph{texto plano}. 
Para evitar que Eva comprenda lo que Alicia le quiere decir a Roberto, Alicia
  encripta el texto puro, 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 puro.

Formalmente tenemos la siguiente
\begin{definition}[Criptosistema Sim\'etrico]
Un criptosistema es una tupla $(\key, \encrip, \decrip)$
tal que:
\begin{itemize}
\item $\key$ es un conjunto de posibles claves.

\item $\encrip=(e_{K})_{K\in\key}$ es una lista de funciones de 
  encripci\'on y $\decrip=(d_{K})_{K\in\key}$ es una lista de funciones
  de decripci\'on.

\item Para toda clave $K\in \key$, 
  $e_{K}\Colon \plain_{K} \to \cipher_{K}$, 
  $d_{K}\Colon \cipher_{K} \to \plain_{K}$ y 
  $d_{K}(e_{K}(x))=x$, cualquiera sea $x\in \plain_{\key}$.
\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
  puro $x=x_{1}\ldots x_{n}$,  $x_{i}\in \plain_{K}$, $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
  puro $x$ utilizando la funci\'on de decripci\'on $d_{K}$,
  \ie\ calcula $x_{i}=d_{K}(y_{i})$, $i=1,\ldots,n$.

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

\begin{observation}
Por su modo de empleo, el criptosistema definido m\'as arriba se denomina
  \emph{criptosistema de bloque}.\footnote{\ Block cipher.}
El nombre se debe a que cualquier mensaje a ser enviado debe romperse en 
  bloques cada uno de los que debe pertenecer al dominio de la funci\'on
  de encripci\'on que se este utilizando.
\end{observation}

Si un criptosistema ha de ser de alguna utilidad, entonces debe 
  satisfacer ciertas propiedades b\'asicas.
Entre ellas:
\begin{itemize}
\item Debe ser posible elegir un elemento $K$ en $\key$ en forma 
  computacionalmente eficiente.
Formalmente, dado un par\'ametro de seguridad, debe ser posible elegir una 
  clave por una m\'aquina de Turing probabilista en tiempo polinomial.

\item Las funciones de encripci\'on $e_{K}$ y decripci\'on $d_{K}$
  deben poder calcularse en forma computacionalmente 
  eficiente.
Formalmente, deben poder ser calculadas 
  por una m\'aquina de Turing probabilista en tiempo polinomial.

\item A un adversario que conoce el texto cifrado
  le debe ser dif\'{\i}cil determinar
  la clave $K$ o el texto puro $x$ tal que $e_{K}(x)=y$.
\end{itemize}
La \'ultima 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.
Pero antes identificaremos algunos conceptos con los que ya nos hemos
  topado.

\subsection{Terminolog\'{\i}a y Conceptos B\'asicos}
%
\noindent{\sc Participantes en la comunicaci\'on:\/} Una \emph{entidad}
  o \emph{parte} es un ente que env\'{\i}a, recive, o manipula
  informaci\'on. 
Alicia y Roberto, mencionados anteriormente, son 
  entidades. 
Una entidad puede ser una persona, pero tambi\'en un terminal de computador,
  etc.
Un \emph{emisor} es una entidad en una comunicaci\'on que es la 
  leg\'{\i}tima originadora de la informaci\'on que se env\'{\i}a, 
  como por ejemplo Alicia mencionada anteriormente. 
Un \emph{receptor} es una entidad en una comunicaci\'on que es un leg\'{\i}timo
  destinatario de informaci\'on, como por ejemplo Roberto mencionada
  anteriormente. 
Un \emph{adversario} es una entidad que participa en la comunicaci\'on,
  que no es ni emisor ni receptor, y que trata de burlar el servicio de
  transmisi\'on de informaci\'on que esta siendo proveido entre el emisor
  y el destinatario.
Otros sin\'onimos de adversario son: enemigo, atacante, oponente, intruso, etc.
Frecuentemente un adversario tratar\'a de jugar el rol de un leg\'{\i}timo
  emisor o receptor.

\noindent{\sc Canales:\/} Un \emph{canal} es un medio de transmisi\'on
  de informaci\'on entre entidades.
Un \emph{canal f\'{\i}sicamente seguro} es aquel
  que no puede ser accesado f\'{\i}sicamente por un adversario.
Un \emph{canal inseguro} es aquel en que una entidad distinta a aquellas
  con las autorizaci\'ones adecuadas puede leer, borrar, insertar, o
  re--enviar mensajes.
Un \emph{canal seguro} es aquel en que ning\'una entidad distinta
  a aquellas con las autorizaci\'ones adecuadas puede leer, borrar, insertar,
  o re--enviar mensajes.
Un canal seguro no es necesariamente un canal f\'{\i}sicamente seguro.
En efecto, la seguridad de un canal puede ser garantizada por medios distintos
  a los f\'{\i}sicos. 
En este curso nos abocaremos al estudio de los mecanismos que permiten
  asegurar un canal por medios que no son f\'{\i}sicos. 

\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 puro.

\subsection{Cifrados de Substituci\'on}
%
En estos casos $|\plain_{K}|=|\cipher_{K}|$, para todo $K\in \key$. 
De hecho, a menudo $\plain_{K}=\cipher_{K}$.
T\'{\i}picamente $\plain_{K}$, $\cipher_{K}$ 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_{K}$ y $\cipher_{K}$, 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 substituci\'on son algunos de los criptosistemas
  utilizados por la masoner\'{\i}a, uno de los cuales se ilustra en
  la \figref{fig:masoneria}. 
(Observar que en este ejemplo, s\'olo existe una clave, luego toda la 
  seguridad del criptosistema se basa en mantenerlo secreto.)

\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 substituci\'on.

\subsection{Cifrado por Corrimiento}
%
En el cifrado por corrimiento\footnote{\ {\it Shift cipher}.}
  $\key = \set{(a,m)}{m\in \Bbb{N}^{*}, a\in \modulo_{m}}$, 
  para todo $K=(k,m)\in\key$ se tiene que
  $\plain_{K} = \cipher_{K} = \modulo_{m}$, y
  para todo $x\in \plain_{K}$, $y\in \cipher_{K}$
\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,m-1\}$
   tal que $a=kb+r$ para alg\'un entero $k$ (i.e. si $a$ y $b$ son
   positivos, $a\bmod b$ es el resto que se obtiene de dividir
   $a$ por $b$).

T\'{\i}picamente $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.
Uno de los criptosistemas m\'as antiguos conocidos, el de Julio Cesar,
  es tambi\'en un c\'odigo de substituci\'on que consist\'{\i}a en substituir
  cada letra del alfabeto por aquella tres posiciones m\'as adelante.

\subsection{Cifrado Af\'{\i}n}
%
En este caso 
\begin{eqnarray*}
\key & = & \set{(a,b,m)}{m\in\Bbb{N}^{*}, a,b\in\modulo_{m}, \mbox{ y }
  \mcd{a}{m}=1 }\,,
\end{eqnarray*}
y para $K=(a,b,m)\in\key$, $\plain_{K} = \cipher_{K} = \modulo_{m}$.
Equivalentemente, $\key$ es el conjunto de tuplas $(a,b,m)$ de n\'umeros 
  tales que $a,b\in\modulo_{m}$ y $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 en $\modulo_{m}$, denotado
  $a^{-1}$.
Si $K=(a,b,m)\in \key$, para todo $x\in \plain_{K}$, $y\in \cipher_{K}$
\begin{eqnarray*}
e_{K}(x) & = & (a\,x + b) \bmod m\,, \\
d_{K}(y) & = & a^{-1}\,(y - b) \bmod m\,.
\end{eqnarray*}

T\'{\i}picamente $m=27$ est\'a fijo, 
  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 puro $d_{K}(y)$
  es el \'unico que tiene sentido.  
La pr\'oxima c\'atedra determinaremos $|\key|$ para el cifrado af\'{\i}n
  en el caso que $m$ este fijo.
Este problema es interesante desde un punto de vista matem\'atico.
M\'as aun, dado que un adversario que ve suficiente texto cifrado, encriptado 
  utilizando
  el criptosistema af\'{\i}n, puede facilmente deducir el valor de $m$.
En efecto, si el texto plano encriptado se distribuye uniformemente 
  en $\modulo_{m}$, se puede probar que si $N$ es el mayor n\'umero
  de $k$ textos cifrados, entonces $N+1\leq m \leq N+c$
  con probabilidad al menos $1-(c/m)^{k}$. 

\end{document}