Matematica Discreta II
Lezione del giorno 25 ottobre 2007 Crittografia.
E’ la scienza che studia la possibilità che un soggetto A (mittente) spedisca un messaggio ad un soggetto B (destinatario) attraverso un canale di comunicazione non sicuro, in modo che un soggetto C (intruso) non sia in grado, intercettando il messaggio, di conoscere le informazioni in esso contenuto.
Anticamente il concetto di ”messaggio” era ristretto al caso alfa-numerico, cioè al caso di un messaggio costituito da caratteri alfabetici e numerici.
Attualmente, con l’avvento dei canali digitali, il concetto di “messaggio” ha un significato più ampio: in generale ha una forma numerica, e spesso consiste in una successione di bits 0,1 (che può rappresentare qualunque tipo di informazione, per esempio un file audio-video) .
Per trasformare un messaggio di testo in forma numerica, si possono usare delle codifiche concordate dagli utenti: una delle codifiche più semplici per le singole lettere dell’alfabeto italiano consiste nel codificare le lettere con i numeri da 0 a 20, (A=0, B=1, C=2,….,Z=20); uno dei codici più usati è poi il codice ASCII che trasforma ogni carattere alfanumerico in un byte di 8 bits binari, corrispondente ad un numero binario compreso fra 0 e 255, secondo una convenzione internazionale.
La successione di bits che forma il messaggio può essere suddivisa in “blocchi” più piccoli di lunghezza prefissata, che possono essere interpretati come numeri di grandezza limitata.
In generale dunque si fisserà un intero N>0 e si definirà “messaggio” un qualunque numero intero x nell’insieme C = {0,1,2,……,N-1} .
L’insieme C sarà detto spazio dei messaggi in chiaro.
Per evitare che l’intruso conosca l’informazione contenuta nel messaggio, il mittente A non spedisce attraverso il canale di comunicazione il messaggio in chiaro xC , ma effettua prima una
“trasformazione” di x (cifratura) mediante un opportuno funzione (funzione di cifratura) ottenendo un messaggio cifrato y che viene spedito attraverso il canale di comunicazione; il destinatario B, ricevuto il messaggio cifrato y, deve essere in grado, mediante un opportuna funzione (funzione di decifratura) di riottenere il messaggio in chiaro x.
Il messaggio cifrato y è in generale elemento dell’insieme D={0,1,2,……,M-1}, dove M è un intero positivo fissato: l’insieme D è detto spazio dei messaggi cifrati. Nei casi concreti spesso si ha M=N, C=D .
In termini formali la funzione di cifratura sarà una funzione f: C D in modo che, se xC è il messaggio in chiaro, y=f(x)D è il corrispondente messaggio cifrato.
Dovrà esistere anche la funzione di decifratura g: D C tale che, se y=f(x)D è un messaggio cifrato, g(y)=g(f(x))=xC è il messaggio in chiaro.
In termini insiemistici la funzione composta gf è la funzione identica di C, e questo implica in particolare che f è iniettiva (se f(x1)=f(x2), applicando g ad ambo i membri si ha x1=x2). In particolare la cardinalità N dello spazio C dei messaggi in chiaro deve essere della cardinalità M dello spazio D dei messaggi in chiaro (ma come già detto, spesso N=M).
Gli algoritmi di cifratura f e di decifratura g si servono rispettivamente di “chiavi di cifratura” e di
“chiavi di decifratura”, ossia di elementi ausiliari che intervengono nel calcolo del messaggio cifrato f(x) e del messaggio in chiaro g(y).
Se identifichiamo lo spazio dei messaggi in chiaro C con l’insieme ZN delle classi di congruenza modulo N, e lo spazio dei messaggi cifrati con l’insieme ZM delle classi di congruenza modulo M, le funzioni di cifratura f : ZN ZM e di decifratura g : ZM ZN possono essere descritte con algoritmi “matematici”, più facili da implementare sui sistemi informatici moderni.
Sistemi crittografici a chiave simmetrica.
In questi sistemi, le chiavi di decifratura coincidono con quelle di cifratura, o possono essere calcolate in modo semplice a partire da quelle di cifratura.
Per esempio se il blocco di un messaggio testuale in chiaro è ridotto ad una singola lettera dell’alfabeto italiano e se codifichiamo ogni lettera con un numero intero compreso fra 0 (codifica della lettera “A”) e 20 (codifica della lettera “Z”), possiamo definire un sistema crittografico, con N=21, C=D=Z21={0,1,….,20}, fissando come chiave di cifratura un qualunque intero a compreso fra 1 e 20, e definendo l’algoritmo di cifratura f: Z21 Z21 ponendo f(x)=(x+a)mod21 (corrispondente ad una traslazione di a posizioni verso destra lungo la successione delle lettere dell’alfabeto, disposte circolarmente, in modo che dopo la “Z” vi sia di nuovo la “A”).
La chiave di decifratura sarà egualmente a, e l’algoritmo di decifratura g: Z21 Z21 sarà definito da g(y)=(y-a)mod21 (corrispondente ad una traslazione di a posizioni verso sinistra).
Si ha g(f(x))=(x+a-a)mod21=x, e si riottiene il messaggio in chiaro x.
Si tratta del cosiddetto “sistema crittografico di Cesare”, ovviamente poco sicuro perché anche con tentativi di “forza bruta” (essendo 20 i valori possibili della chiave a) un intruso che intercetti il messaggio cifrato y=f(x) può facilmente pervenire alla conoscenza della chiave di decifratura e quindi del messaggio in chiaro.
Un sistema a chiave simmetrica più sicuro è il “sistema crittografico di Vigenere”, evoluzione di quello di Cesare. In tale sistema si fissa un intero positivo k>1 e si sceglie come chiave una stringa di k lettere dell’alfabeto a=a1a2…..ak (che può essere anche una parola di senso compiuto, per essere memorizzata più facilmente); il messaggio in chiaro si spezza in blocchi, ognuno di k lettere, e ad ogni blocco si applica una funzione di cifratura lettera per lettera, utilizzando sulla lettera di posto j il sistema di Cesare con chiave coincidente con il valore numerico della lettera aj di posto j nella chiave a.
Essendo le chiavi possibili in numero di 21k, tale sistema è difficilmente attaccabile con il metodo della “forza bruta”, cioè tentando tutti i possibili valori della chiave, ma può essere forzato con metodi che utilizzano l’analisi delle frequenze delle singole lettere nella parole della lingua in cui è scritto il messaggio in chiaro.
Il Governo U.S.A. sin dalla fine degli anni ’70 ha usato il sistema crittografico a chiave simmetrica D.E.S. (Data Encription Standard): esso opera su blocchi di 64=26 bits binari suddivisi in 7 blocchi da 8 bits (più 1 blocco di controllo da 8 bits), e cifrando con un’alternanza di 16 fra disposizioni e sostituzioni. Le chiavi possibili sono in numero di 256. Questo sistema è quello più usato dal Bancomat e in genere dalla carte a banda magnetica.
Sistemi di crittografia a chiave pubblica.
In un sistema a chiave simmetrica il problema più grande è quello dello scambio delle chiavi: i soggetti A (mittente) e B (destinatario) devono concordare sulle chiavi da usare, e la trasmissione del valore di tali chiavi da un soggetto all’altro può comportare problemi di sicurezza.
Una possibile soluzione a questo problema fu trovata negli anni ’70 con la nascita dei sistemi di crittografia a chiave pubblica.
Sono sistemi basati sul concetto di funzione unidirezionale (detta anche one-way function).
Si tratta di algoritmi di cifratura f: C D in cui la chiave di cifratura è pubblica (quindi nota a tutti) ma tali che (a partire dalla conoscenza della chiave di cifratura) il calcolo della chiave di decifratura dell’algoritmo di decifratura g: D C abbia “alta” complessità di calcolo (quindi sia
“computazionalmente difficile” la decifratura del messaggio in chiaro, se non si conosce a priori la chiave di decifratura).
In generale il calcolo della chiave di decifratura é equivalente alla soluzione di un opportuno problema matematico per il quale non sia conosciuto un algoritmo di “bassa” complessità di calcolo (per esempio polinomiale): la sicurezza di tali sistemi può però essere messa in discussione dalla nascita di nuovi algoritmi, di complessità di calcolo minore rispetto a quelli precedenti.
Uno dei più famosi sistemi di crittografia a chiave pubblica è il sistema RSA, proposto da Rivest, Shamir e Adleman nel 1978.
Esso si basa sul seguente risultato.
Teorema RSA.
Sia n un numero naturale prodotto di 2 primi distinti p,q e sia t un naturale tale che t1 (mod (n)), dove (n) è la funzione di Eulero.
Allora per ogni intero x0 si ha: xtx (mod n).
Dimostrazione:
Se x=0 la tesi è banale, quindi sia x>0.
Calcolando la funzione di Eulero con le usuali formule si ha (n)= (pq)=(p-1)(q-1): per ipotesi si ha t-1=k(p-1)q(-1) con k intero.
Dimostriamo dapprima che p è divisore della differenza xt-x.
Se p è divisore di x, ciò è banale perché p sarà divisore anche di xt, e quindi anche della differenza xt-x .
Supponiamo allora p non divisore di x: per il Piccolo Teorema di Fermat si ha:
xp-11 (mod p)
Elevando ambo i membri all’esponente k(q-1) e moltiplicando per x si ottiene:
x1+k(p-1)q(-1)=xtx (mod p) quindi p è divisore della differenza xt-x.
Con ragionamenti analoghi si ha che q è divisore della differenza xt-x.
Essendo p,q primi distinti, anche il loro prodotto n=pq è divisore della differenza xt-x, e si ha la tesi.
Possiamo allora implementare il sistema crittografico RSA nel modo seguente.
Il soggetto destinatario B sceglie 2 numeri primi distinti p,q e calcola il loro prodotto n=pq, rendendo pubblico n, ma tenendo segreti i fattori primi p,q .
Lo spazio dei messaggi in chiaro (e anche di quelli cifrati) é C=D=Zn={0,1,….,n-1}.
Il soggetto B sceglie poi un naturale c coprimo con (n): per esempio basta scegliere c numero primo con c>p,q (se per assurdo fosse c divisore di (n)=(p-1)(q-1), sarebbe c divisore di p-1 oppure di q-1, cioè c<p oppure c<q, contraddizione).
Il soggetto B calcola l’inverso [d] di [c] nel gruppo moltiplicativo Z(n)*: per il calcolo di d si può usare, come sappiamo, l’algoritmo Euclideo delle divisioni successive.
La chiave di cifratura (resa pubblica) è il valore c; la chiave di decifratura (tenuta segreta da B) è il valore d.
L’algoritmo di cifratura f: Zn Zn è definito ponendo f(x)=xcmodn.
L’algoritmo di decifratura g: Zn Zn è definito ponendo g(y)=ydmodn .
Dobbiamo però verificare che per ogni messaggio in chiaro x, si abbia g(f(x))=x.
In effetti applicando il Teorema RSA si ha (osservando che per costruzione si ha [c][d]=[1] in Z(n)* quindi cd1 (mod (n)):
g(f(x))=xcdmodnx (mod n)
Ma g(f(x)), x sono entrambi numeri compresi fra 0,1,…,n-1, dunque se sono congrui modulo n, sono certamente uguali fra loro: g(f(x))=x .
