Folien

Vorlesung Sicherheit
J¨
orn M¨
uller-Quade
ITI, KIT
basierend auf den Folien von Dennis Hofheinz, Sommersemester 2014
04.05.2015
1 / 20
Kummerkasten
Vorlesungsfolien bitte einen Tag vorher hochladen“:
”
Sollte jetzt so sein
(Folien k¨onnen aber potentiell nach der VL aktualisiert
werden, falls n¨otig)
2 / 20
¨
Uberblick
1 Asymmetrische Verschl¨
usselung
Erinnerung
Sicheres RSA
Andere Verfahren
Demonstration
Zusammenfassung
3 / 20
¨
Uberblick
1 Asymmetrische Verschl¨
usselung
Erinnerung
Sicheres RSA
Andere Verfahren
Demonstration
Zusammenfassung
4 / 20
IND-CPA f¨ur asymm. Verschl¨usselung
Herausforderer C erzeugt Schl¨
usselpaar (pk, sk).
Kein Enc-Orakel, stattdessen erh¨alt der Angreifer pk.
C
A
pk
M0 , M1
b ← {0, 1}
C ∗ = Enc(pk,
Mb )
b0
b = b0 ?
5 / 20
Erinnerung
Asymmetrische (Public-Key-)Verschl¨
usselung:
Alicesk
C :=Enc(pk,M)
←−−−−−−−−−−−−−−−−
Bobpk
RSA:
Enc(pk, M) = M e mod N
Dec(sk, C ) = C d mod N
Homomorphie von RSA
Enc(pk, M) · Enc(pk, M 0 ) = Enc(pk, M · M 0 )
Homomorphie kann problematisch sein → Auktionen
6 / 20
¨
Uberblick
1 Asymmetrische Verschl¨
usselung
Erinnerung
Sicheres RSA
Andere Verfahren
Demonstration
Zusammenfassung
7 / 20
L¨osungsvorschl¨age?
Diskussion: Wie k¨
onnte man RSA reparieren“?
”
8 / 20
RSA-Padding
Erster Ansatz (PKCS#1 1.5, 1993): (Randomized) Padding
Enc(pk, M) = (pad(M, R))e mod N (mit Zufall R)
Dec erh¨alt und u
uft pad(M, R), und extrahiert M
¨berpr¨
Beispiel: pad(M, R) = M||0` ||R (mit M, R N)
PKCS#1 1.5 problematisch
Kein Sicherheitsbeweis, 1998 sogar Problem gefunden
Homomorphe Eigenschaft der RSA-Funktion erlaubt subtile
¨
Anderungen
an Nachricht
PKCS#1 2.0 nutzt RSA-OAEP“: besseres Padding
”
9 / 20
RSA-OAEP
pad-Funktion von RSA-OAEP (G , H Hashfunktionen):
Quelle: Wikipedia
10 / 20
Sicherheit von RSA-OAEP
Heuristisch so sicher wie RSA-Funktion invertieren“
”
Sicher heißt hier: semantisch sicher selbst gegen aktive Angriffe
(im idealisierten Random Oracle Modell)
Bester bekannter Angriff: N faktorisieren
P, Q
ϕ(N) = (P − 1)(Q − 1)
d = e −1 mod ϕ(N)
Bester bekannter Faktorisierungsalgorithmus: Zahlk¨orpersieb
Nach heutigem Stand 2048 als Bitl¨ange von N sicher
Offene Forschungsfrage: N faktorisieren notwendig, um
RSA(-OAEP) zu brechen?
11 / 20
Relevanz von RSA(-OAEP)
Nachteil von RSA(-OAEP): rechenaufw¨andig
Naiver Algorithmus f¨
ur Exponentiation modulo `-Bit-Zahl
ben¨
otigt Θ(`3 ) Bitoperationen, schlecht parallelisierbar
Es existieren (asymptotisch) bessere Algorithmen
Aber: F¨
ur realistische ` ist naiver Algorithmus am schnellsten
Gr¨
unde, warum RSA(-OAEP) trotzdem benutzt wird:
Einfach zu implementieren
Einfache Arithmetik
Ver- und Entschl¨
usselung sehr ¨
ahnlich
Mit Optimierungen (e = 3 bei Verschl¨
usselung, CRS nutzen
bei Entschl¨
usselung) teilweise konkurrenzf¨ahig
RSA als Trapdoor One-Way Permutation“ interessant
”
12 / 20
¨
Uberblick
1 Asymmetrische Verschl¨
usselung
Erinnerung
Sicheres RSA
Andere Verfahren
Demonstration
Zusammenfassung
13 / 20
ElGamal (1985)
Szenario: zyklische Gruppe
G
pk = (
, g , g x ),
Enc(pk, M) =
G
G = hg i
sk = ( , g , x) (mit x zuf¨allig)
(g y , g xy
· M) (mit y zuf¨allig)
Dec(sk, (Y , Z )) = Z /Y x
(= (g xy · M)/(g y )x = M)
Beobachtung: Verschl¨
usselung probabilistisch
Aber: ElGamal wie RSA homomorph
0
0
Enc(pk, M) · Enc(pk, M 0 ) = (g y , g xy · M) · (g y , g xy · M 0 )
0
0
= (g y +y , g x(y +y ) · M · M 0 ) = Enc(pk, M · M 0 )
14 / 20
Mehr u¨ber ElGamal
ElGamal unter naheliegender Annahme semantisch sicher
(allerdings nicht gegen aktive Angriffe)
Nicht-homomorphe Varianten von ElGamal existieren
Kandidaten f¨
ur geeignete Gruppen :
G
(Echte) Untergruppen von Z (mit P prim)
Allgemeiner: Untergruppen von F∗q (mit q Primpotenz)
Effizienter: (Untergruppen von) elliptischer Kurve E(Fq )
∗
P
Realistische Gruppengr¨
oße:
|G| ≈ 22048 (f¨
ur G ⊂ Z∗P , F∗q )
|G| ≈ 2200 (f¨
ur G ⊆ E(Fq ))
15 / 20
¨
Uberblick
1 Asymmetrische Verschl¨
usselung
Erinnerung
Sicheres RSA
Andere Verfahren
Demonstration
Zusammenfassung
16 / 20
Demonstration
Demonstration: Geschwindigkeitsvergleich RSA/elliptische
Kurven
17 / 20
¨
Uberblick
1 Asymmetrische Verschl¨
usselung
Erinnerung
Sicheres RSA
Andere Verfahren
Demonstration
Zusammenfassung
18 / 20
Zusammenfassung asymmetrische Verschl¨usselung
Public-Key-Verschl¨
usselung l¨
ost Schl¨
usselverteilungsproblem
RSA wichtig, aber ohne Padding problematisch
RSA-OAEP
ElGamal in kleineren Gruppen m¨
oglich (Effizienz)
Beide Verfahren (ungepadded) homomorph (Vorteil/Nachteil)
19 / 20
Aktuelle Forschung
Mehr/andere Funktionalit¨at, zum Beispiel:
Identit¨atsbasierte Verschl¨
usselung (l¨
ost Zertifizierungsproblem)
Vollhomomorphe Verschl¨
usselung (Berechnungen delegieren1 )
Funktionale Verschl¨
usselung (viele sk f , Dec(sk f , C ) = f (M))
Broadcast-Verschl¨
usselung (Beispielanwendung: Pay-TV)
Andere Probleme, alternative mathematische Strukturen
Public-Key-Verschl¨
usselung so sicher wie Faktorisierung
Gitterbasierte Verschl¨
usselung
1
momentan noch um Gr¨
oßenordnungen zu ineffizient
20 / 20

Download Report