MOOC El algoritmo RSA

Lección 2. Valores de diseño de las claves
Dr. Jorge Ramió Aguirre - 30/03/2012 

Twittear

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 descargar las diapositivas del curso en formato pptx animado o bien en pdf, puedes hacerlo desde esta dirección.

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

• Apartado 2.1. Necesidad de un cuerpo de cifra mayor que 2.000 bits
• Apartado 2.2. Relación tamaño clave pública versus clave privada
• Apartado 2.3. ¿Por qué se usa el número 4 de Fermat como clave pública e?
• Apartado 2.4. ¿Qué pasaría si usamos cualquier valor válido de e?
• Apartado 2.5. Aspectos a tener en cuenta en la elección de los primos p y q
• Apartado 2.6. Test de evaluación de la Lección 2

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

• 1. genRSA
• 2. Fortaleza de Cifrados
• 3. Calculadora científica online

---

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)

---

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 2^1.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.

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.

---

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 F₄, 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 F₄ tiene un conjunto de características interesantes:

   1. 65.537 es un número primo.

   2. 65.537 = 2^{2^4} + 1 = 2¹⁶ + 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á K^e_R mod n_R 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 d_R, obteniéndose por tanto confidencialidad en dicha transmisión.

Si el exponente de dicha ecuación, en este caso e_R, tiene muchos ceros como es el caso de F₄ 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.

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 F₄ = 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.

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 F₄ 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.

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.

---

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 F₄, 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.

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.

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

---

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 = p² = q², 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.

¿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?

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 (2⁵¹² = 1,3x10¹⁵⁴) 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 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 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.

---

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?

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:

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

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

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

---

Ir a: [Portada c4y]    [Lección 1] [Índice] [Lección 3]

---