El RSA Factoring Challenge fue un desafío propuesto por RSA Laboratories el 18 de marzo de 1991 [1] para fomentar la investigación en la teoría de números computacionales y la dificultad práctica de factorizar números enteros grandes y descifrar claves RSA utilizadas en criptografía . Publicaron una lista de semiprimos (números con exactamente dos factores primos ) conocidos como números RSA , con un premio en efectivo para la factorización exitosa de algunos de ellos. El más pequeño de ellos, un número de 100 dígitos decimales llamado RSA-100, fue factorizado el 1 de abril de 1991. Muchos de los números más grandes aún no han sido factorizados y se espera que permanezcan sin factorizar durante bastante tiempo, sin embargo, los avances en las computadoras cuánticas hacen que esta predicción sea incierta debido al algoritmo de Shor .
En 2001, RSA Laboratories amplió el desafío de factorización y ofreció premios que iban desde $10,000 a $200,000 por factorizar números desde 576 bits hasta 2048 bits. [2] [3] [4]
Los desafíos de factorización RSA finalizaron en 2007. [5] RSA Laboratories declaró: "Ahora que la industria tiene una comprensión considerablemente más avanzada de la fortaleza criptoanalítica de los algoritmos comunes de clave simétrica y clave pública , estos desafíos ya no están activos". [6] Cuando el desafío finalizó en 2007, solo se habían factorizado RSA-576 y RSA-640 de los números del desafío de 2001. [7]
El desafío de factorización tenía como objetivo seguir la vanguardia en la factorización de números enteros . Una aplicación principal es la elección de la longitud de la clave del esquema de cifrado de clave pública RSA . El progreso en este desafío debería brindar una idea de qué tamaños de clave siguen siendo seguros y durante cuánto tiempo. Como RSA Laboratories es un proveedor de productos basados en RSA, el desafío fue utilizado por ellos como un incentivo para que la comunidad académica atacara el núcleo de sus soluciones, con el fin de demostrar su solidez.
Los números RSA se generaron en un ordenador sin conexión a la red de ningún tipo. El disco duro del ordenador fue destruido posteriormente para que no quedara registro, en ningún lugar, de la solución del problema de factorización. [6]
Los primeros números RSA generados, RSA-100 a RSA-500 y RSA-617, se etiquetaron según su número de dígitos decimales ; los demás números RSA (comenzando con RSA-576) se generaron más tarde y se etiquetaron según su número de dígitos binarios . Los números de la tabla siguiente se enumeran en orden creciente a pesar de este cambio del decimal al binario.
RSA Laboratories afirma que: para cada número RSA n , existen números primos p y q tales que
El problema es encontrar estos dos primos, dado sólo n .
La siguiente tabla ofrece una descripción general de todos los números RSA. Tenga en cuenta que el Desafío de Factorización RSA finalizó en 2007 [5] y no se otorgarán más premios por factorizar los números más altos.
{{cite journal}}: Requiere citar revista |journal=( ayuda )