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  x 2 º y 2 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