MOOC El algoritmo RSA


Lección 1. Los principios del algoritmo RSA
Dr. Jorge Ramió Aguirre - 15/03/2012 

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 descargar las diapositivas del curso en formato pptx animado o bien en pdf, puedes hacerlo 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

  • 1. Introducir los conceptos del diseño del algoritmo RSA.
  • 2. Proporcionar elementos de juicio que permitan analizar las variables que intervienen en la generación de claves RSA.
  • 3. Conocer las fortalezas y debilidades del sistema de cifra RSA.
  • 4. Familiarizarse con software relacionado con la generación de claves RSA.

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 exorbitante.

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 tipo exponencial 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:

  • 1. Los usuarios Alicia y Bernardo eligen cada uno un grupo n = p x q.
  • 2. Actualmente p y q son primos de valores iguales o superiores a 512 bits.
  • 3. Alicia y Bernardo hacen público el cuerpo o módulo de trabajo n.
  • 4. En el caso de Alicia ese módulo será nA = pA x qA y en el caso de Bernardo será nB = pB x qB.
  • 5. Los valores de los primos p y q serán un secreto, sólo conocido por los propietarios de esas claves.
  • 6. Cada usuario calculará el Indicador de Euler Φ de ese módulo n, que en este caso de dos primos es Φn = (p - 1)(q - 1).
  • 7. Así, Alicia calcula ΦnA = (pA - 1)(qA - 1) y Bernardo calcula ΦB = (pB - 1)(qB - 1).
  • 8. Ese valor va a ser su secreto o trampa, un número que sólo conoce su dueño.
  • 9. A partir de ese valor trampa Φ se calculará ahora la clave pública e y la correspondiente clave privada d.
  • 10. Cada usuario eligirá un valor de clave pública e dentro el siguiente intervalo: 1 < e < Φ(n).
  • 11. Para asegurarse que exista el inverso multiplicativo, y por tanto la clave privada d, debe cumplirse que mcd [e, Φ(n)] = 1.
  • 12. Ese valor e será la segunda parte de su clave pública, además del módulo n.
  • 13. Alicia elige como clave pública 1 < eA < ΦA y Bernardo elige como clave pública 1 < eB < ΦB.
  • 14. Usando ahora el Algoritmo Extendido de Euclides, cada usuario calcula su clave privada d.
  • 15. Alicia calcula dA = inv (eA, ΦA) y Bernardo calcula dB = inv (eB, ΦB).
  • 16. Luego, cada usuario tiene dos valores que forman su clave pública, n y e, y un valor secreto que es su clave privada d.
  • 17. Además del valor d, también guardarán en secreto p y q, que le servirán para acelerar la operación de descifrado.

Repasa estos conceptos en la siguiente diapositiva.

Pasos para generar una clave RSA

Observación:
Se suponen conocidos los principios básicos de la matemática discreta, un tema que será tratado en un próximo curso de este MOOC Crypt4you. No obstante, puedes repasar estos principios de teoría de números en el Capítulo 7 del Libro Electrónico de Seguridad Informática y Criptografía V 4.1.

En el siguiente ejercicioRSA1.3.1 vas a calcular el inverso de un número usando el algoritmo extendido de Euclides.

Vas a generar ahora en el ejercicioRSA1.3.2 tu primera clave RSA.

Aunque en la práctica anterior y siguiendo el protocolo de generación de claves RSA hemos elegido un número cualquiera para la clave e, más adelante veremos que en la práctica los usuarios no eligen el valor de esa clave pública, sino que ésta viene impuesta por un número especial: el número 4 de Fermat.

¿Qué sucedería si nos dejan elegir la clave pública y optamos por e = Φ(n) - 1?

Para apreciar lo que sucede, usa el software Fortaleza de Cifrados para calcula el inv [e, Φ(n)] para diferentes valores de Φ(n), por ejemplo para n = 35 = 7x5, n = 161 = 7x23, n = 221 = 13x17, n = 6.479 = 11x31.

En la prácticaRSA1.3.1 vas a generar una clave 16 bits.

Vas a generar ahora en la prácticaRSA1.3.2 claves de diversos tamaños hasta 2.048 bits, tanto en formato decimal como en hexadecimal, de forma manual y de forma automática.

Recuerda que hacer públicos los valores de e y n, no pone en peligro la clave privada d puesto que para calcular d = inv [e, Φ(n)] hace falta conocer la trampa (p - 1)(q - 1), es decir los primos p y q, y ya hemos visto que si estos primos son mayores que 500 bits esta tarea es computacionalmente imposible a fecha actual.

Para terminar, un apunte. Los valores de p y q se guardan para poder usar en el descifrado el teorema chino del resto como veremos en una próxima lección.

Cuestiones para reflexionar e investigar:
1. Aunque el intervalo de la clave pública e se define como 1 < e < Φ(n), ¿por qué el valor de e no podría ser el número 2?
2. ¿Te ha llamado algo la atención de lo que has visto en esta práctica de generación de claves RSA?
3. ¿Qué puedes decir de los tamaños en bits que aparecen en la aplicación para todas las claves de la prácticaRSA1.3.2?
4. ¿Pensabas que era más difícil o más lento crear una clave de 1.024 ó 2.048 bits?


APARTADO 1.4. OPERACIONES DE CIFRADO Y DESCIFRADO RSA ENTRE ALICIA Y BERNARDO

En la diapositiva "Pasos para generar una clave RSA" del apartado anterior, aparecían al final dos operaciones: cifra y firma. Vamos a analizar estas operaciones en éste y en el siguiente apartado.

Debe recordarse que el principio básico de los sistemas de cifra con clave pública es que lo que se cifra con una clave, sólo puede descifrarse con la clave inversa de aquella, usando el mismo cuerpo de cifra.

Intercambio de clave:
Operación de cifrado con RSA para obtener confidencialidad: Alicia desea enviar un mensaje secreto M a Bernardo.

Observación: aunque se indique que se va a cifrar un "mensaje" M, en la práctica el sistema RSA y todos los sistemas de cifra asimétrica cifrarán números N y no mensajes.

En criptografía de clave pública se cifran números

Como Alicia conoce la clave pública de Bernardo, nB y eB, va a realizar la siguiente operación: MeB mod nB = C, enviando entonces a Bernardo este criptograma C.

Dado que Bernardo es el único que conoce su clave privada dB, sólo él podrá realizar la siguiente operación: CdB mod nB.
Observa que CdB mod nB = [MeB mod nB]dB mod nB = [MeB]dB mod nB.

Puesto que en la operación [MeB]dB mod nB los exponentes se anulan entre sí porque son inversos, en recepción Bernardo recuperará el mensaje M enviado por Alicia dentro del cuerpo nB.

En realidad, lo que sucede es lo siguiente:

1. Como dB = inv [eB, Φ(nB)], entonces eB x dB = k Φ(nB) + 1.
2. Por tanto[MeB]dB mod nB = Mk Φ(nB) + 1 mod nB = M x Mk Φ(nB) mod nB.
3. Por el Teorema de Euler tenemos que que Mk x Φ(n) mod n = 1.
4. Luego M x Mk Φ(nB) mod nB = M x 1 = M y se recupera el mensaje.

En el ejercicioRSA1.4.1 vas a enviar de forma confidencial el valor 101 a un usuario cuya clave pública RSA es n = 5.963 y e = 13.

Como los números son muy pequeños, en la práctica anterior podríamos haber utilizado la calculadora de Windows para realizar la operación 10113mod 5.963. No obstante, cuando los números son muy grandes no podremos realizar la operación de exponenciación usando dicha calculadora pues nos devolverá como error "Invalid input for function" cuando pulsamos Mod.

En la prácticaRSA1.4.1 comprobarás lo indicado en el párrafo anterior para la operación: 100.24530.479mod 790.657.667.

Vamos a solucionar la limitación de dicha calculadora a trabajar con números grandes utilizando, por ejemplo, el software Fortaleza de Cifrados.

Aunque en la próxima lección analizaremos los tamaños de números usados para la generación de una clave RSA, en las siguientes prácticaRSA1.4.2 y prácticaRSA1.4.3 vamos a adelantarnos un poco y generar algunas claves que van a tener ciertas características interesantes.

Cuestiones para reflexionar e investigar:
1. ¿Qué relación tiene el valor de la clave pública en hexadecimal 010001 que has usado en la práctica anterior con el Número 4 de Fermat?
2. Convierte el valor hexadecimal 10001 a binario. ¿Crees que tiene alguna utilidad usar este número con tantos ceros como clave pública e?


APARTADO 1.5. OPERACIONES DE FIRMA Y COMPROBACION DE FIRMA RSA ENTRE ALICIA Y BERNARDO

Si en la cifra usamos nuestra clave privada, obtendremos un criptograma que posteriormente dará lugar a una firma digital.

Firma digital:
Operación de cifrado con RSA para obtener integridad y autenticidad: Alicia desea enviar un mensaje M firmado a Bernardo.

Alicia realiza la siguiente operación con su clave privada dA: MdA mod nA = C, enviando el criptograma de firma C.

Dado que Bernardo conocerá la clave pública de Alicia, nA y eA, podrá realizar la siguiente operación: CeA mod nA.

Observa que CeA mod nA = [MdA mod nA]eA mod nA = [MdA]eA mod nA.

Como en la operación [MdA]eA mod nA los exponentes se anulan entre sí entregando el valor 1 como ya hemos visto, Bernardo recupera el mensaje M firmado por Alicia dentro del cuerpo nA. Por lo tanto: CeA mod nA = M.

En la prácticaRSA1.5.1 vas a firmar y comprobar dicha firma.

Uso de funciones hash en firma digital

Como ya se ha comentado, en los sistemas de cifra asimétricos como es el caso de RSA, en la práctica sólo se cifrarán números y además valores relativamente pequeños: sólo centenas de bits.

Por tanto una firma digital se realizará sobre un número, resultado de aplicar una función hash a un mensaje, ahora sí un archivo ya de cualquier tamaño y tipo.

Pasos a realizar en la firma digital con RSA a través de un hash:

1. Alicia obtiene la función hash (un número) del archivo M que desea firmar.
2. Ese número debe representar al archivo de manera única, como si fuese una huella dactilar de él.
3. Sobre ese número o hash h(M) Alicia realizará la firma usando su clave privada dA.
4. Alicia calcula h(M)dA mod nA = s y le envía a Bernardo la dupla mensaje y firma (M, s).
5. Bernardo recibe (M', s) pues no se sabe si recibe el mismo mensaje M o un mensaje distinto o falso M'.
6. Bernardo realiza la siguiente operación con la clave pública de Alicia: seA mod nA = [h(M)dA mod nA]eA mod nA = h(M).
7. Es decir, recupera el valor h(M) que usó Alicia para su firma en el momento de emisión.
8. Bernardo calcula la función hash h(M') del mensaje M' recibido (puede ser el verdadero mensaje M u otro distinto M').
9. Si el hash calculado en recepción coincide con el hash recuperado y firmado en emisión, se acepta la firma como correcta.
10. En resumen, si h(M') = h(M) se acepta la firma y si h(M') <> h(M) se rechaza la firma.

Si Alicia quisiera también dar confidencialidad al mensaje, deberá además cifrarlo. Pero en este caso deberíamos hablar de cifradores simétricos e intercambio de claves, temas que serán tratados más adelante en Crypt4you, al igual que las funciones hash.

Cuestiones para reflexionar e investigar:
1. Una vez que Alicia comprueba que la firma procede de Bernardo, al deshacer la operación de Bernardo usando la clave pública de él, ¿cómo puede asegurarse que el mensaje es el original?
2. ¿Falta algo aquí para que la firma digital sea completa y permita comprobar autenticidad del emisor e integridad del mensaje?
3. Alicia podría hacer esta operación: MeA mod nA, es decir, cifrar algo con su propia clave pública. ¿De qué le serviría esto? ¿Por qué crees que en la práctica no se usa este tipo de cifra usando la clave pública del emisor?


APARTADO 1.6. TEST DE EVALUACION DE LA LECCION RSA01

En las siguientes 5 preguntas, elige la respuesta correcta.

Sería recomendable que la primera vez que contestes este test lo hagas sin repasar la lección.

1. Si una clave RSA usa p = 7, q = 11 y e = 7, sólo a través de cálculo mental indica cuál será la clave privada d.

a) 13
b) 43
c) 73

2. El problema de la factorización entera requiere un tiempo de cómputo, en función del tamaño de la entrada, de tipo:

a) Aleatorio
b) Lineal
c) Exponencial

3. Las claves pública e y privada d en RSA se calculan en el cuerpo:

a) Φ(n-1)
b) Φ(n)
c) n-1

4. Si en el cuerpo n = 46.031, producto de dos primos, ciframos el valor 48.065, ¿qué valor real estamos cifrando?

a) El valor 2.034
b) El valor -2.034
c) El valor 48.065

5. Si se desea realizar la firma sobre un número con RSA, deberá usarse:

a) La clave pública del receptor
b) La clave pública del emisor
c) La clave privada del emisor


Ir a: [Portada c4y]    [Introducción al curso] [Índice] [Lección 2]