Il logo di batmath
www.batmath.it

Funzioni inverse, numeri primi e crittografia

Pensa un numero, aggiungi 2, moltiplica il risultato per 3, aggiungi il doppio del numero pensato e dimmi che cosa ottieni. E' uno dei classici giochi che tutti abbiamo sperimentato da piccoli, e che possono essere risolti con una "formula magica": in questo caso togli sei dal risultato e dividi per cinque! Il gioco si basa essenzialmente su due fatti:

Detto in termini più "matematici":

Un indovinello del tipo: Pensa un numero, moltiplicalo per 5, sottrai il quadrato del numero e dimmi il risultato, non andrebbe bene. Difatti se la risposta è 6, ci sono due possibili numeri soluzione del problema: 2 e 3. (Detto tra noi, "matematici adulti", questo è legato al fatto che un'equazione di secondo grado può avere anche due soluzioni positive distinte).

Vogliamo utilizzare l'idea che sta alla base di questo indovinello per spiegare il principio su cui si basa la crittografia asimmetrica, una tecnica divenuta fondamentale nel moderno sistema di comunicazioni. Precisiamo subito che non intendiamo proporre un trattato sulla crittografia, ma semplicemente spiegarne il funzionamento, come interessante applicazione del concetto di funzione inversa (e non solo): chi è interessato ad approfondire specificamente lo studio della crittografia trova in rete moltissimo materiale; citiamo qui, a mo' d'esempio, l'interessantissimo ipertesto prodotto al Liceo Foscarini di Venezia, La crittografia da ATBASH a RSA, reperibile all'url: http://www.liceofoscarini.it/studenti/crittografia/index.html.

Crittografare, come è ben noto, significa trasformare, mediante un algoritmo, un testo in un altro testo incomprensibile a chi non conosce l'algoritmo stesso e non è in grado di ripercorrerlo a ritroso. E' un sistema di comunicazione "riservata" tra due (o più) persone, che però devono utilizzare una terza persona (o una macchina) per trasportare il messaggio: se vogliono essere sicuri di mantenere la riservatezza, devono impedire al trasportatore (o agli hacker!) di leggere il messaggio.

Esempi di testi crittografati si trovano fin nell'antichità. Per esempio nella Bibbia, in Geremia 25:26, si trova citato Il re di Sesach, dove Sesach è la crittografia di Babele (in realtà SSK per BBL). Il sistema usato era molto semplice: sostituisci ogni lettera dell'alfabeto con la lettera che occupa la stessa posizione nell'alfabeto scritto alla rovescia (nel nostro alfabeto a diventerebbe z, b diventerebbe y, ecc.). Questo sistema si chiama ATBASH, perché, nell'alfabeto ebraico, a viene sostituita con t e b con sh. Anche Cesare nelle comunicazioni con i suoi familiari, e probabilmente anche con i suoi comandanti militari, usava un sistema di cifratura, come ci dice Svetonio, in De Vita Caesarum, 56:7.

Il sistema usato da Cesare era quello di spostare avanti ogni lettera, nell'ordine alfabetico, di 3 posti. Una tecnica simile fu usata da Augusto spostando in avanti ogni lettera di un posto. E' chiaro che questi sistemi di cifratura erano facilmente attaccabili (ma erano adatti per quei tempi, quando la scrittura era ben poco diffusa!).

Numerosi altri sistemi furono introdotti in seguito, ma ora fissiamo piuttosto l'attenzione su quello che qui ci interessa e cioè la matematica coinvolta.

Intanto osserviamo che possiamo limitarci a considerare testi composti solo da numeri naturali, assegnando, con un qualunque sistema (per esempio ASCII, ANSI, UNICODE), un codice numerico ad ogni carattere (il sistema usato oggi è ancora più sofisticato, ma la cosa non è interessante per i nostri scopi). L'idea di base è allora quella di considerare una funzione, f, iniettiva (e quindi invertibile se facciamo una opportuna restrizione del codominio all'immagine) tra l'insieme di tutti i codici e l'insieme dei numeri naturali. Se chi spedisce il messaggio sostituisce, mediante la funzione f, ogni numero x del suo messaggio con f(x), allora il ricevente potrà decrittare il messaggio solo se conosce l'inversa della funzione f (o se qualcuno l'ha trovata per lui!). Nell'indovinello iniziale la "magia" del gioco sta proprio nel fatto che chi lo propone è in grado di ricavare la funzione inversa (o perlomeno la conosce), mentre chi partecipa al gioco no. La funzione f in questione può essere di qualunque tipo, e in effetti quelle più usate nella crittografia classica erano basate su tabelle: l'unica cosa che conta è la iniettività e la possibilità di calcolare l'inversa. La funzione f può essere chiamata chiave di crittazione, mentre la sua inversa chiave di decrittazione.

E' chiaro che la funzione in questione deve essere molto complessa, per evitare che gli intrusi possano scoprirla. I metodi per scoprire le funzioni utilizzate sono essenzialmente basati su metodi statistici e riescono spesso a scoprire anche funzioni molto complesse. Due esempi famosi di decrittazione sono quelli dell'algoritmo di Blaise de Vigenére, proposto nel 1562 e decrittato da Charles Babbage nel 1854 e da Friedrich Wilhelm Kasiski nel 1863 (aveva resistito comunque 300 anni, tanto da farlo ritenere assolutamente sicuro), e quello della Macchina Enigma, inventata nel 1918 da Arthur Scherbius, estesamente usata dai tedeschi fino alla fine della seconda guerra mondiale, ma già attaccata intorno al 1932 da Marin Rejewsky per i servizi segreti polacchi. Le scoperte di Rejewsky consentirono ai servizi segreti britannici, con l'aiuto di Alan Turing, il padre dell'informatica teorica, di decifrare una gran parte dei messaggi scambiati tra i comandi tedeschi, contribuendo forse in maniera notevole al successo alleato nella seconda guerra mondiale.

Se sia il trasmittente che il ricevente conoscono la funzione f e sono in grado di calcolare l'inversa, possono scambiarsi messaggi, in modo che ciascuno possa leggere i messaggi dell'altro: la complessità della funzione f può essere molto alta, tanto da rendere la sua eventuale scoperta un'impresa molto ardua. I sistemi di crittazione in cui sia il mittente che il ricevente conoscono esattamente la funzione f e la sua inversa (cioè le due chiavi) si chiamano algoritmi a chiavi simmetriche e sono notevolmente veloci anche per funzioni complesse, soprattutto grazie all'uso dei calcolatori. Una elevata sicurezza si raggiunge però solo cambiando, anche spesso, le chiavi.

Il problema più grosso negli algoritmi a chiavi simmetriche è che le chiavi devono essere scambiate tra soggetti che si trovano a notevoli distanze e questo richiede un metodo sicuro (criptato!) per scambiarsi le chiavi. Sembra che il gatto si morda la coda e che non ci siano soluzioni al problema.

Nel 1975 però, Whitfield Diffie e Martin Hellman ebbero un'intuizione geniale che rivoluzionò il mondo della crittografia. L'idea di base è la seguente: trovare una funzione f (chiave di criptazione) tale che, anche se tutti la conoscono, sia praticamente impossibile, tranne per chi l'ha costruita, riuscire a determinarne l'inversa (chiave di decrittazione). In questo modo la chiave di crittazione può addirittura essere resa di dominio pubblico: chiunque può mandare messaggi cifrati al proprietario della chiave di decrittazione, ma nessuno, tranne il destinatario sarà in grado di interpretarlo, nemmeno chi l'ha scritto. Questo tipo di algoritmo si chiama algoritmo a chiavi asimmetriche o a chiave pubblica.

Tra le implementazioni più famose di questa idea è quella nota con la sigla RSA, dai nomi dei suoi tre scopritori: Ronald Rivest, Adi Shamir e Leonard Adleman. La descriveremo qui brevemente, portando un esempio per rendere chiara l'idea.

Indichiamo innanzitutto con M uno dei numeri che costituiscono il nostro messaggio e che dobbiamo cifrare (ricordiamo che il nostro messaggio può essere sempre pensato come una successione di  numeri naturali). I passi da compiere sono i seguenti

  1. Prendere due numeri primi: p e q e indicare il loro prodotto con N. Il numero N viene rese pubblico, mentre i due numeri p e q rimangono segreti. L'affidabilità dell'algoritmo proposto è tanto maggiore quanto più grandi sono i due numeri p e q: la costruzione della chiave di decrittazione richiede infatti di scoprire p e q a partire da N, e non si conoscono allo stato attuale algoritmi veloci per farlo. Se per esempio p e q sono di circa 100 cifre ciascuno, N sarà di circa 200 cifre, e il tempo necessario, con i calcolatori più veloci oggi conosciuti, per decomporre in fattori primi un numero di queste dimensioni (che si sa a priori avere solo 2 fattori primi di circa 100 cifre) può essere valutato nell'ordine di secoli!
  2. Considerare poi il numero z = (p-1)(q-1); anche z deve rimanere segreto. Questo numero, se p e q sono primi, indica quanti numeri minori di N, primi con N, ci sono (questo risultato è un caso particolare della funzione di Eulero che, dato un numero a,calcola appunto quanti numeri primi con a, compreso 1, ci sono ci sono prima di a). Scegliere poi un naturale D primo rispetto a z. Il numero D viene reso pubblico.
  3. Determinare (è una delle cose più difficili da fare tecnicamente) un numero S, tale che il resto della divisione tra il prodotto S·D e z sia 1. Il numero S è quindi il reciproco di D nell'aritmetica dei numeri interi modulo N. Il numero S rimane segreto.

A questo punto l'algoritmo è pronto.

Bisognerebbe in realtà provare che le due funzioni sono proprio una l'inversa dell'altra, ma la cosa richiede conoscenze di aritmetica modulare che esulano dal nostro contesto. La cosa interessante da segnalare è che la funzione di crittazione è di dominio pubblico, come pure il fatto che essa sia invertibile, ma la costruzione esplicita della funzione inversa è praticamente impossibile in tempi ragionevoli, almeno per p e q molto grandi, se non si conoscono p e q: come già osservato la determinazione di p e q, a partire da N, richiede tempi decisamente lunghi.

Proponiamo un esempio per chiarire il concetto (con p e q piccoli per rendere possibile il calcolo manuale!).

  1. Scegliamo p = 3 e q = 11, da cui N = 33.
  2. Si ha z = 20. Scegliamo D = 3.
  3. Possiamo trovare facilmente (in questo esempio semplice!) S = 7 (7·3=21, che diviso per 20 dà proprio resto 1).

La parte pubblica della chiave è costituita dai numeri 3 e 33, mentre la parte segreta dai numeri 7 e 33.

Se consideriamo, per fare un esempio, i numeri da 1 a 8, li eleviamo al cubo (cioè alla D) e calcoliamo il resto della loro divisione per 33, otteniamo la seguente tabella:

Numero originario   Numero cifrato
1 1
2 8
3 27
4 31
5 26
6 18
7 13
8 17

Per verificare che l'algoritmo funziona proviamo ora a decrittare i numeri della colonna di destra. Prendiamo ad esempio il numero 17: 177 = 410338673; 410338673 : 33 = 12434505 con resto di 8. Quindi 17 viene decrittato in 8, come previsto.

Il limite più grosso di questa tecnica è nella lentezza dei calcoli di crittazione e in particolare di decrittazione. E' però il pegno che bisogna pagare per un algoritmo tanto efficiente. Esso, per numeri p e q di oltre 100 cifre è ritenuto, a tutt'oggi, praticamente inattaccabile. Per capire meglio questo fatto consideriamo un esempio, rimasto famoso, quello di RSA-129.

Nel 1977, subito dopo il lancio del sistema di crittografia RSA, Martin Gardner pubblicò su Scientific American un piccolo messaggio cifrato, basato su una chiave costituita da un numero N di 129 cifre, prodotto di due numeri primi molto grandi. Il messaggio e la chiave erano stati forniti da ricercatori del MIT, che offrivano un premio in denaro a chi avesse decrittato il messaggio. A quei tempi si stimò che ci sarebbero voluti all'incirca ventimila anni per scomporre in fattori primi quel numero, con i più veloci calcolatori disponibili. Dopo di allora però ci furono importanti novità, più che sul lato della velocità dei computer, sui metodi per fattorizzare grandi numeri. Inoltre la massiccia diffusione di Internet costituì una variabile imprevista: sotto la guida di alcuni ricercatori, un esercito di 600 volontari si mise all'opera e dopo non molti mesi di lavoro, nell'Aprile del 1994, la fattorizzazione fu scoperta: si trattava di due numeri, uno di 64 e uno di 65 cifre. Erano passati solo (!) 17 anni dalla pubblicazione della chiave pubblica. Solo per curiosità riportiamo qui i valori dei numeri coinvolti (i volonterosi possono provare ad eseguire il prodotto richiesto, per controllare che non ci siano errori):

p = 3490529510847650949147849619903898133417764638493387843990820577
q = 32769132993266709549961988190834461413177642967992942539798288533
N = 114381625757888867669235779976146612010218296721242362562561842935706935245733897830
       597123563958705058989075147599290026879543541 

Insomma per implementare una efficiente tecnica di criptazione occorre conoscere parecchia matematica, e anche di quella che di solito viene considerata inutile:

Per concludere segnaliamo anche che l'algoritmo a chiavi asimmetriche funziona anche in senso contrario: se io che ho la chiave segreta la uso per criptare un messaggio, chiunque conosca la chiave pubblica può decrittare quel messaggio, essendo sicuro che posso averlo scritto solo io: come è ben noto se f-1 è l'inversa di f, f è l'inversa di f-1 (ancora un po' di matematica!). Questo meccanismo, con opportuni adattamenti, è alla base della cosiddetta firma digitale.

pagina pubblicata il 07/04/2004 - ultimo aggiornamento il 07/04/2004