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

% 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{19}{29 de Octubre}{Jens Hardings}


% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI

\newcommand{\sig}{{\cal S}}
\newcommand{\ver}{{\cal V}}
\newcommand{\csig}{{\cal A}}
\newcommand{\bitset}{\lbrace 0,1 \rbrace}

\section{Firmas Digitales}

Antes de abordar directamente el tema de las firmas digitales, es \'util definir
qu\'e es lo que esperamos de ellas, y para ello veamos primero por qu\'e se
utilizan las firmas convencionales:

\begin{enumerate}
\item Autentificaci\'on, i.e. convencer al lector de un documento que \'este
      tuvo su origen en el firmante.
\item Para evitar falsificaciones.
\item No reusables, i.e. no se puede usar la misma firma en otro documento.
\item El documento firmado no se puede alterar.
\item No Repudiaci\'on: al firmar un documento, el emisor no puede negar
      haberlo enviado.
\end{enumerate}

Las caracter\'{\i}sticas enumeradas arriba son las deseables para cualquier
sistema ideal de firmas. En la pr\'actica, los sistemas convencionales de
firmas utilizados no satisfacen todas ellas. A pesar de esto \'ultimo,
dan un grado de seguridad aceptable, dada la dificultad y el riesgo que
implica el falsificar una firma.

Es interesante implementar un sistema de firmas para documentos
o mensajes digitales, de donde surge el concepto de \emph{firmas digitales}.
En este proceso, surgen diferencias sustanciales, dada la naturaleza del
sistema. Por ejemplo, en un sistema de firmas digitales la firma debe ser una
secuencia de bits, para que pueda formar parte del mensaje. Como los bits se
pueden reproducir trivialmente, es imposible evitar que se saquen copias a
documentos firmados. En el caso de un sistema convencional es m\'as f\'acil de
evitar, ya que al copiar un documento, la firma pierde validez. Por ejemplo,
al fotocopiar un documento se puede apreciar la diferencia entre la firma
original y la fotocopia.

\pagebreak
Dadas las diferencias notables entre el sistema tradicional y uno digital,
es necesario plantearse algunas preguntas:

\begin{itemize}
\item ?` c\'omo evitar copias ?
\item ?` c\'omo ``pegar'' las firmas a un documento/archivo ?
\item ?` c\'omo hacer una firma universalmente verificable ?
\end{itemize}

En base a lo anterior, diremos que los requisitos b\'asicos de
un sistema digital que pretenda emular las firmas tradicionales son:

\begin{enumerate}
\item La firma debe depender del documento a ser firmado.

Si no dependiese del documento, ser\'{\i}a trivial que cualquier persona firme
un documento a nombre de otra (recordar que una firma digital ser\'a una
secuencia de bits).

\item La firma debe depender (parcialmente) de informaci\'on que es privada
      a quien firma.

Debe depender de informaci\'on secreta para evitar copias, pero adem\'as
debe permitir verificar el origen del documento (no repudiaci\'on).

\item Debe ser f\'acil producir y verificar una firma.
Aqu\'{\i} existe un compromiso entre la eficiencia de la implementaci\'on y
la seguridad que ofrecer\'a el sistema.

\item Las firmas deben ser computacionalmente dif\'{\i}ciles de falsificar.
Esto para evitar dos tipos de ataques:
  \begin{itemize}
  \item crear un mensaje para una firma existente.
        En el caso general, este ataque es menos importante, dado que
	t\'{\i}picamente el mensaje generado no tendr\'a sentido. Pero hay
	casos en que esto puede ser bastante grave, si se llega a cambiar
	el monto de un cheque, por ejemplo.
  \item crear una firma para un mensaje dado.
        Este caso es m\'as cr\'{\i}tico que el anterior, dado que al estar
	expuestos a un ataque de este tipo, se pierde toda la confiabilidad
	en el sistema.
  \end{itemize}
\item Deben ser f\'aciles de guardar, para poder autentificarlas en el momento
que se necesite.
\end{enumerate}

\section{Firmas basadas en Criptosistemas Sim\'etricos}

Este tipo de firmas est\'an basadas en un criptosistema cl\'asico o
sim\'etrico, y adem\'as se supone la existencia de un \'arbitro en el que todos
los participantes conf\'{\i}an, que denotaremos por $T$ (Trusted).

Entonces, tenemos un criptosistema $(\plain, \cipher, \key, \encrip, \decrip)$,
donde $e_K$ es la funci\'on de encripci\'on y $d_K$ su correspondiente
funci\'on de decripci\'on para una clave $K$ dada. Cada participante en el
sistema tendr\'a su propia clave secreta, la cual ser\'a conocida por $T$ y el
participante mismo.

Queremos construir un protocolo entre $A$ y $B$, donde $A$ tiene la clave
$K_a$ y $B$ tiene la clave $K_b$. Adem\'as, introducimos una estampa de tiempo
(Timestamp) $T_m$, la cual tiene por objeto dar informaci\'on adicional
sobre el momento de la firma del documento.

El protocolo queda como sigue:
\begin{enumerate}
\item $A:$ genera el mensaje $M$ a enviar y le entrega a $M$ el mensaje
      concatenado con la firma:
      \[A \rightarrow T: M \circ e_{K_{a}}(M).\]
\item $T:$ verifica que la segunda parte del mensaje corresponde realmente
      a la firma de $A$, i.e. debe verificar que $d_{K_a}(M) = M$. Si la firma
      no corresponde al mensaje, significa que no fue $A$ el que mando el
      mensaje y se termina.
\item $T:$ transmite el mensaje recibido de $A$ (incluyendo la firma),
      concatenado con $T_m$, todo esto encriptado usando la clave $K_b$:
      \[T \rightarrow B: e_{K_{b}}(M \circ e_{K_{a}}(M) \circ T_m).\]
\item $B:$ decripta lo anterior y obtiene el mensaje de $A$ con su respectiva
      firma y estampa de tiempo:
      \[B: M \circ e_{K_a}(M) \circ T_m.\]
\end{enumerate}

\pagebreak
Veamos ahora c\'omo verificar que $A$ realmente firm\'o el mensaje $M$. Para
ello, supongamos que $B$ quiere convencer a otro participante, $C$, de que
$A$ le mand\'o el mensaje $M$:

\begin{enumerate}
\item $B$: le env\'{\i}a el mensaje que recibi\'o anteriormente:
      \[B \rightarrow T: e_{K_b}(M \circ e_{K_a}(M) \circ T_m).\]
\item $T$: decripta ese mensaje, obteniendo $M \circ e_{K_a}(M) \circ T_m$.
      Luego, verifica que $e_{K_a}(M)$ corresponda a la firma de $A$ para el
      mensaje $M$, i.e. que el mensaje provino originalmente de $A$, y
      transmite el mensaje a $C$:
      \[T \rightarrow C: e_{K_c}(M \circ e_{K_a}(M) \circ T_m).\]
\item $C$: recibe el mensaje anterior y descifrando obtiene:
      \[C: M \circ e_{K_a}(M) \circ T_m.\]
\end{enumerate}

Despu\'es de este proceso, $C$ puede estar seguro de que $A$ le mand\'o el
mensaje $M$ a $B$, y dependiendo de la informaci\'on que contenga $T_m$,
tambi\'en podr\'a saber cu\'ando se envi\'o el mensaje, o cuantas veces se
ha validado, etc.

\begin{observation} impl\'{\i}citamente, para que el sistema funcione de la
  forma presentada, $T_m$ debe satisfacer ciertas propiedades. Por ejemplo,
  un cliente no debe ser capaz de generar una estampa de tiempo v\'alida para
  un documento dado, ya que as\'{\i} podr\'{\i}a alterar la fecha, y
  por lo tanto la validez de un documento.
\end{observation}

\subsection{Problemas con este sistema}

El principal problema que presenta este sistema es el \'arbitro $T$, y esto
por varias razones. Al tratar de implementar este sistema, uno de los primeros
puntos a tratar ser\'a el c\'omo encontrar un $T$ en el que todos los clientes
conf\'{\i}en, cosa muy dif\'{\i}cil en la pr\'actica. $T$ debe ser completamente
confiable para todos los clientes, puesto que si da a conocer o alguien le roba
informaci\'on, el sistema completo queda inservible, al perder toda la
confiabilidad. Ahora, si suponemos que podemos encontrar este $T$, que es
completamente seguro y confiable, tenemos que ,como toda operaci\'on pasa a
trav\'es de $T$, y suponemos que habr\'a una gran cantidad de clientes, $T$
deber\'a tener una gran capacidad computacional para cumplir con todos los
requerimientos que le lleguen. Si no puede procesar los requerimientos a la
velocidad que llegan, se convertir\'a autom\'aticamente en un ``cuello de
botella'', y todos los clientes tendr\'an que esperarlo antes de poder
interactuar con otros.

\section{Firmas basadas en criptosistemas de clave p\'ublica}

Las exigencias m\'as b\'asicas que le podemos hacer a un criptosistema de
firmas est\'an dadas por la siguiente definici\'on:

\begin{definition} Un sistema de firmas digitales p\'ublicas es una tupla
  $(\key,\sig,\ver)$ donde
\begin{enumerate}
\item $\key$ es un conjunto de claves.
\item dada una clave $k \in \key$, existen los conjunto $\plain_{k}$ y
      $\csig_{k}$, y las funciones de firma $S_k$ y de verificaci\'on $V_k$
      tal que:
      \begin{itemize}
      \item $S_k : \plain_k \rightarrow \csig_k$
      \item $V_k : \plain_k \times \csig_k \rightarrow \bitset$
      \item dado cualquier $x \in \plain_k$ se tiene que $V_k(x,y)=1$ si y
            s\'olo si $S_k(x)=y$.
      \end{itemize}
\item $V_k$ es p\'ublica y $S_k$ es privada.
\end{enumerate}
\end{definition}

Para que un sistema de firmas sea implementable computacionalmente, se
requiere la existencia de algoritmos eficientes para calcular $S_k$ y $V_k$.
Claramente, la seguridad de un sistema como el anterior debe estudiarse en el
contexto de la seguridad computacional.

Adem\'as, es importante hacer notar que puede necesitarse algo m\'as que este
sistema basado en criptosistemas de clave p\'ublica. Ello queda m\'as claro
con un ejemplo: supongamos que Alicia le manda a Roberto un cheque, el cual
firma electr\'onicamente. Entonces, Roberto lo puede cobrar en el banco y
mantener una copia en su poder, la cual podr\'{\i}a reutilizar en otro
momento. Si se incluye una estampa de tiempo dentro del documento, se
puede evitar este tipo de enga\~nos.

\subsection{Sistemas de firmas de una vez}
%
Los sistemad de firmas de una vez (one-time signature schemes).
Como su nombre lo dice, son sistemas donde la clave se puede utilizar una
sola vez.

\subsubsection{Sistema de firmas de Lamport}

\underline{Supuesto:} existe una funci\'on $f:\bitset^* \rightarrow \bitset^*$
de un sentido fuerte.

$\key = \set{(y,z)}{y \in M_{2,m}(\bitset^n)\ tal\ que\ f(y_{i,j}) = z_{i,j}}$.
\[ 
{\rm Si}\ (y,z) \in \key\ ,\ \ \ 
y = \left( \begin{array}{ccc}
y_{0,1} & \cdots & y_{0,m}\\
y_{1,1} & \cdots & y_{1,m}\\
\end{array} \right) \ \
z = \left( \begin{array}{ccc}
z_{0,1} & \cdots & z_{0,m}\\
z_{1,1} & \cdots & z_{1,m}\\
\end{array} \right). \]

Dada un clave $K = (y,z)$, la parte p\'ublica ser\'a $z$; $y$ es privada.
Para un mensaje $M = i_1 i_2 \dots i_m$ con $i_k \in \lbrace 0,1 \rbrace$,
la funci\'on de firma es
\[S_k (i_1 i_2 \dots i_m) = y_{1,i_1} \dots y_{m,i_m},\]
y la funci\'on de verificaci\'on:
\[V_k (i_1 i_2 \dots i_m,y_1 y_2 \dots y_m) = \left\{
\begin{array}{l} 1\ {\rm si}\ \forall j=1 \dots m\ f(y_j) = z_{i_j,j}\\
0\ {\rm si\ no}\\
\end{array} \right . \]
Notar que la funci\'on $f$ debe ser p\'ublica tambi\'en, para poder verificar
cada firma. Con este sistema, un adversario no podr\'a falsificar una firma a
menos que pueda calcular preim\'agenes de $f$.

Una desventaja que se presenta es que se requiere una nueva clave por cada
firma, dado que una vez que se firma un documento, se est\'a entregando
la mitad de las preim\'agenes de $f$ para esa clave.  Adem\'as, tenemos que
la firma es $n$ veces m\'as larga que el mensaje original, y nos interesa que
las firmas sean f\'aciles de guardar.

Este sistema fue modificado por Bose y Chaum, llegando a firmas digitales de
aproximadamente la mitad del largo de las de Lamport.

\end{document}


