\documentstyle{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 $2^{da}$ C\'atedra #1 \hfill} }
       \vspace{2mm}
       \hbox to 6in { {\it Transcriptor: #2 \hfill} }
      }
   }}
   \end{center}
   \markboth{$2^{da}$ C\'atedra #1}{$2^{da}$ C\'atedra #1}
   \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{de Sistemas de firmas Digitales}{Miguel Barrera M.}

% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI

\section{Sistema de firmas digitales}
%

Veremos un sistema de firmas digitales basado en el criptosistema de El Gamal,
en el cual la firma digital se puede expresar como
\begin{itemize}

\item $\key$ =
\{($p$,$g$,$a$,$\beta$) $\vert$ $p$ primo, $g$ generador de $\modulo_{p}^{*}$ y $\beta$ $\equiv_{p}$ $g^{a}$\}

\end {itemize}


En la definici\'on anterior, las claves p\'ublicas 
son $g$,$b$ y $p$ y la clave secreta es $a$. \\




{\large \textbf {Uso del sistema de firmas de El Gamal}}\\




En el sistema de firmas basado en El Gamal, en el proceso de firmar un documento
se tiene que:

$\forall$ $\key$ = ($p$,$g$,$a$,$b$)

si se desea firmar $x$ $\in$ $\modulo_{p}^{*}$ se elige $j$ $\in$ $\modulo_{p-1}$
al azar y se genera ($\gamma$,$\delta$) donde

$\gamma$ = $g^{j}$ mod $p$

$\delta$ = ($x$ - $a \gamma$) $j^{-1}$ mod ($p$-1)

para verificar que ($\gamma$,$\delta$) es firma de $x$ se chequea lo siguiente:

$\beta^{\gamma}$ $\gamma^{\delta}$ $\equiv_{p}$ $g^{x}$

\textbf{Observaci\'on }

para toda firma v\'alida se cumple que

$\beta^{\gamma}$ $\gamma^{\delta}$ $\equiv$  $g^{a \gamma + j \delta}$ 
$\equiv_{p}$  $g^{a \gamma + x - a \gamma}$ $\equiv_{p}$ $g^{x}$


Cabe decir que no se conocen formas computacionalmente eficientes de falsificar
una firma de El Gamal para un mensaje conocido dado
pero se puede generar $x$ y  ($\gamma$,$\delta$) firma v\'alida para $x$, i.e.:

$\gamma$ = $g^{i}$ $b^{i}$ mod $p$

$\delta$ =  $-\gamma$ $j^{-1}$ mod ($p$-1)

$x$ = $-\gamma$ $i$ $j^{-1}$ mod ($p$-1)

donde $i$ $\in$ $\modulo_{p}$ y  $j$ $\in$ $\modulo_{p-1}^{*}$

luego se tiene que


$\beta^{\gamma} \gamma^{\delta}$ $\equiv_{p}$
$g^{a \gamma} g^{(i+aj)\delta}$ $\equiv_p$ 
$g^{a \gamma + i \delta + a j \delta}$ $\equiv_{p}$
$g^{a \gamma - \gamma i j^{-1} - a \gamma}$ $\equiv_{p}$ $g^{x}$


Este proceso genera una firma v\'alida de algun texto
pero ya que no se puede elegir este sino s\'olo los numeros
que dan origen a una firma v\'alida, el mensaje correspondiente
a esta firma es initeligible.


Una de desventajas que tiene este m\'etodo de firmas digitales
basado en el criptosistema de El Gamal
es que la firma de un mensaje cualquiera queda del doble 
del tama\~no de los primos elegidos, asi por ejemplo si los primos son de 512 
bits (que es lo est\'andar por seguridad) entoces la firma queda 
de 1024 bits, lo cual se aleja mucho de ser \'optimo, debido a que 
involucra enviar un texto de tama\~no considerable a trav\'es de la 
red, para cada mensaje; lo cual es engorroso para el firmante y para 
el destinatario.

Veremos a continuaci\'on el sistema de firmas DSS (tambi\'enbasado en 
El Gamal) utiliza firma mas peque\~nas, que las del m\'etodo anterior.

\section{DSS (digital signature standard)}

Es una variacion de sistema de firmas digitales normal basado en El Gamal.
Este nuevo sistema utiliza primos de 512 bits (al igual que el anterior) 
sin embargo genera firmas de 320 bits.

Esta mejora se consigue considerando que ahora 
$\gamma$ ya no esta en $\modulo_{p}$ si no en un subgrupo 
ciclico suficientemente grande de este. Se ha especulado que quebrar este 
sistema de firmas es un problema de similar dificultad
que resolver el problema del logaritmo discreto.

\newpage

\section{Otros sistemas de firmas}

Ahora enunciaremos brevemente otros sistemas de firmas

\begin{itemize}

\item Firmas no repudiables

Estas firmas poseen la caracter\'{\i}stica de que 
no pueden ser verificadas sin la colaboraci\'on del firmante.
Esto sirve mucho para evitar chantajes, al no dejar que terceros
verifiquen firmas hechas sin el consentimiento del firmante.

\item Firmas fail-stop 

Mecanismo de firmas digitales que ademas de una firma cuenta con un algoritmo 
de demostraci\'on de firmas falsas.
Para este sistema se pueden hacer firmas que pasen el test de verificaci\'on
pero el sistema de demostraci\'on de firmas falsa que posee permite saber
que para determinada firma generada por un adversario el autor original
de la firma la detecte como falsa.


\item Firmas de grupo

Sistema de firmas que hacen que un grupo posea una sola firma.
Esta firma se puede generar en un porceso que involucra a $n$ personas
que forman parte del grupo, y para firmar se necesita la colaboraci\'on 
de estas $n$ personas tambi\'en. 

\item Firmas umbral

Es un sistema de firmas de grupo en que se requiere de la participacion 
de un umbral de $t$ personas de un total de $n$ para poder efectuar una firma.


\end{itemize}


\section{Seguridad de un sistemas de firmas digital}

Una definici\'on que se presta mejor para estudiar la seguridad
de un sistema de firmas digitales es la siguiente
Un sistema de firmas digitales es una tripleta $(G,\sigma,D)$ tal que

\begin{itemize}

\item El algoritmo de generaci\'on ($G$) 

Es un algoritmo probabilista a tiempo polinomial
que en la entrada $1^{k}$ produce una clave p\'ublica de firmas denotada $P$ 
y una clave privada denotada $S$

\item El algoritmo de firma ($\sigma$) 

Es tambi\'en un algoritmo probabilista a tiempo 
polinomial que en la entrada $1^{k}$ y un mensaje $m$ $\in$ $\{0,1\}^{k}$ 
y la clave secreta $S$, entrega $s$ la firma de $m$.


\item El algoritmo de verificaci\'on ($V$) 

Es un algoritmo probabilista a tiempo polinomial que en la entrada $P$ 
(clave p\'ublica), 
un mensaje $m$ y una suspuesta firma $s$, 
produce un 1 o 0 dependiendo si la firma es v\'alida o no, o lo que es igual 
si $s$ $\in$ $\sigma$ ($1^{k}$,$n$,$S$) el algoritmo genera un 1.


\end{itemize}

\section{Tipos de ataque para sistemas de firmas}

Existen varios posibles tipos de ataques 

\begin{itemize}

\item Ataque de clave p\'ublica

El adversario s\'olo conoce la clave p\'ublica de la persona a plagiar.
La clave p\'ublica es el m\'{\i}nimo de informacion que tiene que obtener
el adversario para efectuar un ataque, cuando no es posible obtener m\'as
puede ser debido a que el firmante original, encripta los mensajes despu\'es
de haberlos firmado.

\item Ataque de firma conocida

El adversario posee $n$ pares de mensajes con sus respectivas firmas
pero no son mensajes de su elecci\'on.
Esto ocurre cuando el adversario se ha dedicado a coleccionar pares de
mesajes-firmas del firmante original, intercept\'andolos en la red o mediante
alg\'un otro medio.

\item Ataque de mensaje elegido 

El adversario puede elegir los mensajes que el desee (en forma adaptativa) 
y puede obtener las firmas para ese mensaje del firmante real.
Este es el caso, por ejemplo, de pedirle al firmante que firme un texto que
el adversario desee, lo cual ocurre cuando el firmante es notario o algo
similar.

\end{itemize}

\newpage

\section{Definici\'on de falsificaci\'on}

Hasta ahora no hemos definido que concepto se engloba en el t\'ermino 
falsificaci\'on

Para esto vamos a dar a conocer primero todos los tipos de de falsificaci\'on
existentes.

\begin{itemize}

\item Falsificaci\'on existencial, 

Un adversario produce una firma v\'alida a un mensaje 
que no es de su elecci\'on

\item Falsificaci\'on selectiva

El adversario produce una firma a un mensaje que es de su elecci\'on.

\item Falsificaci\'on universal

El adversario puede producir una firma v\'alida de cualquier mensaje.
(No necesariamente descubre la clave secreta del firmante original)

\end{itemize}


\section{Concepto de seguridad de un sistema de firmas digitales}


Para definir seguridad de un sistema de firmas digitales, primero veamos 
lo que es un algoritmo de falsificaci\'on.

Un algoritmo de falsificaci\'on $F$ probabil\'{\i}stico, 
que usa al firmante real como "or\'aculo"
(el adversario puede obtener pares mensaje-firma, de cualquier mensaje 
elegido) es tal que puede en tiempo polinomial al tama\~no de la clave p\'ublica
generar una firma de cualquier mensaje cuya firma no haya sido
obtenida del firmante real. Denotemos como $B$ al or\'aculo 
entonces el algoritmo que usa este or\'aculo ser\'a $F^{B}$.

Este algoritmo tiene como entrada una clave publica de firmas $P$ y 
produce un mensaje $m$ y su supuesta firma $s$.


Decimos que $(G,\sigma,D)$ es un sistema de firmas digitales seguro si

$\forall$ $F$ (algoritmo de falsificaci\'on)
$\exists$ $\nu_{F}$ 
funci\'on despreciable, tal que  $\forall$ $k$ suficientemente grande:

Pr$[V(P,m,s)=1 \vert (P,\delta) \gets G(1^{k}), (n,\delta) \gets F^{B}(P)]$
$\le$ $\nu_{F}(k)$

\newpage

\section{An\'alisis de los algoritmos vistos}


Seg\'un nuestras nuevas definiciones veamos que tan seguros son 
los sistemas de firmas digitales vistos hasta ahora.

\begin{itemize}

\item El Gamal 

Este sistema no es seguro deacuerdo a las definiciones anteriores pues es 
existencialmente falsificable.


\item RSA 

Las firmas por RSA tampoco son seguras debido a que son universalmente 
fasificable porque $\sigma(n1)$ $\cdot$ $\sigma(n2)$ $\equiv_{n}$ 
$\sigma(n1 \cdot n2)$


\item Sistema de Diffie-hellman 

El trabajo fundacional de Diffie-Hellman en el cual se necesita
poseer una colecci\'on de funciones de puerta secreta
$F$ = $\{f_{i}\}_{i \in I}$ para firmar un texto, i.e.:

\begin{itemize}
\item genera $i$ $\in$ $I$ $\cap$ $\{0,1\}^{k}$ y $f_{i}$ la puerta secreta 

\item eligen $n$ $\in$ REC($f_{i}$) y obtiene $s$ = $f_{i}^{-1}(n)$ 
para firmar

\item y para verificar $(m,s)$ chequear que $f_{i}(s)$ = $n$

\end{itemize}

Es existencialmente falsificable dperoque dado $s$ $\in$ DOM($f_{i}$)
y calculando $m$=$f_{i}(s)$ generan un par de ($m,s$) mensaje-firma v\'alido


\end{itemize}

\end{document}






