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ącychRSA Laboratories, The RSA Factoring Challenge FAQ..
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 Niech oznacza liczbę RSA. Istnieją liczby pierwsze i takie że:
Zadanie polega na znalezieniu tych liczb, mając dane '.
Liczby te zostały dobrane tak, aby wartości podstawowych funkcji arytmetycznych nie ułatwiały rozłożenia jej na czynniki pierwsze:
Nagrody i postępy 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 $http://www.ontko.com/~rayo/primes/rsa_news.txt 1 kwietnia 1991RSA Honor Roll. Arjen K. Lenstra RSA-110 110 364 4 429 $ 14 kwietnia 1992 Arjen K. Lenstra i M.S. Manasse RSA-120 120 397 5 898 $ 9 czerwca 1993On the factorization of RSA-120 – Springer. Springerlink.com. Retrieved on 2014-05-11. T. Denny et al. RSA-129 129 426 100 $ 26 kwietnia 1994 Arjen K. Lenstra et al. RSA-130 130 430 14 527 $ 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 $ 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 13 maja 2016 S. Bai, P. Gaudry, A. Kruppa, E. Thomé i P. Zimmermann RSA-230 230 762 15 sierpnia 2018Samuel S. Gross, Nobilis Inc. RSA-232 232 768 17 lutego 2020N. L. Zamarashkin, D. A. Zheltkov i S. A. Matveev RSA-768 232 768 50 000 $ (wycofana) 12 grudnia 2009 Thorsten Kleinjung et al. RSA-240 240 795 2 grudnia 2019 F.Boudot, P. Gaudry, A.Guillevic, N. Heninger, E. Thomé i P. Zimmerman RSA-250 250 829 28 lutego 2020.Cado-nfs-discuss lista dyskusyjna.F.Boudot, P. Gaudry, A.Guillevic, N. Heninger, E. Thomé i P. Zimmerman RSA-260 260 862 3 września 2026Eric Lu RSA-270 270 895 – RSA-896 270 896 75 000 $ (wycofana) 19 września 2026Stephen A. Weis 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ż liczby RSA
Przypisy
Linki zewnętrzne RSA Security: The new RSA factoring challenge
Mathematica package for RSA numbers The original challenge announcement on sci.crypt
Kategoria:Kryptografia klucza publicznego