•Stelvio Cimato
•14/05/2010
Computazioni in RSA
Crittografia a chiave
pubblica
Sicurezza di RSA
Come effettuare le computazioni?
Elevazione a potenza modulare
Stelvio Cimato
Generazione numeri primi
Dipartimento di Tecnologie dell’Informazione
Università di Milano
[email protected]
http://www.dti.unimi.it/~cimato
Generazione e,d
generazione di e
d ← e-1 mod (p-1)(q-1)
Stelvio Cimato
1
DTI – Università di Milano, Polo di Crema
Generazione di un
primo ‘grande’
Generazione di un
primo ‘grande’
1. Genera a caso un dispari p di grandezza appropriata
1. Genera a caso un dispari p di grandezza appropriata
2. Testa se p è primo
3. Se p è composto, go to 1.
2. Testa se p è primo
3. Se p è composto, go to 1.
Variante con sequenza di ricerca
1. Genera a caso un dispari p di grandezza appropriata
2. Testa se p è primo
3. Se p è composto, p ← p+2, go to 2.
Stelvio Cimato
Stelvio Cimato
DTI – Università di Milano, Polo di Crema
2
Distribuzione dei
numeri primi
Numeri Primi
π(x) = numero di primi in [2,x]
Thm: Esistono infiniti numeri primi
Prova:
Teorema dei numeri primi:
Assumiamo pmax è massimo numero primo.
Calcola N=p1*p2*…*pmax+1.
N deve essere composto perché è più grande di pmax.
Ma non è vero perché tutti i primi noti dividono N con
resto 1.
Quindi N è primo: contraddicendo l’ipotesi.
lim
x →∞
π (x)
=1
x/ln x
Esempio: π(1010) = 455.052.511
1010/ln 1010 ≈ 434.294.481,9 (4% in meno)
Per x ≥ 17
x
x
< π (x) < 1.25506
ln x
ln x
Stelvio Cimato
DTI – Università di Milano, Polo di Crema
3
DTI – Università di Milano, Polo di Crema
Stelvio Cimato
4
DTI – Università di Milano, Polo di Crema
5
•1
•Stelvio Cimato
•14/05/2010
Scelta di un primo
di 512 bit
Scelta di un primo
di 1024 bit
Scelto un intero in [2,2512] la probabilità che sia primo
è circa 1 su ln 2512 (ln 2512 ≈ 354,89)
Scelto un intero in [2,21024] la probabilità che sia
primo è circa 1 su ln 21024 (ln 21024 ≈ 709,78)
Numero medio di tentativi ≈ 354,89
Numero medio di tentativi ≈ 709,78
Se si scelgono solo dispari dimezza ≈ 177,44
Se si scelgono solo dispari dimezza ≈ 354,89
Se si scelgono dispari in [2511,2512] probabilità è
Se si scelgono dispari in [21023,21024] probabilità
≈
(
512
511
2
2
−
ln 2 512 ln 2 511
)
1
2
511
1 …
Stelvio Cimato
…
2
≈
≈
1
177,79
(
21024
21023
−
1024
ln 2
ln 21023
)
… 1
1
21023 2
1 …
Stelvio Cimato
510 bit scelti a caso
6
DTI – Università di Milano, Polo di Crema
≈
1
355,23
…
… 1
1022 bit scelti a caso
DTI – Università di Milano, Polo di Crema
7
Test di primalità
deterministici
Test di Primalità
Fino al 2002, il miglior algoritmo deterministico era una
Due tipi di test:
variante di Cohen e H. Lenstra del test di Adleman,
Probabilistici
Deterministici
Pomerance e Rumely [1983]
Complessità (ln p)O(lg lg lg p)
Nel 2002 Agrawal et al. scoprirono un algoritmo
deterministico polinomiale in grado di testare se un
numero è primo (AKS test)
Complessità O(ln p)6+ε
Stelvio Cimato
Stelvio Cimato
8
DTI – Università di Milano, Polo di Crema
Probabilmente!
primo
Test Primalità
9
Diminuzione della
probabilità di errore
Test di primalità probabilistici
p
DTI – Università di Milano, Polo di Crema
Probabilità di errore (n è composto ma viene
dichiarato primo) di tale test ≤ 1/2
composto
Certamente!
Se il test viene ripetuto indipendentemente t volte
allora la probabilità di errore ≤ (1/2)t
Stelvio Cimato
DTI – Università di Milano, Polo di Crema
Stelvio Cimato
10
DTI – Università di Milano, Polo di Crema
11
•2
•Stelvio Cimato
•14/05/2010
Test di primalità
probabilistici
Test di primalità probabilistici
Probabilmente!
Test di Solovay-Strassen
p
Test Primalità
Pubblicato nel 1977
Probabilità di errore ≤
primo
(1/2)t
Certamente!
Test di Miller-Rabin
Insieme di witness W(p)
Il più usato in pratica
dato a∈[0, p-1] è facile verificare se a∈W(p)
se p è primo allora W(p) è vuoto
Scelgo a
se p è composto allora |W(p)| ≥ p/2
Il più veloce
Probabilità di errore ≤ (1/4)t
Stelvio Cimato
Stelvio Cimato
12
DTI – Università di Milano, Polo di Crema
Test di Miller-Rabin
Insieme di witness di Miller-Rabin
Se p è primo, per ogni a ∈ Zp*, ap-1 = 1 mod p
p-1 = 2k q con q dispari
W MR(p) = {a : aq ≠ 1 mod p and
j
a2 q ≠ -1 mod p per ogni j∈[0,k-1]}
Se p è un primo dispari
Prima proprietà:
Se p è primo e a<p allora
a2 mod p =1 se e solo se (a mod p= 1) o (a mod p =-1=p-1)
ricorda che a2 mod p = (a modp)(a mod p)
Seconda proprietà
p dispari, p-1 pari
W MR(p) è vuoto
k
Scegli 1 < a < p-1 e calcola aq, a2q, …,a2 q
k
Se p è primo, a2 q = 1 mod p (teorema di Fermat)
Vale
1. aq = 1 mod p
j
13
DTI – Università di Milano, Polo di Crema
Test di Miller-Rabin
Basato sul Teorema di Fermat:
p-1=2kq, con q dispari e k>0
composto
k-1
Se p è un numero composto dispari
| W MR(p) | ≥ (3/4) ·φ(p)
k
2. Se esamino la sequenza a2 q ,ossia aq ,a2q , a4q , ... , a2 q , a2 q,
L’ultimo numero vale 1 e ogni numero della sequenza è il quadrato di quello che lo
precede
La lista contiene un elemento uguale a p-1
Stelvio Cimato
DTI – Università di Milano, Polo di Crema
Stelvio Cimato
14
Test di Miller-Rabin p=29
15
Test di Miller-Rabin p=221
Witness di Miller-Rabin
29-1 = 22 · 7
W MR(29) = {a : a7 ≠ 1 mod 29 and
j
a2 ·7 ≠ -1 mod 29 per ogni j∈[0,1]}
a=10
107 mod 29=17 (continua)
Witness di Miller-Rabin
221-1 = 22 · 55
W MR(221) = {a : a55 ≠ 1 mod 221 and
j
a2 ·55 ≠ -1 mod 221 per ogni j∈[0,1]}
a=5
555 mod 221=112 (continua)
(107)2 mod 29=28=-1 mod 29 (stop: “primo”)
(555)2 mod 221=168 (valori terminati, stop: “composto”)
a=2
a=21
27 mod 29=12 (continua)
2155 mod 221=220= -1 mod 221 (stop: “primo”)
(27)2 mod 29=28= -1 mod 29 (stop: “primo”)
Per ogni a ∈ {1,…,220}/ W MR(221), output: “primo”
Prova per tutti gli a ∈[1,28]: sempre output “primo”
a=1, 21, 47, 174, 200, 220
Stelvio Cimato
DTI – Università di Milano, Polo di Crema
DTI – Università di Milano, Polo di Crema
Stelvio Cimato
16
DTI – Università di Milano, Polo di Crema
17
•3
•Stelvio Cimato
•14/05/2010
Generazione numeri primi
Computazioni in RSA
Come effettuare le computazioni?
p e q devono essere molto grandi
Per scegliere un numero primo:
1. Si sceglie un intero dispari n
2. Si seleziona a caso a
3. Si esegue un test di primalità (Miller Rabin)
4. Se n passa il test viene accettato
L’operazione viene effettuata solo nella
generazione della coppia di chiavi
Elevazione a potenza modulare
Generazione numeri primi
generazione di e
Generazione e,d
Stelvio Cimato
d ← e-1 mod (p-1)(q-1)
Stelvio Cimato
18
DTI – Università di Milano, Polo di Crema
Calcolo di e e d
19
DTI – Università di Milano, Polo di Crema
Algoritmo di Euclide Esteso
Una volta trovati i primi p e q, bisogna
Euclide-esteso (a,n)
if n = 0 then return (a, 1, 0)
(d´, x´, y´) ← Euclide-esteso (n, a mod n)
(d, x, y) ← (d´, y´, x´- a/n y´)
return (d, x, y)
Selezionare e calcolando d
Tale che gcd(ø(n),e)=1
Calcolare d = e-1 mod ø(n)
L’algoritmo esteso di Euclide consente di:
Calcolare il gcd di due interi
Se gcd=1 determinare l’inverso di uno degli
interi modulo l’altro
Oltre a computare d=gcd(a,n) computa anche due interi x, y tali
che d = gcd(a,n) = a·x+n·y
Stesso running time asintotico di Euclide (a,n)
Stelvio Cimato
Stelvio Cimato
20
DTI – Università di Milano, Polo di Crema
Algoritmo di Euclide Esteso
Soluzione di ax≡b (mod n)
Dati
Euclide-esteso (a,n)
if n = 0 then return (a, 1, 0)
(d´, x´, y´) ← Euclide-esteso (n, a mod n)
(d, x, y) ← (d´, y´, x´- a/n y´)
return (d, x, y)
a
n
d
x
99
78
21
15
6
3
78
21
15
6
3
0
3
3
3
3
3
3
-11
3
-2
1
0
1
y
14
-11
3
-2
1
0
Stelvio Cimato
DTI – Università di Milano, Polo di Crema
22
21
DTI – Università di Milano, Polo di Crema
a, b, n calcolare x
0
Esempi:
1
3x≡7 (mod 8) soluzione 5
2
3
2x≡4 (mod 8) soluzione 2,6
4
4x≡2 (mod 8) nessuna soluzione
5
6
Stelvio Cimato
7
DTI – Università di Milano, Polo di Crema
0
0
0
0
0
0
0
0
0
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
23
•4
•Stelvio Cimato
•14/05/2010
Soluzione di ax≡b (mod n)
La congruenza ax≡b (mod n)
Soluzione di ax≡1 (mod n)
g = gcd(a,n)
Ha soluzioni se e solo se gcd(a,n) =1
Ha soluzioni se e solo se g|b
Caso specifico di ax≡b (mod n) con n primo
Se g|b ci sono esattamente g distinte soluzioni mod n:
b n
x' + i
g g
dove
Se gcd(a,n) =1 l’unica soluzione mod n è:
x´
per i = 0,1,…, g-1
dove
Tale soluzione viene denotata con a-1 mod n
(inversa moltiplicativa di a, mod n)
g = a·x′+n·y (da Euclide-esteso (a,n) )
Stelvio Cimato
Stelvio Cimato
24
DTI – Università di Milano, Polo di Crema
Soluzione di ax≡1 (mod 8)
3 = 3-1 mod 8
5=
5-1
mod 8
Ha soluzioni se e solo se gcd(a,7) =1
7 = 7-1 mod 8
Stelvio Cimato
0
0 0
1 0
2 0
1
0
1
2
2
0
2
4
3
0
3
6
4
0
4
0
5
0
5
2
6
0
6
4
7
0
7
6
1 = 1-1 mod 7
3
4
5
6
7
3
4
5
6
7
6
0
2
4
6
1
4
7
2
5
4
0
4
0
4
7
4
1
6
3
2
0
6
4
2
5
4
3
2
1
2 = 4-1 mod 7
0
0
0
0
0
4 = 2-1 mod 7
5 = 3-1 mod 7
3 = 5-1 mod 7
6 = 6-1 mod 7
Stelvio Cimato
26
DTI – Università di Milano, Polo di Crema
Esempio: calcolo di 5-1 mod 7
Euclide-esteso (a,n)
if n = 0 then return (a, 1, 0)
(d´, x´, y´) ← Euclide-esteso (n, a mod n)
(d, x, y) ← (d´, y´, x´- a/n y´)
return (d, x, y)
a n
d = x·a + y·n
1 = 3·5 -2·7
3 = 5-1 mod 7
0
1
2
3
4
5
6
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
6
0
6
5
4
3
2
1
27
DTI – Università di Milano, Polo di Crema
Esempio: calcolo di 5-1 mod 11
7
5
d
1
x
-2
y
3
5
2
1
1
-2
2
1
1
0
1
1
0
1
1
0
Stelvio Cimato
DTI – Università di Milano, Polo di Crema
25
DTI – Università di Milano, Polo di Crema
Soluzione di ax≡1 (mod 7)
Ha soluzioni se e solo se gcd(a,8) =1
1 = 1-1 mod 8
1 = a·x′+n·y (da Euclide-esteso (a,n) )
Euclide-esteso (a,n)
if n = 0 then return (a, 1, 0)
(d´, x´, y´) ← Euclide-esteso (n, a mod n)
(d, x, y) ← (d´, y´, x´- a/n y´)
return (d, x, y)
a n
d = x·a + y·n
1 = 1·11 + (-2)·5
-2 = 5-1 mod 11
Stelvio Cimato
28
-2 = 9 mod 11
DTI – Università di Milano, Polo di Crema
11
5
d
1
x
1
y
-2
5
1
1
0
1
1
0
1
1
0
9 = 5-1 mod 11
29
•5
•Stelvio Cimato
•14/05/2010
Teorema cinese del resto
Soluzione di ax≡b (mod n)
Gli interi in un intervallo posso essere rappresentati dai
resti modulo una coppia di numeri primi relativi.
Se n è composto es. n=pq, allora la
soluzione di ax≡b (mod n) può essere
vista come soluzione del sistema di
congruenze:
Soluzione di ax≡b (mod p)
Soluzione di ax≡b (mod q)
Per Z10 = 0,1,2,…,9, se considero una coppia di primi
relativi, es 2 e 5, e la coppia di resti 0 e 3,
allora esiste un unico intero rappresentato da quei
resti, cioè esiste un unico x tale che
x≡0 mod 2
In questo caso x=8
x≡3 mod 5
Stelvio Cimato
Stelvio Cimato
30
DTI – Università di Milano, Polo di Crema
DTI – Università di Milano, Polo di Crema
31
Teorema cinese del resto
Teorema cinese del resto
Esempio
Dati
x≡2 mod 5
m1, m2,…,mt interi positivi tali che gcd(mi,mj)=1, i≠j
x≡3 mod 13
M= m1·m2 …·mt
a1, a2,…,at interi
a1=2, m1=5, M1=13, y1=13-1 mod 5=2
Esiste una sola soluzione modulo M al sistema di congruenze
x≡a1 mod m1
x≡a2 mod m2
…
a2=3, m2=13, M2=5, y2=5-1 mod 13= 8
M=65
t
X = ∑ ai ⋅ Mi ⋅ yi mod M
Soluzione del sistema:
i =1
x≡at mod mt
Mi = M/mi
2
yi =
Mi-1
X = ∑ ai ⋅ Mi ⋅ yi mod 65 = 2 ⋅ 26 + 3 ⋅ 40 mod65 = 42 mod 65
mod mi
i=1
Stelvio Cimato
Stelvio Cimato
DTI – Università di Milano, Polo di Crema
32
33
Generazione chiavi
Algoritmo CRT
Per trovare la soluzione di x mod N dal
sistema xi mod pi con N=p1p2…pr
Per tutti gli i=1,…,r calcola:
1. Input
L (lunghezza modulo)
2. Genera 2 primi di lunghezza L/2
3. n ← p ·q
4. Scegli a caso e
5. If gcd ( e, (p-1)(q-1) ) = 1
then d ← e-1 mod (p-1)(q-1)
else goto 4.
Le inverse yi di N/pi mod pi
X=Σ i=1,…rN/pi *xiyi mod N
Stelvio Cimato
DTI – Università di Milano, Polo di Crema
DTI – Università di Milano, Polo di Crema
Stelvio Cimato
34
DTI – Università di Milano, Polo di Crema
35
•6
•Stelvio Cimato
•14/05/2010
Sicurezza generazione
chiavi di RSA
Sicurezza di RSA
Sicurezza della generazione delle chiavi
Conoscendo la chiave pubblica (n,e)
vuole calcolare la chiave privata
C
Sicurezza della cifratura
d=e-1 mod (p-1)(q-1)
Stelvio Cimato
Stelvio Cimato
36
DTI – Università di Milano, Polo di Crema
Attacco 1: fattorizzare n
Se
Attacco 2: computare ϕ(n)
saprebbe fattorizzare n
computare d
n = pq
1. Fattorizza n
ϕ(n) = (p-1)(q-1)
2. Computa ϕ(n)=(p-1)(q-1)
3. Computa d ← e-1 mod (p-1)(q-1)
Stelvio Cimato
38
DTI – Università di Milano, Polo di Crema
potesse computare ϕ(n) = (p-1)(q-1),
Attacco 3: computare d
Se
Saprebbe fattorizzare n
39
DTI – Università di Milano, Polo di Crema
Attacco 2: computare ϕ(n)
ϕ(n) = (p-1)(q-1)
sostituendo p = n/q
p2- (n-ϕ(n)+1)p + n = 0
Due soluzioni: p,q
Stelvio Cimato
n = pq
potesse computare ϕ(n)=(p-1)(q-1),
Se
potesse fattorizzare n, saprebbe
Se
37
DTI – Università di Milano, Polo di Crema
potesse computare d saprebbe fattorizzare n
Un algoritmo che computa d (con input n,e) può essere usato come oracolo in
un algoritmo Las Vegas* che fattorizza n con probabilità ≥1/2
sostituendo p = n/q
p2- (n-ϕ(n)+1)p + n = 0
84.773.093 = pq
p2- 18.426 p + 84.773.093
84.754.668 = (p-1)(q-1)
radici: 9539 e 8887
(n,e)
=0
Calcola
d
(p,q)
nessuna
risposta
prob 1/2
prob 1/2
*un algoritmo Las Vegas è un algoritmo probabilistico chepuò non dare una risposta, ma se la dà
questa è corretta
Stelvio Cimato
DTI – Università di Milano, Polo di Crema
Fattorizza n
Stelvio Cimato
40
DTI – Università di Milano, Polo di Crema
41
•7
•Stelvio Cimato
•14/05/2010
Sicurezza generazione
chiavi di RSA
Fattorizzazione: progressi
1MIPS/anno: un milione di istr./s per un anno
Pentium 1 Ghz= 250 mips
Fattorizza n Computa d
Computa d
anno
1984
1988
1993
1994
1996
1999
2005
2003
2003
2005
numero digit numero bit mips per anno
71
236
0.01
106
350
140
120
397
825
129
425
5000
130
430
1000
155
512
8000
160
530
174
576
200
663
RSARSA-129
RSARSA-155
193
640
1600 computer
300 workstation +
per 8 mesi
CRAY per 5 mesi
Stelvio Cimato factoring by e-mail
Fattorizza n
Computare d è equivalente a fattorizzare n
Stelvio Cimato
42
DTI – Università di Milano, Polo di Crema
#op. in bit
7200
3.11+e06
3.72+e10
1.97+e12
2.35+e15
1.26+e18
2.36+e19
Dividi per 106
per avere tempo in s
Limite 1e+14
Ci sono 3e+13 ns/a
30 2.2GHz2.2GHzOpteron-CPU
Opteronyears /5 mesi
DTI – Università di Milano, Polo di Crema
43
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
Stelvio Cimato
DTI – Università di Milano, Polo di Crema
algoritmo
QS
QS
QS
QS
GNFS
GNFS
Che modulo scegliere?
Fattorizzazione
Digit decimali
20
40
80
100
140
180
200
1 mips per anno
≈ 3 ·1013 istruzioni
Stelvio Cimato
44
DTI – Università di Milano, Polo di Crema
Sicurezza cifratura RSA
45
Sicurezza cifratura RSA
Se
Conoscendo la chiave pubblica (n,e) e il
potesse fattorizzare n saprebbe
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
Stelvio Cimato
DTI – Università di Milano, Polo di Crema
Stelvio Cimato
46
DTI – Università di Milano, Polo di Crema
47
•8
•Stelvio Cimato
•14/05/2010
Sicurezza cifratura RSA
Se
Attacchi ad RSA
potesse computare M …
Attacchi non basati sul problema della
fattorizzazione
Importante problema aperto:
non si sa se questo sia computazionalmente
Chosen ciphertext attack
Common modulus attack
Low exponent attack
equivalente a fattorizzare!
Stelvio Cimato
Stelvio Cimato
48
DTI – Università di Milano, Polo di Crema
Chosen ciphertext attack
C1 = M1e mod n
C2 = M2e mod n
(M1·M2)e = M1e · M2e = C1·C2 mod n
Chiave Alice: (n,e1), chiave Bob: (n,e2)
gcd(e1,e2)=1
Stesso messaggio M inviato ai vari utenti
Obiettivo: decifrare C (= Me mod n)
Cifratura per Alice: C1=Me1 mod n,
Cifratura per Bob: C2=Me2 mod n
Scelgo x a caso
C' ← C · x mod n
e
M' ← (C')d mod n
M' = (C')d =(C ·xe )d = Cd ·x mod n
Common Modulus Attack
Stesso modulo n per diverse chiavi pubbliche
Proprietà di omomorfismo
Decifrazione
(d,n)
E’ semplice risalire ad M
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
Stelvio Cimato
Stelvio Cimato
50
DTI – Università di Milano, Polo di Crema
Stesso e per diverse chiavi pubbliche
Chiave Alice: (n1,3), chiave Bob: (n2,3), chiave Eva: (n3,3)
gcd(ni,nj)=1, i≠j
Dato C
Cifratura per Alice: C1=M3 mod n1
Cifratura per Bob: C2=M3 mod n2
Cifratura per Eva: C3=M3 mod n3
e … “difficili” ?
E’ semplice risalire ad M
(hard bit : ultimi c ·loglog n bit)
Usa Teorema cinese del resto per calcolare la soluzione di
x≡C1 mod n1
x≡C2 mod n2
3
n3
mod n1·n2·n3
poi calcola
DTI – Università di Milano, Polo di Crema
C = Me mod n
potrebbero esserci informazioni parziali
sul messaggio M “facili” da ottenere
(senza dover decifrare C ! )
Stesso messaggio M inviato ai vari utenti
x=M3
51
DTI – Università di Milano, Polo di Crema
Informazioni parziali
per RSA
Low Exponent Attack
Stelviox≡C
Cimato
mod
49
DTI – Università di Milano, Polo di Crema
M=x1/3
Stelvio Cimato
52
DTI – Università di Milano, Polo di Crema
53
•9
•Stelvio Cimato
•14/05/2010
Un bit “difficile”
per RSA
Un bit “difficile”
per RSA
0 se M < n/2
halfn,e(C) =
0 se M < n/2
halfn,e(C) =
1 se M > n/2
1 se M > n/2
Calcolare halfn,e(·) è computazionalmente
equivalente ad invertire RSA
C
Calcola
halfn,e(C)
halfn,e( ·)
Stelvio Cimato
C
Decifran,e
M
Calcola
halfn,e(·)
Stelvio Cimato
54
DTI – Università di Milano, Polo di Crema
DTI – Università di Milano, Polo di Crema
55
RSA: Attacchi ad
implementazioni
Predicato parità
C = Me mod n
Timing Attack [Kocher, 97]
Ricava i bit di d uno alla volta, analizzando il
tempo richiesto per l’esponenziazione modulare
(decifratura)
paritàn,e(C) = bit meno significativo di M
I predicati paritàn,e(·) e halfn,e( ·)
sono computazionalmente equivalenti
Power Attack [Kocher, 99]
Ricava d analizzando la potenza consumata da
una smartcard durante la decifratura
paritàn,e(C) = halfn,e(y)
y = C ·(2-1 )e mod n
= (M ·2-1)e mod n
Stelvio Cimato
DTI – Università di Milano, Polo di Crema
Stelvio Cimato
56
DTI – Università di Milano, Polo di Crema
57
•10