Factorización en tiempo polinómico!?

  
Claus P. Schnorr ha presentado en el Eurocrypt 2009 "Average Time Fast SVP and CVP Algorithms: Factoring Integers in Polynomial Time".

Habría que ver el impacto que puede tener este documento en la criptografía de clave pública. Pero si es correcto, podría representar el fin de RSA.

Se ha iniciado un hilo de discusión en sci.crypt.research.

  

Hugo Scolnik: Avances en la Factorización Entera

El pasado 3 de diciembre se celebró el II Día Internacional de la Seguridad en la Información (DISI 2007). En el, Hugo Scolnik presentó un nuevo algoritmo de factorización, que aunque está por terminar, no tiene mala pinta.

A continuación dejo los enlaces (Criptored) a la presentación y el vídeo de la conferencia:

• Presentación PDF.
  

• Vídeo principal.
  
• Vídeo parte 1.
• Vídeo parte 2.
• Vídeo parte 3.
• Vídeo parte 4.
• Vídeo parte 5.
• Vídeo parte 6.

Estos archivos pueden descomprimirse en Línux con el siguiente comando:

$ cat *.z* > video.zip && unzip video.zip


En el foro de Kriptopolis, alguien que firmaba como "Hugo Scolnik" ponía un ejemplo sencillo de factorización:

Enviado por anónimo el 4. Enero 2008 - 8:42.

Pues ahi va un ejemplo pequeño para ilustrar el tema
Sea n = 507527
Los targets únicos son (23 en total):
(1,0,3) , (1,0,4), (4,1,5),....,(649,576,720)
Esto significa que x^2 = 1+3t(1) = 1+4t(2)=...= 649+720t(23)
con t(23) = 88 se consigue la soluciòn
Con respecto a y^2 tenemos que puede escribirse como 576+720u(23) con u(23) = 793
Obviamente con n grande es impracticable buscar los valores de t o de u.
Ahora, (n + 649 -576)/720 = 705 y algunos targets ùnicos de 705 son
(0,1,4) , (0,1,8), (0,1,16)
Llamaremos (a1,b1,c1) al target ùnico elegido del primer nivel, o sea (649,576,720) y
(a2,b2,c2) al del segundo nivel
Si usamos el primero con la fòrmula x^2 =a1+c1a2+c1c2t = 649+2880t correcto con t = 22
Si usamos el segundo obtenemos x^2 = 649+5760t correcto con t = 11
Pero el tercero da x^2= 649+11520t que es FALSO (deberìa dar x^2 = 6409+11520t)
¿Còmo corregir 649 ? Habrìa que sumarle deltax2 = 5760 = 8c1 (siempre es un mùltiplo de c1)
Para y^2 obtenemos y^2= b1+c1b2+c1c2u
En el primer caso y^2 = 1296+2880u correcto con u = 198
En el segundo caso y^2 = 1296+5760u correcto con u = 99
El tercero falla pues da y^2 = 1296+11520u y deberìa ser 7056+11520u
La correcciòn es deltay2 = 5760 que es igual a deltax2
Varios de los teoremas que mostrè ràpidamente tienen que ver con las correcciones, su relaciòn con las ecuaciones
diofánticas, etc. Casos muy interesantes son los simètricos, donde aparecen en el nivel k > 1 targets ùnicos
idènticos a los del primer nivel (al parecer siempre existen pero todavìa no nos dedicamos a demostrarlo porque
hay otras prioridades). Para ellos se pueden demostrar varios resultados muy interesantes, y ahora los estoy
usando para la exploraciòn de las ramas provenientes de las posibles elecciones de targets.
Cordialmente
Hugo Scolnik

Factorización IV: El Método de Curva Elíptica

El siguiente artículo es el cuarto de una serie dedicada a la factorización de números enteros. Hasta ahora se han visto los algoritmos básicos de factorización como Pollard P-1, que aunque pueden parecer rápidos, tienen complejidad exponencial, lo que los incapacita para factorizar números relativamente grandes. También se han introducido algunos de los conceptos necesarios para profundizar en el tema que nos permitirán, en este artículo y en los siguientes, estudiar los tres algoritmos más rápidos de factorización. Estos son el Método de Curva Elíptica (ECM), La Criba Cuadrática (QS) y la Criba en el Campo de Números (NFS), los tres de complejidad subexponencial. Empezaremos por el Método de Curva Elíptica.

En el artículo Criptografía de Curva Elíptica dimos una introducción a este peculiar tipo de curvas y su aplicación a la criptografía. A continuación iremos un poco más lejos y veremos como aprovechar esta herramienta matemática para factorizar números enteros grandes.

Para entender el siguiente artículo es necesario disponer de unos conocimientos básicos de curvas elípticas. En caso contrario, es recomendable leer primero el artículo mencionado anterioremente.


El Teorema de Lagrange:

Si aplicamos el Teorema de Lagrange a las curvas elípticas no encontramos con algo interesante que nos conducizará al método de factorización mediante curvas elípticas.

Si P es un punto en una curva elíptica E, entonces el orden de P dividirá el orden de E.

Recordemos que el orden de E, representado como #E, corresponde al número de puntos que hay en una curva E. Mientras que el orden de P, corresponde al valor k más pequeño (diferente de O) tal que kP = O.


Imaginemos que queremos factorizar un número N. Si encontramos una curva E definida sobre N, cuyo orden sea B-smooth, para un valor de B suficientemente pequeño, nos encontraremos con que B!P = O.

Esto ocurre debido a que #E es B-smooth y el orden de P debe ser un divisor de #E, tal y como nos indica el Teorema de Lagrange.


Factorización:

Encontrar un valor k tal que kP=O, en una curva mod N, es equivalente a encontrar un factor de N.

Esto ocurre por que durante el proceso de cálculo de kP se realizan operaciones que necesitan que cierto número d tenga inversa d^(-1). Para que d sea invertible debe cumplirse que el máximo común divisor entre d i el módulo sea igual a 1.

Pero ¿qué ocurre si d no tiene inversa? pues que el máximo común divisor entre d y el módulo N es diferente de 1. Con lo que tenemos un factor de N!


Imaginemos que queremos factorizar 4453. En este caso buscaríamos curvas aleatorias hasta encontrar una cuyo orden fuese B-smooth. Por ejemplo y²=x³+10x-2 mod 4453.

Ahora calcularíamos, kP para un valor pequeño de K. Empezemos por 2P para, por ejemplo P=(1,3).

(3x²+10) / 2y = 13 / 6 mod 4453 (derivada)

Para calcular 13/6 necesitamos calcular 6^(-1). Dado que MCD(6, 4452) podemos hacerlo: 6^(-1) = 3711, con lo que obtenemos:

13 / 6 = 3713 mod 4453
x = 3713²-2 = 4332
y = -3713(x-1)-3 = 3230

Para calcular 3P hacemos 2P + P:

(3230-3) / (4332-1) = 3227/4331.

Igual que en el cálculo anterior, para poder calcular 3227/4331 es necesario que 4331 tenga inversa, es decir, que MCD(4331, 4453) sea 1. Pero si realizamos el cálculo vemos que MCD(4331, 4453)=61. Con lo que hemos encontrado un factor de N.



Complejidad:

El método de factorización mediante curvas elípticas és muy rápido. De hecho, cuando deseamos factorizar números enteros grandes i sabemos que undo de los factores es mucho menor que el otro, este método es el más rápido.

Veamos a continuación por que és tan rápido.

El teorema de Hasse nos dice que el orden #E satisface la siguiente ecuación:

p+1-2 sqr(p) < #E < p+1-2 sqr(p)

Esto nos da una cierta idea del intervalo en el que puede moverse el valor #E. De esta manera sabemos que al generar una curva aleatoria, estamos obteniendo un valor entre este rango, de manera que si es B-smooth, conseguiremos factorizar N.

El número estimado de operaciones que necesitaremos realizar para encontrar una curva B-smooth es el siguiente:

exp(sqr(2) + O(1) + sqr(lnp ln lnp)

Como vemos, el número de operaciones necesarias es subexponencial, esto proviene del hecho de que la complejidad de encontrar números smooth es también subexponencial. Lo mismo ocurre con los algoritmos QS y NFS.



Software:

Actualmente la implementación libre más rápida de ECM es GMP-ECM, disponible en:

http://www.komite.net/laurent/soft/ecm/



Referencias:
- Elliptic Curves, Number Theory and Cryptography. Lawrence C. Washington.
- Prime Numbers, A Computational Perspective. Crandall & Pomerance.

Factorización III: P-1 de Pollard

Continuamos la serie de artículos sobre factorización con un algoritmo muy sencillo conocido como P-1 de Pollard.

El algoritmo de factorización P-1 de Pollard parte de la idea de smoothness o suavidad. Un número se considera B-smooth cuando todos sus factores son más pequeños que B. Esta idea, puede ser usada con éxito como herramienta de factorización, usando como base el Teorema Pequeño de Fermat:

b^p = b mod p
b^(p-1) = 1 mod p

A partir de la formula anterior deducimos que b^(p-1) - 1 es múltiplo de p. De manera que si disponemos de un número n=pq el cual deseamos factorizar , podremos hacerlo si somos capaces de calcular b^(p-1).
Inicialmente, esto puede parecer complicado, dado que no conocemos p. Pero supongamos que p-1 es B-smooth, para un valor de B bastante pequeño. Esto significaría que podemos calcular un valor M que contenga todos los factores de p-1, por ejemplo, calculando B!. Y si p-1 es un divisor de M, podemos aplicar el Teorema Pequeño de Fermat de la siguiente manera:

b^M = 1 mod p

Lo que nos llevarà a obtener un factor de n calculando el Máximo Común Divisor entre b^M-1 y n.

MCD(b^M-1, n)

Para finalizar, adjunto un programa en C y un ejemplo de su uso.

$ gcc pollard_pm1.c -lgmp -o pollard_pm1
$ ./a.out 97231944203 10
Factor = 888799
Factor = 109397

/* Pollard P-1 */
#include <stdio.h>
#include <gmp.h>


int main(int argc, char *argv[])
{
mpz_t n, a, GCD, tmp, k;
unsigned long int b;
gmp_randstate_t state;

if(argc!=3)
{
printf("Usage: %s [n] [B]\n", argv[0]);
return 0;
}

mpz_init(n);
mpz_init(tmp);
mpz_init(a);
mpz_init(GCD);
mpz_init(k);

mpz_set_str(n, argv[1], 10);
b = atof(argv[2]);

if(mpz_perfect_power_p(n) != 0)
{
mpz_sqrt(tmp, n);
gmp_printf("factor: %Zd\n", tmp);
return 0;
}
mpz_sub_ui(tmp, n, 1);
mpz_fac_ui(k, b);

gmp_randinit_default(state);

while(1)
{
mpz_sub_ui(tmp, n, 1);
mpz_urandomm(a, state, tmp);

if (mpz_cmp_ui(a, 1) <= 0)
mpz_set_ui(a, 2);

mpz_powm(tmp, a, k, n);
mpz_sub_ui(tmp, tmp, 1);
mpz_abs(tmp, tmp);
mpz_gcd(GCD, tmp, n);

if (mpz_cmp_ui(GCD, 1) > 0)
{
if (mpz_probab_prime_p(GCD, 10) > 0)
{
gmp_printf("Factor = %Zd\n", GCD);
mpz_div(n, n, GCD);
}
}
if (mpz_cmp_ui(n, 1) == 0)
{
mpz_clear(a);
mpz_clear(GCD);
mpz_clear(tmp);
mpz_clear(n);
mpz_clear(k);
return 0;
}

if (mpz_probab_prime_p(n, 10) > 0)
{
gmp_printf("Factor = %Zd\n", n);
mpz_clear(a);
mpz_clear(GCD);
mpz_clear(tmp);
mpz_clear(n);
mpz_clear(k);
return 0;
}
}

return 0;
}

Factorización II: Rho de Pollard

Continuando con la serie de artículos sobre factorización, hoy veremos el método Rho de Pollard. Un instructivo algoritmo que permite factorizar números bastante más grandes que los que podríamos factorizar mediante divisiones sucesivas de números primos o aplicando directamente el método de Fermat, tal y como vimos en "Factorización I: Introducción".

A lo largo de este artículo (y de los siguientes) se usará la operación mod. Esta operación representa el resto de una división entera. Por ejemplo 6 mod 5 =1 pues si dividimos seis entre cinco la division no es exacta, dado que tiene resto 1. Otros ejemplos pueden ser: 101 mod 99 = 2, 4^2 mod 15=1 o 33² mod 989 = 10².

Ahora supongamos que tenemos la ecuación F(x)=x² mod n. Si aplicamos esta ecuación para diferentes valores de x queda claro que el resultado siempre será menor que n. Por lo tanto, si aplicamos la ecuación para diferentes valores de x es lógico pensar en que en algun momento los resultados empezarán a repetirse, pues son finitos!

Veamos un ejemplo para n=323, empezando por ejemplo con x=2.

F(2) = 2² mod 323 = 4
F(4) = 4² mod 323 = 16
F(16) = 16² mod 323 = 256
F(256) = 256² mod 323 = 290
F(290) = 290² mod 323 = 120
F(120) = 120² mod 323 = 188
F(188) = 188² mod 323 = 137
F(137) = 137² mod 323 = 35
F(35) = 35² mod 323 = 256
F(256) = 16² mod 323 = 290
F(290) = 290² mod 323 = 120

Como se ve marcado en rojo, a partir de F(35) los resultados empiezan a repetirse, entrando en un ciclo.

Si representamos en un dibujo los resultados obtenidos vemos que su forma es similar al de la letra griega rho. Lo que da nombre al algoritmo.



El algoritmo Rho de Pollard permite encontrar ciclos cuando se trabaja con grupos donde los elementos son finitos. De manera que lo único que hemos hecho hasta ahora es encontrar un ciclo en un campo de números finitos con n=323. Pero, ¿Cómo aplicar esto para factorizar?

Si nos fijamos bien en la Rho dibujada vemos un hecho interesante producido al cerrar el ciclo. Llegamos al número 256 tanto a partir de 16² como a partir de 35². Este hecho, conocido como colisión, nos permite ver que 35²=16² mod 323. Lo que se conoce como congruencia y significa que 35² mod 323 = 16². Así pues, de forma similar a como vimos en el método de Fermat encontraremos un factor p mediante 35-16=19.

Resumiendo, el algoritmo Rho de Pollard nor permitirá encontrar colisiones, que a su vez nos permitiran encontrar un factor de n.

Para aplicar el método Rho de Pollard tal y como lo hemos visto, es necesario almacenar todos los elementos y compararlos con los elementos nuevos que se van generando. Esto es muy costoso tanto en tiempo como en espacio. Afortunadamente, existe una variación conocida como método de Floyd para encontrar ciclos, que permite encontrar una colisición sin almacenar apenas datos. Este método consiste en mantener dos valores. El primero recorrera en cada paso un elemento de la Rho, el segundo recorrerá dos. El tiempo estimado en el que ambos se encontrarán de nuevo, formando una colisión, es en el peor de los casos la raiz de n.

Algoritmo:

1. Elegir un entero aleatorio a entre 1 y n-3.
2. Elegir un entero aleatorio s entre 0 y n-1.
3. Inicializar U=V=s;
4. Calcular U=F(U), V=F(F(V)));
5. Si MCD(U-V, n) = 1, volver al punto 4.
6. Si MCD(U-V, n) = n, volver al punto 1.
7. MCD(U-V, n) es un factor de n.

NOTA: MCD=Máximo Común Divisor.



Hemos visto que el tiempo estimado para factorizar un número es de raiz de n en el peor de los casos. Pero existe una manera de mejorar considerablemente el tiempo de resolución del algoritmo cuando se dispone de cierta información sobre uno de los factores de n.

Se estima que usando F(x)=x^(2k) +a mod n, el número de iteraciones necesarias para encontrar un factor de n es de c*RAIZ(p)/RAIZ(MCD(p-1,2K)-1).
Es decir, quanto más factores comunes existan entre p-1 y 2k, menor será el número de iteraciones necesario para encontrar p.
Si no sabemos que factores puede tener p-1 puede ser útil calcular el factorial de un número B y usarlo como k: k=B!. Cuanto más grande sea B menos operaciones seran necesarias para encontrar el factor. Pero tampoco se puede abusar del tamaño de B, pues para valores demasiado grandes el tiempo por iteración será muy elevado.


Veamos un ejemplo usando el programa rho_2k.cpp que pego al final:

$ g++ -lgmpxx rho_2k.cpp -o rho_2k
$ ./rho_2k [n number] [B bound]

El primer parámetro es el número que queremos factorizar, el segundo el número B que usaremos para calcular k mediante su factorial.

Intentemos factorizar el número de 32 bits: 2930992620606930277. Primero con B=1, que equivale a k=1:

$ ./rho_2k 2930992620606930277 1
factor: 1065951967
count: 19188

Hemos necesitado 19.188 operaciones. Intentemoslo ahora con B=10:

./rho_2k 2930992620606930277 10
factor: 2749647931
count: 9516

El número de iteraciones baja. Con B=100:

./rho_2k 2930992620606930277 100
factor: 2749647931
count: 50

Como podemos observar la mejora es tangible. Finalmente con B=1000:

./rho_2k 2930992620606930277 700
factor: 2749647931
count: 1

En una sola operacion!


Hemos visto que cuantos más factores coinciden entre p-1 i k mejores son los resultados. Hasta el punto de que si todos los factores de p-1 estan en k, se resuelve la factorización en una sola operación. Sin embargo B no puede incrementarse indefinicademente, pues el factorial crece muy rápido, y no tardaremos en llegar a valores que relentizarán demasiado las operaciones.


Finalmente dejo una copia del programa usado:

#include <gmpxx.h>
#include <iostream>

// F(x) = x^2k + a mod n
mpz_class F(mpz_class &x, mpz_class &k, mpz_class &a, mpz_class &n)
{
mpz_class res;
mpz_class pow;

pow = 2*k;
mpz_powm(res.get_mpz_t(), x.get_mpz_t(), pow.get_mpz_t(), n.get_mpz_t());
res += a;

return res;
}

int main(int argc, char *argv[])
{
using namespace std;

mpz_class n;
mpz_class U;
mpz_class V;
mpz_class s;
mpz_class g;
mpz_class k;
mpz_class a;
mpz_class count;

if (argc!=3)
{
cout << argv[0] << " [n number]  [B bound]" << endl;
return 0;
}

n = argv[1];
int B = atoi(argv[2]);
count = 0;
s = 2;
U = s;
V = s;
g = 1;

mpz_fac_ui(k.get_mpz_t(), B);
a = 3;

while(g==1)
{
U = F(U, k, a, n);
V = F(V, k, a, n);
V = F(V, k, a, n);

g = U-V;
mpz_gcd(g.get_mpz_t(), g.get_mpz_t(), n.get_mpz_t());

if(g==n)
{
cout << "bad seed" << endl;
U++;
V++;
g=1;
}
count ++;
}

cout << endl << "factor: " << g << endl;
cout << "count: " << count << endl;

return 0;
}

Referencias:
- Prime Numbers, A Computational Perspective. Crandall & Pomerance. Ed Springer.

Factorización I: Introducción

Ya hablamos de la importancia que tiene la factorización en criptografía en "Rompiendo claves RSA". En esta serie de artículos se hará un repaso a los algoritmos usados para factorizar números grandes, empezando por los algoritmos más básicos hasta llegar a los más actuales y modernos sistemas, que permiten factorizar números de más de 150 dígitos decimales.

Como veremos, existen decenas de algoritmos de factorización, pero los más destacados por su mayor velocidad (o menor complejidad) son:

- Quadratic Sive (QS): El algoritmo más rápido para factorizar números grandes de propósito general menores de 110 dígitos decimales (aproximadamente).

- Number Field Sieve (NFS): El algoritmo más rápido para factorizar números grandes de propósito general mayores de 110 dígitos decimales (aproximadamente).

- Elliptic Curve Method (ECM): El algoritmo más rápido para factorizar números grandes cuando uno de los factores es relativamente pequeño.


Estos tres algoritmos tienen un complejidad subexponencial que es lo más rápido que se ha conseguido llegar en el campo de la factorización. Si se encontrase un algoritmo de complejidad polinómica, podríamos decir que el problema de la factorización queda resuelto y dejaría de poder utilizarse en criptografía. Esto significaría, entre otras cosas, el fin de algoritmos como RSA.

Los algoritmos QS i NFS se basan en una vieja estratégia atribuída al genial matemático Pierre de Fermat. La vemos a continuación:
Supongamos que disponemos de un número n del cual queremos obtener su representación como multiplicación de dos factores, es decir n=pq. Ecuación que también podríamos representar como n=(x+y)(x-y).

Si encontramos dos números enteros positivos que cumlan la ecuación de manera que x-y sea mayor que 1, diremos que hemos encontrado un factor no trivial de n, quedando el problema resuelto. Pero para buscar a y b cambiaremos el enfoque del problema.

Sabemos que (x+y)(x-y)=x²-y² , lo que nos permite un cambio de estrategia importante, pues ya no tenemos que buscar directamente factores de n, sino parejas de cuadrados cuya diferencia sea n.
Veamos un ejemplo para n=989. Si realizamos una búsqueda de cuadrados empezando por la raiz entera de 989, es decir 31, tenemos que 32²-989=35 no es cuadrado, continuamos, 33³-989=100 y bingo! Pues vemos que 33²-10²=989. Partiendo de la fórmula anterior tenemos que el factor p corresponde a p=33-10=23 y el factor q corresponde a q=33+10=43. Quedando n factorizado como 989=23*43.

El método utilizado puede parecer muy rápido, pues hemos factorizado el 989 en solo dos operaciones. Si nos hubiesemos dedicado a probar con todos los números primos menores que 31 habríamos necesitado 9 operaciones! (2, 3, 5, 7, 11, 13, 17, 19, 23). Pero lo cierto es que cuando tratamos de factorizar números más grandes vemos que el enfoque no es el adecuado, pues resulta extremadamente lento.

Lo que debemos tener en cuenta de la idea de Fermat es que proporciona una estrategia diferente para atacar el problema, de manera que pasamos de buscar factores de n a buscar diferencias de cuadrados. Como veremos en próximos artículos, esta estratégia se usa con éxito en los algoritmos QS y NFS.

Rompiendo claves RSA

Aunque hoy por hoy no es posible romper una clave RSA de más de 1024 bits ni con miles de computadoras trabajando en paralelo, los algoritmos de factorización no dejan de mejorar. A continuación voy a explicar cómo romper una clave RSA relativamente pequeña usando uno de estos algoritmos.

Primero crearemos un entorno de pruebas con el que cifrar y descifrar. Usaremos la herramienta openssl.

Generamos un par de claves RSA de 256 bits.
$ openssl genrsa -out privkey.pem 256

# Extraemos la clave publica
$ openssl rsa -in privkey.pem -pubout -out pubkey.pem
$ cat pubkey.pem
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAK1/eaHlW68OrwaeT/X6V9mx4pkvE8mW
QScrI2z8UVBhAgMBAAE=
-----END PUBLIC KEY-----

# Algo que cifrar
$ echo ";)" > msg.txt

# Ciframos (con la clave publica)
$ openssl rsautl -encrypt -pubin -inkey pubkey.pem -in msg.txt -out msg.enc

# Desciframos (con la clave privada)
$ openssl rsautl -decrypt -inkey privkey.pem -in msg.enc
;)

Ya tenemos nuestro entorno de pruebas con un par de claves que nos pemiten cifrar y descifrar mensajes. Como RSA es un criptosistema asimétrico se supone que deberíamos distribuir la clave pública, mientras que guardaríamos con recelo la clave privada.

Nuetro objetivo será obtener la clave privada partiendo únicamente de la clave pública. Una vez obtenida descifraremos el mensaje.

RSA basa su fuerza en el problema de factorización de números grandes. Un problema matemático para el que no se conoce un algoritmo que lo resuelva de forma eficiente. Entre los algoritmos más rápidos destacan QS y NFS. Ambos implementados por la genial herramienta msieve (Instalar).

Lo primero que necesitamos es el módulo n y el exponete de cifrado. Los dos se pueden obtener facilmente a partir de la clave pública.

$ openssl rsa -in pubkey.pem -pubin -text -modulus
Modulus (256 bit):
00:ad:7f:79:a1:e5:5b:af:0e:af:06:9e:4f:f5:fa:
57:d9:b1:e2:99:2f:13:c9:96:41:27:2b:23:6c:fc:
51:50:61
Exponent: 65537 (0x10001)
Modulus=AD7F79A1E55BAF0EAF069E4FF5FA57D9B1E2992F13C99641272B236CFC515061
writing RSA key
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAK1/eaHlW68OrwaeT/X6V9mx4pkvE8mW
QScrI2z8UVBhAgMBAAE=
-----END PUBLIC KEY-----

Observemos que el módulo está en hexadecimal. Para continuar será necesario pasarlo a decimal. A continuación, lo factorizamos con msieve:

$ msieve -v 78475351858145546395020889284272950035474797715255953445997961959441362407521

Obteniendo como resultado los factores:
262908038773065572592762474383232893183
298489738938272421513567914663780208287

Únicamente nos quedará recuperar la clave original a partir de los datos obtenidos. Usaremos el programa get_priv_key.

$ ./get_priv_key 262908038773065572592762474383232893183 298489738938272421513567914663780208287 \ 

65537
-----BEGIN RSA PRIVATE KEY-----
MIGrAgEAAiEArX95oeVbrw6vBp5P9fpX2bHimS8TyZZBJysjbPxRUGECAwEAAQIg
L/uaWxEAq0iHVXBBMwk6dDC0mJubL4dVLLdiaA01NPUCEQDgjwhah0l/hqX+D3Xh
3s6fAhEAxco/F01rh+Uzf+LV2K6A/wIRANOCxcqHPRpKGFV5+H3cYF8CEEN8O0Sf
JNZsTMMQyXgyKk8CEQCRfomgf/LY71boM54D8a5C
-----END RSA PRIVATE KEY-----

Con la nueva clave privada ya podemos acceder al mensaje cifrado.

$ openssl rsautl -decrypt -inkey cracked_privkey.pem -in msg.enc
;)

Referencias:
- RSA Labs.
- Ataque de factorización a RSA (hakin9 nº19).
- On the cost of factoring RSA 1024.

msieve 1.21

Aprovecho mi primer post para comentar la publicación por Jason Papadopoulos de una nueva versión de msieve. Podéis acceder a ella desde http://www.boo.net/~jasonp/qs.html.

msieve es una librería de código abierto de factorización de números grandes. Destaca por ser la implementación más rápida del algoritmo de factorización QS. Actualmente también incluye una implementación del algoritmo de factorización NFS.

El problema de factorización de números grandes es muy importante en criptografía por su utilización en ciertos algoritmos de clave pública como RSA. Su resolución dejaría fuera de combate estos algoritmos, por lo que existe gran cantidad de investigación al respecto.

A continuación dejo algunos enlaces que pueden resultar de interés a los aficionados a la factorización:
- NFSNET: Large-scale distributed factoring.
- DFACT: Distributed Factorization Poject.
- Recuperación de clave después de la factorización.