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 » 10.RSA. Sistema di di Massey-Omura. Sistema di El Gamal


La crittografia a chiave pubblica

L’idea che c’è alla base del Protocollo di Diffie-Hellmann, illustrato nella lezione 9, è quella di utilizzare il fatto che nei campi finiti è possibile calcolare in un tempo polinomiale (rispetto ad opportuni input) le potenze degli elementi, mentre non è in generale possibile compiere in tempo polinomiale l’operazione inversa dell’elevamento a potenza (cioè l’estrazione del “logaritmo discreto”).
Partendo da questa idea, sono stati successivamente sviluppati alcuni sistemi crittografici detti “a chiave pubblica”, cioè sistemi crittografici in cui per ogni ogni utente c’è una diversa funzione di cifratura, da utilizzare quando gli si invia un messaggio; la funzione di cifratura f deve essere una funzione “unidirezionale”, cioè una tale che non sia possibile ricavare la chiave di decifratura conoscendo la chiave di cifratura. Ogni utente rende dunque nota la propria chiave di cifratura mantenendo segreta la chiave di decifratura.
Si consiglia di leggere “Koblitz_ChiavePubblica” per un approfondimento su questo concetto.

RSA – Gli insiemi M e C

Si illustrerà il funzionamento del sistema RSA, basato sul fatto che la moltiplicazione di due numeri primi può essere riguardata come una “funzione unidirezionale”, in quanto eseguire la moltiplicazione di due primi p e q ha una complessità polinomiale rispetto agli input p e q, mentre per opportune scelte dei primi, non è possibile determinarli conoscendo soltanto il loro prodotto.
Sono fissati per tutti gli utenti del sistema:
(1) L’alfabeto Σ={0,…,m-1},
(2) Due numeri naturali k e t tali che k<t
(3) Gli insiemi M={0 ,…, mk-1}  e   C={0 ,…, mt-1}.
(a) Per trasformare ogni messaggio da cifrare, scritto inizialmente come sequenza di elementi di Σ, in una sequenza di elementi di M (ai quali verrà poi applicata la funzione di cifratura) si opera come segue:
il messaggio viene suddiviso in blocchi costituiti da k lettere  ⇒  ogni blocco (a1 ,…, ak)  є Σk determina l’unità di messaggio in chiaro
a1mk-1 +…+ ak-1m +ak  є M

RSA – Gli insiemi M e C

(b) Subito dopo avere applicato la funzione di cifratura, il messaggio cifrato risulta essere una sequenza di elementi di C ; per trasformare il messaggio in una sequenza di elementi di Σ, su ogni unità di messaggio cifrata si opera come segue.

Ogni unità di messaggio cifrata, essendo un elemento di C, si scrive in unico modo nella forma

b1mt-1 +…+ bt-1m +bt    con (b1 ,…, bt ) є Σt
e quindi determina la t-pla (b1 ,…, bt )
(c) L’utente che riceve il messaggio cifrato come sequenza di elementi di Σ, per applicare la funzione di decifratura dovrà prima riconvertire il messaggio in una sequenza di elementi di C:
il messaggio viene suddiviso in blocchi costituiti da t lettere  ⇒  ogni blocco (b1 ,…, bt ) determina l’unità di messaggio cifrata
b1mt-1 +…+ bt-1m +bt   є C

RSA – La funzione di cifratura

Ogni utente A costruisce una propria funzione di cifratura come segue.
L’utente A sceglie due numeri primi distinti pA e qA e calcola il prodotto nA=pAqA con la condizione che sia mk<nA<mt .
L’utente A calcola φ(nA)=(pA-1)(qA-1).
L’utente A sceglie un numero naturale eA appartenente a {0 ,…, φ(nA)-1} che sia coprimo con φ(nA).
La funzione di cifratura di A è la funzione fA:M → C definita dalle condizioni
fA(P)≡P^{e_A} (mod nA) e 0≤fA(P)≤nA-1.
L’utente A rende pubblica la chiave di cifratura (nA,eA).
Un utente che voglia inviare un messaggio P all’utente A, gli invia fA(P) (si tenga presente che fA(P) può essere rapidamente calcolato con il metodo dei quadrati ripetuti).

RSA – La funzione di decifratura

Da quanto descritto nella slide precedente, segue che la funzione di decifratura \bar{f_A}^{-1} utilizzata dall’utente A è costruita come segue:
L’utente A calcola il numero dA appartenente a {0 ,…, φ(nA)-1} tale che [d_A]_{\varphi (n_A)}=[e_A]_{\varphi (n_A)}^{-1}.
Sia E=fA(P) un elemento di fA(M)  ⇒  E≡P^{e_A} (mod nA)
⇒  E^{d_A} \equiv P^{e_Ad_A} (mod nA)  ⇒  E^{d_A}≡P (mod nA) (cfr. Teorema 5.5).
Quindi la funzione di decifratura utilizzata dall’utente A è la funzione \bar{f_A}^{-1}:M → C definita dalle condizioni
\bar{f_A}^{-1}(E) \equiv E^{d_A} (mod nA) e 0≤\bar{f_A}^{-1}(E)≤nA-1 (l’utente A può calcolare \bar{f_A}^{-1}(E) con il metodo dei quadrati ripetuti).
Dunque la chiave di decifratura, che l’utente A tiene segreta è (nA,dA).
Si noti che per calcolare dA è necessario conoscere, oltre a eA (che è pubblico), il numero φ(nA), che l’utente A tiene segreto; si ricordi che, partendo dalla conoscenza di nA , conoscere φ(nA) equivale a conoscere i due primi pA e qA (cfr. Proposizione 4.8).

Sistema di Massey-Omura (1982)

Sia F un campo finito F di ordine q, e sia l’insieme delle unità di messaggio in chiaro un sottoinsieme di F*.
Si supponga che un utente A voglia inviare un messaggio P ad utente B.
L’utente A sceglie due numeri naturali uA ,vA appartenenti a {0 ,…, q-1} (coprimi con q-1) tali che
[uA]q-1[uA]q-1 = [1]q-1
L’utente B sceglie due numeri naturali uB ,vB appartenenti a {0 ,…, q-1} (coprimi con q-1) tali che
[uB]q-1[uB]q-1 = [1]q-1
L’utente A calcola e invia all’utente B l’elemento P^{u_A}.
L’utente B calcola e invia all’utente A l’elemento P^{u_Au_B}.
L’utente A calcola e invia all’utente B l’elemento (P^{u_Au_B})^{v_A}, cioè l’elemento P^{u_B} (cfr. Proposizione 5.2).
L’utente B calcola (P^{u_B})^{v_B}, cioè l’elemento P  (cfr. Proposizione 5.2).

Sistema di El Gamal

Sono fissati per tutti gli utenti del sistema:
(1) un campo finito F e l’insieme M, che è un sottoinsieme di F*
(2) un elemento g di F* (possibilmente un generatore)
Ogni utente A sceglie un numero naturale a appartenente all’insieme {0 ,…, |<g>|-1}.
L’utente A, tenendo segreto il numero a, calcola e rende pubblica la propria chiave di cifratura ga .
Un utente che voglia inviare un messaggio P all’utente A, sceglie un numero naturale k appartenente all’insieme {0 ,…, |<g>|-1} e invia la coppia (gk ,Pgak).
Quando l’utente A riceve un messaggio cifrato (g1 , P1), calcola il messaggio in chiaro P tenendo presente che
P1 =P(g1)a , sicché P=P1((g1)a)-1 .

RSA – Un esercizio di cifratura

Esercizio 10.1

Si supponga di avere un sistema RSA così strutturato:
i) l’alfabeto è costituito da 8 lettere, sicché Σ={0,1,2,3,4,5,6,7}
ii) k=2, l=3, sicché M={0 ,…, 63} e C={0 ,…, 511}
Sia A un utente la cui chiave (pubblica) di cifratura è (209,13). Si invii all’utente A il seguente messaggio
2  0  0  3

Svolgimento dell’esercizio
1) Suddividiamo il messaggio in blocchi di due lettere ciascuno:
il primo blocco è la coppia (2,0) , il secondo blocco è la coppia (0,3)
2)  La coppia (2,0) individua l’unità di messaggio in chiaro 2∙8+0=16 є M
La coppia (0,3) individua l’unità di messaggio in chiaro 0∙8+3=3 є M
3) La funzione di cifratura da usare è la funzione fA:M → C definita da fA(P)≡ P13 (mod 209) e 0≤fA(P)≤208

RSA – Un esercizio di cifratura

4) Calcoliamo [16]_{209}^{13} con il metodo dei quadrati ripetuti:
Scriviamo 13 in base 2 :  13=1∙23+1∙22+0∙2+1
b_0=[16]_{209}
b_1=[16]_{209}^2 =[256]_{209}=[47]_{209}
b_2=[47]_{209}^2=[2209]_{209}=[119]_{209}
b_3=[119]_{209}^2=[14161]_{209}=[158]_{209}
[16]_{209}^{13}=[16]_{209}\cdot [119]_{209} \cdot [158]_{209}=[1904]_{209}\cdot [158]_{209}=[23]_{209} \cdot [158]_{209}=[3634]_{209}=[81]_{209}
Quindi fA(16)=81 є C

RSA – Un esercizio di cifratura

Calcoliamo [3]_{209}^{13} con il metodo dei quadrati ripetuti:
b_0=[3]_{209}
b_1=[3]_{209}^2 =[9]_{209}
b_2=[9]_{209}^2=[81]_{209}
b_3=[81]_{209}^2=[6561]_{209}=[82]_{209}
[3]_{209}^{13}=[3]_{209}\cdot [81]_{209} \cdot [82]_{209}=[243]_{209}\cdot [82]_{209}=[34]_{209} \cdot [82]_{209}=[2788]_{209}=[71]_{209}
Quindi fA(3)=71 є C

RSA – Un esercizio di cifratura

5) La sequenza di unità di messaggio cifrate è 81  71; trasformiamola in una sequenza di elementi di Σ :.
Scriviamo 81 in base 8: si ottiene 81=1∙82+2∙8+1
Scriviamo 71 in base 8: si ottiene 71=1∙82+0∙8+7
Dunque 81 determina la terna (1,2,1) e 71 determina la terna (1,0,7)
6) Quindi il messaggio in chiaro 2  0  0  3  viene cifrato mediante il messaggio 1  2  1  1  0  7

RSA – Un esercizio di decifrazione

Esercizio 10.2
Si supponga di avere un sistema RSA così strutturato:
i) l’alfabeto è costituito da 8 lettere, sicché Σ={0,1,2,3,4,5,6,7}
ii) k=2, l=3, sicché M={0 ,…, 63} e C={0 ,…, 511}
Sia A un utente, e si supponga che A abbia ricevuto il messaggio
2  4  0
Sapendo che A ha scelto i primi 11 e 19 e che la sua chiave (pubblica) di cifratura è (209,13), si decifri il messaggio.

RSA – Un esercizio di decifrazione

Svolgimento dell’esercizio
1) Per determinare la chiave (privata) di decifratura di A, bisogna calcolare [13]_{\varphi(209)}^{-1}=[13]_{180}^{-1}
180=13∙13+11; 13=11∙1+2; 11=2∙5+1
1=11-2∙5=11-(13-11)∙5=13∙(-5)+11∙6=13∙(-5)+(180-13∙13)∙6=180∙6+13∙(-83);
Dunque [13]_{180}^{-1}=[-83]_{180}=[97]_{180}.
Ne segue che la chiave di decifratura di A è (209, 97).
2) Suddividiamo il messaggio in blocchi di tre lettere ciascuno:
L’unico blocco è la terna (2,4,0)
3)  La terna (2,4,0) individua l’unità di messaggio in chiaro 2∙82+4∙8+0=160 є C

RSA – Un esercizio di decifrazione

4) La funzione di decifratura da usare è la funzione
\bar f_A^{-1}:M \longrightarrow M definita da \bar f_A^{-1} (E)\equiv E^{97} (mod \; 209) e 0\leq \bar f_A ^{-1}(E) \leq 208
5) Calcoliamo [160]_{209}^{97} con il metodo dei quadrati ripetuti:
Scriviamo 97 in base 2 :  97=1∙26+1∙25+0∙24+0∙23+0∙22+0∙2+1
b_0=[160]_{209}
b_1=[160]_{209}^2 =[25600]_{209}=[102]_{209}
b_2=[102]_{209}^2=[10404]_{209}=[163]_{209}
b_3=[163]_{209}^2=[26569]_{209}=[26]_{209}
b_4=[26]_{209}^2=[676]_{209}=[49]_{209}
b_5=[49]_{209}^2=[2401]_{209}=[102]_{209}
b_6=[102]_{209}^2=[10404]_{209}=[163]_{209}
[160]_{209}^{97}=[160]_{209}\cdot[102]_{209}\cdot[163]_{209}=[16320]_{209}\cdot[163]_{209}=[18]_{209}\cdot[163]_{209}=[2934]_{209}=[8]_{209}
Quindi \bar f_A^{-1} (160)=8

RSA – Un esercizio di decifrazione

5) L’unità di messaggio in chiaro è 8; trasformiamola in una sequenza di elementi di Σ :
Scriviamo 8 in base 8: si ottiene 8=1∙8+0
Dunque 8 determina la coppia (1,0)
6) Quindi il messaggio cifrato 2  4  0  viene decifrato nel messaggio 1 0

El Gamal – un esercizio

Esercizio 10.3
Si supponga di avere un sistema di El Gamal in cui, per tutti gli utenti, l’insieme delle unità di messaggio sia un campo F={0 ,…, 16} di ordine 17; sia fissato per tutti gli utenti l’elemento g=3 appartenente a F.
Si svolgano i seguenti quesiti:
(a) Si dimostri che 3 è un generatore di F*
(b) Sia A un utente la cui chiave (pubblica) di cifratura è 7. Si invii ad A il messaggio 11.
(c) Sia B un utente la cui chiave (privata) di decifratura è 4; si decifri il messaggio (5,6) inviato a B.

El Gamal – un esercizio

Svolgimento dell’esercizio
(a) F* ha ordine 16, sicché i possibili periodi degli elementi di F* sono 2,4,8,16.
Si ha: 32=9; 34=13; 38=16. Da ciò segue che 3 ha periodo 16 e quindi è un generatore di F*.
(b) Per inviare il messaggio ad A bisogna scegliere un numero naturale k appartenente all’insieme {0 ,…, 15} e
inviare la coppia (3k ,11∙7k).
Scegliamo k=3.
Dunque 3k=33=9∙3=10
Inoltre 7k=73=15∙7=3, sicché  11∙7k=11∙3=16
Ad A si invierà la coppia (10,16).
(c) se P è il messaggio in chiaro e h è il numero naturale scelto da chi ha inviato il messaggio, si ha
5=3h  e  6=P∙34h
Dunque 6=P∙34h=P∙3h4=P∙54; d’altra parte 52=8 e quindi 54=82=13, sicché 6=P∙13.

El Gamal – un esercizio

Ne segue che P=6∙13-1
Dato che 17 è un numero primo, per calcolare 13-1  bisogna applicare l’algoritmo delle divisioni successive a 13 e 17:
17=13∙1+4; 13=4∙3+1
1=13-4∙3=13-(17-13)∙3=17∙(-3)+13∙4
Dunque 13-1=4
In conclusione, si ha  P=6∙13-1=6∙4=7.

I materiali di supporto della lezione

L.M. Adleman, R.L. Rivest, A. Shamir: “A method for obtaining digital signatures and public-key cryptosystems", Communications of the ACM 21 (1978), 120—126

T. El Gamal: “A public key cryptosystem and a signature scheme based on discrete logarithms", IEEE Transactions on Information Theory IT-31 (1985), 469--472

Kolbitz- Chiave Pubblica

  • 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