MOOC El algoritmo RSA


Lección 3. Cifrado de números y mensajes
Dr. Jorge Ramió Aguirre - 12/04/2012 

En esta tercera lección analizaremos el protocolo de intercambio seguro de clave de Diffie y Hellman, su implementación con RSA y las operaciones de cifrado de números y de mensajes de texto con este algoritmo, dedicándole 3 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 RSA03] 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. Comprender la necesidad de un intercambio seguro de clave.
  • 2. Conocer las limitaciones de velocidad de los sistemas de cifra asimétricos.
  • 3. Proponer esquemas de cifrado de textos con RSA.
  • 4. Comprobar las limitaciones del sistema RSA en la cifra de documentos.

Software que vas a utilizar en esta lección


APARTADO 3.1. EL INTERCAMBIO DE CLAVE DE DIFFIE Y HELLMAN

Como ya se ha indicado en la Lección 1, el inicio de los sistemas de cifra con clave pública se remonta a noviembre de 1976 con la propuesta de Diffie y Hellman, cuyo protocolo se muestra en la siguiente diapositiva.

Protocolo básico de intercambio de clave de Diffie y Hellman

Antes de continuar, debemos aclarar dos cosas:

  1. ¿Qué es un generador o raíz primitiva?
  2. ¿Por qué debe usarse una raíz primitiva en este protocolo?

En cuanto a la primera pregunta, una raíz primitiva o generador dentro de un primo p, es aquel número elemento de ese primo que genera todos los restos al hacer la operación de elevarlo a dichos restos y reducirlo módulo p. Es decir, si decimos que α es una raíz primitiva del primo p, entonces α1 mod p; α2 mod p; α3 mod p; ... ; αp-2 mod p y αp-1 mod p entregarán resultados distintos desde el 1 a p-1, y por tanto generará todos los restos del primo p.

Por ejemplo en el primo p = 17, el número 3 es una raíz primitiva porque entrega los resultados que se ven en la siguiente tabla, todos los restos desde el 1 hasta el 16.

31 mod 17 = 3 32 mod 17 = 9 33 mod 17 = 10 34 mod 17 = 13
35 mod 17 = 5 36 mod 17 = 15 37 mod 17 = 11 38 mod 17 = 16
39 mod 17 = 14 310 mod 17 = 8 311 mod 17 = 7 312 mod 17 = 4
313 mod 17 = 12 314 mod 17 = 2 315 mod 17 = 6 316 mod 17 = 1

Con relación a la segunda cuestión, el valor de α no puede ser cualquiera porque sólo un generador en el cuerpo tiene esa propiedad de que C = αx mod p tiene un único valor de x que es solución en p. Si usamos cualquier otro número que no sea un generador, el protocolo sigue funcionando pero existirán varios valores de x válidos como solución en la expresión anterior C = αx mod p, siendo entonces el protocolo más débil ante un ataque.

En la prácticaRSA3.1.1 vas a usar un nuevo software de laboratorio llamado ExpoCrip para encontrar las raíces primitivas de varios números primo.
Importante: Si estás trabajando con Windows 7 y 64 bits, es posible que recibas mensajes de error por la falta de los archivos comdlg32.ocx y tabctl32.ocx. Si es así, por favor instala versiones recientes de estos ocx. En esta página encontrarás el archivo comdlg32.ocx y cómo hacerlo, y en esta otra el archivo tabctl32.ocx. Para el registro de cada programa, debes tener permiso de administrador: debes ejecutar como administrador desde el botón derecho en el icono del sistema de tu PC.

El problema del protocolo de Diffie y Hellman así enunciado es que el secreto compartido αab mod p sólo se conoce a posteriori, una vez terminado el protocolo; es decir no permite enviar un número secreto previamente calculado.

En el ejercicioRSA3.1.1 vas a simular algunos intercambios de clave de Diffie y Hellman entre Alicia y Bernardo, usando la calculadora de Windows y el software Fortaleza de Cifrados.

Existe, eso sí, una variante de este protocolo que permite intercambiar un valor secreto generado o conocido a priori y que, de hecho, se usa en aplicaciones de correo electrónico seguro como PGP que utilizan Diffie y Hellman para el intercambio de clave. La siguiente diapositiva muestra este protocolo.

Protocolo de Diffie y Hellman con clave de sesión KAB calculada previamente

El ejercicioRSA3.1.2 te permitirá comprobar cómo funciona este segundo protocolo de Diffie y Hellman en el intercambio de una clave de sesión, primero entre Alicia y Bernardo y luego entre Bernardo y Alicia.

Hay otros aspectos muy interesantes en el protocolo de Diffie y Hellman, pero no es el objetivo de este curso estudiarlos aquí al estar centrado sólo en RSA. En el caso que nos interesa en este curso, ese problema de temporalidad en el envío de una clave no existe con RSA porque si deseamos enviar al receptor R un número secreto N, simplemente hacemos el cálculo NeR mod nR = C y enviamos al receptor el criptograma C en el cual se encontrará enmascarado el secreto N.

Cuestiones para reflexionar e investigar:
1. ¿Qué porcentaje de generadores se encuentran dentro de un cuerpo p para primos en general y para primos seguros? Usa para ello el software ExpoCrip. Nota: aunque este programa los presenta como primos fuertes, en realidad son primos seguros.
2. ¿Por qué decimos que el segundo protocolo mostrado de Diffie y Hellman permite el envío de una clave de sesión para correo electrónico seguro?


APARTADO 3.2. IMPLEMENTACION DEL INTERCAMBIO DE CLAVE CON RSA

Para enviar una clave de sesión con RSA, basta con cifrar ese número secreto con la clave pública del destinatario, puesto que sólo ese receptor será capaz de descifrar ese criptograma y recuperar el secreto enviado usando su clave privada.

En la prácticaRSA3.2.1 vas a simular el envío de una clave de sesión de 128 bits a un servidor que nos presenta una clave RSA de 1.024 bits, usando el software genRSA.

La siguiente figura es una captura de pantalla del intercambio de la clave K = 123456789000000000000000000000987654321 de la práctica anterior .

Intercambio de una clave de sesión K de 128 bits en RSA con genRSA

En la prácticaRSA3.2.2 repetirás la práctica anterior usando ahora el software ExpoCrip para obtener las siguientes pantallas.



Intercambio de una clave de sesión K de 128 bits en RSA con ExpoCrip

La última prácticaRSA3.2.3 de este apartado consiste en enviar cifrada mediante el programa ExpoCrip una clave de sesión K de 192 bits (58 dígitos) a un servidor Web cuya clave es el último desafío RSA resuelto de 768 bits en diciembre de 2001, y cuyos números primos se indican en la siguiente captura de pantalla del programa factor.exe.

Primos p y q del desafío RSA 768 resuelto en diciembre de 2009

Cuestiones para reflexionar e investigar:
1. Si siempre debe cifrarse un elemento del cuerpo n, es decir valores desde 0 hasta n-1, ¿por qué no es esto un problema en un intercambio de clave de sesión en SSL/TLS?
2. ¿Qué tipo de intercambio de clave te parece más seguro, DH o RSA?


APARTADO 3.3. CIFRANDO MENSAJES CON RSA

Los sistemas de clave pública o asimétricos tienen una velocidad de cifra en torno a los cientos de KiloBytes por segundo, muy lenta si la comparamos con la velocidad de los sistemas de cifra con clave secreta que está en los cientos de MegaBytes por segundo, mil veces más rápidos.

Por tanto, aunque podemos codificar el mensaje M con la codificación que se nos ocurra -puede haber miles- para transformar esa información a un conjunto a números y usar luego RSA para cifrar esa cadena de valores, en la práctica no tiene sentido hacerlo por esta velocidad tan baja.

De esta manera, este tipo de cifra quedará relegada a un ejercicio simple de laboratorio pero sin aplicación real alguna.

Para cifrar con RSA mensajes de texto es menester que previamente codifiquemos el texto a cifrar, por ejemplo según los valores en decimal en tres dígitos de los caracteres en código ASCII. Como se ha comentado, pueden existir infinitas maneras de codificar el texto en claro: dando un peso o valor a cada carácter según un alfabeto dado, dando peso a un conjunto de caracteres, modificando estos pesos, etc.

Cifrando mensajes ASCII con genRSA

Método de cifra de mensajes con genRSA:

1. El software genRSA cifra bloques completos de bytes tomando como entrada el valor decimal del código ASCII.
2. Conocido el módulo, se calcula su tamaño en bytes.
3. Para que puedan cifrarse todos los valores de entrada, se formarán bloques de un byte menos que ese módulo.

Por ejemplo, si el módulo n de RSA es el número 39.618.947, que en binario es 10010111001000100110000011, con 26 bits, deberemos cifrar bloques de 3 bytes -es decir 24 bits- pues así todos los valores posibles serán elementos de n.

Módulo n de 26 bits

En el ejercicioRSA3.3.1 vas a calcular el tamaño de los bloques RSA para cifra de texto con diferentes valores del módulo n.

Para la siguiente clave RSA, en donde p = 5.923, q = 6.689, n = 39.618.947, e = 31, d = 5.110.495, vamos a cifrar el mensaje de texto de 18 caracteres M = CALCULANDO BLOQUES.

Clave RSA del ejemplo con genRSA

1. Como n tiene un tamaño de 26 bits, vamos a cifrar bloques de 3 bytes.
2. Si el mensaje es M = CALCULANDO BLOQUES, cifraremos estos 6 bloques: CAL   CUL   AND   O_B   LOQ   UES.
3. Buscamos en una Tabla ASCII los valores binarios de los caracteres y pasamos su valor a decimal usando la calculadora de Windows.
4. Los 6 bloques serán:
  4.1. CAL = 01000011   01000001   01001100 = M1 = 4.407.628
  4.2. CUL = 01000011   01010101   01001100 = M2 = 4.412.748
  4.3. AND = 01000001   01001110   01000100 = M3 = 4.279.876
  4.4. O_B = 01001111   00100000   01000010 = M4 = 5.185.602
  4.5. LOQ = 01001100   01001111   01010001 = M5 = 5.001.041
  4.6. UES = 01010101   01000101   01010011 = M6 = 5.588.307
5. Usamos el software Fortaleza de Cifrados para encontrar los criptogramas C1 a C6 y luego descifrarlos como M1 a M6 .

  Cifrado: C1: 4.407.62831 mod 39.618.947 = 6.734.280         Descifrado: M1: 6.734.2805.110.495 mod 39.618.947 = 4.407.628
  Cifrado: C2: 4.412.74831 mod 39.618.947 = 21.898.080       Descifrado: M2: 21.898.0805.110.495 mod 39.618.947 = 4.412.748
  Cifrado: C3: 4.279.87631 mod 39.618.947 = 33.215.194       Descifrado: M3: 33.215.1945.110.495 mod 39.618.947 = 4.279.876
  Cifrado: C4: 5.185.60231 mod 39.618.947 = 30.956.224       Descifrado: M4: 30.956.2245.110.495 mod 39.618.947 = 5.185.602
  Cifrado: C5: 5.001.04131 mod 39.618.947 = 8.150.418         Descifrado: M5: 8.150.4185.110.495 mod 39.618.947 = 5.001.041
  Cifrado: C6: 5.588.30731 mod 39.618.947 = 22.796.302       Descifrado: M6: 22.796.3025.110.495 mod 39.618.947 = 5.588.307

Como puedes observar, hemos recuperado el mensaje M = CALCULANDO BLOQUES. Simplemente pasamos a binario el número recuperado en el descifrado y vamos leyendo los bits de derecha a izquierda y formando bloques de 8 bits, un byte. En la última lectura, si es necesario añadimos ceros a la izquierda hasta formar 8 bits.

Cifrado del texto CALCULANDO BLOQUES con genRSA

Para comprobar que el descifrado 43414C43554C414E444F20424C4F51554553 corresponde al texto en claro, puedes usar cualquier conversor de hexadecimal a ASCII 256 como este Online conversion utilities.

Texto en claro CALCULANDO BLOQUES

¿Qué sucedería ahora si el mensaje es sólo la palabra CALCULANDO? Repite el ejemplo anterior para este nuevo mensaje cuyo último bloque no se completa al ser sólo la letra O. Comprobarás que no es necesario incluir un relleno de bits hasta completar el último bloque, como sí se hace en los bloques de cifrado simétrico en algoritmos como DES, 3DES, IDEA, AES, etc.

Cifrando mensajes ASCII con ExpoCrip

Método de cifra de mensajes con ExpoCrip:

1. El software ExpoCrip cifra bloques completos de dígitos decimales.
2. Codifica el texto de entrada mediante el código ASCII en bloques de 3 dígitos decimales.
3. Conocido el módulo, se cuentan sus dígitos y el tamaño del bloque a cifrar tendrá un dígito menos.
4. En texto de entrada representado en un único número decimal ASCII se va cifrando en bloques de ese tamaño.

Como este sistema de cálculo de bloques es algo más complejo que el usado por el software genRSA, ya explicado, éste se detallará en la siguiente práctica.

En la prácticaRSA3.3.1 vas a comprobar esta cifra de texto usando el software genRSA y luego el software ExpoCrip.

Cuestiones para reflexionar e investigar:
1. ¿Qué otras formas de codificación de textos para su cifrado con RSA se te ocurren?


APARTADO 3.4. TEST DE EVALUACION DE LA LECCION RSA03

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. En la propuesta inicial del intercambio de clave de Diffie y Hellman:

a) El secreto compartido se conoce en la primera mitad del protocolo
b) El secreto compartido se conoce una vez terminado el protocolo
c) El secreto compartido lo conoce antes el usuario que inicia el protocolo

2. El valor α que se usa en el intercambio de claves de DH:

a) Debe ser un generador del cuerpo p
b) Debe ser un primo menor que p
c) Debe ser un número pequeño

3. En RSA el intercambio de clave de sesión K se hace cifrando ese valor con:

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

4. Ante la pregunta si es posible cifrar mensajes de texto con RSA, contestaríamos:

a) No, solamente es posible cifrar números
b) Sí, pero sólo cifrar, no firmar
c) Sí, formando bloques mediante alguna codificación

5. Normalmente se cifran números de centenas de bits en RSA porque el sistema:

a) Es mucho más rápido que los cifradores de clave secreta
b) Es mucho más lento que los cifradores de clave secreta
c) No permite cifrar mensajes


Ir a: [Portada c4y]    [Lección 2] [Índice] [Lección 4]