Gli inventori di RSA avevano anche preparato una sfida per i lettori: dato il sistema di codifica secondo il quale A = 01, B = 02, e così via fino a Z = 26 e spazio = 00; data la seguente chiave pubblica (n,e):
n = 11438162575788886766923577997614661201021829672124236256256184293
5706935245733897830597123563958705058989075147599290026879543541,e = 9007;
dato il testo cifrato
c = 9686961375462206147714092225435588290575999112457431987469512093
0816298225145708356931476622883989628013391990551829945157815154;ricavare il testo in chiaro.
Già nel 1976 il matematico Richard Guy scrisse:
“Sarei molto sorpreso se qualcuno riuscisse a fattorizzare numeri delle dimensioni di 1080, senza utilizzare forme particolari, nel presente secolo”.
Nel 1977 Rivest, in una lettera a Martin Gardner, stimò che il tempo necessario per fattorizzare un numero di 125 cifre che è il prodotto di due numeri primi di 63 cifre dovesse essere almeno di 40 quadrilioni di anni (qualunque significato diamo alla parola quadrilione, è comunque un sacco di tempo). Tempo calcolato sulla base del miglior algoritmo di fattorizzazione noto all'epoca, e supponendo che un singolo prodotto ab modulo c potesse essere calcolato in un nanosecondo (e questo era fantascienza).
Sicuri del fatto che il loro codice non sarebbe mai stato decrittato, gli inventori di RSA offrirono un premio di 100 dollari al primo che fosse riuscito a trovare il testo del messaggio in chiaro.
Nel 1993 un gruppo di matematici, composto da Atkins, Graff, Lenstra e Leyland, cominciarono a pensare al modo di fattorizzare il numero n in tempi umani. Per prima cosa ricalcolarono la stima fatta da Rivest nel 1977, e trovarono un errore. Probabilmente Rivest aveva contato male il numero degli zeri, perché il tempo stimato dal gruppo era di soli 4 quadrilioni di anni, e non 40, per un totale di circa 1.3·1032 moltiplicazioni modulari.
Successivamente al 1977, però, la ricerca aveva compiuto grossi passi avanti nella fattorizzazione dei numeri interi, e allo stesso tempo la velocità dei computer era aumentata enormemente. Con hardware costruito ad hoc e tecniche di pipelining, con ritardi di gate di circa 10 picosecondi, si sarebbe forse riusciti ad arrivare al record di una moltiplicazione modulare ogni nanosecondo. In questo caso, utilizzando il nuovo metodo di fattorizzazione che utilizza le curve ellittiche (scoperto da uno dei quattro matematici, Lenstra), il gruppo stimò un tempo di circa due mesi: 240 quadrilioni di volte più veloce rispetto alla stima di Rivest, per un totale di circa 5·1015 moltiplicazioni modulari. E tutto grazie al progresso nelle tecniche di fattorizzazione.
Su un computer normale, però, il tempo di calcolo era ancora proibitivo: la stima era di circa 15000 anni su una workstation Sparc 10.
Stime fatte utilizzando un altro metodo di fattorizzazione, il crivello quadratico, abbassarono ulteriormente il tempo di calcolo: circa 120 anni su una workstation Sparc 10. Per rendere i calcoli indipendenti dalla macchina, si usa un'unità di misura diversa, il mips·anno. Un mips corrisponde a un milione di operazioni elementari per secondo, e quindi un mips·anno corrisponde al numero di operazioni elementari che una macchina con potenza uguale a 1 mips può effettuare in un anno. La stima per fattorizzare n era di circa 4200 mips·anno. Ce la potevano fare.
Non da soli, naturalmente, ma con l'aiuto di uno dei più grandi gruppi di ricerca dell'epoca: il calcolo distribuito su internet.
Le stime erano le seguenti: servivano circa 8 milioni di relazioni, ognuna delle quali occupava circa 350 byte. Il programma doveva tenere in memoria un numero di fattori compreso tra 400000 e 600000, per un totale di 8 MByte. In tutto, il programma utilizzava 10.5 MByte di memoria. All'epoca molti computer affacciati a internet erano dotati di meno di 16 MByte, e molti ne avevano meno di 8.
Atkins e Leyland compilarono il loro programma per il maggior numero possibile di workstation e PC. Il gruppo ottenne in prestito un file server del MIT per la durata del progetto: era un DEC 5000/240 con 32 MByte di RAM e due dischi da 985 MByte. Il terzo disco fu aggiunto poco tempo dopo.
Il 19 agosto 1993 il progetto pubblicò la sua prima richiesta di aiuto nella number theory net, il 23 agosto scrisse ai cypherpunk e al PGP development group, e infine il 24 agosto nei newgroup alt.hackers, alt.security, alt.security.pgp, alt.security.ripem, comp.arch, comp.security.misc, sci.crypt, sci.math (questo, almeno, è quanto riporta l'articolo scritto dal gruppo, ma google groups riporta un'alta data).
Il codice venne fatto girare su macchine molto diverse tra loro: c'erano degli 80386sx a 16MHz e dei Cray C90. Non si riuscì a compilare il codice per una Thinking Machine CM-5, mentre una azienda americana riuscì a farlo girare su due fax (sì, non è sbagliato, due fax).
Per poter fare girare il codice sul maggior numero di macchine possibile, venne ridotto lo spazio di memoria necessario al programma per girare: si passò da 10.5 a 6.5Mbyte, ma il programma dimezzò la sua velocità. Nonostante questo rallentamento, il bilancio fu positivo, perché poterono partecipare molti computer che altrimenti non avrebbero avuto le caratteristiche necessarie.
Parteciparono 600 persone e 1600 computer, una piccola frazione di tutte la capacità di calcolo disponibile. Se tutta la potenza di internet fosse stata disponibile, n sarebbe stato fattorizzato in sole tre ore. L'ottanta per cento del lavoro fu svolto dai volontari, il restante venti per cento da alcuni computer MasPar gestiti da Lenstra e collaboratori.
Il 21 marzo 1994 il coordinamento del progetto aveva raccolto il numero necessario di relazioni, e il 22 marzo venne spedito a tutti i contributori il messaggio di cease and desist. Dopo 220 giorni di setacciamento, il 26 marzo fu fatto il conteggio finale: c'erano 8424486 relazioni da analizzare. Una parte di queste relazioni fu salvata su nastro magnetico e spedita da Atkins a Lenstra mediante il normale servizio postale notturno. Un'altra parte fu trasferita via ftp.
I dati vennero analizzati da un computer MasPar MP-1: dopo 45 ore, alle 18:15 UT del 2 aprile 1994, venne trovata la fattorizzazione di n:
n = 3490529510847650949147849619903898133417764638493387843990820577 ·
32769132993266709549961988190834461413177642967992942539798288533
Ecco l'annuncio.
Il messaggio cifrato da Rivest venne quindi decifrato. Il testo in chiaro era:
200805001301070903002315180419000118050019172105011309190800151919090618010705
che, tradotto secondo la codifica utilizzata da Rivest, diventa:
THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE
Vennero usati dai 4000 ai 6000 mips·anno.
(Tutta la storia è raccontata qui)
Nessun commento:
Posta un commento