Home

Federica EU

1/18

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 ,…, m^k-1} e C={0 ,…, m^t-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 (a₁ ,…, a_k) є Σ^k determina l’unità di messaggio in chiaro
a₁m^k-1 +…+ a_k-1m +a_k є 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

b₁m^t-1 +…+ b_t-1m +b_tcon (b₁ ,…, b_t) є Σ^t
e quindi determina la t-pla (b₁ ,…, b_t )
(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 (b₁ ,…, b_t) determina l’unità di messaggio cifrata
b₁m^t-1 +…+ b_t-1m +b_t є 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 p_A e q_A e calcola il prodotto n_A=p_Aq_A con la condizione che sia m^k<n_A<m^t.
L’utente A calcola φ(n_A)=(p_A-1)(q_A-1).
L’utente A sceglie un numero naturale e_A appartenente a {0 ,…, φ(n_A)-1} che sia coprimo con φ(n_A).
La funzione di cifratura di A è la funzione f_A:M → C definita dalle condizioni
f_A(P)≡ $P^{e_A}$ (mod n_A) e 0≤f_A(P)≤n_A-1.
L’utente A rende pubblica la chiave di cifratura (n_A,e_A).
Un utente che voglia inviare un messaggio P all’utente A, gli invia f_A(P) (si tenga presente che f_A(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 d_A appartenente a {0 ,…, φ(n_A)-1} tale che $[d_A]_{\varphi (n_A)}=[e_A]_{\varphi (n_A)}^{-1}$ .
Sia E=f_A(P) un elemento di f_A(M) ⇒ E≡ $P^{e_A}$ (mod n_A)
⇒ $E^{d_A} \equiv P^{e_Ad_A}$ (mod n_A) ⇒ $E^{d_A}$ ≡P (mod n_A) (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 n_A) e 0≤ $\bar{f_A}^{-1}(E)$ ≤n_A-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 è (n_A,d_A).
Si noti che per calcolare d_A è necessario conoscere, oltre a e_A (che è pubblico), il numero φ(n_A), che l’utente A tiene segreto; si ricordi che, partendo dalla conoscenza di n_A, conoscere φ(n_A) equivale a conoscere i due primi p_A e q_A (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 u_A ,v_A appartenenti a {0 ,…, q-1} (coprimi con q-1) tali che
[u_A]_q-1[u_A]_q-1= [1]_q-1
L’utente B sceglie due numeri naturali u_B ,v_B appartenenti a {0 ,…, q-1} (coprimi con q-1) tali che
[u_B]_q-1[u_B]_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 g^a .
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 (g^k,Pg^ak).
Quando l’utente A riceve un messaggio cifrato (g₁ , P₁), calcola il messaggio in chiaro P tenendo presente che
P₁ =P(g₁)^a , sicché P=P₁((g₁)^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 f_A:M → C definita da f_A(P)≡ P¹³ (mod 209) e 0≤f_A(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∙2³+1∙2²+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 f_A(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 f_A(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∙8²+2∙8+1
Scriviamo 71 in base 8: si ottiene 71=1∙8²+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∙8²+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∙2⁶+1∙2⁵+0∙2⁴+0∙2³+0∙2²+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: 3²=9; 3⁴=13; 3⁸=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 (3^k,11∙7^k).
Scegliamo k=3.
Dunque 3^k=3³=9∙3=10
Inoltre 7^k=7³=15∙7=3, sicché 11∙7^k=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=3^h e 6=P∙3^4h
Dunque 6=P∙3^4h=P∙3^h4=P∙5⁴; d’altra parte 5²=8 e quindi 5⁴=8²=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^-1bisogna 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.

Le lezioni del Corso

1. Espansione di un numero naturale in base b e complessità computazionale delle operazioni elementari

2. Complessità dell'algoritmo delle divisioni successive

3. Struttura dell'anello degli interi modulo m, funzione di Eulero

4. Equazioni congruenziali lineari e Teorema Cinese del Resto

5. Teorema di Fermat-Eulero e Piccolo teorema di Fermat. Alcune proprietà dei gruppi ciclici finiti

6. Cifrario di Cesare. Cifrario di Vigenere. Metodo di Hill

7. Richiami sui campi finiti. Generalità sulle curve ellittiche

8. Complessità delle operazioni nell'anello degli interi modulo m, nei campi finiti e nelle curve ellittiche

9. Premesse all'uso dei campi finiti in crittografia. Problema del logaritmo discreto. Algoritmo di Silver-Pohlig-Hellmann. Protocollo di Diffie-Hellmann

10. RSA. Sistema di di Massey-Omura. Sistema di El Gamal

11. Immersione dei testi in chiaro e sistemi crittografici in una curva ellittica

12. Resti quadratici e simbolo di Legendre

13. Condizioni necessarie e condizioni sufficienti per la primalità; forme di pseudoprimalità

14. Numeri di Carmichael

15. Test di Solovay-Strassen e Test di Miller-Rabin

16. Test di primalità basato sulle curve ellittiche e test AKS

17. Due metodi per inviare la firma digitale

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