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.

Zadanie

Niech ${\displaystyle n}$ oznacza liczbę RSA. Istnieją liczby pierwsze ${\displaystyle p}$ i ${\displaystyle q,}$ takie że:

${\displaystyle n=pq.}$

Zadanie polega na znalezieniu tych liczb, mając dane ${\displaystyle n}$'.

Liczby te zostały dobrane tak, aby wartości podstawowych funkcji arytmetycznych nie ułatwiały rozłożenia jej na czynniki pierwsze:

${\displaystyle d(n)=2}$

${\displaystyle \phi (n)=(p-1)(q-1)=n+1-(p+q)}$

${\displaystyle \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	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ż

• liczby RSA