I Numeri Primi, il World Wide Web e la Crittografia

Ogni qualvolta eseguite una transazione commerciale su internet, vi affidate alla teoria matematica dei numeri primi per mantenere la transazione stessa in condizioni di sicurezza: cerchiamo di capire come.

LA STORIA

Dal momento in cui la gente cominciò ad inviarsi messaggi emerse il seguente problema: come impedire che una persona non autorizzata si impadronisca  del messaggio e venga a conoscenza del suo contenuto? La risposta sta nel codificare (Criptare) il messaggio stesso.

Oggi i sistemi di crittografia consistono essenzialmente di due componenti: una procedura di crittografia e una “chiave”. La prima è solitamente un programma per computer oppure un chip ad hoc, la seconda, la chiave, è un numero segreto. Per crittografare il messaggio, il sistema necessita non solo del messaggio stesso, ma anche della chiave.  Nei primi sistemi di crittografia con chiave, mittente e ricevente concordavano in anticipo una chiave segreta, che poi usavano per scambiarsi messaggi; ovviamente una situazione del genere non è adatta al commercio su internet, contesto nel quale spesso il messaggio deve arrivare dall’altra parte del mondo per raggiungere un destinatario che il mittente non ha mai incontrato di persona.

Queste premesse portarono alla nascita dell’attuale crittografia a chiave pubblica o asimmetrica nella quale la cifratura richiede non una ma due chiavi: una per la codifica, chiamata chiave pubblica, che è a disposizione di chiunque e ci permette di criptare il messaggio ma non di decriptarlo per inviarlo al destinatario interessato; l’altra per la decodifica del messaggio, chiamata chiave privata, che solo il legittimo destinatario del messaggio conosce. Questo è il funzionamento alla base dell’odierno standard di Crittografia. Vediamo quali concetti matematici ne sono alla base.

LA MATEMATICA CHE C’E’ DIETRO

Oggi la cifratura RSA salvaguarda gran parte delle transazioni che avvengono su Internet. La cosa straordinaria è che la matematica che rende possibile questo sistema di crittografia a chiave pubblica è decisamente semplice. Tutto si basa su quattro concetti matematici: Numero Primo, Fattorizzazione, Aritmetica Modulare e Piccolo teorema di Fermat.

1) Un numero primo è un numero naturale che sia divisibile solo per se stesso e per uno;

2) Fattorizzare un numero significa trovare un insieme di numeri tali che il loro prodotto sia il numero scelto in partenza; se ad esempio scegliamo il numero 6 (che non è primo) allora i suoi fattori sono 3 e 2 poiché 3×2=6 . Riuscite ad immaginare già da ora quanto più complesso sarebbe fattorizzare il numero 1544782 (?!?)

3) L’aritmetica modulare è un ramo della matematica che però conosciamo noi tutti molto bene, la usiamo tutte le volte che controlliamo l’ora sul nostro orologio, proprio per questo è anche chiamata aritmetica dell’orologio. Per esempio, in un orologio di 12 ore sappiamo che 9 + 5 = 2 poiché 5 ore dopo le 9 del mattino saranno le 2 del pomeriggio secondo la regola 9 + 5 = 14 allora 14/12 = 1 resto 2 e il resto è quello che dobbiamo prendere in considerazione per avere la nostra uguaglianza.

4) Piccolo teorema di Fermat, non facciamoci spaventare dal nome, afferma semplicemente che, se si prende un “orologio” (di quelli visti al punto precedente) con un numero primo di ore, e prendo un numero su questo calcolatore ad orologio e lo moltiplico per se stesso un numero primo di volte, si ottiene sempre il numero da cui si è partiti. Questo sarà successivamente necessario per la decodifica del messaggio, in particolare con la formula generalizzata del teorema (TFE): (p-1) x (q-1) +1 = D quindi D è il passo di ripetizione dell’orologio. Invece, p e q sono due numeri primi dove N è il loro prodotto (p x q=N) ed è la chiave pubblica utilizzata per la codifica sul Web.

IL METODO

La Codifica

Quando un cliente piazza un ordine sul sito di un’azieda, l’azienda gli comunica quante ore usare nel suo calcolatore ad orologio. Per scegliere questo numero di ore, l’azienda prende due grandi numeri primi, p e q, ciascuno composto da 60 cifre circa (ma posso essere anche di più). Quindi li moltiplica per ottenere un terzo numero, N=p x q. Il numero di cifre dell’orologio risulterà perciò enorme, fino ad un massimo di 120 cifre. Nonostante il numero N sia reso pubblico, i due numeri primi p e q che lo compongono sono segreti.

Dopodiché ogni cliente riceve un secondo numero E chiamato numero di codifica ed è pubblico proprio come lo è N, il numero di ore sul “quadrante” del calcolatore ad orologio. Per cifrare il proprio numero di carta di credito C, il cliente lo eleva alla potenza E, cioè moltiplica il numero della carta di credito per se stesso E volte sul calcolatore a orologio reso pubblico dal sito web. Immaginate che E sia il numero di scozzate che un prestigiatore esegue per nascondere, nel mazzo composto di N carte, la carta da voi scelta, cioè il numero della vostra carta di credito.

La Decodifica

Che cosa rende questa procedura tanto sicura? Dopo tutto qualsiasi hacker può vedere il numero cifrato della carta di credito mentre viaggia nel cyberspazio, e può cercare la chiave pubblica dell’azienda (N per intenderci) ed anche l’istruzione di elevamento alla E (C alla E modulo N). Tutto quello che l’hacker deve fare per decifrare il codice è trovare un numero che, moltiplicato E volte per se stesso nell’oroglogio di N ore, fornisce il numero di carta di credito. Ma questo è molto, molto difficile. La crescita, mentre si moltiplica per se stesso il numero di carta di credito nella codifica, non è lineare nel calcolatore ad orologio e si perde subito il punto di partenza a causa dell’utilizzo di numeri primi. Passare in rassegna tutte le possibili soluzioni con un computer significherebbe impiegare molte centinaia di anni.

L’azienda, dal canto suo, riesce a recuperare il numero della carta di credito grazie al piccolo teorema di Fermat, infatti, moltiplicando il numero cifrato della carta di credito per se stesso altre D volte, grazie all’andamento periodico scoperto dal matematico (Fermat appunto), si riesce a ritornare al punto di partenza cioè il numero NON cifrato della carta di credito. Ma D è un numero ricavabile solo se si conoscono i due numeri primi p e q  secondo la formula vista in precedenza quando si parlava del piccolo teorema di Fermat (Punto 4).

CONCLUSIONI: L’IMPORTANZA DELL’IPOTESI DI RIEMANN

Come abbiamo visto, il solo modo per sapere quanto bisognerà aspettare per vedere la sequenza ricominciare su un orologio con N= p x q ore sul quadrante è conoscere i valori di entrambi i numeri primi p e q attraverso i quali ricavare la chiave di decodifica D. Tuttavia, sebbene i due numeri p e q siano stati tenuti segreti, il loro prodotto N è stato reso pubblico. La sicurezza della cifratura RSA si basa perciò sulla difficoltà di fattorizzare N. Difficoltà alla quale, si pensa, saprà rispondere la dimostrazione all’Ipotesi di Riemann.

APPROFONDIMENTI:

Per approfondire l’argomento, grazie alla cortesia di Cristiano Teodoro, a disposizione per il download trovate listato di codice e relativa spiegazione riguardante la generazione di chiavi private nell’algoritmo di criptatura RSA a chiave pubblica.

In effetti mi rendo perfettamente conto che è un’ardua impresa spiegare e divulgare in termini semplici una materia così ostica come è quella della crittografia. Confido in un vostro dialogo costruttivo in merito. Se volete, i commenti sono a disposizione!

10 commenti su “I Numeri Primi, il World Wide Web e la Crittografia

  1. Pingback: Paolo Bee

  2. annarita

    Articolo superbo, Paolo! Grazie infinite per questo regalo originale. Lo segnalerò, senza ombra di dubbio, il 14 ottobre nel post, che dedicherò su Matem@ticaMente alla 6° edizione del Carnevale della Matematica.

    baciotti gongolanti
    annarita :)

  3. Cristiano

    Bravo: la cifratura RSA per i comuni mortali :-D

    Non sei assolutamente risultato prolisso perchè hai saputo tenere viva l’attenzione del lettore con esempi semplici e concreti.

    La strada è questa (e sai a cosa mi riferisco) ;)

  4. Paolo Bee Autore articolo

    @ annarita:
    contraccambio il baciotto gongolante!!

    @ Daniele Verzetti, Rockpoeta:
    Grazie, sempre troppo gentile!

    @ Cristiano:
    Si, era quello il mio intento: spiegare nel modo più semplice possibile questa parte dell’informatica del tutto affascinante anche se non semplice!

    Sarò riuscito nell’intento? seguirò questa strada nel futuro e ti saprò dire meglio!

  5. Pingback: lattanzio’s Blog

Rispondi