Matematica Discreta Lezione del 15/05/09 La crittografia moderna

Matematica Discreta Lezione del 15/05/09 La crittografia moderna

Attualmente, con l’avvento dei canali digitali, un messaggio testuale viene trasmesso lungo un canale di informazione in formato numerico: ogni carattere è trasformato in un numero intero non negativo (rappresentato in genere in base 2, servendosi delle cifre binarie 0,1) mediante delle codifiche concordate a livello internazionale.

Una delle codifiche più usate è il codice ASCII (American Standard Code for Information Interchange) che trasforma ogni carattere alfanumerico (ed anche vari caratteri di interpunzione e comandi di formattazione) in un byte di 8 bits binari 0,1, corrispondente ad un numero binario compreso fra 0=(00000000)

e 255=(11111111)

.

Per esempio nel codice ASCII la codifica numerica della lettera A maiuscola è 65=(01000001)

, della lettera B maiuscola è 66=(01000010)

, e così via proseguendo fino alla codifica numerica della lettera Z maiuscola che è 90=(01011010)

; le codifiche numeriche delle lettere minuscole vanno da 97=(01100001)

a 122=(01111010)

, lo spazio è codificato con 32=(00100000)

; le cifre decimali 0,1,2,….,9 hanno codifiche numeriche da 48=(00110000)

a 57=(00111001)

etc…

Una volta codificati i singoli caratteri del testo, si trasmettono in successione le loro codifiche, formando una successione di bits 0,1.

Per esempio la frase “Vediamoci alle 3” codificata nel codice ASCII darebbe origine al seguente messaggio di 128 bits:

01010110011001010110010001101001011000010110110101101111011000110110100100100000 011000010110110001101100011001010010000000110011

(ogni gruppo di 8 bits è la codifica di un carattere, ed essendo 16 il numero di caratteri del testo, compresi gli spazi, si ha un totale di 816=128 bits).

Ovviamente oggi il significato di “messaggio” non è più limitato al caso di un messaggio testuale:

può essere un qualunque file che contiene informazioni (un’immagine, un file sonoro,un file video etc…): anche in questo caso l’informazione viene codificata con numeri rappresentati in base 2, e trasmessa come successione di bits 0,1.

Indipendentemente dall’informazione contenuta, definiremo dunque messaggio una qualunque successione finita di bits binari 0,1.

La successione di bits che forma il messaggio è in genere suddivisa in “blocchi” più piccoli (sui quali singolarmente opera l’eventuale cifratura o decifratura): spesso di fissa un intero N>0 tale che il valore numerico rappresentato da ogni singolo blocco sia <N.

Se vogliamo che tutti i blocchi abbiano valore numerico <N (dove N è un intero>0 fissato) e siano blocchi della stessa lunghezza k, dovremmo calcolare la massima potenza 2

di base 2 che sia N, e spezzare la successione di bits in blocchi tutti di lunghezza k (sappiamo che un numero di k cifre in base 2 è sempre <2

, dunque è anche <N a maggior ragione).

Nell’esempio precedente, per fare in modo che ogni blocco abbia per esempio valore numerico

<1200=N, poiché 2

=1024 è la massima potenza di base 2 che sia <1200, dovremmo spezzare la successione di 128 bits in blocchi di lunghezza 10 (l’ultimo blocco avrebbe lunghezza 8), e applicare a ciascuno l’eventuale cifratura o decifratura.

Nella crittografia dunque si definirà “messaggio” un qualunque numero intero x0 che sia minore di un intero positivo prefissato.

Con tale convenzione la struttura di un sistema crittografico sarà formata da:

- l’insieme dei messaggi in chiaro X={0,1,2,….,N}, dove N è un intero >0 fissato

- l’insieme dei messaggi cifrati Y={0,1,2,….,M}, dove M è un intero >0 fissato

- una funzione di cifratura f : X  Y, e una funzione di decifratura g : Y  X tali che g(f(x))=x per ogni messaggio in chiaro xX

Spesso si avrà X=Y (dunque anche N=M).

Il vantaggio di tale schematizzazione è anche quello di permettere di definire le funzioni f, g servendosi di algoritmi aritmetici (visto che f,g agiscono su numeri interi).

Sistemi crittografici a chiave pubblica.

Abbiamo visto che il problema dello scambio delle chiavi è un grave problema dei sistemi crittografici.

Una efficiente soluzione a questo problema fu trovata negli anni ’70 con la nascita dei sistemi crittografici a chiave pubblica.

Si tratta di sistemi crittografici in cui le chiavi di cifratura e decifratura sono diverse; mentre la chiave di cifratura è pubblica (quindi nota a tutti), la chiave di decifratura è segreta e conosciuta solo dal soggetto destinatario, ma con la condizione che, a partire dalla conoscenza della chiave di cifratura, il calcolo della chiave di decifratura (da parte di un intruso) 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 (a partire dalla conoscenza della chiave di cifratura) dovrebbe essere equivalente alla soluzione di un opportuno problema matematico per il quale non sia conosciuto un algoritmo di “bassa” complessità di calcolo (per esempio di complessità polinomiale).

Questa fu l’idea di Diffie ed Hellman (1976): essi però non riuscirono a trovare un problema matematico per la cui soluzione non si fossero trovati algoritmi di complessità polinomiale e che potesse essere utilizzato per costruire un sistema crittografico a chiave pubblica.

Poi, nel 1977, Rivest, Shamir e Adleman (del MIT) proposero un sistema crittografico a chiave pubblica, che dalle loro iniziali fu chiamato sistema RSA.

Esso si basa sul Teorema RSA che ora dimostreremo.

Lemma.

Se i numeri primi distinti p, q sono entrambi divisori del numero naturale a, anche il prodotto pq è divisore di a.

Dimostrazione:

Per ipotesi esistono b, c numeri naturali tali che pb=a, qc=a.

Sia d=mcd(p,q). Poiché d è divisore comune del numero primo p, si ha d=1 oppure d=p.

Analogamente si ha d=1 oppure d=q. Essendo p, q distinti, l’unica possibilità è d=1. Per una proprietà del massimo comune divisore, esistono x, y interi relativi tali che 1=px+qy. Dunque:

a = a1 = apx+aqy =(qc)px+(pb)qy = pq(cx+by) e si ottiene che pq é divisore di a, cioé la tesi.

Teorema RSA.

Sia n un numero naturale prodotto di 2 primi distinti p,q e sia t un naturale tale che t 1 (mod (n)), dove (n) è la funzione di Eulero.

Allora per ogni intero x0 si ha: x

x (mod n).

Dimostrazione:

Se x=0 la tesi è banale, quindi sia x>0, cioè x numero naturale.

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, cioè t=k(p-1)(q-1)

Dimostriamo dapprima che p è divisore della differenza x

-x.

Se p è divisore di x, ciò è banale perché sarà x=ph con h intero, da cui x

-x = p

h

-ph = p(p

h

-h).

Supponiamo allora p non divisore di x: per il Piccolo Teorema di Fermat si ha:

x

1 (mod p)

Ricordando che la congruenza è compatibile con il prodotto, possiamo moltiplicare membro a membro tale congruenza per sé stessa k(q-1) volte ottenendo:

x

1 (mod p)

e moltiplicando ancora per la congruenza x 1 (mod p) otteniamo:

x

x (mod p) ossia: x

x (mod p)

quindi p è divisore della differenza x

-x.

Con ragionamenti analoghi si ha che q è divisore della differenza x

-x.

Per il Lemma, essendo p,q primi distinti, anche il loro prodotto n=pq è divisore di x

-x, e si ha la tesi x

x (mod n).

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) é l’insieme {0,1,….,n-1}.

Il soggetto B sceglie poi un naturale c coprimo con (n): sappiamo che nel monoide Z

delle classi di congruenza modulo (n) (rispetto al prodotto di classi) la classe [c] è simmetrizzabile.

Il soggetto B calcola il simmetrico [d] di [c] nel monoide Z

: per il calcolo di d si può usare, come sappiamo, l’algoritmo Euclideo delle divisioni successive (algoritmo di complessità polinomiale, quindi “efficiente”)

La chiave di cifratura (resa pubblica) è il valore c; la chiave di decifratura (tenuta segreta dal destinatario B) è il valore d.

La funzione di cifratura f : {0,1,….,n-1}  {0,1,….,n-1} è definita ponendo f(x)=x

modn (è la riduzione modulo n del numero x

, ottenuta in pratica calcolando il resto della divisione di x

per n).

La funzione di cifratura g : {0,1,….,n-1}  {0,1,….,n-1} è definita ponendo g(x)=x

modn . Dobbiamo però verificare che per ogni messaggio in chiaro x, si abbia g(f(x))=x.

Osserviamo che (essendo [d] simmetrico di [c]) si ha [c][d]=[cd]=[1] in Z

quindi:

cd 1 (mod (n)).

Posto t=cd, possiamo allora applicare il Teorema RSA ottenendo:

x

= x

 x (mod n).

Ma posto y=f(x)=x

modn segue (per una proprietà della riduzione modulo n):

y  x

(mod n).

Analogamente posto z=f(g(x))=f(y)=y

modn segue:

z  y

(mod n).

Moltiplicando membro a membro la congruenza y  x

(mod n) per sé stessa d volte si ha:

y

 x

(mod n) e per transitività:

z  x

(mod n)

ma x

= x

 x (mod n) e per transitività:

z  x (mod n)

Ma z,x sono entrambi numeri compresi fra 0,1,…,n-1, dunque se sono congrui modulo n, sono certamente uguali fra loro (ricordiamo che le classi di congruenza modulo n con rappresentante compreso fra 0,1,…,n-1 sono tutte distinte), dunque:

x = z = f(g(x)).

E’ dunque vero che decifrando la cifratura del messaggio in chiaro x, si riottiene x.