RSA Factoring Challenge

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.

ZadanieEdytuj

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ępyEdytuj

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 13 maja 2016 S. Bai, P. Gaudry, A. Kruppa, E. Thomé i P. Zimmermann
RSA-230 230 762 15 sierpnia 2018 Samuel S. Gross, Nobilis Inc.
RSA-232 232 768 17 lutego 2020 N. 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[5] F.Boudot, P. Gaudry, A.Guillevic, N. Heninger, E. Thomé i P. Zimmerman
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

PrzypisyEdytuj

  1. RSA Laboratories, The RSA Factoring Challenge FAQ.
  2. a b c d e http://www.ontko.com/~rayo/primes/rsa_news.txt
  3. a b c RSA Honor Roll.
  4. On the factorization of RSA-120 – Springer. Springerlink.com. Retrieved on 2014-05-11.
  5. [1].Cado-nfs-discuss lista dyskusyjna.

Linki zewnętrzneEdytuj