Crittografia a chiave pubblica - Dipartimento di Informatica

Crittografia a chiave
pubblica
Cifrari simmetrici
Barbara Masucci
Dipartimento di Informatica ed Applicazioni
Alice
Università di Salerno
canale insicuro
[email protected]
http://www.dia.unisa.it/professori/masucci
Bob
Barbara Masucci - DIA – Università di Salerno
Gestione delle chiavi
Problemi
Come fanno Alice e Bob a condividere
In una rete con n utenti ogni coppia di utenti deve
condividere una chiave
una chiave comune?
- Ogni utente deve memorizzare n-1 chiavi
Uso di un canale privato
- Il numero totale delle chiavi segrete e’ dell’ordine di n2/2
- un corriere fidato…
- un incontro faccia a faccia in un posto segreto…
- che stabilisce la chiave di sessione e la invia ad
Barbara Masucci - DIA – Università di Salerno
L’aggiunta di un nuovo utente alla rete implica la
distribuzione della chiave a tutti i precedenti utenti...
Uso di una terza parte fidata...
entrambi in modo sicuro...
1
Soluzione: cifrari asimmetrici
2
Barbara Masucci - DIA – Università di Salerno
3
Cifrari asimmetrici
Cifrari asimmetrici
Usano una cassaforte con due lucchetti
m
¾Con una chiave (pubblica) chiudiamo la
cassaforte
¾Con l’altra chiave (privata) apriamo la
cassaforte
m
Alice
can
a
chiave
pubblica di
Bob
Public key ≠ Private key
≠
4
Barbara Masucci - DIA – Università di Salerno
chiave privata
kpriv
utente chiave pubblica
…
file pubblico
utente chiave pubblica
Alice
kpub
…
…
Alice
Alice
6
kpub
…
canal
e insi
curo
Devo cifrare il messaggio
M ed inviarlo ad Alice
Barbara Masucci - DIA – Università di Salerno
Bob
5
Cifratura
file pubblico
Alice
le i
nsic
uro
Barbara Masucci - DIA – Università di Salerno
Cifrari asimmetrici
chiave privata
kpriv
chiave
privata di
Bob
Barbara Masucci - DIA – Università di Salerno
Bob
7
Cifratura
chiave privata
kpriv
Decifratura
file pubblico
Devo decifrare il
messaggio cifrato C
utente chiave pubblica
Alice
…
kpub
…
file pubblico
utente chiave pubblica
Alice
kpub
…
…
C
canal
e insi
curo
Alice
C?
Cifratura di M per Alice
C ← CIFRA (kpub, M)
Alice
Bob
8
Barbara Masucci - DIA – Università di Salerno
Decifratura
chiave privata
kpriv
…
Decifratura di C
M ← DECIFRA (kpriv, C)
Barbara Masucci - DIA – Università di Salerno
9
¾ Chiunque può cifrare un messaggio per Alice
¾ Solo Alice può decifrare un messaggio cifrato
per lei
¾ Non ci sono chiavi condivise tra gli utenti
utente chiave pubblica
Alice
kpub
Alice
Barbara Masucci - DIA – Università di Salerno
Cifrari asimmetrici
file pubblico
…
??
¾ Ogni utente genera da solo la propria coppia di
chiavi (public key, private key) e rende pubblica la
chiave pubblica
C
¾ Ogni utente memorizza una sola chiave
(privata)
10
Barbara Masucci - DIA – Università di Salerno
11
Cifrari simmetrici e
asimmetrici
Cifrari ibridi
chiave privata
kpriv
Vantaggi della crittografia a chiave pubblica
¾ Chiavi private mai trasmesse
¾ Possibile la firma digitale
Alice
Vantaggi della crittografia a chiave privata
…
¾ 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)
12
Barbara Masucci - DIA – Università di Salerno
Cifrari ibridi
chiave privata
kpriv
file pubblico
utente chiave pubblica
Alice
C C
2
kpub
…
canal
1
e insi
curo
Cifratura di M per Alice
k ← genera chiave sessione
C1 ← CIFRA (kpub, k)
C2 ← E (k, M)
Bob
Barbara Masucci - DIA – Università di Salerno
13
Cifrari asimmetrici
file pubblico
utente chiave pubblica
Alice
kpub
…
Decifratura di C1,C2
k ← DECIFRA (kpriv, C1)
M ← D (k, C2)
Alice
Barbara Masucci - DIA – Università di Salerno
Come realizzarli?
…
C1,C2
14
Barbara Masucci - DIA – Università di Salerno
15
Funzioni one-way
Funzioni one-way trapdoor
“Facili” da calcolare e
“Facili” da calcolare e
“difficili” da invertire
“difficili” da invertire
… a meno che si conosca
una “trapdoor”
Barbara Masucci - DIA – Università di Salerno
16
RSA
Chiavi RSA
Proposto nel 1978 da
chiave privata
(n,d)
file pubblico
utente chiave pubblica
Alice
(n,e)
…
Rivest
Shamir
…
n = pq
p,q primi
Adleman
Alice
Barbara Masucci - DIA – Università di Salerno
17
Barbara Masucci - DIA – Università di Salerno
18
gcd(e, (p-1)(q-1))=1
ed = 1 mod (p-1)(q-1)
Barbara Masucci - DIA – Università di Salerno
19
Cifratura RSA
Cifratura RSA
chiave privata
(n,d)
chiave privata
(n,d)
file pubblico
utente chiave pubblica
Alice
…
(n,e)
…
…
canal
e insi
curo
Alice
20
…
Alice
…
C
Barbara Masucci - DIA – Università di Salerno
21
Barbara Masucci - DIA – Università di Salerno
Decifratura RSA
file pubblico
file pubblico
utente chiave pubblica
Alice
(n,e)
Bob
C ← Me mod n
Decifratura RSA
Devo decifrare il
messaggio cifrato C
C
Cifratura di M per Alice
Bob
Barbara Masucci - DIA – Università di Salerno
…
canal
e insi
curo
Alice
Devo cifrare il messaggio
M ed inviarlo ad Alice
file pubblico
utente chiave pubblica
(n,e)
Alice
chiave privata
(n,d)
??
utente chiave pubblica
Alice
(n,e)
…
Decifratura di C
M ← C d mod n
C?
Alice
22
Barbara Masucci - DIA – Università di Salerno
…
C
23
“Piccolo” esempio:
“Piccolo” esempio:
Chiavi RSA
chiave privata
(n=3337, d=1019)
Cifratura RSA
file pubblico
utente
Alice
…
file pubblico
chiave pubblica
1570
(n = 3337, e = 79)
…
utente
chiave pubblica
Alice
…
(n = 3337, e = 79)
…
3337 = 47 ·71
p = 47, q = 71
Alice
Cifratura di M = 688 per Alice
79
1570 ← 688 mod 3337
ed = 79 ·1019 = 1 mod 3220
(p-1)(q-1) = 46 ·70 = 3220
Bob
24
Barbara Masucci - DIA – Università di Salerno
“Piccolo” esempio:
Correttezza decifratura RSA
Decifratura RSA
chiave privata
(n=3337, d=1019)
utente
Alice
…
25
Barbara Masucci - DIA – Università di Salerno
file pubblico
Cd mod n = (Me)d mod n
ed = 1 mod (p-1)(q-1)
ed
= M mod n
= M1+k(p-1)(q-1) mod n
= M·(M(p-1)(q-1))k
Teorema di Eulero
M∈Zn* ⇒ M
=1 mod n
= M mod n
Per
∈Zn//Z
Z * usa
Per M
M∈Z
n nn* usa
il
teorema
cinese
del
il
teorema
cinese
del resto
resto
=M
chiave pubblica
(n = 3337, e = 79)
…
Decifratura di C = 1570
1019
mod 3337
688 ← 1570
(p-1)(q-1)
Alice
1570
poichè 0≤M<n
Barbara Masucci - DIA – Università di Salerno
26
Barbara Masucci - DIA – Università di Salerno
27
Efficienza delle
computazioni
Generazione chiavi
RSA utilizza le seguenti computazioni
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
5.
5. If
If gcd
gcd (( e,
e, (p-1)(q-1)
(p-1)(q-1) )) == 11
then
then dd ←
← ee-1-1 mod
mod (p-1)(q-1)
(p-1)(q-1)
else
else goto
goto 4.
4.
¾Generazione numeri primi p e q
¾Generazione e,d
generazione di e
d ← e-1 mod (p-1)(q-1)
¾Elevazione a potenza modulare
¾Per cifratura e decifratura
Barbara Masucci - DIA – Università di Salerno
28
Scelta esponente pubblico
¾Minimizzare operazioni per elevazione a
potenza
29
Generazione chiavi
(comunemente usata in pratica)
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
then
then dd ←
← ee-1-1 mod
mod (p-1)(q-1)
(p-1)(q-1)
else
else goto
goto 3.
3.
¾e←3
¾ e ← 216+1
¾decimale 65.537
¾binario 10000000000000001
Barbara Masucci - DIA – Università di Salerno
Barbara Masucci - DIA – Università di Salerno
30
Barbara Masucci - DIA – Università di Salerno
31
Sicurezza di RSA
RSA Performance
Celeron 850MHz, Windows 2000, Crypto++,
millisecondi/
operazione
512 bit
cifratura
0,14
512 bit
decifratura
1,93
1024 bit cifratura
0,32
1024 bit decifratura
10,23
2048 bit cifratura
0,89
2048 bit decifratura
64,13
Barbara Masucci - DIA – Università di Salerno
Sicurezza della generazione delle chiavi
C
32
Sicurezza generazione
chiavi di RSA
Sicurezza della cifratura
Barbara Masucci - DIA – Università di Salerno
33
Attacco 1: fattorizzare n
Se
Conoscendo la chiave pubblica (n,e)
potesse fattorizzare n, saprebbe
computare d
1. Fattorizza n
2. Computa ϕ(n)=(p-1)(q-1)
3. Computa d ← e-1 mod (p-1)(q-1)
vuole calcolare la chiave privata
d=e-1 mod (p-1)(q-1)
Barbara Masucci - DIA – Università di Salerno
34
Barbara Masucci - DIA – Università di Salerno
35
Attacco 2: computare ϕ(n)
Attacco 2: computare ϕ(n)
Se
Se
potesse computare ϕ(n)=(p-1)(q-1),
Saprebbe fattorizzare n
saprebbe fattorizzare n
n = pq
ϕ(n) = (p-1)(q-1)
ϕ(n) = (p-1)(q-1)
84.773.093 = pq p2- 18.426 p + 84.773.093 = 0
84.754.668 = (p-1)(q-1)
radici: 9539 e 8887
Due soluzioni: p,q
36
37
Barbara Masucci - DIA – Università di Salerno
Algoritmo Las Vegas per
fattorizzare
Attacco 3: computare d
Se
sostituendo p = n/q
2
p - (n-ϕ(n)+1)p + n = 0
n = pq
sostituendo p = n/q
p2- (n-ϕ(n)+1)p + n = 0
Barbara Masucci - DIA – Università di Salerno
potesse computare ϕ(n) = (p-1)(q-1),
potesse computare d saprebbe
(n,e) Calcola
fattorizzare n
d
d
Un algoritmo che computa d (con input n,e) può essere
usato come oracolo in un algoritmo Las Vegas che
(n,e)
fattorizza n con probabilità ≥1/2
Barbara Masucci - DIA – Università di Salerno
Fattorizza n
Calcola
d
38
(p,q)
nessuna
risposta
Barbara Masucci - DIA – Università di Salerno
prob 1/2
prob 1/2
39
Sicurezza generazione
chiavi di RSA
Fattorizzazione
Fattorizza n Æ Computa d
¾Dato n, calcolare due primi p, q >1 tali che n=pq
Computa d
¾ Per valori grandi di n è un problema ritenuto
computazionalmente difficile
Æ Fattorizza n
¾Complessità di tempo sub-esponenziale in media
Computare d è equivalente a fattorizzare n
40
Barbara Masucci - DIA – Università di Salerno
Calcolo di un fattore primo:
a
n]
con c > 0 ed 0 < a < 1
(esponenziale nella lunghezza dell’input)
Barbara Masucci - DIA – Università di Salerno
1-a
Lq[a,c] = O(e(c+o(1))(ln q) (lnln q) )
Complessità caso peggiore Θ( n ) = Θ(21/2 log n)
n ≈2
41
Barbara Masucci - DIA – Università di Salerno
Complessità di tempo sub-esponenziale in media
Se p|n allora p è fattore di n
Se n ha 512 bit allora
f(n)
=0
¾f(n)=o(g(n)) se lim
n →∞ g(n)
Fattorizzazione:
complessità algoritmi
Fattorizzazione:
un semplice algoritmo
Per tutti i primi p in [2,
¾ Running time O(2o(k)), dove k è la taglia dell’input
¾ Algoritmo basato su curve ellittiche: Ln[ 1/2, 1]
¾ Quadratic sieve: Ln[ 1/2, 1]
¾ General number field sieve: Ln[ 1/3, 1.923]
256
il più veloce
42
Barbara Masucci - DIA – Università di Salerno
43
Fattorizzazione: progressi
Fattorizzazione: sfide
1 mips per anno
13
≈ 3 ·10 istruzioni
¾ Nel 1977 gli inventori di RSA
anno
1984
1988
1993
1994
1996
1999
2003
2005
¾ Pubblicarono una sfida
¾ Rompere RSA con una chiave di 428 bit, premio 100 $
¾ Stimarono il tempo richiesto: 40 quadrilioni di anni
¾ Nel 1994: task force di Internet ha
reclamato il premio dopo 9 mesi di lavoro
¾ RSA Laboratories
¾ Altre sfide con chiavi di varia lunghezza
¾ Ultima sfida vinta: chiave con 512 bit
Barbara Masucci - DIA – Università di Salerno
numero digit
71
106
120
129
130
155
174
193
numero bit
236
350
397
425
430
512
576
640
mips per anno
0.01
140
825
5000
500
8000
RSARSA-129
1600 computer per 8 mesi
44
Prossima sfida RSA
algoritmo
QS
QS
QS
QS
GNFS
GNFS
RSARSA-193
5 mesi
Barbara Masucci - DIA – Università di Salerno
45
Che modulo scegliere?
¾ $ 30.000 a chi fattorizza RSA-704 (212 digit)
74037563479561712828046796097429573142593188889231
28908493623263897276503402826627689199641962511784
39958943305021275853701189680982867331732731089309
00552505116877063299072396380786710086096962537934
650563796359
¾ Ad oggi, i numeri più difficili da fattorizzare
sono del tipo n = p ·q con p,q primi della
stessa lunghezza
¾ … e di almeno (per essere tranquilli!)
¾ 768 bit per uso personale
¾ 1024 bit per le aziende
¾ 2048 per chiavi “importanti”
-ad esempio Autorità di Certificazione
http://www.rsasecurity.com/rsalabs/node.asp?id=2093
Barbara Masucci - DIA – Università di Salerno
46
Barbara Masucci - DIA – Università di Salerno
47
Sicurezza cifratura RSA
Sicurezza cifratura RSA
Se
Conoscendo la chiave pubblica (n,e) e il
computare M
messaggio cifrato C ← Me mod n
1. Fattorizza n
2. Computa ϕ(n)=(p-1)(q-1)
3. Computa d ← e-1 mod (p-1)(q-1)
4. Ricava M decifrando C
vuole calcolare il messaggio M
Barbara Masucci - DIA – Università di Salerno
48
Sicurezza cifratura RSA
Se
Barbara Masucci - DIA – Università di Salerno
49
Altri attacchi ad RSA
¾Attacchi non basati sul problema della
fattorizzazione
potesse computare M …
Importante problema aperto:
non si sa se questo sia computazionalmente
equivalente a fattorizzare!
Barbara Masucci - DIA – Università di Salerno
potesse fattorizzare n saprebbe
50
¾Chosen ciphertext attack
¾Common modulus attack
¾Low exponent attack
¾Attacchi ad implementazioni
Barbara Masucci - DIA – Università di Salerno
51
Chosen ciphertext attack
C1 = M1e mod n
C2 = M2e mod n
Decifrazione
Decifrazione
(d,n)
(d,n)
¾ Stesso modulo n per diverse chiavi pubbliche
(M1·M2)e = M1e · M2e = C1·C2 mod n
¾ Chiave Alice: (n,e1), chiave Bob: (n,e2)
¾ gcd(e1,e2)=1
Proprietà di omomorfismo
Obiettivo: decifrare C (= Me mod n)
¾ Stesso messaggio M inviato ai vari utenti
¾ Cifratura per Alice: C1=Me1 mod n,
¾ Cifratura per Bob: C2=Me2 mod n
Scelgo x a caso
C' ← C · xe mod n
¾ E’ semplice risalire ad M
M' ← (C')d mod n
M' = (C')d =(C ·xe )d = Cd ·x mod n
¾ Usa Euclide–esteso per calcolare x, y tali che 1=e1·x+e2·y
¾ C1x·C2y mod n = (Me1)x·(Me2)y = Me1x+e2y = M
M ← M' ·x-1 mod n
52
Barbara Masucci - DIA – Università di Salerno
¾ Stesso e per diverse chiavi pubbliche
¾Ricava i bit di d uno alla volta, analizzando il tempo
richiesto per l’esponenziazione modulare (decifratura)
¾ Stesso messaggio M inviato ai vari utenti
¾Power Attack [Kocher, 99]
¾ Cifratura per Alice: C1=M3 mod n1
¾ Cifratura per Bob: C2=M3 mod n2
¾ Cifratura per Eva: C3=M3 mod n3
¾Ricava d analizzando la potenza consumata da una
smartcard durante la decifratura
¾Contromisure
¾ E’ semplice risalire ad M
¾ Ritardo costante (tutte le esponenziazioni richiedono lo stesso
tempo)
¾ Ritardo casuale (introduce “rumore” per confondere l’avversario)
¾ Blinding (moltiplica il cifrato per un numero casuale prima di
decifrare)
¾ Usa Teorema cinese del resto per calcolare la soluzione di
x≡C1 mod n1
x=M3 mod n1·n2·n3
poi calcola
Barbara Masucci - DIA – Università di Salerno
53
¾Timing Attack [Kocher, 97]
¾ Chiave Alice: (n1,3), chiave Bob: (n2,3), chiave Eva: (n3,3)
¾ gcd(ni,nj)=1, i≠j
x≡C3 mod n3
Barbara Masucci - DIA – Università di Salerno
RSA: Attacchi ad
implementazioni
Low Exponent Attack
x≡C2 mod n2
Common Modulus Attack
M=x1/3
54
Barbara Masucci - DIA – Università di Salerno
55
Bibliografia
¾Cryptography and Network Security
by W. Stallings (2003)
¾cap. 9 (Public-Key Cryptography and RSA)
¾Cryptography: Theory and Practice (I ed.)
by D.R. Stinson (1995)
¾cap 5 (The RSA System and Factoring)
Barbara Masucci - DIA – Università di Salerno
56