RSA Factoring Challenge

Da Wikipedia, l'enciclopedia libera.

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

n=pq.

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   non ancora fattorizzato
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   non ancora fattorizzato
RSA-704 212 704 $30,000 USD non ancora fattorizzato, premio ritirato
RSA-220 220 729   non ancora fattorizzato
RSA-230 230 762   non ancora fattorizzato
RSA-232 232 768   non ancora fattorizzato
RSA-768 232 768 $50,000 USD[5] 12 dicembre 2009 Thorsten Kleinjung et al.
RSA-240 240 795   non ancora fattorizzato
RSA-250 250 829   non ancora fattorizzato
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]

  1. ^ RSA Laboratories, The RSA Factoring Challenge. Pubblicato il 18 maggio 2007.
  2. ^ RSA Laboratories, The RSA Factoring Challenge FAQ. Pubblicato il 30 maggio 2007.
  3. ^ (EN) The RSA Factoring Challenge - This challenge is no longer active, rsa.com. URL consultato l'8 luglio 2009.
  4. ^ RSA-150 fu ritirato dalla sfida originale dall'RSA Security, ma è stato comunque fattorizzato.
  5. ^ 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]