Z Wikipedii

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 2007r. 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.

[edytuj] Zadanie

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

φ(n) = (p − 1)(q − 1) = n + 1 − s

σ(n) = (p + 1)(q + 1) = n + 1 + p + q.

[edytuj] 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.

Pozostałe nagrody zostały wycofane ze względu na zakończenie zawodów w 2007 roku.

[edytuj] Zobacz też

• RSA Secret-Key Challenge

Przypisy

[edytuj] Linki zewnętrzne

• RSA Security: The new RSA factoring challenge
• MathWorld: RSA Number
• Mathematica package for RSA numbers
• The original challenge announcement on sci.crypt