Criptografía (XLI): ataque a RSA mediante módulo común

En anteriores posts de esta serie he hablado de algunos ataques teóricamente posibles al algoritmo de cifrado RSA (cifrado cíclico y paradoja del cumpleaños), pero que tal y como comenté son ineficientes cuando se utilizan números primos lo suficientemente grandes para generar el par de claves (pública y privada).

Además de los ya mencionados existen otros ataques posibles; y en este post trataré sobre uno de ellos: el ataque a RSA mediante módulo común.

La idea de este ataque consiste en explotar el hecho de que se utilice el mismo módulo (n) a la hora de generar pares de claves para diferentes usuarios (cada uno de ellos con su exponente publico y privado propios). En principio, esto no compromete la seguridad del algoritmo, pero deja la "puerta abierta" a que si se cifra el mismo mensaje para más de un usuario un criptoanalista que intercepte los criptogramas pueda hacerse con el mensaje en claro.

Veamos un ejemplo:

1.- Módulo común a los usuarios (n):  52.841.

2.- Clave pública de dos usuarios a los que se envía el mismo mensaje:

- Usuario 1 (e₁, n): (11, 52.841).
- Usuario 2 (e₂, n): (7, 52.841).

3.- Mensaje común a ambos usuarios (m): 16.708.

4.- Cifrado para cada uno de los dos destinatarios:

- El emisor utiliza la clave pública del Usuario 1: c₁ = m^e1 mod n = 16.708¹¹ mod 52.841 = 7.860.
- El emisor utiliza la clave pública del Usuario 2: c₂ = m^e2 mod n = 16.708⁷ mod 52.841 = 52.061.

Supongamos ahora que se interceptan estos dos criptogramas y el criptoanalista sabe que el mensaje en claro es el mismo en ambos casos. Lo único que debe hacer para obtenerlo, ya que conoce e₁, e₂, n, c₁ y c₂, es lo siguiente:

1.- Como e₁ y e₂ son primos entre sí (lo que ocurre en nuestro caso y es muy probable que en cualquier otro), existirán dos enteros (s, t) tales que:

e₁ s + e₂ t = mcd(e₁, e₂) = 1

2.- Se calculan s y t mediante el algoritmo de Euclides extendido, de la siguiente forma:

a) r₀ = e₁ = 11; r₁ = e₂ = 7; s₀ = 1; t₀ = 0; s₁ = 0; t₁ = 1

b) i = 1

c) Mientras r_i distinto de 0:

c.1) Dividir r_i-1 entre r_i para obtener el cociente q_i+1 y el resto r_i+1
c.2) s_i+1 = s_i-1 - q_i+1 s_i; t_i+1 = t_i-1 - q_i+1 t_i
c.3) i = i + 1

d) Cuando r_i = 0, el resultado buscado es r_i-1 = r₀ s_i-1 + r₁ t_i-1.

En nuestro caso:

3.- Y, finalmente, el criptoanalista obtiene el mensaje en claro realizando la siguiente operación (nótese que alguno de los dos valores obtenidos será necesariamente negativo. En nuestro caso: s = 2 y t = -3):

m = (c₁^s x inv(c₂, n)^-t) mod n
m = (7.860² x 23.101³) mod 52.841 = 16.708, que efectivamente, tal y como se puede comprobar más arriba, es el mensaje en claro.

Sin embargo, este tipo de ataque no es muy viable en la práctica a nada que se adopten unas mínimas precauciones en el uso de este algoritmo, ya que requiere que se intercepten criptogramas correspondientes a mensajes en claro idénticos para usuarios diferentes que compartan el mismo módulo, por lo que, por lo visto en éste y anteriores posts, y aunque hay otros tipos de ataques posibles, tras casi cuatro décadas desde su desarrollo, RSA parece gozar de una "salud" envidiable; a prueba de ruptura, salvo que alguien consiga dar con un algoritmo eficiente para hallar los dos factores primos de un número lo suficientemente grande, un incremento muy significativo de la potencia de cálculo de los ordenadores actuales y/o los avances que se logren en la computación cuántica, pero todo esto será, si es el caso, objeto de posts posteriores.

Quizás también te interese: