MOOC El algoritmo RSA


Lección 2. Valores de diseño de las claves

Dr. Jorge Ramió Aguirre - 30/03/2012 

En esta segunda lección veremos los valores característicos y recomendables de los parámetros que intervienen en la generación de una clave RSA, a lo que dedicaremos 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 RSA02] 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. Familiarizarse con los valores estándar del cuerpo de cifra, las claves públicas y las claves privadas.
  • 2. Analizar el peligro que puede entrañar un diseño libre por parte del usuario en cuanto al tamaño elegido para la clave pública e.
  • 3. Conocer las particularidades que tiene F4, el número 4 de Fermat, y la razón de su elección como valor estándar de clave pública e.
  • 4. Adelantar otras características que influyen en la calidad de las claves en función de una elección adecuada de los parámetros.

Software que vas a utilizar en esta lección


APARTADO 2.1. NECESIDAD DE UN CUERPO DE CIFRA MAYOR QUE 2.000 BITS

Debido al avance que se viene experimentando desde finales de los años 2000 en cuanto a los tiempos de cómputo necesarios para factorizar números RSA, en 2012 es recomendable trabajar ya con módulos superiores a 2.000 bits.

Si no recuerdas la importancia de trabajar con números grandes en RSA, repasa el Apartado 1.2 de la Lección RSA01 La seguridad del algoritmo RSA: Los principios del algoritmo RSA.

De hecho, si accedes al enlace seguro de un banco online, lo más probable es que te encuentres con un certificado digital X.509 que muestre una clave pública RSA cuyo módulo es de 2.048 bits, como se aprecia en la figura.

 

Certificado digital de Citibank USA (fecha de acceso 29/12/2011)

En el ejercicioRSA2.1.1 vas a abrir un certificado digital X.509 y ver sus características.

Cuestiones para reflexionar e investigar:
1. Como has podido observar, el certificado del citibank tiene una validez de dos años. ¿Te parecería bien aceptar una oferta comercial de un certificado de iguales características, más barato pero con una duración de 8 años?


APARTADO 2.2. RELACION TAMAÑO CLAVE PUBLICA VERSUS CLAVE PRIVADA

Seguramente después de generar de forma automática varias claves reales, por ejemplo de 1.204 ó 2.048 bits, con el programa genRSA en la Lección 01, te has preguntado porqué la clave pública que propone el programa está entre 10 y 15 bits y, en cambio, la clave privada que se calcula tiene siempre un valor muy cercano al tamaño del módulo n como muestra la figura.

Clave RSA de 1.204 bits generada con genRSA

Los motivos para usar un valor de clave pública e relativamente pequeño comparado con el módulo n sigue, el siguiente razonamiento:

1. La trampa Φ(n) será igual a (p - 1)(q - 1) y como p y q son primos de al menos 512 bits, el tamaño de Φ(n) será entonces aproximadamente igual al de n, es decir con igual número de bits.

2. Como la clave pública e y la clave privada d son inversas en el cuerpo Φ(n), es decir d = inv [e, Φ(n)], entonces se cumple la siguiente relación: e x d mod Φ(n) = 1.

3. Para que se cumpla esa igualdad, el producto de e x d debe salir del cuerpo Φ(n) al menos una vez para que la operación en ese módulo nos devuelva el valor 1.

4. Es decir, se cumplirá que e x d = k x Φ(n) + 1, con k = 1, 2, 3, 4, ...

5. Para que ese producto salga al menos una vez del cuerpo Φ(n), es decir con k = 1, dado que la clave pública e tiene por ejemplo 14 bits, el valor de la clave privada d debería ser como mínimo mayor a 1.010 bits, para el caso hipotético (y con probabilidad casi nula) que se cumpla la ecuación para k = 1.

6. En la práctica ese valor de k = 1 o un valor bajo de k será muy poco probable y, por tanto, podemos esperar una clave privada d muy cercana o igual en bits al valor de n como así sucede en la práctica.

7. Esto significa que será computacionalmente difícil adivinar el valor de la clave privada d, puesto que encontrar un número dentro de un cuerpo de 1.024 bits significa un tiempo de cómputo totalmente inabordable, en media 21.023 intentos.

8. Luego, forzar que la clave pública e sea un valor pequeño, menor de 20 bits dentro de un cuerpo de 1.024 bits o mayor, asegura que la clave privada d sea un valor muy grande y, por tanto, muy segura pues es imposible encontrarla por fuerza bruta.

9. Como veremos en el próximo apartado, en la práctica se usa un valor único de clave pública e de 17 bits, igual para todo el mundo.

En la prácticaRSA2.2.1 vas a generar 4 claves RSA de tamaños reales donde podrás comprobar lo visto en este apartado.

La clave pública 010001 representada con seis caracteres hexadecimales, es decir con 24 bits, y que has visto en la práctica anterior, es un valor característico y típico: el número 4 de Fermat que veremos en el siguiente apartado.

Las claves tercera y cuarta de la práctica, así como la que puedes ver en la figura de este apartado, son claves que en próximas lecciones calificaremos como claves RSA óptimas en cuanto muestran sólo 9 mensajes o números no cifrables y una única clave privada pareja, aspectos que serán analizados en las lecciones 5 y 6.

Cuestiones para reflexionar e investigar:
1. Como la única condición que debe cumplir e para que sea una clave pública válida es que mcd [e, Φ(n)] = 1 y es deseable que sea además un valor pequeño, ¿por qué no usar e = 3?
2. Después de analizar esta situación, consulta en esta direccion del sitio Web RSA Algorithm, página entregada como referencia al comienzo de este curso, y también en esta otra dirección de los mismos autores.
3. Viendo la relación que existe en tamaño de bits entre la clave pública e y la clave privada d, para claves RSA prácticas y reales, y que se resume en la ecuación del punto 4 del razonamiento explicado más arriba, ¿qué crees que sucedería si intercambiamos las magnitudes y permitimos que la clave pública e sea un valor muy cercano a Φ(n)?
4. ¿Por qué crees que se ha asegurado que con una clave pública de 17 bits dentro de un cuerpo de 1.000 bits o mayor resulta imposible un ataque a la clave privada por fuerza bruta? ¿Cómo harías ese hipotético ataque?


APARTADO 2.3. ¿POR QUE SE USA EL NUMERO 4 DE FERMAT COMO CLAVE PUBLICA e?

Aunque la única condición que debe cumplir la clave pública e para que pueda existir la clave privada inversa d es que exista el inverso de e en Φ(n), es decir d = inv [e, Φ(n)], y por tanto es necesario que mcd [e, Φ(n)] = 1, dado que 1 < e < Φ(n) entonces podríamos elegir cualquier número dentro de este rango que cumpla con esa condición de primalidad.

No obstante, en el apartado anterior ya hemos visto que es recomendable usar un valor pequeño como clave pública. De hecho, valores típicos suelen ser los números 3, 17 y 65.537 puesto que, además, tienen sólo dos bits iguales a 1 en su representación binaria, que como veremos en este apartado tendrá importancia en la eficiencia del cómputo.

Descartando el número 3 por lo que has visto en las cuestiones abiertas del apartado anterior, la representación binaria de los números 17 y 65.537 será:

      17 = 10001.
      65.537 = 10000000000000001.

El número 65.537, número 4 de Fermat o F4, es la clave pública e por defecto de todas las claves RSA comerciales y que podemos ver en certificados digitales; lo que será distinto y propio en cada clave son los primos p y q, y por lo tanto el módulo n.

Es que el número F4 tiene un conjunto de características interesantes:

   1. 65.537 es un número primo.

   2. 65.537 = 22^4 + 1 = 216 + 1.

   3. 65.537 es un número de 17 bits, relativamente pequeño.

   4. 65.537 = 10000000000000001 en binario.

   5. Esta propiedad de tener muchos ceros permitirá una operación de cifra mucho más rápida.

   6. 65.537 = 010001 en hexadecimal, representado por 24 bits.

La operación de cifra con RSA usada para el intercambio de claves en una sesión TLS/SSL, por ejemplo, será KeR mod nR de forma que se envía el valor de una clave secreta K al receptor y sólo éste podrá descifrar el criptograma usando su clave privada dR, obteniéndose por tanto confidencialidad en dicha transmisión.

Si el exponente de dicha ecuación, en este caso eR, tiene muchos ceros como es el caso de F4 entonces la operación se realiza de forma muy rápida. Recuerda que los sistemas de cifra asimétrica o de clave pública son muy lentos comparados con los sistemas de cifra simétrica o de clave secreta y, por tanto, es muy importante optimizar esa tasa de cifra.

Para comprender mejor lo indicado en el párrafo anterior, mira y resuelve el ejercicioRSA2.3.1 en el que puede apreciarse cómo funciona el algoritmo de exponenciación rápida.

La siguiente figura muestra el algoritmo de exponenciación rápida que encontrarás también explicado en esta dirección.

Algoritmo de exponenciación rápida

Como se aprecia en la diapositiva anterior, además de la operación elevar al cuadrado, sólo se multiplica por la base cuando se tiene un bit uno en el exponente. Por tanto, para el exponente F4 = 10000000000000001 en el primer paso del algoritmo no se hace operación alguna, porque el resultado es la misma base A con la que se inicia el cálculo, luego tendríamos 15 operaciones de elevar al cuadrado, que requieren poco tiempo de máquina, y sólo una multiplicación al final.

Esto optimiza el tiempo de cálculo, si bien esta operación de exponenciación a un número relativamente pequeño es bastante rápida como podrás comprobar en la siguiente prácticaRSA2.3.1.

Una de las operaciones que has realizado en la práctica anterior es la que se muestra en la siguiente figura. A la luz de los valores que ves en la captura de pantalla, justifica porqué se ha puesto como pie de figura esa frase.

Simulación de un intercambio de clave real con software Fortaleza de Cifrados

Como conclusión final, el número F4 es apropiado como clave pública universal porque tiene muchos ceros y es un valor relativamente pequeño comparado con el módulo n, que será siempre superior a 1.024 bits. Esto trae consigo las siguiente consecuencias:

1. Forzar a que la clave privada d tenga un tamaño similar al módulo n y, por tanto, sea segura ante un ataque por fuerza bruta.

2. Acelerar la operación de exponenciación para el intercambio de clave por tener sólo dos valores binarios en 1 y los demás en 0.

3. Evitar ataques que podrían producirse si e es un número demasiado pequeño, caso del primo 3, como ya lo has comprobado.

En la prácticaRSA2.3.2 vas a abrir certificados digitales X.509 con diferentes navegadores para ver cómo se muestra la clave pública e.

También se puede llegar a la siguiente conclusión interesante para una clave de un servidor de 1.204 bits, aunque quizás no sea parte de las condiciones de diseño.

1. La operación que debe hacer el cliente para enviar la clave de sesión simétrica por ejemplo de 128 bits a un servidor, una vez conocida su clave pública mediante un certificado digital, es muy rápida. La operación será (128 bits)(17 bits) mod (1.024 bits) y dicho exponente de 17 bits con 15 bits en cero.

2. Por el contrario, la operación de descifrado que deberá realizar el servidor una vez recibido el criptograma será muy pesada pues se asemejará a lo siguiente: (1.204 bits)(1.204 bits) mod (1.204 bits), pero para ello ya usaremos más adelante el teorema chino del resto.

Cuestiones para reflexionar e investigar:
1. Si realizas un ejercicio de comenzar una compra online en unos grandes almacenes como por ejemplo El Corte Inglés en España, observa que sólo se fuerza cambiar a una plataforma segura TLS/SSL cuando vas a pagar con la tarjeta.
2. ¿Por qué no existe anonimato durante la compra y sólo se fuerza una pasarela segura cuando se trata de pagar? ¿Estás de acuerdo con esa falta de anonimato al realizar la compra? Presenta algún ejemplo en que esa falta de seguridad durante la acción de comprar, poner productos en el carro de la compra, pueda afectar a tu intimidad.


APARTADO 2.4. ¿QUE PASARIA SI USAMOS CUALQUIER VALOR VALIDO DE e?

Como hemos visto en el apartado anterior, el valor universal para la clave pública de e es F4, pero en el algoritmo RSA se podría usar en principio cualquier valor de e que estuviese comprendido entre 3 y Φ(n) - 2.

Si una clave pública e válida, es decir que tiene su inverso en Φ(n), fuese un valor muy alto y cercano al cuerpo de cifra n, se podría obtener una clave privada extremadamente pequeña cuyo ataque por fuerza bruta sería trivial.

En la prácticaRSA2.4.1 generarás claves de estas características y podrás llegar a una primera conclusión.

Una de las claves generadas en la práctica anterior es la que se muestra en la figura. ¿Ves algo extraño en ella?

Clave privada insegura al permitir elegir un valor de clave pública del orden del módulo

Lo anterior nos comprueba que no debe dejarse que el usuario genere la clave pública e de forma aleatoria dentro del rango permitido, pues la clave privada d podría ser un número muy pequeño y por tanto fácil de romper mediante un simple ataque por fuerza bruta.

Hay otra razón por la que no se debe dejar al usuario la generación del número e de forma aleatoria dentro del rango permitido y tiene que ver con la cantidad de números o mensajes no cifrables. Aunque este tema lo veremos en la Lección 6, en la prácticaRSA2.4.2 podrás tener una primera idea de lo que podría suceder.

Como has podido comprobar en la práctica anterior, por ejemplo para una clave RSA cuyo valor n = 10.644.059, al elegir mal el valor de la clave pública e todos los mensajes, desde el valor 0 hasta el valor 10.644.058, irán en claro, por lo que no existe cifra alguna.

En la figura se muestra este efecto no deseado por la mala elección de la clave pública. Profundizaremos en ello en la Lección 6.

Clave RSA con todas sus cifras en claro por una mala elección de la clave pública e

Cuestiones para reflexionar e investigar:
1. Si se demostrase en el futuro que el valor de F4 ha dejado de ser suficientemente pequeño, ¿se te ocurre algún otro valor para una clave pública e que cumpliese con lo estudiado en esta lección?


APARTADO 2.5. ASPECTOS A TENER EN CUENTA EN LA ELECCION DE LOS PRIMOS p Y q

Los primos p y q deben ser ambos números grandes. Eso resulta obvio una vez hemos comprobado en la lección anterior el problema de la factorización entera. Pero, ¿por qué no pueden ser los primos p y q iguales? ¿Algo lo prohíbe?

Primero que nada, si p = q y n = p x q, entonces n = p2 = q2, y encontraríamos rápidamente sus valores simplemente calculando la raíz cuadrada de n. Esta tarea tiene para n bits una complejidad algorítmica equivalente a la multiplicación de dos números de igual cantidad de bits, por lo cual no debería jamás usarse.

El siguiente ejercicioRSA2.5.1 te demostrará lo anterior. Harás el cálculo online de la raíz cuadrada de un número de 768 bits, que corresponde al cuadrado del valor del primo p de 116 dígitos (384 bits) del último desafío RSA 768 resuelto en el año 2009, en un tiempo de ejecución inmediato.

¿Qué sucedería ahora si el segundo número a multiplicar fuese el valor q de esa clave RSA 768? Podemos repetir el ejercicio anterior, obtener el producto y nuevamente la raíz cuadrada. Pero, ¿nos serviría de algo?

Ocurre otro fenómeno interesante cuando ambos primos son iguales. En la prácticaRSA2.5.1 comprobarás qué sucede con la clave generada si hacemos p y q iguales.

La figura muestra una de las claves generadas en la práctica anterior. Observa qué sucede con la cantidad de claves privadas parejas. Este tema de las claves privadas y públicas parejas lo abordaremos en la Lección 4.

Clave decimal de 14 bits con valores con p y q = 101

Se observa que si p y q son iguales, además de la grave debilidad de poder encontrar fácilmente la raíz cuadrada de n y con ello el valor del primo que se ha elevado al cuadrado, se obtiene un número p de claves privadas parejas. Si el valor de p es de 512 bits, tendríamos un valor altísimo (2512 = 1,3x10154) de claves privadas parejas, lo que no es recomendable. Se concluye, por tanto, que los primos p y q deben elegirse como números grandes y distintos.

Así mismo, se recomienda que ambos primos estén separados algunos bits, aunque luego esto en la práctica no se tome en cuenta, incluso en software estándar como OpenSSL.

Primos seguros

Además de las características que deberían cumplir los primos p y q, como también la clave pública e en el diseño de una clave RSA, en siguientes lecciones veremos que será recomendable usar primos seguros para generar claves RSA que llamaremos óptimas.

Un primo q se dice que es seguro si, además de ser primo, es el resultado de multiplicar por dos un primo p menor y sumarle uno. Por ejemplo el número 23 es primo seguro porque 23 = 2 x 11 + 1, siendo 11 y 23 primos.

Para una mayor profundización en este tema, puede consultar en la siguiente Tesis Doctoral del Dr. Raúl Durán. También puede consultar en la red por primos fuertes, una Lista de primos, o bien una visita a esta página de Prime Numbers, muy recomendable.

No obstante, para esta lección y para el objetivo y alcance de este curso, será suficiente trabajar con primos seguros.

Al usar primos seguros, en la inmensa mayoría de casos se obtendrán claves RSA con una sola clave privada pareja y nueve números no cifrables, que denominaremos claves RSA óptimas.

En la prácticaRSA2.5.2 vas a generar claves óptimas eligiendo los primos p y q como primos seguros.

En muy pocos casos esto no se cumple. Por ejemplo, si en la prácticaRSA2.5.2 en que p = 23, q = 83, e = 31, cambias la clave pública por e = 19, ya no obtendrás una clave óptima al aparecer 2 claves privadas parejas. Sí se asegura, no obstante, que se tendrá un número muy cercano a la unidad de claves privadas parejas.

El la prácticaRSA2.5.3 comprobarás que si en vez de primos seguros usas primos fuertes, no se logra este tipo de claves óptimas.

El uso de primos seguros y/o primos fuertes en la actualidad no afecta a la calidad de la clave RSA debido a los nuevos algoritmos de factorización, si bien existe alguna discrepancia pues el mayor tiempo de búsqueda de tales primos no compensa los posibles beneficios.

En próximas lecciones nos centraremos en dos aspectos interesantes de las claves RSA, las claves privadas parejas, las claves públicas parejas y los mensajes o números no cifrables, en donde los primos seguros jugarán un papel importante.

Cuestiones para reflexionar e investigar:
1. Analiza qué sucedería si elegimos primos p y q muy cercanos y, en el peor de los casos, primos gemelos.
2. ¿Sería la clave anterior insegura? Ayuda: busca en Google, Yahoo! o Bing el método de factorización de Fermat.


APARTADO 2.6. TEST DE EVALUACION DE LA LECCION RSA02

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. ¿Cuál de estas claves crees que es más segura y mejor?

a) p = 512 bits; q = 512 bits; e = 17 bits; d = 1.023 bits
b) p = 1.024 bits; q = 1.024 bits; e = 17 bits; d = 2.046 bits
c) p = 1.024 bits; q = 1.024 bits; e = 3 bits; d = 2.048 bits

2. Si p y q tienen 1.024 bits y la clave pública es de 10 bits, cabe esperar que la clave privada sea de:

a) 1.034 bits
b) 1.024 bits
c) 2.048 bits

3. El número 4 de Fermat F4 es el valor e estándar porque:

a) Es un número primo
b) Favorece una clave privada grande y optimiza la cifra en el intercambio de clave
c) Favorece una clave privada grande y acelera la operación de firma digital de un documento

4. Si no prestamos atención al valor de la clave pública e respecto a Φ(n) podría ocurrir que:

a) Fuese imposible cifrar ningún valor
b) Fuese posible cifrar sólo números primos
c) La cifra fuese no determinista

5. Si elegimos p y q de igual valor y de 1.024 bits cada uno:

a) Todos los mensajes irían en claro
b) La clave es segura al tener un módulo de 2.048 bits
c) Se puede romper la clave privada de una manera trival e inmediata


APARTADO 2.7. DATOS ESTADISTICOS DE ESTA LECCION

En este apartado se irán incluyendo las estadísticas de seguimiento de esta lección.

Accesos a la lección RSA02 desde el 30 de marzo de 2012 hasta el 31 de julio de 2012: 3.627.

Accesos al proyecto Crypt4you desde el 15 de marzo de 2012 hasta el 31 de julio de 2012: 68.402.

Puedes ver las estadísticas detalladas de accesos a Crypt4you generadas por AWStats.


APARTADO 2.8. ENCUESTA

Si no lo has hecho, por favor contesta a la encuesta sobre este MOOC que encontrarás en la siguiente dirección.

[Portada c4y]    [Lección 1] [Índice] [Lección 3]