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
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
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