Kryptologie (Vorlesung 2)

Skript-Anfang	Skript – Seite 7
Skript-Ende	Skript – Seite 11

CAECAR

• 2 Tabellen übereinander legen und Buchstaben-Paare aus Klar und Geheim verbinden
• Kerckhoff-Prinzip
• 26 Schlüssel existieren (=Schlüsselraum)

Erweiterter CAECAR (Bsp. 1.10)

• Beliebiges Ersetzen von Buchstaben vergößert den Schlüsselraum
• Siehe auch Abbildung Seite 8
• CAECAR = z.B.: QDSQDZ
• Anzahl der Schlüssel
  • 1. Buchstabe kann durch 26 mögliche Buchstaben ersetzt werden
  • 2. Buchstabe kann durch 25 mögliche Buchstaben ersetzt werden
  • ..
  • 26. Buchstabe kann durch 1 möglichen Buchstaben ersetzt werden
  • = 26! bzw. 2⁸⁸ mögliche Schlüssel (1*2*3*..*24*25*26 = 403.291.461.126.605.635.584.000.000)
• Möglicher Angriff über die relative Häufigkeit von Buchstaben in sinnvollen deutschen Texten

Angriffsverfahren – Relative Häufigkeit von Buchstaben

• Die relativen Häufigkeiten werden beim Chiffrieren übernommen, z.B.: E → S
• S kommt im Chiffretext genauso häufig vor wie E im Klartext
• Welcher Buchstabe kommt am häufigsten vor? (ursprünglich E)
• Welcher Buchstabe kommt am zweithäufigsten vor? (ursprünglich N)
• Durch geschicktes Betrachten des Textes können die Buchstaben fortlaufend entziffert werden
• Auch das Austauschen von Leerzeichen und Satzzeichen kann über das Verfahren dechiffriert werden
• Solche Angriffe werden auch statistische Angriffe genannt
• Siehe auch Tabelle auf Seite 9

Weitere Ansätze

• Jedes x-te E durch einen anderen Buchstaben ersetzen (Enigma)
• Buchstaben auffüllen nach bestimmten Raster (einfügen an Positonen 1, 3, 5, .. , etc.)
• Ersetzen von Buchstabenpaaren

Buchstabenpaare ersetzen

• AB → XZ
• AA → ZT
• Nicht sicher! → Brechen über Bigrammhäufigkeit (en, ss, ch, tr)

Sicheres Verschlüsselungsverfahren (Bsp 1.11)

• Klartexte sind Bitstrings x=(x₁, … , x_n) ∈ {0,1}ⁿ
• Kodierung über ASCII-Code
  • A = 01000001
  • B = 01000010
  • C = 01000011
• Schlüssel (k₁, … , k_n) ∈ {0, 1}ⁿ
• Verschlüsselungsfunktion: F = {0, 1}ⁿ x {0, 1}ⁿ → {0, 1}ⁿ; (x, k) → x ⊕ k
• ⊕ ist die komponentenweise Addition modulo Z
• (x₁ , … , x_n) ⊕ (k₁ , … , k_n) = (x₁ ⊕ k₁ , … , x_n ⊕ k_n)
  • 0 ⊕ 0 = 0
  • (1 ⊕ 0) = (0 ⊕ 1) = 1
  • 1 ⊕ 1 = 0
  • XOR
• Absolut sicher → nicht knackbar mit endlichen Ressourcen

Sicherheitsdiskussion

• Angreifer kennt Chiffretext
• y = (y₁, … , y_n)
• Ziel des Angreifers ist die Rekonstruktion des Klartextes (ohne Kenntnis des Schlüssels)

Verfahren

• Schlüssel k = (k₁ , … , k_n)
• Schlüssel ist zufällig gewählt, d.h. für alle ? ? ? gilt Pr(x ⊕ k = y) = (1/2)ⁿ
• Länge von Schlüssel und des Text sind gleich lang
• Für x_i = 0 → Pr(y_i = 0)
  • x_i ⊕ k_i
  • 0 ⊕ k_i
  • = Pr(k_i=0) = 1/2
• Für x_i = 1 → Pr(y_i = 0)
  • x_i ⊕ k_i
  • 1 ⊕ k_i
• → Pr(y_i = 0) = 1/2
• → Pr(y_i = 1) = 1/2
• unabhängig von x_i

Vorteile/Merkmale

• unabhängig von x_i → y enthält keinerlei Informationen über x
• Im informationstechnischen Sinne bedeutet dies Absolut sicheres Verschlüsselungsverfahren
• Selbst ein Angreifer mit unbeschränkten Ressourcen (Ressourcenkapazität und Zeit) kann den Klartext nicht ermitteln

Nachteile

• Idee: Den selben Schlüssel für alle Texte nutzen
• Dann gilt:
  • y¹ ⊕ y² = (x¹ ⊕ k) ⊕ (x² ⊕ k) = x¹ ⊕ x²
  • y² ⊕ y³ = x² ⊕ x³
  • y¹ ⊕ y³ = x¹ ⊕ x³
• Je mehr Texte mit dem selben Schlüssel verschlüsselt sind, desto schneller/einfacher wird das Verfahren geknackt

Angriff:

• Ermittle alle sinnvollen Zeichenkombinationen für x¹
• Wähle eine aus (Annahme/Raten, diese ist der ursprüngliche Klartext)
• Berechne x² = x¹ ⊕ x² ⊕ x¹
• Berechne x³ = s.o.
• Prüfe, ob x² und x³ sinnvolle Kombinationen sind
• Man muss den Schlüssel nicht identifizieren, wir rechnen mittels XOR die Texte gegeneinander und prüfen, ob sinnvolle Texte dabei entstehen.

Ergebnis C.E. Shannon (1948)

• siehe Satz 1.2

Wie messen wir Sicherheit?

• Sicherheitsniveau von n Bit heißt, ein Angreifer benötigt 2ⁿ Versuche um das Verfahren zu brechen
  • Durchsuchen des Schlüsselraums
  • Anwendung anderer kryptographischer Methoden
• Heute gefordertes Sicherheitsniveau = 128 bit (also insbesonders Schlüssellänge = 128 bit)
• Sicherheit hängt primär von der Stärke des Algorithmus ab
• Auch zu berücksichtigen
  • konkrete Implementation des Algorithmus
  • Hintergrundsysteme (z.B.: Zuordnung der Schlüssel zu Personen, Sicherung der Schlüssel)