algoritmo diffie-hellman, los pioneros

El algoritmo Diffie-Hellman fue uno de los métodos pioneros de intercambio de claves en un esquema de alta seguridad.  El presente  artículo trata de la implementación de un ejemplo sencillo de este algoritmo sobre la programación con Socket, lo interesante es que aun hoy se utiliza. 

 

 

 

Algoritmo de intercambio de claves Diffie-Hellman
El algoritmo Diffie-Hellman no es un algoritmo de cifrado como los otros que veremos, este es un algoritmo de intercambio de claves.

Examinemos la siguiente situación :

Alice y Bob quieren comunicarse de una forma segura a través de un canal público, imaginemos una pequeña red LAN de 3 ordenadores.  En esta pequeña red, están los ordenadores de Alice, Bob y la cotilla de Charlotte, que quiere saber a toda costa de que quieren hablar Alice y Bob.

Sería algo así :

Ahora, vemos que cualquier comunicación entre Alice y Bob puede ser leída por Charlotte, así que sabemos que tendrán que cifrar la conversación.

Imaginemos que Alice y Bob van a usar un cifrado simétrico para generar su canal cifrado, este va a ser RC4 128 bits. Alice y Bob tendrían que acordar una clave por esa red insegura (Esta sería la clave 128 bits del RC4) , ¿cómo pueden hacerlo sin que Charlotte averigüe esa clave? Ahí es donde entra el algoritmo de intercambio de claves de Diffie-Hellman.

Vamos por pasos :
1. Alice elige un número primo “p” que suele ser muy grande pero por cuestiones prácticas para el ejemplo, vamos a elegir uno pequeño, utilizaremos el 31 y un número aleatorio “k” menor que “p”, por ejemplo el 12. Tras elegirlo se lo manda a Bob (da igual que Charlotte lo vea).

2. Alice elige un número cualquiera menor que “p” y lo guarda en secreto. A ese número lo vamos a llamar x, luego a partir de x saca A de esta forma :
 A = k^x (mod p)



Imaginemos que  x = 6, por lo tanto :
A = 12^6 (mod 31) = 2
Tras calcularlo , Alice manda a Bob el número A, en este caso 2.

3. Ahora le toca a Bob elegir un número secreto (y menor que “p”) y realizar la operación de antes para conseguir B. Supongamos que y = 26
B = k^y (mod p)
B = 12^26 (mod 31) = 10
Tras calcularlo, Bob envía B a Alice.

4. Este es el momento en el que ambos calculan la clave que van a usar para el RC4 128 bits.
Por una parte Alice :
Clave = B^x (mod 31) = 10^6 (mod 31) = 2
Por otra parte Bob:
Clave = A^y (mod 31) = 2^26 (mod 31) = 2

Y así ambos han llegado a la misma clave. Se puede observar que como Charlotte no conoce ni “x” ni “y”, no puede obtener la clave.

Si Charlotte intentará averiguar x o y, tendría que resolver la siguiente ecuación :
10 = 12^x (mod 31)

Quizás con estos números no tardará mucho, pero normalmente se cogen números de 300 dígitos, por lo que se tardaría un tiempo enorme en encontrar solución a esta ecuación.

Una pequeña explicación matemática es que :
B^x (mod p) = g^y^x (mod p) = g^(yx)  (mod p) = g^(xy) (mod p) = g^x^y (mod p) = A^y (mod p)
(Siendo g el segundo numero elegido y p el número primo del principio)

Y es por eso que llegan a la misma clave.

Una cosa importante de este algoritmo es que no es autenticado, es decir que que no puedes tener la certeza de quien está comunicándose contigo. Esta propiedad del algoritmo hace que solo sea seguro si en este caso, Charlotte no puede modificar el tráfico que va desde Alice a Bob y viceversa