Lezione del 27 maggio 2007 In un sistema crittografico si fisserà dunque un intero N>0 e si definirà “messaggio” un qualunque numero intero x nell’insieme I

(1)

Lezione del 27 maggio 2007

In un sistema crittografico si fisserà dunque un intero N>0 e si definirà “messaggio” un qualunque numero intero x nell’insieme I

N

={0,1,2,……,N-1} .

L’insieme I

N

sarà detto spazio dei messaggi in chiaro.

Per evitare che l’intruso C conosca l’informazione contenuta nel messaggio, il mittente A non spedisce attraverso il canale di comunicazione il messaggio xI

N

, ma effettua prima una

“trasformazione” di x (cifratura) mediante un opportuno algoritmo (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 opportuno algoritmo (funzione di decifratura) di riottenere il messaggio in chiaro x.

Il messaggio cifrato y è in generale elemento dell’insieme I

M

={0,1,2,……,M-1}, dove M è un intero positivo fissato (spesso però M=N): l’insieme I

M

è detto spazio dei messaggi cifrati.

In termini formali l’algoritmo di cifratura sarà una funzione f: I

N



I

M

in modo che, se xI

N

è il messaggio in chiaro, y=f(x)I

M

è il corrispondente messaggio cifrato.

Dovrà esistere anche, come algoritmo di decifratura, una funzione g: I

M

 I

N

tale che, se y=f(x)I

M

è un messaggio cifrato, g(y)=g(f(x))=xI

N

è il messaggio in chiaro.

In termini insiemistici la funzione composta gf è la funzione identica di I

N

, ossia g è una “inversa sinistra” della funzione f, e in particolare f è iniettiva (se f(x

1

)=f(x

2

), applicando g ad ambo i membri si ha x

1

=x

2

). In particolare la cardinalità N dello spazio I

N

dei messaggi in chiaro deve essere non superiore alla cardinalità M dello spazio I

M

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 rispettivamente nel calcolo del messaggio cifrato f(x) e del messaggio in chiaro g(y).

Sistemi crittografici a chiave simmetrica.

In questi sistemi, le chiavi di decifratura coincidono con quelle di cifratura.

Per esempio se il blocco di un messaggio testuale in chiaro è ridotto ad una singola lettera dell’alfabeto italiano oppure allo “spazio”, possiamo codificare ogni lettera con un numero intero compreso fra 1 (codifica della lettera “a”) e 20 (codifica della lettera “z”), lo spazio con il numero 0, e definire un sistema crittografico, con N=22, I

N

=I

M

={0,1,….,21}, fissando come chiave di cifratura un qualunque intero a compreso fra 1 e 21, e definendo l’algoritmo di cifratura f: I

22

 I

22

ponendo f(x)=(x+a)mod22 (corrispondente ad un “shift” di a posizioni verso destra lungo la successione delle lettere dell’alfabeto, disposte circolarmente, in modo che dopo la “z” vi sia di nuovo lo “spazio”).

La chiave di decifratura sarà egualmente a, e l’algoritmo di decifratura g: I

21

 I

21

sarà definito da g(y)=(y-a)mod21 (corrispondente ad uno “shift” 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 21 i valori possibili della chiave a) un intruso C può facilmente pervenire alla decifratura del messaggio cifrato.

Un sistema a chiave simmetrica molto sicuro è invece il seguente: ogni blocco x del messaggio in chiaro è rappresentato come numero binario di lunghezza k (quindi N=2

^k

), eventualmente aggiungendo delle cifre=0 a sinistra; si ha M=2

^k

=N, e la chiave a è una successione casuale di 0,1 di lunghezza k:

a=a

1

a

2

………..a

k

a

i

=0,1

L’algoritmo di cifratura f: I

N



I

N

è definito nel modo seguente: se la rappresentazione in binario di

x è x= x

1

x

2

………..x

k

(con x

i

=0,1), quella di y=f(x) è y=y

1

y

2

………..y

k

, dove y

i

=(x

i

+a

i

)mod2 per

(2)

ogni i=1,…,k (in pratica si effettua l’operazione di “OR esclusivo” fra le cifre del messaggio in chiaro e quelle della chiave).

La chiave di decifratura è la stessa a=a

1

a

2

………..a

k

, e l’algoritmo di decifratura g: I

N

 I

N

coincide con f: si ha infatti f(f(x))=f(y)=z

1

z

2

………..z

k

, dove y

i

=(x

i

+2a

i

)mod2=x

i

, quindi f(y)=x. Poichè la chiave a è una successione casuale di cifre binarie, è praticamente impossibile rompere il sistema: il numero di chiavi possibili è 2

^k

, che si può rendere grande a piacere al crescere di k.

Il problema di questo tipo di sistema è la necessità, per mittente A e destinatario B, di concordare in anticipo la chiave (o l’elenco delle successive chiavi, se si vuole cambiare spesso la chiave): se questo elenco di chiavi deve essere trasmesso attraverso il canale di comunicazione, c’è il rischio che sia intercettato da un intruso.

Una possibile soluzione a tale problema fu trovata negli anni ’70 con la nascita dei sistemi di crittografia a chiave pubblica.

Sistemi di crittografia a chiave pubblica.

Si tratta di sistemi 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 abbia complessità

“alta”, per esempio non polinomiale (quindi sia “computazionalmente difficile” la decifratura del messaggio in chiaro, se non si conosce a priori la chiave di decifratura).

Spesso però la certezza che il calcolo della chiave di decifratura abbia complessità non polinomiale può essere messa in discussione dalla nascita di algoritmi sempre più sofisticati, che minano la sicurezza di questi tipi di sistemi.

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 t 1 (mod (n)), dove (n) è la funzione di Eulero.

Allora per ogni intero x0 si ha: x

^t

x (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 x

^t

-x.

Se p è divisore di x, ciò è banale perché p sarà divisore anche di x

^t

.

Quindi supponiamo p non divisore di x: per il Piccolo Teorema di Fermat si ha:

x

^p-1

1 (mod p)

Elevando ambo i membri all’esponente k(q-1) e moltiplicando per x si ottiene:

x

1+k(p-1)q(-1)

=x

^t

x (mod p) quindi p è divisore della differenza x

^t

-x.

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

^t

-x.

Essendo p,q primi distinti, essi sono coprimi, dunque anche il loro prodotto n=pq è divisore della differenza x

^t

-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.

(3)

Lo spazio dei messaggi in chiaro (e anche di quelli cifrati) sarà I

n

={0,1,….,n-1}.

Il soggetto B sceglie anche un naturale c coprimo con (n): per esempio basta scegliere un numero primo c con c>p,q (se per assurdo fosse c non coprimo con (n), cioé 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 poi l’inverso [d]=[c]

^-1

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) è c; la chiave di decifratura (tenuta segreta da B) è d.

L’algoritmo di cifratura f: I

n



I

n

è definito ponendo f(x)=x

^c

modn : la cifratura del messaggio in chiaro x da parte del mittente A può essere effettuata con l’algoritmo dell’esponenziazione modulare, conosciuti i valori c,n.

L’algoritmo di decifratura g: I

n

 I

n

è definito ponendo g(y)=y

^d

modn : la decifratura del messaggio in chiaro x da parte del destinatario B può essere effettuata anch’essa con l’algoritmo dell’esponenziazione modulare, conoscendo i valori d,n.

Applicando il Teorema RSA si ha per t=cd (essendo per costruzione [c][d]=[1] in Z

(n)

* si ha t=cd1 (mod (n)):

g(f(x))=x

^cd

modnx (mod n)

e quindi g(f(x))=x (perché xI

n

, dunque 0xn-1). Ciò dimostra che decifrando il messaggio cifrato si ritorna effettivamente al messaggio in chiaro x.

Notare che per calcolare la chiave di decifratura d, è necessario conoscere (n)=(p-1)(q-1), e sappiamo (da una lezione precedente) che ciò è equivalente a conoscere i fattori primi p,q di n: il problema è quindi quello di fattorizzare in primi il numero n, e per un generico valore n non è a tutt’oggi noto un algoritmo di fattorizzazione di complessità polinomiale.

Ciò non toglie che per particolari valori di n, alcuni algoritmi di fattorizzazione riescano in modo efficiente a calcolare i fattori primi p,q di n, e quindi a rompere il sistema RSA.

Il soggetto B deve quindi scegliere con cura i primi p,q: non troppo piccoli (algoritmo ingenuo di fattorizzazione), non troppo vicini a n (algoritmo di Fermat); inoltre p-1, q-1 non devono avere fattori primi piccoli (algoritmo p-1 di Pollard) e così via.

Notizie storiche: Nella sfida lanciata nel 1977 dagli inventori del sistema RSA, relativa alla fattorizzazione del numero RSA-129, di 129 cifre in base 10, tale numero (prodotto di 2 primi di 64 e 65 cifre) era alla base di un sistema RSA con cui era cifrato il messaggio testuale “the magic words are squeamish ossifrage”.

L’esponente c per la cifratura (reso pubblico insieme al valore di n) era c=9007.

La decifratura ebbe successo nel 1994, con l’uso dell’algoritmo del crivello quadratico (per il calcolo dei due fattori primi di n) su più di 600 pc che lavorarono in parallelo per 8 mesi.

Esempio.

Diamo un esempio di cifratura e decifratura mediante il sistema RSA.

Sia n=2047, prodotto dei primi p=23, q=89, di modo che (n)= (pq)=(p-1)(q-1)=1936.

Il primo c=97 (che è >p,q) è certamente coprimo con (n).

Con l’algoritmo Euclideo si calcola l’inverso [d] di [c] in Z

1936

*, ottenendo d=1457 .

Se per esempio il messaggio in chiaro è x=10, il messaggio cifrato (ottenuto con l’esponenziazione modulare) è y=10

⁹⁷

mod2047=1607.

Per decifrarlo si calcola 1607

¹⁴⁵⁷

mod2047=10, riottenendo il messaggio in chiaro x.

Il problema del logaritmo discreto.

Si tratta di un altro problema a tutt’oggi di alta complessità di calcolo.

Dal Teorema di Gauss sappiamo che, se n è un numero primo, il gruppo moltiplicativo:

Z

n

* = {[0], [1], ……., [n-1]}

(4)

é un gruppo ciclico (di cardinalità n-1) generato da un opportuno elemento =[a] di periodo n-1 (a è una cosiddetta radice primitiva modulo n).

Illustriamo un algoritmo, dovuto allo stesso Gauss, che permette di calcolare una radice primitiva modulo n, se n è primo, cioè di trovare nel gruppo Z

n

* un elemento di periodo n-1.

Ricordiamo che se un elemento x ha periodo k le potenze distinte di x sono quelle con esponente da 0 a k-1, e ogni altro esponente h>0 tale che x

^h

=1 è multiplo del periodo k. In particolare, considerata una qualunque potenza x

^s

di base x, il periodo t di x

^s

è divisore del periodo k di x: infatti si ha (x

^s

)

^k

=(x

^k

)

^s

=1

^s

=1, e basta applicare la proprietà ricordata sopra alla base x

^s

.

Teorema.

1) Siano n,m interi positivi. Allora esistono interi positivi a,b,c,d tali che:

ac=n; bd=m; a,b sono coprimi; mcm(n,m)=ab

2) Siano a,b elementi di un gruppo commutativo G, di periodo r,s rispettivamente, con r,s coprimi.

Allora l’unico elemento di G che sia potenza comune di a e di b è il neutro 1.

Dimostrazione:

1) Se n=1 allora mcm(1,m)=m, e basta porre a=c=1, b=m,d=1.

Quindi supponiamo n,m>1 e consideriamo le fattorizzazione di n,m in prodotto di potenze di primi distinti (dove, per avere lo stesso elenco di primi nelle due fattorizzazioni, consideriamo la possibilità che qualche esponente sia nullo):

n = p ₁ ^k

¹

p ₂ ^k

²

...p _r ^k

^r

^m= p ₁ ^h

¹

p ₂ ^h

²

...p _r ^h

^r

(con k

i

, h

i

0) Consideriamo il seguente numero naturale:

t = p ₁ ^t

¹

p ₂ ^t

²

...p _r ^t

^r

dove t

i

=max(k

i

, h

i

) per ogni i=1,…..,r Dimostriamo che t=mcm(m,n).

Essendo ogni esponente k

i

t

i

, è ovvio che t è multiplo di n, e analogamente t è multiplo di m.

Resta da dimostrare che se s è multiplo comune di n,m allora s è multiplo di t: ma se fattorizziamo un tale s in prodotto di potenze di primi distinti, essendo t multiplo di n,m, fra tali potenze vi saranno tutte le potenze di base p

i

e ognuna con esponente h

i

, k

i

(con i=1,….,r), dunque con esponente t

i

=max(k

i

, h

i

); e da ciò segue che s è multiplo di t.

Costruiamo ora i numeri a,b,c,d.

Definiamo a uguale al prodotto di quelle potenze p _i ^t

ⁱ

^{in cui t}

ⁱ

^=max(k

ⁱ

^{, h}

ⁱ

^)=k

ⁱ

(cioè in cui k

i

h

i

): è ovvio che a è divisore di n, dunque possiamo porre c=n/a, per avere n=ac.

Definiamo poi b uguale al prodotto delle potenze p _i ^t

ⁱ

non utilizzate nella costruzione di a, cioè in cui k

i

<h

i

): è ovvio che b è divisore di m, dunque possiamo porre d=m/b, per avere m=bd.

Infine a, b sono coprimi (perché non hanno fattori primi comuni nelle loro fattorizzazione) e per costruzione ab= p ₁ ^t

¹

p ₂ ^t

²

...p _r ^t

^r

^=mcm(n,m).

2) Sia z=a

^x

=b

^y

. Come osservato sopra, il periodo di a

^x

è divisore del periodo r di a, ed il periodo di b

^y

è divisore del periodo s di b: dunque l’elemento z ha periodo divisore comune di r,s coprimi, cioè ha periodo 1, e si conclude che z=1.

Esempio.

Diamo un esempio relativo alla 1) del teorema precedente.

Se n=2

⁵

3

⁰

5

²

7

⁴

11

⁰

13

⁴

17

²

, e se m=2

⁴

3

⁷

5

⁶

7

⁴

11

³

13

⁴

17

⁰

, allora, secondo la costruzione fatta nel teorema:

mcm(n,m) = 2

⁵

3

⁷

5

⁶

7

⁴

11

³

13

⁴

17

²

a=2

⁵

7

⁴

13

⁴

17

²

, c=n/a=3

⁰

5

²

11

⁰

, b=3

⁷

5

⁶

11

³

, d=m/b=2

⁴

7

⁴

13

⁴

17

⁰

, con a,b coprimi, ab=mcm(n,m).

Descriviamo ora l’algoritmo di Gauss, per il calcolo di una radice primitiva modulo n, se n è primo.

(5)

1) si sceglie un qualunque elemento x in Z

n

* e si calcolano le successive potenze x

¹

, x

²

, x

³

, …. fino ad ottenere x

^r

=1, dove r è il periodo di x: se r=n-1 si esce (abbiamo trovato un elemento di periodo n-1, dunque un generatore di Z

n

*)

2) se r<n-1, si sceglie un qualunque elemento y¹ x

¹

, x

²

, x

³

, …., x

^r

, si calcolano le successive potenze y

¹

, y

²

, y

³

, …. fino ad ottenere y

^s

=1, dove s è il periodo di y: se s=n-1 si esce (come sopra)

3) se s<n-1, per la 1) del teorema precedente, è possibile trovare interi positivi a,b,c,d tali che:

ac=r; bd=s; a,b coprimi; mcm(r,s)=ab

4) il periodo dell’elemento z=x

^c

y

^d

è uguale al mcm(r,s)>r (vedi sotto), e se tale periodo è n-1 si esce, altrimenti si torna al passo 1) sostituendo z al posto di x (poiché z ha periodo maggiore di x , dopo un numero finito di iterazioni troveremo certamente un elemento di periodo n-1).

Resta però da verificare che, nel passo 4), il periodo dell’elemento z=x

^c

y

^d

è uguale al mcm(r,s), ed inoltre mcm(r,s)>r.

Riguardo alla seconda affermazione, se per assurdo fosse mcm(r,s)=r, sarebbe r multiplo di s, dunque r=sw, y

^r

=(y

^s

)

^w

=1, ossia y sarebbe soluzione del polinomio X

^r

-1; ma tutte le r potenze x

¹

, x

²

, x

³

, …., x

^r

sono soluzioni dello stesso polinomio (perché (x

ⁱ

)

^r

=(x

^r

)

ⁱ

=1), ed essendo y distinto da tali potenze, il polinomio X

^r

-1 (di grado r) avrebbe r+1 soluzioni nel campo Z

n

(contraddizione).

Dimostriamo che, se v é il periodo dell’elemento z=x

^c

y

^d

, allora v=mcm(r,s)=ab.

Si ha z

^ab

=(x

^ac

)

^b

(y

^bd

)

^a

=1

^b

1

^a

=1, dunque mcm(r,s)=ab è multiplo del periodo v di z.

E’ facile verificare che (essendo r=ac il periodo di x) l’elemento x

^c

ha periodo a, e analogamente l’elemento y

^d

ha periodo b (con a,b coprimi per costruzione).

Essendo v il periodo di z, si ha 1=z

^v

= x

^cv

y

^dv

, e moltiplicando per y

^-dv

si ha y

^-dv

=x

^cv

, cioè (y

^d

)

^-v

=(x

^c

)

^v

. Per la 2) del teorema precedente y

^-dv

=x

^cv

=1=y

^dv

. Ma allora v è multiplo del periodo b di y

^d

e del periodo a di x

^c

, e poiché a,b sono coprimi, v è multiplo del loro prodotto ab=mcm(r,s).

In totale i numeri naturali v, mcm(r,s) si dividono a vicenda, dunque coincidono, come si voleva.

Esempio.

Calcoliamo una radice primitiva modulo 13.

Fissato per esempio l’elemento x=[4] in Z

13

* , si calcolano le successive potenze x

¹

=[4], x

²

=[3], x

³

=[12], x

⁴

=[9], x

⁵

=[10], x

⁶

=[1] concludendo che x ha periodo r=6<13-1=12.

Si sceglie allora un qualunque elemento y distinto dalle potenze di x, per esempio y=[8] e si calcolano le successive potenze y

¹

=[8], y

²

=[12], y

³

=[5], y

⁴

=[1]concludendo che y ha periodo s=4<12.

Si calcolano gli interi positivi a,b,c,d tali che:

ac=r=6; bd=s=4; a,b sono coprimi; ab=mcm(6,4)=12

trovando i valori a=3, c=2, b=4, d=1. L’elemento z=x

²

y

¹

=[4]

²

[8]=[11] avrà periodo v=mcm(6,4)=12, dunque sarà un generatore del gruppo ciclico Z

13

* .

Si conclude che 11 è una radice primitiva modulo 13.

Ovviamente l’algoritmo di Gauss per il calcolo della radice primitiva si basa sulla fattorizzazione in primi di alcuni naturali (vedere la dimostrazione della 1) del teorema precedente), quindi attualmente non ha complessità polinomiale.

Fissato n primo, e fissata una radice primitiva a modulo n (quindi un intero a compreso fra 1 e n-1 tale che =[a] sia generatore del gruppo ciclico Z

n

* ) osserviamo che [a] ha periodo n-1, dunque le sue potenze distinte (che esauriscono tutte le classi in Z

n

*) sono [a], [a]

²

,….., [a]

^n-1

.

Dunque per ogni [x]Z

n

* esiste un (unico) esponente k, con 1kn-1 tale che [x]=[a]

^k

.

In altri termini per ogni intero x con 1xn-1 esiste un (unico) esponente k, con 1kn-1 tale che

xa

^k

(mod n): tale k è detto logaritmo discreto di x in base a modulo n (dove a è un radice

primitiva modulo n).

(6)

Esempio.

Se n=13, a=11 (vedi esempio precedente), fissato x=3, il logaritmo discreto di 3 in base 11 è 4, in quanto [11]

⁴

=[3], dunque 311

⁴

(mod 13).

Come per il problema della fattorizzazione in primi, anche per tale problema del logaritmo discreto non esiste a tutt’oggi un algoritmo di complessità polinomiale che, fissato il numero primo n e la radice primitiva a modulo n, e dato in input un intero x con 1 xn-1, calcoli il logaritmo discreto di x in base a.

Su tale problema si può allora basare qualche sistema crittografico a chiave pubblica, come vedremo.

Ma prima vedremo che il problema del logaritmo discreto può essere usato anche per concordare “a distanza” fra due soggetti (in modo sicuro) la chiave di un sistema crittografico a chiave simmetrica.

Scambio di chiavi di Diffie-Hellmann.

In un sistema crittografico a chiave simmetrica, il problema è quello di concordare la chiave comune (di cifratura e decifratura) fra i soggetti A (mittente) e B (destinatario).

Una possibilità è ovviamente quella che A decida il valore della chiave e la trasmetta a B mediante sistemi a chiave pubblica (RSA, ElGamal etc.).

Ma il problema del logaritmo discreto permette di risolvere il problema anche in altro modo, come osservato da Diffie e Hellman, senza che vi sia nessuna comunicazione fra A e B relativa alla chiave da concordare.

I soggetti A,B concordano su un numero primo n e su una radice primitiva a modulo n (che possono essere resi pubblici senza problemi).

Inoltre A sceglie un naturale x con 1xn-1 (tenendolo segreto) e analogamente B sceglie un naturale y con 1yn-1 (tenendolo segreto).

Infine A spedisce a B il valore z=a

^x

modn, mentre B spedisce ad A il valore w= a

^y

modn.

Notiamo che in questa fase un eventuale intruso C che intercetti il valore z o il valore w, non è in grado “facilmente” di calcolare x oppure y (che sono i rispettivi logaritmi discreti in base a).