RSA Factoring Challenge

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

RSA Factoring Challenge były otwartymi zawodami zorganizowanymi przez RSA Security w celu pobudzenia badań nad praktycznymi algorytmami faktoryzacji dużych liczb. Opublikowana została lista pseudopierwszych liczb (rozkładających się na dokładnie dwa czynniki), nazwanych liczbami RSA. Za rozłożenie niektórych z nich wyznaczono pieniężną nagrodę. Najmniejsza z nich, 100-cyfrowa liczba RSA-100 została rozłożona w ciągu kilku dni, ale większość do dziś pozostaje niezłamana.

Konkurs rozpoczął się 18 marca 1991 roku, a zakończył się w maju 2007 r. Organizatorzy stwierdzili, że aktualny stan wiedzy pozwala na stosowanie bardziej zaawansowanych metod oceny siły algorytmów szyfrujących.[1]

Zawody miały na celu śledzenie rozwoju możliwości komputerów w faktoryzacji. Jest to niezwykle istotne przy wyborze długości klucza w szyfrowaniu asymetrycznym metodą RSA. Postęp w łamaniu kolejnych liczb powinien zdradzać jakie długości klucza można jeszcze uznawać za bezpieczne.

Pierwsze wygenerowane liczby RSA, od RSA-100 do RSA-500, były oznaczane według liczby cyfr dziesiętnych. Potem wprowadzono numerację zależną od liczby bitów, począwszy od RSA-576.

Zadanie[edytuj | edytuj kod]

Niech n oznacza liczbę RSA. Istnieją liczby pierwsze p i q, takie że:

n=pq.

Zadanie polega na znalezieniu tych liczb, mając dane n.

Liczby te zostały dobrane tak, aby wartości podstawowych funkcji arytmetycznych nie ułatwiały rozłożenia jej na czynniki pierwsze:

d(n) = 2
\phi(n)=(p-1)(q-1) = n + 1 - (p + q)
\sigma(n)=(p+1)(q+1) = n + 1 + p + q.

Nagrody i postępy[edytuj | edytuj kod]

Poniższa tabela przedstawia stan zawodów.

Wiersze różowe dotyczą liczb podanych w cyfrach dziesiętnych, wiersze żółte dotyczą liczb podanych w bitach, z wyznaczoną nagrodą za rozwiązanie.
Część nagród została wycofana ze względu na zakończenie zawodów w 2007 roku.
Liczba RSA Cyfr Bitów Nagroda Rozłożona Zespół rozwiązujący
RSA-100 100 330 $1 000[2] 1 kwietnia 1991[3] Arjen K. Lenstra
RSA-110 110 364 $4 429[2] 14 kwietnia 1992[3] Arjen K. Lenstra i M.S. Manasse
RSA-120 120 397 $5 898[2] 9 czerwca 1993[4] T. Denny et al.
RSA-129 129 426 $100 26 kwietnia 1994[3] Arjen K. Lenstra et al.
RSA-130 130 430 $14 527[2] 10 kwietnia 1996 Arjen K. Lenstra et al.
RSA-140 140 463 $17 227 2 lutego 1999 Herman J. J. te Riele et al.
RSA-150 150 496   16 kwietnia 2004 Kazumaro Aoki et al.
RSA-155 155 512 $9 383[2] 22 sierpnia 1999 Herman J. J. te Riele et al.
RSA-160 160 530   1 kwietnia 2003 Jens Franke et al., Uniwersytet w Bonn
RSA-170 170 563   29 grudnia 2009 D. Bonenberger i M. Krone
RSA-576 174 576 $10 000 3 grudnia 2003 Jens Franke et al., Uniwersytet w Bonn
RSA-180 180 596   8 maja 2010 S. A. Danilov i I. A. Popovyan, Uniwersytet Moskiewski
RSA-190 190 629   8 listopada 2010 A. Timofeev i I. A. Popovyan
RSA-640 193 640 $20 000 2 listopada 2005 Jens Franke et al., Uniwersytet w Bonn
RSA-200 200 663   9 maja 2005 Jens Franke et al., Uniwersytet w Bonn
RSA-210 210 696   26 września 2013 Ryan Propper
RSA-704 212 704 $30 000 (wycofana) 2 lipca 2012 Shi Bai, Emmanuel Thomé i Paul Zimmermann
RSA-220 220 729  
RSA-230 230 762  
RSA-232 232 768  
RSA-768 232 768 $50 000 (wycofana) 12 grudnia 2009 Thorsten Kleinjung et al.
RSA-240 240 795  
RSA-250 250 829  
RSA-260 260 862  
RSA-270 270 895  
RSA-896 270 896 $75 000 (wycofana)
RSA-280 280 928  
RSA-290 290 962  
RSA-300 300 995  
RSA-309 309 1024  
RSA-1024 309 1024 $100 000 (wycofana)
RSA-310 310 1028  
RSA-320 320 1061  
... ... ...   ...
RSA-450 450 1493  
RSA-460 460 1526  
RSA-1536 463 1536 $150 000 (wycofana)
RSA-470 470 1559  
RSA-480 480 1593  
RSA-490 490 1626  
RSA-500 500 1659  
RSA-617 617 2048  
RSA-2048 617 2048 $200 000 (wycofana)

Zobacz też[edytuj | edytuj kod]

Przypisy

Linki zewnętrzne[edytuj | edytuj kod]