17 oct 2019

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


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)

¿Cómo se generan y/o eligen los dos números primos p y q empleados en RSA a la hora de generar el par de claves, pública y privada?... y otras cuestiones interesantes asociadas a la generación de las claves en RSA ;-)

Otras preguntas relacionadas que también surgieron, y que es lógico que se plantee cualquier mente inquieta y ávida de sabiduría son, ¿al generar un par de claves RSA de 2.048 bits, la longitud de los número primos p y q es exactamente de 1.024 bits para cada uno, o puede haber ligeras variaciones en su longitud, sin que sean necesariamente números exactamente de la misma longitud? {P2}, ¿cómo se generan y/o eligen los números primos p y q empleados en RSA por parte de un software de referencia en la industria como, por ejemplo, OpenSSL? {P3} y, por último, ¿una vez generadas las dos claves, pública y privada, se podría elegir indistintamente una u otra para jugar el papel de clave pública o privada? {P4}

A continuación vamos a intentar responder a todas estas preguntas y a proporcionar referencias adicionales para quienes estén interesados en profundizar aún más en las respuestas asociadas.
De manera breve e introductoria (para más información se recomienda la lectura del libro "Cifrado de las comunicaciones digitales. De la cifra clásica al algoritmo RSA" de Jorge Ramió y Alfonso Muñoz, cuya 2ª edición ha sido publicada en 2019 [0]), el algoritmo de cifra asimétrico RSA permite tanto cifrar la información (proporcionando confidencialidad), como firmarla (proporcionando autenticidad e integridad). Centrándonos en las operaciones de cifrado, es posible cifrar un mensaje M mediante la clave pública del destinatario (n,e) empleando la siguiente operación de exponenciación en aritmética modular, así como descifrar el mensaje cifrado C mediante la clave privada del destinatario (n,d) para obtener de nuevo el mensaje M original:

Cifrado: C = Me mod nDescifrado: M = Cd mod n
Imagen del certificado digital de la web de CriptoCert (https://www.criptocert.com), con módulo de 2.048 bits, obtenido mediante Firefox en macOS.

La fortaleza de RSA reside en la dificultad computacional de factorizar un número compuesto muy grande, es decir, el módulo n, compuesto por el producto de los dos números primos p y q.

Sin profundizar en los detalles matemáticos, una vez se dispone de p y q, y por tanto de n, se calcularán el resto de valores (e y d) en base a ciertas fórmulas matemáticas como, por ejemplo, el indicador de Euler del módulo n, f(n) = (p-1)(q-1), un valor trampa secreto que permite elegir el exponente público e en el rango 2 < e < f(n), coprimo1 con f(n). Como detalle adicional, el indicador de Euler f(n) proporciona el orden, es decir, la cantidad de números enteros positivos menores o iguales a n y coprimos con n, es decir, el tamaño del "grupo de cifra" definido por el módulo n. Teóricamente, cada usuario elegirá un valor de e para su clave pública asegurándose de que existe un inverso multiplicativo2, es decir, un valor d para poder disponer de una clave privada asociada:
d = inv(e,f(n)) o d = e-1 mod f(n).
En resumen, a la hora de generar sus claves RSA, cada usuario elige dos números primos p y q y los mantiene en secreto, obtiene el módulo n=p*q, que es público, genera la clave pública e, o (n,e), y calcula el indicador de Euler f(n) que actúa como valor trampa secreto para poder calcular la clave privada asociada d, o (n,d)3. El hacer públicos los valores e y n no pone en peligro la clave privada d, ya que para calcular d es necesario conocer el valor secreto trampa f(n), es decir, los números primos p y q.

La pregunta inicial planteada {P1} centrada en cómo se eligen los números primos p y q es común y se ha repetido en foros y grupos de discusión de criptología a lo largo de los años. Conocer los detalles para elegir p y q correctamente es fundamental para cualquier desarrollador que quiera hacer uso de RSA en su software sin emplear librerías criptográficas o software de terceros, o que aun haciendo uso de éstas, quiera verificar que se hace un uso correcto de RSA. Tal como se describe en la nota 4.51 del capítulo 4 del libro "Handbook of Applied Cryptography" de A. Menezes, P. vanOorschot, y S. Vanstone, publicado en 1996 [2], y como se resume en [3], el algoritmo genérico empleado para la obtención de los números primos p y q en RSA es el siguiente:
  1. Generar un número impar p (condición necesaria para que potencialmente sea un número primo4) aleatorio de 'n' bits, siendo 'n' = 1.024 bits para las claves RSA de 2.048 bits comúnmente empleadas hoy en día. Si el número generado no es impar, se le suma 1.
  2. Comprobar si p es un número primo. Para llevar a cabo esta comprobación se pueden emplear diferentes métodos de verificación denominados tests de primalidad, descritos posteriormente.
  3. Si p no es primo, se puede tomar p = p+2 (búsqueda incremental) y volver a realizar la verificación del paso 2, o tomar un nuevo valor de p aleatorio (paso 1) y realizar de nuevo la verificación del paso 2.
Los tests de primalidad [9] utilizados actualmente para números grandes (de cientos o miles de bits) son test probabilísticos5, es decir, comprueban con una muy alta probabilidad si un número grande es primo o no. Para ello tienen en cuenta ciertas propiedades conocidas que cumplen los números primos en base a la teoría de números. Si se ejecutan varias veces sobre un mismo número candidato con distintos valores semilla de entrada, y todas las ejecuciones ratifican que el número parece ser primo, se dispondrá de un mayor nivel de certeza. A un mayor número de ejecuciones del test, mayor certeza de que el número candidato realmente es primo.

El test de primalidad más comúnmente empleado en la actualidad para verificar si un número es primo es el de Miller-Rabin6. Este tipo de tests son bastante rápidos de calcular y, de media, a la hora de comprobar si un número de 1.024 bits es primo, sólo tienen que verificar unos cientos de candidatos posibles, ya que la densidad de números primos en un rango de números cualquiera es bastante elevada (definida por aproximadamente 1/ln(n)). El teorema de los números primos [6] refleja que la distancia entre números primos, por ejemplo de 1.024 bits, es aproximadamente 1.024*ln(2), es decir, 710. Dado que sólo hay que comprobar los números impares como posibles números primos, la verificación o test de primalidad necesitaría comprobar unos 355 candidatos (710/2) antes de encontrar el siguiente número primo de manera incremental. Como referencia, la probabilidad de que Miller-Rabin detecte si un número es primo en una ejecución o ronda es del 75% [7], por lo que tras 64 ejecuciones, la probabilidad de error es muy pequeña, del orden de 2-128.

En el caso de OpenSSL [7], respondiendo a la pregunta {P3}, es posible consultar su código fuente7 [8] para ver que hace uso de numerosos tests, encontrándose referencias a un primer filtrado mediante un algoritmo determinista de criba rápida (cuyo código está basado en la implementación y código de PGP [8]), donde se divide al número candidato por algunos números primos pequeños (los primeros 2.048 números primos8, para descartar rápidamente si el candidato es primo o no), y si el número candidato pasa ese filtro, se emplean principalmente varias ejecuciones9 del test de Miller-Rabin y de su versión mejorada (mencionada posteriormente en el estándar FIPS 186-4, C.3.1 y C.3.2), así como finalmente ciertas comprobaciones para hacer uso de números primos seguros (en inglés, safe primes), es decir, donde (p-1)/2 también es un número primo10 [10]. La utilización de primos seguros puede mitigar ciertos ataques cuando estos números son utilizados con el algoritmo de intercambio de clave de Diffie-Hellman, así como minimizar el número de Claves Privadas Parejas (CPP) asociadas a las claves RSA

A modo de curiosidad, ciertas versiones de OpenSSL para claves con un reducido número de bits (128 bits), no utilizadas en la práctica actualmente, no verifican adecuadamente los números primos p y q empleados para la generación de las claves, lo que da lugar a claves RSA incorrectas, tal como se detalla en el artículo publicado en 2018 por Jorge Ramió: "¿Son correctas las claves RSA que generamos con Win64 OpenSSL1.1.0g? Intentando cifrar con RSA cuando p y q no son primos" [14].

Algunos estándares de la industria para la generación de claves RSA robustas, como ANSI X9.3111
, requerían que los números primos p y q empleados fuesen además primos fuertes (en inglés, strong primes), es decir, en teoría de números, un número primo que está más cerca del siguiente número primo que del número primo que le precede. En criptografía, un primo fuerte cumple ciertas condiciones relacionadas con el número primo que le precede y con el siguiente número primo [11]. El uso de primos fuertes en RSA se recomendó para minimizar los ataques de factorización mediante el algoritmo de Pollard p-1, aunque no protegen frente a otros métodos de factorización del módulo n, como Lenstra (basado en curvas elípticas) o la criba numérica o NFS (Number Field Sieve, o GNFS, General Number Field Sieve), por lo que algunos criptógrafos como Ron Rivest desaconsejaron su utilización ya en 2001 [12], debido también al mayor tiempo de búsqueda necesario para encontrar estos números primos y los limitados beneficios que aportan. En la actualidad, las implementaciones hacen uso de primos fuertes sólo si deben cumplir una certificación que lo impone como requisito (por ejemplo, IEEE 1363).

A modo de curiosidad, el record público actual de factorización de un módulo n de RSA es de 768 bits, conseguido mediante el método NFS a finales del año 2009 y documentado en "Factorization of a 768-bit RSA modulus" [19], asociado al RSA Factoring Challenge [20] (desafío que fue retirado previamente, en el año 2007).


Comentarios

1 Los números coprimos son números enteros (positivos), por ejemplo, a y b, que no tienen ningún factor primo en común, es decir, que su único divisor común es el 1. Dos números son coprimos si su máximo común divisor (MCD) es igual a 1 (mcd [a, b] = 1).
2 mcd [e, f(n)] = 1 (es decir, e y f(n) son números coprimos)
3 La clave privada d se calcula mediante el algoritmo extendido de Euclides.
4 Todos los números primos (números enteros positivos) mayores que 2 son impares.
5 A diferencia de las comprobaciones o tests determinísticos, como la criba de Eratóstenes, mucho más lento de calcular, o como el test AKS: https://es.wikipedia.org/wiki/Test_de_primalidad_AKS
6 Complementariamente, existen algoritmos para la generación de números primos, como el algoritmo de Maurer (apartado 4.4.4 [2]), empleado para la generación de primos provables: https://pdfs.semanticscholar.org/3df0/e64897ebbed46a6d034196f9b3962ca45b07.pdf
7 La versión actual de OpenSSL disponible en GitHub en el momento de elaboración del presente artículo era la 3.0.0-dev, mientras que la versión estable principal era la 1.1.1c.
9 El número de ejecuciones o iteraciones del test de primalidad de Miller-Rabin depende de la longitud en bits del número primo (tal y como también establece el estándar FIPS 186-4, descrito posteriormente).
10 Un número primo seguro se define habitualmente como un número de la forma 2p+1, donde p también es primo como, por ejemplo, 23 = 2*11+1, al ser 11 también un número primo.

Referencias:

en
Etiquetas: , , , ,

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)