Kryptologie (Vorlesung 5)

Skript-Anfang	Skript – Seite 19
Skript-Ende	Skript – Seite 23

Wiederholung

• Z_n = {0 , … , n-1}
• Z_n^* = Menge der multiplikativ inversen Elemente in Z_n
• a ∈ Z_n ist genau dann mult. invertierbar in Z_n, wenn a und n T eilerfremd sind, d.h. ggt(a,n)=1
• Z₁₀^* = {1,3,7,9}
  • 1*1 = 1 mod 10
  • 3*7 = 21 mod 10 = 1
  • 9*9 = 81 mod 10 = 1
• Ist p eine Primzahl, dann ist Z_p^* = {1 , … , p-1}
• Sind p und q Primzahlen, dann |Z_p*q^*| = (p-1)(q-1)
• Eulerzahl: Für n=p*q ist φ(n) =|Z_n^*| = (p-1)(q-1)
• Siehe Satz 3.2
• Siehe Lemma 3.3
• (Z_n*;) ist eine absolute Gruppe. Weiter |Z_n^*| = φ(n)
• Also: Sind a und n teilerfremd, dann gilt a ∈ Z_n^*
• Weiter gilt a^|Z_n*| = 1 = a^φ(n)

Beweis von Lemma 3.3

• bijektiv:
  • Sei g ∈ G, dann gilt f_g : G -> G; x |-> gx
• injektiv:
  • Aus f_g(x) = f_g(x‘) folgt x=x‘.
  • Aus f_g(x) = f_g(x‘) folgt g*x = g*x‘
  • Also g^-1 *g *x = g^-1*g*x‘
  • Also x=x‘
• surjektiv:
  • für alle y ∈ G existiert x ∈ G mit f_g(x)= y
  • Sei y ∈ G und x = g^-1*y dann gilt f_g(x) = g*x = g(g^-1*y) = y
  • Also ist f_g bijektiv
  • ∏_{h ∈ G}h
  • = ∏_{h ∈ G}f_g(h)
  • = ∏_{h ∈ G} g*h
  • = g^|G| * ∏_{h ∈ G} h
  • Also g^|G| = 1

p*q Primzahlen

• n=p*q
• φ(n) = |Z_n^*| = (p-1)(q-1)
• Siehe Kleiner Satz von Fermat
• Siehe Seite 20 – Schlüsselgenerierung
• Angreifer kann (n,d) nicht berechnen, da er die Primzahlen p und q nicht kennt

Beispiel

Auswahl

• p = 5
• q = 11
• n = 55
• φ(n)=40
• Kandidaten für e: 3,7,9 ..
• e = 7
• d = 23
• 7*23 = 161 = 1 mod 40

RSA Modul

• Public Key = (55,7)
• Private Key = (55,23)
• Nachricht = m = 3
• C = m^e = 3⁷ = 2187 = 42 mod 55
• Entschlüsselung des Ciphertextes 42
• Berechne c^d = 42²³

Binäre Exponentiation ( square and multiply)

• 23 = 1 * 2⁴ + 0 * 2³ + 1 * 2² + 1 * 2¹ + 1 * 2⁰
• 23 = ((2 * 2+1)2 * 1) * 2+1
• Also 42²³ = (((42²)² * 42)² * 42)² * 42

Berechnung

• 42² = 1764 = 4 mod 55
• 4²=16
• 16 * 42 = 672 = 12 mod 55
• 12² = 144 = 34 mod 55
• 34 * 42 = 1428 = 53 mod 55
• 53² = 2809
• 4 mod 55
• 4 * 42 = 168 = 3 mod 55

Beweisskizze

• Siehe Satz 3.4

Sicherheitsbewertung des RSA-Verfahrens

• Nicht nur Durchprobieren aller Schlüssel
• Alle kryptoanalytischen Methoden müssen herangezogen werden
• Wir fordern Sicherheitsniveau von 100 Bit (2¹⁰⁰ Versuche sind nötig zum Durchprobieren)
• Ziel: Gesucht ist die untere Schranke für die Schlüssellänge

Aufgabe

1. Gegeben: öffentlicher Schlüssel (n,e) und c = m^e mod n. Berechne m
2. Gegeben: öffentlicher Schlüssel (n,e). Berechne d mit e*d = 1 mod phi(n)
3. Gegeben: Modul n = p*q. Berechne p und q

Probleme

• Wenn Problem 3 lösbar ist, dann ist Problem 2 lösbar (weil p und q bekannt) und dann ist Problem 1 lösbar
• Sind die Probleme äquivalent, d.h. Problem 1 lösbar -> Problem 2 lösbar -> Problem 3 lösbar?
• Bekannt: Problem 2 und 3 sind ca. gleich schwer
• Nicht bekannt: Ob die Probleme 1 und 2 äquivalent sind
• D.h. die Entschlüsselung könnte leichter sein als d zu berechnen
• Wenn man faktorisieren kann, dann ist RSA gebrochen
• Also: Sicherheit des RSA-Verfahrens beruht auf der vermuteten Schwierigkeit des Faktorisierens ganzer Zahlen
• Wie schnell arbeitet der derzeit schnellste Faktorisierungsalgorithmus?
• Laufzeit = O(e^{sqrt(lnn*ln(lnn))} )
• Für n ≈ 2 ²⁰⁴⁸ hat der Algorithmus eine Laufzeit von 2^100