Diffie-Hellman

Resumen:
Redes sociales, cuentas de banco, teléfonos, entre otros más necesitan de una contraseña para que el usuario acceda a cierta información. Esta contraseña es lo que se conoce como una llave privada, es decir, solo el usuario la conoce. Sin embargo de vez en cuando es necesario que dos usuarios establezcan una nueva llave privada (solo ellos dos conocen) para poder acceder a información. El protocolo de Diffie-Hellman proporciona una manera de generar una llave compartida haciendo uso de las llaves privadas de dos usuarios. En lineas posteriores daremos de forma explícita dicho protocolo.

Otra cuestión a tratar es el cifrado de mensajes. Los bancos en particular necesitan de herramientas de cifrado para poder enviar información de sus cuentas sin que estas puedan ser robadas. Usaremos el protocolo Diffie-Hellman para dar una manera de cifrar mensajes.

Para finalizar, daremos una manera de formar mensajes usando el protocolo Diffie-Hellman. Los esquemas de firma digitial son escenciales en la criptografía para corroborar que la información obtenida en verdad la enviado la persona que dice enviarla.


$\textbf{Protocolo de intercambio de llave compartida Diffie-Hellman}$
El protocolo de intercambio de llave compartida Diffie-Hellman usa las llaves privadas de dos usuarios para obtener una llave compartida (clave simétrica) que es usada para el cifrado y descifrado de mensajes.

Ana y Bob quieren tener una llave de intercambio en común.
-Primero, se ponen de acuerdo en elegir un número primo p (suficientemente grande) y $\alpha \in \mathbb{Z}_p$ elemento primitivo.

El esquema pretende darle poder a Ana y Bob, por ello, Ana elige una llave secreta $x_A\in \mathbb{Z}_p$ (solo Ana conoce la llave) y de manera similar con Bob elijiendo $x_B \in \mathbb{Z}_p$.

-Ana manda a Bob $K_A \equiv \alpha ^ {x_A} \mathrm{mod} \ p$ y Bob manda a Ana $K_B \equiv \alpha ^ {x_B} \mathrm{mod} \ p$.

-Entonces la llave en común la pueden obtener ambos y está dada por:

\begin{equation}
K \equiv \alpha ^{x_A\cdot x_B}\mathrm{mod} \ p
\end{equation}

Note que con este protocolo Ana y Bob pueden obtener $K$ de manera muy sencilla, pero para un intruso hallar $K$ puede ser muy difícil, lo cual hace a este protocolo ideal para implementarse en criptografía.

$\textbf{Seguridad de las llaves $x_A$ y $x_B$}$
Digamos que Ana quisiera obtener la llave privada de Bob, esto es posible haciendo el cálculo:
\begin{equation}
x_B \equiv log \ disc _{\alpha} (K )- x_A \mathrm{mod} \  p
\end{equation}

El cálculo anterior puede ser determinado, sin embargo por la dificultad del $\textit{Problema del Logaritmo Discreto}$ (PLD) este cálculo puede demorar mucho tiempo (incluso siglos) con el cómputo clásico, lo cual no es conveniente para fines prácticos. Es por ello que podemos decir que las llaves de Ana y Bob permanecen seguras por la complejidad del PLD. Sin embargo existen ataques a este protocolo, por mencionar Man-in-the-middle.

$\textbf{Sistema de llave pública}$
Supongamos que Ana quiere mandar un mensaje $m\in \mathbb{Z}_p$ (con $p$ número primo suficientemente grande) a Bob.

-Primero Ana elije su número favorito $k\in \mathbb{Z}_p$. Observe que $k$ sirve como el número secreto $x_A$ en el protocolo anterior.
-Ana calcula $K \equiv y_B ^k \mathrm{mod} \ p$, donde $y_B\equiv \alpha ^{x_B}\mathrm{mod} \ p$ es público o mandado por Bob.
-El mensaje encriptado es el par $(c_1,c_2)$ donde
\begin{equation}
c_1\equiv \alpha ^k \mathrm{mod} \ p \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ c_2\equiv Km \ \mathrm{mod} \ p
\end{equation}
Observemos que el mensaje cifrado es de doble tamaño que el mensaje, además la operación $Km$ puede ser reemplazada por una operación invertible, por ejemplo la suma en $\mathbb{Z}_p$.

Si ahora Bob quiere descifrar el mensaje recibido $(c_1,c_2)$, entonces:

-Primero Bob debe recuperar $K$.
\begin{equation}
K\equiv (\alpha ^ k)^{x_B}\equiv c_1 ^{x_B} \mathrm{mod} \ p
\end{equation}
Observe que Bob conoce su llave privada $x_B$ por lo cual siempre puede hallar $K$.
-Bob descifra el mensaje $m$ con
\begin{equation}
m\equiv c_2K^{-1}\mathrm{mod }\ p
\end{equation}

$\textbf{Esquema de firma digital}$
Se presentará un esquema de firma digital basado en el protocolo Diffie-Hellman.
Supongmos que queremos firmar un mensaje $m\in \mathbb{Z}_p$. El protocolo aún consiste de la llave pública $y=\alpha ^{x_A} \mathrm{mod}\ p$. Para firmar un documento, Ana debe usar su llave privada $x_A$ para encontrar una firma para el mensaje $m$, con la cual todos los usuarios puedan autentificar usando la llave pública $y_A$.

La firma para $m$ es el par $(r,s)$ con $r,s\in \mathbb{Z}_p$ elejidos de tal manera que cumplan la congruencia:
\begin{equation}
\alpha ^m \equiv y^r r^s \mathrm{mod} \ p
\end{equation}

El protocolo de firma digital es el siguiente:
-Ana elije un número aleatorio $k\in \mathbb{Z}_p$ tal que $g.c.d(k,p-1)=1$.
-Ana calcula $r\equiv \alpha ^k \mathrm{mod}\ p$
-Ahora $\alpha ^m$ puede ser escrito como
\begin{equation}
\alpha ^m \equiv \alpha ^{x_A \cdot r}\alpha ^{k \cdot s}\mathrm{mod}\ p
\end{equation}
Por lo tanto podemos encontrar $s$ usando:
\begin{equation}
 m\equiv x_A\cdot r + k\cdot s \ \mathrm{mod}\ (p-1)
\end{equation}
la cual tiene solución desde que pedimos $g.c.d(k,p-1)=1$.

Supongamos que ahora Bob quiere autentificar que fue Ana quien le envió el mensaje. Entonces Bob necesita hacer lo siguiente.
 -Dados $m,r,s$ es fácil verificar la autenticidad de la firma viendo que se cumple la congruencia $\alpha ^m \equiv y^r r^s\  \mathrm{mod} \ p$.