MOOC El algoritmo RSA


Lección 4. Claves privadas y públicas parejas
Dr. Jorge Ramió Aguirre - 04/05/2012 

Los 4 apartados de esta cuarta lección están dedicados al análisis de las denominadas claves privadas parejas y claves públicas parejas en RSA, números distintos a aquellos pero que, sin embargo, realizan la misma función. ¿Puede ser esto un motivo de preocupación?

Si deseas descargar las diapositivas del curso en formato pptx animado o bien en pdf, puedes hacerlo 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 RSA04] 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. Entender qué son las claves parejas en RSA.
  • 2. Proponer condiciones de diseño en las claves RSA para minimizar las claves parejas.
  • 3. Diferenciar entre claves privadas y claves públicas parejas.
  • 4. Comprobar este hecho en claves RSA reales.
  • 5. Conocer si la existencia de claves privadas y públicas parejas es una vulnerabilidad de RSA.

Software que vas a utilizar en esta lección


APARTADO 4.1. ¿QUE SON LAS CLAVES PRIVADAS PAREJAS

Cuando generamos una clave RSA, usamos como trampa el indicador de Euler Φ(n) para calcular la clave privada d a partir del conocimiento de la clave pública e. Puesto que mcd [e, Φ(n)] = 1, se asegura que el inverso d existe y que, además, es el único inverso de la clave pública e en ese cuerpo Φ(n).

No obstante, como es lógico, la cifra se hace posteriormente en el cuerpo público n para que todo el mundo pueda utilizarlo. Y en dicho cuerpo n ya no se cumple que el único inverso de la clave pública e sea la clave privada d. Verás que hay al menos otro valor diferente a d que cumple las mismas funciones y que, por tanto, permite descifrar lo cifrado con la clave pública. A estas claves se les llama Claves Privadas Parejas o de forma abreviada CPP.

Esto es algo en principio inesperado porque normalmente siempre se ha dicho que un sistema de cifra asimétrico, como lo es RSA, tiene una única clave pública y, por lo tanto, también una única clave privada. Esto es falso.

Vamos a explicarlo con un sencillo ejemplo, que podrás comprobar fácilmente usando por ejemplo la calculadora de Windows.

Sea una clave RSA con p = 37, q = 41, n = 1.517, Φ(n) = 1.440, e = 13, d = 997. Vamos a cifrar el valor 1.001 con la clave pública e = 13 y luego descifrar el criptograma con la clave privada d = 997.

  Cifrado con e = 13: 1.00113 mod 1.517 = 1.088
  Descifrado con d = 997: 1.088997 mod 1.517 = 1.001. Se ha recuperado el secreto.
Pero si usamos los números 277, 637 y 1.357 como si fuesen la clave privada d, obtenemos lo siguiente:
  Descifrado con d' = 277: 1.088277 mod 1.517 = 1.001
  Descifrado con d' = 637: 1.088637 mod 1.517 = 1.001
  Descifrado con d' = 1.357: 1.0881.357 mod 1.517 = 1.001 ... ¡también se ha recuperado el texto en claro o secreto!

Lo que ha sucedido en el ejemplo anterior es que en el cuerpo de cifra n = 1.517 con una clave pública e = 13, los valores 277, 637 y 1.357 son claves privadas parejas (CPP) d' que hacen la misma función que la clave privada d = 997.

Las tres claves privadas parejas de la clave RSA del ejemplo

En la prácticaRSA4.1.1 comprobarás con el software genRSA y con ExpoCrip que esos tres valores son las claves privadas parejas de dicha clave RSA.

Toda clave RSA tendrá como mínimo una clave privada pareja. Como podrás comprobar, la cantidad de claves privadas parejas dependerá fuertemente de los primos p y q, siendo las ecuaciones que nos entregan este valor de CPP las que se aprecian en la siguiente diapositiva.

Cálculo de las claves privadas parejas en RSA

Observa en la diapositiva anterior que las claves privadas parejas están separadas entre ellas por un valor constante, en este caso igual a 36, y que la clave privada d se encuentra entre uno de esos valores.

En el ejercicioRSA4.1.1 deberás usar las ecuaciones que se muestran en la diapositiva anterior para calcular la cantidad de claves privadas de una clave RSA, así como sus valores, sin contar con la ayuda de software de prácticas.

Generamos ahora otra clave RSA (p = 211, q = 239, e = 131) y obtenemos las siguientes 13 claves privadas parejas, además de la clave privada marcada en negrita, separadas por una distancia igual a 3.570:
  CPP: [3.461; 7.031; 10.601; 14.171; 17.741; 21.311; 24.881; 28.451; 32.021; 35.591; 39.161; 42.731; 46.301; 49.871]

En este caso hemos encontrado varias claves privadas parejas mucho menores que la propia clave privada, y en el ejemplo de la diapositiva incluso menor que la propia clave pública. A primera vista, esto no es algo muy agradable, pero no hay de qué preocuparse porque verás que para los valores que se usan en la práctica y estudiados en la Lección 2, esta situación de claves privadas parejas muy pequeñas, y por tanto muy fáciles de atacar por fuerza bruta, no se dará. Pero eso lo veremos en un próximo apartado.

Cuestiones para reflexionar e investigar:
1. ¿Crees que esto que has visto podría ser un motivo de preocupación o de debilidad de una clave RSA?
2. ¿Qué utilidad le puedes encontrar al conocimiento por un tercero de una clave privada pareja si el dueño de la clave no la conoce, porque por ejemplo no es él o ella quien genera dicha clave RSA -como lo has hecho aquí- sino un software que le entrega los valores públicos e y n, y el usuario se limita sólo a introducir una frase de paso para guardar o recuperar su clave privada d?
3. Si has utilizado alguna vez el programa de correo seguro PGP o bien GnuPG, recuerda cómo has creado una clave RSA o DH.
Nota: Si esta última cuestión te supera, no te preocupes. Para llegar a la respuesta correcta es necesario conocer cómo operan las funciones hash y cuál es su fortaleza ante posibles ataques. Algo que escapa del objetivo de este curso, pero que sin embargo te lo comento por si deseas averiguar qué tienen que ver las funciones hash y el almacenamiento seguro de tu clave privada en tu PC.


APARTADO 4.2. MINIMIZANDO LAS CLAVES PRIVADAS PAREJAS

Las claves privadas parejas dependerán fuertemente de la elección de los primos p y q. Para obtener una clave con la mínima cantidad de claves privadas parejas, es decir solamente una, se recomienda usar primos seguros ya vistos en la Lección 2. Recuerda que si deseas buscar diferentes tipos de números primos, los puedes encontrar en está página List_of_prime_numbers.

Por ejemplo si generamos estas 5 claves RSA, en donde verás que sólo cambia ligeramente el valor del primo q, encontramos grandes variaciones en la cantidad de claves privadas parejas.

  Clave 1: p = 53, q = 59, e = 11, d = 1.371
CPP = 2.879 (una)
  Clave 2: p = 53, q = 61, e = 11, d = 851
CPP = 71, 1.631, 2.411, 3.191 (cuatro)
  Clave 3: p = 53, q = 73, e = 11, d = 2.723
CPP = 851, 1.787, 3.659 (tres)
  Clave 4: p = 53, q = 79, e = 11, d = 1.475
CPP = 71, 227, 383, 539, 695, 851, 1.007, 1.163, 1.319, 1.631, 1.787, 1.943, 2.099, 2.255, 2.411, 2.567, 2.723, 2.879, 3.035, 3.191, 3.347, 3.503, 3.659, 3.815, 3.971, 4.127 (veintiséis)
  Clave 5: p = 53, q = 97, e = 11, d = 2.723
CPP = 227, 1.475, 3.971 (tres)

De los números primos usados en el ejemplo anterior, sacaremos una primera conclusión:

  El primo p = 53 no es un primo seguro porque se obtiene como (26x2 + 1) y 26 obviamente no es primo.
  Todos los primos q, excepto el primero q = 59 = 29x2 + 1, con 29 primo, tampoco son primos seguros porque:
  61 = (30x2 + 1), 73 = (36x2 + 1), 79 = (39x2 + 1) y 97 = (48x2 + 1) y los números 30, 36, 39 y 48 no son primos.

Precisamente sólo cuando se ha usado un primo seguro q = 59, la clave RSA generada ha presentado el número mínimo de CPP, es decir una. Esto no es una casualidad; para minimizar la cantidad de claves privadas parejas, la mejor solución pasa por usar primos seguros, aunque es posible que generemos una clave RSA con una sola CPP sin usar estos primos seguros, como comprobarás en la próxima práctica.

En la siguiente captura de pantalla se muestra una clave que definiremos como óptima, con una clave privada pareja y 9 nueve números no cifrables pero que no se obtiene con primos seguros, en tanto que p = 59.771 y q = 50.159 no son primos seguros.

Clave óptima generada sin primos seguros

No obstante, como ya se ha comentado en el apartado 2.5 de Lección 2, la recomendación que se hace en el estándar ANSI X9.31 es usar primeros fuertes (strong primes) en vez de primos seguros (safe primes).

En la siguiente práctica vas a necesitar usar un software que te convierta los valores decimales a hexadecimal y viceversa. Aunque puedes encontrar en la red varias páginas Web con conversores online como el que ya hemos utilizado en la Lección 3 para convertir de hexadecimal a ASCII, te recomiendo que uses el programa Conversor dec2hex desarrollado en Java, que realiza esta conversión de manera muy rápida y funciona correctamente para números grandes.

Conversor dec2hex para números grandes

En la prácticaRSA4.2.1 generarás con el software genRSA y con ExpoCrip varias claves RSA con primos seguros y no seguros y comprobarás lo que hemos comentado sobre las claves privadas parejas.

La elección de la clave pública e también afecta, pero de manera casi insignificante, a la cantidad de claves privadas; será mucho más importante controlar los valores de p y q.

En la prácticaRSA4.2.2 comprobarás con el software genRSA que el valor de la clave pública e puede modificar sólo ligeramente la cantidad de claves privadas parejas.

De hecho, de las 29 claves generadas en la práctica anterior, 24 de ellas muestran 26 claves privadas parejas y sólo en 5 casos el número de claves privadas parejas ha sido 25, es decir sólo una menos. Y esto sucede incluso con primos seguros.

En la prácticaRSA4.2.3 vas a comprobar esto último con el software genRSA para una clave RSA con primos seguros y verás cómo se comportan las CPP cuando usas hasta dieciocho claves públicas válidas.

Cuando generes claves con OpenSSL en la Lección 10 verás que por lo general se obtienen claves RSA con una única CPP, aunque el software no asegura que siempre se obtenga ese valor mínimo, como lo comprobaremos en su momento. No obstante, con una librería Crypto++ mucho más antigua, como la de Wei Dai del año 2003 que es la utilizada en el software genRSA, a veces se obtienen claves reales llamativas como la que se muestra en la siguiente captura de pantalla.

Clave generada con genRSA, con librería Crypto++ de Wei Dai del año 2003

En la prácticaRSA4.2.4 vas a generar con el software genRSA algunas claves RSA que entregan cantidades muy altas de CPP.

Cuestiones para reflexionar e investigar:
1. A partir de los resultados vistos en este apartado, vuelve a la Lección 2.5 y recuerda qué sucedía con las claves privadas parejas cuando cometíamos el error de hacer q = p.
2. ¿Te parece que una clave RSA con mil o más claves privadas parejas podría llegar a ser vulnerable?


APARTADO 4.3. TAMBIEN EXISTIRAN CLAVES PUBLICAS PAREJAS

Las operaciones de cifra con RSA serán KeR mod nR para un intercambio de clave secreta K con un receptor R, o bien h(M)dE mod nE para la firma digital de un mensaje M a través de su función hash h(M) por parte un emisor E.

Por ejemplo, si la clave RSA es p = 193, q = 241, n = 46.513, e = 37, d = 39.853, el intercambio de una clave K 150 sería 15037 mod 46.513 y la firma digital de un hash 150 sería 15039.853 mod 46.513.

Como es fácil observar, al pasar las ecuaciones a números, da exactamente lo mismo poner en el exponente la clave pública del receptor eR en el primer caso que la clave privada dE del emisor en el segundo; son simplemente números sin ningún otro sentido.

En el ejercicioRSA4.3.1 te encontrarás con dos ecuaciones de cifra que, en principio, no puedes saber cuál es un intercambio de clave y cuál una firma digital.

Al resolver dicho ejercicio, podrás llegar a una conclusión razonada sobre cuál de las dos operaciones se trata de un intercambio de clave y cuál de una firma digital porque ya conoces los tamaños recomendables para la clave pública e y la clave privada d que hemos analizado en la Lección 2, pero sin ese dato perfectamente podrías haber aceptado la situación contraria.

Por lo tanto, si una determinada clave RSA tiene, por ejemplo, 6 claves privadas parejas, tendrá también 6 claves públicas parejas. Simplemente cambiamos los valores de e por d en las ecuaciones de claves parejas vistas en el apartado 4.1 como lo indica la siguiente diapositiva, salvo que como es lógico los números serán distintos.

Claves públicas parejas de la misma clave que la diapositiva anterior

Por ejemplo si con la clave de la diapositiva anterior se firma el valor 24, la firma podrá podrá comprobarse con la clave pública e y con cualquiera de las claves públicas parejas como se muestra, usando la calculadora de Windows.

Firma con clave privada: 24137 mod 247 = 215
Comprobación de firma con clave pública: 21541 mod 247 = 24
Comprobación de firma con claves públicas parejas:
2155 mod 247 = 21577 mod 247 = 215113 mod 247 = 215149 mod 247 = 215185 mod 247 = 215221 mod 247 = 24

Cuestiones para reflexionar e investigar:
1. Sin haber leído el siguiente apartado de esta lección, ¿qué te llama la atención o te preocupa más, la existencia de claves privadas parejas o de claves públicas parejas?


APARTADO 4.4. ¿HAY QUE PREOCUPARSE POR ESTAS CLAVES PAREJAS?

A primera vista, no resulta agradable el conocimiento de estas claves parejas en RSA y que realizan la misma función que una clave privada o una clave pública, más aún si se tiene en mente lo que se dice habitualmente de este sistema de cifra asimétrico: que existe una única clave pública (e, n) y una única clave privada (d), y lo que se cifra con una de ellas se descifra con la otra. De hecho, todos los certificados digitales X.509 que trabajan con RSA tienen este tipo de claves.

Hemos visto además que el cálculo de estas CPP es muy sencillo, que están separadas por un valor constante y que incluso para claves con valores reales de miles de bits se obtienen sus valores muy rápidamente porque el cálculo es elemental.

Pero, ¿qué sucedería si al generar una clave RSA obtenemos un número muy alto de claves privadas parejas (y públicas obviamente) como muestra la figura?

Clave RSA con más de 3.000 claves privadas parejas

Aunque claves como las de la diapositiva son muy raras (una excepción) y con versiones actuales de OpenSSL ya no se generan claves RSA con tantas CPP como lo comprobarás en la Lección 10, la verdad es que no hay de qué alarmarse puesto que debido a los valores estándar que se usan de p, q y e en la generación de claves reales, y que ya estudiamos en la Lección 2, aunque existan varios miles de CPP sus valores serán todos muy próximos al valor del módulo n y, por lo tanto, será imposible adivinarlos o intentar romperlos por fuerza bruta.

Vas a comprobar esto en la prácticaRSA4.4.1 generando esta clave con el software genRSA y viendo luego el tamaño en bits de todas esas claves privadas parejas.

Como habrás podido comprobar en la práctica anterior, para esta clave en concreto con 3.149 CPP, la clave privada pareja de mayor tamaño tiene 1.024 bits, es decir igual que el módulo n, y la clave privada pareja de menor tamaño tiene nada menos que 1.012 bits.

Esta característica de una especie de nebulosa de CPP muy cerca del módulo será una constante en todas las claves reales, si bien como ya se ha dicho hoy en día con el software actualizado ya no se obtienen estos valores tan altos, lo normal será como mucho una cifra de 2 ó 3 dígitos en CPP y más del 95% de claves generadas mostrarán una sola CPP.

Para estas condiciones de diseño estándar de claves RSA, en que p y q son primos de al menos 512 bits y la clave pública es el número 4 de Fermat (65.537 en decimal ó 10001 en hexadecimal), aunque existan muchas claves privadas parejas éstas son de un valor inmenso y por tanto imposibles de adivinar.

Por ese motivo, también es importante que exista esa gran diferencia de tamaños entre la clave pública e y la clave privada d.

Como conclusión, en este rango de valores como los que se usan en banca online y comercio electrónico por ejemplo, no tiene ninguna trascendencia la existencia de claves privadas parejas.

Lo que sucede es que todo aquel que tenga una clave RSA, salvo que la haya generado él mismo o ella misma, nunca sabrá cuántas claves privadas parejas tiene esa clave RSA ni mucho menos menos sus valores. Cuando generes claves RSA con OpenSSL en la Lección 10, podrás conocer los valores de p, q, n, e y d, además de otros parámetros para usar el teorema chino del resto en el descifrado, pero no te informará sobre la existencia de estas CPP.

¿Qué pasará ahora con la claves públicas parejas?

La situación en este caso es ligeramente diferente en tanto los valores de las claves públicas parejas podrán tener valores muy pequeños y, además, la clave es por definición pública y no tiene ningún secreto.

No obstante, existe un escenario de firma digital como el que se comenta a continuación que nos deja ciertas dudas.

Supongamos que un usuario firma el hash de un mensaje con su clave privada, lo que envía a destino junto con el mensaje original pues no es necesario agregarle confidencialidad. En destino se descifra el criptograma con la clave pública del emisor, recuperando por tanto el hash firmado. Se calcula el hash del mensaje recibido y se comparan los dos hash, el de emisión y el recuperado en recepción, para dar validez a dicha firma.

Hasta aquí todo es correcto pero, ¿qué pasaría si mediante algún artilugio alguien puede comprobar la firma usando una clave pública pareja e’ distinta a la clave pública e conocida por todo el mundo? Esto podría interpretarse como una muestra de debilidad del sistema, en tanto nadie conoce la existencia de estas claves parejas y consecuentemente podrían, incluso, dudar de las bondades del algoritmo.

Cuestiones para reflexionar e investigar:
1. Si sabes que una clave RSA de 1.024 bits tiene una cantidad muy alta de claves privadas parejas, ¿crees que con varios cientos de miles de computadores conectados en Internet podría intentarse un ataque por fuerza bruta hasta encontrarla?
2. ¿Cómo crees que reaccionaría un banquero que tiene conocimientos nulos de criptografía si le dices que la clave RSA que usa su servidor Web tiene unas cuantas claves que hacen lo mismo que su clave privada? ¿Crees que sería capaz de entender lo que tú has aprendido en esta lección? ¿Es mejor no decirle nada?
3. ¿Crees que puede ser una vulnerabilidad lo que se comenta en los últimos párrafos de este apartado, en cuanto a que una firma digital pueda comprobarse con una clave distinta de la verdadera clave pública del sujeto que ha firmado?
4. Si fueses un Magistrado con conocimientos básicos de informática y un perito en forensia te demuestra que la firma digital, que está como una prueba en entredicho en el juicio, puede comprobarse no sólo con la clave pública del sujeto que dice haber firmado el documento sino con muchos otros valores, ¿cómo crees que reaccionarías? ¿Dudarías del software? ¿Declararías la prueba como no válida?


APARTADO 4.5. TEST DE EVALUACION DE LA LECCION RSA04

En las siguientes 5 preguntas, elige la respuesta correcta.

1. Una clave RSA tendrá:

a) Como máximo 9 claves privadas parejas
b) Como mínimo 1 clave privada pareja
c) Más claves privadas parejas que claves públicas parejas

2. Una clave pública pareja permitiría:

a) Comprobar una firma digital con una clave distinta a la pública
b) Firmar un documento con esa clave pareja, distinta de la pública
c) Recuperar la clave de sesión en un intercambio de clave

3. Las posibles claves privadas parejas RSA en cuerpos de 2.048 bits se distribuyen:

a) En torno al valor del número F4 de Fermat
b) En torno al módulo de trabajo n
c) Uniformemente en todo el cuerpo n

4. Con respecto a las posibles claves privadas parejas de una clave RSA de 1.024 bits:

a) No significan ninguna amenaza
b) Habrá que tener cierta cautela
c) Deberíamos estar preocupados

5. Para minimizar la cantidad de claves parejas es recomendable:

a) Usar primos gemelos en p y q
b) Usar primos de al menos 512 bits para p y q
c) Usar primos seguros en p y q


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