Lezione del 28 maggio 2007 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=ahmodn: quindi bºah (mod n), ossia h è il logaritmo discreto in base a del numero b.
In questo sistema lo spazio dei messaggi in chiaro è In-{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=akmodn d=(xbk)modn (quindi 1£g,d£n-1, gºak (mod n), dº (xbk) (mod n)).
Il messaggio cifrato è la coppia (g,d): quindi lo spazio dei messaggi cifrati è il prodotto cartesiano In-{0}x In-{0}, e la funzione di cifratura f: In-{0} ® In-{0}x In-{0} è definita da:
f(x) = (g,d) = (akmodn, (xbk)modn)
Descriviamo la funzione di decifratura g: In-{0}x In-{0}® In-{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 Zn* (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=(dbh)modn (quindi sºdbh (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 º dbh º xbkbh º x(ah)kbh º x(ak)hbh º xghbh º x(gb)h º 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=7105mod997=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=787mod997=849, d=(813×98987)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 Z997*, ottenendo b=869, e calcola anche s=(19×869105)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 nA=pAqA prodotto di 2 primi distinti, una chiave di cifratura cA e una di decifratura dA, con funzione di cifratura definita da:
fA(x)=xcAmodn (per ogni xÎ{0,1,……,nA-1}
e funzione di decifratura gA definita da:
gA(y)=ydAmodn (per ogni yÎ{0,1,……,nA-1}
Analoghe scelte da parte del soggetto B: nB=pBqB , cA, dA
fB(x)=x modn (per ogni xÎ{0,1,……,ncB B-1}
gB(y)=ydBmodn (per ogni yÎ{0,1,……,nB-1}
Supponiamo che sia per esempio nA<nB.
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 <nA; se x è uno di tali blocchi, A applica ad x l’algoritmo di decifratura gA (come se x fosse un messaggio cifrato da decifrare) ottenendo y=gA(x)Î{0,1,……,nA-1}Í{0,1,……,nB-1}, e poi applica l’algoritmo di cifratura fB ottenendo z=fB(y)=fB(gA(x)) Î{0,1,……,nB-1}, spedendo z al destinatario B.
Notiamo che il valore y=gA(x) può essere calcolato solo da A, in quanto la chiave di decifratura dA è conosciuta solo da A; il valore z=fB(y) può essere calcolato da chiunque perché la chiave di cifratura cB è pubblica.
Il destinatario B, ricevendo z, applica la decifratura gB (ricordiamo che B è in possesso della chiave segreta dB di decifratura) ottenendo gB(z)=gB(fB(y))=y, poi applica la cifratura fA (B è in possesso come tutti della chiave pubblica cA di cifratura) ottenendo fA(y)=fA(gA(x))=gA(fA(x))=x (si è sfruttata la proprietà fA·gA=gA·fA, in quanto xcAdAmodn=xdAcAmodn).
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 è nB<nA allora {0,1,……,nB-1}Í{0,1,……,nA-1}:il mittente A suddivide la “firma digitale” in blocchi x<nB, e spedisce z=gA(fB(x)); il destinatario B calcolando gB(fA(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=ahmodn, 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 Zn* ha periodo n-1, dunque se rºs (mod n-1) allora [a]r=[a]s, ossia arºas (mod n) .
Per “firmare”, il mittente A sceglie un wÎ{1,……,n-1}, calcola z=awmodn, 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 Zn-1*, spedendo poi, insieme con il messaggio cifrato (g,d)=(akmodn, (xbk)modn), anche la coppia (a,b) dove a=aymodn, b=t(x-wa)mod(n-1), dove x è il messaggio in chiaro.
Essendo bºt(x-wa) (mod n-1), per quanto premesso si ha:
abºat(x-wa) (mod n)
ed elevando ambo i membri all’esponente y (osservando che come sopra da tyº1 (mod n-1) segue atyºa (mod n)) :
abyºaty(x-wa)ºa(x-wa) (mod n) da cui:
abyawa º ax (mod n)
Tale congruenza modulo n si può riscrivere nel modo seguente:
(ay)b(aw)a º ax (mod n) da cui deriva la congruenza:
abzaº ax (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, 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=28mod11=3 e rende pubblico z; poi sceglie un naturale y coprimo con 10, per esempio y=7, calcola l’inverso [t] di [9] in Z10* (ottenendo t=3), e spedisce come firma la coppia:
(a=aymodn, b=t(x-wa)mod(n-1)) = (7,7).
Per verificare la firma, il destinatario verifica se è vera la congruenza:
7737º25 (mod 11)
e poiché la risposta è affermativa, B è certo (con alta probabilità) dell’identità di A.
