Sicurezza della crittografia

Da quanto mi risulta, la sicurezza del metodo crittografico RSA (Rivest, Shamir, Adleman) si basa sulla difficoltà di scomporre in fattori numeri molto grandi. D'altra parte ho letto che tale sicurezza verrebbe meno se venisse dimostrata l'ipotesi di Riemann. Desidererei dei chiarimenti in merito, grazie
Laura Listanti
11 febbraio 2005
Sul numero di settembre 2004 di Le Scienze c'è un interessante articolo di Graham P. Collins sulla dimostrazione, da parte del matematico russo Grigory Perelman, della famosa congettura di Poincaré. Si tratta, come viene spiegato sulla stessa rivista, di uno dei sette "problemi del millennio", pubblicati sul sito del Clay Mathematics Institute. Per ognuno di essi viene offerto al solutore un premio di un milione di dollari.

Tra i magnifici sette appare, e non poteva essere altrimenti, la congettura di Riemann, più frequentemente detta ipotesi di Riemann.
Il matematico Louis de Branges de Bourcia, che lavora presso la Purdue University, sostiene di avere provato la verità dell'ipotesi di Riemann, ma la comunità degli esperti non è completamente convinta della validità della dimostrazione.

Sembra, dai commenti della stampa internazionale, che la possibilità dell'esistenza della dimostrazione faccia paura.
Qualche esempio:

Maths holy grail could bring disaster for internet
Guardian, 7 Settembre 2004.
Math problem solved=No Net transaction safe
Hindustan Times, 7 Settembre 2004.
Solution to arcane maths problem leads to doomsday projections
The Times of India, 11 Settembre 2004.

Vorrei cercare di spiegare, per quanto possibile brevemente e in modo semplice, da dove nascono questi timori e fino a che punto essi siano giustificati.

Tutto il commercio elettronico e i rapporti tra banche si fondano sulla crittografia. Quando, per esempio, acquistiamo qualcosa in rete, veniamo inseriti in un canale particolare, sicuro. Il male intenzionato che riuscisse a intercettare il documento che inviamo al server non sarebbe in grado di decifrare il numero della nostra carta di credito, perché esso è stato crittato.

Tutti i codici classici si basano su una chiave segreta. Il vostro computer e il server ospite si scambiano una chiave, che viene creata sul momento, nuova ogni volta. Per passarsi la chiave occorre evidentemente un protocollo di trasmissione che metta in cifra il messaggio senza avere a sua volta bisogno di effettuare uno scambio di chiavi, altrimenti si entrerebbe in un circolo vizioso.

I metodi usati in questa prima ed essenziale fase vengono detti "cifrari a chiave pubblica". Nel caso di un cifrario a chiave pubblica, chiunque può conoscere la chiave: non riuscirà lo stesso a rompere il codice.

In sostanza, tralasciando diverse altre componenti troppo tecniche, in una transazione commerciale on-line vengono utilizzati due codici: uno standard (si dice simmetrico) che necessita di una chiave segreta ed è molto veloce, l'altro a chiave pubblica, in genere più lento perché esegue calcoli pesanti. Per esempio, come codice simmetrico si potrebbe usare l'AES (Advanced Encription Standard) e come codice a chiave pubblica l'RSA (acronimo dei nomi dei suoi inventori: Rivest, Shamir e Adleman). Il lettore che desideri chiarimenti in proposito può consultare Crittografia e numeri primi.

È chiaro che se si rompe il codice a chiave pubblica, che custodisce la chiave del codice simmetrico, tutto viene a cadere.

Uno degli algoritmi più usati è proprio lo RSA. La sua forza si basa sul fatto che:

1) È facile trovare numeri primi grandi.
2) È difficile fattorizzare un intero prodotto di due numeri primi grandi.

Ovviamente, il termini "facile", "difficile" e "grande" sono relativi alla conoscenza e alla tecnologia disponibili. Attualmente sono grandi numeri primi di alcune centinaia di cifre decimali. Facile rappresenta un tempo di secondi e difficile di secoli.
Concludendo: l'intero sistema di sicurezza mondiale entrerebbe in gravi difficoltà se qualcuno trovasse un algoritmo veloce per la fattorizzazione di interi.
Che cosa c'entra tutto questo con la congettura di Riemann? Leggiamo le parole del professor Marcus du Sautoy, autore di L'enigma dei numeri primi, un bestseller pubblicato in Italia da Rizzoli:

L'intero commercio elettronico dipende dai numeri primi. Io ho descritto i primi come atomi: ciò che manca ai matematici è uno spettrometro di primi. I chimici hanno una macchina che, se ci mettete una molecola, vi dice di quali atomi è composta. I matematici non hanno inventato una versione analoga di essa. Se l'ipotesi di Riemann è vera, essa non produrrà di per sé uno spettrometro. Ma la sua dimostrazione potrebbe farci capire meglio il funzionamento dei numeri primi, e quindi la dimostrazione potrebbe essere trasformata in qualcosa che potrebbe produrre questo spettrometro di primi. Se ciò accadrà, metterà in ginocchio l'intero commercio elettronico nello spazio di una notte.

Si tratta di affermazioni prudenti, piene di "se" e "potrebbe". Ma la stampa, con la sua solita sensibilità, si è lanciata con entusiasmo nell'impresa di spaventare gli utenti, prospettando un futuro prossimo in cui utilizzare bancomat e carte di credito sarà impossibile.

In uno degli articoli citati si legge: Fino a che i numeri primi erano considerati casuali, poteveno essere utilizzati senza problemi nelle moderne applicazioni di cifratura dei dati, che vanno dalle transazioni bancarie e il commercio elettronico all'uso delle carte di credito e al trasferimento di denaro su internet. Una volta che la casualità sia provata falsa, però, finirà la cuccagna, nessun codice sarà più sicuro e nessuna transazione sarà protetta da intrusioni fraudolente. Alcuni pensano che per l'economia questo potrebbe essere l'equivalente di un asteroide che colpisca la Terra.

Siamo all'apocalisse! La matematica ha creato il paradiso della sicurezza informatica, dei codici inviolabili, e ora vuole distruggerlo! Ma, alla fine, che cosa dice mai questa congettura di Riemann? La forza è nella verità o nella dimostrazione?

Si ricorderà che alcuni sostengono che l'impatto della dimostrazione della congettura di Riemann (RH) sarebbe terribile.
Un tema ricorrente a favore di questo è che "i numeri primi non sarebbero più a caso". Su questo facciamo tre considerazioni.

La prima è di carattere, direi quasi, ontologico. La sequenza dei primi non può essere in nessun modo casuale, qualsiasi sia il significato che si voglia dare a questa frase, per il semplice fatto che è completamente determinata dalla struttura aritmetica dell'insieme dei numeri interi.
Prendete i numeri naturali 1, 2, 3, 4, 5..., cominciate a giocare con l'addizione (il prodotto non serve in modo diretto) ed eccoli lì: preziosi, luminosi e belli come le stelle del cielo!

La seconda è che, paradossalmente, la RH sembra puntare in direzione completamente opposta. Abbiamo visto che, se RH è vera, la distribuzione degli interi che sono il prodotto di un numero pari di primi o di un numero dispari di primi segue da vicino la distribuzione delle apparizioni di testa o croce in una sequenza abbastanza lunga di lanci di una moneta non truccata. Che cosa c'è di più casuale di questo?

La terza, come la prima, elimina la possibiltà che la successione dei primi sia casuale, perché presenta notevoli regolarità. Ne citiamo due:

1) Per ogni n, tra n e 2n c'è almeno un numero primo.
2) Tra n! + 2 e n! + n non ci sono numeri primi.

L'affermazione 1) è detta Postulato di Bertrand, matematico che la verificò nel 1845 per n fino a 3 000 000. Venne dimostrata da Tchebychef nel 1850. Il grande Erdös ne diede una dimostrazione assai elegante e semplice nel 1932. La tecnica di Erdös può essere estesa per dimostrare che dato qualsiasi k, esiste un N tale che, se n è maggiore di N, ci sono tra n e 2n almeno k primi.

La 2), sebbene interessante, è ovvia. Ricordiamo che n! è il prodotto degli interi tra 1 e n. Allora n! + 2 è divisibile per 2, n! + 3 è divisibile per 3, e così via fino a n! + n, che è divisibile per n.
Pur essendo poco più di una banalità la 2) dà un'argomentazione fortissima in sostegno della non-casualità della successione dei primi. In una successione casuale esisteranno spazi lunghi quanto si vuole privi di un certo simbolo, ma non sapremo mai dove si trovano. Dunque, certamente la successione dei primi non è casuale. Però, a partire da essa si generano sequenze con un comportamento apparentemente casuale, e la RH fornisce informazioni asintotiche sulla oscillazione di queste quantità.

Per concludere dirò che ritengo assai improbabile che la dimostrazione della RH possa portare a grandi rivoluzioni nel mondo delle comunicazioni riservate. Questo avverrebbe se, per esempio, facilitasse la fattorizzazione degli interi. Occorre però ricordare che da anni e anni vengono studiate tutte le possibili implicazioni logiche della RH.
Per esempio, è noto che se la RH fosse vera allora un certo test probabilistico di primalità darebbe risultati certi e veloci, mentre ora sono sì veloci ma sicuri solo entro un certo limite, che possiamo fissare. Per esempio un numero di 500 cifre che abbiamo trovato è dichiarato primo con una probabilità di 1 su 10 100 di non esserlo. Tutti i programmi di calcolo simbolico, come Maple o Mathematica, utilizzano combinazioni di test di questo genere. La differenza tra la certezza assoluta e la garanzia con probabilità 0.99999999... con cento 9 dopo il punto è, ad ogni effetto pratico, irrilevante.

Il problema della fattorizzazione è diverso. Essa avviene o non avviene, semplicemente. Che io sappia, nessuno ha ricavato metodi di fattorizzazione dall'ipotesi che RH sia vera. Non esiste un teorema del tipo: se vale RH allora, dato un intero N, faccio questo e questo e lo fattorizzo velocemente.
Se esistesse, lo si potrebbe usare: se N non si fattorizza nel tempo previsto la RH è falsa; se N si fattorizza siamo felici e rompiamo il codice RSA, anche senza avere dimostrato la RH.

Un teorema può avere un enunciato elegante ed essere esteticamente bello; può avere una dimostrazione difficile e profonda, ed essere per questo di grande interesse matematico. Però la sua forza, la sua efficacia, non sta nella dimostrazione ma nelle sue possibilità di applicazione, nelle conseguenze che da lui si possono trarre, e queste dipendono solo dalla sua verità.

Per approfondimenti consultare:
Blog matematico di Umberto Cerruti

Umberto Cerruti Dipartimento di Matematica, Università di Torino

© Copyright SISSA - Scuola Internazionale Superiore di Studi Avanzati - Trieste (Italy) - 2001-2011