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.