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.

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

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

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ż

• RSA liczby

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