Dr. Jorge Ramió Aguirre 

Esta primera lección abordará los antecedentes históricos del algoritmo RSA, sus fundamentos matemáticos, la generación de claves y el cifrado, que se estudiarán a través de cinco apartados.

Si deseas ver todas las diapositivas de las 10 lecciones de este curso en formato Power Point animado o bien en pdf, puedes descargar el archivo desde esta dirección.

IMPORTANTE: Aunque existe un enlace directo a cada ejercicio y práctica de esta lección, éstos se encuentran todos juntos en el documento anexo [PDF-Ejercicios-Prácticas RSA01] de esta lección, que te recomiendo lo descargues e imprimas ahora mismo.

Recuerda que el tiempo máximo recomendado para el seguimiento de esta lección, la realización de sus prácticas y ejercicios, así como la búsqueda de información en la red sobre los temas abiertos planteados al final de cada apartado, es de dos semanas.

Temario

Objetivos

Software que vas a utilizar en esta lección


APARTADO 1.1. UN POCO DE HISTORIA

Los sistemas de cifra con clave pública tuvieron su inicio con la propuesta de Diffie y Hellman en noviembre del año 1976 para realizar un intercambio de clave computacionalmente seguro, usando para ello el problema del logaritmo discreto. Sin embargo, aunque dicha propuesta se convierte en un hito que revoluciona el mundo de la criptografía en aquellos años, hasta ese momento sólo de tipo simétrica y con una sola clave secreta, no permitía realizar una cifra real de información o la firma digital sobre un documento.

En febrero de 1978, es decir poco más de un año después de aquel intercambio de clave propuesto por Whitfield Diffie y Martin Hellman, otros tres investigadores norteamericanos, Ron Rivest, Adi Shamir y Leonard Adleman, proponen un sistema de cifra que llevará las iniciales de sus apellidos y el algoritmo se patenta como RSA.

A diferencia del intercambio de clave de DH, que basaba su fortaleza en la dificultad computacional de calcular logaritmos discretos en primos muy grandes, RSA basa su fortaleza en la dificultad computacional de factorizar un número compuesto muy grande, producto de dos primos grandes, y encontrar por tanto tales factores primos. Ambos problemas tienen una complejidad algorítmica similar y son inabordables para la capacidad mundial de cómputo en nuestros días cuando se trata de valores por encima de miles de bits.

No fueron fáciles los primeros años de este algoritmo pues nadie creía en su utilidad. Sin embargo, el tiempo fue dándoles la razón a sus inventores y finalmente se convirtió en un estándar, más precisamente PKCS #1 RSA Cryptography Standard.

Sin embargo, aunque Rivest, Shamir y Adleman son los autores de RSA, el mismo algoritmo de cifra asimétrico basado en la dificultad de factorizar números grandes fue descubierto mucho antes. En el año 1969 el Government Communications Headquarters GCHQ en Gran Bretaña comienza a trabajar en la idea de poder distribuir claves a través de una cifra no simétrica, llegando en el año 1973 -cinco años antes- a la misma conclusión que los creadores de RSA.

Esa investigación fue dirigida por el matemático Clifford Cocks. Desgraciadamente el trabajo fue considerado como alto secreto por el gobierno británico por lo que su contenido no se hace público ni se patenta como invento. Sobre este asunto de la criptografía unida a los servicios de inteligencia de los países existe bastante documentación en la Red.

Cuestiones para reflexionar e investigar: 1. ¿Qué papel jugó Ralph Merkle en el invento de la clave pública? 2. Encontrarás una interesante historia sobre el nacimiento de la criptografía de clave pública, y en especial sobre RSA, narrada magistralmente en el libro The Code Book por Simon Singh, documento liberado para uso personal y educativo a comienzos del año 2005 pero que actualmente sólo se encuentra de pago en librerías y en el sitio Web del autor. Sin embargo, puedes buscarlo en Internet porque esa versión se almacenó en diversos servidores. Dejamos esta tarea a los seguidores de Crypt4you. Si lo encuentras, por favor coméntalo en sus redes sociales Facebook y Twitter para beneficio de todos.

APARTADO 1.2. LA SEGURIDAD DEL ALGORITMO RSA

La seguridad del algoritmo RSA se basa en la dificultad computacional que conlleva encontrar los dos factores primos de un número compuesto muy grande, resultado del producto de éstos, donde sus primos también son números grandes. Esto es lo que matemáticamente se conoce como el problema de la factorización entera, uno de los problemas denominados No Polinomiales o de tipo NP, muy usados en la criptografía.

Se trata de un problema que en un sentido el cálculo es muy fácil y rápido (por ejemplo multiplicar dos números primos) pero que en sentido contrario (por ejemplo, encontrar esos dos factores conocido el producto) se vuelve computacionalmente intratable a medida que la entrada es cada vez mayor. Es decir, requiere de unos recursos informáticos excesivos y, por tanto, de un tiempo de cálculo exhorbitante.

En el ejercicioRSA1.2.1 te propongo que realices un conjunto de multiplicaciones. Posteriormente, te pido que encuentres los factores de números similares a los resultados de la primera parte del ejercicio para entender qué significa en la práctica el problema de la factorización entera.

Aunque no sea matemáticamente exacto, se podría aceptar que la primera operación es lineal en el sentido de que la cantidad de operaciones a realizar es directamente proporcional al tamaño de los dos operandos; en cambio, la segunda operación es de tipoexponencial de manera que, por ejemplo, aumentando al doble el tamaño de la entrada, el número de cálculos a realizar no aumenta al doble sino mucho más, reflejándose esto en una curva de tipo exponencial del tiempo de cálculo en función del tamaño de la entrada.

Realizando la prácticaRSA1.2.1 podrás comprobar dicho comportamiento.
Como comprobarás en la siguiente prácticaRSA1.2.2, no obstante la operación directa de multiplicación de dos números primos muy grandes es sencilla y consume escasos recursos computacionales.

Pero, ¿qué entendemos en el año 2012 por un número muy grande aplicado a la criptografía?

En el caso de RSA y ya en el año 2012, los valores mínimos de esos dos primos debe ser de 512 bits (unos 155 dígitos) en certificados digitales X.509 y, por tanto, su producto es un número de 1.024 bits (unos 310 dígitos), siendo su factorización un problema actualmente intratable. Aunque sólo se ha llegado a factorizar a fecha actual números de unos 700 bits (768 bits en 2009) como veremos en próximas lecciones, esto recomienda el aumento de esos primos por ejemplo a 1.024 bits cada uno con lo que se obtiene un producto de 2.048 bits, valor que se usa ya en diversos programas, algunas aplicaciones, certificados digitales y pasarelas seguras.

Cuestiones para reflexionar e investigar: 1. ¿Se te ocurre alguna forma de calcular el tiempo que tarda el programa factor.exe en encontrar los dos primos? Primero piénsalo y después de analizarlo y presentar tu propuesta, mira este ejercicio sobre el problema de la factorización entera. 2. ¿Por qué para pasar de dígitos a bits multiplicamos por 3,3 y para pasar de bits a dígitos, dividimos por dicho número?

APARTADO 1.3. ESQUEMA DE GENERACION DE CLAVES RSA CON DOS USUARIOS ALICIA Y BERNARDO

El protocolo detallado para la generación de un par de claves RSA es el siguiente:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Repasa estos conceptos en la siguiente diapositiva.

Pasos para generar una clave RSA
Lección 2. Valores de diseño de las claves →← Lección 4. Claves privadas y públicas parejas