De cara a finalizar el artículo, y con el objetivo de comprobar los contenidos previos, se debe tener en cuenta que todos los detalles descritos previamente a lo largo del presente artículo sobre los números p y q y las claves RSA pueden ser analizados y corroborados de forma práctica mediante la generación de un par de claves RSA, pública y privada, empleando OpenSSL [15] (los ejemplos hacen uso de macOS, pero los resultados serán muy similares en Windows o Linux). El siguiente comando permite la generación del par de claves RSA, pública y privada, de 2.048 bits mediante OpenSSL (sin proteger o cifrar el fichero resultante que contiene la clave privada):
$ openssl genrsa -out privada.pem 2048
Generating RSA private key, 2048 bit long modulus
.......................................................................................................................+++
.............+++
e is 65537 (0x10001)
$ ls -l
-rw-r--r-- 1 siles staff 1679 Sep 1 00:00 privada.pem
$ file privada.pem
privada.pem: PEM RSA private key
NOTA: Si se procede a la generación de claves RSA de mayor tamaño, por ejemplo de 8.192 bits, se apreciará cómo el tiempo medio necesario para encontrar los números primos p y q aumenta significativamente (por ejemplo, de 0,14s a 14s), y cómo el número de iteraciones de los test de primalidad disminuye (ver FIPS 186-4).
Los signos, o símbolos, asociados al carácter "." y "+" que se muestran durante la generación de la clave indican el progreso en la selección de los números primos p y q. Tal como indica la página del manual (man) del comando genrsa de OpenSSL , el "." indica cada número candidato que ha pasado una criba inicial como posible número primo, y el "+" indica que el número candidato ha pasado una iteración del test de primalidad de Miller-Rabin. Un carácter de nueva línea indica que el número ha pasado todos los tests de primalidad. En base a estos detalles, parece que en la versión de OpenSSL empleada en los ejemplos con macOS Mojave 10.14.x (LibreSSL19 2.6.520), únicamente se llevan a cabo 3 iteraciones del test de primalidad de Miller-Rabin para cada número primo p y q cuando estos son de 1.024 bits (a diferencia de las 5 iteraciones esperadas según el código fuente de OpenSSL, tal como se detalla posteriormente).
Si en su lugar se hace uso de la versión de OpenSSL disponible en Linux, por ejemplo 1.1.0h, es posible corroborar que se llevan a cabo las 5 iteraciones del test de primalidad de Miller-Rabin esperadas (indicadas en la salida del siguiente comando por los 5 signos "+"):
Si en su lugar se hace uso de la versión de OpenSSL disponible en Linux, por ejemplo 1.1.0h, es posible corroborar que se llevan a cabo las 5 iteraciones del test de primalidad de Miller-Rabin esperadas (indicadas en la salida del siguiente comando por los 5 signos "+"):
$ openssl genrsa -out privada.pem 2048
Generating RSA private key, 2048 bit long modulus
...+++++
...+++++
e is 65537 (0x010001)
Si se inspecciona el fichero "privada.pem" generado, es posible identificar que contiene una clave RSA privada (en formato base64) mediante el texto "-----BEGIN RSA PRIVATE KEY-----":
$ cat privada.pem
-----BEGIN RSA PRIVATE KEY-----
MIIEpAIBAAKCAQEAtxNesQq1i5i/4BBWWe5JBc02+E6GaRLeVbSaYS3+OKWzPCKb
...
zTIN1f91C1/t2/rYQGWEumCqKnq/UIQTLVeOOg0+wcolnHLMoeVGKg==
-----END RSA PRIVATE KEY-----
El siguiente comando de OpenSSL permite obtener una versión en formato texto de la clave privada RSA generada, con todos los parámetros asociados:
$ openssl rsa -in privada.pem -text -out privada.txt
writing RSA key
$ ls -l
-rw-r--r-- 1 siles staff 1679 Sep 1 00:00 privada.pem
-rw-r--r-- 1 siles staff 5681 Sep 1 00:01 privada.txt
$ cat privada.txt
Private-Key: (2048 bit)
modulus:
00:b7:13:5e:b1:0a:b5:8b:98:bf:e0:10:56:59:ee:
<… +15 líneas …>
39:00:4b:4a:65:3f:90:13:f3:11:2a:ce:48:61:f8:
77:6b
publicExponent: 65537 (0x10001)
privateExponent:
00:99:86:bd:de:fc:1b:18:b1:05:1f:72:b3:e7:80:
<… +15 líneas …>
5e:cf:6b:7e:11:7c:9d:ca:56:e2:6b:16:17:35:13:
ca:31
prime1:
00:df:bb:4c:7b:56:b1:71:9b:c8:10:9f:a8:65:8b:
<… +6 líneas …>
ab:15:56:ab:b5:af:8f:65:ef:63:bc:6a:a9:7b:82:
26:ac:71:79:a1:71:aa:63:a9
prime2:
00:d1:7a:f4:da:fb:74:c1:1b:19:df:7d:cc:07:d1:
<… +6 líneas …>
c1:9d:ee:57:2f:22:9c:67:8f:59:82:bf:9b:9f:41:
ee:fd:5b:a6:a1:c0:e7:ae:f3
exponent1:
00:86:97:05:26:79:7b:9b:8d:8c:68:3b:b3:b1:0a:
<… +6 líneas …>
5d:9c:23:9c:7e:5a:d3:98:0d:cf:e0:ec:05:72:f0:
53:d5:8f:1a:0d:7d:f4:73:a9
exponent2:
0a:ec:d8:bc:5b:04:f9:d5:4a:02:27:f3:6e:2c:f0:
<… +6 líneas …>
92:b0:0d:87:fd:cc:1e:72:91:7e:8a:33:b9:98:9c:
b8:46:01:68:ca:40:cb:15
coefficient:
23:d5:3c:97:e5:8b:34:0f:4c:51:6e:b9:12:72:3c:
<… +6 líneas …>
aa:2a:7a:bf:50:84:13:2d:57:8e:3a:0d:3e:c1:ca:
25:9c:72:cc:a1:e5:46:2a
-----BEGIN RSA PRIVATE KEY-----
MIIEpAIBAAKCAQEAtxNesQq1i5i/4BBWWe5JBc02+E6GaRLeVbSaYS3+OKWzPCKb
...
zTIN1f91C1/t2/rYQGWEumCqKnq/UIQTLVeOOg0+wcolnHLMoeVGKg==
-----END RSA PRIVATE KEY-----
NOTA: Los valores se muestran empleando 15 pares de caracteres hexadecimales (o 15 bytes) por cada fila.
Se puede ver como las claves RSA generadas por OpenSSL hacen uso del número 4 de Fermat para la clave pública e = 65.537 (0x10001), tanto en el proceso de generación de las claves, como al inspeccionar sus detalles.
Los detalles en formato texto de la clave privada permiten obtener el tamaño de la clave privada, 2.048 bits, junto al módulo n (modulus, compuesto por 257 bytes o 2.056 bits), los valores del exponente público e (65.537) y del exponente privado d, pudiendo apreciarse la diferencia en tamaño entre ambos (17 bits y 2.056 bits, o 257 bytes, respectivamente), los números primos p (prime1, compuesto por 129 bytes o 1.032 bits) y q (prime2, también compuesto por 129 bytes o 1.032 bits), y la clave privada RSA en formato base64 al final (al no hacer uso de la opción "-noout").
Adicionalmente, OpenSSL proporciona otros parámetros como exponent1 (dp, compuesto por 129 bytes o 1.032 bits), exponent2 (dq, compuesto por 128 bytes o 1.024 bits) y coefficient (qInv, también compuesto por 128 bytes o 1.024 bits) que son utilizados, junto a los números primos p y q, en la fórmula de Garner [0] como parte de las optimizaciones empleadas al aplicar el TRC en el proceso de descifrado de RSA.
Curiosamente, el tamaño en bits (o bytes) de los diferentes elementos involucrados en la clave privada RSA no coinciden con los esperados. Ello se debe a que OpenSSL, con el formato de fichero DER (Distinguished Encoding Rules, que es realmente el formato binario que es codificado en base64 en los ficheros ".pem", Privacy Enhanced Mail, PEM), añade un byte inicial con el valor 0x00 que debe ser eliminado. Como resultado, tanto el módulo n como el exponente privado d pasarían a estar formados por un byte menos, es decir, 2.048 bits (o 256 bytes), los números primos p y q pasarían a estar compuestos por 1.024 bits (o 128 bytes), al igual que el exponent1 (dp). De esta forma, el tamaño de todos los valores mostrados coincide con el esperado.
El motivo de este byte adicional se debe a que el formato de representación binaria ASN.1 que es utilizado por el formato de fichero DER codifica los números enteros (ASN.1 INTEGER) con signo, en formato big endian. Como todos los números empleados en RSA son enteros positivos, y dado que son números cuya longitud es múltiplo de 8 bits (o un byte), como 1.024 o 2.048 bits, OpenSSL los antecede por la izquierda con el valor 0x00. En caso contrario, la codificación ASN.1 de estos valores podría representar números enteros negativos (en codificación de complemento a 2, donde el bit más significativo representa el bit de signo, indicando un bit con valor 1 un número negativo). Se debe hacer notar que en el ejemplo previo no se ha añadido ese byte 0x00 adicional para los valores de exponent2 y de coefficient (que presentaban el tamaño esperado de 1.024 bits), y se deja como ejercicio para el lector descubrir cuál es el motivo. Alternativamente, el siguiente comando de OpenSSL (asn1parse) permite obtener los valores numéricos sin el valor 0x00:
$ openssl asn1parse -in privada.pem
Por otro lado, es posible exportar únicamente la clave pública (opción "-pubout") a un fichero, mediante el siguiente comando de OpenSSL21:
$ openssl rsa -in privada.pem -outform PEM -pubout -out publica.pem
writing RSA key
$ ls -l
-rw-r--r-- 1 siles staff 1679 Sep 1 00:00 privada.pem
-rw-r--r-- 1 siles staff 5681 Sep 1 00:01 privada.txt
-rw-r--r-- 1 siles staff 451 Sep 1 00:02 publica.pem
$ file publica.pem
publica.pem: ASCII text
NOTA: Como se puede ver, el tamaño del fichero con la clave pública es significativamente más pequeño que el tamaño del fichero con la clave privada.
Si se inspecciona el fichero "publica.pem", es posible identificar que contiene una clave RSA pública (en formato base64) mediante el texto "-----BEGIN PUBLIC KEY-----":
Si se inspecciona el fichero "publica.pem", es posible identificar que contiene una clave RSA pública (en formato base64) mediante el texto "-----BEGIN PUBLIC KEY-----":
$ cat publica.pem
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAtxNesQq1i5i/4BBWWe5J
...
awIDAQAB
-----END PUBLIC KEY-----
Al igual que anteriormente se ha hecho con la clave privada, es posible mediante el siguiente comando de OpenSSL obtener una versión en formato texto de la clave pública RSA generada (opción "-pubin"), con todos los parámetros asociados:
$ openssl rsa -in publica.pem -text -pubin -out publica.txt
writing RSA key
$ ls -l
-rw-r--r-- 1 siles staff 1679 Sep 1 00:00 privada.pem
-rw-r--r-- 1 siles staff 5681 Sep 1 00:01 privada.txt
-rw-r--r-- 1 siles staff 451 Sep 1 00:02 publica.pem
-rw-r--r-- 1 siles staff 1369 Sep 1 00:03 publica.txt
$ cat publica.txt
Public-Key: (2048 bit)
Modulus:
00:b7:13:5e:b1:0a:b5:8b:98:bf:e0:10:56:59:ee:
<… +15 líneas …>
39:00:4b:4a:65:3f:90:13:f3:11:2a:ce:48:61:f8:
77:6b
Exponent: 65537 (0x10001)
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAtxNesQq1i5i/4BBWWe5J
...
awIDAQAB
-----END PUBLIC KEY-----
Los detalles en formato texto de la clave pública permiten obtener el tamaño de la clave pública, 2.048 bits, junto al módulo n, con exactamente el mismo valor que el de la clave privada (modulus, compuesto por 256 bytes o 2.048 bits, eliminando el valor 0x00 inicial), junto al valor del exponente público e (65.537), y de la clave pública RSA en formato base64 al final (al no hacer uso de la opción "-noout").
Complementariamente se puede hacer uso del software educativo genRSA [16] (actualmente en su versión 2.1), ampliamente referenciado en la certificación CriptoCert Certified Cripto Analyst, para llevar a cabo el estudio y los cálculos relativos a los números primos p y q y a las claves RSA asociadas, tanto de manera manual como automática, para la obtención de las Claves Privadas Parejas (CPP), así como para la realización de diferentes ataques sobre las claves RSA. genRSA incluye los tests de primalidad de Miller-Rabin y de Fermat. Complementariamente, se puede seguir el cuaderno 4 del proyecto CLCript (junto a otros cuadernos también focalizados en RSA), centrado en la generación de claves RSA con genRSA v2.1 [17].
Comentarios
20 Obtenida mediante el comando "openssl version".
21 Posteriormente se podría convertir la clave pública de formato PEM a formato DER: "openssl rsa -pubin -inform PEM -in publica.pem -outform DER -out publica.der".
Referencias:
[0] https://0xword.com/es/libros/36-libro-cifrado-comunicaciones-rsa.html
[1] https://is.muni.cz/th/oba30/thesis-nemec.pdf
[2] http://cacr.uwaterloo.ca/hac/about/chap4.pdf
[3] https://crypto.stackexchange.com/questions/1970/how-are-primes-generated-for-rsa
[4] https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
[5] https://www.sans.org/reading-room/whitepapers/vpns/prime-numbers-public-key-cryptography-969
[6] https://en.wikipedia.org/wiki/Prime_number_theorem
[7] https://security.stackexchange.com/questions/176394/how-does-openssl-generate-a-big-prime-number-so-fast
[8] https://github.com/openssl/openssl/blob/master/crypto/bn/bn_prime.c
[9] https://es.wikipedia.org/wiki/Test_de_primalidad
[10] https://en.wikipedia.org/wiki/Safe_prime
[11] https://en.wikipedia.org/wiki/Strong_prime
[12] https://eprint.iacr.org/2001/007
[13] https://crypto.stackexchange.com/questions/5262/rsa-and-prime-difference
[14] http://www.criptored.upm.es/descarga/Win64OpenSSL1.1.0g_No_Genera_Claves_Correctas_Hasta_128_Bits.pdf
[15] https://www.openssl.org
[16] http://www.criptored.upm.es/software/sw_m001d.htm
[17] http://www.criptored.upm.es/software/sw_m001s.htm
[18] https://crocs.fi.muni.cz/public/papers/rsa_ccs17, https://crocs.fi.muni.cz/_media/public/papers/nemec_roca_ccs17_preprint.pdf
[19] https://eprint.iacr.org/2010/006.pdf, https://hal.inria.fr/inria-00444693v2/document
[20] https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
[1] https://is.muni.cz/th/oba30/thesis-nemec.pdf
[2] http://cacr.uwaterloo.ca/hac/about/chap4.pdf
[3] https://crypto.stackexchange.com/questions/1970/how-are-primes-generated-for-rsa
[4] https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
[5] https://www.sans.org/reading-room/whitepapers/vpns/prime-numbers-public-key-cryptography-969
[6] https://en.wikipedia.org/wiki/Prime_number_theorem
[7] https://security.stackexchange.com/questions/176394/how-does-openssl-generate-a-big-prime-number-so-fast
[8] https://github.com/openssl/openssl/blob/master/crypto/bn/bn_prime.c
[9] https://es.wikipedia.org/wiki/Test_de_primalidad
[10] https://en.wikipedia.org/wiki/Safe_prime
[11] https://en.wikipedia.org/wiki/Strong_prime
[12] https://eprint.iacr.org/2001/007
[13] https://crypto.stackexchange.com/questions/5262/rsa-and-prime-difference
[14] http://www.criptored.upm.es/descarga/Win64OpenSSL1.1.0g_No_Genera_Claves_Correctas_Hasta_128_Bits.pdf
[15] https://www.openssl.org
[16] http://www.criptored.upm.es/software/sw_m001d.htm
[17] http://www.criptored.upm.es/software/sw_m001s.htm
[18] https://crocs.fi.muni.cz/public/papers/rsa_ccs17, https://crocs.fi.muni.cz/_media/public/papers/nemec_roca_ccs17_preprint.pdf
[19] https://eprint.iacr.org/2010/006.pdf, https://hal.inria.fr/inria-00444693v2/document
[20] https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
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)
No hay comentarios:
Publicar un comentario