Kryptographie – Wie geheime Nachrichten funktionieren

Einführung

Jedes Mal, wenn du eine Website mit HTTPS aufrufst, eine Bankkarte nutzt oder eine Nachricht in WhatsApp sendest, arbeitet im Hintergrund Mathematik, die deine Daten schützt. Kryptographie ist die Wissenschaft des geheimen Schreibens – und ihre modernen Methoden beruhen nicht auf komplizierten Schlössern, sondern auf eleganten mathematischen Problemen, die leicht zu stellen, aber praktisch unmöglich zu lösen sind.

Grundidee

Das Grundprinzip der Kryptographie ist einfach: Eine Nachricht wird so transformiert, dass nur der berechtigte Empfänger sie rückgängig machen kann. Das gelingt, wenn die Verschlüsselung eine Einwegfunktion nutzt – eine mathematische Operation, die leicht auszuführen, aber schwer umzukehren ist. Das Multiplizieren zweier großer Primzahlen ist solch eine Einwegfunktion: $p \cdot q$ berechnen ist trivial, das Ergebnis wieder in $p$ und $q$ zu zerlegen ist für große Zahlen praktisch unlösbar.

Erklärung

Historische Vorläufer: Caesar-Chiffre

Julius Caesar verschlüsselte Nachrichten, indem er jeden Buchstaben um 3 Positionen im Alphabet verschob:

$A \to D, \quad B \to E, \quad \ldots, \quad Z \to C$

Verschlüsseln: HALLO $\to$ KDOOR Entschlüsseln: zurückverschieben um 3

Die Caesar-Chiffre ist eine monoalphabetische Substitution – leicht zu knacken, weil die Buchstabenhäufigkeit erhalten bleibt. Die Vigenère-Chiffre (16. Jh.) nutzt ein Schlüsselwort und ist schwerer zu brechen.

Mathematisch: Bei Caesar mit Verschiebung $k$ gilt: $c = (m + k) \bmod 26 \qquad m = (c - k) \bmod 26$

Symmetrische Verschlüsselung

Bei der symmetrischen Verschlüsselung benutzen Sender und Empfänger denselben geheimen Schlüssel – sowohl zum Verschlüsseln als auch zum Entschlüsseln.

Vorteil: Sehr schnell (geeignet für große Datenmengen). Problem: Wie tauscht man den Schlüssel aus, ohne dass ein Angreifer ihn abfängt?

Modernes Beispiel: AES (Advanced Encryption Standard) – verwendet für verschlüsselte Festplatten, WLAN.

Asymmetrische Verschlüsselung: Das Briefkasten-Modell

Idee: Jeder hat zwei Schlüssel – einen öffentlichen Schlüssel (darf jeder sehen) und einen privaten Schlüssel (streng geheim).

Analogie: Stell dir einen Briefkasten mit einem offenen Schlitz vor:

• Jeder kann einen Brief einwerfen (verschlüsseln mit dem öffentlichen Schlüssel).
• Nur der Besitzer hat den Schlüssel zum Öffnen des Kastens (entschlüsseln mit dem privaten Schlüssel).

Alice will Bob eine geheime Nachricht schicken:

1. Bob veröffentlicht seinen öffentlichen Schlüssel $e$.
2. Alice verschlüsselt ihre Nachricht $m$ damit: $c = m^e \bmod n$.
3. Nur Bob kann mit seinem privaten Schlüssel $d$ entschlüsseln: $m = c^d \bmod n$.

RSA im Detail

RSA (Rivest–Shamir–Adleman, 1977) funktioniert so:

Schlüsselerzeugung:

1. Wähle zwei große Primzahlen $p$ und $q$.
2. Berechne $n = p \cdot q$ (öffentlich) und $\varphi(n) = (p-1)(q-1)$ (privat).
3. Wähle $e$ mit $\gcd(e, \varphi(n)) = 1$ (z. B. $e = 65537$).
4. Berechne $d = e^{-1} \bmod \varphi(n)$ (privater Schlüssel).

Öffentlicher Schlüssel: $(e, n)$ – Privater Schlüssel: $(d, n)$

Kleines Beispiel: $p = 11$, $q = 13$, $n = 143$, $\varphi(n) = 120$, $e = 7$, $d = 103$.

Verschlüsseln: $c = m^7 \bmod 143$ Entschlüsseln: $m = c^{103} \bmod 143$

Die Sicherheit beruht darauf, dass $n$ aus $p$ und $q$ zu faktorisieren für große Zahlen (1024–4096 Bit) praktisch unmöglich ist.

Diffie-Hellman-Schlüsselaustausch

Diffie und Hellman (1976) lösten das Problem des sicheren Schlüsselaustauschs über einen unsicheren Kanal – mit einer verblüffenden Idee:

Analogie: Alice und Bob einigen sich öffentlich auf eine Farbe (z. B. Gelb). Dann mischen beide ihre geheime Farbe ein (Alice: Blau → Grün; Bob: Rot → Orange). Sie tauschen die gemischten Farben aus. Jetzt mischen beide ihre eigene geheime Farbe zum Austauschpaket dazu – und erhalten beide dieselbe Farbe! Ein Angreifer sieht nur Gelb, Grün und Orange – nicht die geheimen Farben.

Mathematisch: Öffentlich vereinbart: Primzahl $p$ und Basis $g$.

$\text{Alice wählt } a,\ \text{sendet } A = g^a \bmod p$ $\text{Bob wählt } b,\ \text{sendet } B = g^b \bmod p$ $\text{Gemeinsamer Schlüssel: } K = B^a \bmod p = A^b \bmod p = g^{ab} \bmod p$

Die Sicherheit beruht auf dem diskreten Logarithmusproblem: Aus $A = g^a \bmod p$ auf $a$ zu schließen ist für große $p$ praktisch unlösbar.

Digitale Signatur

Die Asymmetrie lässt sich auch umdrehen: Alice signiert eine Nachricht mit ihrem privaten Schlüssel. Jeder kann mit Alices öffentlichem Schlüssel prüfen, ob die Signatur echt ist – aber nur Alice kann sie erstellt haben.

$\text{Signatur: } s = m^d \bmod n \qquad \text{Verifikation: } m' = s^e \bmod n,\ m' \stackrel{?}{=} m$

TLS/HTTPS

Das HTTPS-Protokoll kombiniert beide Welten:

1. Asymmetrisch (RSA oder Diffie-Hellman): sicherer Austausch eines Sitzungsschlüssels.
2. Symmetrisch (AES): schnelle Verschlüsselung aller übertragenen Daten mit dem Sitzungsschlüssel.

Das grüne Schloss zeigt: Der Server hat ein gültiges Zertifikat, das von einer vertrauenswürdigen Stelle digital signiert ist.

Beispiel aus dem Alltag

Online-Banking: Wenn du dich bei deiner Bank einloggst, läuft im Hintergrund ein TLS-Handshake ab. Dein Browser und der Server einigen sich in Millisekunden auf einen Sitzungsschlüssel – dank Diffie-Hellman, ohne dass der Schlüssel übertragen wird. Alle deine Kontodaten sind dann mit AES verschlüsselt.

WhatsApp End-to-End: Jede Nachricht wird mit dem öffentlichen Schlüssel des Empfängers verschlüsselt. WhatsApps Server sehen nur unlesbaren Chiffretext – selbst wenn sie wollten, könnten sie die Nachrichten nicht lesen.

Anwendung

Aufgabe (kleines RSA-Beispiel): Sei $p = 5$, $q = 11$, also $n = 55$ und $\varphi(n) = 40$. Mit $e = 3$ ist $d = ?$ Verschlüssle die Nachricht $m = 2$.

Lösung:

• $d$ muss erfüllen: $3d \equiv 1 \pmod{40}$. Erweiterter euklidischer Algorithmus: $d = 27$ (Probe: $3 \cdot 27 = 81 = 2 \cdot 40 + 1$ ✓).
• Verschlüsseln: $c = 2^3 \bmod 55 = 8 \bmod 55 = 8$
• Entschlüsseln: $m = 8^{27} \bmod 55 = 2$ ✓

Typische Fehler

„Der öffentliche Schlüssel muss geheim gehalten werden.” Nein – er ist absichtlich öffentlich. Nur der private Schlüssel ist geheim. Die Sicherheit liegt nicht im Verstecken des öffentlichen Schlüssels, sondern in der mathematischen Einwegfunktion.

„Symmetrisch ist unsicher, asymmetrisch ist sicher.” Asymmetrisch löst das Schlüsselaustausch-Problem, ist aber viel langsamer. In der Praxis nutzt man immer beides: Asymmetrisch zum Austausch des Schlüssels, symmetrisch für die eigentlichen Daten.

„Caesar ist unknackbar, wenn die Verschiebung unbekannt ist.” Nein – es gibt nur 25 mögliche Verschiebungen. Ein Computer testet alle in Mikrosekunden. Außerdem verrät die Häufigkeitsanalyse den Schlüssel.

Zusammenfassung

Merke dir:

• Symmetrisch: ein Schlüssel für Ver- und Entschlüsselung – schnell, aber Schlüsselaustausch-Problem
• Asymmetrisch: öffentlicher Schlüssel (verschlüsseln/prüfen) + privater Schlüssel (entschlüsseln/signieren)
• RSA: Sicherheit durch Schwierigkeit der Faktorisierung großer Zahlen ($n = p \cdot q$)
• Diffie-Hellman: sicherer Schlüsselaustausch ohne gemeinsamen Kanal, basiert auf diskretem Logarithmus
• Digitale Signatur: privater Schlüssel signiert, öffentlicher Schlüssel verifiziert
• TLS/HTTPS: asymmetrisch für Schlüssel, symmetrisch (AES) für Daten

Quiz

Frage 1: Verschlüssele den Buchstaben M (= 12) mit Caesar-Verschiebung $k = 5$.

Antwort anzeigen

$c = (12 + 5) \bmod 26 = 17$. Buchstabe Nummer 17 ist R. Also wird M zu R verschlüsselt.

Frage 2: Was ist der grundlegende Unterschied zwischen dem öffentlichen und dem privaten Schlüssel bei RSA?

Antwort anzeigen

Der öffentliche Schlüssel $(e, n)$ wird geteilt – jeder kann damit verschlüsseln oder Signaturen prüfen. Der private Schlüssel $(d, n)$ bleibt geheim – nur der Besitzer kann damit entschlüsseln oder signieren. Beide Schlüssel sind mathematisch über $ed \equiv 1 \pmod{\varphi(n)}$ verknüpft, aber aus $e$ auf $d$ zu schließen erfordert die Faktorisierung von $n$.

Frage 3: Warum ist die Caesar-Chiffre trotz unbekannter Verschiebung unsicher?

Antwort anzeigen

Erstens gibt es nur 25 mögliche Schlüssel – ein Computer (oder ein Mensch) kann alle in Sekunden ausprobieren (Brute-Force). Zweitens bleibt die Buchstabenhäufigkeit erhalten: Im Deutschen ist E der häufigste Buchstabe. Der häufigste verschlüsselte Buchstabe entspricht also wahrscheinlich dem verschlüsselten E – damit lässt sich die Verschiebung erraten.

Frage 4: Alice sendet Bob die Zahl $A = g^a \bmod p$ per Diffie-Hellman. Bob sendet $B = g^b \bmod p$. Warum kann ein Lauscher, der $A$, $B$, $g$ und $p$ kennt, den gemeinsamen Schlüssel $K = g^{ab} \bmod p$ nicht einfach berechnen?

Antwort anzeigen

Der Lauscher müsste entweder $a$ aus $A = g^a \bmod p$ oder $b$ aus $B = g^b \bmod p$ berechnen. Das ist das diskrete Logarithmusproblem – für große Primzahlen $p$ gibt es keinen bekannten effizienten Algorithmus. Ohne $a$ oder $b$ kann er $g^{ab} \bmod p$ nicht berechnen.