Criptografía (XXXIX): RSA o por qué los números aleatorios son demasiado importantes para dejarlos en manos del azar

Decía en el primer post sobre RSA que utilizando este algoritmo el emisor cifra el mensaje con la clave pública del receptor y que el criptograma resultante sólo puede descifrarse utilizando la clave privada de este último. Esto es una de las primeras cosas que uno aprende al estudiar cómo funciona el cifrado y descifrado usando este algoritmo, pero: ¿es cierto?

Prescindiendo del ataque a RSA mediante cifrado cíclico, que, como vimos en este post, en teoría nos permitiría descifrar un mensaje concreto cifrándolo sucesivas veces con la clave pública del destinatario hasta volver a obtener el criptograma: ¿sería posible descifrar el criptograma utilizando una clave distinta de la clave privada correspondiente a la clave pública con la que se cifró? Pues he aprendido que sí, aunque esto parezca ir en contra de la seguridad de este algoritmo.

Veamos un ejemplo:

En el primer post al que he hecho referencia realicé el cifrado de un mensaje (m) con una clave pública (e, n) y su posterior descifrado con la clave privada correspondiente (d, n), de la siguiente manera:

m = 17.225

Clave pública (e, n): (7, 52.841) 

Cifrado: c = m^e mod n = 17.225⁷ mod 52.841 = 1.855

Clave privada (d, n): (7.399, 52.841)

Descifrado: m = c^d mod n = 1.855^7.399 mod 52.841 = 17.225

Vamos ahora a utilizar otras 3 claves diferentes a la clave privada en el cuerpo de cifra (n) para intentar descifrar el criptograma (c):

k1: (20.347, 52.841)
Descifrado: m = 1.855^20.347 mod 52.841 = 17.225

k2: (33.295, 52.841) 
m = 1.855^33.295 mod 52.841 = 17.225

k3: (46.243, 52.841) 
m = 1.855^46.243 mod 52.841 = 17.225

Como se observa, en los tres casos conseguimos descifrar el criptograma sin utilizar la clave privada del destinatario.

- ¿Por qué ocurre esto? Hay que tener en cuenta que, tal y como comentaba en el primer post, al generarse un par de claves, la clave privada se calcula como el inverso del exponente de la clave pública (e) en el cuerpo j(n) = (p - 1)(q - 1), siendo 'p' y 'q' los dos números primos aleatorios a partir de los cuales se genera el par de claves, y 'n' su producto. Como 'e' y j(n) son coprimos o primos relativos, es decir, mcd(e, j(n)) = 1, esto asegura que el exponente de la clave privada (d) existe, es decir, que 'e' tiene inverso módulo j(n) y, además, que éste (d) es el único inverso de 'e' en el cuerpo j(n).

Lo que ocurre es que como el cuerpo de cifra no es j(n) sino 'n' existirá al menos otro inverso de 'e' en el cuerpo de cifra 'n' con el que también se podrán descifrar los mensajes cifrados con la clave pública (e, n).

- ¿Puedo saber cuántas claves de este tipo existen al generar un par de claves?. Esto depende de los dos números primos aleatorios ('p' y 'q') empleados para generar el par de claves, y puede calcularse de la siguiente forma:

En nuestro caso:

- ¿Puedo saber cuáles son estas claves al generar un par de ellas?:

Calculamos: d₁ = inv(e, mcm(p-1, q-1)

Los exponentes de estas claves, incluido el de la clave privada (d), serán:

d_i = d₁ + (i-1) x mcm(p-1, q-1)

Donde: 1 < d_i < n

Por lo que las claves, incluida la clave privada, serán:

k_i: (d_i, n)

En nuestro caso:

d₁ = inv(7, mcm(52, 996)) = inv(7, 12.984) = 7.399

Por lo que los exponentes de estas claves. incluido el de la clave privada (d), serán:

d₁ = d₁ + (i-1) x mcm(p-1, q-1) = 7.399 + 0 x 12.948= 7.399

d₂ = d₁ + (i-1) x mcm(p-1, q-1) = 7.399 + 1 x 12.948 = 20.347

d₃ = d₁ + (i-1) x mcm(p-1, q-1) = 7.399 + 2 x 12.948 = 33.295

d₄ = d₁ + (i-1) x mcm(p-1, q-1) = 7.399 + 3 x 12.948 = 46.243

Por tanto, incluida la clave privada, las claves serán:

k₁: (7.399, 52.841)
k₂: (20.347, 52.841)
k₃: (33.295, 52.841)
k₄: (46.243, 52.841)

Es decir, además de la clave privada (7.399, 52.841), existen otras tres claves con las que se pueden descifrar los criptogramas cifrados con la clave pública (7, 52.841).

- ¿Al generarse un par de claves podrían existir muchas claves de este tipo que hagan vulnerables los criptogramas a una ataque de fuerza bruta?. Pues, en teoría, sí. Ya he dicho que el número de ellas depende de los número primos aleatorios que se empleen para generarlas.

Veamos que ocurre variando los números primos empleados para generar el par de claves de nuestro ejemplo, que eran p = 53 y q = 997 (en este caso, eligiendo '7' como exponente de la clave pública existen 3 claves de este tipo. En los casos que se indican a continuación también elegimos '7' como exponente de la clave pública):

1.- p = 53; q = 53

n = 2.809; clave pública: (7, 2.809); clave privada: (1.159, 2.809)

Aplicando las fórmulas indicadas anteriormente, calculamos que existen 53 claves de este tipo. La primera (15, 2.809), y todas ellas, cuyos exponentes se encuentran separados a lo largo del cuerpo de cifra por 52 (mcm(p-1, q-1)), serán: (15, 2.809), (67, 2.809), (119, 2.809), (171,2.809), (223,2.809),...   

2.- p = 997; q = 997

n = 994.009; clave pública: (7, 994.009); clave privada: (708.583, 994.009)

Existen 997 claves de este tipo: (427, 994.009), (1.423, 994.009), (2.419, 994.009),...

3.- p = 53 ; q = 1.171

n = 62.063; clave pública: (7, 62.063); clave privada: (17.383, 62.063)

Existen 26 claves de este tipo: (1.003, 62.063), (3.343, 62.063), (5.683, 62.063),...

4.- p = 53; q = 983

n = 52.099; clave pública: (7, 52.099); clave privada: (7.295, 52.099)

Existe sólo 1 clave de este tipo: (32.827, 52.099).

Como se ve, al menos yo, saco inicialmente las siguientes conclusiones:

1.- No parece una buena idea utilizar el mismo número primo para 'p' y 'q'.

2.- El número de claves de este tipo, tal y como comentaba, tiene una fuerte dependencia directa de la elección de los dos números primos aleatorios a partir de los cuales se genera el par de claves. 

- ¿Cómo puede evitarse que al generar un par de claves existan muchas claves de este tipo?

Parece ser, por lo que voy aprendiendo, que utilizando números primos fuertes o primos seguros en la generación del par de claves. Pero esto es algo que tengo que estudiar e intentar comprender antes de contarlo :). Si lo consigo escribiré otra entrada para compartirlo.

Por tanto, entiendo que es muy importante que los números primos 'p' y 'q' a partir de los cuales se genera el par de claves no sean predecibles, ya que en ellos descansa el secreto de las comunicaciones entre el emisor y el receptor, y la idea de seleccionarlos de forma aleatoria parece la mejor opción. No obstante, visto lo visto y por otros efectos no deseados que podrían producirse si se realiza una elección no adecuada de los mismos, la frase que oí en su día y que me hizo mucha gracia empieza a tener sentido para mí:

"Los números aleatorios son demasiado importantes para dejarlos en manos del azar"

Quizás también te interese: