Ir al contenido principal

Entradas

Mostrando entradas de mayo, 2017

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 xy2 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 (xy) ni (x + y) sean múlti…