RSA Factoring Challenge

RSA Factoring Challenge var en utmaning som lades fram av RSA Laboratories den 18 mars 1991 för att uppmuntra forskning om beräkningstalteori och den praktiska svårigheten att faktorisera stora heltal och knäcka RSA -nycklar som används i kryptografi . De publicerade en lista över semiprimtal (tal med exakt två primtalsfaktorer ) kända som RSA-tal , med ett kontantpris för den framgångsrika faktoriseringen av några av dem. Den minsta av dem, ett siffror med 100 decimaler kallat RSA-100, räknades in den 1 april 1991. Många av de större siffrorna har fortfarande inte räknats in och förväntas förbli opåverkade under ganska lång tid, hur framsteg inom kvantdatorer än gör . denna förutsägelse osäker på grund av Shors algoritm .

År 2001 utökade RSA Laboratories factoringutmaningen och erbjöd priser från $10 000 till $200 000 för factoringtal från 576 bitar upp till 2048 bitar.

RSA Factoring Challenges avslutades 2007. RSA Laboratories uttalade: "Nu när branschen har en betydligt mer avancerad förståelse för den kryptoanalytiska styrkan hos vanliga symmetriska och publika nyckelalgoritmer är dessa utmaningar inte längre aktiva." När utmaningen avslutades 2007 hade endast RSA-576 och RSA-640 räknats med från 2001 års utmaningssiffror.

Faktoreringsutmaningen var avsedd att spåra framkanten i heltalsfaktorisering. En primär applikation är för att välja nyckellängden för RSA - krypteringsschemat med publik nyckel . Framsteg i denna utmaning bör ge en inblick i vilka nyckelstorlekar som fortfarande är säkra och hur länge. Eftersom RSA Laboratories är en leverantör av RSA-baserade produkter, användes utmaningen av dem som ett incitament för det akademiska samhället att attackera kärnan i sina lösningar – för att bevisa sin styrka.

RSA-numren genererades på en dator utan någon nätverksanslutning av något slag. Datorns hårddisk förstördes därefter så att det inte skulle finnas några uppgifter någonstans om lösningen på factoringutmaningen.

De första genererade RSA-numren, RSA-100 till RSA-500 och RSA-617, märktes enligt deras antal decimalsiffror ; de andra RSA-numren (som börjar med RSA-576) genererades senare och märktes enligt deras antal binära siffror. Siffrorna i tabellen nedan listas i stigande ordning trots denna förskjutning från decimal till binär.

Matematiken

RSA Laboratories säger att: för varje RSA-tal n finns det primtal p och q så att

n = p × q .

Problemet är att hitta dessa två primtal, givet endast n .

Priserna och rekorden

Följande tabell ger en översikt över alla RSA-nummer. Observera att RSA Factoring Challenge avslutades 2007 och inga ytterligare priser kommer att delas ut för att faktorisera de högre siffrorna.

Utmaningsnumren i vita linjer är en del av den ursprungliga utmaningen och uttrycks i bas 10 , medan utmaningsnumren i gula linjer är en del av 2001 års expansion och uttrycks i bas 2
RSA-nummer Decimalsiffror Binära siffror Kontantpris erbjuds Beaktad Factored by
RSA100 100 330 1 000 USD 1 april 1991 Arjen K. Lenstra
RSA110 110 364 4 429 USD 14 april 1992 Arjen K. Lenstra och MS Manasse
RSA120 120 397 5 898 USD 9 juli 1993 T. Denny et al.
RSA129 129 426 100 USD 26 april 1994 Arjen K. Lenstra et al.
RSA130 130 430 14 527 USD 10 april 1996 Arjen K. Lenstra et al.
RSA140 140 463 17 226 USD 2 februari 1999 Herman te Riele et al.
RSA150 150 496   16 april 2004 Kazumaro Aoki et al.
RSA155 155 512 9 383 USD 22 augusti 1999 Herman te Riele et al.
RSA160 160 530   1 april 2003 Jens Franke et al. , universitetet i Bonn
RSA170 170 563   29 december 2009 D. Bonenberger och M. Krone
RSA576 174 576 10 000 USD 3 december 2003 Jens Franke et al. , universitetet i Bonn
RSA180 180 596   8 maj 2010 SA Danilov och IA Popovyan, Moscow State University
RSA190 190 629   8 november 2010 A. Timofeev och IA Popovyan
RSA640 193 640 20 000 USD 2 november 2005 Jens Franke et al. , universitetet i Bonn
  RSA200 ? 200 663   9 maj 2005 Jens Franke et al. , universitetet i Bonn
RSA210 210 696 26 september 2013 Ryan Propper
RSA704 212 704 30 000 USD 2 juli 2012 Shi Bai, Emmanuel Thomé och Paul Zimmermann
RSA220 220 729   13 maj 2016 S. Bai, P. Gaudry, A. Kruppa, E. Thomé och P. Zimmermann
RSA230 230 762   15 augusti 2018 Samuel S. Gross, Noblis, Inc.
RSA232 232 768   17 februari 2020 NL Zamarashkin, DA Zheltkov och SA Matveev.
RSA768 232 768 50 000 USD 12 december 2009 Thorsten Kleinjung et al.
RSA240 240 795   2 december 2019 F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé och P. Zimmermann
RSA250 250 829   28 februari 2020 F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé och P. Zimmermann
RSA260 260 862  
RSA270 270 895  
RSA896 270 896 75 000 USD
RSA280 280 928  
RSA290 290 962  
RSA300 300 995  
RSA309 309 1024  
RSA1024 309 1024 100 000 USD
RSA310 310 1028  
RSA320 320 1061  
RSA330 330 1094  
RSA340 340 1128  
RSA350 350 1161  
RSA360 360 1194  
RSA370 370 1227  
RSA380 380 1261  
RSA390 390 1294  
RSA400 400 1327  
RSA410 410 1360  
RSA420 420 1393  
RSA430 430 1427  
RSA440 440 1460  
RSA450 450 1493  
RSA460 460 1526  
RSA1536 463 1536 150 000 USD
RSA470 470 1559  
RSA480 480 1593  
RSA490 490 1626  
RSA500 500 1659  
RSA617 617 2048  
RSA2048 617 2048 200 000 USD

Se även

Anteckningar

  1. ^ Kaliski, Burt (18 mars 1991). "Meddelande om "RSA Factoring Challenge" " . Hämtad 8 mars 2021 . [ död länk ]
  2. ^ Leyden, John (25 juli 2001). "RSA ställer $200 000 kryptoutmaning" . Registret . Hämtad 8 mars 2021 .
  3. ^ RSA-laboratorier. "The New RSA Factoring Challenge" . Arkiverad från originalet 2001-07-14.
  4. ^ RSA-laboratorier. "The RSA Challenge Numbers" . Arkiverad från originalet 2001-08-05.
  5. ^ a b RSA-laboratorier. "RSA Factoring Challenge" . Arkiverad från originalet 2013-09-21 . Hämtad 2008-08-05 .
  6. ^ a b RSA-laboratorier. "The RSA Factoring Challenge FAQ" . Arkiverad från originalet 2013-09-21 . Hämtad 2008-08-05 .
  7. ^ RSA-laboratorier. "The RSA Challenge Numbers" . Arkiverad från originalet 2013-09-21 . Hämtad 2008-08-05 .
  8. ^ a b c d e "Status-/nyhetsrapport om RSA datasäkerhet factoring utmaning (från och med 3/30/00)" . 30 januari 2002.
  9. ^ a b c RSA Hedersrulle
  10. ^   Denny, T.; Dodson, B.; Lenstra, AK; Manasse, MS (1994). Om faktoriseringen av RSA-120 . Framsteg inom kryptologi — CRYPTO' 93 . Föreläsningsanteckningar i datavetenskap. Vol. 773. s. 166–174. doi : 10.1007/3-540-48329-2_15 . ISBN 978-3-540-57766-9 .
  11. ^ a b Danilov, SA; Popovyan, IA (9 maj 2010). "Faktorisering av RSA-180" (PDF) . Kryptologi ePrint-arkiv .
  12. ^ RSA-210 factored , mersenneforum.org
  13. ^ INM RAS nyheter
  14. ^ Kleinjung, Thomas (18 februari 2010). "Faktorisering av en 768-bitars RSA-modul" (PDF) . {{ citera journal }} : Citera journal kräver |journal= ( hjälp )
  15. ^ Thomé, Emmanuel (2 december 2019). "795-bitars factoring och diskreta logaritmer" . cado-nfs-discuss (e-postlista).
  16. ^ Zimmermann, Paul (28 februari 2020). "Faktorisering av RSA-250" . cado-nfs-discuss (e-postlista).
Hämtad från " https://en.wikipedia.org/w/index.php?title=RSA_Factoring_Challenge&oldid=1125050682 "