\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}}}
\newtheorem{example}{Ejemplo}
\newcommand{\alpkey}{{\cal L}}
\newcommand{\maximo}[2]{max\{#1,#2\}}

% FIN LISTA DE MACROS PERSONALES

\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
\catedra{3}{13 de Agosto}{Alejandro Hevia}

% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI

\section{Costo Computacional Operaciones B\'asicas}

\begin{definition}
Diremos que un algoritmo que realiza c\'alculos que involucran
  enteros $n_{1},\ldots,n_{r}$ es polinomial o eficiente si existen
  $d_{1},\ldots,d_{r}$ enteros tal que el n\'umero de operaciones
  del algoritmo es:

\begin{center}
$O (lg(n_{1})^{d_{1}}\ldots lg(n_{r})^{d_{r}})$
\end{center}

\underline{Convenci\'on:} Salvo que se indique lo contrario,
  asumimos que todos los enteros se codifican en binario.
\end{definition}

El siguiente resultado nos ser\'a \'util en el resto de la
secci\'on.
\begin{proposition}
La cantidad de d\'{\i}gitos de la representaci\'on binaria (n\'umero
de bits) de un entero $n$ es $\lfloor lg(n) \rfloor +1$.
\end{proposition}
La demostraci\'on se deja como ejercicio.\\

Estimar el tiempo que se demora un algoritmo corresponde a 
  estimar el n\'umero de operaciones que realiza en funci\'on
  del tama\~no la entrada.\\

\begin{example}

Sumar dos n\'umeros de $k$ y $l$ bits\\
\begin{tabular}{crc}
\qquad & 1100101 & $\longleftarrow k$ bits\\
\qquad & \underline{10011} & $\longleftarrow l$ bits\\
\qquad & 1111000 & \\
\end{tabular}

Para realizar esta operaci\'on debemos recorrer ambos n\'umeros
  de derecha a izquierda e ir sumando bit a bit cada uno de sus
  d\'{\i}gitos. En el caso general, el n\'umero de sumas {\em bit a bit}
  efectuadas no ser\'a mayor que la cantidad de d\'{\i}gitos del mayor
  de ambos n\'umeros\footnote {Notar que la cantidad de bits de un
  n\'umero es una funci\'on no decreciente de \'el.}. En notaci\'on 
  de orden, esto significa que la operaci\'on toma $O (\maximo{k}{l})$
\end{example}

\newpage
\begin{example}
Multiplicar dos n\'umeros de k y l bits
\begin{tabbing}
------ \= - \= - \= - \= - \= - \= - \= - \= \kill
  \>\>\>\>\>1100101       $\longleftarrow$ k bits\\
  \>\>\>\>\>\underline{\quad 10011}       $\longleftarrow$ l bits \\
  \>\>\>\>\>1100101\\
  \>\>\>\>1100101\\
  \>\>\underline{\mbox{ 1100101}\qquad}\\
  \>\,\,\,\,\,\mbox{11101111111}\\
\end{tabbing}

Esta operaci\'on toma $O (k*l)$ operaciones binarias. Por ello, la 
multiplicaci\'on de dos enteros $n$ y $m$ tomar\'a
  $O ((\lfloor lg(m) \rfloor +1)(\lfloor lg(n) \rfloor +1))= O (lg(n)lg(m))$.

\begin{observation} En este caso s\'olo contamos las operaciones binarias
y consideramos el peor caso (hacemos la suma sobre enteros de k bits), 
debido a que nos interesa encontrar una 
estimaci\'on general del n\'umero de operaciones, lo cual debe ser 
independiente de caracter\'{\i}sticas circunstanciales de la entrada en
cuesti\'on.
\end{observation}
\end{example}

\begin{example}
N\'umero de operaciones necesarias para calcular $n!$\\

El c\'alculo de $n!$ requiere que en el $(j-1)-$\'esimo paso ($j=2,\ldots,n$)
  multipliquemos $j!$ por $(j+1)$. Acotaremos el n\'umero m\'aximo de bits
	requeridos en la representaci\'on binaria, de
  $j!$ por los bits requeridos en la representaci\'on binaria de $n!$. \\
Dado que el n\'umero de bits del producto de dos n\'umeros de $k$ y $l$ bits, 
  es a lo m\'as $kl$ bits, entonces el producto de n n\'umeros de $k$ bits
  ser\'a de a lo m\'as $nk$ bits. Si $n$ posee $k$ bits, cada entero positivo
  menor que $n$ poseer\'a menos de $k$ bits, luego $n!$ poseer\'a a lo sumo 
  $nk$ bits.\\
Si consideramos que $(j+1)$ tiene a lo m\'as $k$ bits, $j!$ tendr\'a $nk$ bits a lo sumo, luego como esta multiplicaci\'on se repite $(n-2)$ veces y
  $k=\lfloor lg(n)\rfloor +1$, el n\'umero de operaciones binarias es

\begin{center}
$O ((k(nk))(n-2)) = O (n^{2}(lg(n))^{2})$
\end{center}
\end{example}

Para otras operaciones usuales es posible determinar una cota para el
n\'umero de operaciones que demanda su realizaci\'on. Esta cota la 
denotaremos por $Tiempo(\cdot)$, donde el argumento es la operaci\'on
en referida.\\
Algunas cotas usuales se detallan a continuaci\'on:\\

\begin{enumerate}
\item $Tiempo(nm)= O(lg(n)lg(m))$
\item $Tiempo(n/m)= O(lg(n)lg(m))$
\item $Tiempo(n+m)= O(\maximo{lg(n)}{lg(m)})$
\item $Tiempo(ab)= O(n_{1}n_{2}((lg(m))^{2}+lg(min\{n_{1},n_{2}\})))$, donde 
  $a=\sum_{i=0}^{n_{1}}{a_{i}x^{i}}$, $b=\sum_{i=0}^{n_{2}}{b_{i}x^{i}}$ 
	y  $a_{i}, b_{i} \leq m$.
\item $Tiempo (\mbox{expresar n en base b})= O ((lg(n))^{2})$
\item $Tiempo (\mcd{a}{b}) = O ((lg(a))^{3})$ donde $a \ge b$.
\item $Tiempo (\mbox{encontrar $u,v$ tq. $\mcd{a}{b}=ua+vb$}) = 
  O ((lg(a))^{3})$ donde $a \ge b$.
\item $Tiempo (\sqrt{n}) = O ((lg(n))^{3})$. 
\end{enumerate}

\begin{exercise}
Demostrar la estimaci\'on de tiempo para $\sqrt{n}$.
\end{exercise}

Algunas mejoras:\\ 
\begin{enumerate}
\item $Tiempo(nm)= O(klg(k)(lg(lg(k)))$ con $k=\maximo{lg(n)}{lg(m)}$
  \qquad (ver \footnote{D.E.Knuth \em {Art of Computing Programming: 
	Seminumerical Algorithms} Vol. 2, 2da. ed., Addison Wesley, 
	Reading Massachusetts, 1981.}). 
\item $Tiempo(\mcd{a}{b}) = O ((lg(a))^{2})$ \qquad (ver \footnote{N. Koblitz 
	\em {A Course in Number Theory and Criptography}, p\'ag. 16, 2da. ed., 
	Springer-Verlag, 1994.} y el siguiente ejercicio).
\end{enumerate}

\begin{exercise}
{\em (a)} Pruebe que el siguiente algoritmo encuentra $d=\mcd{a}{b}$ 
	un n\'umero finito de pasos. Primero note que $\mcd{a}{b}=\mcd{|a|}{|b|}$
	luego, sin p\'erdida de ge\-ne\-ra\-li\-dad, podemos suponer que $a$ y $b$ son
	positivos. Si $a$ y $b$ son ambos pares, hacemos $d=2d^{\prime}$ con 
	$d^{\prime}=\mcd{a/2}{b/2}$. Si $a$ es impar y $b$ par, hacemos $d=d^{\prime}$
	con $d^{\prime}=\mcd{a}{b/2}$ (analogamente con $a$ par y $b$ impar). 
	Si $a$ y $b$ son impares distintos (con $a>b$ por ejemplo) hacemos
	$d=d^{\prime}$ con $d^{\prime}=\mcd{a-b}{b}$. Finalmente, si $a=b$,
	entonces hacemos $d=a$. El algoritmo se basa en repetir este 
	procedimiento hasta llegar al \'ultimo caso ($a=b$).\\
{\em (b)} Pruebe que el algoritmo de la parte {\em (a)} toma s\'olo 
	$O((lg(a))^{2})$ operaciones de bits (donde $a>b$).\\
{\em (c)} Por qu\'e este algoritmo (en la forma presentada) puede
	no ser preferible al al\-go\-rit\-mo de Euclides ?\\
\end{exercise}

\section{Criptoan\'alisis}

Corresponde a tratar de quebrar un criptosistema, lo cual entenderemos,
  por ahora, como tratar de determinar la clave $k$ usada en la encriptaci\'on
  de un texto plano $x$, conocido el texto cifrado $y$. \\
 
\underline{Principio:} Siempre asumiremos que el adversario Eva conoce el 
  criptosistema (algoritmo) utilizado.\\

Diferenciamos entre distintos tipos de ataques 
a un criptosistema (en orden creciente de fortaleza):

\renewcommand{\labelenumi}{(\roman{enumi})}
\begin{enumerate}
\item {\bf S\'olo texto cifrado} ({\em ciphertext only}): El adversario s\'olo
  ve el canal y el texto cifrado $y=y_{1}y_{2}\ldots y_{n}$. Es el tipo de 
	ataque m\'as d\'ebil y usualmente considera el supuesto que el mensaje 
	(texto plano) est\'a escrito en alg\'un lenguaje conocido.
\item {\bf Texto plano conocido} ({\em know plaintext}): El adversario conoce
  $x=x_{1}x_{2}\ldots x_{n}$ y $y=y_{1}y_{2}\ldots y_{n}$ (pero el 
  adversario {\em no} elige $x$).
\item {\bf Texto plano elegido} ({\em chosen plaintext}): El adversario tiene acceso al
  mecanismo de encripci\'on, donde puede elegir
  $x=x_{1}x_{2}\ldots x_{n}$ y calcular $y=y_{1}y_{2}\ldots y_{n}$. El
	poder de este ataque se basa en que es posible elegir el texto plano 
	de manera de disminuir ciertos efectos de la encripci\'on y as\'{\i}
	obtener informaci\'on acerca de la clave.
\item {\bf Texto cifrado elegido} ({\em chosen ciphertext}): El adversario
  tiene acceso al me\-ca\-nis\-mo de decripci\'on y puede elegir 
  $y=y_{1}y_{2}\ldots y_{n}$ y calcular $x=x_{1}x_{2}\ldots x_{n}$. 
	Este tipo de ataque es especialmente relevante en los criptosistemas
	de llave p\'ublica.
\end{enumerate}

\underline{Ilustraciones:}\\
{\bf 1.} Ataque de texto cifrado en el criptosistema Af\'{\i}n.\\

Ten\'{\i}amos $\plain = \cipher = \modulo_{m}$, donde
\begin{eqnarray*}
\key & = & \set{(a,b) \in \modulo_{m}\times \modulo_{m}}{ \mcd{a}{m}=1 }\,. 
\end{eqnarray*}
Con las funciones de encripci\'on y decripci\'on 
\begin{eqnarray*}
e_{K}(x) & = & (a\,x + b) \bmod m \\
d_{K}(y) & = & a^{-1}\,(y - b) \bmod m
\end{eqnarray*}

Si asumimos que conocemos
\begin{displaymath}
\Pi\Colon  \modulo_{m} \to [0,1] \,\,tq \,\, \sum_{i \in \modulo_{m}}{\Pi(i)} = 1
\end{displaymath}

donde $\Pi(i)$ es la frecuencia relativa con que $i \in \modulo_{m}$ 
  aparece en un mensaje t\'{\i}pico, o en el lenguaje que est\'a escrito el 
  mensaje\footnote{Usualmente la frecuencia de aparici\'on de letras,
  pares de letras o trios de letras.}.\\

Conocido $y=y_{1}y_{2}\ldots y_{n}$ determinamos 

\begin{displaymath}
\Pi_{y}\Colon  \modulo_{m} \to [0,1] \,\,tq \,\, \sum_{i \in \modulo_{m}}{\Pi_{y}(i)} = 1
\end{displaymath}

donde $\Pi_{y}(i)$ es la frecuencia relativa con que $i \in \modulo_{m}$ 
  aparece en el texto cifrado $y$.\\
Elegimos $s,t \in \modulo_{m}$ tales que 

\begin{displaymath}
\Pi (s) \ge \Pi (t) \ge max_{i\in \modulo_{m}\backslash\{s,t\}}\,\Pi_{x \in \modulo_{m}}(x)
\end{displaymath}

i.e. los dos valores que maximizan $\Pi$.
Luego hacemos lo mismo para elegir $s^{\prime},t^{\prime} \in \modulo_{m}$ 
con respecto a $\Pi_{y}$. Con esto, resolvemos 

\begin{eqnarray*}
s^{\prime} & = & (a\,s + b) \bmod m\\
t^{\prime} & = & (a\,t + b) \bmod m
\end{eqnarray*}

obteniendo,
\begin{eqnarray*}
s^{\prime} - t^{\prime} & = & a\,(s - t) \bmod m
\end{eqnarray*}

De aqu\'{\i} existen tres casos:
\begin{enumerate}
\item Existe un \'unico valor para $a$ tal que $\mcd{a}{m}=1$ y
con el determinamos $b$. Basta verificar que el mensaje 
decriptado con esta llave ($a$,$b$) tenga sentido. Si as\'{\i} es,
hemos quebrado el criptosistema. 
\item Existen varios valores posibles para $a$. Luego, fall\'o la 
suposici\'on de que $s^{\prime}$ es la codificaci\'on de $s$. 
Elegimos otro valor para $s$ (o bien para $t$) 
dentro de los elementos de maximizan $\Pi$ sobre
$\modulo_{m}\backslash S$, donde $S$ contiene a los elementos 
de $\modulo_{m}$ ya probados. Luego, iteramos. 
\item $s - t$ no es invertible en $\modulo_{m}$, lo que indica que fall\'o 
alguna suposici\'on (acerca de $s$ o $t$). 
Luego elegimos seg\'un lo se\~nalado en el punto anterior e iteramos.
\end{enumerate}

{\bf 2.} Ataque de texto plano conocido en el criptosistema de chorro\\

Ten\'{\i}amos $\plain = \cipher = \alpkey = \modulo_{2}$, con
\begin{eqnarray*}
\key & = & ( \modulo_{2} )^{m} \setminus \{(0,\ldots,0)\}
\end{eqnarray*}

donde definimos 
\begin{eqnarray*}
z_{i+m} & = & (\sum_{j=0}^{m-1}{c_{j}\,z_{i+j}}) \bmod 2
\end{eqnarray*}
y $c_{0},c_{1},\ldots,c_{m-1} \in \modulo_{2}, c_{0} \ne 0$
  para las funciones de encripci\'on y decripci\'on 
\begin{eqnarray*}
e_{z}(x) & = & (x + z) \bmod m\,, \\
d_{z}(y) & = & (y + z) \bmod m\,.
\end{eqnarray*}

Supongamos que Eva conoce $x_{1},x_{2},\ldots,x_{n}$ y
  $y_{1},y_{2},\ldots,y_{n}$. Entonces ella puede calcular: 
\begin{eqnarray*}
z_{i} & = & (x_{i} + y_{i}) \bmod 2\,,\qquad i=\,1,\ldots,n\,.
\end{eqnarray*}

Si asumimos que $m$ es conocido por el adversario, y se tiene
que $n > 2m$, entonces

\begin{displaymath}
(z_{m+1}\,\ldots z_{2m}) = 
\underbrace{(c_{0}\,\ldots c_{m-1})}_{C}\, 
\underbrace{
\left(
\begin{array}{cccc}
z_{1} & z_{2} & \ldots & z_{m} \\
z_{2} & z_{3} & \ldots & z_{m+1} \\
\vdots & \vdots & \ddots & \vdots \\
z_{m} & z_{m+1} & \ldots & z_{2m-1} \\
\end{array} \right)
}_{Z}
\end{displaymath}
donde la aritm\'etica es en $\modulo_{2}$. \\
Es posible demostrar que $Z$ es invertible. Con ello, podemos
obtener

\begin{eqnarray*}
C & = & (z_{m+1}\,\ldots z_{2m}) \, Z^{-1}\,. 
\end{eqnarray*}
Con lo cual recuperamos, los coeficientes $c_{0}\,\ldots c_{m-1} \in \modulo_{2}$ 
que generan la clave $z$ del criptosistema.

\begin{exercise}
Demuestre que la matriz $Z \in M_{m}(\modulo_{2})$ es invertible. 
  Para ello, demuestre que las filas de esta matriz son vectores
  linearmente independientes sobre $\modulo_{2}$.\\

{\em (a)} Sea 
$\qquad v_{i} = (z_{i},\ldots,z_{i+m-1})\,,\qquad i \ge 1\,.$\\

Pruebe que, para todo $i \ge 1$,
\begin{eqnarray*}
v_{m+i} & = & (\sum_{j=0}^{m-1}{c_{j}\,v_{i+j}}) \bmod 2
\end{eqnarray*}

{\em (b)} Elija $h$ de manera que sea el m\'{\i}nimo entero tal que
existe una combinaci\'on lineal no trivial de los vectores 
$v_{1},\ldots,v_{h}$ que suma el vector nulo (mod 2). Entonces

\begin{eqnarray*}
v_{h} & = & (\sum_{j=0}^{h-2}{\alpha_{j}\,v_{j+1}}) \bmod 2
\end{eqnarray*}
donde los $\alpha_{j}$ no son todos cero. Notar que $h \leq m+1$ 
pues cualesquiera $m+1$ vectores en un espacio $m-$dimensional
son linealmente dependientes. \\

{\em (c)} Pruebe que los $z^{\prime}$s de la clave deben satisfacer la
recurrencia lineal
\begin{eqnarray*}
z_{h-1+i} & = & (\sum_{j=0}^{h-2}{\alpha_{j}\,z_{j+i}}) \bmod 2
\end{eqnarray*}
para todo $i \ge 1$.

{\em (d)} Observe que si $h \leq m$ los $z^{\prime}$s de la clave
satisfacen una recurrencia lineal de grado menor que $m$, una 
contradicci\'on. Luego, $h=m+1$, y la matriz debe ser invertible.
\end{exercise}

\section{Seguridad Incondicional}

Existen dos tipos de seguridad que estudiaremos:
\begin{definition} 
\underline{Seguridad Computacional}\\
Tiene que ver con los requisitos computacionales necesarios para
  quebrar un criptosistema. Diremos que un criptosistema es 
  {\em computacionalmente seguro} si el mejor algoritmo para quebrarlo
  requiere a lo menos $N$ operaciones, donde $N$ es un n\'umero espec\'{\i}fico
  muy grande.\\
No sabemos como probar que un criptosistema tiene este nivel de seguridad
  por lo que usualmente s\'olo se prueba que quebrar un criptosistema es 
  equivalente a resolver un problema bien conocido que se piensa es dif\'{\i}cil.
\end{definition}

\begin{definition}
\underline{Seguridad Incondicional}\\
Un criptosistema es {\em seguro incondicionalmente} si es imposible de 
  quebrar aunque se utilice una cantidad infinita de recursos computacionales.
\end{definition}

\end{document}
-----------> cut here <---------------------


