RSA faktorizazio-lehia
RSA faktorizazio-lehia zenbakien teoria konputazionalaren eta zenbaki handien faktorizazioaren ikerketa sustatzeko asmoz RSA Security enpresak 1991ko martxoaren 18an abian jarritako lehiaketa da. Zenbaki erdilehenen (bi zenbaki lehenen biderkadura diren zenbakiak) zerrenda bat argitaratu zuten, RSA zenbaki izenez ezagutzen direnak, eta haietako batzuk faktorizatzea lortzen zuenarentzat diru-saria eskaini zuten. Zerrenda argitaratu eta egun gutxira zerrendako zenbakirik txikiena faktorizatzea lortu zen: RSA-100 zenbakia zen, 100 zifra hamartarreko RSA zenbakia. Zerrendako zenbaki handienak oraindik faktorizatu gabe daude eta luzaroan horrela egongo direla uste da. Dena den, konputazio kuantikoari esker arlo honetan aurrerakuntza handiak egotea espero da.
RSA faktorizazio-lehia 2007an amaitu zen. Ordutik aurrera enpresak ez du saririk eskaini RSA zenbakiren bat faktorizatzea lortzeagatik. Izan ere, ordurako Kriptografia asko garatu zela ikusita, lehiaketa dagoeneko beharrezkoa ez zela erabaki zuten. Lehiaketarekin lortu zen kriptografia asimetrikokoko RSA gakoen luzera finkatzea, RSA bidezko kriptografia segurua izango baita RSA zenbakia faktorizatzea ezinezkoa denean. RSA Security enpresak RSA zifratze-algoritmoan oinarritutako produktuak saltzen zituenez, haien produktuen sendotasuna frogatzeko baliogarria izan zitzaien lehiaketa.
RSA zenbakien zerrenda osatzeko, zenbakiak sarera konektatu gabeko konputagailu batean sortzen ziren eta ondoren konputagailuaren disko gogorra suntsitu egiten zuten. Horrela, lehiaketaren soluzioak ez ziren inon gordeta geratuko eta sekretu izaten jarraituko zuten[1].
Faktorizatu ziren lehen RSA zenbakiak RSA-100etik RSA-500era bitartekoak eta RSA-617 izan ziren. Zenbaki horiek duten zifra hamartar kopuruaren arabera izendatu ziren (RSA-500 zenbakia, adibidez, 500 zifra hamartar dituen zenbakia da). Gainerako RSA zenbakiak gerora sortu zituzten eta duten zifra bitar kopuruaren arabera izendatu ziren.
Matematika
[aldatu | aldatu iturburu kodea]RSA zenbaki bat emanik, n, beti existituko dira bi zenbaki lehen p eta q, non zera betetzen den:
n = p × q
n zenbakia emanik, p eta q zenbakiak aurkitzean datza RSA zenbakien faktorizazioaren problema. n zenbakia oso handia denean, haren faktorizazioa zaila da, konputazionalki eraginkorra den algoritmorik ez dagoelako.
Sariak eta errekorrak
[aldatu | aldatu iturburu kodea]Hurrengo taulan RSA zenbakien ikuspegi orokorra ikus daiteke:
Txuriz ageri diren errenkadetako RSA zenbakiak adierazpen hamartarrean duten zifra kopuruaren arabera daude izendatuta. Gainerakoak, haien adierazpen bitarrean duten zifra kopuruaren arabera. Azken horietatik RSA-576 eta RSA-640 zenbakiak bakarrik izan ziren sarituak.
RSA zenbakia | Zifra hamartarrak | Zifra bitarrak | Diru-saria | Noiz faktorizatua | Nork faktorizatua |
---|---|---|---|---|---|
RSA-100 | 100 | 330 | US$1,000[2] | 1991ko apirilaren 1ean[3] | Arjen K. Lenstra |
RSA-110 | 110 | 364 | US$4,429[2] | 1992ko apirilaren 14an [3] | Arjen K. Lenstra eta M.S. Manasse |
RSA-120 | 120 | 397 | $5,898[2] | 1993ko uztailaren 9an [1] | T. Denny et al. |
RSA-129 | 129 | 426 | US$100 | 1994ko apirilaren 26an [3] | Arjen K. Lenstra et al. |
RSA-130 | 130 | 430 | US$14,527[2] | 1996ko apirilaren 10ean | Arjen K. Lenstra et al. |
RSA-140 | 140 | 463 | US$17,226 | 1999ko otsailaren 2an | Herman te Riele et al. |
RSA-150 | 150 | 496 | 2004ko apirilaren 16an | Kazumaro Aoki et al. | |
RSA-155 | 155 | 512 | $9,383[2] | 1999ko abuztuaren 22an | Herman te Riele et al. |
RSA-160 | 160 | 530 | 2003ko apirilaren 1ean | Jens Franke et al., Bonneko Unibertsitatea | |
RSA-170 | 170 | 563 | 2009ko abenduaren 29an | D. Bonenberger eta M. Krone [***] | |
RSA-576 | 174 | 576 | US$10,000 | 2003ko abenduaren 3an | Jens Franke et al., Moskuko Estatu Unibertsitatea |
RSA-180 | 180 | 596 | 2010eko maiatzaren 8an | S. A. Danilov eta I. A. Popovyan, Moskuko Estatu Unibertsitatea[4] | |
RSA-190 | 190 | 629 | 2010eko azaroaren 8an | A. Timofeev eta I. A. Popovyan | |
RSA-640 | 193 | 640 | US$20,000 | 2005eko azaroaren 2an | Jens Franke et al., Bonneko Unibertsitatea |
RSA-200 | 200 | 663 | 2005eko maiatzaren 9an | Jens Franke et al., Bonneko Unibertsitatea | |
RSA-210 | 210 | 696 | 2013ko irailaren 26an[5] | Ryan Propper | |
RSA-704 | 212 | 704 | US$30,000 | 2012ko otsailaren 2an | Shi Bai, Emmanuel Thomé eta Paul Zimmermann |
RSA-220 | 220 | 729 | 2016ko maiatzaren 13an | S. Bai, P. Gaudry, A. Kruppa, E. Thomé eta P. Zimmermann | |
RSA-230 | 230 | 762 | 2018ko abuztuaren 15ean | Samuel S. Gross, Noblis, Inc. | |
RSA-232 | 232 | 768 | |||
RSA-768 | 232 | 768 | US$50,000 | 2009, abenduaren 12an | Thorsten Kleinjung et al. |
RSA-240 | 240 | 795 | 2019, abenduaren 2an | Fabrice Boudot et al. | |
RSA-250 | 250 | 829 | |||
RSA-260 | 260 | 862 | |||
RSA-270 | 270 | 895 | |||
RSA-896 | 270 | 896 | US$75,000 | ||
RSA-280 | 280 | 928 | |||
RSA-290 | 290 | 962 | |||
RSA-300 | 300 | 995 | |||
RSA-309 | 309 | 1024 | |||
RSA-1024 | 309 | 1024 | US$100,000 | ||
RSA-310 | 310 | 1028 | |||
RSA-320 | 320 | 1061 | |||
RSA-330 | 330 | 1094 | |||
RSA-340 | 340 | 1128 | |||
RSA-350 | 350 | 1161 | |||
RSA-360 | 360 | 1194 | |||
RSA-370 | 370 | 1227 | |||
RSA-380 | 380 | 1261 | |||
RSA-390 | 390 | 1294 | |||
RSA-400 | 400 | 1327 | |||
RSA-410 | 410 | 1360 | |||
RSA-420 | 420 | 1393 | |||
RSA-430 | 430 | 1427 | |||
RSA-440 | 440 | 1460 | |||
RSA-450 | 450 | 1493 | |||
RSA-460 | 460 | 1526 | |||
RSA-1536 | 463 | 1536 | US$150,000 | ||
RSA-470 | 470 | 1559 | |||
RSA-480 | 480 | 1593 | |||
RSA-490 | 490 | 1626 | |||
RSA-500 | 500 | 1659 | |||
RSA-617 | 617 | 2048 | |||
RSA-2048 | 617 | 2048 | US$200,000 |
Erreferentziak
[aldatu | aldatu iturburu kodea]- ↑ a b On the factorization of RSA-120 - Springer[Betiko hautsitako esteka]. Springerlink.com. Retrieved on 2014-05-11.
- ↑ a b c d e http://www.ontko.com/~rayo/primes/rsa_news.txt
- ↑ a b c RSA Honor Roll
- ↑ http://eprint.iacr.org/2010/270.pdf
- ↑ RSA-210 factored, mersenneforum.org