* ={1,2,….,n-1} è un gruppo ciclico (un generatore a di Z

(1)

Matematica Discreta II

Lezione del giorno 15 novembre 2007

Dagli ultimi risultati dimostrati segue che se n è primo (quindi Z

n

è un campo finito) il gruppo moltiplicativo Z

n

* ={1,2,….,n-1} è un gruppo ciclico (un generatore a di Z

n

* è chiamato radice primitiva modulo n).

Illustriamo l’algoritmo di 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= Z

n

*:

1) si sceglie un qualunque elemento x in Z

n

*

2) si calcolano le successive potenze x

¹

, x

²

, x

³

, …. in Z

n

* 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 una radice primitiva modulo 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, si considerano le fattorizzazioni di r,s in prodotto di potenze di primi distinti (dove, per avere lo stesso elenco di primi nelle due fattorizzazioni, si utilizzano eventualmente esponenti nulli):

r = p

₁^k¹

p

₂^k²

...p

_r^k^r

^s= p

₁^h¹

p

₂^h²

...p

_r^h^r

(con k

i

, h

i

³0) e si costruiscono i seguenti numeri naturali:

a = 

³ _i

i i

h k

ik

p

(quindi a è divisore di r, cioè r=ac con c naturale) b = 

 _i

i i

h k

ih

p

(quindi b è divisore di s, cioè s=bd con d naturale)

Si può dimostrare che l’elemento z=x

^c

y

^d

ha periodo uguale al prodotto ab, e che ab>r (omettiamo la dimostrazione). Si sostituisce x con z e si ritorna al passo 2), iterando il procedimento.

Poiché l’algoritmo costruisce elementi di periodo sempre crescente, esso ha termine dopo un numero finito di passi, fornendo il valore di un elemento di periodo n-1, cioè di una radice primitiva modulo n.

Esempio.

Calcoliamo una radice primitiva modulo n=13, cioè un elemento di periodo n-1=12 in Z

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

Date le fattorizzazioni in primi: r = 6 = 2

¹

3

¹

, s = 4 = 2

²

3

⁰

, si calcolano i valori:

a = 3

¹

, c= r/a = 2, b = 2

²

= 4, d = s/b =1

L’elemento z = x

²

y

¹

= 4

²

8 = 11 avrà periodo ab = 12, dunque sarà 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, quindi attualmente non ha complessità polinomiale.

Se n è primo, fissata una radice primitiva a modulo n, si ha:

Z

n

* = {1,2,…..,n-1}={a

⁰

,a

¹

,a

²

,……,a

^n-2

}

(2)

dunque, comunque fissato un intero y, con 2yn-1, esiste un (unico) intero t con 1tn-2 per cui si abbia y=a

^t

in Z

n

* (eguaglianza ovviamente da intendere modulo n). Tale intero t è detto logaritmo discreto di y in base a.

Problema del logaritmo discreto: dato un numero primo n, una radice primitiva a modulo n e un intero y, con 2yn-1, calcolare il logaritmo discreto di y in base a.

Attualmente non esiste una algoritmo di complessità bassa (polinomiale) che risolva tale problema:

quindi lo si può scegliere come base per sistemi crittografici a chiave pubblica, come vedremo.

Sistema crittografico di ElGamal.

E’ un sistema crittografico a chiave pubblica basato sul problema del logaritmo discreto.

Il destinatario B fissa un numero primo n, e calcola una radice primitiva a modulo n (per esempio con l’algoritmo di Gauss).

Poi sceglie un numero intero h, con 1hn-1, e calcola (per esempio con l’esponenziazione modulare) il valore b=a

^h

in Z

n

* (h è dunque il logaritmo discreto in base a del numero b).

In questo sistema lo spazio dei messaggi in chiaro è Z

n

* ={1,2,….,n-1}, mentre la chiave di cifratura (pubblica) è b.

L’algoritmo di cifratura è definito nel modo seguente: il mittente A fissa a piacere un intero k , con 1kn-1 (senza la necessità di comunicarlo a B) e se xÎ{1,2,….,n-1} è il messaggio in chiaro, calcola (utilizzando per esempio l’esponenziazione modulare) i seguenti due elementi in Z

n

*:

g=a

^k

d=xb

^k

Il messaggio cifrato è la coppia (g,d): quindi lo spazio dei messaggi cifrati è il prodotto cartesiano Z

n

* x Z

n

*, e l’algoritmo di cifratura f: Z

n

* ® Z

n

* x Z

n

* è definito da:

f(x) = (g,d) = (a

^k

, xb

^k

)

Descriviamo l’algoritmo di decifratura cioè la funzione g: Z

n

* x Z

n

* ® Z

n

* tale che g(f(x))=x per ogni messaggio in chiaro x.

Sia y=f(x)=(g,d) il messaggio cifrato.

Sia poi g

^-1

l’inverso di g in Z

n

* (il valore g

^-1

si calcola a partire da g, n con l’algoritmo Euclideo).

Ponendo g(y)=g(g,d)=(g

^-1

)

^h

d si ha in effetti g(y)=(g

^-1

)

^h

d=a

^-kh

xb

^k

=(a

^h

)

^-k

b

^k

x=b

^k

b

^-k

x=x .

La chiave di decifratura (tenuta segreta da B) è h (cioè il logaritmo discreto in base a del numero b, che, pur essendo pubblico b, è computazionalmente “difficile” da calcolare).

Il vantaggio del sistema di ElGamal rispetto al sistema RSA è che basta la scelta di un solo primo come base del sistema, ma lo svantaggio é che il messaggio cifrato ha mediamente lunghezza doppia del messaggio in chiaro, e che la radice primitiva modulo n non è facile da calcolare.

Esempio.

Sia n=997 (primo). Con l’algoritmo di Gauss si trova una radice primitiva modulo n, per esempio a=7.

Supponiamo che la chiave di decifratura (segreta) scelta da B sia h=105.

Il destinatario B calcola la chiave di cifratura b=7

¹⁰⁵

=989, e la rende pubblica.

Supponiamo che il messaggio in chiaro che il mittente A deve spedire sia x=813.

Supponiamo anche che il valore k fissato da A sia k=87.

Per cifrare il messaggio x, il mittente A calcola g=7

⁸⁷

=849, d=813989

⁸⁷

=19, e spedisce come messaggio cifrato la coppia (g,d)=(849,19).

Il destinatario B, per decifrare il messaggio, calcola l’inverso g

^-1

di g in Z

997

*, ottenendo g

^-1

=869, e

calcola anche (g

^-1

)

^h

d=869

¹⁰⁵

19=813, riottenendo il messaggio in chiaro.

(3)

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 “pericolosa” 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 2xn-1 (tenendolo segreto) e analogamente B sceglie un naturale y con 2yn-1 (tenendolo segreto).

Infine A spedisce a B il valore z=a

^x

, mentre B spedisce ad A il valore w= a

^y

(sono sempre valori calcolati in Z

n

*, quindi ridotti modulo n).

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