Lezione del 27 maggio 2009 Sistemi di crittografia a chiave pubblica.

Lezione del 27 maggio 2009

Sistemi di crittografia a chiave pubblica.

Si tratta di sistemi crittografici, proposti in modo solo teorico nel 1976 da Diffie e Hellman, in cui la chiave di cifratura è pubblica (quindi nota a tutti) mentre la chiave di decifratura è segreta (conosciuta solo dal destinatario) ma in modo 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): in genere il calcolo della chiave di decifratura è equivalente ad un problema matematico per la cui soluzione non esistano ancora algoritmi di complessità polinomiale.

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.

La prima realizzazione concreta di un sistema crittografico a chiave pubblica avvenne nel 1978, con il sistema RSA, proposto da Rivest, Shamir e Adleman, basato sul problema matematico della

“fattorizzazione in primi”..

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

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

-x.

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

.

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

x

1 (mod p)

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

x

=x

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

-x.

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

-x.

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

-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) sarà I

={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]

nel gruppo moltiplicativo Z

*: 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



I

è definito ponendo f(x)=x

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

 I

è definito ponendo g(y)=y

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

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

g(f(x))=x

modnx (mod n)

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

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

*, 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

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

é 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

* 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

=1 è multiplo del periodo k. In particolare, considerata

una qualunque potenza x

di base x, il periodo t di x

è divisore del periodo k di x: infatti si ha

(x

)

=(x

)

=1

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

.

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

^m= p ₁ ^h

p ₂ ^h

...p _r ^h

(con k

, h

0) Consideriamo il seguente numero naturale:

t = p ₁ ^t

p ₂ ^t

...p _r ^t

dove t

=max(k

, h

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

Essendo ogni esponente k

t

, è 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

e ognuna con esponente h

, k

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

=max(k

, h

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

h

): è 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

<h

): è 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

^=mcm(n,m).

2) Sia z=a

=b

. Come osservato sopra, il periodo di a

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

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

1) si sceglie un qualunque elemento x in Z

* e si calcolano le successive potenze x

, x

, x

, …. fino ad ottenere x

=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

*)

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

, x

, x

, …., x

, si calcolano le successive potenze y

, y

, y

, …. fino ad ottenere y

=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

y

è 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

y

è 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

=(y

)

=1, ossia y sarebbe soluzione del polinomio X

-1; ma tutte le r potenze x

, x

, x

, …., x

sono soluzioni dello stesso polinomio (perché (x

)

=(x

)

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

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

(contraddizione).

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

y

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

Si ha z

=(x

)

(y

)

=1

1

=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

ha periodo a, e analogamente l’elemento y

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

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

= x

y

, e moltiplicando per y

si ha y

=x

, cioè (y

)

=(x

)

. Per la 2) del teorema precedente y

=x

=1=y

. Ma allora v è multiplo del periodo b di y

e del periodo a di x

, 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

* , 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

* .

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

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

*) sono [a], [a]

,….., [a]

.

Dunque per ogni [x]Z

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

.

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

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

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

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

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

A questo punto A calcola il valore w

modn, mentre B calcola il valore z

modn: tali valori (compresi fra 1 ed n-1) coincidono con a

modn, e possono essere quindi scelti come chiave concordata per un sistema crittografico a chiave pubblica.

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), rendendo pubblici tali dati.

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

modn: quindi ba

(mod n), ossia h è il logaritmo discreto in base a del numero b.

In questo sistema lo spazio dei messaggi in chiaro è I

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

La chiave di cifratura è b, che viene resa pubblica; la chiave di decifratura è h, tenuta segreta.

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 due numeri:

g=a

modn d=(xb

)modn (quindi 1g,dn-1, ga

(mod n), d (xb

) (mod n)).

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

-{0}x I

-{0}, e la funzione di cifratura f: I

-{0}  I

-{0}x I

-{0} è definita da:

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

modn, (xb

)modn)

Descriviamo la funzione di decifratura g: I

-{0}x I

-{0} I

-{0} tale che g(f(x))=x per ogni messaggio in chiaro x. Sia y=f(x)=(g,d) il messaggio cifrato.

Sia poi [b] l’inverso di [g] in Z

* (il valore b si calcola a partire da g,n con l’algoritmo Euclideo):

quindi bg1 (mod n).

Si calcola infine, con l’esponenziazione modulare, il valore s=(db

)modn (quindi sdb

(mod n)) e si definisce l’algoritmo di decifratura ponendo g(y)=s.

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

Resta da verificare però che g(f(x))=x.

Infatti si hanno le seguenti congruenze modulo n:

g(f(x))  s  db

 xb

b

 x(a

)

b

 x(a

)

b

 xg

b

 x(gb)

 x (mod n) da cui s=x (perché sono numeri congrui modulo n, e compresi fra 1 e n-1).

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.

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 b=7

mod997=989, e rende pubblica la chiave di cifratura (n=997,a=7,b=989).

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

mod997=849, d=(813×989

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

Il destinatario B, per decifrare il messaggio, calcola l’inverso [b] di [g] in Z

*, ottenendo b=869, e calcola anche s=(19×869

)modn=813, riottenendo il messaggio in chiaro.

Il problema della firma digitale nei sistemi a chiave pubblica.

In un sistema crittografico a chiave pubblica, la chiave di cifratura è pubblica, dunque un intruso C potrebbe spedire al destinatario B un messaggio cifrato firmandolo come se il mittente fosse A, ossia “fingendo” che A sia l’autore del messaggio.

Per ovviare a questo problema, vi sono varie soluzioni, relative al singolo sistema crittografico.

Firma digitale nel sistema RSA.

E’ necessario che sia A che B implementino un proprio sistema RSA.

Il soggetto A sceglierà un intero n

=p

q

prodotto di 2 primi distinti, una chiave di cifratura c

e una di decifratura d

, con funzione di cifratura definita da:

f

(x)= x

modn (per ogni x{0,1,……,n

-1}

e funzione di decifratura g

definita da:

g

(y)= y

modn (per ogni y{0,1,……,n

-1}

Analoghe scelte da parte del soggetto B: n

=p

q

, c

, d

f

(x)= x modn (per ogni x{0,1,……,n

-1}

g

(y)= y

modn (per ogni y{0,1,……,n

-1}

Supponiamo che sia per esempio n

<n

.

Insieme con il messaggio cifrato, il mittente A manda una sua “firma digitale” (per esempio una frase del tipo “Firmato: Mario Rossi”) ma affinché B sia certo che la firma è proprio quella del soggetto A, il mittente A suddivide la “firma digitale” in blocchi codificati con numeri <n

; se x è uno di tali blocchi, A applica ad x l’algoritmo di decifratura g

(come se x fosse un messaggio cifrato da decifrare) ottenendo y=g

(x){0,1,……,n

-1}Í{0,1,……,n

-1}, e poi applica l’algoritmo di cifratura f

ottenendo z=f

(y)=f

(g

(x)) {0,1,……,n

-1}, spedendo z al destinatario B.

Notiamo che il valore y=g

(x) può essere calcolato solo da A, in quanto la chiave di decifratura d

è

conosciuta solo da A; il valore z=f

(y) può essere calcolato da chiunque perché la chiave di cifratura

c

è pubblica.

Il destinatario B, ricevendo z, applica la decifratura g

(ricordiamo che B è in possesso della chiave segreta d

di decifratura) ottenendo g

(z)=g

(f

(y))=y, poi applica la cifratura f

(B è in possesso come tutti della chiave pubblica c

di cifratura) ottenendo f

(y)=f

(g

(x))=g

(f

(x))=x (si è sfruttata la proprietà f

·g

=g

·f

, in quanto x

modn= x

modn).

Alla fine B legge la “firma digitale”in chiaro (dopo avere riunito i blocchi x), e può essere certo dell’identità del mittente A.

Se invece è n

<n

allora {0,1,……,n

-1}Í{0,1,……,n

-1}:il mittente A suddivide la “firma digitale” in blocchi x<n

, e spedisce z=g

(f

(x)); il destinatario B calcolando g

(f

(x))=x riottiene la firma digitale in chiaro (dopo avere riunito i blocchi x), e può essere certo dell’identità del mittente A.

Firma digitale nel sistema di ElGamal.

Il destinatario B ha scelto il numero primo n, la radice primitiva a modulo n, l’esponente h con 1hn-1, ha calcolato b=a

modn, e reso pubblica la chiave di cifratura b, tenendo segreto il logaritmo discreto h di b in base a, come chiave di decifratura.

Ricordiamo che [a] nel gruppo Z

* ha periodo n-1, dunque se rs (mod n-1) allora [a]

=[a]

, ossia a

a

(mod n) .

Per “firmare”, il mittente A sceglie un w{1,……,n-1}, calcola z=a

modn, e rende pubblico z (il logaritmo discreto w di z in base a è tenuto segreto da A); poi A sceglie un naturale y coprimo con n-1, e calcola l’inverso [t] di [y] nel gruppo Z

*, spedendo poi, insieme con il messaggio cifrato (g,d)=(a

modn, (xb

)modn), anche la coppia (,b) dove =a

modn, b=t(x-w)mod(n-1), dove x è il messaggio in chiaro.

Essendo bt(x-w) (mod n-1), per quanto premesso si ha:

a

a

(mod n)

ed elevando ambo i membri all’esponente y (osservando che come sopra da ty1 (mod n-1) segue a

a (mod n)) :

a

a

a

(mod n) da cui:

a

a

 a

(mod n)

Tale congruenza modulo n si può riscrivere nel modo seguente:

(a

)

(a

)

 a

(mod n) da cui deriva la congruenza:



z

 a

(mod n) (*) .

Il destinatario B ha tutti gli elementi per verificare se tale congruenza è vera: infatti B conosce

,b,z,n,x (x è il messaggio in chiaro che ha decifrato dopo averlo ricevuto cifrato).

Se la congruenza (*) è verificata, B può essere certo dell’identità del mittente A (solo A, conoscendo w, può avere spedito la coppia “corretta” (,b) che “firma” il messaggio): ovviamente potrebbe casualmente avvenire che la “firma” (,b) sia spedita da un intruso C, e che casualmente la congruenza (*) sia verificata: ma la probabilità che 2 interi siano congrui modulo n è 1/n, quindi trascurabile, se n è grande (come avviene nei casi reali, per rendere più sicuro il sistema).

Esempio.

Sia n=11, a=2 (è radice primitiva modulo 11), messaggio in chiaro x=5.

Per firmare il messaggio, il mittente A sceglie w{1,……10}, per esempio w=8, calcola z=2

mod11=3 e rende pubblico z; poi sceglie un naturale y coprimo con 10, per esempio y=7, calcola l’inverso [t] di [9] in Z

* (ottenendo t=3), e spedisce come firma la coppia:

(=a

modn, b=t(x-w)mod(n-1)) = (7,7).

Per verificare la firma, il destinatario verifica se è vera la congruenza:

7

3

2

(mod 11)

e poiché la risposta è affermativa, B è certo (con alta probabilità) dell’identità di A.