Criptografía (XL): ataque a RSA mediante la paradoja del cumpleaños

Decía en un post anterior de esta serie que existen algunos métodos para intentar "romper" el cifrado RSA sin necesidad de factorizar el módulo para hallar sus dos factores primos.

Como comenté en ese post, el ataque utilizando el cifrado cíclico nos podría permitir "romper" el secreto que se pretende guardar (en teoría se puede obtener el mensaje en claro), aunque no obtendríamos la clave privada del receptor.

Pero, ¿existen otros métodos de criptoanálisis al cifrado RSA que teniendo en cuenta sólo información pública del destinatario (la clave pública con la que se cifran los mensajes en claro: el exponente y el módulo) podrían revelarnos su clave privada?. La respuesta es, otra vez y en teoría, sí, y, además, ni siquiera haría falta interceptar un criptograma, como sí que es necesario en el caso del ataque mediante cifrado cíclico. Éste es el caso de un ataque basado en la paradoja del cumpleaños.

Veamos un ataque de este tipo con el ejemplo que vengo utilizando en esta serie de posts:

Clave pública del receptor (e, n): (7, 52.841)
Clave privada del receptor (d, n): (7.399, 52.841)
mensaje (m) = 17.225

Cifrado (el emisor utiliza la clave pública del receptor): c = m^e mod n = 17.225⁷ mod 52.841 = 1.855.
Descifrado (el receptor utiliza su clave privada): m = c^d mod n = 1.855^7.399 mod 52.841 = 17.225.

Tal y como he comentado, para realizar el ataque partimos únicamente de la clave pública del receptor (e, n), que como su propio nombre indica es información pública.

Conocido el módulo 'n' (52.841) dividimos el espacio del cuerpo de cifra en dos mitades, de la siguiente manera:

Escogemos un número cualquiera (m). Por ejemplo: 4.683.

Y ahora vamos realizando simultáneamente las dos siguientes operaciones:

c_i = mⁱ mod n; c_j = m^j mod n

hasta encontrar una colisión, es decir, que uno de los valores obtenidos en la primera mitad del espacio del cuerpo de cifra coincida con uno de los obtenidos en la segunda mitad, o viceversa. Si esto ocurre el ataque puede haber prosperado de forma que a partir de los valores de i y j sea posible obtener la clave privada del destinatario (d, n) o una clave que siendo diferente a ésta nos permita descifrar los criptogramas (ver este post).

En nuestro ejemplo:

Como se observa, para i = 524 y j = 26.420 se produce una colisión, por lo que el ataque podría haber prosperado en tan sólo 524 iteraciones (2 cifrados en cada una de ellas) en un cuerpo de cifra de tamaño 52.841. Comprobémoslo:

- Calculamos: x = |i - j| / mcd(e, |i - j|) = |524 - 26.420| / mcd(7, |524 - 26.420|) = 25.896 / mcd(7, 25.896) = 25.896.

- El exponente de la clave podría ser: inv(e, x) = inv(7, 25.896) = 7.399, y, tal y como se puede ver al inicio de este ejemplo, efectivamente hemos obtenido el exponente (d) de la clave privada del receptor, por lo que esta última es (7.399, 52.841).

¿Hemos tenido mucha suerte?. Parece que sí, ya que a simple vista no parece muy probable que se produzca una colisión en la iteración 524 (2 cifrados en cada una de ellas) en un cuerpo de cifra de tamaño mucho mayor. Sin embargo, conforme a la paradoja del cumpleaños (ver este post donde la explico), hacen falta muchas menos iteraciones de las que intuitivamente puede parecer para que la probabilidad de que se produzca una colisión sea muy alta.

De nuevo, como en el caso de ataque mediante cifrado cíclico (ver este post), aunque en teoría es posible, este tipo de ataque se convierte en una tarea inabordable en un tiempo razonable, por mucha potencia de cálculo de la que se disponga con los ordenadores actuales, cuando se utilizan números lo suficientemente grandes para generar las claves.

Quizás también te interese: