Complejidad y criptografía

La criptografía es la ciencia encargada del estudio y diseño de sistemas que permiten ocultar información.Desde sus inicios, esta capacidad de encubrimiento se ha basado en la dificultad que supondría a una entidad no autorizada el obtener la información original escondida en un conjunto de datos cifrado.Un algoritmo tiene utilidad si es fácilmente resoluble, esto es, pertenece a la clase P (Talbot, 2006:15).Sin embargo, desde un punto de vista criptográfico, no poder hallar una solución a un problema de una forma práctica en términos computacionales (es decir, no pertenecer a la clase P) se traduce en seguridad (Rothe, 2005:2).A pesar de haberse desarrollado por separado, en la actualidad ambos campos están fuertemente ligados: La criptografía depende de los resultados proporcionados por la teoría de la complejidad, a la vez que las investigaciones en esta última son en muchas ocasiones promovidas por problemas desarrollados en un marco criptográfico (Rothe, 2005:1).Existe una serie de problemas matemáticos comúnmente utilizados en los sistemas criptográficos.Sin embargo, no es trivial comprobar que uno de estos números sea realmente primo.Este problema ha sido investigado a conciencia y se han descubierto algunos tests de primalidad que reducen su complejidad.El test de Fermat se fundamenta en el pequeño teorema de Fermat, que demuestra que, si n es primo, para cualquier número natural a coprimo con n se cumple que Se trata de un test probabilístico que, para determinar si un número n es primo, realiza la prueba anterior para diferentes valores de a.Cuantos más valores se prueben, mayor probabilidad de que n sea realmente primo.No obstante, este test apenas se utiliza, debido entre otras cosas a los números de Carmichael, que siempre satisfacen la igualdad del pequeño teorema de Fermat pero no son primos.Al igual que los anteriores, se trata de un test probabilístico.Diseñado en 2002 por Manindra Agrawal, Neeraj Kayal y Nitin Saxena, AKS es el primer algoritmo determinista de primalidad.Sirvió además para demostrar que este problema pertenece a la clase de complejidad P y, por tanto, es computacionalmente practicable.Sí existen, sin embargo, algoritmos para factorizar números con determinadas características, por lo que conviene tomar ciertas precauciones a la hora de elegir los números que serán la base de un criptosistema.divisiones (si no se comprueba que cada divisor sea verdaderamente primo).conocidos, se puede optar por probar todos los posibles valores de x menores que p. No obstante, esto requeriría del orden de p operaciones.Se trata de un algoritmo cuya complejidad temporal y espacial esPese a mejorar al anterior algoritmo, éste sigue siendo poco eficiente y, en consecuencia, desaconsejado (Rothe, 2005: 368).Este algoritmo, cuya complejidad temporal para una entrada de m bits es, tiene una complejidad espacial despreciable, siendo entonces más eficiente que el algoritmo paso-gigante paso-enano y por tanto preferible (Menezes, 1997:106).El mismo algoritmo cuántico usado para la factorización de enteros también puede ser aplicado al problema del logaritmo discreto.Suelen estar fundamentados en el uso de funciones trampa, esto es, funciones fáciles de computar si se conoce cierta información, pero difíciles si se desconoce.También hubo diseños basados en el problema de la mochila, pero algunos fueron criptoanalizados con éxito, por lo que este enfoque ya no se utiliza.Presentado en 1977 por Ron Rivest, Adi Shamir y Leonard Adleman, se trata del criptosistema de clave pública más usado hasta la fecha (Menezes, 1997:285).La seguridad del criptosistema de Merkle-Hellman se basaba en que, dado un criptograma C y una clave pública Kpu, hallar los valores de Kpu tales que suman C se reduce a resolver el problema de la mochila, el cual es computacionalmente intratable.Sin embargo, en 1984 Adi Shamir diseñó un algoritmo que, para la mayoría de los casos, permitía obtener la clave privada partiendo de la clave pública en tiempo polinómico, y con ello descifrar los criptogramas (Menezes, 1997:302).Sin embargo, debe hacerse notar que este algoritmo NO resuelve el problema de la mochila, tan solo halla la clave privada del criptosistema.La idea principal es ocultar el mensaje introduciendo errores de un modo que el receptor sepa corregirlos.Esto es debido principalmente a sus tamaños de clave (219 bits = 64 Mbytes para la clave pública) y a su factor de expansión del mensaje (para los parámetros recomendados por McEliece, el criptograma tiene un tamaño un 60% mayor que el mensaje en claro) (Menezes, 1997:299).