Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Maria De Falco » 17.Due metodi per inviare la firma digitale


Firma digitale con RSA

Si supponga che A e B siano due utenti di uno stesso sistema RSA; si utilizzeranno le notazioni della Lezione 10.
Sia il numero naturale s, appartenente all’insieme {0 ,…, mk-1} la firma dell’utente A.
Si supponga che l’utente A voglia inviare la propria firma all’utente B, che sa che la firma di A è il numero s.
Sia (nB ,eB ) la chiave di cifratura di B e sia (nA ,dA) la chiave di decifratura di A.
(i) Si supponga, in primo luogo, che sia nA<nB
In questo caso A calcola (con il metodo dei quadrati ripetuti) [s]_{n_A}^{d_A} trovando  il numero
s1 tale che 0≤s1≤nA-1 e s_1 \equiv s^{d_A} (mod nA);
poi A calcola (con il metodo dei quadrati ripetuti) [s_1]_{n_B}^{e_B}, trovando  il numero naturale s2 tale che 0≤s2≤nB-1 e  s_2 \equiv s_1^{e_B} (mod nB);
L’utente A invia come propria firma s2 .
L’utente B riceve s2 .

Firma digitale con RSA

Si ha s_2^{d_B} \equiv s_1^{e_Bd_B} \equiv s_1 (mod nB) e 0≤s1≤nB-1
⇒ calcolando [s_2]_{n_B}^{d_B} con il metodo dei quadrati ripetuti, B trova s1 ;
Inoltre s_1^{e_A} \equiv s^{d_Ae_A} \equiv s (mod nA) e 0≤s≤nA-1
⇒ calcolando [s_1]_{n_A}^{e_A} con il metodo dei quadrati ripetuti, B trova s, avendo così la conferma che la firma è stata inviata proprio da A.
(ii) Si supponga ora che sia nA>nB
In questo caso A calcola (con il metodo dei quadrati ripetuti) [s]_{n_B}^{e_B} trovando  il numero
s1 tale che 0≤s1≤nB-1 e s1s^{e_B} (mod nB);
poi A calcola (con il metodo dei quadrati ripetuti) [s_1]_{n_A}^{d_A}, trovando  il numero naturale s2 tale che 0≤s2≤nA-1 e s2s_1^{d_A} (mod nA).

Firma digitale con RSA

L’utente A invia come propria firma s2 .
L’utente B riceve s2 .
Si ha s_2^{e_A} \equiv s_1^{d_Ae_A} \equiv s_1 (mod nA) e 0≤s1≤nB-1<nA-1
⇒ calcolando [s_2]_{n_A}^{e_A} con il metodo dei quadrati ripetuti, B trova s1 ;
Inoltre s_1^{d_B} \equiv s^{e_Bd_B} \equiv s (mod nB)
⇒calcolando [s_1]_{n_B}^{d_B} con il metodo dei quadrati ripetuti, B verifica la congruenza su citata, avendo così la conferma che la firma è stata inviata proprio da A.

Firma digitale con El Gamal

Siano il campo finito Zp (con p numero primo) e l’elemento [g]p fissati per tutti gli utenti del sistema (cfr. Lezione 14).
Si supponga che l’utente A voglia firmare un messaggio da inviare ad un utente B.
L’utente A applica al suo testo (in chiaro) m una funzione hash h, in modo da ottenere un numero s=h(m), appartenente all’insieme {0 ,…, p-1}, che sarà la firma del messaggio.
Sia ga la chiave di cifratura dell’utente A.
L’utente A sceglie un numero naturale k appartenente all’insieme {0 ,…, p-1} che sia coprimo con p-1.
L’utente A calcola con il metodo dei quadrati ripetuti [g]pk trovando  il numero r tale che

0≤r≤p-1 e  [r]p k =[g]pk    (cioè r≡gk (mod p))

L’utente A risolve l’equazione congruenziale kx≡s-ar (mod p-1), trovando un numero t tale che
0≤t≤p-1 e s≡kt+ar (mod p-1)
L’utente A invia, insieme al messaggio cifrato, la coppia (r,t) come propria firma .

Firma digitale con El Gamal

Si osservi che dal fatto che s≡kt+ar (mod p-1) , segue che

[g]ps = [g]pkt+ar = [gk]p[ga]pr ≡ [r]p[ga]pr

L’utente B riceve il messaggio cifrato, accompagnato dalla coppia (r,t).
Controllando che sia verificata l’uguaglianza [g]ps = [r]p[ga]pr , l’utente B ha la conferma che la firma è stata inviata proprio da A.

Un esempio di verifica di firma digitale con RSA

Esempio 17.1
Si supponga di avere un sistema RSA così strutturato:
i) l’alfabeto è costituito da 2 lettere, sicché Σ={0,1}
ii) k=5, l=8, sicché M={0 ,…, 31} e C={0 ,…, 255}
Sia A un utente la cui chiave di cifratura è (35, 11), e la cui firma è 01001, corrispondente ad s=9.
Si supponga che un utente B riceva due messaggi nei quali si dichiara che il mittente è l’utente A con due firme diverse.
Il primo messaggio ha firma 00001101, mentre il secondo messaggio ha firma 00110001.
L’utente B deve verificare quale dei due messaggi proviene davvero dall’utente A.
La chiave di cifratura di B è (55,27), mentre la chiave di decifratura è (55,3).
L’utente B controlla prima la firma 00001101:
La 8-pla (0,0,0,0,1,1,0,1) individua l’unità di messaggio cifrata 0∙27+0∙26+0∙25+0∙24+1∙23+1∙22+0∙2+1=13
B calcola [13]553  con il metodo dei quadrati ripetuti, e trova che [13]553 = [52]55 .
A questo punto B sa che la firma è falsa perché 52 >35.
Per completare la verifica, l’utente B controlla la firma 00110001:

Un esempio di verifica di firma digitale con RSA

La 8-pla (0,0,1,1,0,0,0,1) individua l’unità di messaggio cifrata 0∙27+0∙26+1∙25+1∙24+0∙23+0∙22+0∙2+1=49
B calcola [49]553  con il metodo dei quadrati ripetuti, e trova che [49]553 = [4]55 .
Dunque s1 =4 è un valore accettabile.
L’utente B calcola ora [4]3511  con il metodo dei quadrati ripetuti, e trova che [4]3511 = [9]35 .
Dunque questo messaggio è stato veramente inviato dall’utente A.

Un esempio di firma digitale con il sistema di l Gamal

Esempio 17.2
Si supponga di avere un sistema di El Gamal in cui sono fissati per tutti gli utenti:
i) Il campo F=Z17
ii) l’elemento [g]17=[3]17 (che è un generatore di F*)
Sia A un utente la cui chiave di cifratura è [9]17
Si supponga che un utente B riceva un messaggio nel quale si dichiara che il mittente è l’utente A con la firma (r,t)=(5,12).
Si supponga che l’utente B si aspetti dall’utente A la firma s=6.
L’utente B deve verificare che sia verificata l’uguaglianza  [g]ps = [r]p[ga]pr
[g]17s = [3]176 =  [15]17 ;  [r]p[ga]pr= [5]1712  [9]175=[4]17 [8]17=  [15]17 . Dunque l’utente B ha la conferma che il messaggio è stato inviato effettivamente dall’utente A.

Esempio 17.3
Si supponga di avere un sistema di El Gamal in cui sono fissati per tutti gli utenti:
i) Il campo F=Z13
ii) l’elemento [g]13=[2]13 (che è un generatore di F*)
Sia A un utente la cui chiave di decifratura è a=3
Si supponga che l’utente A invii ad un utente B un messaggio la cui firma è s=9.
L’utente A scegli k=5; poi calcola con il metodo dei quadrati ripetuti [g]pk =[2]135 =[6]13
Dunque r=6.
L’utente A risolve l’equazione congruenziale kx≡s-ar (mod p-1), cioé  5x≡3 (mod 12); una soluzione di tale equazione è t=3.
L’utente A invia, insieme al messaggio cifrato, la coppia (r,t)=(6,3) come propria firma.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion