RSA Factoring Challenge
Lo RSA Factoring Challenge fu una sfida proposta da RSA Laboratories dal 18 marzo 1991 per incoraggiare la ricerca nel campo della teoria dei numeri computazionale, in particolare nella fattorizzazione di grandi numeri naturali. Fu pubblicata una lista di semiprimi (numeri che hanno esattamente due fattori primi) conosciuti come numeri RSA, con un premio in denaro per chi fosse riuscito a fattorizzarli. Il più piccolo di questi, un numero con 100 cifre decimali chiamato RSA-100, fu fattorizzato in pochi giorni, ma molti dei numeri più grossi non sono stati ancora fattorizzati, e ci si aspetta che rimarranno tali ancora per un tempo relativamente lungo.
Il concorso finì nel 2007.[1] Secondo la RSA "Ora che l'industria ha una comprensione molto più avanzata della forza crittanalitica dei comuni algoritmi a chiave simmetrica e a chiave pubblica, queste sfide non saranno più attive."[2]
Questa sfida ha lo scopo di sondare lo "stato dell'arte" nella fattorizzazione di interi. Una primaria applicazione è la scelta della lunghezza della chiave per l'algoritmo RSA di crittografia a chiave pubblica; infatti, i risultati sulla fattorizzazione di questi numeri aiutano a capire quali dimensioni delle chiavi sono ancora sicure e per quanto tempo. Dato che RSA Laboratories produce prodotti basati sull'algoritmo RSA, questa sfida fu lanciata per spingere la comunità scientifica ad affrontare il problema della fattorizzazione di semiprimi grandi, con l'obiettivo di provare la sicurezza di tale algoritmo.
I primi numeri RSA generati, dal RSA-100 al RSA-500, furono chiamati in accordo con il numero di cifre decimali; tuttavia, in seguito, dal numero RSA-576, si contò il numero di cifre binarie. Un'eccezione è per il numero RSA-617, che fu creato prima del cambiamento nel sistema di numerazione.
Matematica[modifica | modifica wikitesto]
Sia n un numero RSA. Esistono e sono unici due numeri primi p e q tali che
Il problema è trovare questi due numeri primi, conoscendo solo n.
Premi e annotazioni[modifica | modifica wikitesto]
La seguente tabella fornisce una visione dei numeri RSA. Il concorso è terminato nel 2007.[3]
- Il numero con cui sono catalogati i numeri RSA su sfondo rosa è espresso in base 10, mentre su sfondo giallo è espresso in base 2.
| Numero RSA | Cifre decimali | Cifre binarie | Premio offerto | Data fattorizzazione | Fattorizzato da |
|---|---|---|---|---|---|
| RSA-100 | 100 | 330 | Aprile 1991 | Arjen K. Lenstra | |
| RSA-110 | 110 | 364 | Aprile 1992 | Arjen K. Lenstra e M.S. Manasse | |
| RSA-120 | 120 | 397 | Giugno 1993 | T. Denny et al. | |
| RSA-129 | 129 | 426 | $100 USD | Aprile 1994 | Arjen K. Lenstra et al. |
| RSA-130 | 130 | 430 | 10 aprile 1996 | Arjen K. Lenstra et al. | |
| RSA-140 | 140 | 463 | 2 febbraio 1999 | Herman te Riele et al. | |
| RSA-150[4] | 150 | 496 | 16 aprile 2004 | Kazumaro Aoki et al. | |
| RSA-155 | 155 | 512 | 22 agosto 1999 | Herman te Riele et al. | |
| RSA-160 | 160 | 530 | 1º aprile 2003 | Jens Franke et al., Università di Bonn | |
| RSA-170 | 170 | 563 | 29 dicembre 2009 | D. Bonenberger and M. Krone | |
| RSA-576 | 174 | 576 | $10,000 USD | 3 dicembre, 2003 | Jens Franke et al., Università di Bonn |
| RSA-180 | 180 | 596 | 8 maggio 2010 | S. A. Danilov and I. A. Popovyan, Università statale di Mosca | |
| RSA-190 | 190 | 629 | 8 novembre 2010 | A. Timofeev and I. A. Popovyan | |
| RSA-640 | 193 | 640 | $20,000 USD | Novembre, 2005 | Jens Franke et al., Università di Bonn |
| RSA-200 | 200 | 663 | 9 maggio 2005 | Jens Franke et al., Università di Bonn | |
| RSA-210 | 210 | 696 | 26 settembre 2013 | Ryan Propper | |
| RSA-704 | 212 | 704 | $30,000 USD | 2 luglio 2012 | Shi Bai, Emmanuel Thomé and Paul Zimmermann |
| RSA-220 | 220 | 729 | 13 maggio 2016 | S. Bai, P. Gaudry, A. Kruppa, E. Thomé and P. Zimmermann | |
| RSA-230 | 230 | 762 | 15 agosto 2018 | Samuel S. Gross, Noblis, Inc. | |
| RSA-232 | 232 | 768 | 17 febbraio 2020 | N. L. Zamarashkin, D. A. Zheltkov e S. A. Matveev | |
| RSA-768 | 232 | 768 | $50,000 USD[5] | 12 dicembre 2009 | Thorsten Kleinjung et al. |
| RSA-240 | 240 | 795 | 2 dicembre 2019 | Fabrice Boudot et al. | |
| RSA-250 | 250 | 829 | 28 febbraio 2020 | Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, Paul Zimmermann | |
| RSA-260 | 260 | 862 | non ancora fattorizzato | ||
| RSA-270 | 270 | 895 | non ancora fattorizzato | ||
| RSA-896 | 270 | 896 | $75,000 USD | non ancora fattorizzato, premio ritirato | |
| RSA-280 | 280 | 928 | non ancora fattorizzato | ||
| RSA-290 | 290 | 962 | non ancora fattorizzato | ||
| RSA-300 | 300 | 995 | non ancora fattorizzato | ||
| RSA-309 | 309 | 1024 | non ancora fattorizzato | ||
| RSA-1024 | 309 | 1024 | $100,000 USD | non ancora fattorizzato, premio ritirato | |
| RSA-310 | 310 | 1028 | non ancora fattorizzato | ||
| RSA-320 | 320 | 1061 | non ancora fattorizzato | ||
| RSA-330 | 330 | 1094 | non ancora fattorizzato | ||
| RSA-340 | 340 | 1128 | non ancora fattorizzato | ||
| RSA-350 | 350 | 1161 | non ancora fattorizzato | ||
| RSA-360 | 360 | 1194 | non ancora fattorizzato | ||
| RSA-370 | 370 | 1227 | non ancora fattorizzato | ||
| RSA-380 | 380 | 1261 | non ancora fattorizzato | ||
| RSA-390 | 390 | 1294 | non ancora fattorizzato | ||
| RSA-400 | 400 | 1327 | non ancora fattorizzato | ||
| RSA-410 | 410 | 1360 | non ancora fattorizzato | ||
| RSA-420 | 420 | 1393 | non ancora fattorizzato | ||
| RSA-430 | 430 | 1427 | non ancora fattorizzato | ||
| RSA-440 | 440 | 1460 | non ancora fattorizzato | ||
| RSA-450 | 450 | 1493 | non ancora fattorizzato | ||
| RSA-460 | 460 | 1536 | non ancora fattorizzato | ||
| RSA-1536 | 463 | 1536 | $150,000 USD | non ancora fattorizzato, premio ritirato | |
| RSA-470 | 470 | 1559 | non ancora fattorizzato | ||
| RSA-480 | 480 | 1593 | non ancora fattorizzato | ||
| RSA-490 | 490 | 1626 | non ancora fattorizzato | ||
| RSA-500 | 500 | 1659 | non ancora fattorizzato | ||
| RSA-617 | 617 | 2048 | non ancora fattorizzato | ||
| RSA-2048 | 617 | 2048 | $200,000 USD | non ancora fattorizzato, premio ritirato | |
Note[modifica | modifica wikitesto]
- ^ RSA Laboratories, The RSA Factoring Challenge Archiviato il 7 maggio 2013 in Internet Archive.. Pubblicato il 18 maggio 2007.
- ^ RSA Laboratories, The RSA Factoring Challenge FAQ Archiviato il 13 febbraio 2010 in Internet Archive.. Pubblicato il 30 maggio 2007.
- ^ (EN) The RSA Factoring Challenge - This challenge is no longer active, su rsa.com. URL consultato l'8 luglio 2009 (archiviato dall'url originale il 7 maggio 2013).
- ^ RSA-150 fu ritirato dalla sfida originale dall'RSA Security, ma è stato comunque fattorizzato.
- ^ RSA-768 è stato fattorizzato successivamente alla chiusura della sfida; di conseguenza il premio non è stato consegnato.
Voci correlate[modifica | modifica wikitesto]
Collegamenti esterni[modifica | modifica wikitesto]
- (EN) RSA Security: The new RSA factoring challenge, su rsasecurity.com. URL consultato il 10 maggio 2006 (archiviato dall'url originale il 26 aprile 2006).
- (EN) pacchetto per Mathematica sui numeri RSA, su mathworld.wolfram.com.
- (EN) La sfida originale su sci.crypt [collegamento interrotto], su google.com.
