Kryptologie (Vorlesung 10)

Skript-Anfang	Skript – Seite 36
Skript-Ende	Skript – Seite 37

Wiederholung

• Diskretes Logarithmusproblem (Siehe Mitschrift vom 04.06.2011)
• Symmetrische Schlüssel zum Erreichen des gleichen Sicherheitsniveaus sind kürzer als asymmetrische Schlüssel

Beispiele für Gruppen zum DL

• ℤ_p^* = {1, … , p-1}

Eigenschaften

• Zyklisch:
  • Es gibt ein g ∈ ℤ_p^* mit {1, … , p-1} = {gⁿ, n ∈ ℕ}
  • Gruppe ℤ₅^* = {1, 2, 3, 4}
  • 3 ist ein Erzeuger (Das Verfahren zum Herausfinden folgt später)
  • 4 ist kein Erzeuger (Nicht jede Zahl in der Gruppe ist auch ein Erzeuger für diese Gruppe)
  • Ist g ∈ ℤ_p* ein Erzeuger, dann existiert für alle h ∈ ℤ_p^* ein x ∈ ℕ mit g^x = h
  • Dies bedeutet, dass log_gh = x existiert
• Daran lassen sich dann Schlüssel ableiten, z.B. für Secure Messaging (verschlüsselte und authentisierte Kommunikation)
  • K_E = Hashwert H (g^xy || 0x00) Verschlüsselungsschlüssel
  • K_E = Hashwert H (g^xy || 0x01) Schlüssel für Authentisierung

Angriff

• Angreifer kennt g, g^x, g^y
• Ziel ist es das gemeinsame Geheimnis g^xy heraus zu finden
• Derzeitig einzige Möglichkeit:
  • Bestimme x oder y, d.h. berechne log_g(g^x) = y oder log_g(g^y) = x
• Erster Ansatz über Probepotenzieren (Brute Force):
  1. Wähle x‘, berechne g^x‘ und vergleiche mit g^x‘ = gx
  2. Für p > 2¹⁰⁰ ist |ℤ_p*| > 2¹⁰⁰
  3. D.h. Wahrscheinlichkeit für Gleichheit kleiner als 2^-100 bzw. 1/2¹⁰⁰
  4. Man braucht also ca. 2¹⁰⁰ Versuche x zu finden (Sicherheitsniveau ist 100 Bit)
  5. Schnellster Algorithmus für das DLP (Diskretes Logarithmusproblem) O(e^{sqrt(log₁₀(p) * log₁₀(log₁₀p))})
  6. p ≈ 2⁴⁰⁰⁰ gilt log₁₀(2⁴⁰⁰⁰) ≈ 1200
  7. log₁₀(log₁₀ (2⁴⁰⁰⁰) ≈ 3
  8. sqrt(1200*3) = e⁶⁰ = 2⁹⁰

Erfolgreicher Angriff – Man in the middle

• Also: Das Verfahren muss mit Instanzauthentisierung einher gehen, um g^x / g^y den Kommunikationspartner zuordnen zu können

Secret Sharing

• Ziel: Durchsetzung eines Mehr-Augen-Prinzips
• Aufteilen eines Geheimnisses K (z.B. kryptographischer Schlüssel) in n Teilgeheimnisse so, dass
• t ≤ n Teilgeheimnisse notwendig sind um K zu erhalten
• t-1 Teile aber keinerlei Informationen über K liefern

(t, n) – Schwellwert – Schema

• (4,10) = Ich brauche 4 von 10 Teilen

Einfaches und unsicheres Verfahren:

• 128 bit Schlüssel in z.B. 4 Teile aufteilen
• K = {K₁, … , K₂₂ , … , K₁₂₈}
• K₁ bis K₂2 = Teilschlüssel 1, usw.
• Mit 3 Teilen des Schlüssels ließen sich z.B. schon 96 Bit wieder herstellen, d.h. es werden Informationen über K geliefert

Einfaches und sicheres Verfahren

1. Wähle zufällig n-1 Werte TK₁, … , TK_n-1 = {0,1}¹²⁸
2. Setze T,K_n = TK₁ ⊕ … ⊕ TK_n-1 ⊕ K
3. Dann gilt TK₁ ⊕ … ⊕ TK_n = K
4. Kennt man weniger als n Teilgeheimnisse erhält man keine Informationen über den Schlüssel K
5. Vergleichbar zum One-time-pad

Shamirs Secret Sharing (RSA) – (t,n)

• Idee: Verstecke K in einem Polyom
• Betrachte k ∈ {0,1}¹²⁸ als natürliche Zahl \( k = \sum_{i=1}^{128} * K_i * 2^{i-1}\)
• Wähle k-1 zufällig Werte a₁, … , a_t-1
• Betrachte f(x) = K + a₁ x¹ + a₂x² + … + a_t-1 x^t-1
• Dann gilt f(0) = K
• Erzeugen der Geheimnisse:
  • Pers 1 → (1,f(1))
  • Pers 2 → (2,f(2))
  • …
  • Pers n → (n,f(n))
• Lösche a₁ bis a_t-1
• Rekonstruktion des Polynoms:
  • Fundamentalsatz der Algebra: Polynom (t-1) Grades wird durch t Punkte (x_i, f(x_i)) ist eindeutig festgelegt
  • Es werden also t der n zuvor berechneten Werte benötigt
  • \( f(x) = \sum_{i=1}^{t}f(x_i) * \prod_{j=1 \wedge y\neq i }^{t}\frac{x-x_j}{x_i-x_j} \) (Lagrange-Formel)
  Sicherheit
  • t-1 (und weniger) Teile liefern keinerlei Informationen über k
  • Angreifer kennt t-1 Werte (1,f(1)) , … , (t-1, f(t-1))
  • \( K=f(0)=\sum_{i=1}^{t}f(i)*\prod_{j=1 \wedge j\neq i}^{t}\frac{0-j}{i-j} \)
  • \( K=f(0)=\sum_{i=1}^{t-1}f(i)*\prod_{j=1 \wedge j\neq i}^{t-1}\frac{0-j}{i-j} + f(t)*\prod_{j=1 \wedge j\neq i}^{t}\frac{0-j}{t-j} \)
  • Nur f(t) ist nicht bekannt
  • f(t) kann alle möglichen Werte annehmen, damit auch f(0) = K
  • D.h. Angreifer hat keinerlei Informationen über K