Criptografía, MAPLE y RSA
Autor: Carlos B. Escuela Técnica Superior de Ingenieros de Telecomunicación. Universidad Politécnica de Madrid. Marzo de 1998
“Un analfabeto digital es un analfabeto” Nicholas Negroponte
Resumen
En este trabajo se utiliza el sistema de computación matemática MAPLE V R4 como soporte didáctico para introducir la criptografía y especialmente el algoritmo de clavepública RSA. Primeramente se introducen los conceptos fundamentales de criptografía y criptosistemas, haciendo especial hincapié en el esquema RSA, para más tarde tratar cómo sería la implementación de RSA con ordenador utilizando MAPLE. Los algoritmos que se presentan en la tercera parte no están optimizados para una ejecución veloz, y por lo tanto sólo deben ser utilizados para codificarpequeñas cantidades de datos. Sin embargo, con ligeras modificaciones se puede mejorar su velocidad de ejecución de manera notable.
Agradecimientos
Querría expresar mi agradecimiento a Francisco Ballesteros Olmo, por haberme dirigido esta monografía, tanto en el enfoque como en la discusión de los pormenores de la implementación de los algoritmos. Deseo además agradecer a David Rodríguez Ibeas susinnumerables comentarios que suscitaron correcciones en los puntos de vista adoptados para la implementación del código de los algoritmos. También querría hacerle patente mi agradecimiento expreso por construir y mostrarme, de un día para otro, una función de conversión de texto a número entero y por explicarme la codificación en base 256 de los caracteres ISO-Latin 1 con un algoritmo de suinvención. Su interés y dedicación sobrepasaron los límites de la amistad. La función “val” por él diseñada no está incluida debido a que MAPLE dispone de la función parse, que es idéntica a la por él realizada, pero los algoritmos “file2declist” y “dec2word” están basados en sus ideas. A los dos, muchas gracias por el tiempo y el esfuerzo que me han prestado.
Conceptos de criptografía
Introducción
Lacriptografía es la ciencia que se ocupa de la escritura secreta. Desde la Antigüedad los
Page 1
hombres han necesitado cifrar sus mensajes para que pudieran ser enviados por canales inseguros sin ser interceptados por terceras personas. Hay a lo largo de la Historia muchos ejemplos de sistemas criptográficos utilizados por personas relevantes: Cesar, Vigenère, Beaufort,… pero todos ellosson fáciles de “romper” aun sin saber la clave (mediante, por ejemplo, sustituciones estadísticas o simple “fuerza bruta”). La criptografía moderna, sin embargo, se encarga de la construcción de esquemas eficientes para los cuales es inviable (no imposible) recuperar el texto original a partir del texto cifrado. El lector puede preguntarse ahora qué diferencia hay entre inviable e imposible. Paraexplicar la diferencia entre ambos vocablos necesitamos primero definir qué es una función de un sólo sentido. Definición. Una función f ; [ 0, 1 ] ? [ 0, 1 ] se llama unidireccional si y sólo si: (i) existe un algoritmo eficiente que para una entrada x produzca una salida f(x). (ii) dada f(x), donde x se ha seleccionado uniformemente, no es viable encontrar, con probabilidad apreciable, unapreimagen de f(x), es decir, si un algoritmo intenta encontrar una preimagen de f(x) en tiempo finito la probabilidad de que lo encuentre es despreciable. A la luz de la anterior definición vemos la diferencia entre inviable e imposible. Lo primero significa que hay una probabilidad muy pequeña pero existente de encontrar una preimagen sin conocer la función, mientras que lo segundo quiere decir que noexiste probabilidad alguna. Los algoritmos utilizados para cifrar siempre tienen función preimagen (si no sería imposible obtener de vuelta el texto original), lo que sucede es que encontrarla por azar es muy difícil. Hemos utilizado el término “eficiente”, pero no nos ocuparemos de definirlo formalmente. Podríamos, simplemente, decir que es un algoritmo que funciona de manera correcta. Para…
