lunes, 23 de enero de 2017

Criptografía (XLIII): ataque a RSA mediante factorización (II)

Continúo con el pequeño repaso a algunos de los métodos de factorización más conocidos que inicie en el post anterior y que, en teoría, podrían emplearse para atacar al algoritmo de cifrado RSA.

Digo en teoría porque, como ya he venido insistiendo en esta serie de post, los métodos conocidos y que es posible implementar hasta la fecha no resuelven la factorización del módulo (n) en sus dos factores primos (p y q) en tiempo polinomial y, por tanto, son ineficientes para abordar este problema en un tiempo razonable cuando se trata de números lo suficientemente grandes (ya dije en el post anterior que actualmente se emplea un tamaño para el módulo de 2.048 bits).

En esta ocasión le toca el turno al método de factorización rho de Pollard.

Como siempre utilizaré el ejemplo que vengo usando en esta serie de posts (n = pq = 53 x 997 = 52.841).
En nuestro caso:
Como vemos, en tan sólo 6 iteraciones hemos conseguido factorizar el módulo (52.841) en sus dos factores primos (53 y 997); de forma significativamente más eficiente, en este caso, que con el método de Fermat al que me referí en el post anterior, pero, por lo que voy aprendiendo, no se puede afirmar rotundamente que un método sea más eficiente que otro, sino que esto depende del número concreto a factorizar.

Me pregunto: ¿cuál de estos dos métodos sería más eficiente en el ejemplo que puse en el post anterior en el que los dos factores primos estaban muy cercanos entre sí (n = pq = 991 x 997 = 988.027)?. Asunto que dejo como ejercicio para quien quiera resolverlo (como siempre se admiten conclusiones, etc. en forma de comentario a esta entrada).

En cualquier caso, comentar que se considera que el método de factorización rho de Pollard es eficiente para factorizar números compuestos con factores menores de 1012, lo que está muy por debajo de los utilizados actualmente por RSA.

En poteriores posts continuaré con este pequeño repaso a los métodos de factorización más conocidos.

domingo, 22 de enero de 2017

Criptografía (XLII): ataque a RSA mediante factorización (I)

Ya he dicho en posts anteriores que la fortaleza del cifrado RSA reside en el elevadísimo coste computacional al que tendrían que enfrentarse quienes pretendan atacar este algoritmo; y referido al caso concreto de la factorización del módulo (n) para hallar sus dos factores primos (p y q), en la enorme cantidad de cálculos a realizar para ello cuando se trata de números lo suficientemente grandes (actualmente se emplea para el módulo un tamaño de 2.048 bits).

Por tanto, se trata de un problema perfectamente resoluble desde un punto de vista matemático, pero inabordable actualmente por la ingente cantidad de tiempo y recursos necesarios.

Comienzo con este post un pequeño repaso a algunos de los métodos de factorización más conocidos para hacernos una idea del esfuerzo que esto conlleva. Para ello, intentaré factorizar mediante estos métodos el módulo del ejemplo que vengo utilizando en esta serie de posts (n = pq = 53 x 997 = 52.841).

- Método de factorización de Fermat:
En nuestro caso:
Aún con un número tan pequeño como módulo nos ha costado realizar 296 iteraciones para conseguir obtener sus dos factores primos, lo que puede parecer que no es mucho, pero este proceso presenta un carácter exponencial en función del tamaño de la entrada (el número a factorizar).

Sin embargo, cabe indicar que este método es muy eficiente cuando los dos factores están cercanos entre sí, o, lo que es lo mismo, cuando están próximos a la raíz cuadrada de n, ya que la factorización se resuelve en muy pocos pasos. Comprobémoslo con el siguiente ejemplo:
Como se observa los dos factores son números primos consecutivos y su factorización mediante este método se resuelve en un único paso, razón por la que es muy recomendable que en RSA los números primos aleatorios (p y q) elegidos como factores del módulo (n) se encuentren separado entre sí una cierta distancia. Ya decía yo en este post que "los números aleatorios son demasiado importantes para dejarlos en manos de azar" :).

No obstante, teniendo en cuenta esto último, que p y q se encuentren separados entre sí una cierta distancia, este método no es eficiente para factorizar el módulo en sus dos factores primos en un tiempo razonable cuando se trata de números lo suficientemente grandes, como digo actualmente se emplean números de 2.048 bits para el módulo (n).

En posteriores posts continuaré con el repaso de otros métodos de factorización, pero ya adelanto que: aunque hay algunos más eficientes que otros ante determinadas circunstancias, se van produciendo mejoras a los ya existentes y van surgiendo otros nuevos, de momento no existe un algoritmo que resuelva esta factorización en tiempo polinomial; lo que constituye el "Santo Grial" de los criptoanalistas para conseguir "romper" el cifrado basado en el algoritmo RSA.

domingo, 15 de enero de 2017

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 (e1, n): (11, 52.841).
- Usuario 2 (e2, 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: c1 = me1 mod n = 16.70811 mod 52.841 = 7.860.
- El emisor utiliza la clave pública del Usuario 2: c2 = me2 mod n = 16.7087 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 e1e2, n, c1 y c2, es lo siguiente:

1.- Como e1 y e2 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:

e1 s + e2 t = mcd(e1e2) = 1

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

a) r0 = e1 = 11; r1 = e2 = 7; s0 = 1; t0 = 0; s1 = 0; t1 = 1

b) i = 1

c) Mientras ri distinto de 0:

c.1) Dividir ri-1 entre ri para obtener el cociente qi+1 y el resto ri+1
c.2) si+1 = si-1 - qi+1 si; ti+1 = ti-1 - qi+1 ti
c.3) i = i + 1

d) Cuando ri = 0, el resultado buscado es ri-1 = r0 si-1 + r1 ti-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 = (c1s x inv(c2n)-t) mod n
m = (7.8602 x 23.1013) 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.

jueves, 29 de diciembre de 2016

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 = me mod n = 17.2257 mod 52.841 = 1.855.
Descifrado (el receptor utiliza su clave privada): m = cd mod n = 1.8557.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:

ci = mi mod n; cj = mj 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

miércoles, 28 de diciembre de 2016

Gimnasia mental (XXIX): probabilidad de que me toque el Gordo del Niño

Como complemento a este post, en el que me preguntaba: ¿Cuál es la probabilidad de que me toque el Gordo de Navidad?, en éste me pregunto:


"¿Qué probabilidad hay de que me toque el Gordo de la lotería del Niño: menor, mayor o igual que en la lotería de Navidad?".

Si no estoy equivocado, según tengo entendido (por favor, si no es así que alguien me corrija):

- En la lotería de Navidad hay un bombo con 100.000 bolas con los números (del 0 al 99.999) y en otro están las bolas con los premios; de tal forma que se van extrayendo del primero las bolas con los números agraciados y del segundo las bolas con el premio que corresponde a cada uno de los anteriores.

- En la lotería de Niño se utiliza el sistema de bombos múltiples, es decir, hay cinco bombos con 10 bolas cada uno (del 0 al 9), un bombo para cada uno de los cinco dígitos posibles (decena de millar, unidad de millar, centena, decena y unidad, respectivamente) que podrían formar los 100.000 números posibles (del 0 al 99.999); de manera que tras la extracción de una bola de cada uno de los cinco bombos se obtiene el número agraciado con el premio programado (los premios van saliendo de forma ordenada ascendente por cuantía) y después se reponen las bolas extraídas en sus respectivos bombos.

También, tal y como tengo entendido, en el sorteo de Navidad resultan premiados menos números que en el del Niño.

La pregunta en concreto es, suponiendo que juego un único décimo en cada sorteo:

¿Qué probabilidad existe de que me toque el Gordo en cada uno de ambos sorteos?:

a) Mayor en la Lotería de Navidad que en la del Niño.
b) Mayor en la del Niño que en la de Navidad.
c) La misma en ambos sorteos.