\documentstyle[12pt,epsfig]{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{5}{20 de Agosto}{Mladen W. Nadinic}

% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI


\section{Pendientes}
%
Partimos probando que si en el \emph{one-time pad}, las claves se usan
 dos veces, entonces el criptosistema deja de ser \emph{perfectamente
 secreto}.

En este caso $\plain = \cipher = (\modulo_{2})^{2n}$ y
$\key=(\modulo_{2})^{n}$
\begin{eqnarray*}
e_{K}((u,v)) & = & (u+k,v+k)\,, \\
d_{K}((u,v)) & = & (u^\prime+k,v^\prime+k) \,.
\end{eqnarray*}
donde $k$ es la clave, $u,v,u^\prime,v^\prime\in (\modulo_{2})^{n}$, y
$x+y=(x_{i}+_{2}y_{i})_{i=1}^{n}$.
%
Veamos, si es que\footnote{\
  En la clase anterior se definio de esta manera a un criptosistema
  perfectamente secreto.}
$p_{\plain}((u,v)) = p_{\plain}((u,v)/(u^\prime,v^\prime)$,  $\forall\ u,v,u'
,v'\in(\modulo_{2})^{n}$.

Supongamos que $u^\prime=v^\prime$ y $u\not=v$, y que $p_{\plain}$ asigna la
misma probabilidad a todos los elementos en $\plain$, entonces
\begin{eqnarray*}
 p_{\plain}((u,v)) & = & \frac{1}{|\plain|} =  \frac{1}{2^{2n}}\,, \\
 p_{\plain}((u,v)/(u',v') & = & p_{\key}(u'=u+k,v'=v+k)=0\,. \\
\end{eqnarray*}

Puesto que estas dos \'ultimas expresiones son distintas, concluimos
que usar la clave dos veces en el criptosistema de \emph{one-time pad}
hace que este criptosistema deje de ser perfectamente seguro.

\section{Criptosistema Producto}
%

Shannon [1949] introdujo la idea de iterar un criptosistema con la
 esperanza que esto condujese a criptosistemas m\'as dificiles de quebrar.
Esta idea a afectado el dise\~no de criptosistemas en uso actualmente, como el
DES.
%
En t\'eminos m\'as formales, se tiene:

\begin{definition}
Criptosistema Producto

Sean $S=(\plain,\cipher,\key,\encrip,\decrip)$ y $S'=(\plain^\prime,\cipher',
 \key^\prime,\encrip^\prime,\decrip^\prime)$,
Definimos el criptosistema producto, denotado por $S'\times\ S ''$ tal que:
 $\plain=\plain^\prime$
 $\cipher=\cipher^{\prime\prime}$,
 $\key=\key^\prime\times\key^{\prime^\prime}$,
 $e_{K}(x)  = e_{K}(e_{K'}(x))$,
 $d_{K}(y)  =  d_{K'}(d_{K''}(y))$,     $K=(K',\ K'')$.
\end{definition}

Si $S=(\plain, \cipher, \key, \encrip, \decrip)$ y adem\'as
$\plain=\cipher$. Escribimos $S^{2}$ como el producto del criptosistema
$S$, por si mismo, es decir, $S\times\ S$. Y en general denotamos el producto
\emph{$n$-\'esimo} del criptosistema
$S$ por $S^{n}=\ S\times\ S\times\ldots\times\ S$; observar que el producto es
asociativo.


Ahora introducimos el concepto de \emph{criptosistemas equivalentes}.
%
\begin{definition}
 Decimos que los criptosistemas
 $S=(\plain,\cipher,\key,\encrip,\decrip)$ y $S'=(\plain',\cipher',\key'
,\encrip',\decrip')$,
 son equivalentes bajo las distribuciones a priori $p_{\plain}$, $p_{\plain^\prime}$
 y las distribuciones de claves $p_{\key},p_{\key^\prime}$  si:
$a\Colon\ Sop(p_{\plain})=\plain \to\ Sop(p_{\plain^\prime})=\plain^\prime$\,,
$b\Colon\ Sop(p_{\cipher})=\cipher \to\ Sop(p_{\cipher^\prime})=\cipher^\prime$\,
,
$g\Colon\ Sop(p_{\key})=\key  \to\ Sop(p_{\key^\prime})=\key$
%
 son biyectivas y\,, \\
%
\begin{eqnarray*}
 p_{\plain}(x)&=&p_{\plain^\prime}(a(x))\ ,\forall\,x\in{\plain}\,,\\
 p_{\key}(k)&=&p_{\key^\prime}(g(K))\ ,\forall\,k\in{\key}\,,\\
 e_{g(k)}(a(x)) & = & b(e_{K}(x))\, \forall\,x\in\ Sop(p_{\plain}),\forall\,k\in\
 Sop(p_{\key})\,, \\
\end{eqnarray*}

Decimos que $S=(\plain,\cipher,\key,\encrip,\decrip)$ es idempotente
bajo la distribuci\'on a priori $p_{\plain}$ y la distribuci\'on de claves
$p_{\key}$, si $S^{2}$ es equivalente a $S$ bajo las distribuciones $p_{\plain}$
$p_{\plain}$
y distribuci\'on de claves $p_{\key\times\key},p_{\key}$.
\end{definition}



\begin{exercise}
El criptosistema af\'{\i}n es idempotente.
\end{exercise}






\section{DES (Data Encryption Standard)}
%
\subsection{Un poco de Historia}
%
En 1972 la NBS (National Bureau of Standards), hoy en d\'{\i}a la NIST (National
 Institute of Standards and Technology), inicio un programa para proteger
 computadores y comunicaciones.
En 1973  la NBS public\'o una solicitud p\'ublica para proposiciones conducentes a
 establecer algoritmos criptograf\'{\i}cos.
 Entre los criterios de dise\~no estaban:

\begin{itemize}
\item el algoritmo debe proveer un alto grado de seguridad
\item el algortimo debe estar completamente especificado y ser f\'acil de
entender
\item la seguridad del algoritmo debe residir en la clave; la seguridad no
debe depender de mantener el algoritmo secreto
\item el algoritmo debe estar disponible para todos los usuarios
\item el algoritmo debe poder implementarse econ\'omicamente a nivel de hardware
\item el algoritmo debe ser eficiente
\item el algoritmo debe ser exportable
\item el algoritmo debe poder validarse.
\end{itemize}
%
IBM desarrollo DES (Data Encryption Standard) como una modificaci\'on de un
sistema conocido como LUCIFER. La NBS pidi\'o ayuda a la NSA (National Security
Agency) para evaluar el algoritmo.
DES se public\'o en 1975, y se adopt\'o como standard despu\'es de un
intenso debate en 1976.
El debate se centraba en las modificaciones sugeridas por NSA. Estas
consistieron basicamente en :
\begin{itemize}
\item Reducci\'on del tama\~no de la clave de 128 bits a 56 bits.
\item Modificaci\'on de ciertas partes del algoritmo que en la \'epoca
vieron misteriosas pero que se aclararon a comienzos de 1990.
\end{itemize}

 La NBS (NIST) re-evalua el DES aproximadamente cada cinco a\~nos. La pr\'oxima
evaluaci\'on es en 1998, donde se espera sea descartado.







\subsection{Descripci\'on de DES}
%

Una completa descripci\'on del DES fue dada por la \emph{Federal Information 
Processing Standards Publication 46} el 15 de enero de 1977. Basicamente
el DES es un criptosistema en que $\plain=(\modulo_{2})^{64}$\, es el 
conjunto de textos planos y $\key=(\modulo_{2})^{56}$, es el conjunto
de claves.

El algoritmo consta de tres etapas(figuras 1 y 2):


%\begin{center}
%\input{l1-f1}
%\end{center}
%\caption{Algoritmo del DES.a) Esquema general. b) Detalle de una iteraci\'on}
%\end{figure}


\begin{itemize}
\item Etapa Inicial
      $IP\Colon (\modulo_{2})^{64}\to\ (\modulo_{2})^{64}$, es una permutaci\'on
      fija.
Escribimos $x_{0}=IP(x)=L_{0}R_{0}$, donde $L_{0}$ y $R_{0}$ son el primer
y el segundo bloque, cada uno de 32 bits de largo.


\item Etapa Intermedia
Se realiza 16 veces el siguiente computo, para obtener $L_{i}$ y $R_{i}$, $1<i<16$:


\begin{eqnarray*}
L_{i}&=&R_{i-1}\,, \\
R_{i}&=&L_{i-1}+_{2}   f(k_{i},R_{i-1})\,. \\
\end{eqnarray*}

M\'as adelante se describe como obtener las claves $k_{i}$ de 48 bits, apartir
de una clave $k$ de 64 bits.


Por ahora nos centramos en la funci\'on $f$ que es donde descansa la fortaleza del
 criptosistema.


La funci\'on $f$ tiene dos argumentos $k_{i}$ y $R_{i-1}$, como se puede apreciar en la
figura 3. El primero de estos argumentos es sometido a una expansi\'on $E$, que le agrega
16 bits m\'as. Este \'ultimo resultado se opera con una operaci\'on $xor$, con el valor 
de la clave $k_{i-1}$. El resultado de esta operaci\'on es dividido en 8 bloques de 6
bits cada uno. Cada bloque es pasado por una \emph{caja-S}, que entrega como resultado
un bloque de 4 bits de tamano. Finalmente los \'ultimos 32 obtenidos se permutan.\footnote{
 Ejemplos del operarar de las cajas-S se puede encontrar en D. R. Stinson
, "Cryptography: Theory and cryptography". Cap\'{\i}tulo 3.}
 
Como se 
puede apreciar la piedra angular de la funci\'on $f$ son las famosas \emph{cajas-S}, que son una
de las tantas fuentes de controversias de la DES.


\item Etapa Final
      Notar que el orden de $L_{16}$ y $R_{16}$ estan invertidos. Y adem\'as
se aplica una permutaci\'on inversa a la permutaci\'on inicial, es decir,
$y=IP^{-1}(R_{16}L_{16})$.

\end{itemize}

\section{Controversia en torno a el DES}
%
Como ya se senalo el DES ha estado, desde su origen, envuelto en muchas
controversias [Diffie y Hellman, 1977; Kolata, 1977].\footnote{V\'ease como referencia: "Redes de Ordenadores", Andrew Tanenbaum, 2� edici\'on.}

Varios cient\'{\i}ficos
de computaci\'on han proclamado que 56 bits representa un tama\~no muy
pequeno para una clave, haciendo que sea f\'acilmente atacada aplicando
fuerza bruta. De hecho en 1993 Wiener detallo una m\'aquina que por un
mill\'on de dolares (poco en el contexto actual de una gran compa\~n\'{\i}a) 
permite descubrir la clave de encripci\'on en un promedido  de 3 horas.
Otra cosa que ha molestado a numerosos cient\'{\i}ficos es el rechazo de IBM
para hacer p\'ublicas las razones por las cuales se escogieron para el cifrador
unas \emph{cajas-S} espec\'ificas. Lo \'unico que IBM ha comentado a respecto
es que la NSA le solicit\'o que mantuviera en secreto los principios de diseno.
Sin el conocimiento de los principios de dise\~no resulta d\'{\i}ficil excluir la
posibilidad de que exista alg\'un truco por medio del cual el cifrado puede
llegar a romperse f\'acilmente. Tambi\'en hubo un incidente, que algunos
investigadores interpretaron como un intento realizado por un empleado
del gobierno para impedir la publicaci\'on de investigaciones academicas
enfocadas a desarrollo de cifradores m\'as poderosos [Shapley y Kolata, 1977].\footnote{V\'ease como 
referencia: "Redes de Ordenadores", Andrew Tanenbaum, 2� edici\'on.}


\section{Como mejorar el DES}
%
DES, al igual que otros cifradores, se le puede aplicar ciertas t\'ecnicas
para hacer m\'as d\'ificil su violaci\'on. Entre estas destacamos.

\subsection{Cifrador Nulo}
%
Esta t\'ecnica suguiere incluir caracteres aleatorios en el texto plano, de
acuerdo con una regla bien definida (por ejemplo, todos los $n$-\'esimos caracteres son
reales  y el resto s\'olo \emph{ruido}. En t\'erminos formales se tiene un
criptosistema $S$ como una \emph{tupla} $(\plain, \cipher, \key, R, \decrip)$,
donde lo nuevo es la \emph{regla} $R$ para agregar basura al texto plano.
Podemos definir $R$ como:
$ R :\ \plain \to\ \plain_{R}$\, donde $\plain_{R}$ es el conjunto de todos
los textos planos a los cuales se le ha agregado basura en ciertas posiciones.
Obviamente debe existir $R^{-1}$, para poder, despu\'es de desencriptar
el texto cifrado, elimminar la basura.  
Este principio, que se conoce como \emph{cifrador nulo}, tiene la desventaja
de desperdiciar \emph{ancho de banda} en el sistema. Pero su fortaleza radica
en que es muy dif\'{\i}cil de descifrar, porque la posici\'on de los caracteres
reales y de los mensajes se conserva en secreto, y se cambia cuando se modifica
la clave. En l\'{\i}neas privadas alquiladas, vale la pena pensar en la importacia
de transmitir basura, cuando de otra manera la l\'{\i}nea quedar\'{\i}a inactiva.

%
\subsection{Cifrador de Flujo.}\footnote{Tambi\'en conocido como cifrador por
chorro.}
%
Otra manera de lograr que el criptoan\'alisis del DES sea m\'as dif\'{\i}cil,
es la de hacerla funcionar como si fuera un \emph{cifrador de flujo}, como
se muestra en la figura 4, en lugar de que opere como un \emph{cifrador
de bloque}, como se le describio en las secciones anteriores. Cuando se le
utiliza como un cifrador de flujo, tanto el trasmisor como el receptor
operar sus circuitos integrados DES en modo de cifrado. Cada uno de los circuitos
integrados DES cuenta con registro de entrada de 64 bits, el cual opera como un registro
de desplazamiento, y un registro de salida de 64 bits, que no lo hace as\'{\i}. En el 
momento que llega un car/'acter de texto plano, se le realiza un $xor$ con los 8 bits
del registro de salida, O1. (Los correspondientes a O2 hasta O8, nunca se utilizan). De
esta manera en car\'acter as\'{\i} creado se transmite al receptor y se introduce en el registro
de desplazamiento de entrada, sacando a I8 del registro. Despu\'es, el circuito integrado (DES) 
es activado, y la salida se calcula para la nueva entrada.
Por otra parte, en el extremo receptor, al car\'acter que llega se le aplica primero un 
$xor$ con O1 (produciendo texto plano) , y despu\'es se introduce en I1. Si el transmisor y el 
receptor arrancan con registros id\'enticos , \'estos permanecer\'an iguales para siempre.
La propiedad de los cifradores de flujo que los hace muy valiosos, es que O1 depende de la 
historia completa del texto plano, por lo que la repetici\'on de un patr\'on en el texto
plano no generar\'a un patr\'on repetido en el texto cifrado. Los cifradores de flujo, tambi\'en,
son muy apropiados para utilizarse en terminales, porque no tienen que colectar ocho 
caracteres antes de emitir un texto cifrado. Cada golpe de tecla ganarar\'a inmediatamente una
salida, a medida que se teclea.



% Figuras

\epsfig{file=c5-f1.ps} \\  \\.
%
%
\epsfig{file=c5-f2.ps} \\.
\epsfig{file=c5-f3.ps} \\.
\epsfig{file=c5-f4.ps}.

\end{document}






