Cripto Serie: Nuevas Direcciones en Criptografía

Seifreed · 20-Dec-2009, 13:33

Como algunos ya habréis notado por el título, este post será el primero hablando sobre criptografía de clave pública. Hoy introduciré las ideas básicas sobre criptografía de clave pública y las ideas propuestas por Diffie y Hellman en su famoso artículo de 1976 ‘New Directions in Cryptography‘.
En próximos posts, trataremos el problema del logaritmo discreto y de la factorización de números enteros grandes. También trataremos criptosistemas de clave pública como El-Gamal y RSA. Y más tarde trataremos la Criptografía de Curvas Elípticas. Con todo esto, la parte sobre algoritmos de esta serie se considerará cerrada y pasaré a hablar sobre sistemas criptográficos y protocolos.
PD: Hay cosas que no tengo ni la más remota idea de cómo traducir correctamente al español… si veis alguna cosa rara decidmelo en los comentarios y lo cambio

.

Y qué es lo que propusieron Diffie y Hellman exactamente? Bueno… dejadme primero contaros por qué querían cambiar la forma en que la criptografía funcionaba. Como sabéis, con la criptografía simétrica necesitamos una clave compartida entre los dos extremos que se comunican. Esto funciona bien y es fácil de mantener cuando tenemos pocas entidades tomando parte en un sistema de comunicación.
En cambio, con la llegada de los sistemas de comunicación globales, Internet y todas esas cosas que ya conocéis, este esquema se vuelve inmanejable. Un sistema simétrico con n usuarios requiere una clave única por cada par de usuarios, lo que significa $\frac{n(n-1)}{2}$ claves.
Por tanto, la principal motivación para la criptografía de clave pública es la reducción del número de claves necesitado para un sistema criptográfico, reduciendo la complejidad del manejo de claves. Ahora, cómo lo conseguimos? Básicamente, la Criptografía de Clave Pública se basa en la existencia de dos algoritmos distintos: uno público para el cifrado, y otro privado para el descifrado.
Así, digamos que quieres cifrar algo para una persona en concreto. Entonces, obtienes la clave pública de dicha persona y aplicas el algoritmo público para cifrado. Luego envías el mensaje a esa persona, que una vez recibido, aplicará el algoritmo privado con la parte privada de su clave.
Esto implica que el algoritmo público de cifrado, $E_K$ , y el algoritmo privado de descifrado $D_K$ son operaciones inversas (para proporcionar la posibilidad de recuperar el mensaje). Además, el cálculo debe ser sencillo (o de bajo coste) para que se pueda aplicar de forma eficiente. Finalmente, debería ser complejo (prácticamente imposible) realizar el cálculo de la parte de descifrado $D_K$ dada la parte de cifrado $E_K$ .
Funciones trapdoor
Necesitamos pues una función que sea sencilla de calcular, pero que su inversa sea difícil de calcular. Eso es una función unidireccional (como una función hash criptográfica)… pero espera, además necesitamos que sea sencillo de calcular para el otro extremo de la comunicación. Así que necesitamos añadir un componente extra (vease una clave) que haga el cálculo sencillo: una trampilla! (trapdoor, no me matéis por la traducción malísima de trapdoor pero no se me ocurre otro nombre

)
Veremos cómo construir este tipo de funciones en los próximos posts sobre distintos sistemas criptográficos de clave pública

. Por ahora, solo diré que este tipo de funciones se puede construir basándose en la exponenciación entera módulo p o en operaciones sobre grupos de Curvas Elípticas.
Intercambio de claves Diffie-Hellman
Finalmente llegamos al intercambio de claves Diffie-Hellman. Este es un protocolo para calcular conjuntamente una clave compartida entre dos entidades sobre un canal inseguro, usando únicamente datos públicos.
El intercambio DH funciona bajo el supuesto de que el problema del logaritmo discreto (DL) es difícil de resolver. El problema DL se enuncia como sigue:

Dado $y = g^x \mod p$ , obtén x

Donde g es un generador y p es un número primo grande. Así, asumimos que este problema es difícil de resolver (hablaré sobre métodos para resolverlo en el próximo post), y tenemos dos entidades Alice y Bob que quieren comunicarse de forma segura. Entonces, Alice genera un número aleatorio $x_A$ módulo p-1 y calcula $y_A = g^{x_A} \mod p$ . A su vez, Bob hace lo mismo, generando $x_B$ y $y_B$ .
Ahora, Alice y Bob intercambian la parte pública de sus claves y realizan el cálculo de la clave compartida como:

$k = y_B^{x_A} = (g^{x_B})^{x_A} = g^{x_B x_A} = (g^{x_A})^{x_B} = y_A^{x_B} = k^{\prime}$

Notad que Alice y Bob son capaces de generar la clave compartida únicamente basándose en la clave pública de la otra parte y en su propia clave privada, que no comunican a nadie. Además, notad que bajo el supuesto DL no es prácticamente posible calcular la clave privada de ninguna de las partes a partir de su clave pública.

Sin embargo, aquí el atacante tiene algo más de información para resolver el problema que en un DL simple, y por tanto esto requiere realizar una hipótesis más estricta: el supuesto DH. El supuesto (o la asunción…) DH significa que asumimos que dados $g^x$ y $g^y$ , es complejo calcular $g^{x y}$ .

Notad que esto es diferente de la asunción DL, puesto que cabe la posibilidad de que alguien sea capaz de calcular el resultado sin tener que calcular x o y de forma individual. Sin embargo, hasta donde yo sé, este es un problema complejo al menos en el grupo de enteros módulo un número primo grande. Por tanto, esto garantiza la confidencialidad de la clave acordada entre nuestras dos partes, Alice y Bob.

El problema del hombre en el medio

He dicho que garantiza la confidencialidad de la clave acordada, pero eso no es completamente cierto… sólo lo hace si la clave pública recibida realmente viene de quien se cree. Y puesto que este intercambio de claves no hace nada para garantizar la autenticidad de dicha clave, hay un claro problema de hombre en el medio (man in the middle).

Imaginad un atacante, llamese Eve o Mallory o como os guste llamar a vuestro atacante, situado en el medio de la comunicación entre Alice y Bob. Este atacante es capaz no sólo de recibir la información comunicada, sino de modificarla. Entonces, el atacante sería capaz de mandar a Alice y Bob su propia clave pública, y interceptar las suyas para sí mismo.

Esto resultaría en que el atacante habría generado un canal seguro entre Alice y él mismo, y otro entre Bob y él mismo. Cualquier cosa que Alice o Bob envien, podrá ser descifrada, leída y modificada si lo desea.

Para resolver este problema, es obvio que necesitamos añadir autenticación al intercambio de claves. Esto es algo que podríamos hacer con construcciones MAC o HMAC como ya aprendimos, pero entonces nos encontramos con el problema del huevo y la gallina: usamos el intercambio de claves Diffie-Hellmanpara evitar tener que compartir una clave secreta, pero ahora queremos autenticar el mensaje con MAC o HMAC, que a su vez requieren una clave secreta compartida!

Aquí es donde las firmas digitales, la solución de la criptografía de clave pública para autenticación, nos serán de utilidad. Las veremos en próximos posts, que creo que ya hemos tenido suficiente por hoy todos

.
Fuente