Il problema della firma digitale nei sistemi a chiave pubblica.

(1)

Lezione del 16 gennaio 2012

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 non vi è una soluzione “universale” ma 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

A

=p

A

q

A

prodotto di 2 primi distinti, una chiave di cifratura c

A

e una di decifratura d

A

, con funzione di cifratura definita da:

f

A

(x)= x

^c^A

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

A

-1}

e funzione di decifratura g

A

definita da:

g

A

(y)= y

^d^A

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

A

-1}

Analoghe scelte da parte del soggetto B: n

B

=p

B

q

B

, c

A

, d

A

f

B

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

^c^B ^B

-1}

g

B

(y)= y

^d^B

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

B

-1}

Primo caso: supponiamo che sia n

A

≤n

B

.

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 valore numerico <n

A

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

A

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

A

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

A

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

B

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

B

ottenendo z=f

B

(y)=f

B

(g

A

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

B

-1}, e infine spedisce z al destinatario B.

Notiamo che il valore y=g

A

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

A

è conosciuta solo da A; il valore z=f

B

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

B

è pubblica.

Il destinatario B, ricevendo z, applica la decifratura g

B

(ricordiamo che B è in possesso della chiave segreta d

B

di decifratura) ottenendo g

B

(z)=g

B

(f

B

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

A

(B è in possesso come tutti della chiave pubblica c

A

di cifratura) ottenendo f

A

(y)=f

A

(g

A

(x))=g

A

(f

A

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

A

·g

A

=g

A

·f

A

, ovviamente valida in quanto x

^c^A^d^A

modn= x

^d^A^c^A

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.

Secondo caso: sia invece n

B

<n

A

.

In questo caso {0,1,……,n

B

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

A

-1}: il mittente A suddivide la sua “firma digitale” in blocchi codificati con valore numerico <n

B

, e (se x è uno di tali blocchi) spedisce z=g

A

(f

B

(x)) al destinatario B, il quale calcolando g

B

(f

A

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

Sappiamo che, per costruire il suo sistema crittografico, il destinatario B ha scelto il numero primo

n, la radice primitiva a modulo n (ambedue resi pubblici), l’intero h (tenuto segreto) con 1£h£n-1,

ha calcolato b=a

^h

modn, e reso pubblica la chiave di cifratura b.

(2)

Ricordiamo anche che [a] nel gruppo Z

n

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

^r

=[a]

^s

, ossia a

^r

ºa

^s

(mod n) .

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

^w

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

n-1

, inviando infine al destinatario B, insieme con il messaggio cifrato (g,d)=(a*

^k

modn, (xb

^k

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

^y

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

Essendo bºt(x-wa) (mod n-1), per quanto premesso sopra sul periodo di [a] si ha:

a

^b

ºa

^t(x-wa)

(mod n)

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

^ty

ºa (mod n)) ottiene :

a

^by

ºa

^ty(x-wa)

ºa

^(x-wa)

(mod n) da cui:

a

^by

a

^wa

º a

^x

(mod n)

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

(a

^y

)

^b

(a

^w

)

^a

º a

^x

(mod n) ossia:

a

^b

z

^a

º a

^x

(mod n) () .*

Il destinatario B ha tutti gli elementi per verificare se tale congruenza è vera: infatti B conosce a,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” (a,b) che “firma” il messaggio): ovviamente potrebbe casualmente avvenire che la “firma” (a,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 (visto che* sono n le diverse classi di congruenza), quindi trascurabile, se n è grande (come avviene nei casi reali).

Esempio.

Sia n=11, a=2 (è radice primitiva modulo 11 come si verifica facilmente), 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

10

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

(a=a

^y

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

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

7

⁷

3

⁷

º2

⁵