Factorización de RSA-200

Un equipo multinacional resuelve el reto RSA-200, consistente en
factorizar un número de 200 dígitos decimales.

El equipo, formado por centros de investigación alemanes y holandeses,
ha invertido casi año y medio en encontrar la solución y ha requerido la
potencia equivalente a un AMD Opteron a 2.2 Ghz trabajando durante 55 años.

En el momento de escribir este boletín RSA, la compañía convocante de
los retos, todavía no ha confirmado su validez.

Pero, por supuesto, cualquiera que utilice un programa capaz de
multiplicar dos números de cien dígitos puede comprobar si la solución
propuesta es correcta.

Este tipo de retos tienen una gran importancia para conocer el estado
del arte en cuanto a ataques a los sistemas criptográficos más
utilizados en la actualidad. El algoritmo RSA, por ejemplo, es ubicuo.
Se utiliza en la mayoría de las transacciones electrónicas que hacen uso
de la criptografía, como el cifrado SSL utilizado por los navegadores
web, o el S/MIME o PGP (GPG) empleado en el correo electrónico.

Una de las ventajas del algoritmo RSA, además de su simplicidad, es que
su patente expiró en Septiembre de 2000, por lo que se trata de un
algoritmo que cualquier individuo puede utilizar libremente, al menos en
los países sin legislación restrictiva en cuanto a criptografía.

Para los alarmistas, recordemos que el número factorizado tiene
doscientos dígitos decimales o, aproximadamente, 660 bits,
y que las claves RSA más típicas miden 1024 bits, y que cada bit
adicional duplica la complejidad del problema. Por lo tanto las claves
RSA «normales» siguen siendo seguras, salvo avances teóricos o el
advenimiento de la informática cuántica, que es el espectro que planea
sobre el algoritmo RSA…

Algunos datos de interés:

El número a factorizar era

27.997.833.911.221.327.870.829.467.638.722.601.621.070.446.786.
955.428.537.560.009.929.326.128.400.107.609.345.671.052.955.360.
856.061.822.351.910.951.365.788.637.105.954.482.006.576.775.098.
580.557.613.579.098.734.950.144.178.863.178.946.295.187.237.869.
221.823.983

y sus factores son

3.532.461.934.402.770.121.272.604.978.198.464.368.671.197.400.
197.625.023.649.303.468.776.121.253.679.423.200.058.547.956.528.
088.349

y

7.925.869.954.478.333.033.347.085.841.480.059.687.737.975.857.
364.219.960.734.330.341.455.767.872.818.152.135.381.409.304.740.
185.467

Más información:

Factors Found in 200-Digit RSA Challenge
http://it.slashdot.org/article.pl?sid=05/05/10/1955226

Two hundred digit number factored
http://en.wikinews.org/wiki/200_digit_number_factored

rsa200
http://www.loria.fr/%7Ezimmerma/records/rsa200

RSA-200 Factored
http://mathworld.wolfram.com/news/2005-05-10/rsa-200/

The RSA Challenge Numbers
http://www.rsasecurity.com/rsalabs/node.asp?id=2093