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

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

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

Ikus, gainera aldatu

Kanpo estekak aldatu