Diffie y Hellman
Whitfield
Diffie
Whitfield Diffie nació en Nueva York, EUA, en 1944. Desde niño tenía fascinación por la matemática y fue esto que acabó estudiando en el MIT - Massachusetts Institute of Technology, formándose en 1965. Después de esto trabajó en seguridad de ordenadores hasta que, en 1970, estaba pronto para una caerse al suelo - se transformó en un de los pocos especialistas en seguridad realmente independiente, sin vínculos con el gobierno o con grandes corporaciones. Sus cabellos largos y su modo de ser hacen de Diffie una especie de hippie de alta tecnología y, a buen seguro , puede ser considerado el primero cypherpunk de la historia.
Uno de los problemas que más llamaba la atención de Diffie era el problema de la distribución de llaves. Acompañando la evolución de la organización de investigación ARPA (Advanced Research Projects Agency), fundada por el Departamento de Defensa de los EU, la cual, en 1969, creó el sistema de comunicación en red llamado de ARPANet, Diffie sentía que una revolución estaba punto de acontecer y que el proyecto abría las puertas para el desarrollo de una supervía de comunicación. El tiempo mostró que su pronóstico era correcto (en 1982 nacía internet) y que su preocupación con el sigilo y la privacidad de los usuarios de una gran red era más que justificado. En este contexto, sabía que la criptografía se transformaría en una herramienta esencial y que el problema de la distribución de llaves se haría especialmente agudo.
Martin
Hellman
En 1974 Diffie fue invitado para dar una charla en IBM y el tema, como no podría dejar de ser, fue sobre las varias estrategias de ataque a la distribución de llaves y propuestas para algunas soluciones. La reacción de los oyentes no fue de las más calurosas. Los monstruos sagrados de la IBM, así como todo el mundo, tenían la idea preconcebida de que este era un problema insoluble (y no sería un peludo quién iba a cambiar las cosas). La única respuesta positiva fue a de Alan Konheim, uno de los especialistas en criptografía de la IBM. Comentó que Martin Hellman, profesor de la Universidad de Stanford, California, también había dado una charla con énfasis en el problema de la distribución de llaves. Fue lo que bastó para Diffie atravesará los EU a la busca de la persona que, aparentemente, era la única que compartía sus opiniones.
Martin Hellman nació en el Bronx, Nueva York, EUA, en 1945. Judío en una vecindad católica, tuvo problemas de autoafirmación desde la infancia. Él cuenta que este fue uno de los motivos por los cuáles comenzó a interesarse por la criptografía - ya que era diferente, quería ser diferente para todo. Hasta la inesperada visita de Diffie en 1974, el famoso libro de David Kahn, The Codebreakers, había sido el libro de cabecera y la única fuente de información de Hellman. Después de una media hora de conversación, ambos estaban impresionados con el conocimiento del otro y percibieron que ya no estaban solos en la búsqueda de una solución "imposible". A pesar de las evidentes diferencias de personalidad, este fue el comienzo de una gran amistad y compañerismo. Inmediatamente comenzaron a elaborar un plan para poder trabajar juntos. Como Diffie no tenía condiciones de contratar el nuevo amigo como investigador, Hellman resolvió registrar Diffie como estudiante graduado de Stanford. Y la peregrinación comenzó…
Ralph Merkle
Después de algún tiempo de trabajo conjunto, Ralph Merkle se unió a los dos. Merkle era un refugiado intelectual de un otro grupo de investigación cuyo profesor no simpatizaba ni un poquito con las ideas ingeniosas de distribución de llaves de Merkle. Era el "loco belleza" ideal y su ayuda era más que bienvenida. Estaba formado el trío, los tres mosqueteros de esta historia.
El problema de la distribución de llaves
El problema de la distribución de llaves es si; fue primero el huevo o la gallina. Si dos personas que quieran intercambiar mensajes secretos, ellas necesitan cifrar los mensajes. Para cifrarlas y descifrarlas, necesitan una llave secreta. Como esta llave también necesita ser transmitida, tendría que ser cifrada con otra llave, y así indefinidamente.
Una forma bastante simple de resolver el problema de las llaves sería usar candados. Digamos que Antonio quiere enviar un mensaje a Belén . Ella coloca el mensaje en una caja de metal, cierra la caja con un candado (sólo ella tiene la llave de este candado) y a envió a Belén . Belén también coloca un candado en la caja (sólo él tiene la llave de este segundo candado) y devuelve la caja para Antonio. Al recibir la caja, Antonio abre y retira su candado y, nuevamente, envía la caja para Belén . Ahora, Belén puede quitar su candado, abrir la caja y leer el mensaje.
Funciones matemáticas
Si las funciones matemáticas necesarias para cifrar un mensaje tuvieran un comportamiento igual a lo de los candados, la solución encontrada por Belén y Antonio sería perfecta. Desgraciadamente, este no es el caso Las funciones matemáticas necesitan ser "retiradas" en la orden inversa en que fueron "colocadas", lo que no es necesario cuando se trata de candados. A pesar de esto, este fue el punto de partida usado por Diffie y Hellman.
La mayoría de las funciones matemáticas son fácilmente reversibles y, por este motivo, pueden ser llamadas de funciones bidireccionales . Una función multiplicativa es reversible, fácil de resolver y un óptimo ejemplo. Digamos que f(x) = 2x. En este caso, si x = 3, entonces f(x) = 2 x 3 = 6. Conociendo la función se puede calcular x con rapidez, independientemente del tamaño del resultado de la función. Por ejemplo, si f(x) = 1000, podemos hacer la cuenta de cabeza y llegar en x = 500. Hasta ahí, nada de muy especial. Acontece que Diffie y Hellman estaban concentrando esfuerzos en la busca de una función unidireccional.
Podemos definir una función unidireccional como una función que no tiene vuelta (esta sería la verdadera función unidireccional) o cuya vuelta es tan complicada o tan lenta que, en la práctica, la vuelta se hace inviable.
La aritmética modular
Una excelente fuente de funciones unidireccionales es la aritmética modular. La aritmética modular es una área de la matemática donde se lidia con una cantidad finita de números arreglados como en una esfera de reloj. Por esto la aritmética modular también es conocida como aritmética circular. Usando la esfera del reloj como ejemplo, es fácil entender cómo funciona. La primera cosa es saber que la esfera posee sólo 12 números, por lo tanto, el reloj muestra las horas en módulo 12 (este es el campo finito citado en la introducción). A pesar de esta limitación, solemos decir, por ejemplo, 15 horas. Como estamos acostumbrados a razonar en este módulo, inmediatamente sabemos que el puntero de las horas está en el 3. En la verdad hicimos un pequeño cálculo mental (15 - 12 = 3) que infelizmente no es tan eficiente cuando hablamos, por ejemplo, 43 horas. Donde estará la esfera del reloj cuando son 43 horas? Estará en el 7 porque el puntero dio 3 vueltas completas (3 x 12 = 36) y después avanzó 7 posiciones más (43 - 36 = 7). Resumiendo, para hallar el módulo de un número (o de una operación), se divide este número (o el resultado) por el módulo y se considera sólo el resto.
43 (mod 12) = 43 ÷ 12 = 3 con resto 7 --> 43 (mod 12) = 7
59 (mod 5) = 59 ÷ 5 = 11 con resto 4 --> 59 (mod 5) = 4
de la misma forma
2 + 3 (mod 7) = 5 porque 5 ÷ 7 = 0 con resto 5
2 + 9 (mod 7) = 4 porque 11 ÷ 7 = 1 con resto 4
3 x 3 (mod 7) = 2 porque 9 ÷ 7 = 1 con resto 2.
El comportamiento errático de los resultados modulares hace con que la reversión de una operación modular sea muy trabajosa que la reversión de una operación normal. Si consideramos la función 4x, por ejemplo, a medida que el valor de x aumentar, el valor del resultado también aumenta. La misma función en cualquier módulo, sin embargo, no muestra la misma linearidade. Observe a continuación:
41 = 4 41 (mod 11) = 4
42 = 16 42 (mod 11) = 5
43 = 64 43 (mod 11) = 9
44 = 256 44 (mod 11) = 3
45 = 1024 45 (mod 11) = 1.
Cuando los valores son pequeños, como los mostrados en el ejemplo, montar una tabla para encontrar el valor de x buscada no es ningún bicho de siete cabezas. Pero imagine encontrar por el frente alguna cosa como 1793x (mod 32748) u otros números bien mayores. En primer lugar ya habría un problema con las calculadoras (y, dependiendo del tamaño de los números, hasta con el ordenador) y, en segundo lugar, el proceso puede ser tan lento que a usted le llevaría la vida entera hallar el resultado correcto. Es por esto que este es un ejemplo clásico de función unidireccional.
Como investigadores, Diffie y Hellman sabían que nada podía ser despreciado, aún aquello que pareciera ser cosa que los niños aprenden en el primer grado. Después de dos años de trabajo con las funciones unidireccionales ofrecidas por la aritmética modular, Hellman finalmente consiguió probar lo que hasta entonces era considerado imposible: remitente y destinatario podrían usar una estrategia que ponía el problema de la distribución de llaves en la picota!
El algoritmo Diffie-Hellman
En el inicio de 1976, Hellman estaba analizando un axioma que ya existe hace algunos centenares de años. La idea era usar la función en la forma de g
x (mod n)
Para que la mágica funcionara, había algunas restricciones:
g (la base) necesita ser menor que n (el módulo)
y g necesita ser mayor que 1.
Para obtener las llaves, Belén y Antonio pueden intercambiar informaciones abiertamente, sin la mínima preocupación con alguien que esté presente o que eventualmente esté interceptando estas informaciones. En sólo 4 etapas, los dos tendrán una llave secreta.
1. La elección de la base y del módulo
Inicialmente Belén y Antonio escogen dos números grandes, uno para la base g y uno para el módulo n, obedeciendo las restricciones citadas arriba. Esta elección no necesariamente envuelve sólo los dos, más personas pueden participar del grupo de usuarios. Para facilitar, será usado un ejemplo con números pequeños y sólo con Belén y Antonio. Digamos que ellos, durante el intervalo de las clases, hayan concordado con
g = 7
y n= 11
2. La elección de los exponentes
Después, en la privacidad de su casa, Belen escoge una exponente x bien grande. Este número Belén mantiene cuidadosamente en secreto. Antonio hace la misma cosa y también mantiene su elección en secreto. De posesión de sus exponentes, los dos calculan el resultado de la función:
Antonio Belen
-------------------------- --------------------------
x = 6 y = 3
M = 76 (mod 11) J = 73 (mod 11)
M = 117649 (mod 11) J = 343 (mod 11)
M = 4 J = 2
3. El cambio de resultados
El día siguiente, los dos se encuentran nuevamente en el intervalo de las clases. Antonio entrega el resultado obtenido (M=4) para Belén y este entrega el resultado que obtuvo (J=2) para Antonio. Más una vez, ninguno de los dos está preocupado que alguien tome conocimiento de estos números.
4. El cálculo de la llave secreta
Con el resultado obtenido por el otro, Belén y Antonio vuelven a hacer cálculos en particular. Usan la misma función sólo que, esta vez, la base usada por Antonio es el resultado obtenido por Belén y la base usada por Belén es el resultado obtenido por Antonio. Los exponentes continúan siendo los previamente escogidos:
Antonio Belen
-------------------------- --------------------------
x = 6 y = 3
J' = 26 (mod 11) M' = 43 (mod 11)
J' = 64 (mod 11) M' = 64 (mod 11)
J' = 9 M' = 9.
Como en un pase de mágica, ambos llegaron al mismo resultado y ahora poseen una llave secreta en común
Algunas consideraciones
La llave secreta no es más que gxy (mod n). Para confirmar, basta hacer los cálculos:
gxy (mod n) = 76 x 3 (mod 11)
= 718 (mod 11)
= 1.628.413.597.910.449 (mod 11)
= 9.
Aunque se conozca los valores de g , n, M y J no es posible calcular el valor de la llave secreta. Si usáramos el método de las tentativas (o sea, la fuerza bruta) podremos encontrar incontables valores que cierran las primeras ecuaciones. Por ejemplo, en el caso de Antonio, los valores posibles de x son 6, 16, 26, ..., 6 + 10n y, en el caso de Belén , los valores posibles de y son 3, 13, 23, ..., 3 + 10n. Tanto x cuanto y pueden tener infinitos valores de acuerdo con las progresiones aritméticas citadas y estos valores necesitan ser agrupados en todos los pares posibles para intentar encontrar la llave - una tarea imposible de ser realizada si los valores escogidos que sean grandes el suficiente.
Pero no son sólo los valores suficientemente grandes de los exponentes que confieren seguridad a este sistema. La elección de g y n también tiene una influencia acentuada. El módulo n debe ser un número primo y, más importante que esto, (n-1)/2 también debe ser un número primo. La base g, por su parte, debe ser una raíz primitiva en el módulo n (más sobre el asunto inmediatamente a continuación). Ahora, el más importante de todo es que n debe ser grande, que haya como mínimo 512 bits (o sea, que haya 64 bytes, lo que es lo aunque 64 algarismos). Usar 1028 bits sería más seguro.
Operaciones modulares de la Teoría de los Números
Normalmente las operaciones modulares y los números primos son conceptos fáciles de que sean absorbidos. Estos conceptos forman parte de la Teoría de los Números, una área de la matemática que lidia sólo con números enteros. Una de las cosas que siempre me llamó la atención es que los matemáticos adoran encontrar particularidades y ciertas características de comportamiento de los números. Como no soy matemática, veo esto como una manía de querer descubrir la personalidad de los números, lo que transforma la matemática en una investigación de detective, en un juego de caza al tesoro o en una broma de "lo que es, lo que es?".
Raíz Primitiva
Por ejemplo, fui dar un vistazo en lo que es la raíz primitiva de un módulo. Descubrí que un número g es la raíz primitiva de un módulo n cuando este número elevado a las potencias de 1 hasta n-1 (mod n) suministrar todos los residuos posibles de este módulo. Por ejemplo, 3 es una raíz primitiva de lo (mod 5) porque:
31 (mod 5) = 3 (mod 5) = 3
32 (mod 5) = 9 (mod 5) = 4
33 (mod 5) = 27 (mod 5) = 2
34 (mod 5) = 81 (mod 5) = 1.
Estas operaciones resultaron en todos los residuos que el módulo 5 puede ofrecer. El hecho de que no estuvieran en orden no tiene importancia, pues la premisa es que todos aparezcan una vez. Sólo para fijar esta noción, observe el comportamiento de 4 en el módulo 5:
41 (mod 5) = 4 (mod 5) = 4
42 (mod 5) = 16 (mod 5) = 1
43 (mod 5) = 64 (mod 5) = 4
44 (mod 5) = 256 (mod 5) = 1.
Estos cálculos nos muestran que 4 no es una raíz primitiva del módulo 5. Cuando el valor de los módulos es pequeño, puedes hacer el cálculo con lápiz y papel, pero, si el valor de que el módulo sea muy grande, la calculadora no va a tener espacio para los dígitos y los cálculos van a llevar un tiempo enorme. Menos mal que los matemáticos hallan atajos que facilitan nuestra vida. Conforme Burton publicó en 1986, uno de los atajos que podemos coger es
Si el MDC(g,n)=1 (o sea, g y n son primos entre sí)
y la orden multiplicativa de g (mod n) que sea igual la φ(n), donde φ(n) es la función totiente, entonces g es una raíz primitiva del módulo n.
Dio nó en su cabeza? Para hablar la verdad, en mi también dio. Es que están faltando algunas piezas para resolver este rompecabezas. El MDC, o máximo divisor común, no tiene secretos. Ya la orden multiplicativa y la función totiente...
Orden Multiplicativa
El modo es ir por partes. La orden multiplicativa, también llamada de orden modular, Haupt-exponent (exponente principal) o simplemente orden, es una característica de los módulos (uno más de sus trazos de personalidad ) Que se obtengamos la respuesta para la pregunta "Cuál es el exponente de un número (mod n) para que el resultado sea 1?", sabremos la orden de este número en este módulo. Por ejemplo, la orden de 2 (mod 7) es igual la 3 porque 21 (mod 7) = 2, 22 (mod 7) = 4 y 23 (mod 7) = 1. Como el resultado buscado es el exponente 3, la orden multiplicativa de 2 (mod 7) = 3. Vuelva a ver los cálculos que fueron hechos para hallar una de las raíces primitivas del módulo 5. Ellos también nos muestran que la orden de 3 (mod 5) = 4.
Pero, y si el módulo fuera muy grande? Será que necesitamos calcular un monte de potencias módulo hasta descubrir cual es la orden multiplicativa de un número en este módulo? Algunos matemáticos famosos ya cuidaron de eso, facilitando las cosas para nosotros.
El Pequeño Teorema de Fermat
Fermat nos cuenta que, si el módulo que n sea un número primo y si el número g que no fuera un múltiplo de n , entonces la orden multiplicativa del número g en el módulo n es igual a n-1 porque
gn-1 (mod n) = 1
Función Totiente de Euler
La función totiente de Euler, también conocida como función phi de Euler, es designada por phi(n) o φ(n). Esta función, donde la n representa un módulo, nos revela más una faceta modular: indica cuántos residuos (los restos de las divisiones) de este módulo son primos en relación a n . Por ejemplo, en el módulo 6, los residuos posibles van de 1 la 5. Como el valor cero indica ausencia de residuo, él no es considerado. Ahora, comparando 6 con cada elemento del conjunto de residuos posibles, cuando es que estos números son primos entre sí? Acompañe:
6 y 1 --> Sí, el único divisor común es 1, o sea, MDC(6, 1) = 1
6 y 2 --> No, ambos son divisibles por 1 y 2
6 y 3 --> No, ambos son divisibles por 1 y 3
6 y 4 --> No, ambos son divisibles por 1 y 2
6 y 5 --> Sí, MDC(6, 5) = 1.
De acuerdo con los resultados, φ(6) es representado por el conjunto de dos elementos {1, 5}, o sea, φ(6) = 2. Ahí acontece más una cosa interesante: cuando n fuera un número primo, todos los residuos son relativamente primos a n . Si supiéramos de eso de antemano, no será preciso calcular ningún MDC, es sólo acordarse que el cero es la ausencia de residuo. Entonces, φ(7) = 6, φ(5) = 4 y, generalizando, φ(n) = n - 1 Y tiene más una pista. Si el módulo fuera un número compuesto por dos factores primos p y q , entonces
phi(n) o φ(n) = (p - 1) x (q - 1)
Para conferir, basta hacer las cuentas con el módulo 6. Como 6 es compuesto por los números primos 2 y 3, entonces phi(6) = (2 - 1) x (3 - 1) = 1 x 2 = 2. Guarde bien esta última fórmula porque ella aparece una porción de veces en algoritmos de llave pública!
Pero Euler también nos suministró una otra herramienta muy útil que sirve para calcular la orden multiplicativa de un número en un módulo que no sea primo. Acabamos de ver que Fermat quebró la rama para los módulos que son primos. Euler generalizó el Pequeño Teorema de Fermat y quebró una rama aún mayor.
La generalización de Euler del Pequeño Teorema de Fermat
Euler nos enseña que, si el MDC(g, n) = 1, o sea, si el número g y el módulo que n sean primos entre sí, entonces la orden multiplicativa de g (mod n) es igual la phi(n) porque
gφ(n) (mod n) = 1
Confiriendo la raíz primitiva calculada en el inicio
En el ejemplo 3 (mod 5), de acuerdo con aquella afirmación de Burton que dio nó en mi cabeza, si la orden multiplicativa 3 (mod 5) y la función totiente phi(5) que sean iguales, entonces 3 es una raíz primitiva del módulo 5. Por otro lado, si los resultados fueran diferentes, 3 no es una raíz primitiva del módulo 5. Como ya hicimos los cálculos y determinamos que 3 es una raíz primitiva del módulo 5, entonces la orden multiplicativa de 3 (mod 5) y phi(5) necesitan ser iguales. Burton parece tener razón, ellas son realmente iguales: orden multiplicativa de 3 (mod 5) = 4 y phi(5) = 4
Raíz primitiva de un módulo grande
Las herramientas citadas en este texto ayudan a probar con rapidez se determinado número es o no una raíz primitiva de determinado módulo, aún cuando este módulo tuviera un valor muy grande. Vea más un ejemplo: 143 es una raíz primitiva del módulo 1142? Para responder esta pregunta, la primera providencia es verificar se 143 y 1142 son primos entre sí:
143 | 11
13 | 13 --> Los divisores de 143 son 11, 13 y 1
1 |
1142 | 2
571 | 571 --> Los divisores de 1142 son 2, 571 y 1
1 |
El único y el máximo divisor que estos números tienen en común es 1, o sea
MDC(143, 1142) = 1 muestra que 143 y 1142 son primos entre sí.
A continuación, calculamos el phi(1142). Como 1142 es un número compuesto por los factores 571 y 2, el phi(1142) puede ser calculado de acuerdo con la fórmula
phi(n) = (p - 1) x (q - 1)
phi(1142) = (571 - 1) x (2 - 1) = 570.
Ahora es sólo confirmar si la orden multiplicativa de 143 (mod 1142) también es igual la 570, o sea, si 143570 (mod 1142) = 1. Como el módulo 1142 no es un número primo, no vamos a poder usar el Pequeño Teorema de Fermat, pero, en compensación, como el MDC(143, 1142) = 1, ellos son primos entre sí y podemos apelar para la generalización que Euler hizo de este teorema, lo cual nos dice que:
gφ(n) (mod n) = 1
o sea, de acuerdo con Euler,
143φ(1142) (mod 1142) = 1
143570 (mod 1142) = 1
y, si aún hubiera dudas, es sólo calcular para verificar que
3,4796964099440242706248097324932y+1228 (mod 1142) = 1
Confiriendo los valores de Belén y Antonio
Será que nuestros amigos cuidaron para que los valores usados con el algoritmo Diffie-Hellman realmente ofrecieran el máximo de seguridad posible? Descontando el hecho de que propositalmente fueron escogidos valores pequeños para la base y para el módulo afín de facilitar el acompañamiento del ejemplo, aún falta evaluar algunos ítems de la checklist :
El módulo n debe ser un número primo: el módulo escogido fue 11, que es primo --> OK
(n-1)/2 también necesita ser primo: (11 - 1) / 2 = 10 / 2 = 5, que es primo --> OK
La base g necesita ser una raíz primitiva en el módulo n: OK (vea abajo)
Los escogidos fueron g = 7 y n = 11
. MDC(7, 11) = 1 (son primos entre sí)
phi(11) = (11 - 1) = 10 (phi de número primo)
Como n es primo y g no es un múltiplo de n ,
el Pequeño Teorema de Fermat es aplicable:
710 (mod 11) =
282.475.249 (mod 11) = 1 (la orden multiplicativa de 7 (mod 11) es 10)
phi(11) = 10 |
| --> 7 es una raíz primitiva en el módulo 11
orden 7 (mod 11) = 10 |
Diffie-Hellman extendido
V. S. Miller y Kevin McCurley extendieron este algoritmo para curvas elípticas y Taher ElGamal usó la idea básica para desarrollar un algoritmo de encriptación y de firma digital. Además de eso, el protocolo de cambio de llaves puede ser fácilmente extendido para atender tres o más personas. Si Belén , Antonio y que Ana quieran generar una llave secreta, el procedimiento es el siguiente:
1. Antonio escoge un entero grande cualquier x y calcula
X = gx (mod n)
2. Belén escoge un entero grande cualquier y y calcula
Y = gy (mod n)
3. Ana escoge un entero grande cualquier z y calcula
Z = gz (mod n)
4. Antonio envía X para Belén , Belén envía Y para Ana y Ana envía Z para Antonio.
5. Antonio calcula Z' = Zx (mod n)
6. Belén calcula X' = Xy (mod n)
7. Ana calcula Y' = Yz (mod n)
8. Alice envía Z' para Belén , Belén envía X' para Ana y Ana envía Y' para Antonio.
9. Alice calcula k = Y'x (mod n)
10. Belén calcula k = Z'y (mod n)
11. Ana calcula k = X'z (mod n)
La llave secreta k es igual a gxyz (mod n) y este protocolo puede ser fácilmente extendido para cuatro o más personas.
