Criptografía (LIII): ataque a RSA mediante factorización (IV)

En esta ocasión me referiré al método de factorización de Dixon, un algoritmo de propósito general.

Recordar que, tal y como comenté en un post anterior, mientras que en los algoritmos de propósito específico (Fermat, rho Pollard, p -1 Pollard,...) el tiempo de ejecución depende de las características propias de los dos factores primos (p y q) del módulo (n) a factorizar, en los de propósito general éste sólo depende del tamaño del módulo.

Antes que nada explico lo que he entendido sobre este método (espero no equivocarme mucho) y pongo un ejemplo con el número que vengo utilizando como módulo en los ejemplos de cifrado RSA.

Si no lo he entendido mal, la idea básica de este método es, dado un número n a factorizar, encontrar dos números x e y tales que x² º y² mod n, con lo que (x - y) (x + y) es un múltiplo de n, y, por consiguiente, tanto el mcd(x - y, n) como el mcd(x + y, n) nos entregarán un factor no trivial de n (distinto de 1 y n) siempre y cuando ni (x - y) ni (x + y) sean múltiplos de n.

Supongamos que queremos factorizar n, el método consiste en:

a) Tomar una base (B) de números primos consecutivos, empezando en 2, unión con -1, es decir, B = {-1, p₁, p₂, p₃,...}.

b) Después elegimos números enteros z_i tales que z_i² pueda factorizarse como el producto de potencias de elementos de la base (B) mod n, de tal forma que: z_i2 º (-1)^e1 x (p₁)^e2 x (p₂)^e3 x (p₃)^e4 x ... mod n.

c) Cuando encontremos varios números que satisfagan la condición anterior (w_j) buscamos un subconjunto de ellos en los que la suma de exponentes de cada elemento de la base (s_k) sea par, y eso nos llevará a la congruencia buscada: (w₁ x w₂ ...)2 º ((-1)^s1/2 x (p₁)^s2/2 x (p₂)^s3/2 x (p₃)^s4/2 x ...)2 mod n.

Es decir:
x2 º y2 mod n.

d) Con lo que tanto el mcd(x - y, n) como el mcd(x + y, n) es muy probable que nos entreguen un factor no trivial de n (distinto de 1 y n).

Ejemplo: sea n = 52.841.

a) Tomamos como Base: B = {-1, 2, 3, 5}.

b) Elegimos como números enteros cuyos cuadrados se factorizan como el producto de potencias de elementos de la base módulo n, los siguientes:

(229)² º (-1)¹ x (2)⁴ x (3)⁰ x (5)² mod 52.841
(514)² º (-1)¹ x (2)⁰ x (3)² x (5)⁰ mod 52.841

c) (229 x 514)² º (2² x 3 x 5)² mod 52.841

Lo que nos da: (12.024)² º (60)² mod 52.841

d) mcd(12.024 - 60, 52.841) = 997, y , por tanto, hemos conseguido factorizar el módulo: 52.841 = 997 x 53.

Pero en la práctica: ¿cómo se implementa este método? En un próximo post intentaré poner un algoritmo para ello, conforme a lo que he entendido, y aplicarlo a este mismo ejemplo. ¿Algún voluntario para incluirlo en forma de comentario?

Quizás también te interese: