\documentstyle[12pt,epsfig,spanish]{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 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

\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{\plainm}{{\cal P}_{m}}
\newcommand{\cipherm}{{\cal C}_{m}}
\newcommand{\keym}{{\cal K}_{m}}
\newcommand{\encripm}{{\cal E}_{m}}
\newcommand{\decripm}{{\cal D}_{m}}

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

\catedra{6}{31 de Marzo}{H'ector L'opez Moraga}

\subsubsection{ [Continuaci'on de Seguridad Incondicional]}

\begin{proposition}
Sea $C=( \key , \encrip, \decrip)$, con 
$ \key= \bigcup_{ m \in {\cal I}_{C} }\keym$, un 
criptosistema incondicionalmente seguro. Entonces, si $P_X[x] > 0$
$(\forall x \in \plainm)$ y $P_Y[y] > 0$ $(\forall y \in \cipherm)$
se cumple que $| {\cipherm} | \leq | \keym |$.
\end{proposition}

\begin{proof}
Fijemos $x \in \plainm$. Si $ P_Y[y/X=x]=P_Y[y] >0$,
entonces $(\forall y \in \cipherm)$ $(\exists K \in \keym)$ 
tal que $e_{K}(x)=y$. Luego la aplicaci'on que va de $\keym 
\longrightarrow \cipherm$ y que a cada $K$ le asocia $e_K(x)$ es 
sobreyectiva, y por lo tanto se cumple que
$ |\cipherm| \leq |\keym|$ 
\end{proof}

\begin{observation}
Notemos el hecho importante que si las funciones de 
encripci'on no son ambiguas, entonces debe cumplirse que
$ |\plainm| \leq |\cipherm|$. 
\end{observation}

\begin{lemma}
Sea $C=(\key,\encrip,\decrip)$,  con $\key=\bigcup_{m\in{\cal I}_{C}}\keym$,
 un criptosistema donde $|\keym|=|\cipherm|=|\plainm|
$. Entonces el criptosistema provee seguridad incondicional si y solo si cada
clave es usada con probabilidad igual a $\frac{1}{|\keym|}$, y para cada $x \in 
\plain$ e $y \in \cipher$, hay una 'unica clave K tal que $e_K(x)=y$.
\end{lemma}

\begin{proof}

$(\Rightarrow)$

Supongamos que el criptosistema dado provee seguridad incondicional. Entonces 
por la proposici'on anterior, para cada $x \in \plainm$ e $y \in \cipherm$ debe 
haber al menos una clave K tal que $e_K(x)=y$. As'i, obtenemos que

\begin{eqnarray*}
        |\cipher| & = & | \{ e_K(x) : K \in \keym \}|\\
		  & \leq & |\keym|\\
\end{eqnarray*}

Pero estamos asumiendo que $|\cipherm|=|\keym|$. De aqu'i, debe cumplirse que
        \[ \{ e_K(x) : K \in \keym \}| = |\keym| \]

Esto es, no existen dos claves $K_1$ y $K_2$, distintas, tal que $e_{K_1}(x) =
e_{K_2}(x)=y$. De aqu'i, hemos mostrado que para alg'un $x \in \plainm$ e $y \in
\cipherm$, hay exactamente una clave K tal que $e_K(x)=y$.

Denotando $n=|\keym|$, sea $\plainm=\{x_i : 1 \leq i \leq n\}$ y fijemos un 
$y \in \cipherm$. Podemos nombrar las claves $K_1 , K_2, ... , K_n$ de la forma
$e_{K_i} (x_i) = y$  para $1 \leq i \leq n$.

Usando el teorema de Bayes, tenemos que

\begin{eqnarray*}
P_X(x_i/y) & = & \frac{P_Y(y/x_i) P_X(x_i)}{P_Y(y)}\\
           & = & \frac{P_K(K_i) P_X(x_i)}{P_Y(y)}
\end{eqnarray*}

Consideramos la condici'on de seguridad incondicional $P_X(x_i/y)=P_X(x_i)$.
De esto sigue que $P_K(K_i)= P_Y(y)$, para $1\leq i\leq n$. Esto dice que las
claves $K_i$ son equiprobables, pero ya que el n'unero de claves es
$|\keym|$ tenemos que $P_K(K)=\frac{1}{|\keym|}$ para todo $K \in \keym$.


$(\Leftarrow)$

La otra parte de la demostraci'on se deja propuesta. Es f'acil
ver, con las dos condiciones de hip'otesis, que  un criptosistema que las cumple
debe ser incondicionalmente seguro.
\end{proof}

\section{Criptosistemas Productos}

Shannon [1949] introdujo la idea de iterar un criptosistema con la esperanza
que esto condujese a criptosistemas m'as dif'iciles de quebrar. Esta idea a
afectado el dise~no de criptosistemas en uso actualmente, como {\em DES}.

\begin{definition} [Criptosistema Producto]

Sean $C_i=(\key_{i},\encrip_{i},\decrip_{i})$ con $i=0,1$ dos criptosistemas
  tales que $\exists {\cal I}_{C_0},{\cal I}_{C_1} \subseteq N$ y 
una funci'on $\varphi \: : \: {\cal I}_{C_0} \longrightarrow {\cal I}_{C_1}$
donde adem'as

\begin{enumerate}
\renewcommand{\labelenumi}{(\roman{enumi})}

\item $\key_{i} = \bigcup_{m \in {\cal I}_{C_i}}\key_{m,i} \: , \: i\in \{0,1\}$

\item $\forall K \in \key_{i} \: , \: Dom(e_K) = \plain_{m,i}$ , $Rec(e_K)
=\cipher_{m,i}$ $i  \in \{0,1\}.$

\item $\forall m_0 \in {\cal I}_{C_0}\:,$ si $m_1 = \varphi(m_0)
\Longrightarrow \cipher_{m_0,0} = \plain_{m_1,1}$

\end{enumerate}

Se define el \emph{criptosistema producto} como la tupla
\[C \times C' = (\key,\encrip,\decrip)\]
donde
\[\key=\bigcup_{ m \in {\cal I}_{C}}\key_{m,0}\times\key_{\varphi(m),1}\]
para

\begin{eqnarray*}
K & = & (K_0, K_1 ) \in \key \\
e_K & = & e_{K_1} \circ e_{K_0} \\
d_K & = & d_{K_0} \circ d_{K_1} \\
\end{eqnarray*}

\end{definition}


\section{DES (Data Encription Standard)}

\subsection{Un poco de Historia}

En 1972 la NBS (National Bureau of Standards), hoy en d'ia conocida como
NIST (National Institute of Standards and Technology), inici'o un programa
para proteger computadores y comunicaciones. En 1973 la NBS public'o una
solicitud p'ublica para proposiciones conducentes a establecer algoritmos
criptogr'aficos. Entre los criterios de dise~no de estos mecanismos se
encontraban:

\begin{itemize}
\item el algoritmo debe proveer un alto grado de seguridad.
\item el algoritmo debe estar completamente especificado y ser f'acil de
entender.
\item la seguridad del algoritmo debe residir en la clave, es decir, la 
seguridad no puede depender del mantenimiento en secreto del m'etodo.
\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 desarroll'o DES (Data Encryption Standard) como una modificaci'on de un
sistema conocido bajo el nombre de LUCIFER. La NBS para poder analizar las
distintas propuestas pidi'o ayuda a la NSA (National Security Agency) para 
evaluar los algoritmos. DES se public'o en 1975, y se adopt'o como un
standard despu'es de un intenso debate en 1976. Este debate se centraba en
las modificaciones sugeridas por la NSA, las que consistieron b'asicamente
en:

\begin{itemize}
\item Reducci'on del tama~no de la clave de 128 a 56 bits.
\item Modificaci'on de ciertas partes del algoritmo que en la 'epoca se 
vieron misteriosas pero a comienzos de 1990 los acad'emicos advirtieron 
la trascendencia de ellas.
\end{itemize}

La NBS (NIST) eval'ua DES aproximadamente cada cinco a~nos. La pr'oxima
evaluaci'on es este a~no (1998), en donde se espera sea descartado.
\end{document}

