Nuovi primi di Mersenne, titaniche fattorizzazioni
e guerre crittografiche.
Fino a quando?

1 - Primi di Mersenne

Il 4 Settembre 2006 è stato scoperto il 44° numero primo di Mersenne, vedi il Blog Non smettono di stupire i primi di Mersenne!.

Nel 2007 nessun nuovo arrivato.

Nel biennio 2008 - 2009 sono stati trovati tre nuovi primi di Mersenne! Sono attualmente noti 47 primi di Mersenne, e - conseguentemente - 47 numeri perfetti pari.

Ecco gli ultimi arrivati:

     M₄₅ = 2^43112609-1,     12978189 cifre,     trovato il 23 Agosto 2008, su un computer della UCLA (USA)

     M₄₆ = 2^37156667-1,     11185272 cifre,     trovato il 6 Settembre 2008, da Hans-Michael Elvenich (Germania)

     M₄₇ = 2^42643801-1,     12837064 cifre,     trovato il 12 Aprile 2009, da Odd Magnar Strindmo (Norvegia)

(per un elenco completo vedere qui)

M₄₅ rimane ancora il più grande numero primo mai scoperto dall'uomo. Attendiamo il prossimo record. M₄₅ è stato inserito dal Time (al posto 29°) tra le 50 invenzioni migliori del 2008.
Si noterà che il Time chiama il nostro campione "il 46° numero di Mersenne". Il motivo sta nel fatto che il giornale li ordina per grandezza, mentre GIMPS li ordina secondo la data di scoperta. Ordinarli secondo grandezza comporta dovere a volte cambiare la numerazione. Per esempio, per gli utltimi tre, l'odine temporale A - B - C diventa, secondo la grandezza, B - C - A, e il Time dovrebbe oggi chiamare lo stesso numero "il 47° numero di Mersenne"
E' curioso il fatto che il Time parli di invenzione. Certamente nessun uomo ha inventato M₄₅, che se ne sta da sempre, e per sempre, nella sua celestiale dimora.
M₄₅ ha anche vinto il premio di 100000$ promesso dalla Electronic Frontier Foundation.

Ricordiamo che queste ricerche sono gestite dalla GIMPS (Great Internet Mersenne Prime Search), attraverso una rete di computer sparsi in tutto il mondo. Chiunque può iscriversi e scaricare l'apposito software. Il computer verrà utilizzato dal programma soltanto nei periodi di inattività. Per esempio, il norvegese Odd Magnar Strindmo che ha scoperto M₄₇ è un professionista dell'informatica che fin dal 1996 ha impegnato il tempo libero dei suoi computer per testare la primalità di ben 1440 candidati!

2 - Fattorizzazioni

Siamo in grado di trovare numeri primi con migliaia di cifre in pochi secondi, con apposito software, sul nostro piccolo personal computer. Ma nemmeno i matematici più brillanti, neanche con l'aiuto dei più grandi supercompter o della rete, sono capaci di fattorizzare numeri interi di qualche centinaio di cifre. Questo fatto, da solo, dimostra quanto poco sappiamo e quanto siamo deboli. E dovrebbe far riflettere i superbi.

Bisogna inoltre sottolineare il fatto che vengono impiegati ingenti capitali e le migliori menti in questa impresa.

Queste ricerche godono di ampi finanziamenti, perché sono applicabili alla crittoanalisi, la scienza che si occupa di trovare metodi per decifrare codici segreti e messaggi crittografati. Molti metodi crittografici, tra i quali come prototipo proprio RSA, si basano sulla difficoltà di fattorizzare i numeri interi. Chi desidera saperne di più può leggere questo breve articolo: - Collane colorate, Fermat, Eulero e la crittografia -, che scrissi nel 2008. Contiene anche un efficiente calcolatore (in java-script) che creai apposta per esercitarsi con RSA (funziona bene con Internet Explorer).

Si osservi che esistono metodi ovvi per fattorizzare qualsiasi numero N: per esempio basta dividerlo per tutti gli interi che lo precedono. O - assai meglio! - dividerlo per i primi che lo precedono. Se non abbiamo trovato un fattore prima della radice quadrata di N possiamo smettere: il numero è primo. I primi possono essere trovati con il classico crivello di Eratostene. Purtroppo questo tipo di attacco, detto di forza bruta, richiede tempi troppo lunghi per interi generici di centinaia di cifre, come quelli usati nelle chiavi crittografiche.

Quasi tutti i più efficaci metodi di fattorizzazione odierni si basano su una idea molto semplice, che risale a Legendre.
Sia N l'intero da fattorizzare. Se troviamo due interi x e y tali che N divide x² - y², senza dividere né x-y né x+y, allora il massimo comun divisore di N e di x+y è un fattore proprio di N (così come il massimo comun divisore di N e di x-y). Il massimo comun divisore di due numeri si calcola molto velocemente (chi desiderasse vedere da vicino questo famoso algoritmo e alcune sue applicazioni può leggere Diofanto, Euclide e le noci di cocco).
Rimane quindi da trovare una coppia (x,y) con la proprietà desiderata. E' principalmente su questo punto che i metodi differiscono.
Anche il Number Field Sieve (NFS), un crivello (o setaccio) assai sofisticato che si basa sulla teoria algebrica dei numeri, persegue lo stesso scopo, in maniera del tutto particolare e innovativa.
La comprensione completa, da parte della comunità matematica, del funzionamento concreto del NFS è ancora lontana. Prima di farlo partire si devono fissare i valori di alcuni parametri (in particolare due polinomi), essenziali per la riuscita finale dell'impresa. Ma non esiste ancora un metodo di selezione che si possa dimostare ottimale.

Ecco quanto dice uno dei massimi esperti

Vista la comprensione in un certo senso inadeguata di quello che stiamo cercando, questo settore è oggetto di intense ricerche. I metodi attuali richiedono molto tempo e pazienza, sono guidati dall'esperienza e aiutati dalla buona sorte.

Il 21 Maggio 2007 venne fattorizato il numero di Mersenne 2¹⁰³⁹ - 1 (313 cifre decimali). La fattorizzazione è:

2¹⁰³⁹ - 1 = p7 * p80 * p227.

Con pk denotiamo un numero primo di k cifre. Precisamante si ha

p7   = 5080711
p80  = 558536666199362912607492046583159449686465270184886376480100\
        52346319853288374753
p227 = 207581819464423827645704813703594695162939708007395209881208\
        387037927290903246793823431438841448348825340533447691122230\
        281583276965253760914101891052419938993341097116243589620659\
        72167481161749004803659735573409253205425523689

Per avere un'idea degli immensi progressi compiuti dai matematici, è utile confrontare il periodo di 158 anni con il tempo che occorrerebbe utilizzando un attacco di forza bruta. Chiamiamo N il numero 2¹⁰³⁹ - 1. Cominciamo a dividere N per i primi che lo precedono. Trascuriamo il tempo necessario a trovare i primi. Facciamo inoltre l'ipotesi, anche se evidentemente non realistica, che il nostro Athlon64 da 2,2 GHz esegua una divisione per ogni ciclo del suo clock. Il fattore più piccolo di N, p7, viene trovato dopo esattamente 353722 divisioni, ovvero dopo appena 16 decimillesimi di secondo. Quando arriveremo al secondo fattore p80, N sarà completamente fattorizzato, perché la parte rimanente è il terzo fattore primo p227. p80 è circa 5,6 x 10⁷⁹. Prima di p80 dobbiamo aspettarci più o meno p80/log(p80) numeri primi (vedi Il postulato di Bertrand e i primi di Ramanujan), ovvero 3 x 10⁷⁷ primi. Il muro insuperabile è esattamente questo esponente: 77. Sempre correndo alla stessa velocità, per arrivare a p80 dovremo attendere 1,3 x 10⁶⁸ anni. Se mettiamo insieme un miliardo di computer mille volte più veloci, miglioriamo di un fattore 10¹², e il tempo si riduce a 1,3 x 10⁵⁶ anni. L'età dell'universo è valutata in 13 x 10⁹ anni...

Torniamo alla crittografia. La RSA pubblicò anni fa una lista di interi, ordinati secondo il numero di bit, prodotti apposta per essere resistenti alla fattorizzazione. Questi numeri sono il prodotto di due primi della medesima grandezza (il caso più difficile) p e q. Vi sono poi altre richieste, per esempio p-1, p+1, q-1 e q+1 non devono essere prodotto di primi piccoli. Questi numeri sono denotati RSA-140 (140 bit), ... , RSA-160 (160 bit) ... etc. Per ogni intero c'era un premio, da consegnarsi al gruppo che lo avesse fattorizzato. Questa sfida matematica a premi è cessata nel 2007. Le fattorizzazioni però sono continuate.

Il 12 Dicembre 2009 è stato fattorizzato RSA-768 (232 cifre). Il numero è molto più piccolo del Mersenne 2¹⁰³⁹ - 1, che però era più facile da fattorizzare per la sua forma speciale. L'impresa ha richiesto 10²⁰ operazioni, pari a circa 2000 anni di calcolo di un singolo 2,2 GHz AMD Opteron, e tre anni di calcolo effettivo su una rete di computer.

Questo è RSA-768

12301866845301177551304949583849627207728535695953347921973224521517264005\
07263657518745202199786469389956474942774063845925192557326303453731548268\
50791702612214291346167042921431160222124047927473779408066535141959745985\
6902143413

p =
3347807169895689878604416984821269081770479498371376856891\
2431388982883793878002287614711652531743087737814467999489 

q = 
3674604366679959042824463379962795263227915816434308764267\
6032283815739666511279233373417143396810270092798736308917

p-1 = 28 * 11^2 * 13 * 7193 * 160378082551 * 7721565388263419219
      * 111103163449484882484711393053 * p47
p+1 = 2 * 3 * 5 * 31932122749553372262005491861630345183416467 * p71
q-1 = 22 * 359 * p113
q+1 = 2 * 3 * 23 * 41 * 47 * 239875144072757917901 * p90 

E' evidente che chiunque riuscisse a fattorizzare RSA-768 sul suo personal (senza partire da p e q .... :) in un tempo ragionevole, diventerebbe famoso e forse anche ricco. Dovrebbe però stare molto attento a non finire male, perché si tratta di un campo pericoloso, che interessa sia i servizi segreti di tutto il mondo che la criminalità organizzata e il terrorismo. Probabilmente l'unico modo per evitare di essere assassinato (o di vivere il resto della sua vita in un laboratorio segreto, sorvegliato a vista) sarebbe quello di rendere pubblico l'algoritmo immediatamente.

Gli autori della mirabolante fattorizzazione hanno pubblicato un rapporto sull'argomento pochi giorni fa, il 24 Gennaio 2010. Nella introduzione dicono

La fattorizzazione di un intero RSA di 1024 bit dovrebbe richiedere un tempo circa 1000 volte più grande di uno di 512 bit, mentre il rapporto dei tempi tra un RSA di 768 bit e uno di 512 bit è di diverse migliaia. Poichè sono passati circa dieci anni tra la fattorizzazione di RSA-512 e RSA-768, non è irragionevole pensare che un RSA di 1024 bit possa essere fattorizzato entro la prossima decade, mediante un progetto accademico del tipo di quello che abbiamo portato avanti. Quindi sarebbe opportuno cessare di usare la crittografia RSA con chiavi a 1024 entro tre o quattro anni.

• Lo spione S deve essere certo che il messaggio M che A sta per inviare a B sia di estrema importanza. Se A invia un M' ordinario, di normale amministrazione, S farà tanta fatica per nulla.
• S deve intercettare N, e, C.
• S non può intraprendere nessuna azione relativa al messaggio immediatamente, perché per conoscere M ci vuole tempo. Questo fa sì che la intercettazione effettuata risulta essere inutile per gran parte dei messaggi di tipo militare o commerciale.
• S dispone di una rete di computer e di uno staff di esperti.
• S attende qualche anno e scopre M.
• Il lavoro fatto non sarà di nessuna utilità per decifrare un altro messaggio in codice.

1. Personale infiltrato, o connivente con la parte avversa, o controllato in qualche modo dall'esterno.
2. Personale incompetente.
3. Cause oggettive, legate al software stesso o alla struttura fisica del sistema.

Un interessante esempio sono gli attacchi temporali a RSA (si estendono a molti altri sistemi). Quando la macchina decodifica un messaggio cifrato utilizzando la chiave segreta, i bit di quest'ultima possono a volte essere dedotti, con buona probabilità, da un esame dei tempi di lavoro della CPU. Questa possibilità dipende sia dalla struttura fisica della unità di calcolo che dalla ottimizzazione delle procedure di calcolo. Facciamo una semplicissima considerazione. La macchina deve calcolare M^d mod N, dove d, la chiave segreta, è un intero grande.
L'algoritmo di potenza veloce (nella sua versione più ovvia) esamina d un bit alla volta. Se il bit è 0, la CPU esegue un quadrato. Se il bit è 1, la CPU esegue lo stesso quadrato e una moltiplicazione. La differenza dei tempi di esecuzione può rivelare il bit.

Pensiamo alla crittografia quantistica. Essa si basa sul fatto che la semplice osservazione del sistema muta la distribuzione di probabilità degli eventi, e questo permette agli utenti di accorgersi in ogni caso della presenza di uno spione. Questo metodo è, a livello di teoria fisica, inattaccabile e perfetto. Ma tra teoria e pratica c'è sempre una differenza (direi un abisso, personalmente) e questa differenza è stata utilizzata, sfruttando le imperfezioni fisiche del ricevitore. Nel 2008 è stato attuato un attacco attivo di intercettazione-ritrasmissione su una linea protetta da crittografia quantistica (per notizie più recenti si veda per esempio quanto è accaduto durante il 26th Chaos Communication Congress, del Dicembre 2009).

Si assiste ad una gara senza fine, primi sempre più grandi, più sicurezza, fattorizzazioni sempre più veloci, meno sicurezza, nuovi scienziati, nuova crittografia, nuovi hackers, nuovi attacchi. La competizione è sostenuta da qualità umane (intelligenza, coraggio, scienza, creatività, operosità, ...) che potranno migliorare e incrementarsi anche per millenni, se l'umanità eviterà di autodistruggersi. Ma è resa possibile anche e, al momento, sostanzialmente, dai computer. Computer sempre più veloci. Ma fino a quando potranno migliorare le prestazioni dei computer?

3 - Fino a quando?

Viviamo sotto l'egida della legge di Moore, la quale prevede che ogni due anni si raddoppi la densità dei transistor nei circuiti integrati delle CPU. Questo è quanto in effetti accaduto negli ultimi trentacinque anni. Vi sono diversi motivi in base ai quali la legge di Moore non può essere vera. Il primo è di carattere assolutamente generale:

Un altro motivo è di tipo economico - sociologico. I costi delle progressive miniaturizzazioni diventano proibitivi, a fronte di un mercato che forse si sta orientando in modo differente. Più verso la rete, e la comunicazione che verso il calcolo. Bisogna però tener presente l'impatto dei giochi e dei video-game, i quali sono sempre più complessi e realistici, ma proprio per esserlo hanno bisogni di chip ultraveloci. Per non parlare del sistema militare, della sicurezza (crittografia ...), e degli scienziati che - comunque - desiderano superare i limiti del presente. Ci saranno forse macchine sempre più potenti riservate alla guerra e alla ricerca, e si fermeranno i nostri portatili?

Il terzo motivo è legato alla fisica della materia. La velocità della luce è finita e non superabile. Essa si muove a circa 3 x 10¹¹ mm (millimetri) al secondo (ho approssimato la velocità della luce a 300000 Km al secondo). L'informazione non può andare più veloce. Se un bit di informazione deve passare da un punto A a un punto B in 10^-10 secondi (frequenza di 10 GHz), A e B non possono distare più di 30 mm tra di loro. Si tratta quindi di mettere tutti i transistor necessari in un dischetto di un centimetro e mezzo di raggio. Al crescere della velocità, il raggio deve diminuire. Lo stesso Moore disse nel 2005 che la legge da lui proposta sarebbe giunta presto (nell'arco di una ventina di anni) a scontrarsi con la barriera invalicabile delle dimensioni atomiche.

Molti però ritengono che la legge di Moore corrisponderà alla realtà ancora per centinaia di anni. Gli scienziati pensano, ad esempio di utilizzare anche la terza dimensione. Per ora i circuiti sono su film sottilisissimi, praticamente bidimensionali. Si cerca ora di produrre strutture molecolari autoassemblanti in tre dimensioni. Oppure si potranno, forse, realizzare computer "di luce", basati su tecnologie laser, miliardi di volte più veloci di quelli attuali.

E la salvezza può venire proprio dall'ostacolo. Diventando sempre più piccoli si entra nel mondo subatomico, soggetto alle leggi della meccanica quantistica. A quel livello il computer ordinario non può più operare. E se allora il computer stesso divenisse quantico?

La teoria dei computer quantici è assai sviluppata. Per non dire della matematica. Se mai ci saranno computer quantici veri e potenti (al di là degli strumenti-giocattolo oggi esistenti) potranno funzionare con programmi fin d'ora pronti. Già nel 1996 il matematico Peter W. Shor descrisse in un articolo seminale un algoritmo che fattorizzerebbe velocemente i numeri interi su un "hypothetical quantum computer", per usare le sue stesse parole.

Sulla possibilità di produrre effettivamente un computer quantico e sulle sue presunte capacità di calcolo vi sono infinite discussioni e pareri discordi.

Un noto esperto, Scott Aaronson, ha scritto recentemente

E' perfettamente concepibile che la computazione quantica possa essere impossibile per una qualche ragione insita nei fondamenti stessi della realtà fisica.
Certo, sarebbe molto più interessante se essa fosse possibile, perché potrebbe mettere sottosopra le nostre concezioni di base riguardo al mondo fisico.
Il solo modo per saperlo è costruire un computer quantico.
Questo tentativo mi sembra scientificamente importante almeno quanto (diciamo) le ricerche sulla supersimmetria o il bosone di Higgs.

Io e ' compagni eravam vecchi e tardi
quando venimmo a quella foce stretta
dov' Ercule segnò li suoi riguardi

acciò che l'uom più oltre non si metta;
da la man destra mi lasciai Sibilia,
da l'altra già m'avea lasciata Setta.

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni, inviandomi una lettera a questo indirizzo: umberto.cerruti@unito.it. Nel soggetto scrivete 'mathblog'.