•Alfredo De Santis
•04/04/2002
Crittosistema a chiave pubblica
Cifratura
file pubblico
file pubblico
utente
utente chiave
chiave pubblica
pubblica
A
kpub
A
kpub
…
…
…
…
chiave
chiave privata
privata
kpriv
kpriv
utente
utente chiave
chiave pubblica
pubblica
A
kpub
A
kpub
…
…
…
…
Devo cifrare il messaggio M
ed inviarlo ad A
iagio
nnarella
Crittografia a Chiave Pubblica
0
Cifratura
Cifratura di M per
A
Devo decifrare il
messaggio cifrato C
iagio
C ← CIFRA (kpub, M)
Crittografia a Chiave Pubblica
2
•Corso di Sicurezza su Reti
C
Crittografia a Chiave Pubblica
C?
3
“… both Gauss and lesser mathematicians may be
justified in rejoicing that there is one science at any
rate, and that their own, whose very remoteness
from ordinary human activities keep it gentle and
clean.”
G. H. Hardy, A Mathematician’s Apology, 1940
Decifratura di C
M ← DECIFRA (kpriv , C)
Crittografia a Chiave Pubblica
nnarella
??
Crittosistemi a chiave pubblica più comuni basati sulla
Teoria dei Numeri
file pubblico
utente
utente chiave
chiave pubblica
pubblica
A
kpub
A
kpub
…
…
…
…
nnarella
file pubblico
utente
utente chiave
chiave pubblica
pubblica
A
kpub
A
kpub
…
…
…
…
Teoria dei Numeri
Decifratura
chiave
chiave privata
privata
kpriv
kpriv
1
Decifratura
file pubblico
utente
utente chiave
chiave pubblica
pubblica
A
kpub
A
kpub
…
…
…
…
C
Crittografia a Chiave Pubblica
C
4
Crittografia a Chiave Pubblica
5
•1
•Alfredo De Santis
•04/04/2002
RSA
RSA
Proposto nel 1978 da
Rivest
Shamir
Shamir
Adleman
Rivest Adleman
Sicurezza basata sulla difficoltà di fattorizzare
Crittografia a Chiave Pubblica
6
Chiavi RSA
Crittografia a Chiave Pubblica
Cifratura RSA
file pubblico
chiave
chiave privata
privata
(n,d)
(n,d)
7
file pubblico
utente
utente chiave
chiave pubblica
pubblica
A
(n,e)
A
(n,e)
…
…
…
…
utente
utente chiave
chiave pubblica
pubblica
A
(n,e)
A
(n,e)
…
…
…
…
n = pq
p,q primi
Devo cifrare il messaggio M
ed inviarlo ad
A
ed = 1 mod (p-1)(q-1)
nnarella
iagio
Crittografia a Chiave Pubblica
8
Cifratura RSA
Crittografia a Chiave Pubblica
Decifratura RSA
file pubblico
file pubblico
utente
utente chiave
chiave pubblica
pubblica
A
(n,e)
A
(n,e)
…
…
…
…
C
Cifratura di M per
A
e
C ← M mod n
Crittografia a Chiave Pubblica
•Corso di Sicurezza su Reti
9
Devo decifrare il
messaggio cifrato C
iagio
10
utente
utente chiave
chiave pubblica
pubblica
A
(n,e)
A
(n,e)
…
…
…
…
C
??
C?
nnarella
Crittografia a Chiave Pubblica
11
•2
•Alfredo De Santis
•04/04/2002
Decifratura RSA
chiave
chiave privata
privata
(n,d)
(n,d)
“Piccolo” esempio: Chiavi RSA
file pubblico
file pubblico
chiave
chiave privata
privata
(n=3337,
(n=3337, d=1019)
d=1019)
utente
utente chiave
chiave pubblica
pubblica
A
(n,e)
A
(n,e)
…
…
…
…
utente
utente
A
A
…
…
Decifratura di C
3337 = 47 ·71
p = 47, q = 71
M ← Cd mod n
C
ed = 79 ·1019 = 1 mod 3220
(p-1)(q-1) = 46 ·70 = 3220
nnarella
nnarella
Crittografia a Chiave Pubblica
12
Esempio: Cifratura RSA
file pubblico
utente
utente
A
A
…
…
1570
chiave
chiave pubblica
pubblica
(n
(n==3337,
3337,ee==79)
79)
…
…
Crittografia a Chiave Pubblica
Esempio: Decifratura RSA
file pubblico
chiave
chiave privata
privata
(n=3337,
(n=3337, d=1019)
d=1019)
chiave
chiave pubblica
pubblica
(n
(n==3337,
3337,ee==79)
79)
…
…
13
utente
utente
A
A
…
…
chiave
chiave pubblica
pubblica
(n
(n==3337,
3337,ee==79)
79)
…
…
Decifratura di C = 1570
1019
688 ← 1570
Cifratura di M = 688 per
1570 ← 6887 9 mod 3337
A
iagio
Crittografia a Chiave Pubblica
14
Crittografia a Chiave Pubblica
15
Esempio: Cifratura RSA
file pubblico
utente
utente
A
A
…
…
1570
nnarella
“Piccolo” esempio: Chiavi RSA
chiave
chiave privata
privata
(n=55,
(n=55,d=27)
d=27)
mod 3337
file pubblico
chiave
chiave pubblica
pubblica
(n
(n == 55,
55, ee == 3)
3)
…
…
utente
utente
A
A
…
…
15
chiave
chiave pubblica
pubblica
(n
(n==55,
55,ee==3)
3)
…
…
55 = 11 ·5
p = 11, q = 5
Cifratura di M = 5 per
ed = 3 · 27 = 1 mod 40
(p-1)(q-1) = 10 · 4 = 40
15 ← 53 mod 55
A
nnarella
Crittografia a Chiave Pubblica
•Corso di Sicurezza su Reti
16
Crittografia a Chiave Pubblica
iagio
17
•3
•Alfredo De Santis
•04/04/2002
Esempio: Decifratura RSA
chiave
chiave privata
privata
(n=55,
(n=55,d=27)
d=27)
Esempio: Cifratura RSA
file pubblico
utente
utente
A
A
…
…
file pubblico
chiave
chiave pubblica
pubblica
(n
(n==55,
55,ee==3)
3)
…
…
utente
utente
A
A
…
…
47
chiave
chiave pubblica
pubblica
(n
(n==55,
55,ee==3)
3)
…
…
Decifratura di C = 15
27
5 ← 15
mod 55
Cifratura di M = 5718 per
47 ← 57183 mod 55
15
nnarella
Crittografia a Chiave Pubblica
18
Esempio: Decifratura RSA
chiave
chiave privata
privata
(n=55,
(n=55,d=27)
d=27)
file pubblico
utente
utente
A
A
…
…
27
file pubblico
utente
utente
A
A
…
…
27
53 ← 47
20
file pubblico
utente
utente
A
A
…
…
Crittografia a Chiave Pubblica
file pubblico
utente
utente
A
A
…
…
011110110100010
Decifratura di C = 47
27
nnarella
Crittografia a Chiave Pubblica
•Corso di Sicurezza su Reti
chiave
chiave pubblica
pubblica
(n
(n==55,
55,ee==3)
3)
…
…
55=1101112
mod 55
5718≡ 53 mod 55
21
Esempio corretto
15,13,2
chiave
chiave pubblica
pubblica
(n
(n==55,
55,ee==3)
3)
…
…
53 ← 47
47
nnarella
Esempio: Decifratura RSA
chiave
chiave privata
privata
(n=55,
(n=55,d=27)
d=27)
mod 55
53≠ 5718
47
Crittografia a Chiave Pubblica
chiave
chiave pubblica
pubblica
(n
(n==55,
55,ee==3)
3)
…
…
Decifratura di C = 47
mod 55
nnarella
19
Esempio: Decifratura RSA
Decifratura di C = 47
53 ← 47
iagio
Crittografia a Chiave Pubblica
chiave
chiave privata
privata
(n=55,
(n=55,d=27)
d=27)
chiave
chiave pubblica
pubblica
(n
(n==55,
55,ee==3)
3)
…
…
A
Cifratura di
001010011110010
15 ← 53 mod 55
13 ← 73 mod 55
2 ← 183 mod 55
47
22
Crittografia a Chiave Pubblica
iagio
23
•4
•Alfredo De Santis
•04/04/2002
Esempio corretto
Esempio: Decifratura RSA
file pubblico
15,13,2
utente
utente
A
A
…
…
011110110100010
chiave
chiave privata
privata
(n=55,
(n=55,d=27)
d=27)
chiave
chiave pubblica
pubblica
(n
(n==55,
55,ee==3)
3)
…
…
file pubblico
utente
utente
A
A
…
…
chiave
chiave pubblica
pubblica
(n
(n==55,
55,ee==3)
3)
…
…
Decifratura di C = 15,13,2
27
5 ← 15 mod 55
27
7 ← 1327 mod 55
18 ← 2 mod 55
Cifratura di M = 5718 per A
15 ← 53 mod 55
13 ← 73 mod 55
2 ← 183 mod 55
iagio
Crittografia a Chiave Pubblica
Esercizio
Svolgere altro “ piccolo ” esempio RSA
– Calcolo p, q
– Calcolo n
– Calcolo e, d
– Calcolo cifratura
– Calcolo decifratura
Crittografia a chiave pubblica
ed a chiave privata
q Vantaggi della crittografia a chiave pubblica
– Molto più veloce (ad es., DES è ≥100 volte più veloce
di RSA, in hardware tra 1.000 e 10.000 volte)
– Sufficiente in diverse situazioni
(ad esempio, applicazioni per singolo utente)
26
Crittografia a Chiave Pubblica
chiave
chiave privata
privata
kpriv
kpriv
file pubblico
utente
utente chiave
chiave pubblica
pubblica
A
kpub
A
kpub
…
…
…
…
Decifratura di
C1,C2
k ← DECIFRA (kpriv , C1)
M ← D (k, C2)
Cifratura di M per A
k ← genera chiave sessione
•Corso di Sicurezza su Reti
27
Digital Envelope: Decifratura
file pubblico
utente
utente chiave
chiave pubblica
pubblica
A
kpub
A
kpub
…
…
…
…
Crittografia a Chiave Pubblica
25
q Vantaggi della crittografia a chiave privata
Digital Envelope
C1 ← CIFRA (kpub, k)
C2 ← E (k, M)
15,13,2
Crittografia a Chiave Pubblica
– Chiavi private mai trasmesse
– Possibile la firma digitale
Crittografia a Chiave Pubblica
C1,C2
nnarella
24
iagio
28
nnarella
Crittografia a Chiave Pubblica
C1,C2
29
•5
•Alfredo De Santis
•04/04/2002
Digital Envelope : vantaggi
Correttezza decifratura RSA
Cd mod n = (Me)d mod n
ed = 1 mod (p-1)(q-1)
= Mde mod n
= M1+r(p-1)(q-1) mod n
= M mod n
Teorema di Eulero
=M
x ∈Z * ⇒ x (p-1)(q-1)=1 mod n
q Chiave di sessione solo per uno o
pochi messaggi
q Molto più veloce della sola
crittografia a chiave pubblica
n
poichè 0≤M<n
Crittografia a Chiave Pubblica
30
Funzione di Eulero
q φ(n) = cardinalità di Zn* = { x | 0<x<n
q φ(p) = p-1 se p primo
q φ(pq) = (p-1)(q-1) se p,q primi
x ∈ Zn* ⇒ x
Crittografia a Chiave Pubblica
31
Efficienza delle computazioni
tali che gcd(x,n)=1}
Come effettuare le computazioni?
– Elevazione a potenza modulare

1 
1  
1 
q φ(n) = n ⋅ 1 −  ⋅ 1 − L1 − 
 p1   p2   p k 
fattorizzazione n = p1e1 p2 e2... pkek, pi primo, ei ≥ 0
q Teorema di Eulero:
Prova
Prova per
per tutti
tutti gli
gli xx mediante
mediante
ilil teorema
teorema del
del resto
resto cinese
cinese
φ(n)
– Generazione e,d
d ← e-1 mod (p-1)(q-1)
– Generazione numeri primi
= 1 mod n
Crittografia a Chiave Pubblica
generazione di e
32
Elevazione a potenza modulare
Metodo naive
Calcolo di x y mod z
Crittografia a Chiave Pubblica
33
Elevazione a potenza modulare
Metodo naive
Calcolo di x y mod z
Potenza_Modulare_naive
Potenza_Modulare_naive (x,
(x, y,
y, z)
z)
Potenza_Modulare_naive
Potenza_Modulare_naive (x,
(x, y,
y, z)
z)
aa ←
← 11
for
for ii == 11 to
to yy do
do
aa ←
← (a
(a··x)
x) mod
mod zz
return
return aa
aa ←
← 11
for
for ii == 11 to
to yy do
do
aa ←
← (a
(a··x)
x) mod
mod zz
return
return aa
Se y è di 512 bit, occorrono ≈ 2512 operazioni
Crittografia a Chiave Pubblica
•Corso di Sicurezza su Reti
34
Crittografia a Chiave Pubblica
35
•6
•Alfredo De Santis
•04/04/2002
Elevazione a potenza modulare
Metodo left-to-right
Calcolo di xy mod z
Elevazione a potenza modulare
Metodo left-to-right
Calcolo di xy mod z
y = y 02 0+ y12 1 +… +y t 2t
Idea: y = y0+2(y1+ 2(y 2+… +2(y t-1+2yt)))))
Idea:
y = y 02 0+ y12 1 +… +y t 2t
y = y0+2(y1+ 2(y2+… +2(y t-1+2yt)))))
xy = xy 0+2(y 1+2(y 2+…+2(y t-1+2y t)))))
= xy 0 x2(y 1+2(y 2+…+2(y t-1+2y t)))))
Esempio:
40 = 0 ·2 0 + 0·21 + 0·2 2 + 1 ·2 3 + 0·24 + 1·2 5
= xy 0(xy 1+2(y 2+…+2(y t-1+2y t))))))2
40 = 0 + (2 (0 + 2 (0 + (2 (1 + 2 (0 + 2·1))))))
= xy 0( xy 1(xy 2+…+2(y t-1+2y t))))))2)2
= xy 0 (xy 1( … (xy t-1(xy t)2)2 … )2
Crittografia a Chiave Pubblica
36
Crittografia a Chiave Pubblica
Elevazione a potenza modulare
Metodo left-to-right
Calcolo di xy mod z
Idea: y = y0+2(y1+… +2(y t-1+2yt)))))
xy = xy 0 (… (xy t-1(xy t)2)2 … )2
y = y 02 0+ y12 1 +… +y t 2t
Potenza_Modulare
Potenza_Modulare (x,
(x, y,
y, z)
z)
40 = 0 ·2 0 + 0·21 + 0·2 2 + 1 ·2 3 + 0·24 + 1·2 5
40 = 0 + (2 (0 + 2 (0 + (2 (1 + 2 (0 + 2·1))))))
x40 = x0 ( x0
(x0
(x1
(x0 (x1 )2 )2 )2 ) 2 )2
Crittografia a Chiave Pubblica
2 0+
y = y0
20y 0+2 1y1…+2ty t
2 1 +…
y1
+y t
2t
39
Elevazione a potenza modulare
Metodo right-to-left
Calcolo di x y mod z
Idea:
xy = x
0
1
t
= x2 y 0 · x2 y 1 · … · x2 y t
0
1
t
= (x2 )y 0 · (x2 )y 1 · … · (x2 )y t
left-to-right
Crittografia a Chiave Pubblica
Metodo right-to-left
x y mod z
aa ←
← 11
for
for ii == tt downto
downto 00 do
do
aa ←
← (a
(a··a)
a) mod
mod zz
if
if yyii == 11 then
then aa ←
← (a
(a·· x)
x) mod
mod zz
return
return aa
38
Elevazione a potenza modulare
Idea:
Metodo left-to-right
Idea: y = y0+2(y1+… +2(y t-1+2yt)))))
xy = xy 0 (… (xy t-1(xy t)2)2 … )2
Esempio: x40
Calcolo di
Elevazione a potenza modulare
Calcolo di xy mod z
y = y 02 0+ y12 1 +… +y t 2t
37
20 y 0
y = y 02 0+ y12 1 +… +y t 2t
1
t
xy = (x ) · (x2 )y 1 · … · (x2 )y t
Esempio: x40
40 = 0 ·2 0+ 0·2 1 +0 ·2 2 + 1·23 + 0·2 4 + 1 ·2 5
x40 = (x1 )0 · (x2) 0 · (x4)0 · (x8)1 · (x16) 0 · (x3 2)1
Crittografia a Chiave Pubblica
•Corso di Sicurezza su Reti
40
Crittografia a Chiave Pubblica
41
•7
•Alfredo De Santis
•04/04/2002
Elevazione a potenza modulare
Metodo right-to-left
Calcolo di x y mod z
Idea:
y = y 02 0+ y12 1 +… +y t 2t
20 y 0
y
21 y 1
40 = 0 ·
=1
Idea:
y = y 02 0+ y12 1 +… +y t 2t
20 y 0
1
t
x = (x ) · (x2 )y 1 · … · (x2 )y t
y
Esempio: x40
0·
2 1 +0
· + 1· + 0· + 1 ·
22
23
24
40 = 0 ·2 0+ 0·2 1 +0 ·2 2 + 1·23 + 0·2 4 + 1 ·2 5
25
x2
=1
x40 = (x1 )0 · (x2) 0 · (x4)0 · (x8)1 · (x16) 0 · (x3 2)1
=1
=1
x4
x8
x16
x3 2
Crittografia a Chiave Pubblica
x40 =
42
Metodo right-to-left
Potenza_Modulare
Potenza_Modulare (x,
(x, y,
y, z)
z)
if
if yy == 00 then
then return
return 11
X
X←
← x;
x; PP ←
← 11
if
if yy00 == 11 then
then X
X←
← xx
for
for ii == 11 to
to tt do
do
X
X←
←X
X·X
·X mod
mod zz
if
then
PP ←
if yyi=1
=1
then
← PP·X
·X mod
modzz
i
return
return PP i 0 1 2
3
4
5
0
25
1
1
625
625
0
681
625
596mod 1234
55596
mod 1234
6
7
8
9
44
RSA Performance
decifratura
1024 bit cifratura
1024 bit decifratura
Crittografia a Chiave Pubblica
•Corso di Sicurezza su Reti
x8
· x32
43
Scelta esponente pubblico
qMinimizzare operazioni per elevazione a
potenza
qe←3
q e ← 216+1
decimale 65.537
binario 10000000000000001
Crittografia a Chiave Pubblica
45
Come effettuare le computazioni?
ms/operazione
512 bit
=1
=1
Efficienza delle computazioni
q Celeron 450, Windows 2000, Crypto++,
cifratura
=1
1
0
1
0
0
1
1011 369 421 779 947 925
67
67 1059 1059 1059 1013
Crittografia a Chiave Pubblica
512 bit
=1
Crittografia a Chiave Pubblica
Elevazione a potenza modulare
yi 0
X 5
P 1
Calcolo di x y mod z
x = (x ) · (x ) · … · (x )
x40 = (x1 )0 · (x2) 0 · (x4)0 · (x8)1 · (x16) 0 · (x3 2)1
x1
Metodo right-to-left
2t y t
Esempio: x40
2 0+
Elevazione a potenza modulare
– Elevazione a potenza modulare
0,2
– Generazione e,d
4
1
generazione di e
d ← e-1 mod (p-1)(q-1)
– Generazione numeri primi
27
46
Crittografia a Chiave Pubblica
47
•8
•Alfredo De Santis
•04/04/2002
Algoritmo di Euclide
Algoritmo di Euclide: Esempi
Descritto negli Elementi di Euclide (circa 300 A. C.)
Euclide
Euclide(a,b)
(a,b)
if
if bb == 00 then
then return
return aa
else
else return
return Euclide
Euclide (b,
(b, aa mod
modb)
b)
Euclide (4864,3458) = Euclide (3458,1406)
= Euclide (1406,646)
= Euclide (646,114)
= Euclide (114,76)
= Euclide (76,38)
= Euclide (38,0) = 38
Teorema
Teorema della
della ricorsione
ricorsione del
del gcd
gcd
Per
Per tutti
tutti gli
gli interi
interi aa ≥≥ 00 ee bb >> 00
gcd(a,b)
gcd(a,b) == gcd(b,a
gcd(b,a mod
mod b)
b)
Crittografia a Chiave Pubblica
Euclide (30,21) = Euclide (21,9)
= Euclide (9,3)
= Euclide (3,0) = 3
48
Algoritmo di Euclide: complessità
q Assumiamo a ≥ b
q Al massimo log b chiamate
q Per ogni chiamata O( (log a)2 ) operazioni su bit
q Totale: al massimo O( (log a)3 ) operazioni su bit
q Euclide (a,b) richiede al massimo O( (log a)2 )
operazioni su bit
Crittografia a Chiave Pubblica
49
Algoritmo di Euclide Esteso
Euclide-esteso
Euclide-esteso (a,b)
(a,b)
if
if bb == 00 then
then return
return (a,
(a, 1,
1, 0)
0)
(d´,
(d´, x´,
x´, y´)
y´) ←
← Euclide-esteso
Euclide-esteso (b,
(b, aamod
modb)
b)
(d,
(d, x,
x, y)
y) ←
← (d´,
(d´, y´,
y´, x´
x´-- a/b
a/b y´)
y´)
return
return (d,
(d, x,
x, y)
y)
q Computa interi d, x, y tali che d = gcd(a,b) = ax+by
q Stesso running time asintotico di Euclide (a,b)
Crittografia a Chiave Pubblica
50
Algoritmo di Euclide (iterativo)
Euclide_iterativo
Euclide_iterativo (a,b)
(a,b)
while
while bb ≠≠ 00 do
do
rr ←
← aa mod
mod b;
b; aa ←
← b;
b; bb ←
← r;
r;
return
a
return a
•Corso di Sicurezza su Reti
a, b, m calcolare x
0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
Esempi:
3x≡7 (mod 8) soluzione 5
2x≡4 (mod 8) soluzione 2,6
4x≡2 (mod 8) nessuna soluzione
52
51
Soluzione di ax≡b (mod m)
Dati
Esercizio: versione iterativa di
Euclide-esteso (a,b)
Crittografia a Chiave Pubblica
Crittografia a Chiave Pubblica
1 0 1 2 3 4 5 6 7
2 0 2 4 6 0 2 4 6
3 0 3 6 1 4 7 2 5
4 0 4 0 4 0 4 0 4
5 0 5 2 7 4 1 6 3
6 0 6 4 2 0 6 4 2
7 0 7 6 5 4 3 2 1
Crittografia a Chiave Pubblica
53
•9
•Alfredo De Santis
•04/04/2002
Soluzione di ax≡b (mod m)
Soluzione di ax≡1 (mod m)
gg == gcd
gcd(a,m)
(a,m)
gcd(a,m)
q Ha soluzioni se e solo se g|b
q Se g|b ci sono esattamente g distinte
q Ha soluzioni se e solo se gcd
gcd(a,m)
(a,m) =1
q Se gcd
gcd(a,m)
(a,m) =1 l’unica soluzione mod n è:
x´
soluzioni mod m:
x'
dove
b m
+i
g
g
dove
per i = 0,1,…, g-1
g = ax′+my (da Euclide-esteso (a,m) )
Crittografia a Chiave Pubblica
54
Soluzione di ax≡1 (mod 8)
3 = 3 -1 mod 8
5 = 5 -1 mod 8
7 = 7 -1 mod 8
4 0 4 0 4 0 4 0 4
5 0 5 2 7 4 1 6 3
3 = 5 -1 mod 7
Crittografia a Chiave Pubblica
56
Esempio: calcolo di 5-1 mod 7
3=
mod 7
•Corso di Sicurezza su Reti
2 = 4 -1 mod 7
6 = 6 -1 mod 7
0
0
0
0
0
0
0
0
1
0
1
2
3
4
5
6
2
0
2
4
6
1
3
5
3
0
3
6
2
5
1
4
4
0
4
1
5
2
6
3
5
0
5
3
1
6
4
2
Crittografia a Chiave Pubblica
6
0
6
5
4
3
2
1
57
Efficienza delle computazioni
Come effettuare le computazioni?
– Elevazione a potenza modulare
7
5
d
1
x y
-2 3
5
2
1
1 -2
2
1
1
0
1
0
1
1
Crittografia a Chiave Pubblica
0
1
2
3
4
5
6
4 = 2 -1 mod 7
5 = 3 -1 mod 7
6 0 6 4 2 0 6 4 2
7 0 7 6 5 4 3 2 1
d = x·a + y·b
1 = -2·7 + 3·5
1 = 1-1 mod 7
1 0 1 2 3 4 5 6 7
2 0 2 4 6 0 2 4 6
3 0 3 6 1 4 7 2 5
Euclide-esteso
Euclide-esteso (a,b)
(a,b)
if
if bb == 00 then
then return
return (a,
(a, 1,
1, 0)
0)
(d´,
(d´, x´,
x´, y´)
y´) ←
← Euclide-esteso
Euclide-esteso (b,
(b, aamod
modb)
b)
(d,
(d, x,
x, y)
y) ←
← (d´,
(d´, y´,
y´, x´
x´-- a/b
a/b y´)
y´)
return
a b
return (d,
(d, x,
x, y)
y)
55
Ha soluzioni se e solo se gcd
gcd(a,7)
(a,7) =1
0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 = 1-1 mod 8
Crittografia a Chiave Pubblica
Soluzione di ax≡1 (mod 7)
Ha soluzioni se e solo se gcd
gcd(a,8)
(a,8) =1
5 -1
1 = ax′+my (da Euclide-esteso (a,m) )
q Tale soluzione viene denotata con a -1 mod m
1
– Generazione e,d
generazione di e
d ← e-1 mod (p-1)(q-1)
– Generazione numeri primi
0
58
Crittografia a Chiave Pubblica
59
•10
•Alfredo De Santis
•04/04/2002
Generazione chiavi
Generazione chiavi
(comunemente usata in pratica)
1.
1. Input
Input LL (lunghezza
(lunghezza modulo)
modulo)
2.
2. Genera
Genera 22 primi
primi di
di lunghezza
lunghezza L/2
L/2
3.
3. nn ←
← pp ·q
·q
4.
4. Scegli
Scegli aa caso
caso ee
1.
1. Input
Input LL (lunghezza
(lunghezza modulo)
modulo)
16+1
2.
2. ee ←
← 33 oppure
oppure ee ←
← 2216
+1 (=
(= 65.537)
65.537)
3.
3. Genera
Genera 22 primi
primi di
di lunghezza
lunghezza L/2
L/2
4.
4. nn ←
← pp ·q
·q
5.
5. If
If gcd
gcd (( e,
e, (p-1)(q-1)
(p-1)(q-1) )) == 11
-1 mod
then
then dd ←
← ee-1
mod(p-1)(q-1)
(p-1)(q-1)
else
else goto
goto 3.
3.
5.
5. If
If gcd
gcd (( e,
e, (p-1)(q-1)
(p-1)(q-1) )) == 11
-1 mod
then
d
then d ←
← ee-1
mod (p-1)(q-1)
(p-1)(q-1)
else
goto
4.
else goto 4.
Crittografia a Chiave Pubblica
60
Generazione di un primo ‘grande’
1.
1. Genera
Genera aa caso
caso un
un dispari
dispari pp di
di grandezza
grandezza appropriata
appropriata
2.
2. Testa
Testa se
se pp èè primo
primo
3.
3. Se
Se pp èè composto,
composto, go
go to
to 1.
1.
Crittografia a Chiave Pubblica
61
Generazione di un primo ‘grande’
1.
1. Genera
Genera aa caso
caso un
un dispari
dispari pp di
di grandezza
grandezza appropriata
appropriata
2.
2. Testa
Testa se
se pp èè primo
primo
3.
3. Se
Se pp èè composto,
composto, go
go to
to 1.
1.
Variante
Variante con
con sequenza
sequenza di
di ricerca
ricerca
1.
1. Genera
Genera aa caso
caso un
un dispari
dispari pp di
di grandezza
grandezza appropriata
appropriata
2.
2. Testa
Testa se
se pp èè primo
primo
3.
3. Se
Se pp èè composto,
composto, pp ←
← p+2,
p+2, go
go to
to 2.
2.
Crittografia a Chiave Pubblica
62
Crittografia a Chiave Pubblica
Distribuzione dei numeri primi
Scelta di un primo di 512 bit
q Scelto un intero in [2,2512] la probabilità che sia
primo è circa 1 su ln 2512 (ln 2512 ≈ 354,89)
q π(x) = numero di primi in [2,x]
q Teorema dei numeri primi: lim
x→ ∞
p (x)
=1
x/ln x
q Numero medio di tentativi ≈ 354,89
q Se si scelgono solo dispari dimezza ≈ 177,44
q Esempio: π(1010) = 455.052.511
1010/ ln 1010 ≈ 434.294.481,9 (4% in meno)
q Se si scelgono dispari in [2511 ,2512] probabilità è
≈
q Per x ≥ 17
x
x
< p (x) < 1.25506
ln x
ln x
Crittografia a Chiave Pubblica
•Corso di Sicurezza su Reti
63
1 …
64
…
(ln22
512
512
−
2511
ln 2511
) 2 1 2 ≈ 1771,79
511
… 1
510 bit scelti a caso
Crittografia a Chiave Pubblica
65
•11
•Alfredo De Santis
•04/04/2002
Scelta di un primo di 1024 bit
q Scelto un intero in [2,21024] la probabilità che sia
primo è circa 1 su ln 21024 (ln 21024 ≈ 709,78)
Test di primalità
qIl miglior algoritmo deterministico è una
q Numero medio di tentativi ≈ 709,78
variante di Cohen e H. Lenstra del test
q Se si scelgono solo dispari dimezza ≈ 354,89
di Adleman, Pomerance e Rumely [1983]
q Se si scelgono dispari in [21023 ,21024] probabilità
≈
1 …
(ln22
…
1024
1024
−
21023
ln 21023
) 2 1 2 ≈ 3551,23
qComplessità (lg p)O(lg lg lg p)
1023
… 1
1022 bit scelti a caso
Crittografia a Chiave Pubblica
66
primo
Test
Test Primalità
Primalità
Probabilmente!
Probabilmente!
Certamente!
Certamente!
– dato a∈[0, p-1] è facile verificare se a∈W(p)
– se p è primo allora W(p) è vuoto
Scelgo
Scelgo aa
– se p è composto allora |W(p)| ≥ p/2
Crittografia a Chiave Pubblica
68
Test di primalità probabilistici
q Test di Solovay-Strassen
– Probabilità di errore ≤ (1/2)t
volte allora la probabilità di errore ≤ (1/2)t
Crittografia a Chiave Pubblica
69
Test di Solovay-Strassen
q Sia n un numero composto dispari.
|{a : gcd(a,n) = 1 and a(n-1)/2 = (a|n) mod n} | ≤ φ(n)/2
q Test di Miller-Rabin
– Il più usato in pratica
q Insieme di witness di Eulero
– Il più veloce
W E(n) = {a : gcd(a,n)>1 oppure a(n-1)/2 ≠ (a|n) mod n}
(1/4)t
Crittografia a Chiave Pubblica
•Corso di Sicurezza su Reti
q Se il test viene ripetuto indipendentemente t
q (a|n) simbolo di Jacobi
q Criterio di Eulero: Sia n un primo dispari.
gcd(a,n) = 1 ⇒ a(n-1)/2 = (a|n) mod n
– Pubblicato nel 1977
– Probabilità di errore ≤
q Probabilità di errore (n è composto ma viene
dichiarato primo) di tale test ≤ 1/2
composto
Insieme di witness W(p)
67
Diminuizione della
probabilità di errore
Test di primalità probabilistici
p
Crittografia a Chiave Pubblica
70
Crittografia a Chiave Pubblica
71
•12
•Alfredo De Santis
•04/04/2002
Simbolo di Jacobi
q (a|n) = (a|p1) e1 (a|p2 ) e2... (a|pk) ek
(a|p) =
Simbolo di Jacobi
Simbolo di Legendre
p primo
(a|p) = a(p-1)/2 mod p
0 se p divide a
1 se a è un quadrato mod p
-1 se a non è un quadrato mod p
fattorizzazione dispari n = p1e 1 p2e 2... pk e k , pi primo, ei ≥ 0
q Può essere computato con O((log n) 2) operazioni su bit
– (a|n) = 0 ⇔ gcd(a,n) > 1
– a = b mod n ⇒ (a|n) = (b|n)
– (ab|n) = (a|n) (b|n)
2
– (2|n) = (-1)(n -1)/8
– (m|n) = (n|m) (-1)(n-1)(m -1)/4
Crittografia a Chiave Pubblica
72
s
n-1
n-1 == 22srr con
con rr dispari
dispari
q Se n è un primo dispari
W MR(n) è vuoto
W MR (91) = {a : a45 ≠ 1 mod 91 and
j
a2 ·45 ≠ -1 mod 91 per ogni j∈[0,0]}
q Se n è un numero composto dispari
| W MR (n) | ≥ (3/4) ·φ(n)
Sono 18 = φ(91)/4 elementi
74
Witness di Miller-Rabin
n=105
105 = 3·5
3 5 ·77
105 = 3·5 ·7
3
105-1
105-1 == 223··13
13
j∈[0,2]
1
91-1
91-1 == 221··45
45
{1,9,10,12,16,17,22,29,38,53,62,69,74,75,79,81,82,90}
Crittografia a Chiave Pubblica
}
q Strong liars: elementi in {1,2,…,104} / W MR (105)
{1,104}
Crittografia a Chiave Pubblica
75
Fattorizzazione
Dato n calcolare l’unica fattorizzazione
e
e
e
n = p1 1 p2 2... pk k
con pi primo ed ei ≥ 0
Splitting di n: calcolare due interi a,b >1
Sono solo 2 < 12 = φ(105)/4 elementi
In genere strong liars molto meno di φ(n)/4
•Corso di Sicurezza su Reti
73
q Strong liars: elementi in {1,2,…,90} / W MR (91)
q Se n è un numero composto dispari (n ≠ 9)
| W MR(n) | ≥ (3/4) ·φ(n)
Crittografia a Chiave Pubblica
Crittografia a Chiave Pubblica
q Witness di Miller-Rabin
W MR(n) = {a : a r ≠ 1 mod n and
j
a 2 r ≠ -1 mod n per ogni j∈[0,s-1] }
W MR (105) = {a : a ≠ 1 mod 105 and
j
a2 ·13 ≠ -1 mod 105 per ogni
Esempio:
Esempio: (158|235)
(158|235) == (2|235)
(2|235) (79|235)
(79|235)
(78)(234)/4
== (-1)
(-1)(235|79)
(235|79)(-1)
(-1) (78)(234)/4
== (77|79)
(77|79)
(76)(78)/4
== (79|77)
(79|77) (-1)
(-1) (76)(78)/4
== (2|77)
(2|77)
== -1
-1
91 = 7·13
q Insieme di witness di Miller-Rabin
13
– (ab|n) = (a|n) (b|n)
2
– (2|n) = (-1)(n -1)/8
– (m|n) = (n|m) (-1)(n-1)(m -1)/4
Witness di Miller-Rabin
n=91
91 = 7·13
7 13
Test di Miller-Rabin
q Witness di Miller-Rabin
Può essere computato con O((log n) 2 ) operazioni su bit
– a = b mod n ⇒ (a|n) = (b|n)
76
(fattori non-triviali) tali che n = a·b
Crittografia a Chiave Pubblica
77
•13
•Alfredo De Santis
•04/04/2002
Fattorizzazione: un semplice algoritmo
Calcolo di un fattore primo:
Per tutti i primi p in [2,
Complessità di tempo sub-esponenziale in media
Lq[a,c] = O(e(c+o(1))(ln q)
n]
q General number field sieve : Ln[ 1/3, 1.923]
n ≈ 2 256
il più veloce
Crittografia a Chiave Pubblica
78
Crittografia a Chiave Pubblica
Quadratic sieve in pratica
q Quadratic sieve è migliore dell’algoritmo basato su
curve ellittiche
q Implementazioni del Quadratic sieve
1 mips per anno
13
≈ 3 ·10 istruzioni
RSA-- 129
RSA
1600 computer
per 8 mesi
factoring by e-mail
= 425 bit
Crittografia a Chiave Pubblica
80
Calcolo di fattori “piccoli”
q Algoritmo Rho di Pollard: tempo medio O(√p)
q Algoritmo basato su curve ellittiche: tempo medio
(√2+o(1))(l n q )1/2(lnln q)1/2
)
q General Number field sieve è migliore del Quadratic
sieve solo per interi di almeno 110-120 cifre decimali
q RSA-130, fattorizzato nel 1996 con 500 mips per
anno
q RSA-140, fattorizzato il 2 febbraio 1999, elapsed
time 9 settimane
q RSA-155, fattorizzato il 22 agosto 1999, con 8000
mips per anno, elapsed time 7,4 mesi
160
160
88
120
120
44
175-400
175-400MHz
MHzSGI
SGIand
andSun
Sunworkstations
workstations
250
250MHz
MHzSGI
SGIOrigin
Origin2000
2000 processors
processors
300-450
300-450MHz
MHzPentium
PentiumIIIIPCs
PCs
500
500MHz
MHzDigital/Compaq
Digital/Compaqboxes
boxes
512 bit!
Crittografia a Chiave Pubblica
81
Una strategia generale per fattorizzare
q Prova divisione per alcuni piccoli primi (2,3,5,7,…)
q Prova algoritmo Rho di Pollard
q Prova algoritmo basato su curve ellittiche
q Prova Quadratic sieve oppure
tipo
tipo nn == pq
pq con
con p,q
p,q primi
primi della
della stessa
stessa lunghezza
lunghezza
•Corso di Sicurezza su Reti
General Number field sieve in pratica
Cerca fattori “grandi”
II numeri
numeri più
più difficili
difficili da
da fattorizzare
fattorizzare sono
sono del
del
Crittografia a Chiave Pubblica
79
Cerca fattori “piccoli”
Algoritmi per calcolare un fattore p di n:
Lp[1/2, √2] = O(e
)
q Quadratic sieve: Ln[ 1/2, 1]
(accade se n = pq)
mips per anno
0.01
140
825
5000
(lnln q) 1-a
q Algoritmo basato su curve ellittiche: Ln[ 1/2, 1]
Complessità caso peggiore Θ( n )
anno numero digit
1984
71
1988
106
1993
120
1994
129
a
con c > 0 ed 0 < a < 1
Se p|n allora p è fattore di n
Se n ha 512 bit allora
Fattorizzazione: complessità algoritmi
82
General Number field sieve
Crittografia a Chiave Pubblica
83
•14
•Alfredo De Santis
•04/04/2002
Che modulo scegliere?
Intrattabilità della fattorizzazione
qAd oggi, i numeri più difficili da
fattorizzare sono del tipo n = p ·q con
p,q primi della stessa lunghezza
q… e di almeno (per essere tranquilli!)
– 768 bit ( = 230 digit) per uso personale
– 1024 bit per le aziende
– 2048 per chiavi “importanti”
ad esempio Autorità di Certificazione
Crittografia a Chiave Pubblica
La sicurezza di molte tecniche crittografiche si
basa sulla intrattabilità della fattorizzazione:
q crittosistema RSA, Rabin
q firme digitali RSA
q…
84
Crittografia a Chiave Pubblica
Sicurezza di RSA
Se
Sicurezza di RSA
potesse fattorizzare…
Se
86
Crittografia a Chiave Pubblica
Sicurezza di RSA
Se
potrebbe calcolare d ← e
n = pq
ϕ(n) = (p -1)(q-1)
Se
sostituendo
sostituendo pp == n/q
n/q
pp22-- (n(n-ϕ(n)+1)p
ϕ(n)+1)p ++ nn == 00
Due soluzioni: p,q
•Corso di Sicurezza su Reti
potesse computare ϕ(n) = (p-1)(q-1),
potrebbe calcolare d ← e-1 mod (p-1)(q-1)
mod (p-1)(q-1)
Crittografia a Chiave Pubblica
87
Sicurezza di RSA
potesse computare ϕ(n)=(p-1)(q-1),
-1
potesse computare ϕ(n)=(p-1)(q-1)
potrebbe calcolare d ← e-1 mod (p-1)(q-1)
1.
1. Fattorizza
Fattorizza nn
2.
2. Computa
Computa (p-1)(q-1)
(p-1)(q-1)
3.
3. Computa
Computa dd ←
← ee-1-1 mod
mod (p-1)(q-1)
(p-1)(q-1)
Crittografia a Chiave Pubblica
85
n = pq
ϕ(n) = (p -1)(q-1)
sostituendo
sostituendo pp == n/q
n/q
pp22-- (n(n-ϕ(n)+1)p
ϕ(n)+1)p ++ nn == 00
84.773.093 = pq pp22-- 18.426
18.426 pp ++ 84.773.093
84.773.093 == 00
84.754.668 = (p-1)(q-1)
radici: 9539 e 8887
88
Crittografia a Chiave Pubblica
89
•15
•Alfredo De Santis
•04/04/2002
Sicurezza di RSA
Se
Sicurezza di RSA
Se
potesse computare d …
potesse computare d … ma questo è
computazionalmente equivalente a fattorizzare!
Crittografia a Chiave Pubblica
90
91
Piccoli messaggi
Sicurezza di RSA
Se
Crittografia a Chiave Pubblica
q Posso cifrare un solo digit 0,1,… ,9 con RSA ?
potesse computare d … ma questo è
C ← Me mod n
computazionalmente equivalente a fattorizzare!
Esempio:
Un
Un algoritmo
algoritmo che
che computa
computa dd (con
(con input
input n,e)
n,e)
125 ← 53 mod 6.012.707
può
può essere
essere usato
usato come
come oracolo
oracolo in
in un
un algoritmo
algoritmo
Las
Las Vegas
Vegas che
che fattorizza
fattorizza nn con
con probabilità
probabilità ≥1/2
≥1/2
Crittografia a Chiave Pubblica
92
Piccoli messaggi
93
Proprietà moltiplicativa di RSA
q Posso cifrare un solo digit 0,1,… ,9 con RSA ?
C ← Me mod n
Esempio:
Crittografia a Chiave Pubblica
Proprietà di omomorfismo
C1 = M1 e mod n
(M1M2 ) e = M 1 e M2 e = C1 C2 mod n
C2 = M2 e mod n
125 ← 53 mod 6.012.707
q Se M < n 1/e allora
– uso di Digital Envelope
– salting del messaggio M
Crittografia a Chiave Pubblica
•Corso di Sicurezza su Reti
94
Crittografia a Chiave Pubblica
95
•16
•Alfredo De Santis
•04/04/2002
Proprietà moltiplicativa di RSA
C1 = M1e mod n
C2 = M2 e mod n
(M1M2 ) e = M 1e M2 e = C1C2 mod n
q Piccolo esponente pubblico (ad es., e = 3)
– Stesso messaggio inviato a più utenti
Chosen-ciphertext attack adattivo
Obiettivo: decifrare C (= Me mod n)
Decifrazione
Decifrazione
(d,n)
(d,n)
Attacchi ad RSA
q Attacchi ad implementazioni:
– Timing Attack
– Random Faults
– Attacco di Bleichenbacher [1998 ] su PKCS 1 (vecchia
versione): uso del Web browser come oracolo!
Scelgo x a caso
C' ← C ·xe mod n
M' ← (C') d mod n
02
02
M ← M' ·x-1 mod n
M' = (C') d =(C ·xe ) d = Cd ·x mod n
Crittografia a Chiave Pubblica
00
00
M
M
16 bit
96
Crittografia a Chiave Pubblica
Informazioni parziali per RSA
Dato C
Random
Random
97
Un bit “facile” per RSA
e
C
C == M
Me mod
modnn
e
C
C == M
Me mod
modnn
E’ facile calcolare il simbolo di
Jacobi del testo in chiaro
– potrebbero esserci informazioni parziali
sul messaggio M “facili” da ottenere
(senza dover decifrare C ! )
(C|n) = (Me |n) = (M|n) e = (M|n)
– e … “difficili” ?
hard bit : ultimi c ·loglog n bit
Crittografia a Chiave Pubblica
98
Crittografia a Chiave Pubblica
Un bit “difficile” per RSA
halfn,e(C) =
99
Un bit “difficile” per RSA
0 se M < n/2
halfn,e(C) =
1 se M > n/2
0 se M < n/2
1 se M > n/2
Calcolare halfn ,e( ·) è computazionalmente
equivalente ad invertire RSA
C
Calcola
Calcola
half
(·)
halfn,e
n,e (·)
Crittografia a Chiave Pubblica
•Corso di Sicurezza su Reti
100
half n,e (C)
C
Decifra
Decifrann,e
,e
M
Calcola
Calcola
half
(·)
halfn,e
n,e(·)
Crittografia a Chiave Pubblica
101
•17
•Alfredo De Santis
•04/04/2002
Un bit “difficile” per RSA
halfn,e(C) =
Un bit “difficile” per RSA
0 se M < n/2
1 se M > n/2
half n,e (C) =
0 se M < n/2
halfn,e(C) =
0
C ´←
1
C ·(2e
1 se M > n/2
C´= (2 ·M)e mod n
mod n)
half n,e (C´) = 0
M∈ 0
n/2
M∈ 0
Crittografia a Chiave Pubblica
102
halfn,e(C´´) =
M∈ 0
0
n/8
n/4
1
3n/8
0
n/2
1
0
3n/4
n
103
1
5n/8 3n/4 7n/8
Crittografia a Chiave Pubblica
Predicato
n/2
q Dopo log n chiamate ad halfn,e( ·)
l’intervallo consta di un solo valore
C´´= (4 ·M)e mod n
0
n/4
q Ricerca binaria
1 se M > n/2
1
1
Un bit “difficile” per RSA
0 se M < n/2
C´´← C ·(4e mod n)
0
Crittografia a Chiave Pubblica
Un bit “difficile” per RSA
halfn,e(C) =
1
n
n
104
parità
e
C
C == M
Me mod
modnn
paritàn,e(C) = bit meno significativo di M
I predicati paritàn,e( ·) e halfn,e( ·)
sono computazionalmente equivalenti
Crittografia a Chiave Pubblica
105
Crittografia probabilistica
Testo in chiaro
Testo cifrato
M = M1 M2 M3 …
C = C 1 C2 C3 …
Mi = predicato_difficile (Ci)
halfn,e(Me mod n) = paritàn,e((2M) e mod n)
e
half
(C) = parità n,e(( CC (2
halfn,e
(2e mod
mod n)
n) mod
mod nn ))
n,e(C) = paritàn,e
e
parità
(C) = half ,e(( CC ((2
paritàn,e
((2-1-1))emod
mod n)
n) mod
mod nn ))
n,e(C) = halfnn,e
Crittografia a Chiave Pubblica
•Corso di Sicurezza su Reti
106
Crittografia a Chiave Pubblica
107
•18
•Alfredo De Santis
•04/04/2002
Alcuni Crittosistemi
a chiave pubblica
q RSA [1977] (fattorizzazione)
q Merkle-Hellman [1978] (zaino 0 -1)
Funzioni one-way
rotto!
– Molte varianti… rotte! Resiste Chor-Rivest [1988]
q
q
q
q
“Facili” da calcolare e
Rabin [1979] (fattorizzazione)
McEliece [1978] (decodifica codici lineari)
El-Gamal [1984] (logaritmo discreto)
Uso di curve ellittiche [1985]
curve iperellittiche [1989]
automi cellulari [1985]
Crittografia a Chiave Pubblica
108
Funzioni one-way trapdoor
“Facili” da calcolare e
Crittografia a Chiave Pubblica
… a meno che si conosca
una “trapdoor”
110
109
Alcuni brevetti software (USA)
numero
3.962.539
4.200.770
4.218.582
4.424.414
4.405.829
4.748.668
4.850.017
5.140.634
5.231.668
5.214.703
5.276.737
“difficili” da invertire
Crittografia a Chiave Pubblica
“difficili” da invertire
oggetto
DES
Diffie-Hellman
Critt. chiave pubblica
Pohling-Hellman
RSA
Shamir-Fiat
Vettori di controllo
Guillou-Quisquater
DSA
IDEA
Fair Cryptosystems
inventore
Ehrsam ed al.
Hellman, Diffie, Merkle
Helman, Merkle
Hellman, Pohling
Rivest, Shamir, Adleman
Shamir, Fiat
Matyas, Meyer, Bracht
Guillou-Quisquater
Kravitz
Massey-Lai
Micali
Crittografia a Chiave Pubblica
scadenza
1993
1997
1997
3 gen 2001
20 sett 2000
2005
2006
2009
2010
2010
2011
111
Export dagli USA
International Traffic in Arms Regulations (ITAR)
q United States Munitions List
q Strong encryption
[1989]
– RSA ≥ 512 bit
– cifrari a blocco (DES, IDEA, RC6,…) ≥40 bit
q eccetto se limitato a
non deve essere facilmente
– controllo accessi (ad es., ATM)
utilizzabile per cifrare!
– autenticazione dati (ad es., MAC, firme)
q Permesso dal Department of Commerce,
ad es. Cybercash, cifratura RSA 768 bit per transazioni finanziarie
Crittografia a Chiave Pubblica
•Corso di Sicurezza su Reti
112
•19