Criptografía XVI

Por petición popular voy a darle un empujoncito al blog que lo tengo muy "dejao".
Seguimos con la criptografía.
Dejamos el otro día a dos locos buscando solución para poder intercambiar claves sin riesgo.
Diffie y Hellman se estrujaron los sesos buscando una función matemática que les permitiera realizar esa tarea. La mayoría de funciones matemáticas son funciones de doble vía, es decir son fáciles de hacer y fáciles de deshacer. Por ejemplo una función que triplica un número (2 se convierte en 6) es fàcil de deshacer simplemente dividiendo entre 3. Así que de entrada descartaron ese tipo de funciones y se centraron en las funciones de una via... que son fáciles de hacer, pero difíciles de deshacer. Una función de doble vía sería como encender una luz desde un interruptor, que volviendolo a pulsar la apagamos, y una función de vía única sería por ejemplo mezclar una pintura azul con otra amarilla...fácil de hacer, pero imposible de deshacer.
Entramos aquí en matemáticas modulares. Imaginemos un reloj de pared, de cuco, de péndulo, de cocina, como queráis, pero con varillas, ahora imagina que sólo tenemos números del 0 al 6.
Sumemos 2 + 3 con este reloj. Empezamos en el número 2 y avanzamos 3 lugares hasta llegar al 5, hasta aquí bien todo. Ahora calculemos 2+6. Comenzamos en el 2 y avanzamos 6 lugares: 3,4,5,6,0,1 . Al llegar al 6 volvemos a iniciar la rueda con el 0.
Estas sumas se podrían expresar de la siguiente manera:

2 + 3 =5 (mod 7) y 2 + 6 = 1 (mod 7)

Este tipo de suma modular la realizamos a diario. Si son las 9 de la mañana y tenemos una reunión dentro de 8 horas, no decimos que la tenemos a las 17, decimos que tenemos una reunión a las 5.

9 + 8 = 5 (mod 12)

Matemáticamente y para no estar todo el día imaginando relojes analógicos, para encontrar la solución a estas sumas, simplemente sumamos los sumandos (valga la redundancia) normalmente y luego dividimos la respuesta por el modular que queramos, el resto que queda es el resultado.

11 x 9 (mod 13)

11 x 9 = 99

99 / 13 = 7 y quedan 8

11 x 9 = 8 (mod 13)

Una gran diferencia entre estos dos tipos de aritmética radica en su linealidad. Por ejemplo tenemos una función 3^x para x=2 3^2 = 3 x 3 = 9

Si nos dieran el resultado y tuvieramos que averiguar x, sería bastante fàcil. Si el resultado fuera 81 podríamos probar con x=5. 3^5 = 243 demasiado alto. Bajaríamos a x=4 por ejemplo y daríamos con la respuesta. O sea, que podríamos ir tanteando según el resultado hasta localizar el número correcto.
Pero esto no sucede en aritmética modular. Imaginemos que nos dicen que 3^x en (mod 7) es = 1
¿Cuanto vale x? De entrada ni idea, así que probaríamos por ejemplo con x=5 y nos daría un resultado de 5. Lo lógico sería probar con un x más pequeño, pero nos equivocaríamos, pues el resultado correcto se obtiene para x=6.
Para averiguarlo podríamos crear una tabla con muchos valores hasta encontrar la respuesta correcta. Esto es factible para número pequeños, pero imaginemos la tabla para 453^x (mod 21.997)
Resumiendo: puedo calcular el resultado de una función en segundos, pero tardaría mucho tiempo si tuviera la respuesta e intentara invertir la función para averiguar x.
Estuvieron un par de años estudiando este tema hasta que consiguieron que Benito y Alicia se pudieran intercambiar una clave sin reunirse.

Centremonos ahora en el ejemplo:

La idea de Hellman se basaba en la función antes vista de la forma Y^x (mod P)
Alicia y Benito se llaman por teléfono y acuerdan valores para Y y P (supongamos y=7 y P=11).
Da igual que Eva tenga pinchado el teléfono de Alicia y oiga estos valores como veremos más adelante.

Veamos paralelamente y por fases lo que hacen Alicia y Benito

Fase 1

Alicia elige un número, por ejemplo el 3, y lo mantiene en secreto. Llamemos a este número A.
Benito elige un número, pongamos el 6, y lo guarda en secreto. Denominemos a este número B.

Fase 2

Alicia pone 3 en la función de una sola via y calcula el resultado 7^3 (mod 11) = 343 (mod 11)=2
Benito hace lo mismo 7^6 (mod 11) = 117649 (mod 11) = 4

Fase 3

Alicia llama al resultado de este cálculo @ y envia su resultado 2 a Benito.
Benito llama al resultado de su cálculo & y envia su resultado 4 a Alicia

Eva sigue a la escucha y ahora sabe los valores de la función Y=7 y P =11, además de los números intercambiados 2 y 4.

Fase 4

Alicia toma el resultado de Benito y calcula el resultado de &^A (mod 11) Recordemos que A es el número secreto de Alicia. 4^3 (mod 11) = 64 (mod 11) = 9

Benito toma el resultado de Alicia y calcula el resultado de @^B (mod 11) 2^6 (mod 11) = 64 (mod 11) = 9

Alicia y Benito han acabado con el mísmo número, el 9. Esa es la clave !!!
y esa es la clave que usarán para codificar sus mensajes secretos.

Ahora pongámonos en la situación de Eva.

Eva sabe que la función es 7^x (mod 11), conoce @=2 y &=4 lo único que desconoce es el número personal secreto escogido por cada uno de ellos, A=3 y B=6.
Para encontrar la clave Eva debe de hacer lo que hicieron Alicia y Benito, pero desconoce A y B, pues estos no se han intercambiado en ningún momento. Sólo le queda calcular @ o &, pues sabe que estos número salieron de poner A y B en la función. Pero por desgracia para ella, esta función es de una vía y el proceso es muy difícil, especialmente si los números son muy altos.

Este hallazgo obligó en 1976 al mundo criptográfico a reescribir las reglas de la codificación.

Pero no todo era perfecto. Si Alicia vive en un lugar del mundo y Benito en el opuesto necesitan acordar la clave, por lo que ambos deben de estar conectados al mismo tiempo. Si alicia quiere enviar un mail codificado a Benito tendrá que esperar a que despierte para poder intercambiar primero los números para obtener la clave. Podría Alicia enviar su parte del intercambio de clave y esperar 12 horas el mail de Benito con su parte. Esto entorpece la espontaneidad del email.
Tenemos ahora la seguridad de que Benito y Alicia no necesitan reunirse para pasarse la clave secreta, ahora sólo falta encontrar un sistema eficaz para la distribución de claves. Tenemos el intercambio pero no la distribución.
La siguiente genialiadad fue: mi clave de codificación es pública, todo el mundo sabe cual es, pero no me importa.

Pero esto lo dejaremos para el próximo capítulo.

Fuente: Los códigos secretos (Simon singh)