RSA Factoring Challenge

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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 mają 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 - s
\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   kwiecień 1991 Arjen K. Lenstra
RSA-110 110 364   kwiecień 1992 Arjen K. Lenstra and M.S. Manasse
RSA-120 120 397   czerwiec 1993 T. Denny et al.
RSA-129 129 426 $100 kwiecień 1994 Arjen K. Lenstra et al.
RSA-130 130 430   10 kwietnia 1996 Arjen K. Lenstra et al.
RSA-140 140 463   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   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  
RSA-576 174 576 $10 000 3 grudnia 2003 Jens Franke et al., Uniwersytet w Bonn
RSA-180 180 596  
RSA-190 190 629  
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  
RSA-704 212 704 $30 000 (wycofana)
RSA-220 220 729  
RSA-230 230 762  
RSA-232 232 768  
RSA-768 232 768 $50 000 (wycofana) 12 grudnia 2009 Thorsten Kleinjung i inni
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]