Numeri RSA
# Numeri RSA

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 2007 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".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:

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-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.

La fattorizzazione di RSA-120 è la seguente:

## 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; 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:

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.

La fattorizzazione di RSA-130 è la seguente:

La fattorizzazione è stata calcolata usando il Crivello dei campi di numeri e il polinomio:

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.

La fattorizzazione di RSA-140 è la seguente:

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-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.

La fattorizzazione di RSA-155 è la seguente:

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 × $10^{17}$ 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öhm e la fattorizzazione è stata calcolata usando il Crivello dei campi di numeri.

La fattorizzazione di RSA-160 è la seguente:

## RSA-170

RSA-170 è stato fattorizzato il 29 dicembre 2009 da D. Bonenberger e M. Krone dell'università Fachhochschule Braunschweig/Wolfenbüttel.

La fattorizzazione di RSA-170 è la seguente:

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.

La fattorizzazione di RSA-576 è la seguente:

## RSA-180

RSA-180 è stato fattorizzato l'8 maggio 2010 da S. A. Danilov e I. A. Popovyan dell'Università statale di Mosca.

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-640

RSA-640 è stato fattorizzato il 4 novembre 2005 da F. Bahr, M. Boehm, J. Franke e T. Kleinjung della Bundesamt für Sicherheit in der Informationstechnik (BSI), i quali hanno dunque vinto il premio di 20.000 dollari associato a tale numero. Lo stesso gruppo qualche mese prima aveva fattorizzato RSA-200.

La fattorizzazione di RSA-640 è la seguente:

Il calcolo ha richiesto circa 5 mesi su 80 CPU Opteron a 2.2 GHz ed è stato effettuato usando il Crivello dei campi di numeri.

## RSA-200

RSA-200 è stato fattorizzato il 9 maggio 2005 da F. Bahr, M. Boehm, J. Franke, e T. Kleinjung della Bundesamt für Sicherheit in der Informationstechnik (BSI). La potenza di calcolo utilizzata è paragonabile a quella di 75 anni di lavoro su un PC basato su processore Opteron a 2,2 GHz.

La fattorizzazione di RSA-200 è la seguente:

## RSA-210

RSA-210 è stato fattorizzato nel settembre 2013 da Ryan Propper.

## RSA-704

RSA-704 ha una lunghezza di 212 cifre decimali; ad esso la RSA Laboratories aveva associato un premio di 30.000 dollari, premio che è stato ritirato nel 2007 alla conclusione della sfida. È stato fattorizzato da Shi Bai, Emmanuel Thomé e Paul Zimmermann il 2 luglio 2012.

## RSA-220

RSA-220 ha una lunghezza di 220 cifre ed è stato fattorizzato da S. Bai, P. Gaudry, A. Kruppa, E. Thomé and P. Zimmermann il 13 maggio 2016.

## RSA-230

RSA-230 ha una lunghezza di 230 cifre ed è stato fattorizzato da Samuel S. Gross il 15 agosto 2018.

## RSA-232

RSA-232 ha una lunghezza di 232 cifre decimali ed è stato fattorizzato il 17 febbraio 2020 da N. L. Zamarashkin, D. A. Zheltkov e S. A. Matveev.

## RSA-768

RSA-768 ha una lunghezza di 232 cifre decimali ed è stato fattorizzato il 12 dicembre 2009 da Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen K. Lenstra, Emmanuel Thomé, Pierrick Gaudry, Alexander Kruppa, Peter Montgomery, Joppe W. Bos, Dag Arne Osvik, Herman te Riele, Andrey Timofeev, e Paul Zimmermann.

## RSA-240

RSA-240 è stato fattorizzato il 2 dicembre 2019 da Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, e Paul Zimmermann.

## RSA-250

RSA-250 è stato fattorizzato il 28 febbraio 2020 da Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, e Paul Zimmermann.

## RSA-260

RSA-260 non è ancora stato fattorizzato.

## RSA-270

RSA-270 non è ancora stato fattorizzato.

## RSA-896

RSA-896 ha una lunghezza di 270 cifre decimali e non è ancora stato fattorizzato; ad esso la RSA Laboratories aveva associato un premio di 75.000 dollari, premio che è stato ritirato nel 2007 alla conclusione della sfida.

## RSA-280

RSA-280 non è ancora stato fattorizzato.

## RSA-290

RSA-290 non è ancora stato fattorizzato.

## RSA-300

RSA-300 non è ancora stato fattorizzato.

## RSA-309

RSA-309 non è ancora stato fattorizzato.

## RSA-1024

RSA-1024 ha una lunghezza di 309 cifre decimali e non è ancora stato fattorizzato; ad esso la RSA Laboratories aveva associato un premio di 100.000 dollari, premio che è stato ritirato nel 2007 alla conclusione della sfida.

L'eventuale fattorizzazione di RSA-1024 avrebbe importanti conseguenze sulla sicurezza di molti messaggi crittati con l'algoritmo di crittografia a chiave pubblica RSA; infatti attualmente la lunghezza delle chiavi comunemente usate con tale algoritmo è di 1024 bits.

## RSA-310

RSA-310 non è ancora stato fattorizzato.

## RSA-320

RSA-320 non è ancora stato fattorizzato.

## RSA-330

RSA-330 non è ancora stato fattorizzato.

## RSA-340

RSA-340 non è ancora stato fattorizzato.

## RSA-350

RSA-350 non è ancora stato fattorizzato.

## RSA-360

RSA-360 non è ancora stato fattorizzato.

## RSA-370

RSA-370 non è ancora stato fattorizzato.

## RSA-380

RSA-380 non è ancora stato fattorizzato.

## RSA-390

RSA-390 non è ancora stato fattorizzato.

## RSA-400

RSA-400 non è ancora stato fattorizzato.

## RSA-410

RSA-410 non è ancora stato fattorizzato.

## RSA-420

RSA-420 non è ancora stato fattorizzato.

## RSA-430

RSA-430 non è ancora stato fattorizzato.

## RSA-440

RSA-440 non è ancora stato fattorizzato.

## RSA-450

RSA-450 non è ancora stato fattorizzato.

## RSA-460

RSA-460 non è ancora stato fattorizzato.

## RSA-1536

RSA-1536 ha una lunghezza di 463 cifre decimali e non è ancora stato fattorizzato; ad esso la RSA Laboratories aveva associato un premio di 150.000 dollari, premio che è stato ritirato nel 2007 alla conclusione della sfida.

## RSA-470

RSA-470 non è ancora stato fattorizzato.

## RSA-480

RSA-480 non è ancora stato fattorizzato.

## RSA-490

RSA-490 non è ancora stato fattorizzato.

## RSA-500

RSA-500 non è ancora stato fattorizzato.

## RSA-617

RSA-617 non è ancora stato fattorizzato. Ha una lunghezza di 2048 cifre binarie.

## RSA-2048

RSA-2048 ha una lunghezza di 617 cifre decimali e non è ancora stato fattorizzato. È il più grande numero RSA e ad esso era associato il premio di valore più elevato, 200.000 dollari. Tale premio è stato ritirato nel 2007 alla conclusione della sfida. Probabilmente RSA-2048 non sarà fattorizzato per ancora molti anni, a meno di considerevoli progressi nella velocità di fattorizzazione dei numeri interi o nella potenza computazionale.

