INTERCAMBIO DE CLAVES

 

En los años '70 se desarrollaron los primeros métodos de encriptación de clave privada diseñada para aprovechar el potencial de las computadoras. Sin embargo, al igual que sus antecesores, estos algoritmos seguían teniendo una debilidad básica: el peligro de que un “espía” consiguiera las claves y, conocido el algoritmo de encriptación, lograra descifrar los mensajes.

Con el nacimiento de Internet en 1982 y su posterior desarrollo, el problema de la distribución de claves de manera segura se volvió aún más acuciante. ¿Sería posible para dos partes que quieren comunicarse acordar una clave secreta compartida aun no teniendo manera de contactarse de forma segura?

En su trabajo New direction in cryptography , publicado en 1976 (en IEEE Transactions on Information Theory, IT-22, 6, páginas 644-654), Whitfield Diffie y Martin Hellman propusieron un esquema público de intercambio de claves como respuesta a este problema. El mural ilustra este esquema. 

La idea básica puede entenderse pensando en pinturas y mezclas de colores. Ana y Bruno comienzan con una pintura base, color amarillo en el mural, a disposición de cualquiera y van a fabricar un color conocido sólo por ellos. Para hacer esto, cada uno elige un color secreto; por ejemplo, Ana elige un tono de rojo y Bruno, un tono de azul. Ana y Bruno le agregaron a la pintura base una cierta cantidad de pintura de su color secreto. Así se obtuvieron dos colores distintos; en el ejemplo, Ana obtiene un tono de naranja y Bruno, un tono de verde. A continuación, intercambian de manera pública, las pinturas que han fabricado. Al recibir la pintura verde que le envía Bruno, Ana le agrega su pintura roja secreta, produciendo un cierto tono de marrón. Bruno procede de la misma forma con la pintura naranja que recibe de Ana: le agrega su tono azul secreto, obteniendo así el mismo tono de marrón que Ana. Si alguien intercepta el envío de las pinturas naranja o verde, no podrá fabricar el tono de marrón secreto, porque no conoce el tono de rojo que compró Ana ni el azul de Bruno, y separar la mezcla para individualizarlos le resultaría muy costoso.

El mural presenta también, en un ejemplo, la versión matemática propuesta por Diffie y Hellman, haciendo el paralelismo con las pinturas y colores. 

Ana y Bruno comienzan con un número primo positivo p y un número natural n menor que p , que pueden ser públicamente conocidos; en el ejemplo, p = 13 y n = 2 (serían como la pintura base amarilla). Ana elige un número a , que mantiene en secreto, y Bruno elige un número b , que también guarda en secreto (los números a y b juegan el papel de los colores secretos, rojo y azul); en el ejemplo, a = 5 y b = 4. Ana calcula el resto r a de dividir n a por p y Bruno calcula el resto r b de dividir n b por p ; en el ejemplo, r a = 6 es el resto de dividir 2 5 por 13 y r b = 3 es el resto de dividir 2 4 por 13 (estos restos juegan el papel de las pinturas naranja y verde).

A continuación intercambiarán los resultados r a y r b obtenidos, utilizando un canal de comunicación que puede ser inseguro. Luego del intercambio, Ana calcula el resto r ba de dividir ( r b ) a por p y Bruno calculan el resto r ab de dividir ( r a ) b por p ; en el ejemplo, r ba = 9 es el resto de dividir 3 5 por 13 y r ab = 9 es el resto de dividir 6 4 por 13 (estos restos serían la pintura marrón).

La clave secreta compartida es r ba =  r ab ; en el ejemplo, el número 9. 

Observar que los números r ba y r ab siempre serán iguales. En el ejemplo, 9 es el resto de la división de 2 20 por 13.

Si Ema intercepta el envío de r a o r b  no puede calcular la clave secreta compartida porque no conoce los números secretos elegidos por Ana y Bruno.

La seguridad de este método depende crucialmente de la dificultad computacional del cálculo de logaritmos módulo un primo p : conociendo el resto de dividir n a por p , el número n y el primo p , no se sabe cómo calcular de manera eficiente el exponente a . Esto es lo que le impide a un espiar obtener los numeros secretos de Ana y Bruno, aun conociendo los resultados que intercambian.

UN COFRE PARA EL SECRETO

A comienzos de los años '80, Adi Shamir menciona un nuevo esquema para el envío de mensajes secretos sin necesidad de intercambio o distribución previa de claves conocidas como protocolo de tres pasos . El nombre se debe a que, a lo largo del proceso, emisor y destinatario intercambian, sucesivamente, tres mensajes encriptados. Para presentar la idea de cómo funciona este esquema utilizaremos un cofre y dos candados, uno rojo y otro azul, con sus correspondientes llaves. 

Digamos que Ana quiere enviarle a Bruno un mensaje sin que Ema, que podría espiar, tenga acceso a su contenido. 

• Ana guarda el mensaje en el cofre y le pone el candado rojo del que solo ella tiene la llave. Ahora le manda el cofre a Bruno. Si Ema intercepta el envío y trata de espiar el mensaje, no puede hacerlo, porque no tiene la llave para abrir el candado rojo. 

• Cuando Bruno recibe el cofre, el problema es que él tampoco tiene la llave para quitar el candado rojo. Lo que hace entonces es ponerle otro candado, en este caso el azul, del que sólo él tiene la llave, y se lo vuelve a enviar a Ana. Si Ema intercepta el envío, ¡está peor que antes! Ahora el cofre tiene dos candados y ella no tiene llave de ninguno de los dos.

• Al recibir nuevamente el cofre, Ana le quita el candado rojo usando su llave y se lo vuelve a mandar a Bruno. El cofre sigue teniendo un candado, el azul, que le impide a Ema abrirlo para ver su contenido. Cuando Bruno lo recibe, usa su llave para quitar el candado azul, abre el cofre y accede así al mensaje secreto de Ana.

En la práctica, para implementar este esquema se usan técnicas de aritmética modular similares a las que se presentan en los murales de criptografía de clave pública o intercambio de claves.