In matematica, i numeri RSA sono un insieme di semiprimi (ossia numeri con esattamente due fattori primi) che facevano parte del RSA Factoring Challenge. La sfida, che consisteva nel trovare la fattorizzazione di tali numeri, è stata dichiarata conclusa nel 2007RSA Laboratories, The RSA Factoring Challenge . Consultato il 13 giugno 2010. ed era stata creata dai RSA Laboratories nel 1991 per incoraggiare la ricerca nella teoria dei numeri computazionale ed in particolare nella fattorizzazione di interi molto grandi.
All'inizio della sfida la RSA Laboratories pubblicò 54 semiprimi con numero di cifre decimali compreso tra 100 e 617. Ad alcuni di questi semiprimi fu associato un premio in denaro da destinare a chi ne avesse trovato per primo la fattorizzazione. Il primo dei numeri RSA fu fattorizzato in pochi giorni, ma per la maggior parte degli altri numeri il problema è ancora aperto e per molti di loro ci si aspetta che rimanga aperto ancora a lungo. Fino ad ora (gennaio 2021), sono stati fattorizzati 23 dei 54 numeri RSA, da RSA-100 a RSA-250.
La sfida fu dichiarata ufficialmente conclusa nel 2007, ma vari gruppi di lavoro continuano tuttora a cercare di fattorizzare i numeri rimanenti. Al momento di interrompere la sfida, la RSA Laboratories dichiarò che "Ora che l'industria ha raggiunto una comprensione più avanzata della potenza crittografica degli algoritmi a chiave simmetrica e a chiave pubblica, la sfida non è più attiva".RSA Laboratories, The RSA Factoring Challenge FAQ . Consultato il 13 giugno 2010.Alcuni dei premi di valore minore sono stati assegnati nel corso degli anni, mentre tutti quelli non ancora assegnati al momento della chiusura della sfida sono stati annullati.
La cifra nel nome dei primi numeri RSA generati, da RSA-100 a RSA-500, indica il numero delle cifre decimali; successivamente, a partire da RSA-576, quello indicato è il numero di cifre binarie. Il numero RSA-617 rappresenta un'eccezione, in quanto creato prima del cambiamento nel sistema di numerazione.
RSA-100 La fattorizzazione di RSA-100 fu annunciata il 1º aprile 1991 da Arjen K. Lenstra. La fattorizzazione venne effettuata in pochi giorni utilizzando il crivello quadratico su un MasPar computer.
La fattorizzazione di RSA-100 è la seguente:
RSA-100 = 15226050279225333605356183781326374297180681149613 80688657908494580122963258952897654000350692006139
RSA-100 = 37975227936943673922808872755445627854565536638199 × 40094690950920881030683735292761468389214899724061
La fattorizzazione di RSA-100 eseguita con il programma Msieve su un processore Athlon 64 da 2200 MHz richiede quattro ore.
RSA-110 RSA-110 è stato fattorizzato nell'aprile 1992 da Arjen K. Lenstra e Mark S. Manasse in circa un mese.
La fattorizzazione di RSA-110 è la seguente:
RSA-110 = 3579423417972586877499180783256845540300377802422822619 3532908190484670252364677411513516111204504060317568667
RSA-110 = 6122421090493547576937037317561418841225758554253106999 × 5846418214406154678836553182979162384198610505601062333
RSA-120 RSA-120 è stato fattorizzato nel giugno 1993 da Thomas Denny, Bruce A. Dodson, Arjen K. Lenstra, e Mark S. Manasse. Il calcolo ha richiesto circa tre mesi.T. Denny, B. Dodson, A. K. Lenstra, M. S. Manasse (1994), "On The Factorization Of RSA-120" .
La fattorizzazione di RSA-120 è la seguente:
RSA-120 = 227010481295437363334259960947493668895875336466084780038173 258247009162675779735389791151574049166747880487470296548479
RSA-120 = 327414555693498015751146303749141488063642403240171463406883 × 693342667110830181197325401899700641361965863127336680673013
RSA-129 RSA-129 non faceva propriamente parte del RSA Factoring challenge, ed è legato all'articolo di Martin Gardner sullo Scientific American dell'agosto 1977. È stato fattorizzato nell'aprile 1994 da un team diretto da Derek Atkins, Michael Gradd, Arjen K. Lenstra e Paul Lyland, usando approssimativamente 1600 computer con la collaborazione di circa 600 volontari connessi tramite Internet;Mark Janeba (1994), Factoring Challenge Conquered. Consultato il 16 aprile 2010. un premio di $100 USD è stato assegnato dalla RSA Security per la sua fattorizzazione, il quale è stato donato alla Free Software Foundation.
La fattorizzazione di RSA-129 è la seguente:
RSA-129 = 11438162575788886766923577997614661201021829672124236256256184293 5706935245733897830597123563958705058989075147599290026879543541
RSA-129 = 3490529510847650949147849619903898133417764638493387843990820577 × 32769132993266709549961988190834461413177642967992942539798288533
La fattorizzazione è stata calcolata usando l'algoritmo del crivello quadratico.
La sfida per la fattorizzazione includeva un messaggio da decriptare con RSA-129. Una volta decriptato usando la fattorizzazione il messaggio trovato fu "The Magic Words are Squeamish Ossifrage" (in italiano, Le parole magiche sono avvoltoio schizzinoso).
RSA-130 RSA-130 è stato fattorizzato il 10 aprile 1996 da un team diretto da Arjen K. Lenstra con Jim Cowie, Marije Elkenbracht-Huizing, Wojtek Furmanski, Peter L. Montgomery, Damian Weber e Joerg Zayer.Arjen K. Lenstra (12-04-1996), Fattorizzazione di RSA-130. Consultato il 16 giugno 2010.
La fattorizzazione di RSA-130 è la seguente:
RSA-130 = 18070820886874048059516561644059055662781025167694013491701270214 50056662540244048387341127590812303371781887966563182013214880557
RSA-130 = 39685999459597454290161126162883786067576449112810064832555157243 × 45534498646735972188403686897274408864356301263205069600999044599
La fattorizzazione è stata calcolata usando il Crivello dei campi di numeri e il polinomio:
5748302248738405200 x5 + 9882261917482286102 x4 - 13392499389128176685 x3 + 16875252458877684989 x2 + 3759900174855208738 x1 - 46769930553931905995
che ha una radice uguale a 12574411168418005980468 modulo RSA-130.
RSA-140 RSA-140 è stato fattorizzato il 2 febbraio 1999 da un team diretto da Herman J. J. te Riele e con la partecipazione di Stefania Cavallar, Bruce Dodson, Arjen K. Lenstra, Paul Leyland, Walter Lioen, Peter Montgomery, Brian Murphy e Paul Zimmermann.Herman te Riele (04-02-1999), Fattorizzazione di RSA-140 . Consultato il 16 giugno 2010RSA Laboratories, RSA-140 è stato fattorizzato! . Consultato il 16 giugno 2010.
La fattorizzazione di RSA-140 è la seguente:
RSA-140 = 2129024631825875754749788201627151749780670396327721627823338321538194 9984056495911366573853021918316783107387995317230889569230873441936471
RSA-140 = 3398717423028438554530123627613875835633986495969597423490929302771479 × 6264200187401285096151654948264442219302037178623509019111660653946049
La fattorizzazione è stata calcolata usando il Crivello dei campi di numeri.
RSA-150 RSA-150 venne ritirato anticipatamente dalla sfida dalla RSA Security; è stato comunque fattorizzato da Aoku e altri nel 2004 usando il Crivello dei campi di numeri.
La fattorizzazione di RSA-150 è la seguente:
RSA-150 = 155089812478348440509606754370011861770654545830995430655466945774312632703 463465954363335027577729025391453996787414027003501631772186840890795964683
RSA-150 = 348009867102283695483970451047593424831012817350385456889559637548278410717 × 445647744903640741533241125787086176005442536297766153493419724532460296199
RSA-155 RSA-155 è stato fattorizzato il 22 agosto 1999 da un team guidato da Herman te Riele comprendente Stefania Cavallar, Bruce Dodson, Arjen K. Lenstra, Walter Lioen, Peter L. Montgomery, Brian Murphy, Karen Aardal, Jeff Gilchrist, Gerard Guillerm, Paul Leyland, Joel Marchand, Francois Morain, Alec Muffett, Craig Putnam, Chris Putnam e Paul Zimmermann.Herman te Riele (26-08-1999), Nuovo record di fattorizzazione (annuncio della fattorizzazione di RSA-155). Consultato il 16 giugno.RSA Laboratories, RSA-155 è stato fattorizzato! . Consultato il 16 giugno.
La fattorizzazione di RSA-155 è la seguente:
RSA-155 = 109417386415705274218097073220403576120037329454492059909138421314763499842889 34784717997257891267332497625752899781833797076537244027146743531593354333897
RSA-155 = 102639592829741105772054196573991675900716567808038066803341933521790711307779 × 106603488380168454820927220360012878679207958575989291522270608237193062808643
La fattorizzazione è stata calcolata usando il Crivello dei campi di numeri ed ha richiesto circa 8000 MIPS-anni di calcoli, pari a circa 250.000 bilioni di istruzioni (2,5 × 1017 istruzioni).
RSA-160 RSA-160 è stato fattorizzato il 1º aprile 2003 da un gruppo di lavoro dell'Università di Bonn, in collaborazione con la Bundesamt für Sicherheit in der Informationstechnik (BSI, "Ufficio federale per la sicurezza informatica"). Il team conteneva Jens Franke, F. Bahr, Thorsten Kleinjung, M. Lochter e M. BöhmAnnuncio della fattorizzazione di RSA-160. Consultato il 29 giugno 2010.RSA Laboratories, RSA-160 è stato fattorizzato! . Consultato il 29 giugno 2010. e la fattorizzazione è stata calcolata usando il Crivello dei campi di numeri.
La fattorizzazione di RSA-160 è la seguente:
RSA-160 = 21527411027188897018960152013128254292577735888456759801704976767781331452188591 35673011059773491059602497907111585214302079314665202840140619946994927570407753
RSA-160 = 45427892858481394071686190649738831656137145778469793250959984709250004157335359 × 47388090603832016196633832303788951973268922921040957944741354648812028493909367
RSA-170 RSA-170 è stato fattorizzato il 29 dicembre 2009 da D. Bonenberger e M. Krone dell'università Fachhochschule Braunschweig/Wolfenbüttel.D. Bonenberger e M. Krone, RSA-170 Consultato il 29 giugno 2010.
La fattorizzazione di RSA-170 è la seguente:
RSA-170 = 2606262368413984492152987926667443219708592538048640641616478519185999962854206936145 0283931914514618683512198164805919882053057222974116478065095809832377336510711545759
RSA-170 = 3586420730428501486799804587268520423291459681059978161140231860633948450858040593963 × 7267029064107019078863797763923946264136137803856996670313708936002281582249587494493
La fattorizzazione è stata calcolata usando il Crivello dei campi di numeri.
RSA-576 RSA-576 è stato fattorizzato il 3 dicembre 2003 da J. Franke e T. Kleinjung all'Università di Bonn, usando il Crivello dei campi di numeri.Riproposizione dell'annuncio della fattorizzazione . Consultato il 29 giugno 2010.Eric W. Weisstein, articolo sulla fattorizzazione di RSA-576 su MathWorld. Consultato il 29 giugno 2010.RSA Laboratories, RSA-576 è stato fattorizzato! . Consultato il 2008-03-10.
La fattorizzazione di RSA-576 è la seguente:
RSA-576 = 188198812920607963838697239461650439807163563379417382700763356422988859715234665485319 060606504743045317388011303396716199692321205734031879550656996221305168759307650257059
RSA-576 = 398075086424064937397125500550386491199064362342526708406385189575946388957261768583317 × 472772146107435302536223071973048224632914695302097116459852171130520711256363590397527
RSA-180 RSA-180 è stato fattorizzato l'8 maggio 2010 da S. A. Danilov e I. A. Popovyan dell'Università statale di Mosca.S.A. Danilov e I.A. Popovyan, Report sulla fattorizzazione di RSA-180. Consultato il 29 giugno 2010.
RSA-180 = 1911479277189866096892294666314546498129862462766673548641885036388072607034 3679905877620136513516127813425829612810920004670291298456875280033022177775 2773957404540495707851421041
RSA-180 = 400780082329750877952581339104100572526829317815807176564882178998497572771950624613470377 × 476939688738611836995535477357070857939902076027788232031989775824606225595773435668861833
La fattorizzazione è stata calcolata usando il Crivello dei campi di numeri eseguito su 3 Intel Core i7.
RSA-190 RSA-190 (629 bits) è stato fattorizzato l'8 novembre 2010 da I. A. Popovyan from Moscow State University, Russia e A. Timofeev from CWI, Netherlands.
RSA-190 = 1907556405060696491061450432646028861081179759533184460647975622318915025587 1841757540549761551215932934922604641526300932385092466032074171247261215808