Upload
ercanbald-streif
View
104
Download
0
Embed Size (px)
Citation preview
Einwegfunktionen mit und ohne „Falltür“
Technisches Seminar 2012
von Bjarne Adam
Gliederung
1. Einführung – Was sind Einwegfunktionen
2. Einwegfunktion ohne Falltür
- Hashalgorithmus
3. Zahlentheorie
4. Diffie-Hellman Schlüsselaustausch Protokoll
5. Einwegfunktion mit Falltür
- RSA
Eine Funktion f(x) lässt sich „leicht“ berechnen!
Die Umkehrfunktion f‾¹(x) lässt nicht bzw. nur sehr „schwer“ berechnen!
Was heißt leicht oder schwer berechnen?
1. EinführungWas sind Einwegfunktionen?
leicht:
Algorithmus der in Polynomialzeit den Funktionswert von f(x) lösen kann:
Ơ(nk) -> k konstant!
schwer:
kein Algorithmus der in Polynomialzeit f‾¹(x) bei bekanntem Funktionswert y lösen kann:
Ơ(2n) -> exponentiell wachsend!
1. EinführungWas sind Einwegfunktionen?
1. EinführungWas sind Einwegfunktionen?
Diskretes Logarithmus Problem
- Diffie-Hellman-Protokoll
- ElGamal Verschlüsselung
- Eleptic Curve Diffie-Hellman
Faktorisierung eines Produktes großer Primzahlen
- RSA
1. EinführungWas sind Einwegfunktionen?
Einwegfunktionen mit Falltür (One-Way-Trapdoor)
Effiziente Umkehrung der Funktion durch Besitz einer Zusatzinformation (Falltür).
Beispiel: Briefkasten
Gliederung
1. Einführung – Was sind Einwegfunktionen
2. Einwegfunktion ohne Falltür
- Hashalgorithmus
3. Zahlentheorie
4. Diffie-Hellman Schlüsselaustausch Protokoll
5. Einwegfunktion mit Falltür
- RSA
2. Einwegfunktion ohne Falltür Hashalgorithmus
Abbildung eines beliebig langen Klartext auf einen Hashwert fester länge.
Ziel: - einzigartiger Fingerabdruck (Fingerprint)- keine Umkehrung von Hashwert auf Klartext
Hashwert ist Hexadezimal
2. Einwegfunktion ohne Falltür Hashalgorithmus - Anforderungen
KollisionsresistentKompressionChaosSurjektivitätEffizienz
Preimage resistantSecond Preimage resistant
2. Einwegfunktion ohne Falltür Hashalgorithmus – Ablauf
Merkle-Demgard-Verfahren
PaddingTrennenKompressionTransformation (optional)
2. Einwegfunktion ohne Falltür Hashalgorithmus – Ablauf
Sha-1 Hashfunktion
2. Einwegfunktion ohne Falltür Hashalgorithmus - Anwendung
Signierung von Daten:Wurde der Inhalt manipuliert?
Prüfsummen:Wurden Daten fehlerfrei übertragen?
Identifikation größerer Datenmengen mit Hashwert:Identifikation von Inhalten in Peer-to-Peer-Tauschbörsen
Passwortschutz bei InternetseiteSpeicherung des Hashwert, nicht des Klartextes
Gliederung
1. Einführung – Was sind Einwegfunktionen
2. Einwegfunktion ohne Falltür
- Hashalgorithmus
3. Zahlentheorie
4. Diffie-Hellman Schlüsselaustausch Protokoll
5. Einwegfunktion mit Falltür
- RSA
Anzahl der Teilerfremden ganzen Zahlen einer Zahl n für alle ganzen Zahlen 1 bis n.
Wenn n = prim, dann gilt: φ( n ) = n – 1
Wenn n das Produkt zweier verschiedener Primzahlen ist, dann gilt:
φ( p * q ) = (p – 1) * (q – 1)
φ( 8 ) = 4 : { 1, 3, 5, 7 }
φ( 11 ) = 10 : { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
3. Zahlentheorie Eulersche-Phi-Funktion
Berechnung ℤ7*:
Zeilen*Spalte % n
Ordnung:
φ( n ) = φ( 7 ) = 6
3. Zahlentheorie Prime Restklassengruppen ℤn*
3. Zahlentheorie Primitivwurzeln
Berechnung ℤ7:
Zeilen^Spalten % n
Primitivwurzeln:
φ( φ( n )) = φ( φ( 7 ))
= φ( 6) = 2
Zeile 3 und 5 sind PW!
Gliederung
1. Einführung – Was sind Einwegfunktionen
2. Einwegfunktion ohne Falltür
- Hashalgorithmus
3. Zahlentheorie
4. Diffie-Hellman Schlüsselaustausch Protokoll
5. Einwegfunktion mit Falltür
- RSA
- 1976, Whitefield Diffie und Martin Hellman
- Protokoll zur Schlüsselvereinbarung
- Sichere Schlüsselvereinbarung über unsicheren Kanal
- Diskretes Logarithmus Problem
4. Diffie-Hellman-Verfahren Schlüsselvereinbarung
p = große Primzahlg = Primitivwurzel von px = Zufallszahl
mod := Division mit Rest
4. Diffie-Hellman-Verfahren Funktion und Aufbau
Exponentialfunktion mit Restbildung
Alice und Bob bestimmen g und p
4. Diffie-Hellman-Verfahren Ablauf
AliceWählt Zufallszahl a (geheim)A = ga mod pA wird Bob zugesendet
S = Ba mod p
BobWählt Zufallszahl b (geheim)B = gb mod pB wird Alice zugesendet
S = Ab mod p
p = 23, g = 17
4. Diffie-Hellman-Verfahren Beispiel
Alice
Zufallszahl a = 4A = ga mod pA = 174 mod 23 = 8
S = Ba mod pS = 74 mod 23 = 9
Bob
Zufallszahl b = 9B = gb mod pB = 179 mod 23 = 7
S = Ab mod p = 9S = 89 mod 23 = 9
Gliederung
1. Einführung – Was sind Einwegfunktionen
2. Einwegfunktion ohne Falltür
- Hashalgorithmus
3. Zahlentheorie
4. Diffie-Hellman Schlüsselaustausch Protokoll
5. Einwegfunktion mit Falltür
- RSA
- 1978, Ronald Linn Rivest, Adi Shamir und Leonard Adleman
- asymmetrische Verschlüsselung
- Faktorisierung eines Produkts großer Primzahlen
5. Einwegfunktion mit Falltür RSA
n = Produkt großer Primzahlenx = zu verschlüsselnde/entschlüsselnde Zahld = öffentlicher / privater Teil von Schlüssel
mod := Division mit Rest
5. Einwegfunktion mit Falltür RSA - Funktion und Aufbau
Exponentialfunktion mit Restbildung
5. Einwegfunktion mit Falltür RSA - Ablauf
Empfänger:- bestimmt Primzahl p und q- n = p*q- φ( n )- bestimmt Zahl e: 1 < e < φ( n ) und teilerfremd zu φ( n ) - bestimmt Zahl d: e*d und φ( n ) teilerfremd
- Öffentliches Zahlenpaar (n,e)
5. Einwegfunktion mit Falltür RSA - Ablauf
Sender:- nimmt öffentliches Zahlenpaar (n,e)- Verschlüsselt Nachricht g = ke % n- Sendet verschlüsselte Nachricht
-Empfänger- Entschlüsselung durch k = gd % n
5. Einwegfunktion mit Falltür RSA - Beispiel: Zahl 14 Ver-/Entschlüsseln
Empfänger:- bestimmt Primzahl p = 5 und q = 11- n = p*q = 55- φ( n ) = 40- bestimmt Zahl e: 1 < e < φ( n ) und teilerfremd zu φ( n )
e = 7- bestimmt Zahl d: e*d und φ( n ) teilerfremd
d = 23- Öffentliches Zahlenpaar (55,7)
5. Einwegfunktion mit Falltür RSA - Beispiel: Zahl 14 Ver-/Entschlüsseln
Sender:- nimmt öffentliches Zahlenpaar (55,7) - Verschlüsselt Nachricht g = 147 % 55 = 9 - Sendet verschlüsselte Nachricht
-Empfänger- Entschlüsselung durch k = 923 % 55 = 14
Schlusswort
Ende
Vielen Dank!