Einstieg · Ein Bit
Eve fängt ein Bit ab. Was weiß sie danach?
Die Hafenbehörde meldet dem Lotsen jeden Morgen ein Bit: m = 1 heißt „Tanker läuft heute ein“, m = 0 heißt „nicht“. Aus alten Fahrplänen weiß Eve: An 80 % der Tage ist m = 1.
Verschlüsselt wird mit einem Schlüsselbit k aus einem fairen Münzwurf, jeden Tag neu: c = m ⊕ k. Heute fängt Eve c = 1 ab.
Wie wahrscheinlich ist für Eve jetzt, dass heute ein Tanker kommt (m = 1)?
80 % – genau so viel wie vorher. Zu c = 1 passen m = 1 mit k = 0 und m = 0 mit k = 1, beide Schlüssel sind gleich wahrscheinlich. Der Geheimtext ändert Eves Wissen nicht. Ihr Vorwissen (80 %) bleibt ihr aber.
Wie beschreibt man „Eve lernt nichts“ mathematisch, und bleibt das so, wenn die Münze nicht fair ist?
Station 1 · Vernam-Verfahren
Klartext ⊕ Schlüssel, Bit für Bit
Auftrag: Tippt ein Wort. Begründet algebraisch, warum Bob mit demselben Schlüssel zurückkommt: (m ⊕ k) ⊕ k = ?
XOR (⊕) = Addition modulo 2
(m ⊕ k) ⊕ k = m ⊕ (k ⊕ k) = m ⊕ 0 = m
Assoziativität, k ⊕ k = 0, 0 ist neutral. Ver- und Entschlüsseln sind dieselbe Operation.
Gilbert Vernam verknüpfte 1917 so die Lochstreifen von Fernschreibern (Patent 1919). Mit echt zufälligem Schlüssel, der nur einmal benutzt wird, heißt das Verfahren One-Time-Pad. Der Schlüssel hier kommt aus crypto.getRandomValues.
Station 2 · Shannons Definition
Perfekt sicher heißt: Vorher = nachher
Auftrag: Sagt erst voraus, was bei unfairer Münze passiert. Dann stellt q ein und lest Eves Wissen nach dem Abfangen ab.
Für alle m, c mit P(C = c) > 0:
P(M = m | C = c) = P(M = m)
Claude Shannon, 1949: Der abgefangene Geheimtext ändert die Wahrscheinlichkeit keines Klartexts. M, K, C sind Zufallsgrößen; K ist unabhängig von M.
| C = 0 | C = 1 | Summe |
|---|
Eves Wissen über M = 1
Satz von Bayes. Bei q = ½ kürzt sich der Schlüssel heraus: p·½ / (p·½ + (1−p)·½) = p.
Station 3 · Satz und Beweis
Das One-Time-Pad mit n Bit ist perfekt sicher
Auftrag: Deckt Schritt für Schritt auf. Begründet vor jedem Klick, warum der nächste Schritt gilt.
Satz: Ist K gleichverteilt auf {0,1}n und unabhängig von M, und ist C = M ⊕ K, dann gilt P(M = m | C = c) = P(M = m).
Zu festem m und c gibt es genau einen Schlüssel mit m ⊕ k = c, nämlich k = m ⊕ c.
XOR mit m ist umkehrbar (Station 1).
P(C = c | M = m) = P(K = m ⊕ c | M = m) = P(K = m ⊕ c) = 2−n
Erst Schritt 1, dann Unabhängigkeit von K und M, dann Gleichverteilung. Das Ergebnis hängt nicht von m ab.
P(C = c) = Σm′ P(C = c | M = m′) · P(M = m′) = 2−n · Σm′ P(M = m′) = 2−n
Totale Wahrscheinlichkeit (Summe über m′ mit P(M = m′) > 0). Jeder Geheimtext ist gleich wahrscheinlich, egal wie M verteilt ist.
P(M = m | C = c) = P(C = c | M = m) · P(M = m) / P(C = c) = 2−n · P(M = m) / 2−n = P(M = m) ∎
Satz von Bayes mit Schritt 2 und 3.
Wo bricht der Beweis bei zweimal benutztem Schlüssel? In Schritt 2: Wer c₁ kennt, für den ist K = M₁ ⊕ c₁ nicht mehr unabhängig vom Klartext (Station 5).
Station 4 · Shannons Schranke
Geht es auch mit kürzerem Schlüssel?
Auftrag: 3-Bit-Nachrichten, ein ℓ-Bit-Schlüssel wird wiederholt (wie bei Vigenère). Welche Klartexte kann Eve ausschließen?
Allgemein (Zählargument)
Zu festem c liefert jeder Schlüssel höchstens einen Klartext. Also passen höchstens |K| Klartexte zu c.
Ist |K| < |M|, bleibt ein Klartext m übrig mit P(M=m | C=c) = 0, obwohl P(M=m) > 0 sein kann. Dann ist das Verfahren nicht perfekt sicher.
Perfekte Sicherheit ⇒ |K| ≥ |M|
|M| zählt die Nachrichten mit P > 0. Bei n-Bit-Nachrichten: mindestens 2n Schlüssel, also mindestens n Bit Schlüssel pro Nachricht. Das gilt für jedes Verfahren, nicht nur für XOR.
Station 5 · Two-Time-Pad
Ein Schlüssel, zwei Nachrichten
Auftrag: Eve kennt c₁ ⊕ c₂ = m₁ ⊕ m₂. Legt ein vermutetes Wort an: Wo wird der andere Text lesbar?
ASCII: Großbuchstaben sind 010xxxxx, das Leerzeichen 00100000. Buchstabe ⊕ Buchstabe gibt ein Steuerzeichen (·), Buchstabe ⊕ Leerzeichen einen Kleinbuchstaben. Dort hat ein Text eine Lücke, der andere diesen Buchstaben.
Venona: Sowjetische Stellen druckten 1942 Schlüsselseiten doppelt. Das US-Programm Venona (ab 1943) las dadurch rund 3000 Funksprüche zumindest teilweise.
Station 6 · Vertraulichkeit ist nicht Integrität
Eve ändert den Betrag, ohne den Schlüssel zu kennen
Auftrag: Eve kennt das Format des Auftrags und vermutet den üblichen Betrag 0100. Wählt einen neuen Betrag und lasst Eve eingreifen. Ist das One-Time-Pad damit gebrochen?
Δ = „0100“ ⊕ „9100“ an den Stellen des Betrags, sonst 0. Dann gilt c′ ⊕ k = m ⊕ Δ.
Die Vertraulichkeit hält: Was Eve über den Betrag weiß, wusste sie vorher. Die Integrität fehlt: Bob merkt die Änderung nicht. Das One-Time-Pad verspricht nur Vertraulichkeit.
Abhilfe: zusätzlich ein Prüfwert mit eigenem Schlüssel (MAC). Heutige Verfahren verbinden beides, etwa AES-GCM oder ChaCha20-Poly1305 in TLS 1.3.
Station 7 · Vom One-Time-Pad zur Stromchiffre
Den Schlüsselstrom aus einem Startwert berechnen
Auftrag: Ein Spielzeug-Generator macht aus einem 16-Bit-Startwert den Schlüsselstrom. Eve vermutet „MOIN“ am Anfang. Schätzt erst die Rechenzeit.
xi+1 = (25173 · xi + 13849) mod 216
Schlüsselbyte = oberes Byte von xi+1
Mit nur zwei bekannten Bytes passen bei diesem Generator meist zwei Startwerte; vier Bytes legen ihn fest.
Alle Schlüssel probieren, angenommen 1018 Versuche pro Sekunde
| Schlüssel | Anzahl | Dauer |
|---|---|---|
| 16 Bit | 65 536 | unmessbar kurz |
| 64 Bit | 1,8 · 1019 | rund 18 s |
| 128 Bit | 3,4 · 1038 | rund 1,1 · 1013 Jahre |
| 256 Bit | 1,2 · 1077 | rund 3,7 · 1051 Jahre |
Eine Stromchiffre ist nicht perfekt, sondern berechenbar sicher: Knacken geht, dauert nach heutigem Wissen aber viel zu lange. Beispiele: ChaCha20 (256 Bit), AES im Zählermodus. Jede Nachricht braucht eine neue Nonce, sonst droht Station 5.
Station 8 · Sicherheit beurteilen
Perfekt, berechenbar sicher oder gebrochen?
Auftrag: Prüft echt zufällig · so lang wie die Nachricht · nur einmal · geheim. Erst begründen, dann aufdecken.
A · „OTP-App“: Eine App erzeugt den Schlüssel so lang wie die Nachricht mit Math.random().
Nicht perfekt sicher. Math.random() berechnet Pseudozufall aus einem inneren Zustand und ist nicht für Kryptographie gedacht: in Wahrheit eine schwache Stromchiffre.
B · Heißer Draht ab 1963: Fernschreiber Washington–Moskau. Jede Seite liefert der anderen Schlüsselbänder per Kurier über die Botschaften.
Perfekt sicher möglich, wenn die Bänder echt zufällig sind, nur einmal laufen und geheim bleiben. Preis: Logistik der Schlüsselverteilung.
C · Messenger: AES-256-GCM, Schlüssel per Diffie-Hellman ausgehandelt, für jede Sitzung neu.
Berechenbar sicher, nicht perfekt: 256 Bit für viel mehr Daten verletzt Shannons Schranke. Dafür kein Kurier, und GCM prüft die Integrität.
D · Gigabyte-Schlüssel: 1 GB echter Zufall auf einem USB-Stick. Jede neue Nachricht wird wieder ab dem ersten Byte verschlüsselt.
Gebrochen durch Mehrfachnutzung: c₁ ⊕ c₂ = m₁ ⊕ m₂ (Station 5). Verbrauchte Bytes nie wieder verwenden.
Abschluss · Teil 1
Check
Auftrag: Entscheidet euch zuerst, dann auflösen.
„Das One-Time-Pad ist perfekt sicher.“ Was bedeutet das genau?
Raten mit Vorwissen bleibt möglich (Einstieg: 80 %). „In absehbarer Zeit“ beschreibt berechenbare Sicherheit.
Nachrichten haben 128 Bit, der Schlüssel echt zufällige 127 Bit, sonst wie beim One-Time-Pad. Was folgt?
2127 Schlüssel liefern zu festem c höchstens 2127 von 2128 Klartexten (Station 4). Den Klartext findet Eve trotzdem praktisch nicht.
Abschluss · Teil 2
Check
Auftrag: Entscheidet euch zuerst, dann auflösen.
Eve kippt im Geheimtext c das erste Bit. Was liest Bob?
(c ⊕ Δ) ⊕ k = m ⊕ Δ. Ohne Prüfwert merkt Bob nichts (Station 6).
Warum ist ChaCha20 kein One-Time-Pad, obwohl es den Klartext mit einem Schlüsselstrom XOR-verknüpft?
256 Bit Schlüssel für beliebig viele Daten verletzen Shannons Schranke: berechenbar sicher statt perfekt sicher (Station 7). Weiter mit Schlüsselaustausch und RSA.