18 oct 2019

Generación de claves RSA y selección de los números primos. Parte 2


La idea general empleada por las implementaciones reales se basa en que verificar si un número es primo con una muy alta probabilidad es mucho más rápido que factorizar dicho número, y dado que la existencia de números primos no es infrecuente cuando los números son grandes, es decir, es fácil encontrar números primos incrementando el número candidato y probando de nuevo, los tests de primalidad son muy eficientes (sin entrar en los detalles de cómo funcionan estos tests internamente, por ejemplo, verificando si un número es compuesto mediante el teorema de Fermat12, junto a otras comprobaciones adicionales). A modo de referencia, y sin entrar en sus detalles, existen otros tests de primalidad adicionalmente al de Miller–Rabin, como Lucas (mencionado posteriormente en FIPS 186-4), Baillie-PSW, o Solovay-Strassen.

Adicionalmente, otras implementaciones basadas en el estándar FIPS 186-4 [4] (analizado posteriormente), concretamente en el apartado B.3.1 (centrado en la generación del par de claves empleadas por RSA; requisito 2(d)), una vez generados los números p y q, comprueban que la diferencia entre ambos números primos sea mayor a m bits, siendo m igual a 2 elevado a la mitad de la longitud del módulo n ("nlen") menos 100 (|p-q|>2(nlen/2)-100), para que no se trate de números primos "muy" cercanos, lo que facilitaría factorizar el módulo n13 [13]. Por otro lado, los números primos p y q empleados no pueden ser iguales, ya que si p=q sería trivial factorizar n calculando la raíz cuadrada de n (n=p*q=p2=q2), lo que permitiría conocer p y q, y por tanto poder calcular Φ(n) = (p-1)(q-1), y como resultado obtener la clave privada d = inv(e,Φ(n)).

La documentación oficial de la certificación CriptoCert Certified Crypto Analyst (https://www.criptocert.com/#cert-analyst) profundiza en otros aspectos del algoritmo RSA, incluyendo la existencia de Claves Privadas Parejas (CPP) y Claves Públicas Parejas y sus cálculos asociados, los números o mensajes no cifrables, el Teorema Chino del Resto (TCR), etc. En relación con las preguntas que nos ocupan, es interesante conocer que si ambos números primos p y q son seguros, sólo existirá una Clave Privada Pareja (el valor mínimo posible y más recomendable desde un punto de vista criptográfico).

Un breve artículo introductorio centrado en la elección de los números primos utilizados en la criptografía de clave pública es "Prime Numbers in Public Key Cryptography" [5], de Gerald Crow, publicado en 2003 en la SANS Reading Room, que describe ciertas propiedades asociadas a los números primos, ciertos tipos de números primos como los de Mersenne (2n-1) o el concepto de números primos relativos o coprimos1 (o números primos entre sí), y algunos teoremas relacionados, como el pequeño teorema de Fermat, que permite excluir si un número es o no primo, o el teorema de Euler.

La tesis "The properties of RSA key generation process in software libraries" de Matúš Nemec (Masaryk University - Faculty of Informatics) [1], publicada en 201614, realiza un análisis muy completo y exhaustivo de las diferentes aproximaciones y algoritmos empleados por las implementaciones de múltiples librerías criptográficas a la hora de generar las claves del algoritmo RSA (comparándolas con los requisitos definidos por estándares internacionales, como NIST FIPS 186-4, detallado posteriormente, ANSI X9.31 y X9.44, IEEE 1363-2000, RSAES-OAEP y otros), la selección de los números primos p y q asociados, y los tests de primalidad empleados para su verificación. La tesis profundiza en las peculiaridades de las distintas implementaciones analizadas, comparándolas entre sí, y en algunas optimizaciones existentes que intentan, por ejemplo, minimizar el número de invocaciones al generador de números (pseudo)aleatorios. Adicionalmente, describe trabajos previos, potenciales ataques sobre las claves RSA, algoritmos y métodos de factorización, e identifica propiedades comunes a claves débiles. Como conclusión, algunas implementaciones aumentan su eficiencia en el proceso de generación de las claves sacrificando unos pocos bits de entropía, pero sin un impacto significativo en la seguridad de las claves generadas.

En el caso de OpenSSL, la tesis indica (en el apartado 4.2) lo comentado anteriormente tras realizar un breve análisis de su código fuente, es decir, que hace uso de una búsqueda incremental basada en la división del número candidato por algunos números primos pequeños (ya que llegar hasta la raíz cuadrada del número candidato no es práctico, por la cantidad de cálculos requeridos), teniendo en cuenta que los cálculos de división se realizan tanto para p como para p/2 (para emplear primos seguros). Sin embargo, los tests de primalidad no se realizan sobre p/2, lo que parece un bug, hecho que permite identificar claves RSA generadas por OpenSSL (v1.0.2g). La tesis también detalla el uso de OpenSSL con el módulo de compatibilidad FIPS.

Dentro de los estándares internacionales de referencia más relevantes para la generación de claves RSA, con carácter público y oficial, se encuentra la publicación del NIST conocida como FIPS 186-4, "Digital Signature Standard (DSS)", de julio de 2013 [4], y asociada a la firma digital (la certificación CriptoCert Certified Crypto Analyst cubre esta temática en el módulo 9, tal como se puede consultar en su temario: https://www.criptocert.com/CriptoCert_Analyst.html). En concreto, la sección 5.1 de FIPS 186-4, y especialmente el apéndice B.3.1, detallan los requisitos formales y más restrictivos (en comparación a otras implementaciones) para la generación del par de claves RSA y de la selección de los números primos p y q, y las relaciones entre estos, en base a FIPS 186-4 (referenciadas como IFC, Integer Factorization Cryptography). En resumen, se debe hacer uso de un generador de números aleatorios, o bits, de confianza, y los números primos p y q de 1.024 bits deben ser primos provables o probables  (en inglés), o satisfacer un conjunto de condiciones (primos con condiciones), asociadas a factores primos denominados primos auxiliares, que deben cumplir también unos requisitos de longitud mínima (> 140 bits) y máxima (su sumatorio debe ser, según si son provables, <494 bits, o probables, <1.007 bits). El estándar también define los requisitos del exponente público e y del exponente privado d, y su relación respecto a los valores de p y q. La generación de números primos provables y probables, y de primos de ambos tipos con condiciones, se describe en los apéndices B.3.2, B.3.3, B.3.4, B.3.5 y B.3.6 respectivamente (en base a los requisitos de A.1 y A.2), empleando una semilla aleatoria o tests de primalidad probabilísticos (según el apéndice C.3). Los tests de primalidad probabilísticos referenciados en FIPS 184-6 son Miller-Rabin (C.3.1), una versión mejorada de éste (C.3.2), y Lucas (C.3.3), sugiriéndose la utilización de un número mínimo de iteraciones de Miller-Rabin (según la longitud en bits de p y q y la probabilidad de error que se considera aceptable), o para más certeza (por ejemplo en DSA frente a RSA), su uso combinado, aplicando un test de Lucas adicional. El motivo es que no se conocen valores de números no primos que satisfagan el número de iteraciones del test Miller-Rabin indicadas, y también satisfagan el test de Lucas. En el caso de RSA, y como referencia, el número de iteraciones del test Miller-Rabin es de 5 siendo p y q números primos de 1.024 bits (con una probabilidad de error de 2-112).

Los dos números primos p y q son habitualmente generados aleatoriamente con una longitud de 1.024 bits y posteriormente se comprueba su primalidad (tal y como se ha descrito anteriormente). Algunas implementaciones, incluyendo OpenSSL, generan un número aleatorio de 1.024 bits, asegurándose de que es un número impar (es decir, su bit menos significativo debe ser 1) y, por tanto, potencialmente primo. Adicionalmente se aseguran de que su bit más significativo también es 1 (el número comienza por 1 en binario) para estar seguros de que el número es de 1.024 bits, y no de 1.023 bits, asegurándose así también de que el módulo n será de 2.048 bits (o al menos de 2.047 bits16). Respondiendo a la pregunta {P2}, teóricamente no necesariamente ambos números p y q deben ser de 1.024 bits, para que su producto n sea de 2.048 bits, sino que uno de ellos podría ser algo más pequeño (por ejemplo, p de 1.020 bits), y el otro algo más grande (por ejemplo, q de 1.028 bits), siendo el producto n de ambos también de 2.048 bits. El conocer de antemano la longitud (1.024 bits) de ambos números primos p y q no facilita los ataques por factorización del módulo n. Lo importante es que el módulo n sea de 2.048 bits. De hecho ocurriría lo contrario, si uno de los dos números primos p o q fuera significativamente más pequeño, se facilitarían los ataques de factorización, que se centrarían en ese número más pequeño o débil. Se debe tener en cuenta que se está trabajando con números de gran tamaño y que la cantidad de números primos de 1.024 bits que existe es muy elevada. Además, por el teorema de Dirichlet, los números primos están uniformemente distribuidos en el módulo n.

Una vez elegidos los números primos p y q, es posible calcular n, junto a Φ(n), y se pueden por tanto generar las claves pública y privada, e y d, o (e,n) y (d,n). Se podría pensar que dado que los datos que se cifran con la clave pública se pueden descifrar con la clave privada, y teniendo en cuenta que ambas claves permiten realizar operaciones matemáticas inversas, una vez generadas ambas claves, se podría indistintamente seleccionar inicialmente cualquiera de ellas para que actuase como la clave pública y/o como la clave privada, siendo la otra clave su inversa. Es decir, cuando un software con soporte para RSA, como por ejemplo OpenSSL, genera las dos claves, se podría pensar que es posible elegir indistintamente una u otra como clave pública o privada, aunque en realidad no es así. Planteado de otra forma, se podría pensar que el exponente público e (de la clave pública) y el exponente privado d (de la clave privada) son de un tamaño en bits similar, tal y como ocurría con p y q.

En realidad, y respondiendo a la pregunta {P4}, se recomienda elegir un valor de clave pública e pequeño en relación con el módulo n [0], ya que esto asegura que el valor de la clave privada d será muy grande, y potencialmente más segura, al dificultarse su obtención mediante fuerza bruta. En la práctica, se toma como valor único y conocido del exponente público e el número 65.537, conocido como número 4 de Fermat o F4.

Tomando los dos números primos p y q de 1.024 bits, y el módulo n de 2.048 bits, al igual que Φ(n), y dado que d = inv (e, Φ(n)) y que e es el valor 65.537 (compuesto por 17 bits), por concepto de inversos, el valor de d será como mínimo de 2.031 bits (2.048-17 bits).

Adicionalmente, el número 4 de Fermat, empleado en e, presenta propiedades muy interesantes para las operaciones de cifrado de RSA. Debido a que el número 65.537 sólo tiene dos bits con valor 1 (y 15 bits con valor 0), 0x10001 en hexadecimal, al aplicar el algoritmo de exponenciación rápida en las operaciones de cifrado, donde e actúa de exponente, C = Me mod n, debido a que está compuesto de muchos ceros , permite agilizar las operaciones de cálculo [0], mejorando la eficiencia del proceso de cifrado de RSA. Por tanto, las operaciones de cifrado con la clave pública e en RSA son mucho más eficientes y rápidas que las operaciones de descifrado con la clave privada d.

En resumen, la clave pública basada en el exponente público e es de reducido tamaño, los 17 bits del número 4 de Fermat, mientras que la clave privada basada en el exponente privado d tiene un tamaño cercano al módulo n (2.048 bits).

Para agilizar las costosas operaciones de exponenciación con números grandes involucradas en el proceso de descifrado de RSA empleando la clave privada d se hace uso del Teorema del Resto Chino (TRC), descrito en detalle en la documentación de la certificación CriptoCert Certified Crypto Analyst. El destinatario de un mensaje cifrado, al disponer tanto de d, como de los números primos p y q, podrá realizar los cálculos de aritmética modular en los grupos de p y q, de 1.024 bits, en lugar de en el grupo del módulo n, de 2.048 bits, reduciendo el tiempo de cómputo (en unas 4 veces [0]). Como se verá posteriormente de forma práctica, OpenSSL proporciona ciertos valores adicionales a la hora de generar las claves RSA que permiten hacer uso del TRC en el proceso de descifrado

Comentarios

13 Si los números primos p y q son "muy" cercanos, sería trivial factorizar n simplemente obteniendo su raíz cuadrada y buscando números impares, por arriba y por debajo de ese valor, que fuesen primos.
14 El autor de la tesis estuvo involucrado en el descubrimiento y publicación de la vulnerabilidad ROCA [18] en el año 2017.
15 En teoría de números, los números primos provables son aquellos que se ha calculado que son primos mediante algoritmos que permiten comprobar que no son números compuestos (garantizan que son primos), mientras que los números primos probables son aquellos que han pasado tests de primalidad probabilísticos y que muy probablemente (pero no con total certeza) son primos [1].
16 Posteriormente se describirá como OpenSSL se asegura en realidad de que los dos primeros bits de los números primos p y q tienen el valor 1, por lo que el módulo n será del tamaño esperado, 2.048 bits.
17 Técnicamente se indica que F4 tiene un peso de Hamming bajo: https://en.wikipedia.org/wiki/Hamming_weight

Referencias:


Artículo cortesía de Raúl Siles (raul@criptocert.com) - CriptoCert - www.criptocert.com

Agradecimientos: Jorge Ramió (jorge@criptocert.com) y Alfonso Muñoz (alfonso@criptocert.com)


en
Etiquetas: , , , ,

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)