Public Key Kryptosysteme - Prof. Dr. Christoph Karg

Kryptografische Algorithmen
Lerneinheit 6: Public Key Kryptosysteme
Prof. Dr. Christoph Karg
Studiengang Informatik
Hochschule Aalen
Wintersemester 2015/2016
19.1.2016
Public Key Kryptosysteme
Einleitung
Einleitung
Thema dieser Lerneinheit ist die Funktionsweise von Public Key
Kryptosystemen.
Die Lerneinheit gliedert sich in folgende Abschnitte:
• Aufbau von Public Key Kryptosystemen
• Generierung von Primzahlen
• Rabin-Kryptosystem
• RSA-Kryptosystem
• Diffie Hellman Key Exchange
• El-Gamal-Kryptosystem
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
2 / 138
Public Key Kryptosysteme
Aufbau
Aufbau eines Public Key Kryptosystems
Alice
Oskar
Bob
x
enc
x
y
unsicherer Kanal
y
dec
ke
ke
kd
Schlüsselverzeichnis
Prof. Dr. C. Karg (HS Aalen)
Benutzer
Schlüssel
Bob
ke
Kryptografische Algorithmen
Public Key Kryptosysteme
3 / 138
Public Key Kryptosysteme
Sicherheitsaspekte
Sicherheitsaspekte
• Die Sicherheit gängiger Public Key Kryptosysteme basiert auf der
(hoffentlich) hohen Komplexität von algorithmischen Problemen
• Häufig verwendete Problemstellungen:
. Faktorisierung von ganzen Zahlen
. Berechnung des diskreten Logarithmus
. Berechnung von quadratischen Resten
• Die Parameter von Public Key Kryptosystemen werden mittels
Pseudo-Zufallszahlen-Generatoren erzeugt
• Voraussetzungen:
. Für kryptografische Zwecke geeignete Generatoren für
Pseudo-Zufallszahlen
. Primzahltests
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
4 / 138
Public Key Kryptosysteme
Sicherheitsaspekte
Faktorisierung von ganzen Zahlen
Faktorisierungsproblem
Gegeben: Zusammengesetzte Zahl n ∈ N
Gefragt: Finde einen Faktor f von n, d.h., eine Zahl f mit folgenden
Eigenschaften:
• 1 < f < n, und
• f |n
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
5 / 138
Public Key Kryptosysteme
Sicherheitsaspekte
Berechnung des diskreten Logarithmus
Diskreter-Logarithmus-Problem
Gegeben:
• Primzahl p
• Erzeugendes Element α von Z∗p
• Element β ∈ Z∗p
Gefragt: Berechne die eindeutige ganze Zahl a, 1 ≤ a ≤ p − 1, so
dass
αa ≡ β (mod p).
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
6 / 138
Public Key Kryptosysteme
Sicherheitsaspekte
Beispiel zum Diskreten Logarithmus
Betrachte Z∗11 und α = 2.
1 2 3 4 5 6 7 8 9 10
i
α mod 11 2 4 8 5 10 9 7 3 6 1
i
Demnach ist log2 (10) = 5 und log2 (6) = 9.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
7 / 138
Public Key Kryptosysteme
Sicherheitsaspekte
Einwegfunktionen
Eine Abbildung f bezeichnet man als Einwegfunktion, falls sie
folgende Bedingungen erfüllt:
• f kann man einfach berechnen
• Selbst wenn der Algorithmus zur Berechnung von f bekannt ist,
ist es für fast alle y schwer, ein x zu finden, so dass f (x) = y gilt
Ob Einwegfunktionen existieren, ist eine der offenen Fragen in der
Kryptografie
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
8 / 138
Public Key Kryptosysteme
Sicherheitsaspekte
Kandidaten für Einwegfunktionen
• Produkt zweier Primzahlen: f (p, q) = p · q, wobei p und q
Primzahlen.
• Diskrete Exponentialfunktion: f (x) = g x mod p, wobei p eine
Primzahl und g ein Generator von (Z∗p , ×p ) ist.
• Modulare Polynomfunktion:
f (x) = an · x n + . . . + a1 · x + a0 mod p,
wobei p eine Primzahl und ai ∈ Zp für 0 ≤ i ≤ n.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
9 / 138
Public Key Kryptosysteme
Sicherheitsaspekte
Falltürfunktionen
Eine Abbildung f bezeichnet man als Falltürfunktion, falls sie
folgende Bedingungen erfüllt:
• f ist einfach zu berechnen.
• Bei Kenntnis einer mit f verbundenen Information (der
sogenannten Falltürinformation), ist die Gleichung f (x) = y für
gegebenes y leicht lösbar
• Ohne Kenntnis der Falltürinformation ist die Gleichung f (x) = y
für alle y schwer lösbar
Bisher konnte nicht nachgewiesen werden, dass Falltürfunktionen
existieren.
Ein Kandidat für eine Falltürfunktion ist die bei RSA eingesetzte
modulare Potenzfunktion
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
10 / 138
Generierung von Primzahlen
Generierung von Primzahlen
• Primzahlen sind die Grundlage für viele Public Key Verfahren
• Die verwendeten Primzahlen müssen geheim gehalten werden
• Konsequenz: ein Benutzer muss in der Lage sein, Primzahlen auf
eine vertrauliche Art und Weise zu generieren
• Ansatz:
1. Zähle zufällig unter Gleichverteilung eine ungerade Zahl mit
einer vorgegebenen Größe
2. Überprüfe, ob die Zahl eine Primzahl ist
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
11 / 138
Generierung von Primzahlen
Der Primzahlsatz
Der Primzahlsatz
Satz 1 (Primzahlsatz) Sei π(n) gleich der Anzahl der Primzahlen,
die kleiner-gleich n sind, d.h.,
π(n) = k{p ∈ N | p ist ein Primzahl und p ≤ n}k.
Dann gilt für alle n ∈ N:
lim
n→∞
π(n)
n
ln n
→ 1.
Interpretation: Für große n ist π(n) ≈
Prof. Dr. C. Karg (HS Aalen)
n
ln n
Kryptografische Algorithmen
Public Key Kryptosysteme
12 / 138
Generierung von Primzahlen
Der Primzahlsatz
Anwendung des Primzahlsatzes
Anwendung: Im Mittel muss man
m=
ln(2k )
k ln(2)
=
2
2
ungerade Zahlen aus {1, 3, . . . , 2k − 1} zufällig unter Gleichverteilung
ziehen, um eine Primzahl zu erhalten.
Zahlenbeispiele:
k
m
128 44.36
256 88.72
512 177.45
1024 354.89
Prof. Dr. C. Karg (HS Aalen)
k
m
2048 709.78
4096 1419.57
8192 2839.13
16384 5678.26
Kryptografische Algorithmen
Public Key Kryptosysteme
13 / 138
Generierung von Primzahlen
Ein einfacher Primzahltest
Ein einfacher Primzahltest
Satz 2 (Fermat) Ist n eine Primzahl, dann gilt für alle a ∈ Z∗n :
an−1 ≡ 1 (mod n).
Ansatz: Finde ein a ∈ {2, . . . , n − 1}, so dass
an−1 6≡ 1 (mod n).
In diesem Fall ist n keine Primzahl.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
14 / 138
Generierung von Primzahlen
Ein einfacher Primzahltest
Probleme und Lösungen
Probleme
1. an−1 mod n muss effizient berechnet werden
2. Man kann nicht alle Elemente a ∈ {2, . . . , n − 1} testen
3. Es gibt Zahlen, die durch den Test nicht erkannt werden
Lösungen
1. Einsatz der modularen Exponentiation
2. Zufällige Auswahl von a
3. Einsatz einer verbesserten Testmethode
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
15 / 138
Generierung von Primzahlen
Ein einfacher Primzahltest
Modulare Exponentation
ModularExponentation(a, b, n)
Input: a, b, n ganze Zahlen, wobei n > 0
Output: ab mod n
1
d := 1
2
Sei hbk−1 , . . . , b0 i die Binärdarstellung von b
3
for i := k − 1 downto 0 do
4
d := (d · d) mod n
5
if (bi = 1) then
6
d := (d · a) mod n
7
return d
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
16 / 138
Generierung von Primzahlen
Carmichael-Zahlen
Carmichael-Zahlen
Eine Carmichael-Zahl ist eine zusammengesetzte Zahl n mit der
Eigenschaft, dass
an−1 ≡ 1 (mod n)
für alle a ∈ {1, 2, . . . , n − 1}.
Bemerkungen:
• Carmichael-Zahlen sind extrem selten. Es gibt nur 255 solche
Zahlen, die kleiner als 108 sind
• Die ersten drei Carmichael-Zahlen sind 561, 1105 und 1729
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
17 / 138
Generierung von Primzahlen
Verbesserung des Primzahltests
Verbesserung des Primzahltests
Satz 3 Ist n eine Primzahl, dann hat die Gleichung
x 2 ≡ 1 (mod n)
genau die zwei Lösungen x = 1 und x = −1 = n − 1.
Folgerung: Ist die Gleichung
x 2 ≡ 1 (mod n)
lösbar für ein x mit x 6= 1 und x 6= n − 1, dann ist n keine Primzahl.
Ansatz: Modifikation der modularen Exponentiation
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
18 / 138
Generierung von Primzahlen
Verbesserung des Primzahltests
Algorithmus Witness(a, n)
Witness(a, n)
Input: a, n ganze Zahlen, wobei n > 0 und 1 ≤ a ≤ n − 1
Output: true, falls n keine Primzahl, false, sonst.
1
Sei hbk , bk−1 , . . . , b0 i die Binärdarstellung von n − 1
2
d := 1
3
for i := k downto 0 do
4
x := d
5
d := (d · d) mod n;
6
if (d = 1) and (x 6= 1) and (x 6= n − 1) then
7
return true
8
if (bi = 1) then d := (d · a) mod n
9
if (d 6= 1) then
10
return true
11
return false
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
19 / 138
Generierung von Primzahlen
Verbesserung des Primzahltests
Eigenschaften von Witness(a, n)
• Die Funktion Witness(a, n) ist eine abgewandelte Form von
modularer Exponentiation
• Der Algorithmus berechnet an−1 mod n und sucht während der
Berechnung nach Lösungen für die Gleichung x 2 ≡ 1 (mod n),
die verschieden zu 1 und n − 1 sind
• Falls Witness(a, n) = true, dann wird a als Beleg
(engl. witness) für die Tatsache angesehen, dass n keine
Primzahl ist.
• Ist n > 2 eine zusammengesetzte Zahl, dann existieren hierfür
mindestens (n − 1)/2 Belege in {1, 2, . . . , n − 1}
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
20 / 138
Generierung von Primzahlen
Miller-Rabin-Test
Miller-Rabin-Test
MillerRabinTest(n, s)
Input: n, s ganze positive Zahlen
Output: true, falls n eine Primzahl ist, false, sonst.
1 for i := 1 to s do
2
a := Random(2, n − 1)
3
if Witness(a, n) = true then
4
return false
5 return true
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
21 / 138
Generierung von Primzahlen
Miller-Rabin-Test
Bemerkungen zum Miller-Rabin-Test
• Der Miller-Rabin-Test besitzt einen einseitigen Fehler:
. Falls MillerRabinTest(n, s) = false, dann ist n keine
Primzahl
. Falls MillerRabinTest(n, s) = true, dann ist n
Primzahl mit einer Wahrscheinlichkeit von 1 − 2−s
• Die Wahl von s beeinflusst die Fehlerwahrscheinlichkeit
• Die Laufzeit von MillerRabinTest(n, s) ist O(log2 (n)3 · s)
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
22 / 138
Rabin-Kryptosystem
Rabin-Kryptosystem
•
•
•
•
Erfunden von Michael O. Rabin im Jahr 1979
Verschlüsselung mittels quadratischer Funktion
Beweisbar sicheres Kryptosystem
Geringe Bedeutung für die Praxis
. Verschlüsselungsfunktion nicht injektiv
erhöhter
Aufwand bei der Entschlüsselung
. Anfällig gegen eine Chosen-Ciphertext-Attacke
• Grundlage für weitere Kryptosysteme
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
23 / 138
Rabin-Kryptosystem
Definition
Definition Rabin-Kryptosystem
Parameter:
• Primzahlen p und q, wobei p 6= q, p ≡ 3 (mod 4) und
q ≡ 3 (mod 4)
• n =p·q
Kryptosystem:
• P = C = Zn
• K = {(n, p, q)}
• Schlüssel k = (n, p, q)
. Öffentlicher Teil: n
. Privater Teil: (p, q)
• Verschlüsselung: enc ((n, p, q), x) = x 2 mod n
√
• Entschlüsselung: dec ((n, p, q), y ) = y mod n
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
24 / 138
Rabin-Kryptosystem
Quadratische Reste
Quadratischer Reste
Definition. Sei n eine ungerade ganze Zahl. Sei a eine Zahl, die
teilerfremd zu n ist, d.h., gcd(a, n) = 1.
a ist ein quadratischer Rest modulo n, falls eine Zahl x ∈ Zn existiert,
so dass
x 2 ≡ a (mod n)
Ist a kein quadratischer Rest, dann nennt man a einen quadratischen
Nicht-Rest.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
25 / 138
Rabin-Kryptosystem
Quadratische Reste
Beispiel zu Quadratischen Resten
Betrachte n = 11.
a 1 2 3 4 5 6 7 8 9 10
a2 1 4 9 5 3 3 5 9 4 1
Also ist die Menge der quadratischen Reste modulo 11 gleich
{1, 3, 4, 5, 9}
Die Menge der quadratischen Nicht-Reste ist
{2, 6, 7, 8, 10}
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
26 / 138
Rabin-Kryptosystem
Quadratische Reste
Zwei nützliche Sätze
Satz 1. Seien p und q Primzahlen mit der Eigenschaft, dass
• p 6= q
• p ≡ 3 (mod 4) und q ≡ 3 (mod 4)
Sei n = p · q. Sei a ein quadratischer Rest modulo n.
Dann besitzt die Gleichung
x2 ≡ a
(mod n)
vier Lösungen.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
27 / 138
Rabin-Kryptosystem
Quadratische Reste
Zwei nützliche Sätze (Forts.)
Satz 2. Sei p eine Primzahl mit der Eigenschaft, dass
p ≡ 3 (mod 4).
Sei a ein quadratischer Rest modulo p.
Dann sind
x1,2 = ±a(p+1)/4 mod p
die beiden Lösungen für die Gleichung
x2 ≡ a
Prof. Dr. C. Karg (HS Aalen)
(mod p).
Kryptografische Algorithmen
Public Key Kryptosysteme
28 / 138
Rabin-Kryptosystem
Entschlüsselung
Entschlüsselung
Gegeben: Quadratischer Rest a modulo p · q
Ansatz: Einsatz des Chinesischen Restsatzes
1. Berechne die Lösungen x1,2 der Gleichung x 2 ≡ a (mod p)
2. Berechne die Lösungen y1,2 der Gleichung y 2 ≡ a (mod q)
3. Berechne mittels des Chinesischen Restsatzes die vier Lösungen
hv1 , v2 , v3 , v4 i der Gleichung v 2 ≡ a (mod p · q)
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
29 / 138
Rabin-Kryptosystem
Entschlüsselung
Wiederholung: Chinesischer Restsatz
Satz. Seien p und q Primzahlen, wobei p 6= q.
Dann besitzt das Gleichungssystem
x ≡ bp
x ≡ bq
(mod p)
(mod q)
die eindeutige Lösung
(bp · mp · q + bq · mq · p) mod (p · q)
wobei
Prof. Dr. C. Karg (HS Aalen)
mp ≡ q −1
mq ≡ p −1
(mod p)
(mod q)
Kryptografische Algorithmen
Public Key Kryptosysteme
30 / 138
Rabin-Kryptosystem
Entschlüsselung
Beispiel zur Entschlüsselung
Bob wählt die Primzahlen p = 131 und q = 139 als geheimen
Schlüssel und veröffentlicht den Schlüssel n = p · q = 18209.
Alice will die Nachricht x = 4273 verschlüsselt an Bob senden. Hierzu
berechnet sie
y = x2
(mod n) = 42732
(mod 18209) = 13111
und sendet anschließend den Geheimtext 13111 an Bob.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
31 / 138
Rabin-Kryptosystem
Entschlüsselung
Beispiel zur Entschlüsselung (Forts.)
Um Alices Nachricht zu entschlüsseln, berechnet Bob mit dem
erweiterten Algorithmus von Euklid die Werte mp und mq , so dass
1 = mq · p + mp · q
Man überprüft ohne Mühe, dass
mp · q ≡ 1
mq · p ≡ 1
(mod p) und
(mod q)
Der Euklid’sche Algorithmus liefert mp = −49 und mq = 52 als
Ergebnis.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
32 / 138
Rabin-Kryptosystem
Entschlüsselung
Beispiel zur Entschlüsselung (Forts.)
Bob berechnet
x1 ≡
≡
x2 ≡
≡
13111(131+1)/4
81
131 − 81
50
(mod
(mod
(mod
(mod
131)
131)
131)
131)
y1 ≡
≡
y2 ≡
≡
13111(139+1)/4
36
139 − 36
103
(mod
(mod
(mod
(mod
139)
139)
139)
139)
und
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
33 / 138
Rabin-Kryptosystem
Entschlüsselung
Beispiel zur Entschlüsselung (Forts.)
Anschließend benutzt Bob den Chinesischen Restsatz zur Berechnung
der Wurzeln:
v1 ≡
≡
≡
v2 ≡
≡
≡
(x1 · q · mp + y1 · p · mq )
(81 · 139 · −49 + 36 · 131 · 52)
3094
(x2 · q · mp + y2 · p · mq )
(50 · 139 · −49 + 36 · 131 · 52)
13936
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
(mod
(mod
(mod
(mod
(mod
(mod
n)
18209)
18209)
n)
18209)
18209)
Public Key Kryptosysteme
34 / 138
Rabin-Kryptosystem
Entschlüsselung
Beispiel zur Entschlüsselung (Forts.)
v3 ≡
≡
≡
v4 ≡
≡
≡
(x1 · q · mp + y2 · p · mq )
(81 · 139 · −49 + 103 · 131 · 52)
4273
(x2 · q · mp + y1 · p · mq )
(50 · 139 · −49 + 103 · 131 · 52)
15115
(mod
(mod
(mod
(mod
(mod
(mod
n)
18209)
18209)
n)
18209)
18209)
Bob erkennt (auf eine dem Autor dieses Dokuments nicht bekannte
Art und Weise), dass v3 = 4273 der von Alice versendete Klartext ist.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
35 / 138
Rabin-Kryptosystem
Entschlüsselung
Algorithmus zur Entschlüsselung
RabinDecrypt(a, p, q)
Input: Geheimtext a, geheimer Schlüssel (p, q)
Output: Wurzeln hv1 , v2 , v3 , v4 i von a modulo p · q
1 n := p · q
2 hd, mq , mp i := ExtendedEuclid(p, q)
3 x1 := a(p+1)/4 mod p
4 x2 := p − x1
5 y1 := a(q+1)/4 mod q
6 y2 := q − y1
7 v1 := (x1 · q · mp + y1 · p · mq ) mod n
8 v2 := (x2 · q · mp + y1 · p · mq ) mod n
9 v3 := (x1 · q · mp + y2 · p · mq ) mod n
10 v4 := (x2 · q · mp + y2 · p · mq ) mod n
11 return hv1 , v2 , v3 , v4 i
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
36 / 138
Rabin-Kryptosystem
Sicherheitsaspekte
Sicherheitsaspekte
• Die Sicherheit des Rabin-Kryptosystems ist an das
Faktorisierungsproblem gekoppelt
• Findet man eine effiziente Methode, um das Rabin-Kryptosystem
zu brechen, dann kann man effizient zusammengesetzte Zahlen
faktorisieren, und umgekehrt
• Das Rabin-System ist anfällig gegen eine Attacke mit frei
wählbarem Geheimtext
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
37 / 138
Rabin-Kryptosystem
Angriff mit frei wählbarem Geheimtext
Angriff mit frei wählbarem Geheimtext
Annahme: x ist eine der vier Wurzeln von y = r 2 mod n
Dann kann man unter Einsatz des CRT vier Fälle unterschieden:
(1)
(2)
(3)
(4)
x
x
x
x
≡ r (mod p) und x
≡ −r (mod p) und
≡ r (mod p) und x
≡ −r (mod p) und
≡ r (mod q)
x ≡ −r (mod q)
≡ −r (mod q)
x ≡ r (mod q)
Erkenntnis:
• Die Fälle (1) und (2) sind nicht verwertbar
• Anhand Fall (3) oder (4) kann man n faktorisieren
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
38 / 138
Rabin-Kryptosystem
Angriff mit frei wählbarem Geheimtext
Angriff mit frei wählbarem Geheimtext (Forts.)
Aus Fall (3) folgt, dass:
x − r ≡ 0 (mod p) und x − r ≡ −2r (mod q)
Anwendung des CRT:
x − r ≡ 0 · q · mp − 2 · r · p · mq
≡ −2 · r · p · mq
(mod n)
(mod n)
Also ist:
x − r = ` · n − 2 · r · p · mq
= p · (` · q − 2 · r · mq )
für ein ` ∈ N. Hieraus folgt: gcd(x − r , n) = p
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
39 / 138
Rabin-Kryptosystem
Angriff mit frei wählbarem Geheimtext
Angriff mit frei wählbarem Geheimtext (Forts.)
Fall (4) kann auf analoge Weise analysiert werden
Bemerkungen:
• Die Wahrscheinlichkeit, dass für ein zufälliges r Fall (3) oder (4)
eintritt, ist 21
• Durch wiederholtes Ausführen von RabinAttack(n) kann die
Erfolgswahrscheinlichkeit erhöht werden
• Liefert RabinAttack(n) alle vier Wurzeln als Ergebnis, dann
führt der Angriff direkt zum Erfolg
• Der Angriff kann verhindert werden, indem man den Klartext mit
einer eindeutigen, wiedererkennbaren Markierung versieht
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
40 / 138
Rabin-Kryptosystem
Angriff mit frei wählbarem Geheimtext
Angriff mit frei wählbarem Geheimtext (Forts.)
RabinAttack(n)
Input: Öffentlicher Schlüssel n
1 r := Random(1, n − 1)
2
2 y := r mod n
3 // Die Entschlüsselung liefert eine der vier Wurzeln
4 x := RabinDecrypt(y )
5 if x ≡ ±r (mod n) then
6
return”Failure”
7 else
8
p := gcd(x − r , n)
9
q := n/p
10
return (p, q)
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
41 / 138
RSA-Kryptosystem
RSA-Kryptosystem
• Erstes asymmetrisches Kryptosystem
• Erfindung im Jahr 1977
• Benannt nach seinen Erfindern Ronald Rivest, Adi Shamir &
Leonard Adleman
• Sicherheit abhängig von der Komplexität des
Faktorisierungsproblems
• Weltweit meist genutztes Public Key Kryptosystem
• Für Details zur Implementierung siehe Standard PKCS #1
Version 2.2 ( Webpage)
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
42 / 138
RSA-Kryptosystem
Definition
Definition RSA-Kryptosystem
Parameter:
• Primzahlen p und q, wobei p 6= q
• n =p·q
Kryptosystem:
• P = C = Zn
n = pq, wobei p, q prim,
• K = (n, p, q, e, d) e · d ≡ 1 (mod φ(n))
• Schlüssel k = (n, p, q, e, d) ∈ K
. Öffentlicher Teil: (n, e)
. Privater Teil: (p, q, d)
• Verschlüsselung: enc (k, x) = x e mod n
• Entschlüsselung: dec (k, y ) = y d mod n
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
43 / 138
RSA-Kryptosystem
Beispiel
Beispiel zu RSA
Angenommen, Bob wählt p = 101 und q = 113. Dann ist n = 11413
und φ(n) = 100 × 112 = 11200.
Die Primfaktorzerlegung von 11200 ist 26 52 7. Also muss Bob für e
eine Zahl wählen, die nicht durch 2, 5 und 7 teilbar ist. Er
entscheidet sich für e = 3533. Er überprüft mittels des Extended
Euklid Algorithmus, dass gcd(e, φ(n)) = 1 und ermittelt
e −1 = 6597 mod 11200.
Der geheimzuhaltende Exponent zur Entschlüsselung ist also
d = 6597.
Bob veröffentlicht den öffentlichen Schlüssel (n = 11413, e = 3533)
in einem für jedermann lesbaren Public Key Verzeichnis.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
44 / 138
RSA-Kryptosystem
Beispiel
Beispiel zu RSA (Forts.)
Alice will den Klartext x = 9726 an Bob senden. Hierzu besorgt sie
sich Bob’s öffentlichen Schlüssel (n = 11413, e = 3533) aus obigem
Public Key Verzeichnis.
Anschließend berechnet sie
97263533 mod 11413 = 5761
und sendet den Geheimtext 5761 an Bob.
Bob benutzt seinen geheimen Schlüssel d = 6597, um die Nachricht
zu entschlüsseln:
57616597 mod 11413 = 9726.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
45 / 138
RSA-Kryptosystem
Offene Fragen
Offene Fragen
• Ist RSA tatsächlich ein Kryptosystem? Mit anderen Worten, gilt
die Gleichung
dec (k, enc (k, x)) = (x e mod n)d mod n = x
für alle x ∈ P und k = (n, p, q, e, d) ∈ K?
• Warum ist RSA sicher?
• Kann man RSA effizient implementieren?
• Wie wird der Schlüssel k = (n, p, q, e, d) erzeugt? Was ist
hierbei zu beachten?
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
46 / 138
RSA-Kryptosystem
Korrektheit
Warum funktioniert RSA?
Aufgrund der Definition von RSA gilt für k = (n, p, q, e, d):
dec (k, enc (k, x)) = x ed mod n.
Die Zahlen e und d sind multiplikative Inverse modulo
φ(n) = (p − 1)(q − 1). Somit ist
ed = 1 + i(p − 1)(q − 1)
für eine ganze Zahl i.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
47 / 138
RSA-Kryptosystem
Korrektheit
Warum funktioniert RSA? (Forts.)
Für x 6≡ 0 (mod p) folgt wegen dem Satz von Fermat:
x ed ≡ x(x p−1 )i(q−1)
≡ x(1)i(q−1)
≡ x
(mod p)
(mod p)
(mod p)
Ferner ist x ed ≡ x mod p, falls x ≡ 0 (mod p).
Also gilt für alle x ∈ Zn : x ed ≡ x mod p.
Analog zeigt man, dass x ed ≡ x mod q für alle x ∈ Zn .
Da n = pq, folgt wegen des Chinesischen Restsatzes, dass
x ed ≡ x
(mod n)
für alle x ∈ Zn .
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
48 / 138
RSA-Kryptosystem
Sicherheit
Sicherheit von RSA
Die Sicherheit von RSA beruht auf der (vermutlich) hohen
Komplexität zweier arithmetischer Probleme.
• Faktorisierungsproblem: Finde für eine gegebene ganze Zahl n
zwei ganzzahlige Faktoren von n, d.h., zwei Zahlen p, q ∈ Z so
dass p · q = n.
• Invertieren der modularen Potenzfunktion: Finde für die
gegebenen ganzen Zahlen e, n, y wobei n > 0 ein x ∈ Zn so dass
x e mod n = y .
Für keines der beiden Probleme ist ein Polynomialzeit Algorithmus
bekannt. Allerdings konnte bisher auch nicht bewiesen werden, dass
kein Polynomialzeit Algorithmus für obige Probleme existiert.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
49 / 138
RSA-Kryptosystem
Erzeugen eines RSA Schlüssels
Erzeugen eines RSA Schlüssels
Schritte zur Generierung eines RSA-Schlüssels:
1. Generierung zweier großer Primzahlen p und q (mindestens 2048
Bit pro Primzahl)
2. Berechnung von n = pq und φ(n) = (p − 1)(q − 1)
3. Generierung einer Zufallszahl e ∈ {1, 2, . . . , φ(n) − 1}, wobei
gcd(e, φ(n)) = 1
4. Berechnung d = e −1 mod φ(n) mit dem Erweiterten
Algorithmus von Euklid
5. Veröffentlichung des öffentlichen Schlüssels (n, e) auf geeignete
Art und Weise
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
50 / 138
RSA-Kryptosystem
Berechnung von multiplikativen Inversen
Erweiterter Algorithmus von Euklid
ExtendedEuclid(a, b)
Input: a, b ganze Zahlen, wobei a > b > 0
Output: (d, x, y ) wobei d = ax + by = gcd(a, b)
1
if (b = 0) then
2
return (a, 1, 0);
3
else
4
(d 0 , x 0 , y 0 ) := ExtendedEuclid(b, a mod b)
5
d := d 0 ;
6
x = y 0;
7
y = x 0 − b ba cy 0
8
return (d, x, y )
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
51 / 138
RSA-Kryptosystem
Berechnung von multiplikativen Inversen
Berechnung von multiplikativen Inversen
Bekannt: a ist invertierbar modulo n, falls gcd(a, n) = 1.
Wegen ZTK (Satz 3.4) gibt es x, y ∈ Z so dass
gcd(a, n) = 1 = ax + ny .
Somit gilt:
1 ≡ ax + ny
≡ ax
(mod n)
(mod n)
Also: x ist das multiplikative Inverse von a modulo n.
Fazit: Multiplikative Inverse kann man mittels dem Extended Euklid
Algorithmus berechnen.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
52 / 138
RSA-Kryptosystem
Berechnung von multiplikativen Inversen
Algorithmus zur Inversenberechnung
MultInverse(a, n)
Input: a, n ganze Zahlen, wobei n > 0
Output: a−1 mit aa−1 ≡ 1 (mod n) falls existent
1
(d, x, y ) := ExtendedEuklid(a, n)
2
if (d 6= 1) then
3
return “Inverse doesn’t exist.”
4
else
5
return x
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
53 / 138
RSA-Kryptosystem
Garner Verfahren
Effiziente Entschlüsselung mit Garners Verfahren
Ansatz: Einsatz von p und q zur effizienteren Entschlüsselung von y
Garner’s Formel: Berechne
a = y d mod p
b = y d mod q
x = (((a − b)(q −1 mod p)) mod p) · q + b
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
54 / 138
Angriffe auf RSA
Angriffe auf RSA
• Die Sicherheit von RSA hängt von verschiedenen Faktoren ab,
insbesondere von
. der Qualität des Schlüssels, und
. der Geheimhaltung des privaten Schlüssels
• Gelingt es, ein Bit eines beliebig wählbaren Geheimtextes zu
entschlüsseln, dann kann man den kompletten Geheimtext
entschlüsseln
• Trotz der bekannten Schwächen ist RSA bei korrekter
Benutzung als sicher einzustufen
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
55 / 138
Angriffe auf RSA
Angriffsziele
• Komplette Kompromittierung
Oskar ist in der Lage, den geheimen Teil des RSA-Schlüssels
von Bob zu ermitteln und kann somit alle Geheimtexte
entschlüsseln
• Komplette oder teilweise Entschlüsselung eines Geheimtexts
Oskar kann Teile von vertraulichen Informationen ermitteln,
jedoch nicht den geheimen Teilschlüssel von Bob berechnen
• Unterscheidbarkeit von Geheimtext
mit einer Wahrscheinlichkeit von > 12 kann Oskar einen
verschlüsselten Klartext von einem Zufallsstring unterscheiden
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
56 / 138
Angriffe auf RSA
Faktorisierung von n bei bekannten φ(n)
Faktorisierung von n bei bekanntem φ(n)
Annahme: Oskar kennt:
1. n = p · q
2. φ(n) = (p − 1) · (q − 1)
Ziel: Berechnung eines Faktors von n
Ansatz: Gleichungssystem mit den Unbekannten p und q lösen
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
57 / 138
Angriffe auf RSA
Faktorisierung von n bei bekannten φ(n)
Faktorisierung von n bei bekanntem φ(n) (Forts.)
Gleichung 1: q =
n
p
Einsetzen in Gleichung 2
φ(n) = (p − 1) ·
n
−1
p
Umformen:
n
+1
p
p · φ(n) = pn − p 2 − n + p
0 = p 2 + (φ(n) − n − 1)p + n
φ(n) = n − p −
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
58 / 138
Angriffe auf RSA
Faktorisierung von n bei bekannten φ(n)
Faktorisierung von n bei bekanntem φ(n) (Forts.)
Mitternachtsformel:
p1,2 =
−b ±
√
b 2 − 4ac
2a
mit:
a = 1
b = φ(n) − n − 1
c = n
Ist diese Gleichung lösbar, dann sind p1 und p2 die beiden Faktoren
von n, d.h., n = p1 · p2
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
59 / 138
Angriffe auf RSA
Die Wiener Attacke
Die Wiener Attacke
• Angriff von Michael J. Wiener
• Sind die Parameter des RSA-Schlüssels ungünstig gewählt, dann
kann man n faktorisieren
• Es kommt ein Satz aus der Zahlentheorie zum Einsatz
• Herleitung mittels endlichen Kettenbrüchen
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
60 / 138
Angriffe auf RSA
Die Wiener Attacke
Endliche Kettenbrüche
Ein (endlicher) Kettenbruch ist ein Term
q1 +
1
q2 +
1
q3 +...+ q1
.
m
wobei q1 , . . . , qm nicht-negative, ganze Zahlen sind.
Eine alternative Schreibweise ist:
[q1 , . . . , qm ]
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
61 / 138
Angriffe auf RSA
Die Wiener Attacke
Endliche Kettenbrüche (Forts.)
Satz 4 Seien a, b ∈ N, wobei b > 0. Dann existiert ein endlicher
Kettenbruch [q1 , . . . , qm ] mit
a
1
= q1 +
1
b
q2 + q +...+
3
.
1
qm
Bemerkung. Der Kettenbruch kann mit dem Algorithmus von Euklid
berechnet werden.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
62 / 138
Angriffe auf RSA
Die Wiener Attacke
Algorithmus von Euklid
Euklid(a, b)
Input: Ganze Zahlen a, b ∈ N 0 , wobei a > 0, b ≥ 0.
Output: (d, hq1 , . . . , qm i), wobei d = gcd(a, b)
1 r0 := a
2 r1 := b
3 m := 1
4 while rm 6= 0 do
j
k
5
qm := rm−1
rm
6
7
8
9
rm+1 := rm−1 − qm · rm
m := m + 1
m := m − 1
return (rm , hq1 , . . . , qm i)
Prof. Dr. C. Karg (HS Aalen)
// d.h. rm+1 = gcd(rm−1 , rm )
Kryptografische Algorithmen
Public Key Kryptosysteme
63 / 138
Angriffe auf RSA
Die Wiener Attacke
Beispiel: Berechnung eines Kettenbruchs
Gegeben: a = 42, b = 73
Der Ablauf der Berechnung des Algorithmus von Euklid ist:
42
73
42
31
11
9
2
=
=
=
=
=
=
=
0 · 73 + 42
1 · 42 + 31
1 · 31 + 11
2 · 11 + 9
1·9+2
4·2+1
2·1+0
Jede Gleichung repräsentiert dabei den Term rm−1 = qm · rm + rm+1 .
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
64 / 138
Angriffe auf RSA
Die Wiener Attacke
Beispiel: Berechnung eines Kettenbruchs (Forts.)
Der Algorithmus von Euklid liefert (1, [0, 1, 1, 2, 1, 4, 2]) als Ergebnis.
Also ist:
Prof. Dr. C. Karg (HS Aalen)
42
=0+
73
1+
1
1
1+
1
2+
1+
Kryptografische Algorithmen
1
1
4+ 1
2
Public Key Kryptosysteme
65 / 138
Angriffe auf RSA
Die Wiener Attacke
Konvergenten eines Kettenbruchs
Sei [q1 , . . . , qm ] ein Kettenbruch. Für 1 ≤ j ≤ m ist
Cj = [q1 , . . . , qj ]
die j-te Konvergente von [q1 , . . . , qm ].
Cj nennt man auch den j-ten Näherungsbruch.
Cj ist darstellbar als
cj
,
dj
wobei




1,
j
=
0
j =0

0,
cj = q 1 ,
j = 1 und dj = 1,
j =1




qj · cj−1 + cj−2 , j ≥ 2
qj · dj−1 + dj−2 , j ≥ 2
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
66 / 138
Angriffe auf RSA
Die Wiener Attacke
Beispiel: Konvergenten
Gegeben ist der Kettenbruch [0, 1, 1, 2, 1, 4, 2].
Die entsprechenden Konvergenten sind:
[0]
[0, 1]
[0, 1, 1]
[0, 1, 1, 2]
[0, 1, 1, 2, 1]
[0, 1, 1, 2, 1, 4]
[0, 1, 1, 2, 1, 4, 2]
Prof. Dr. C. Karg (HS Aalen)
=
=
=
=
=
=
=
Kryptografische Algorithmen
0/1
1/1
1/2
3/5
4/7
19/33
42/73
Public Key Kryptosysteme
67 / 138
Angriffe auf RSA
Die Wiener Attacke
Ein wichtiger Satz . . .
Satz 5 Seien a, b, c, d beliebige natürliche Zahlen.
Angenommen, gcd(a, b) = 1, gcd(c, d) = 1 und
a c 1
− < 2.
b d
2d
Dann ist
c
d
eine der Konvergenten des Kettenbruchs von ba .
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
68 / 138
Angriffe auf RSA
Die Wiener Attacke
. . . und seine Folgen
Anwendung: Berechnung des geheimen Exponenten d
Voraussetzungen:
• q < p < 2q
• 3d < n1/4
Bemerkung: Der Angriff ist erfolgreich, wenn
• p und q nicht zu weit auseinander liegen und
• die Binärdarstellung von d weniger als `/4 − 1 Bits groß ist.
Hierbei steht ` für die Länge der Binärdarstellung von n
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
69 / 138
Angriffe auf RSA
Die Wiener Attacke
Anwendung des Satzes
Da e · d ≡ 1 (mod φ(n)), existiert ein t, so dass
e · d − t · φ(n) = 1.
√
Da n = p · q > q 2 , ist q < n.
Hieraus folgt:
√
0 < n − φ(n) = p + q − 1 < 2q + q − 1 < 3q < 3 n
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
70 / 138
Angriffe auf RSA
Die Wiener Attacke
Anwendung des Satzes (Forts.)
Einsetzen, wobei a = e, b = n, c = t, d = d:
e
ed − tn t − = n d
dn 1 + t(φ(n) − n) = dn
1
+
t(φ(n)
−
n)
= −
dn
t(n − φ(n)) − 1 = dn
t(n − φ(n)) < dn
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
71 / 138
Angriffe auf RSA
Die Wiener Attacke
Anwendung des Satzes (Forts.)
√
t(n − φ(n)) t
·
3
n
<
dn
dn
3t
√
=
d n
Da t < d, ist 3t < 3d < n1/4 . Hieraus folgt:
n1/4
dn1/2
d n
1
=
dn1/4
1
<
3d 2
3t
√
Prof. Dr. C. Karg (HS Aalen)
<
Kryptografische Algorithmen
Public Key Kryptosysteme
72 / 138
Angriffe auf RSA
Die Wiener Attacke
Anwendung des Satzes (Forts.)
Zusammenfassung:
e
t 1
− < 2
n d
3d
Wegen des obigen Satzes ist
t
d
eine der Konvergenten von
Folgerung: Anhand der Konverten von
berechnen
Prof. Dr. C. Karg (HS Aalen)
e
n
e
n
kann man φ(n) =
Kryptografische Algorithmen
e·d−1
t
Public Key Kryptosysteme
73 / 138
Angriffe auf RSA
Die Wiener Attacke
Wiener Attacke
Eingabe: Öffentlicher RSA-Schlüssel (n, e)
Vorgehen:
1. Berechne die Konvergenten
c0 c1
ck
, ,...,
d0 d1
dk
des Kettenbruchs
e
n
2. Überprüfe für die Konvergente
ci
,
di
i = 2, . . . , k,
e·di −1
ci
. ob φn =
eine ganze Zahl ist, und
. ob n anhand von φn faktorisierbar ist
3. Schlägt die obige Überprüfung für alle Konvergenten fehl, dann
gib “Angriff fehlgeschlagen” aus.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
74 / 138
Angriffe auf RSA
Die Wiener Attacke
Beispiel Wiener Attacke
Gegeben: n = 2989234739, e = 2501103889.
Der Kettenbruch von
e
n
ist:
[0, 1, 5, 8, 13, 3, 2505, 1, 7, 3, 1, 5, 3]
Für c4 = 41 und d4 = 49 ist
φn =
e · d4 − 1
2501103889 · 49 − 1
=
= 2989124160
c4
41
Die Faktorisierung von n anhand von φn liefert p = 47059 und
q = 63521 als Faktoren von n.
Der geheime RSA-Schlüssel ist d = 49.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
75 / 138
Angriffe auf RSA
Highest-Order-Bit-Attacke
Highest-Order-Bit-Attacke
Annahme: Für y = enc (K , x) ist die Funktion
0, 0 ≤ x < n2
half (y) =
1, n2 < x ≤ n − 1
effizient berechenbar.
Frage: Lässt sich dies für einen Angriff auf RSA ausnutzen?
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
76 / 138
Angriffe auf RSA
Highest-Order-Bit-Attacke
Eine nützliche Eigenschaft von RSA
Für alle x1 , x2 ∈ Zn gilt:
enc (K , x1 · x2 ) ≡ (x1 · x2 )d
≡ x1d · x2d
≡ enc (K , x1 ) · enc (K , x2 )
(mod n)
(mod n)
(mod n)
Insbesondere gilt für alle i = 1, 2, 3, . . .:
enc (K , 2i · x2 ) ≡ enc (K , 2i ) · enc (K , x2 )
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
(mod n)
Public Key Kryptosysteme
77 / 138
Angriffe auf RSA
Highest-Order-Bit-Attacke
Anwendung der obigen Eigenschaft
n
half (enc (K , x)) = 0 ⇔ x ∈ 0,
2
h n n 3n half (enc (K , 2 · x)) = 0 ⇔ x ∈ 0,
∪ ,
4
2 4
h n n 3n half (enc (K , 4 · x)) = 0 ⇔ x ∈ 0,
∪ ,
∪
8
4 8
n 5n
3n 7n
,
∪
,
2 8
4 8
..
.
h
Mittels Binärer Suche kann man den Schlüssel systematisch
berechnen.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
78 / 138
Angriffe auf RSA
Highest-Order-Bit-Attacke
Algorithmus HalfAttack(n, e, y )
HalfAttack(n, e, y )
Input: Öffentlicher RSA-Schlüssel (n, e), Geheimtext y
Output: Zu y gehörender Klartext x
1 ` := blog2 nc
2 for i := 0 to ` do
3
hi := Half(n, e, y )
4
y := y · 2e mod n
5 lo := 0; hi := n
6 for i := 0 to `
7
mid := (hi + lo)/2
8
if hi = 1 then
9
lo := mid
10
else
11
hi := mid
12 return bhic
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
79 / 138
Angriffe auf RSA
Highest-Order-Bit-Attacke
Bemerkungen zu HalfAttack(n, e, y )
• Der Algorithmus nutzt die multiplikative Eigenschaft sowie die
Half-Funktion, um das höchstwertigste Bit von
x, 2 · x, 22 · x, . . . , 2`−1 · x
zu berechnen.
• Anschließend wird auf Basis der höchstwertigsten Bits eine
Binäre Suche durchgeführt, um den Klartext x zu bestimmen.
• Die Nachkommastellen bei der Division sind zu beachten.
• Die Laufzeit des Algorithmus ist O(`3 + ` · th (`)), wobei th (`) für
die Laufzeit von Half(n, e, y ) für `-Bit Zahlen steht
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
80 / 138
Angriffe auf RSA
Highest-Order-Bit-Attacke
Beispiel
Gegeben: n = 4757, e = 857, y = 2238.
Die Wortlänge von n ist ` = blog2 c = 12.
Die Berechnung der höchstwertigsten Bits liefert:
i 0 1 2 3 4 5 6 7 8 9 10 11 12
hi 0 0 1 0 0 1 1 1 1 1 1 0 1
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
81 / 138
Angriffe auf RSA
Highest-Order-Bit-Attacke
Beispiel (Forts.)
i
0
1
2
3
4
5
6
7
8
9
10
11
12
−
hi
0
0
1
0
0
1
1
1
1
1
1
0
1
−
lo
0.000000000000
0.000000000000
0.000000000000
594.625000000000
594.625000000000
594.625000000000
668.953125000000
706.117187500000
724.699218750000
733.990234375000
738.635742187500
740.958496093750
740.958496093750
741.539184570312
mid
2378.500000000000
1189.250000000000
594.625000000000
891.937500000000
743.281250000000
668.953125000000
706.117187500000
724.699218750000
733.990234375000
738.635742187500
740.958496093750
742.119873046875
741.539184570312
741.539184570312
hi
4757.000000000000
2378.500000000000
1189.250000000000
1189.250000000000
891.937500000000
743.281250000000
743.281250000000
743.281250000000
743.281250000000
743.281250000000
743.281250000000
743.281250000000
742.119873046875
742.119873046875
Ergebnis: Klartext x = 742
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
82 / 138
Angriffe auf RSA
Highest-Order-Bit-Attacke
Angriff durch Berechnung des niederwertigsten Bits
Falls für y = enc (K , x) die Funktion
0, x gerade
parity(y ) =
1, x ungerade
effizient berechenbar ist, dann kann man auch den kompletten
Klartext berechnen.
Begründung: Es gelten folgende Beziehungen:
half (y ) = parity((y · enc (K , 2)) mod n)
parity(y ) = half ((y · enc (K , 2−1 )) mod n)
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
83 / 138
Angriffe auf RSA
Zusammenfassung
Zusammenfassung
• RSA nutzt modulare Exponentiation zur Ver- und
Entschlüsselung.
• Die Sicherheit von RSA beruht auf der (hoffentlich) hohen
Berechnungskomplexität des Faktorisierungsproblems und des
diskreten Logarithmus.
• Da der öffentliche Teil des Schlüssels öffentlich zugänglich ist,
kann jedermann eine verschlüsselte Nachricht an Bob senden.
• RSA kann auch zur Signatur von Nachrichten eingesetzt werden.
• Bei hinreichend langer Schlüssellänge und guter Wahl der
Parameter gilt RSA als sicheres Kryptosystem.
• Für eine praxistaugliche Implementierung sind diverse Aspekte
zu beachten. Weitere Details findet man im RSA-Standard.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
84 / 138
Diffie-Hellman-Schlüsselaustausch
Diffie-Hellman-Schlüsselaustausch
• Erfunden von Whitfield Diffie und Martin E. Hellman aus dem
Jahr 1976
• Protokoll zur vertraulichen Konstruktion eines Schlüssels über
einen unsicheren Kanal
• Sicherheit basiert auf dem Diskreter-Logarithmus-Problem
• Die Arbeit von Diffie und Hellman gilt als die Geburtsstunde der
Public Key Kryptografie
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
85 / 138
Diffie-Hellman-Schlüsselaustausch
Protokoll
Protokoll zum Schlüsselaustausch
Sei p eine Primzahl und α ein Generator von Z∗p
Alice
Bob
Wählt zufällig ein a ∈ Z∗p
Wählt zufällig ein b ∈ Z∗p
αa mod p
αb mod p
αab mod p
Geheimer Schlüssel
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
86 / 138
Diffie-Hellman-Schlüsselaustausch
Protokoll
Beispiel
Angenommen, p = 27803 und α = 5 sind die öffentlichen Parameter
für einen Diffie-Hellman-Schlüsselaustausch.
Alice würfelt a = 21131 und berechnet 521131 mod 27803 = 21420.
Anschließend sendet sie Bob diesen Wert.
Bob würfelt b = 17555 und berechnet 517555 mod 27803 = 17100.
Diesen Wert sendet er an Alice.
Alice und Bob berechnen schließlich den geheimen Schlüssel
2142017555 mod 27803 = 1710021131 mod 27803 = 11134.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
87 / 138
Diffie-Hellman-Schlüsselaustausch
Protokoll
Man-In-The-Middle Attacke
∗
αa mod p
Alice
αa mod p
Oskar
b∗
α
Bob
b
mod p
α mod p
• Oskar sitzt “zwischen” Alice und Bob und fungiert als
Vermittlungsstelle.
• Oskar ersetzt die Teilschlüssel von Alice und Bob durch seine
eigenen.
• Alice und Bob können zwar ihre Daten mit dem ausgehandelten
Schlüssel verschlüsseln, aber keiner kann die Daten des anderen
entschlüsseln.
• Oskar kann alle Daten ver- bzw. entschlüsseln und entsprechend
weiterleiten.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
88 / 138
Diffie-Hellman-Schlüsselaustausch
Station-To-Station-Protokoll
Verbessertes Verfahren
Sei p eine Primzahl und α ein Generator von Z∗p
Alice
Bob
a
α
αb , signB (mB , αa , αb )
signA (mA , αa , αb )
Alle Berechnungen verstehen sich modulo p
mA und mB stehen für den Signaturschlüssel von Alice bzw. Bob
• Dieses Verfahren ist eine Vereinfachung des Station-To-Station
Protokolls.
• Eine zusätzliche Absicherung wird durch den Einsatz von
Zertifikaten erreicht.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
89 / 138
El Gamal Kryptosystem
ElGamal Kryptosystem
• Erfindung von Taher ElGamal aus dem Jahr 1984
• Probabilistisches Kryptosystem
• Sicherheit hängt ab vom Diskreter-Logarithmus-Problem für
endliche Körper
• Grundlage für zahlreiche weitere Kryptosysteme
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
90 / 138
El Gamal Kryptosystem
Definition
Definition ElGamal-Kryptosystem
Parameter:
• Primzahl p
• Erzeugendes Element α von Z∗p
Kryptosystem:
• P = Zp , C = Zp × Zp
• K = {(p, α, a, β) | 2 ≤ a ≤ p − 2, β ≡ αa (mod p)}.
• Schlüssel k = (p, α, a, β) ∈ K:
. Öffentlicher Teil: (p, α, β)
. Geheimer Teil: a
• Verschlüsselung: enc (k, x) = (y1 , y2 ), wobei
. y1 = αz mod p
. y2 = xβz mod p
für eine zufällig gewählte, geheime Zahl z ∈ Zp−1
• Entschlüsselung: dec (k, (y1 , y2 )) = y2 (y1a )−1 mod p
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
91 / 138
El Gamal Kryptosystem
Definition
Die Idee hinter ElGamal
• Alice verschlüsselt den Klartext x ∈ Zp , indem sie ihn
“maskiert”, d.h., mit βz multipliziert. Die modulare
Exponentialfunktion wird also zur Generierung eines
Zufallsstroms eingesetzt.
• Da Bob die Zufallszahl z nicht kennt, muss Alice diese an ihn
senden. Dies kann nicht direkt geschehen, da Oskar sonst aus
dem öffentlich bekannten β den Wert βz berechnen und somit
den Geheimtext dechiffrieren könnte.
• Da Bob a und somit auch (αz )a = βz kennt, sendet Alice den
Wert αz . Somit ist Bob in der Lage, die Maske zu entfernen
indem er y2 mit dem Inversen von βk multipliziert.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
92 / 138
El Gamal Kryptosystem
Beispiel
Beispiel
Bob wählt p = 2579, α = 2, a = 765 und β = 2765 mod 2579 = 949.
Angenommen, Alice will an Bob die Nachricht x = 1299 senden. Sie
wählt (zufällig) die Zahl z = 853 aus. Dann berechnet sie
• y1 = 2853 mod 2579 = 435, und
• y2 = 1299 × 949853 mod 2579 = 2396.
Bei Empfang des Geheimtextes y = (435, 2396) berechnet Bob
x = 2396 × (435765 )−1 mod 2579 = 1299.
Das Ergebnis ist offensichtlich identisch mit dem von Alice
versandten Klartext.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
93 / 138
El Gamal Kryptosystem
Korrektheit
Korrektheit von ElGamal
Zum Nachweis der Korrektheit des ElGamal Kryptosystems ist zu
zeigen, dass
dec (k, enc (k, x, z)) = x
für alle k = (p, α, a, β) ∈ K, alle z ∈ Zp−1 und alle x ∈ Zp gilt.
Betrachte y1 = αz mod p und y2 = xβz mod p.
Da
y1a ≡ (αz )a ≡ (αa )z ≡ βz
(mod p)
ist (y1a )−1 = (βz )−1 .
Hieraus folgt:
y2 (y1a )−1 ≡ xβz (βz )−1 ≡ x
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
(mod p).
Public Key Kryptosysteme
94 / 138
El Gamal Kryptosystem
Sicherheit
Warum ist ElGamal sicher?
Die Sicherheit des ElGamal Kryptosystems basiert auf folgenden
Annahmen:
• Hohe Berechnungskomplexität des DLP: Verfügt Oskar über
einen effizienten Algorithmus zur Berechnung von logpα β, dann
kann er ohne Mühe aus β = αa den geheimen Schlüssel a
berechnen.
• Zufällige Wahl von z: Benutzt Alice immer dasselbe z zur
Verschlüsselung, dann besteht die Möglichkeit eines Angriffs mit
bekanntem Klartext-Geheimtext-Paar.
Das ElGamal Kryptosystem wird auch als probabilistisches
Kryptosystem bezeichnet, da der Klartext x in viele zufällige
Geheimtexte (y1 , y2 ) abgebildet wird.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
95 / 138
El Gamal Kryptosystem
Schlüsselerzeugung
Wie erzeugt man einen Generator?
Ähnlich wie bei RSA werden auch beim ElGamal Kryptosystem die
Parameter zufällig erzeugt.
Bei der Erstellung des Generators sind folgende Fakten hilfreich:
• Ist Z∗n eine zyklische Gruppe, dann ist die Anzahl ihrer
Generatoren gleich φ(φ(n)). Für eine Primzahl p ist die Anzahl
der Generatoren von Z∗p gleich φ(p − 1).
• Man kann beweisen, dass φ(n) ≥ n/6 ln(ln(n)) für alle n. Wenn
man also zufällig ein Element α aus Z∗n zieht, dann ist die
Chance gut, dass α ein Generator ist.
• Die Zahl α ∈ Z∗n ist ein Generator von Z∗n genau dann, wenn
αφ(n)/p 6≡ 1 (mod n) für alle Primteiler p von φ(n).
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
96 / 138
El Gamal Kryptosystem
Schlüsselerzeugung
Algorithmus zur Generatorerzeugung
RandomGenerator(p, p1 , e1 , p2 , e2 , . . . , pk , ek )
Input: Primzahl p, Primfaktorzerlegung p1e1 p2e2 . . . pkek von φ(p)
Output: Generator α von Z∗p
1
found := false;
2
while (found = false) do
3
α := Random(2, p − 1);
4
found := true;
5
for i := 1 to k do
6
b := αp−1/pi mod p;
7
if (b = 1) then found := false;
8
return α;
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
97 / 138
El Gamal Kryptosystem
Schlüsselerzeugung
Erzeugen eines ElGamal Schlüssels
Zur Erstellung eines ElGamal Schlüssels geht man folgendermaßen
vor:
1. Generiere unter Verwendung des Miller-Rabin Primzahltests
zufällig eine Primzahl q so dass auch p = 2q + 1 eine Primzahl
ist.
2. Generiere mittels randomGenerator(p, 2, 1, q, 1) einen
Generator α von Z∗p .
3. Wähle zufällig ein a ∈ {2, . . . , p − 2} und berechne
β = αa mod p.
4. Mache die Werte p, α und β öffentlich zugänglich.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
98 / 138
El Gamal Kryptosystem
Verallgemeinerung
Verallgemeinerung
Unter dem Diskreter Logarithmus Problem über (G , ⊕) versteht man
folgendes Berechnungsproblem:
Gegeben: (G , α, β), wobei G eine endliche Gruppe mit
Gruppenoperation ⊕, α ∈ G und β ∈ H ist. Hierbei ist
H die von α erzeugte Untergruppe.
Gesucht: Finde die eindeutig bestimmte ganze Zahl a,
0 ≤ a ≤ kHk − 1, so dass α(a) = β. Hierbei ist
a
(k)
=
k
M
i=1
Prof. Dr. C. Karg (HS Aalen)
a = a| ⊕ a ⊕{z. . . ⊕ a} .
Kryptografische Algorithmen
k-mal
Public Key Kryptosysteme
99 / 138
El Gamal Kryptosystem
Verallgemeinerung
ElGamal Kryptosystem über (G , ⊕)
Sei (G , ⊕) eine endliche Gruppe. Sei α ∈ G ein Element, so dass das
DLP über der von α erzeugten Untergruppe H = {αi | i ≥ 0}
schwierig zu lösen ist.
Das ElGamal Kryptosystem über (G , ⊕) ist:
• P = G, C = G × G,
• K = {(G , α, a, β) | 2 ≤ a ≤ kHk − 1, β = α(a) }
Für k = (G , α, a, β) ∈ K und eine (geheime) ganze Zahl z ∈ ZkHk
definiere:
• Verschlüsselung: enc (k, x, z) = (y1 , y2 ), wobei y1 = α(z) , und
y2 = x ⊕ β(z) .
• Entschlüsselung: dec (k, (y1 , y2 )) = y2 ⊕ (y1(a) )−1 mod p
(G , α, β) ist der öffentliche, a der geheime Schlüssel.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
100 / 138
Elliptische Kurven
Definition
Elliptische Kurven über Zp
Betrachte eine Gleichung der Bauart
y 2 ≡ x 3 + ax + b
(mod p),
wobei p > 3 eine Primzahl und a, b ∈ Zp mit
4a3 + 27b 2 6≡ 0 (mod p).
Die durch diese Gleichung beschriebene Elliptische Kurve E(p, a, b)
ist die Menge all ihrer Lösungen (x, y ) ∈ Zp × Zp , zusammen mit
einem zusätzlichen Punkt O. Der Punkt O wird Unendlichkeitspunkt
(engl.: point at infinity) genannt.
√
Man kann zeigen: kE(p, a, b)k = p + 1 − t mit t ≤ 2 p.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
101 / 138
Elliptische Kurven
Gruppenoperation
Gruppenoperation ⊕ über E(p, a, b)
Seien P = (x1 , y1 ) und Q = (x2 , y2 ) von O verschiedene Punkte in
E(p, a, b).
• P ⊕O =O⊕P =P
• Falls x2 = x1 und y2 = −y1 , dann ist P ⊕ Q = O.
• Ansonsten ist P ⊕ Q = (x3 , y3 ), wobei
x3 = λ2 − x1 − x2 , und
y3 = λ(x1 − x3 ) − y1 ,
wobei
λ=
Prof. Dr. C. Karg (HS Aalen)
(y2 − y1 )/(x2 − x1 ), falls P 6= Q,
(3x12 + a)/2y1 ,
Kryptografische Algorithmen
falls P = Q,
Public Key Kryptosysteme
102 / 138
Elliptische Kurven
Gruppenoperation
(E(p, a, b), ⊕) ist eine Gruppe
Die Struktur (E(p, a, b), ⊕) ist eine endliche kommutative Gruppe.
• Da (Zp , +, ·) ein Körper ist, sind alle Berechnungen von ⊕
innerhalb von Zp durchführbar. Daher ist die Menge E(p, a, b)
abgeschlossen unter ⊕.
• Das neutrale Element ist O.
• Das Inverse zu (x, y ) ist (x, −y ).
• Die Operation ⊕ ist assoziativ und kommutativ. Der Beweis
dieser Tatsache ist jedoch schwierig.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
103 / 138
Elliptische Kurven
Beispiel
Beispiel: E(11, 1, 6)
Zur Illustration untersuchen wir die Elliptische Kurve
y 2 ≡ x 3 + x + 6 (mod 11).
Zunächst werden die Elemente in E(11, 1, 6) berechnet.
Da 11 = 4 · 2 + 3, sind die Wurzeln eines quadratischen Rests z gleich
±z (11+1)/4 mod 11 = ±z 3 mod 11.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
104 / 138
Elliptische Kurven
Beispiel
Beispiel: E(11, 1, 6) (Forts.)
x x 3 + x + 6 mod 11 ∈ QR(11)?
0
6
−
1
8
−
2
5
X
3
3
X
4
8
−
5
4
X
6
8
−
7
4
X
8
9
X
9
7
−
10
4
X
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
y
4, 7
5, 6
2, 9
2, 9
3, 8
2, 9
Public Key Kryptosysteme
105 / 138
Elliptische Kurven
Beispiel
Beispiel: E(11, 1, 6) (Forts.)
Neben dem Punkt O enthält E(11, 1, 6) die folgenden Elemente:
(2, 4) (2, 7) (3, 5) (3, 6)
(5, 2) (5, 9) (7, 2) (7, 9)
(8, 3) (8, 8) (10, 2) (10, 9)
Somit gilt: kE(11, 1, 6)k = 13. Die Gruppe ist (E(11, 1, 6), ⊕) also
zyklisch.
Wegen des Satzes von Lagrange ist jedes von O verschiedene
Element ein Generator.
Im folgenden wird α = (2, 7) als Generator ausgewählt. Da die
Gruppe additiv ist, schreiben wir der Einfachheit halber i · α anstatt
α(i) .
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
106 / 138
Elliptische Kurven
Beispiel
Beispiel: E(11, 1, 6) (Forts.)
Um 2α = α ⊕ α zu ermitteln, berechnet man zuerst:
λ ≡
≡
≡
≡
(3 · 22 + 1) · (2 · 7)−1
2 · 3−1
2·4
8
(mod
(mod
(mod
(mod
11)
11)
11)
11)
Somit:
x3 = 82 − 2 − 2 mod 11 = 5, und
y3 = 8(2 − 5) − 7 mod 11 = 2.
Also: 2α = (5, 2).
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
107 / 138
Elliptische Kurven
Beispiel
Beispiel: E(11, 1, 6) (Forts.)
Insgesamt:
α
4α
7α
10α
=
=
=
=
(2, 7)
(10, 2)
(7, 2)
(8, 8)
2α
5α
8α
11α
=
=
=
=
(5, 2)
(3, 6)
(3, 5)
(5, 9)
3α
6α
9α
12α
=
=
=
=
(8, 3)
(7, 9)
(10, 9)
(2, 4)
Also ist α = (2, 7) tatsächlich ein Generator von (E(11, 1, 6), ⊕).
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
108 / 138
Elliptische Kurven
Anwendung: ElGamal-Kryptosystem
ElGamal mit (E(11, 1, 6), ⊕)
Bob wählt α = (2, 7) und a = 7 aus. Also ist β = 7α = (7, 2). Der
Schlüssel ist k = ((2, 7), 7, (7, 2)). Die Verschlüsselungsfunktion ist
enc (k, x, z) = (z(2, 7), x ⊕ z(7, 2)),
wobei x ∈ E(11, 1, 6) und 0 ≤ z ≤ 12. Die Entschlüsselungsfunktion
ist
dec (k, y1 , y2 ) = y2 7y1 .
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
109 / 138
Elliptische Kurven
Anwendung: ElGamal-Kryptosystem
ElGamal mit (E(11, 1, 6), ⊕) (Forts.)
Angenommen, Alice will Bob den Klartext (10, 9) ∈ E(11, 1, 6)
senden. Falls sie z = 3 zufällig zieht, dann berechnet sie:
y1 = 3 · (2, 7)
= (8, 3)
und
y2 = (10, 9) ⊕ 3 · (7, 2)
= (10, 9) ⊕ (3, 5)
= (10, 2)
Der Geheimtext ist y = ((8, 3), (10, 2)).
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
110 / 138
Elliptische Kurven
Anwendung: ElGamal-Kryptosystem
ElGamal mit (E(11, 1, 6), ⊕) (Forts.)
Nach Empfang des Geheimtexts y = ((8, 3), (10, 2)) entschlüsselt
Bob diesen wie folgt:
x =
=
=
=
(10, 2) 7 · (8, 3)
(10, 2) (3, 5)
(10, 2) ⊕ (3, 6)
(10, 9)
Die Entschlüsselung liefert also den korrekten Klartext x = (10, 9).
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
111 / 138
Elliptische Kurven
Implementierungsaspekte
Implementierungsaspekte
Die Implementierung von ElGamal über Elliptischen Kurven ist
problematisch.
• Bei ElGamal über Zp ist der Geheimtext um den Faktor 2 größer
als der Klartext. Bei ElGamal über E(p, a, b) ist der
Vergrößerungsfaktor gleich 4.
• Der Klartextraum besteht aus Paaren in E(p, a, b). Es existiert
jedoch keine effiziente deterministische Methode, um diese Paare
systematisch zu erzeugen.
Verbesserung: Methode von Menezes und Vanstone
Idee: Verwende Elliptische Kurven “nur” zur Maskierung!
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
112 / 138
Elliptische Kurven
Kryptosystem von Menezes & Vanstone
Kryptosystem von Menezes & Vanstone
Sei E = E(p, a∗ , b ∗ ) eine Elliptische Kurve, wobei p > 3 prim und das
DLP für eine Untergruppe H von E schwierig ist. Sei α der Generator
dieser Untergruppe.
• P = Z∗p × Z∗p , C = E × Z∗p × Z∗p
• K = {(α, a, β) | α ∈ E, 2 ≤ a ≤ kHk − 1, β = a · α}
• Für k = (α, a, β) und eine (geheime) Zufallszahl z ∈ ZkHk und
für x = (x1 , x2 ) ∈ Z∗p × Z∗p definiere
enc (k, x, z) = (y0 , y1 , y2 )
wobei y0 = z · α, (c1 , c2 ) = z · β, und yi = ci xi mod p für
i = 1, 2.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
113 / 138
Elliptische Kurven
Kryptosystem von Menezes & Vanstone
Kryptosystem von Menezes & Vanstone
• Für einen Geheimtext y = (y0 , y1 , y2 ), definiere
dec (k, y ) = (y1 c1−1 mod p, y2 c2−1 mod p)
wobei (c1 , c2 ) = ay0 .
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
114 / 138
Digitale Signaturen
Einleitung
Alice hat Probleme
Alice erhält per Post ein teures Laptop vom Online Händler XY,
welches sie nie bestellt hat.
Sie geht der Sache nach und stellt fest, daß Oskar sie hinters Licht
geführt hat. Er hat eine E-Mail an den Händler gesandt und in ihrem
Namen den Laptop bestellt.
Um derartige Zwischenfälle in Zukunft zu vermeiden, beschließt Alice,
ihre auf elektronischem Wege abzuwickelnden Geschäfte mittels
digitaler Signaturen abzusichern.
Aber was genau ist eine digitale Signatur?
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
115 / 138
Digitale Signaturen
Einleitung
Anforderungen an eine digitale Signatur
• Die Signatur muss fälschungssicher sein.
• Die Echtheit der Signatur muss effizient überprüfbar sein.
• Die Signatur darf nicht von einem auf ein anderes Dokument
übertragbar sein.
• Eine Änderung des zur Signatur gehörenden Dokuments muss
erkannt werden.
Und Vorsicht: Eine digitale Signatur ist keine eingescannte
Unterschrift.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
116 / 138
Digitale Signaturen
Einleitung
Definition einer digitalen Signatur
Eine digitale Signatur ist gegeben durch ein Tupel (P, S, K, sign, ver)
mit folgenden Eigenschaften:
• P ist die Menge aller Klartexte.
• S ist die Menge aller Signaturen.
• K ist die Menge aller Schlüssel.
• sign : P × K 7→ S ist der Signierungsalgorithmus.
• ver : P × K × S 7→ {true, false} ist der
Verifikationsalgorithmus.
• Für alle Klartexte x und alle Schlüssel k gilt:
true falls s = sign(k, x),
ver(k, x, s) =
false falls s 6= sign(k, x).
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
117 / 138
Digitale Signaturen
Einleitung
Anwendung einer digitalen Signatur
Alice
Oskar
Bob
x
x, s
sign
ke
unsicherer Kanal
kv
x
yes
x, s
ver
kv
Schlüsselverzeichnis
Prof. Dr. C. Karg (HS Aalen)
Benutzer
Schlüssel
Alice
kv
Kryptografische Algorithmen
Public Key Kryptosysteme
118 / 138
Digitale Signaturen
RSA Signatur
Die RSA Signatur
Das auf dem RSA Kryptosystem beruhende Signaturverfahren ist wie
folgt aufgebaut:
• P = S = Zn , wobei n = pq für hinreichend große Primzahlen p
und q
n = pq, wobei p, q prim,
• K = (n, p, q, e, d) e · d ≡ 1 (mod φ(n))
Für k = (n, p, q, e, d) ∈ K definiere
• Signierung: s = sign(k, x) = x d mod n wobei x ∈ Zn
• Verifikation: ver(k, x, s) = true ⇔ x ≡ s e (mod n)
(n, e) ist der öffentliche Teil, (p, q, d) der geheime Teil des Schlüssels.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
119 / 138
Digitale Signaturen
RSA Signatur
Beispiel RSA Signatur
Alice wählt p = 7 und q = 11 und n = p · q = 77. Als geheimen
Schlüssel würfelt sie e = 13 und berechnet d = e −1 mod 60 = 37.
Um die Nachricht m = 5 zu signieren, berechnet Alice
537 mod 77 = 47
und sendet das Paar (5, 47) an Bob.
Bob überprüft die Signatur, indem er
4713 mod 77 = 5
berechnet. Offensichtlich ist sie korrekt, da das Ergebnis mit der
Nachricht identisch ist.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
120 / 138
Digitale Signaturen
RSA Signatur
Verschlüsselung und Signatur
Kombiniert man ein Kryptosystem mit einem Signaturverfahren, dann
stellt sich die Frage nach Reihenfolge von Verschlüsselung und
Signierung.
Eine Möglichkeit ist, den Klartext zunächst zu verschlüsseln und
anschließend den Geheimtext zu signieren. Alice berechnet
y = enc (kB , x) und s = sign(kA , y ). Dann sendet sie die Nachricht
(y , s) an Bob.
Aber: Fängt Oskar die Nachricht ab, dann kann er die Signatur von
Alice durch seine eigene ersetzen.
Daher empfiehlt es sich, die Nachricht zuerst zu signieren und erst
danach zu verschlüsseln.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
121 / 138
Digitale Signaturen
RSA Signatur
Bemerkungen zur RSA Signatur
• Die RSA Signatur ist das am häufigsten eingesetzte
Signaturverfahren.
• Die Sicherheit beruht auf der (vermutlich) hohen Komplexität
des Faktorisierungsproblems.
• Der Schlüssel einer digitalen Signatur ist in der Regel länger als
bei einem Public Key Kryptosystem. Der Grund ist die zeitlich
längere Haltbarkeit von digitalen Signaturen.
• Anstatt die Nachricht blockweise zu signieren, berechnet man
mit einer kryptografischen Hashfunktion eine Prüfsumme und
signiert diese.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
122 / 138
Digitale Signaturen
ElGamal Signatur
Signaturen auf Basis von ElGamal
Sei p eine Primzahl und α ein Generator von Z∗p .
Das ElGamal Signaturverfahren ist wie folgt definiert:
• P = Z∗p , S = Z∗p × Zp−1
• K = {(p, α, a, β) | 2 ≤ a ≤ p − 2, β ≡ αa (mod p)}.
Für k = (p, α, a, β) ∈ K und eine (geheime) Zufallszahl z ∈ Z∗p−1
definiere:
• Signierung: sign(k, x, z) = (γ, δ), wobei
. γ = αz mod p und
. δ = (x − aγ)z −1 mod (p − 1).
• Verifikation: ver(k, (x, γ, δ)) = true genau dann, wenn
βγ γδ ≡ αx (mod p)
(p, α, β) ist der öffentliche und a der geheime Schlüssel.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
123 / 138
Digitale Signaturen
ElGamal Signatur
Beispiel zur ElGamal Signatur
Sei p = 467, α = 2, a = 127 und somit β = 2127 mod 467 = 132.
Bob will die Nachricht x = 100 signieren. Hierzu zieht er die
Zufallszahl z = 213. Man beachte, daß gcd(213, 466) = 1 und
z −1 = 431. Bob berechnet
γ = 2213 mod 467 = 29
und
δ = (100 − 127 × 29) × 431 mod 466 = 51.
Die Signatur von x = 100 ist (γ, δ) = (29, 51).
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
124 / 138
Digitale Signaturen
ElGamal Signatur
Beispiel zur ElGamal Signatur (Forts.)
Um zu verifizieren, daß (γ, δ) = (29, 51) die korrekte Signatur von
x = 100 ist, berechnet man
13229 × 2951 ≡ 189 (mod 467)
und
2100 ≡ 189 (mod 467).
Offensichtlich ist die Signatur korrekt. Zur Überprüfung der Signatur
wird nur der öffentliche Schlüssel benötigt.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
125 / 138
Digitale Signaturen
ElGamal Signatur
Korrektheit der ElGamal Signatur
Zum Nachweis der Korrektheit verwenden wir die Gleichung
aγ + zδ ≡ x
(mod p − 1).
Somit ist aγ + zδ = i(p − 1) + x für eine ganze Zahl i.
Es gilt:
βγ γδ ≡
≡
≡
≡
Prof. Dr. C. Karg (HS Aalen)
αaγ αzδ
αaγ+zδ
αi(p−1)+x
αx
Kryptografische Algorithmen
(mod
(mod
(mod
(mod
p)
p)
p)
p)
Public Key Kryptosysteme
126 / 138
Digitale Signaturen
ElGamal Signatur
Achtung: z unbedingt geheim halten!
Bei der ElGamal Signatur muss Bob unbedingt darauf achten, daß die
Zufallszahl z geheim bleibt.
Gelangt z in die Hände von Oskar, dann kann dieser unter
Verwendung des öffentlichen Schlüssels den geheimen Schlüssel a
berechnen, denn
aγ = (x − zδ) mod (p − 1).
Falls γ ein Inverses modulo p − 1 besitzt, dann ist das
Signaturverfahren gebrochen. Somit kann Oskar beliebige Daten mit
Bob’s Signatur unterzeichnen.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
127 / 138
Digitale Signaturen
ElGamal Signatur
Achtung: z nur einmal verwenden!
Benutzt Bob ein z zur Signierung zweier verschiedener Nachrichten,
dann kann Oskar hieraus a berechnen. Angenommen, (γ1 , δ1 ) und
(γ2 , δ2 ) sind Signaturen der Nachricht x1 bzw. x2 , die unter
Verwendung derselben Zufallszahl z entstanden sind.
Es gilt: γ1 = γ2 = αz und
δ1 − δ2 ≡ (x1 − x2 )z −1
(mod p − 1).
Falls (x1 − x2 ) mod (p − 1) invertierbar ist, dann kann Oskar hieraus
z −1 und somit z bestimmen. Aus z berechnet er anschließend den
geheimen Schlüssel a.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
128 / 138
Digitale Signaturen
ElGamal Signatur
Bemerkungen zur ElGamal Signatur
• Die Sicherheit der ElGamal Signatur hängt von der Komplexität
des Diskreter Logarithmus ab.
• Die ElGamal Signatur kann auch auf Basis anderer Gruppen
(z.B. elliptischer Kurven) berechnet werden.
• Obwohl die ElGamal Signatur frei verfügbar ist, wird sie selten
eingesetzt.
• Aus der ElGamal Signatur wurde der Digital Signature Algorithm
(DSA) abgeleitet und im Jahre 1991 von der NIST standardisiert.
• Der DSA nimmt nach der RSA Signatur den zweiten Platz auf
der Liste der am meisten eingesetzten Signaturverfahren ein.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
129 / 138
Digitale Signaturen
Digital Signature Algorithm (DSA)
Digital Signature Algorithm (DSA)
Der Digital Signature Algorithm ist eine Variante der ElGamal
Signatur. Folgende Modifikationen wurden vorgenommen:
• Die Berechnungen erfolgen über einer Untergruppe von Z∗p der
Größe q. Hierbei ist q eine 160 Bit Primzahl, die die Zahl p − 1
teilt.
• In der Berechnung von δ wird das “−” durch ein “+” ersetzt,
d.h., δ = (x + aγ)z −1 mod q.
• Die Verifikation wird abgeändert in αx βγ ≡ γδ (mod p).
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
130 / 138
Digitale Signaturen
Digital Signature Algorithm (DSA)
Definition von DSA
Sei p eine 512-bit Primzahl und q eine 160-bit Primzahl, die (p − 1)
teilt. Sei α ∈ Z∗p ein Element mit khαik = q.
Der
•
•
•
Digital Signature Algorithm (DSA) ist wie folgt definiert:
P = Z∗p
S = Zq × Zq
K = {(p, q, α, a, β) | 2 ≤ a ≤ p − 2, β ≡ αa (mod p)}.
Für k = (p, q, α, a, β) ∈ K und eine (geheime) Zufallszahl
1 ≤ z ≤ q − 1 definiere:
• Signierung: sign(k, x, z) = (γ, δ), wobei
. γ = (αz mod p) mod q und
. δ = (x + aγ)z −1 mod q.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
131 / 138
Digitale Signaturen
Digital Signature Algorithm (DSA)
Definition von DSA (Forts.)
• Verifikation: Für x ∈ Z∗p und γ, δ ∈ Zq werden die folgenden
Berechnungen durchgeführt:
. e1 = xδ−1 (mod q)
. e2 = γδ−1 (mod q)
ver(k, (x, γ, δ)) = true genau dann, wenn
(αe1 βe2 mod p) mod q = γ
(p, q, α, β) ist der öffentliche und a der geheime Schlüssel.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
132 / 138
Digitale Signaturen
Digital Signature Algorithm (DSA)
Generierung der DSA Parameter
Zur Erstellung des DSA Schlüssels führt Alice die folgenden Schritte
aus:
1. Wähle eine Primzahl q mit 2159 ≤ q ≤ 2160 .
2. Wähle eine Zahl t mit 0 ≤ t ≤ 8 und eine Primzahl
2511+64t < p < 2512+64t mit der Eigenschaft, daß q die Zahl
(p − 1) teilt.
3. Wähle ein g ∈ Z∗p und berechne α = g (p−1)/q mod p. Wiederhole
diesen Vorgang solange, bis α 6= 1.
4. Wähle eine Zufallszahl a mit 1 ≤ a ≤ q − 1.
5. Berechne β = αa mod p.
Anschließend veröffentlicht Alice den öffentlichen Schlüssel
(p, q, α, β).
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
133 / 138
Digitale Signaturen
Digital Signature Algorithm (DSA)
Beispiel zu DSA
Angenommen, q = 101 und p = 78q + 1 = 7879. Die Zahl 3 ist ein
Generator von Z7879 . Wir wählen daher
α = 378 mod 7879 = 170.
Der geheime Teil des Schlüssels ist a = 75. Somit ist
β = αa mod 7879 = 17075 mod 7879 = 4567.
Bob will die Nachricht x = 1234 signieren. Hierzu zieht er die
Zufallszahl z = 50 und berechnet z −1 mod 101 = 99.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
134 / 138
Digitale Signaturen
Digital Signature Algorithm (DSA)
Beispiel zu DSA (Forts.)
Anschließend berechnet er die Signatur:
γ =
=
δ =
=
(17050 mod 7879) mod 101
2518 mod 101 = 94
(1234 + 75 × 94) × 99 mod 101
97
Die Signatur (94, 97) der Nachricht 1234 wird wie folgt verifiziert:
δ−1 = 97−1 mod 101 = 25
e1 = 1234 × 25 mod 101 = 45
e2 = 94 × 25 mod 101 = 27
Somit (17045 456727 mod 7879) mod 101 = 2518 mod 101 = 94.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
135 / 138
Zusammenfassung
Vorteile von Public Key Kryptosystemen
Vorteile von Public Key Kryptosystemen
• Nur der private Schlüssel muss geheimgehalten werden.
• Der öffentliche Schlüssel ist für jedermann verfügbar.
• Abhängig von der Art der Nutzung bleibt das Schlüsselpaar über
lange Zeit unverändert.
• Aus Public Key Kryptosystemen lassen sich effiziente
Signaturmechanismen ableiten.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
136 / 138
Zusammenfassung
Nachteile von Public Key Kryptosystemen
Nachteile von Public Key Kryptosystemen
• Der Datendurchsatz ist bei Public Key Kryptosystemen in der
Regel deutlich niedriger als bei Symmetrischen Kryptosystemen.
• Für Public Key Kryptografie werden längere Schlüssel benötigt
als für symmetrische Kryptografie.
• Für keines der Public Key Kryptosysteme konnte die Sicherheit
bewiesen werden.
• Alle Public Key Kryptosysteme basieren auf einer Handvoll
mathematischer Probleme.
• Public Key Kryptosysteme gibt es erst seit den 1970er Jahren.
Sie sind daher relativ unerforscht.
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
137 / 138
Zusammenfassung
Zusammenfassung
• Public Key Kryptosysteme lösen eine Vielzahl kryptografischer
Fragestellungen, die man mit symmetrischen Systemen nicht
lösen kann
• Public Key Kryptosysteme basieren auf einer kleinen Auswahl
von zahlentheoretischen Problemen
• Für keines der obigen Kryptosysteme konnte die Sicherheit
bewiesen werden
• Die in Public Key Kryptosystemen eingesetzten Techniken
werden auch für die Entwicklung von kryptografischen
Protokollen eingesetzt
Prof. Dr. C. Karg (HS Aalen)
Kryptografische Algorithmen
Public Key Kryptosysteme
138 / 138

Download Report