\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}}}
\newcommand{\Prob}[1]{{{\rm Pr}[#1]}}

% FIN LISTA DE MACROS PERSONALES
% MACROS PARA LA CATEDRA No.3

\newcommand{\Pp}{{p_{\plain}}}
\newcommand{\Pk}{{p_{\key}}}
\newcommand{\Pc}{{p_{\cipher}}}

\begin{document}

% LOS DATOS IDENTIFICATORIOS DE LA CATEDRA TRANSCRITA VAN AQUI
\catedra{4}{14 de Agosto}{Juan Pablo Alamo E.}

% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI

\section{Seguridad incondicional}

En la c\'atedra anterior digimos que un criptosistema es incondicionalmente
seguro si no puede quebrarse frente a un ataque, sin importar cuanta
capacidad computacional utilizemos. Queremos formalizar esta noci\'on
para un ataque dirigido al texto cifrado.\\
\\
El estudio de la seguridad incondicional no se puede hacerce en terminos
de la capacidad computacional en relaci\'on al tiempo necesario en quebar
un criptosistema, una forma apropidada es utilizar teor\'{\i}a de
probabilidades como base. revisemos brevemente las principales definiciones
en relaci\'on a esta materia que utilizaremos mas adelante.

\begin{definition}\label{Prob}
  Sean $X$ e $Y$ dos variables aleatorias, denotamos la probabilidad que
  $X$ tome el valor $x$ por $p(x)$ y la probalilidad que $Y$ tome el valor
  $y$ por $p(y)$. {\bf la probabilidad conjunta} $p(x,y)$ denota la
  probalilidad que $X$ tome el valor $x$ e $Y$ tome el valor $y$.
  {\bf la probabilidad condicional} $p(x|y)$ denota la probabilidad que
  $X$ tome el valor $x$ dado que $Y$ tomo el valor $y$. Decimos que las
  variables aleatorias $X$ y $Y$ son independientes si $p(x,y)=p(x)p(y)$
  para todo valor $x$ de $X$ e $y$ de $Y$.
\end{definition}

Es posible expresar la probabilidad conjunta en terminos de probabilidad
condicional como $p(x,y)=p(x|y)p(y)$, o bien $p(x,y)=p(y|x)p(x)$. De estas
dos expresiones se desprende el {em Teorema de Bayes}

\begin{theorem}\label{bayes}
  {\em Teorema de Bayes} si $p(y)>0$, entonces 
  \begin{displaymath}
     p(x|y)=\frac{p(x)p(x|y)}{p(y)}
  \end{displaymath}
\end{theorem}

\begin{corollary}
  $X$ e $Y$ son variables aleatorias independientes si y solo si
  $p(x|y)=p(x)$ para todo $x,y$
\end{corollary}

Consideramos un criptosistema $(\plain,\cipher,\key,\encrip,\decrip)$ de
bloque, donde la clave que se eliga es usada para una sola encripci\'on.
Vamos a asumir, salvo que se diga lo contrario, que
$|\plain|, |\cipher|, |\key|, |\encrip|, |\decrip|<+\infty$, es decir 
los conjunto $\plain, \cipher, \key, \encrip$ y $\decrip$ son finitos.\\ 
\\
Tomaremos una distribuci\'on de probabilidad sobre el conjunto de textos
plano $\plain$ denotando la probabilidad a priori de escoger $x$ como
$\Pp(x)$. Ademas asumimos que la clave $k$ escogida por Alicia y
Roberto tiene la misma distribuci\'on de probabilidad a priori denotada
por $\Pk(k)$. As\'{\i} ($\plain$,$2^{\plain}$,$\Pp$) modela
la elecci\'on de textos planos comunicados y ($\key$,$2^{\key}$,$\Pk$)
modela la elecci\'on de claves. Donde $2^{\plain}$ y $2^{\key}$ son el
conjunto de las partes de $\plain$ y $\key$ respectivamente.\\
\\
Vamos a considerar tres variables aleatorias $X,Y,K$, donde $X$ representa
el texto plano que ha sido encriptado, $Y$ el texto cifrado enviado y $K$
la clave escogida. Es natural asumir que $X$ y $K$ son variables aleatorias
independientes ya que el texto plano $x$ a enviar es un evento independiente
a la elecci\'on de la clave $k$ para el proceso de encripci\'on.\\
\\
Por \'ultimo, las distribuciones de probabilidad en $\plain$ y $\key$
induce una distribuci\'on de probabilidad $\Pc(y)$ ($y$ es el
texto cifrado) en $\cipher$ que se puede calcular usando los elementos de
probabilidades anteriormente vistos.\\
%--------------------------------------------------
%Por \'ultimo consideramos el espacio de probabilidades
%($\plain\times\key$,$2^{\plain\times\key}$,$p_{\plain\times\key$) que
%repesenta todos los posiblies texto planos y claves.\\
%--------------------------------------------------
\\
Estudiemos la siguientes cantidades

\renewcommand{\labelenumi}{(\roman{enumi})}
\begin{enumerate}
  \item $\Pp(x)=\Prob{X=x}$, la probabilidad a priori que se envie
	el texto plano $x$, donde $x\in\plain$

  \item $\Pk(k)=\Prob{K=k}$, la probabilidad que se elija una cierta
	clave $k$, donde $k\in\key$

  \item $\Pc(y)=\Prob{Y=y}$, la probabilidad que se envie el texto 
	cifrado $y$, donde $y\in\cipher$. Observar que
	$\Pc(y)=\Prob{(X,K)\in\{ (x,k) \,|\, e_{k}(x)=y \}}$.

  \item $\Pp(x|y)=\Prob{{X\!\!=\!\!x}\,\,|\,\,{Y\!\!=\!\!y}}$, la
        probabilidad que $x$ se haya encriptado dado que $y$ fue enviado.
        Notar que 
	$\Pp(x|y)=\Prob{X=x, K\in\{ k \,|\, e_{k}(x)=y\} }$ 
	  
  \item $\Pp(y|x)=\Prob{K \in \{ k \,|\, e_{k}(x)=y \} }$, la 
        probabilidad que $y$ se envie dado que $x$ se encripto. De la
	definici\'on de probalilidades condicionales sigue que
        \begin{displaymath} 
	   \Pp(y|x)=\frac{\Pp(x|y)\,\Pc(y)}{\Pp(x)}
        \end{displaymath}
 
        luego se tiene que         
        \begin{displaymath}
          \Pp(x|y)=\frac{\Pp(x)\Pc(y|x)}{\Pc(y)}
        \end{displaymath}

        De la independencia de las variables aleatorias $X$ e $Y$ se deduce
        que
        \begin{displaymath}
           \Pc(y)=
             \sum_{\stackrel{\{x\in\plain, k\in\key}{: \,\, e_{\key}(x)=y\}}}
                \Prob{X\!\!=\!\!x, K\!\!=\!\!k} =
             \sum_{\stackrel{\{x\in\plain, k\in\key}{: \,\, e_{\key}(x)=y\}}}
                \Pp(x)\,\Pk(k)
        \end{displaymath}
\end{enumerate}

Ahora podemos formalizar la noci\'on de ciptosistema perfectamente secreto.

\begin{definition}\label{perfecto} Criptosistema perfectamente secreto\\
 El criptosistema ($\plain,\cipher,\key,\encrip,\decrip$) es perfectamente
 secreto si $\Pp(x|y)=\Pp(x)$ para todo $x\in\plain, y\in\cipher$. Esto es,
 La probabilidad a posteriori que el texto plano sea $x$, dado que se obtiene
 el texto cifrado $y$, es identica a la probabilidad a priori que el texto
 plano sea $x$.
\end{definition}

Estudiemos la seguridad del criptosistema Af\'{\i}n.\\
\\
Recordemos que en el criptosistema Af\'{\i}n teniamos que
$\plain=\cipher=\modulo_{m}$ y
$\key = \{ (a,b) \in (\modulo_{m})^2 \,\, | \,\, mcd(a,m)=1 \}$. Ahora
calculemos $\Pp(x|y)$ usando el {\em teorema de Bayes} 
\begin{displaymath}
   \Pp(x|y)=\frac{\Pp(x) \Pc(y|x)}{\Pc(y)}
\end{displaymath}

La probabilidad $\Pc(y|x)=\Prob{ax+b = y \,\,mod\,\, m}$ es sobre la
elecci\'on de la tupla $(a,b)\in({\cal Z}_m)^2$ sujeto a que $mcd(a,m)=1$.
Suponiendo que la claves se eligen uniformemente y fijamos $a$, s\'olo hay
un valor $b\in{\cal Z}_m$ tal que $ax+b=y \,\,mod\,\, m$, por otro lado,
si fijamos $b$ entonces hay un valor de $a$ que cumple la misma condici\'on
pero el rango en que varia $a$ esta acotado por $mcd(a,m)=1$, luego
\begin{displaymath}
   \Pc(y|x)=\frac{1}{\phi(m)m}.
\end{displaymath}

donde $\phi(m)$ es la cardinalidad del conjunto
$\{a\in{\cal Z}_m:mcd(a,m)=1\}$ que depende del valor $m$

Por otro lado como las variables aleatorias $X$ e $Y$ son independientes
se tiene que
\begin{displaymath}
  \Pc(y)=\sum_{\stackrel{\{x\in\plain, k\in\key}{: \,\, e_{\key}(x)=y\}}}
         \Pp(x)\,\Pk(k)
\end{displaymath}

Usando el supuesto de la uniformidad de la distribuci\'on de probabilidades
$\Pk$ sobre $\key$, la expresi\'on anterior se puede escribir como 
\begin{displaymath}
  \Pc(y)=\frac{1}{\phi(m)m}\sum_{x\in\plain}\Pp(x)
\end{displaymath}

entonces; cada vez que se fija una clave, existe un solo texto plano que
cumple la condici\'on $e_{k}(x)=y$, o bien, cada vez que se fija un texto
plano, existe una sola clave que cumple la misma condici\'on, luego
$\sum_{x\in\plain} \Pp(x)=1$ entonces 
\begin{displaymath}
  \Pc(y)=\frac{1}{\phi(m)m}. 
\end{displaymath}

Hemos probado que $P_{\plain}(x|y)=P_{\plain}(x)$ esto significa que si
utilizamos una clave distinta para encriptar cada texto plano, el
criptosistema Af\'{\i}n es perfectamente secreto.

El ataque de la clase pasada (\#3), radica en el hecho que las claves se
utilizan rei\-te\-ra\-ti\-va\-men\-te para encriptar distintos textos plano.

\begin{proposition}\label{perfect}
  El criptosistema $(\plain,\cipher,\key,\encrip,\decrip)$ es perfectamente
  secreto si se cumple que $\Pc(y|x)=\Pc(y)$, para todo $x\in\plain$ y para
  todo $y\in\cipher$.
\end{proposition}
 
\begin{proof}
  De la \defref{perfecto}, perfectamente secreto significa que
         $\Pp(x|y)=\Pp(x)$. Luego del teorema de Bayes se puede escribir
  \begin{displaymath}
     \Pp(x) = \Pp(x|y) = \frac{\Pc(y|x)\Pp(x)}{\Pc(y)}
  \end{displaymath}
  
  Cancelando $\Pp(x)$ y reordenando t\'erminos en la expresion anterior
  se desprende que
  \begin{displaymath}
      \Pc(y)=\Pc(y|x)
  \end{displaymath}  
\end{proof}

Es natural asumir que $\Pc(y)>0$ para todo $y\in\cipher$, de lo contrario
el texto cifrado nunca se genera, entonces puede ser omitido del conjunto
$\cipher$. Luego en un criptosistema perfectamente secreto
$\Pc(y|x)=\Pc(y)>0$, por lo tanto para cada $y\in\cipher$ debe haber por lo
menos una clave $k\in\key$ tal que $e_{k}(x)=y$ luego $|\cipher|\leq|\key|$
(no se puede ocupar las mismas claves). Si la regla de encripci\'on no es
ambigua entonces $|\plain|\leq|\cipher|$. En el caso l\'{\i}mite donde
$|\key|=|\cipher|=|\plain|$ la siguiente proposici\'on no da una
caracterizaci\'on alternativa de lo que es un criptosistema perfectamente
secreto.

\begin{proposition}
  Sea $(\plain,\cipher,\key,\encrip,\decrip)$ un criptosistema donde
  $|\key|=|\cipher|=|\plain|$, entonces es perfectamente secreto si y s\'olo
  si cada clave es usada con igual probabilidad $1/|\key|$, y para todo
  $x\in\plain, y\in\cipher$ existe por lo menos una clave $k\in\key$ tal que
  $e_{k}(x)=y$. 
\end{proposition}

\begin{proof} Haremos la demostraci\'on en los dos sentidos separadamente\\
 
  \fbox{$\Rightarrow$} De la definici\'on de criptosistema perfectamente
  secreto se sabe que $\forall x\in\plain, \forall y\in\plain$ 
  existe $k\in\key$ tal que $e_{k}(x)=y$, luego $\forall x\in\plain$, se
  tiene que
  \begin{displaymath}
     |\cipher|=|\{ e_{k}(x) \,:\, k\in\key \}| = |\key|,
  \end{displaymath}

  \begin{figure}\label{biyeccion}
  \begin{center}
  \input{c4-f1}
  \end{center}
  \caption{Biyecci\'on entre los conjunto $\key$ y $\cipher$}
  \end{figure}

  entonces no existen dos claves distintas $k_1,k_2\in\key$ tal que 
  $e_{k_1}(x)=e_{k_2}(x)=y$, luego $\forall x\in\plain, \forall y\in\cipher$
  existe una sola clave $k\in\key$ que cumple $e_k(x)=y$. De esta forma
  hemos probado que hay una biyecci\'on entre el conjunto $\key$ y $\cipher$,
  (ver \figref{biyeccion}) formalmente
  \begin{displaymath}
     \forall x\in\plain, \forall y\in\cipher \,\,\exists! k\in\key \,\,
     {\rm que \,\, cumple} \,\, e_{k}(x)=y. 
  \end{displaymath}
    
  Ahora definimos la biyecci\'on $\Pi_{y}:\plain\longrightarrow\key$ tal que
  para cada $x\in\plain$ se asocia $k\in\key$ que cumple
  $e_{\Pi_{y}(k)}(x)=y$. Queremos calcular $\Prob{K=\Pi_y(x)}$, utilizando el
  hecho que el criptosistema es perfectamente secreto, de la \propref{perfect}
  se tiene que $\Pc(y|x)=\Pc(y)$ luego como $\Prob{K=\Pi_y(x)}=\Pc(y|x)$
  se cumple que
 
  \begin{displaymath}
     \Prob{K=\Pi_y(x)}=\Pc(y), \forall x\in\plain 
  \end{displaymath}
  
  considerando que existe una biyecci\'on entre el conjuto $\key$ y
  $\cipher$ la distribuci\'on de $\Pc$ es igual a la de $\Pk$ entonces
  se deduce que
  \begin{displaymath}
     \Prob{K=k}=\frac{1}{|\key|} 
  \end{displaymath} 
  %<=  
  \fbox{$\Leftarrow$} \\
  Sabemos que $\Pc(y|x)=\Pk(k\in\{k:e_k(x)=y\})$, luego como cada clave se
  usa con igual probabilidad se tiene que $\Pc(y|x)=1/|\key|$. Por otro
  lado, como vimos anteriormente, del {\em Teorema Bayes}  se sabe que 
  \begin{displaymath}
    \Pc(y)=\sum_{\stackrel{ \{x\in\plain,k\in\key}{:\,e_k(x)=y\} }}
      \Pp(x)\Pk(k)
  \end{displaymath}
  
  Ya que la elecci\'on de claves tiene una distribuci\'on uniforme se puede
  separar la suma de la expresi\'on anterior sacando un t\'ermino com\'un
  como sigue
  \begin{displaymath}
    \Pc(y)=
      \frac{1}{|\key|}
      \sum_{x\in\plain}\Pp(x)
      \sum_{\stackrel{\{ k\in\key}{:\,e_k(x)=y\}}} 1 
  \end{displaymath} 
 
  De la expresi\'on anterior se puede concluir que la suma
  $\sum_{x\in\plain}\Pp(x)$ representa todos los posibles valores que toma
  la variable aleatoria $X$, luego tiene el valor 1. La siguiente suma s\'olo
  tiene un t\'ermino que cumple la condici\'on $e_{k}(x)=y$ luego tambi\'en su
  valor es 1. As\'{\i} se obtiene que  
  \begin{displaymath}
    \Pc(y)=\frac{1}{|\key|}
  \end{displaymath}

  entonces, de esta \'ultima ecuaci\'on se concluye que
  \begin{displaymath}
    \Pc(y|x)=\Pc(y)
  \end{displaymath}
  
  As\'{\i}, de la \propref{perfect}, el cirtosistema es perfectamente
  secreto. 
\end{proof}

Un criptosistema que cumple la condici\'on de ser perfectamente secreto
es el llamado {\bf one-time Pad} inventado por Vernam (1917), quien lo
utiliz\'o para la encripci\'on y decripci\'on de mensajes telegr\'aficos.
Ahora lo describiremos formalmente

\begin{definition}\label{onetime}
  Criptosistema One-time Pad\\
  Sea el criptosistema $(\plain,\cipher,\key,\encrip,\decrip)$ done
  $\plain=\cipher=\key=({\cal Z}_2)^n$ con $n\geq 1$ entero, y una clave
  $k\in({\cal Z}_2)^n$. Se define $e_k(x)$ como la suma del
  vector $k$ y $x$ modulo 2 (o equivalentemente el OR-exclusivo entre
  estas cadenas de bit). De este modo, si $x=(x_1,...,x_n)$ y
  $k=(k_1,...,k_n)$ entonces, la funci\'on de encripci\'on es
  \begin{displaymath}
     e_k(x)=(x_1+k_1,...,x_n+k_n)\,\,{\rm mod}\,\,2  
  \end{displaymath}

  y la funci\'on de decripci\'on, si $y=(y_1,...,y_n)$ es
  \begin{displaymath}
     d_k(y)=(y_1+k_1,...,y_n+k_n)\,\,{\rm mod}\,\,2  
  \end{displaymath}
\end{definition}

Este criptosistema tiene seria limitaciones, por ejemplo; hay un serio
manejo de claves ya que hay problemas de sincronizaci\'on, se necesita
generar una gran cantidad de bits aleatorios, lo que es costoso. Si la clave
se genera utilizando bits pseudo-aleatorios entonces se habre la posibilidad
de atacar el criptosistema atacando el generador de bits pseudo-aletorios.
Por \'ultimo, $|\key|\geq|\plain|$, i.e. la clave es por lo menos tan larga
como toda la comunicaci\'on, sin enbargo la propiedad de ser
incondicionalmente seguro lo hace muy \'util en el contexto diplomatico o
militar. 

\end{document}


