viernes, 30 de abril de 2010

Criptografía XVII


Nuestro amigo Diffie se centró en el problema de la distribución de claves en cuerpo y alma. Y así un día le vino a la mente una gran idea. Un nuevo tipo de cifra, una cifra asimétrica.

Hasta ahora todas la cifras eran de tipo simétricas, o sea que el proceso de descodificación era simplemente el opuesto al de codificación. Emisor y receptor utilizan la misma clave para codificar que para descodificar. En una cifra asimétrica si Alicia sabe la clave de codificación puede codificar un mensaje pero no descodificarlo. Para eso necesita otra clave.
Diffie tenía el concepto, pero no un ejemplo real. Había que encontrar una cifra asimétrica que funcionase en la vida real. De esta manera Alicia crearía su propio par de claves: una clave de codificación y otra de descodificación. Ella debe mantener en secreto su clave de descodificación pero publicará para todo el mundo su clave de codificación. De esta manera cualquiera puede enviar un mensaje codificado con la clave pública de Alicia, pero sólo ella puede descodificarlo con su clave privada.
Esto es una ventaja pues desaparecen las idas y venidas como con el intercambio Diffie-Hellman. Benito no tiene que esperar a que Alicia le envíe cierta información antes de poder mandarle el mensaje. También se soluciona el problema de la distribución de claves, pues no hace falta transportar de manera segura la clave pública a Benito, todo lo contrario, cuanta más gente la conozca mejor, así todo el mundo podrá enviarle mensajes codificados. Conocer la clave pública no ayuda a descubrir la clave privada de Alicia para leer los mensajes que le envían. Del mismo modo Alicia para escribir un mensaje codificado a Benito buscará la clave pública de Benito en algo parecido a una guía telefónica y codificará el mensaje.
Con el ejemplo de los candados la cosa quedaría algo así...todo el mundo puede cerrar un candado...pero sólo el que tiene la llave puede abrirlo. Saber cerrar un candado no implica ni da pistas para poder abrirlo.
Pero claro, todo esto es teoría... ¿pero que pasa con la práctica? ¿De donde sacamos una clave que sirva para codificar pero no para codificar y que encima la que descodifica no tenga nada en común con la que codifica? Hacía falta una función matemática nueva. Diffie publico su idea de clave asimétrica en verano de 1975 y rápidamente mucha gente se puso a buscar esta función... a final de año los ánimos habían decaído. Podría ser que ese tipo de funciones simplemente no existieran.
Aquí aparecen tres informáticos del MIT: Rivest, Shamir y Adleman. Durante su primer año de búsqueda no encontraron ninguna ecuación satisfactoria, pero de un día para otro a Rivest le vino la idea y creó el sistema RSA (Rivest, Shamir, Adleman)
La cifra de Rivest se basa en el sistema de funciones modulares descrita en la entrada anterior. Si alguien lo pide pondré la función de una sola vía más detallada en la próxima entrada, mientras nos centraremos en uno de sus valores principales llamado N que es lo que hace que estas funciones sean de una sola vía.
Cada persona puede elegir su valor personal de N y personalizar su función. Para elegir este valor N, Alicia coge dos números primos p y q y los multiplica uno por el otro. Por ejemplo p=17159 y q=10247, al multiplicarlos N=175828273. Esta es la clave pública de Alicia y la podría publicar en facebook, llevarla en sus tarjetas de visita e incluso perderla en la calle sin ningún riesgo, pues es la clave para que codifiquen mensajes que le enviaran a ella. Benito cogería N y lo insertaría en la función de una sola vía, que también es de dominio público, para codificar el mensaje y enviarselo a Alicia. Ahora el mensaje es seguro, pues por definición es my difícil descodificar una función de una sola vía. ¿Pero como descodifica Alicia el mensaje? Pues con p y q, los dos números que sólo conoce Alicia y que al multiplicarlos nos dieron N. Los detalles del funcionamiento de la función, si alguien lo pide, pues en la siguiente entrada.
Y os estareis preguntando...bueno pero si N ha salido de multiplicar p y q, no debe de ser tan dificil encontrar esos dos números., ¿no? Pues resulta que si N es suficientemente alto es virtualmente imposible deducir p y q a partir de N. Si yo os doy el número 408508091, a mi obtener ese número me ha costado con una calculadora un par de segundos, pero seguramente os costaría todo el día encontrar los números que he utilizado. Para poder hacerlo hay que factorizar el número. Factorizar es un proceso lento, primero empezaríamos dividiendo por 3 pero no divide exactamente, seguiríamos por el 5, pero tampoco, luego el 7, luego el siguiente número primo, etc... así hasta llegar al 18313, que es el número primo 2000. El siguiente factores es fácil de sacar dividieno N entre 18313, o sea 22307. Con una calculadora podríamos sacarlo en medio día. Pues vaya seguridad... con un ordenador esto se hace en segundos...
Vale, pues digamos que elegimos unos números primos mas altos, digamos del orden de 10^65, es decir un 1 seguido de 65 ceros. Esto resultaría un valor de N del orden de 10^130. A un ordenador le costaría multiplicar estos dos números primos menos de 1 segundo pero a ti con tu ordenador...algunos años. (posiblemente se colgaría o se estropearía antes). Pero como los criptógrafos no se fian de nada, supusieron que pasaría si cien millones de ordenadores trabajando conjuntamente intentaran factorizar el número...pues que tardarían unos 15 segundos. Así que hay que utilizar números más grandes. Para una gran seguridad se acepta que N debe ser del orden de 10^308 (un 1 seguido de 308 ceros).Ahora esos cien millones de ordenadores tardarían más de mil años en descifrar la clave. De momento el único peligro es que alguien piense una manera más rápida de factorizar. De momento no es algo que parezca posible.
El sistema RSA fue anunciado por primera vez en 1977 en Scientific American (Investigación y ciencia) y después de explicar su funcionamiento se desafiaba a los lectores a encontrar los valores de p y q dándo el número N de 123 cifras.
En 1994 un equipo de seiscientos voluntarios anunció los factores de N.
Actualmente lo habitual es codificar con un valor N lo suficientemente grande para que todos los ordenadores del mundo trabajando conjuntamente necesiten más tiempo que la edad del universo para poder romper la cifra.

No hay comentarios: