El RSA Factoring Challenge fue un desafío presentado por RSA Laboratories el 18 de marzo de 1991 [1] para fomentar la investigación sobre la teoría numérica computacional y la dificultad práctica de factorizar enteros grandes y descifrar claves RSA utilizadas en criptografía . Publicaron una lista de semiprimes (números con exactamente dos factores primos ) conocidos como números RSA , con un premio en efectivo por 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-100fue factorizado el 1 de abril de 1991. Muchos de los números más grandes aún no se han factorizado 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 RSA Factoring Desafíos terminó en 2007. [5] RSA Laboratories afirmó: "Ahora que la industria tiene una comprensión mucho más avanzada de la fuerza de cryptanalytic común de clave simétrica y algoritmos de clave pública , estos retos han sido desactivados." [6] Cuando el desafío terminó en 2007, solo RSA-576 y RSA-640 se habían factorizado de los números de desafío de 2001. [7]
El desafío de factorización tenía la intención de seguir la vanguardia en factorización de enteros. Una aplicación principal es elegir la longitud de la clave del esquema de cifrado de clave pública RSA . El progreso en este desafío debería dar 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, utilizaron el desafío como un incentivo para que la comunidad académica atacara el núcleo de sus soluciones, con el fin de demostrar su fortaleza.
Los números RSA se generaron en una computadora sin conexión de red de ningún tipo. Posteriormente, el disco duro de la computadora fue destruido para que no existiera ningún registro, en ninguna parte, de la solución al desafío de factorización. [6]
Los primeros números RSA generados, RSA-100 a RSA-500 y RSA-617, se etiquetaron de acuerdo con su número de dígitos decimales ; los otros números RSA (comenzando con RSA-576) se generaron más tarde y se etiquetaron de acuerdo con su número de dígitos binarios . Los números de la siguiente tabla se enumeran en orden creciente a pesar de este cambio de decimal a binario.
Las matemáticas
RSA Laboratories establece que: para cada número de RSA n , existe números primos p y q tal que
- n = p × q .
El problema es encontrar estos dos números primos, dado solo n .
Los premios y récords
La siguiente tabla ofrece una descripción general de todos los números RSA. Tenga en cuenta que el RSA Factoring Challenge finalizó en 2007 [5] y no se otorgarán más premios por factorizar los números más altos.
- Los números de desafío en líneas blancas son números expresados en base 10 , mientras que los números de desafío en líneas amarillas son números expresados en base 2
Número RSA | Dígitos decimales | Dígitos binarios | Premio en efectivo ofrecido | Factorizado en | Factorizado por |
---|---|---|---|---|---|
RSA-100 | 100 | 330 | 1.000 dólares estadounidenses [8] | 1 de abril de 1991 [9] | Arjen K. Lenstra |
RSA-110 | 110 | 364 | US $ 4.429 [8] | 14 de abril de 1992 [9] | Arjen K. Lenstra y MS Manasse |
RSA-120 | 120 | 397 | US $ 5.898 [8] | 9 de julio de 1993 [10] | T. Denny y col. |
RSA-129 [a] | 129 | 426 | 100 dólares | 26 de abril de 1994 [9] | Arjen K. Lenstra y col. |
RSA-130 | 130 | 430 | US $ 14 527 [8] | 10 de abril de 1996 | Arjen K. Lenstra y col. |
RSA-140 | 140 | 463 | US $ 17.226 | 2 de febrero de 1999 | Herman te Riele y col. |
RSA-150 | 150 | 496 | 16 de abril de 2004 | Kazumaro Aoki y col. | |
RSA-155 | 155 | 512 | US $ 9.383 [8] | 22 de agosto de 1999 | Herman te Riele y col. |
RSA-160 | 160 | 530 | 1 de abril de 2003 | Jens Franke y col. , Universidad de Bonn | |
RSA-170 [b] | 170 | 563 | 29 de diciembre de 2009 | D. Bonenberger y M. Krone [c] | |
RSA-576 | 174 | 576 | 10.000 dólares | 3 de diciembre de 2003 | Jens Franke y col. , Universidad de Bonn |
RSA-180 [b] | 180 | 596 | 8 de mayo de 2010 | SA Danilov e IA Popovyan, Universidad Estatal de Moscú [11] | |
RSA-190 [b] | 190 | 629 | 8 de noviembre de 2010 | A. Timofeev e IA Popovyan | |
RSA-640 | 193 | 640 | 20.000 dólares | 2 de noviembre de 2005 | Jens Franke y col. , Universidad de Bonn |
RSA-200 [b] ? | 200 | 663 | 9 de mayo de 2005 | Jens Franke y col. , Universidad de Bonn | |
RSA-210 [b] | 210 | 696 | 26 de septiembre de 2013 [12] | Ryan Propper | |
RSA-704 [b] | 212 | 704 | US $ 30.000 | 2 de julio de 2012 | Shi Bai, Emmanuel Thomé y Paul Zimmermann |
RSA-220 [b] | 220 | 729 | 13 de mayo de 2016 | S. Bai, P. Gaudry, A. Kruppa, E. Thomé y P. Zimmermann | |
RSA-230 [b] | 230 | 762 | 15 de agosto de 2018 | Samuel S. Gross, Noblis, Inc. | |
RSA-232 [b] | 232 | 768 | 17 de febrero de 2020 [13] | NL Zamarashkin, DA Zheltkov y SA Matveev. | |
RSA-768 [b] | 232 | 768 | 50.000 dólares | 12 de diciembre de 2009 | Thorsten Kleinjung y col. [14] |
RSA-240 [b] | 240 | 795 | 2 de diciembre de 2019 [15] | F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé y P. Zimmermann | |
RSA-250 [b] | 250 | 829 | 28 de febrero de 2020 [16] | F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé y P. Zimmermann | |
RSA-260 | 260 | 862 | |||
RSA-270 | 270 | 895 | |||
RSA-896 | 270 | 896 | US $ 75 000 [d] | ||
RSA-280 | 280 | 928 | |||
RSA-290 | 290 | 962 | |||
RSA-300 | 300 | 995 | |||
RSA-309 | 309 | 1024 | |||
RSA-1024 | 309 | 1024 | US $ 100.000 [d] | ||
RSA-310 | 310 | 1028 | |||
RSA-320 | 320 | 1061 | |||
RSA-330 | 330 | 1094 | |||
RSA-340 | 340 | 1128 | |||
RSA-350 | 350 | 1161 | |||
RSA-360 | 360 | 1194 | |||
RSA-370 | 370 | 1227 | |||
RSA-380 | 380 | 1261 | |||
RSA-390 | 390 | 1294 | |||
RSA-400 | 400 | 1327 | |||
RSA-410 | 410 | 1360 | |||
RSA-420 | 420 | 1393 | |||
RSA-430 | 430 | 1427 | |||
RSA-440 | 440 | 1460 | |||
RSA-450 | 450 | 1493 | |||
RSA-460 | 460 | 1526 | |||
RSA-1536 | 463 | 1536 | US $ 150 000 [d] | ||
RSA-470 | 470 | 1559 | |||
RSA-480 | 480 | 1593 | |||
RSA-490 | 490 | 1626 | |||
RSA-500 | 500 | 1659 | |||
RSA-617 | 617 | 2048 | |||
RSA-2048 | 617 | 2048 | US $ 200 000 [d] |
- ^ RSA-129 no formaba parte del RSA Factoring Challenge, pero estaba relacionado con una columna de Martin Gardner en Scientific American .
- ^ a b c d e f g h i j k l El número se factorizó una vez finalizado el desafío.
- ↑ RSA-170 también fue factorizado independientemente por SA Danilov e IA Popovyan dos días después. [11]
- ^ a b c d El desafío terminó antes de que se otorgara este premio.
Ver también
- Números RSA , expansiones decimales de los números y factorizaciones conocidas
- LCS35
- Las palabras mágicas son Squeamish Ossifrage , la solución encontrada en 1993 a otro desafío RSA planteado en 1977
- Desafío de clave secreta RSA
- Registros de factorización de enteros
Notas
- ^ Kaliski, Burt (18 de marzo de 1991). "Anuncio de" RSA Factoring Challenge " " . Consultado el 8 de marzo de 2021 .
- ^ Leyden, John (25 de julio de 2001). "RSA plantea un desafío criptográfico de $ 200.000" . El registro . Consultado el 8 de marzo de 2021 .
- ^ Laboratorios RSA. "El nuevo desafío de factorización RSA" . Archivado desde el original el 14 de julio de 2001.
- ^ Laboratorios RSA. "Los números del desafío RSA" . Archivado desde el original el 5 de agosto de 2001.
- ^ a b Laboratorios RSA. "Desafío de factorización RSA" . Archivado desde el original el 21 de septiembre de 2013 . Consultado el 5 de agosto de 2008 . CS1 maint: parámetro desalentado ( enlace )
- ^ a b Laboratorios RSA. "Preguntas frecuentes sobre el desafío de factorización de RSA" . Archivado desde el original el 21 de septiembre de 2013 . Consultado el 5 de agosto de 2008 . CS1 maint: parámetro desalentado ( enlace )
- ^ Laboratorios RSA. "Los números del desafío RSA" . Archivado desde el original el 21 de septiembre de 2013 . Consultado el 5 de agosto de 2008 . CS1 maint: parámetro desalentado ( enlace )
- ^ a b c d e "Informe de estado / noticias sobre el desafío de factorización de seguridad de datos RSA (a partir del 30/03/00)" . 30 de enero de 2002.
- ^ a b c Cuadro de honor de RSA
- ^ Denny, T .; Dodson, B .; Lenstra, AK; Manasse, MS (1994). Sobre la factorización de RSA-120 . Avances en criptología - CRYPTO '93 . págs. 166-174. doi : 10.1007 / 3-540-48329-2_15 .
- ^ a b Danilov, SA; Popovyan, IA (9 de mayo de 2010). "Factorización de RSA-180" (PDF) . Archivo ePrint de criptología .
- ^ RSA-210 factorizado , mersenneforum.org
- ^ Noticias de INM RAS
- ^ Kleinjung, Thomas (18 de febrero de 2010). "Factorización de un módulo RSA de 768 bits" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ Thomé, Emmanuel (2 de diciembre de 2019). "Factorización de 795 bits y logaritmos discretos" . cado-nfs-discus (lista de correo).
- ^ Zimmermann, Paul (28 de febrero de 2020). "Factorización de RSA-250" . cado-nfs-discus (lista de correo).