MOOC El algoritmo RSA


Lección 5. Mensajes no cifrables
Dr. Jorge Ramió Aguirre - 21/05/2012 

Los cuatro apartados de esta quinta lección están dedicados al estudio de los mensajes o números no cifrables, es decir aquellos números que aunque se cifren con RSA usando una clave pública o una clave privada, se transmiten en claro. Determinaremos en esta lección si esta característica de RSA es o no un motivo de preocupación.

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 RSA05] 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. Entender qué son los mensajes no cifrables o números no cifrables en RSA.
  • 2. Conocer cómo se encuentran los números no cifrables.
  • 3. Proponer condiciones de diseño para minimizar estos números no cifrables.
  • 4. Conocer si la existencia de números no cifrables es una vulnerabilidad de RSA.

Software que vas a utilizar en esta lección


APARTADO 5.1. ¿QUE SON LOS MENSAJES NO CIFRABLES?

Aunque sea común hablar de mensajes no cifrables en un sistema de cifra de información, ya hemos comentado que en RSA sólo cifraremos números. Por lo tanto, en adelante nos referiremos a esta característica de RSA como números no cifrables o NNC.

Puesto que la operación de cifrado RSA de un número N es Nclave mod n, donde clave puede ser la pública de destino o la privada de emisión según la cifra que se desee realizar, y siendo los elementos N a cifrar todos los valores que van desde 0 hasta n-1, existirán algunos números N que, aunque se cifren, irán en claro. Como es evidente, el valor de la clave en ese exponente puede ser cualquier número entre 0 y n-1 que cumpla los requisitos que correspondan a dicha clave.

Dos casos obvios de números que se cifran y van en claro serán el 0 y 1 puesto que:
  0clave mod n = 0
  1clave mod n = 1.

Otro valor no tan obvio pero que puede demostrarse fácilmente que se transmite en claro es el número n-1 puesto que:
  n-1clave mod n = n-1.

Por ejemplo para la clave RSA con n = 323 y e = 11, se obtiene:
  011 mod 323 = 0
  111 mod 323 = 1
  32211 mod 323 = 322 (puedes comprobarlo con la calculadora de Windows)

Además de esos tres valores, en RSA existirán siempre como mínimo otros 6 valores que irán en claro. Por tanto, cualquier clave RSA tendrá como mínimo 9 números no cifrables.

En el ejemplo anterior, los otros seis valores que se transmiten en claro son:
  1811 mod 323 = 18 (comprueba todos estos valores con la calculadora de Windows)
  15211 mod 323 = 152
  15311 mod 323 = 153
  17011 mod 323 = 170
  17111 mod 323 = 171
  30511 mod 323 = 305

En la prácticaRSA5.1.1 vas a realizar algunos intercambios de claves secretas con el software Fortaleza de Cifrados que verás se trasmitirán en claro, entre ellos el valor 36.060 que aparece en la imagen para una clave RSA de 16 bits con n = 40.301 y e = 31.

Cifra del número secreto 36.060 que se transmite en claro

Pero, ¿cómo podemos encontrar estos valores de números no cifrables? Lo veremos en el siguiente apartado.

Cuestiones para reflexionar e investigar:
1. ¿Conocías esta característica de la cifra asimétrica exponencial y en particular de RSA?
2. ¿Qué pasaría si tienes la mala suerte de elegir como número secreto que vas a enviar a un amigo precisamente uno de los números no cifrables de su clave RSA? Si tu respuesta tiene algo de preocupación, en el Apartado 5.4 veremos que no será el caso.
3. ¿En qué circunstancias especiales crees que podría hablarse con propiedad de "mensajes" no cifrables? Ayuda: recuerda que en la Lección 3 vimos que hay diferentes formas de codificar un texto antes de cifrarlo.


APARTADO 5.2. CALCULANDO LOS NUMEROS NO CIFRABLES

A diferencia de las claves privadas y públicas parejas, cuyos valores se obtenían de forma inmediata mediante una ecuación en la que existía una separación constante entre dichas claves como vimos en la Lección 4, en este caso el cálculo de los números no cifrables NNC es más laborioso porque habrá que hacer un ataque de cifrado por fuerza bruta en el espacio de los primos p y q, para comprobar qué valores de X nos entregan las siguientes igualdades:
  Xe mod p = X     para 1 < X < p-1
  Xe mod q = X     para 1 < X < q-1

Como es de esperar, para claves reales de 1.024 o más bits, resulta computacionalmente imposible realizar esos cálculos dentro de los primos p y q de 512 bits cada uno. Por lo tanto, para estas claves reales excepto los valores 0, 1 y n-1, no será posible encontrar los demás números no cifrables.

En la siguiente diapositiva se indican las ecuaciones que intervienen en el cálculo de estos números no cifrables. Como puedes apreciar, la única dificultad de cálculo se encuentra en las dos últimas ecuaciones, que significan aplicar fuerza bruta con todos los valores de N candidatos a ser número no cifrable, siendo 1 < N < p-1 para el primo p y 1 < N < q-1 para el primo q.

Cálculo de números no cifrables NNC en RSA

Vamos a encontrar los 21 números no cifrables de la clave RSA que se muestra en los apuntes:
Sea p = 13; q = 17; n = p*q = 221; e = 7; d = inv (7, 192) = 55. Luego la cantidad de números no cifrables σn será:
σn = [1 + mcd (e-1, p-1)][1 + mcd (e-1, q-1)]
σ221 = [1 + mcd (6, 12)][1 + mcd (6, 16)] = (1+6)(1+2) = 21
Los números no cifrables serán:
NNC = [q{inv (q, p)}Np + p{inv (p, q)}Nq] mod n
NNC = [17{inv (17, 13)}Np + 13{inv (13, 17)}Nq] mod 221
  inv (17, 13) = inv (4, 13) = 10
  inv (13, 17) = 4
NNC = [{17*10}Np + {13*4}Nq] mod 221
NNC = [170*Np + 52*Nq] mod 221
Por fuerza bruta encontramos las soluciones de Np = N7 mod 13 = N    Np = {0, 1, 3, 4, 9, 10, 12}
Por fuerza bruta encontramos las soluciones de Nq = N7 mod 17 = N    Nq = {0, 1, 16}
Luego:
NNC = [170*{0, 1, 3, 4, 9, 10, 12} + 52*{0, 1, 16}] mod 221
NNC = [{0, 170, 510, 680, 1.530, 1.700, 2.040} +{0, 52, 832}] mod 221
NNC = [0+0, 0+52, 0+832, 170+0, 170+52, 170+832, ..., 2.040+832] mod 221
NNC = [0,52,832,170,222,1.002,510,562,1.342,680,732,1.512,1.530,1.582,2.362,1.700,1.752,2.531,2.040,2.092,2.872] mod 221
Reduciendo cada uno de esos veintún números módulo 221 obtenemos:
NNC = [0, 52, 169, 170, 1, 118, 68, 120, 16, 17, 69, 186, 204, 35, 152, 153, 205, 101, 51, 103, 220]
Y ordenando de menor a mayor:
NNC = [0, 1, 16, 17, 35, 51, 52, 68, 69, 101, 103, 118, 120, 152, 153, 169, 170, 186, 204, 205, 220]
Estos son los 21 mensajes de la clave RSA que se indican en la figura.

Números no cifrables en RSA del ejemplo, entregado por el sotfware genRSA

En la prácticaRSA5.2.1 vas a generar esta clave y otras más. Para claves menores de 25 bits, por razones de tiempo de cálculo, vas a generar un archivo log en html con todos esos números no cifrables tal y como aparece en la imagen superior.

De los resultados del ejercicio anterior podemos observar dos características interesantes de estos números no cifrables en RSA.

1. Que aparecen muchos números consecutivos: (0, 1); (16, 17); (51, 52); (68, 69); (152, 153); (169, 170); (204, 205).

2. Que excepto el valor 0, los valores de los extremos siempre sumarán el valor del módulo n:
    1+220 = 16+205 = 17+204 = 35+186 = 51+170 = 52+169 = 68+169 = 69+153 = 101+120 = 103+118 = 221 = n.

A pesar de este comportamiento tan peculiar, ninguna de estas características debería interpretarse como una vulnerabilidad.

Ahora como ejercicioRSA5.2.1 deberás encontrar los 49 números que se transmiten en claro para la clave RSA de 18 bits que se muestra en la siguiente figura y que has encontrado en la práctica anterior, usando solamente las ecuaciones ya presentadas y el software Fortaleza de Cifrados para operaciones y cálculos.

Clave RSA de 18 bits con 49 números no cifrables del ejercicio

Cuestiones para reflexionar e investigar:
1. Aunque el comportamiento que has visto de los números no cifrables no parece traer ninguna vulnerabilidad asociada, ¿crees que un atacante podría sacar algún beneficio de su conocimiento?
2. ¿Por qué podemos afirmar que en claves reales de 1.024 ó 2.048 bits es imposible conocer estos números no cifrables excepto tres de ellos? ¿Cuáles sí podemos conocer?


APARTADO 5.3. MINIMIZANDO LOS NUMEROS NO CIFRABLES

Siguiendo la ecuación indicada en el apartado anterior y dado que e-1 será siempre un número par, podemos concluir que la cantidad de números no cifrables será mínima cuando:
  mcd (e - 1, p - 1) = 2
  mcd (e - 1, q - 1) = 2
Entonces:
  σn = [1 + mcd (e-1, p-1)][1 + mcd (e-1, q-1)] = [1 + 2][1 + 2] = 9

Una manera sencilla de lograr con bastante probabilidad este mínimo, consiste en elegir p y q como primos seguros.

Supongamos que p = 2r + 1 y q = 2s + 1 , donde r, s, p y q son primos grandes.
Como e-1 es par, con estos primos seguros se obtendrán los siguientes valores del Máximo Común Divisor:
  mcd (e - 1, p - 1) = mcd (e - 1, (2r + 1) - 1) = mcd (e - 1, 2r) = 2 o bien 2r.
  mcd (e - 1, q - 1) = mcd (e - 1, (2s + 1) - 1) = mcd (e - 1, 2s) = 2 o bien 2s.

Por lo tanto, los cuatro valores posibles de números no cifrables para p y q primos seguros serán:
  σn = (1 + 2)(1 + 2) = 9
  σn = 3(2r + 1)
  σn = 3(2s + 1)
  σn = (2r + 1)(2s + 1) = p*q = n

Este último valor de σn = n debería llamarte la atención. Si n es el cuerpo de cifra y hay n mensajes que van en claro, quiere decir que ningún número se cifra... no sirve de nada nuestro sistema de cifra. Analizaremos este caso más adelante.

Supongamos que tenemos la clave RSA generada con los primos seguros p = 23, q = 59. El primo p 23 es igual a 2r + 1 siendo r el primo 11 y el primo q 59 es igual a 2s + 1 siendo s el primo 29. El cuerpo n = 23*59 = 1.357.

Las claves públicas e posibles no deberán tener factor en común con el cuerpo trampa Φ(n) = (p-1)(q-1) = 22*58 = 1.276.

Usando este programa de factorización online de la página Web SolveMyMath, encontramos que Φ(1.357) = 1.276 = 22*11*29.

Bien mediante propia ecuación de σn o con la ayuda del software genRSA, hacemos un barrido con las 251 primeras claves públicas e, generamos las correspondientes claves y obtenemos lo siguiente:

a) Valores de e para σ1.357 = (1 + 2)(1 + 2) = 9:
    e = 3, 5, 7, 9, 13, 15, 17, 19, 21, ... 249, 251, ...
b) Valores de e para σ1.357 = 3(2r + 1)= 3(2*11 + 1) = 69:
    e = 23, 45, 67, 89, 111, 133, 155, 177, 199, 221, 243, ...
c) Valores de e para σ1.357 = 3(2s + 1)= 3(2*29 + 1) = 177:
    e = 59, 117, 175, 233, ...
d) Valores de e para σ1.357 = n = 1.357 ... te lo dejo como ejercicio, si lo encuentras hazlo saber en las redes sociales de c4y.

Seguramente te has dado cuenta que los valores válidos de clave pública e del ejercicio anterior siguen un claro patrón. Si no es así, ¡descúbrelo! En todo caso, termina el ejercicio anterior hasta e < 500 -obviamente encontrado el patrón no tiene sentido que continúes usando genRSA- con todos los valores válidos de clave pública e. Da a conocer en las redes sociales de c4y sólo la cantidad de valores de e válidos en cada tramo a, b, c, d (no sus valores) y haz tus comentarios; hay alguna conclusión muy interesante escondida entre esos valores cuando los primos p y q son grandes. ¿Cuál puede ser?

En la prácticaRSA5.3.1 vas a comprobar la variación en la cantidad de números no cifrables σ(n) para claves RSA generadas con primos seguros, en función del valor que tome la clave pública e.

Una vez conocidas las condiciones de diseño para que una clave RSA tenga la menor cantidad posible de números no cifrables, la pregunta que nos acecha es: ¿y cuál será la cantidad mayor de estos NNC?

El peor de los escenarios será cuando:
  mcd (e - 1, p - 1) = p - 1
  mcd ( e - 1, q - 1) = q - 1
En estas condiciones σn = [1 + mcd (e - 1, p - 1)] [1 + mcd (e - 1, q - 1)] = [1 + (p -1)] [1 + (q - 1)] = p*q = n.
Así, todos los elementos del cuerpo n = p*q irán en claro. Esto nos indica que una vez elegidos p y q, hay que tener especial cuidado en la elección de la clave pública e.

Veamos un ejemplo. Supongamos que tenemos una clave RSA con p = 13, q = 17, Φ(n) = 192, n = 221 y e = 11.
Si la generamos, obtenemos una clave óptima con 9 números no cifrables en el cuerpo n = 221. Pero si hubiésemos elegido como clave pública el valor e = 49, igual de válido que 11, observamos ahora lo siguiente:
  mcd (e - 1, p - 1) = mcd (48, 12) = 12
  mcd (e - 1, q - 1) = mcd (48, 16) = 16
Por lo tanto σ221 = [1 + 12][1 + 16] = 13*17 = 221 = n, como se observa en la figura.

Clave RSA todo el cuerpo no cifrable

¿Por qué ha pasado esto? En el ejemplo anterior, observamos que e = 49 = 192/4 +1 = Φ(n)/4 + 1. En general, si elegimos un valor de clave pública e = Φ(n)/k + 1 para valores de k igual a 2, 3, 4, ... siempre pequeños, la cantidad de NNC puede ser muy alto, incluso todo el cuerpo como acaba de suceder para e = 49 y que se va a repetir en esta clave RSA para e = 97.

Si σ(n) = n, como todo el cuerpo de cifra irá en claro, entonces el valor de la clave pública se repetirá en la clave privada o en una clave privada pareja.

Si llega a cumplirse que e = Φ(n)/2 + 1, entonces σ(n) = n y será no cifrable cualquier valor de n. Es más, en este caso observarás que la clave privada tendrá el mismo valor que la clave pública.

La prácticaRSA5.3.2 te permitirá comprobar lo que se indica en el párrafo anterior en cuanto a clave pública igual a clave privada.

Cuestiones para reflexionar e investigar:
1. ¿Crees que puede ser una vulnerabilidad el hecho de que una clave RSA tenga demasiados mensajes no cifrables?
2. ¿Crees que esto puede ser una amenaza en claves reales?


APARTADO 5.4. ¿HAY QUE PREOCUPARSE POR ESTOS NUMEROS NO CIFRABLES?

En el apartado anterior hemos visto que hay que tener cuidado en la elección del valor de la clave pública e, puesto que una mala elección de ésta podría llevarnos a una clave RSA en la que todos los valores a cifrar irían en claro.

Para ello había que prestar especial atención a que el valor de la clave pública e no coincidiese nunca con Φ(n)/k + 1 para k = 2, es decir e = Φ(n)/2 + 1, y con menos exigencias para k igual a 3, 4, 5, ... en general para valores de k bajos.

Pero como ya hemos visto en la lección 2, en la práctica la clave pública e no la elige el usuario sino que se fuerza a que sea el número 4 de Fermat, es decir 65.537 de solamente 17 bits.

En estas condiciones, puesto que n y Φ(n) serán números de mínimo 1.024 bits, entonces en el supuesto caso de que se cumpliese la relación e = Φ(n)/k + 1 el valor de k sería tan grande que la cantidad de números no cifrables nunca llegará a estos extremos.

Después de haber generado muchas centenas de claves RSA en diversos cursos y prácficas con librerías antiguas como Crypto++ del año 2004 que se usa en el software genRSA, la clave estándar de 1.024 bits y e igual a F4 con mayor cantidad de números no cifrables que he obtenido ha mostrado σ(n) = 33.825, como se muestra en la siguiente figura.

Nota: con librerías actuales como las que usa OpenSSL en 2012, ya no se obtienen claves tan singulares como ésta; lo veremos en una próxima lección. Recuerda que genRSA usa la librería Crypto++ del año 2004 y por eso se generan claves tan "extrañas".
Si con genRSA encuentras claves de 1.024 ó 2.048 bits con e = 10001 en hexadecimal y con más de 35.000 NNC, envía ese aporte a las redes sociales de c4y.

Clave RSA de 1.024 bits y 33.825 NNC

Genera con genRSA esta clave para comprobar lo anterior:
p = 1CC0C6A8909BE5B660807C6156F93DDDE67D4F08877AFD4C0752B0C721A31AA951CCB5DEE7AD6CEE5BAE9721E0022DE63B2D3575D6C37EB410739057D845E24C7C01
q = 06F90C2DB8C3537D9ED1226721C4175DFC37F077FC95FF1211DBD9BEA59F4F572C529F71FDC2EBF960E2E91AE8CEDD5E030AC416CF0AD2FB2FF81F151FB1E1
e = 010001

En el ejemplo anterior hemos generado una clave RSA de un tamaño real y estándar que muestra casi 35.000 números no cifrables. A primera vista esto podría ser un motivo de preocupación, pero vas a comprobar a continuación que en absoluto podría asociarse a esta clave vulnerabilidad alguna y es tan segura como cualquier otra clave de 1.024 bits que presente tan sólo 9 números no cifrables.

Vas a generar esta clave en la prácticaRSA5.4.1 y dos más de tipo estándar con 1.024 y 2.048 bits que entregan muchos números no cifrables.

Para entender que la clave anterior y las que has generado en la práctica no pueden considerarse claves débiles, debemos recordar qué es lo que se cifra con RSA y, en general, con cualquier algoritmo asimétrico. Como se comentó en la Lección 1, con estos sistemas asimétricos se cifrarán solamente números y, puesto que la velocidad de cifra es unas mil veces más baja que en algoritmos simétricos, dichos números serán sólo de unas centenas de bits, nunca miles de bytes.

El caso que más nos preocupa aquí es que un número secreto que cifremos con RSA para un intercambio de clave, al final vaya en claro. Pero los números que cifraremos en la práctica pueden ser de estos dos tipos:

1. Una clave de sesión para su uso en un algoritmo simétrico y que estará entre los 128 bits (RC4, AES, ...) y los 256 bits (AES), en lo que se conoce como intercambio de clave con RSA usando la clave pública del receptor.

2. Un número resultado de aplicar a un documento una función hash MD5 (128 bits, no recomendable) o SHA-1 (160 bits), en lo que se conoce como firma digital RSA usando la clave privada del emisor.

En ambos casos son números de tan sólo unas centenas de bits dentro de un cuerpo de cifra que actualmente es de 1.024 ó 2.048 bits. Por lo tanto, la posibilidad de que dentro de un cuerpo n de 1.024 bits un conjunto de números secretos caiga precisamente en la zona de centenas de bits, es decir, sea un número con una gran cantidad de ceros a la izquierda y sólo cien o doscientos bits significativos, es extremadamente pequeña.

Pero, así y todo, si aceptamos que hay varios números de ese conjunto no cifrable de la clave RSA que tienen sólo una o dos centenas de bits significativos, la probabilidad ahora de que alguno de ellos sean precisamente el número secreto que hemos elegido para ese intercambio de clave es de uno entre 2128 para una clave de 128 bits, una probabilidad ínfima.

Como conclusión, vemos que para valores de diseño estándar de una clave RSA por sobre los mil bits y por el hecho de que no se deja al usuario la elección aleatoria de una clave pública e, sino que esta viene forzada por F4, tampoco será un motivo de preocupación la existencia de una gran cantidad de números no cifrables.

Cuestiones para reflexionar e investigar:
1. Encuentra cuál es la probabilidad de que dentro de un cuerpo de 1.024 bits nos encontremos con un número de sólo 100 ó 200 bits significativos. A continuación, encuentra la probabilidad de adivinar un número en particular dentro de un cuerpo de 128 bits.
2. ¿Crees que puedes hacer un dibujo que permita apreciar gráficamente las probabilidades que hemos estudiado en este apartado?
3. ¿Podrías presentar con un ejemplo de la vida real qué significarían esas probabilidades tan pequeñas encontradas en este apartado para hacer un símil y explicarle a alguien sin conocimientos de matemáticas de qué estamos hablando? Por ejemplo, la probabilidad de ganar varias veces seguidas el premio mayor de la lotería una misma persona. Comenta estas cuestiones en las redes sociales de c4y.


APARTADO 5.5. TEST DE EVALUACION DE LA LECCION RSA05

En las siguientes 5 preguntas, elige la respuesta correcta.

1. Un número no cifrable significa:

a) Que no funciona correctamente el algoritmo RSA
b) Que el texto se transmite en claro
c) Que no se puede descifrar el criptograma

2. Una clave RSA tendrá

a) Como mínimo 1 número no cifrable
b) Como máximo 9 números no cifrables
c) Como mínimo 9 números no cifrables

3. En alguno de estos casos la cantidad de números no cifrables será el máximo:

a) Cuando e = Φ(n)/ 2 + 1
b) Cuando e = Φ(n)/ 2 + 1.024
c) Cuando e = Φ(n/2) + 1

4. Generamos una clave RSA de 1.024 bits y encontramos que tiene 45 números no cifrables:

a) Podemos generar el log para saber cuáles son esos números pero tardará algunas horas
b) No podremos saber nunca ninguno de esos valores
c) Sólo podremos saber tres de esos 45 valores

5. Vamos a intercambiar una clave de sesión AES de 256 bits mediante clave RSA que sabemos tiene 587 NNC:

a) No lo haríamos nunca porque hay una probabilidad alta de que esa clave vaya en claro
b) Lo haríamos sin preocuparnos porque la probabilidad de que esa clave vaya en claro es extremadamente pequeña
c) Lo haríamos con cierta preocupación porque existe una probabilidad real de que esa clave vaya en claro


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