RSA Factoring Challenge - RSA Factoring Challenge

The RSA Factoring Challenge byla výzva, kterou předložil RSA Laboratories dne 18. března 1991 na podporu výzkumu výpočetní teorie čísel a praktická obtížnost factoring velký celá čísla a praskání RSA klíče používané v kryptografie. Zveřejnili seznam semiprimes (čísla s přesně dvěma hlavní faktory ) známý jako Čísla RSA, s finanční odměnou za úspěšnou faktorizaci některých z nich. Nejmenší z nich, volané 100místné číslo RSA-100 byl zapracován do 1. dubna 1991, ale mnoho z většího počtu dosud nebylo započítáno a očekává se, že zůstane nefaktorizované po nějakou dobu, nicméně pokrok v kvantové počítače učinit tuto předpověď nejistou kvůli Shorův algoritmus.

Výzvy RSA skončily v roce 2007.[1] Laboratoře RSA uvedly: „Nyní, když má toto odvětví podstatně pokročilejší znalosti o kryptoanalytické síle symetrický klíč a algoritmy veřejného klíče, tyto výzvy již nejsou aktivní. “[2]

Úkolem faktoringové výzvy bylo sledovat špičku v celočíselné faktorizaci. Primární aplikace je pro výběr délka klíče z RSA šifrování veřejného klíče systém. Pokrok v této výzvě by měl poskytnout pohled na to velikosti klíčů jsou stále v bezpečí a na jak dlouho. Vzhledem k tomu, že RSA Laboratories je poskytovatelem produktů na bázi RSA, využili tuto výzvu jako pobídku pro akademickou komunitu k útoku na jádro jejich řešení - za účelem prokázání její síly.

Čísla RSA byla generována na počítači bez jakéhokoli síťového připojení. Pevný disk počítače byl následně zničen, takže by nikde neexistoval žádný záznam o řešení faktoringové výzvy.[3]

První vygenerovaná čísla RSA, RSA-100 až RSA-500 a RSA-617, byla označena podle jejich počtu desetinný číslice; další čísla RSA (počínaje RSA-576) byla vygenerována později a označena podle jejich počtu binární číslice. Čísla v tabulce níže jsou uvedena v rostoucím pořadí i přes tento posun z desítkového na binární.

Matematika

RSA Laboratories uvádí, že: pro každé číslo RSA n, tady existuje prvočísla p a q takhle

n = p × q.

Problém je najít tyto dvě prvočísla, pouze uvedená n.

Ceny a záznamy

Následující tabulka poskytuje přehled všech čísel RSA.

Čísla výzev v bílých čarách jsou čísla vyjádřená v základna 10, zatímco čísla výzev ve žlutých čarách jsou čísla vyjádřená v základna 2
Číslo RSADesetinná číslaBinární čísliceNabízena peněžní výhraZapočítánoFaktor
RSA-1001003301 000 USD[4]1. dubna 1991[5]Arjen K. Lenstra
RSA-1101103644 429 USD[4]14. dubna 1992[5]Arjen K. Lenstra a SLEČNA. Manasse
RSA-1201203975 898 USD[4]9. července 1993[6]T. Denny et al.
RSA-129 [**]129426100 USD26.dubna 1994[5]Arjen K. Lenstra et al.
RSA-13013043014 527 USD[4]10. dubna 1996Arjen K. Lenstra et al.
RSA-14014046317 226 USD2. února 1999Herman te Riele et al.
RSA-150150496 16. dubna 2004Kazumaro Aoki et al.
RSA-1551555129 383 USD[4]22. srpna 1999Herman te Riele et al.
RSA-160160530 1. dubna 2003Jens Franke et al., University of Bonn
RSA-170 [*]170563 29. prosince 2009D. Bonenberger a M. Krone [***]
RSA-57617457610 000 USD3. prosince 2003Jens Franke et al., University of Bonn
RSA-180 [*]180596 8. května 2010S. A. Danilov a I. A. Popovyan, Moskevská státní univerzita[7]
RSA-190 [*]190629 8. listopadu 2010A. Timofeev a I. A. Popovyan
RSA-64019364020 000 USD2. listopadu 2005Jens Franke et al., University of Bonn
RSA-200 [*] ?200663 9. května 2005Jens Franke et al., University of Bonn
RSA-210 [*]21069626. září 2013[8]Ryan Propper
RSA-704 [*]21270430 000 USD2. července 2012Shi Bai, Emmanuel Thomé a Paul Zimmermann
RSA-220 [*]220729 13. května 2016S. Bai, P. Gaudry, A. Kruppa, E. Thomé a P. Zimmermann
RSA-230 [*]230762 15. srpna 2018Samuel S. Gross, Noblis, Inc.
RSA-232 [*]232768 17. února 2020[9]N. L. Zamarashkin, D. A. Zheltkov a S. A. Matveev.
RSA-768 [*]23276850 000 USD12. prosince 2009Thorsten Kleinjung et al.
RSA-240 [*]240795 2. prosince 2019[10]F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé a P. Zimmermann
RSA-250 [*]250829 28. února 2020[11]F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé a P. Zimmermann
RSA-260260862 
RSA-270270895 
RSA-89627089675 000 USD
RSA-280280928 
RSA-290290962 
RSA-300300995 
RSA-3093091024 
RSA-10243091024100 000 USD
RSA-3103101028 
RSA-3203201061 
RSA-3303301094 
RSA-3403401128 
RSA-3503501161 
RSA-3603601194 
RSA-3703701227 
RSA-3803801261 
RSA-3903901294 
RSA-4004001327 
RSA-4104101360 
RSA-4204201393 
RSA-4304301427 
RSA-4404401460 
RSA-4504501493 
RSA-4604601526 
RSA-15364631536150 000 USD
RSA-4704701559 
RSA-4804801593 
RSA-4904901626 
RSA-5005001659 
RSA-6176172048 
RSA-20486172048200 000 USD

^ * Číslo bylo zohledněno poté, co se výzva stala neaktivní.

^ ** RSA-129 nebyl součástí RSA Factoring Challenge, ale byl příbuzný sloupci od Martina Gardnera v Scientific American.

^ *** RSA-170 byl také nezávisle zapracován S. A. Danilovem a I. A. Popovyanem o dva dny později.[7]

Viz také

Poznámky

  1. ^ RSA Laboratories, RSA Factoring Challenge Archivováno 10. 11. 2013 v Wayback Machine. Citováno 2013-11-09.
  2. ^ RSA Laboratories, Časté dotazy k výzvě RSA Factoring Archivováno 10. 11. 2013 v Wayback Machine. Citováno 2013-11-09.
  3. ^ Laboratoře RSA. „Časté dotazy k výzvě RSA Factoring Challenge“. Archivovány od originál dne 21. 9. 2013. Citováno 2008-08-05.
  4. ^ A b C d E „Stavová / zpravodajská zpráva o výzvě faktoringu zabezpečení dat RSA (stav k 30. 3.00)“. 30. ledna 2002.
  5. ^ A b C RSA Honor Roll
  6. ^ Denny, T .; Dodson, B .; Lenstra, A. K .; Manasse, M. S. (1994). O faktorizaci RSA-120. Pokroky v kryptologii - CRYPTO '93. 166–174. doi:10.1007/3-540-48329-2_15.
  7. ^ A b Danilov, S. A .; Popovyan, I. A. (9. května 2010). "Faktorizace RSA-180" (PDF). Archiv kryptologie ePrint.
  8. ^ RSA-210 zapracován, mersenneforum.org
  9. ^ Novinky INM RAS
  10. ^ Thomé, Emmanuel (2. prosince 2019). „795bitový factoring a diskrétní logaritmy“. cado-nfs-discuss (Poštovní seznam).
  11. ^ Zimmermann, Paul (28. února 2020). "Faktorizace RSA-250". cado-nfs-discuss (Poštovní seznam).

externí odkazy