Klassische Verfahren und Hash

Grundbegriffe: Schlüssel und Sicherheitsziele

Eine Verschlüsselung macht aus einem lesbaren Klartext mithilfe eines Schlüssels einen unlesbaren Geheimtext. Die Umkehrung heißt Entschlüsselung.

Symmetrische Verfahren sind schnell, haben aber das Schlüsselaustausch-Problem: Wie kommt der geheime Schlüssel sicher zum Empfänger? Asymmetrische Verfahren lösen dieses Problem, sind aber deutlich langsamer. In der Praxis (z. B. HTTPS/TLS) kombiniert man beide: asymmetrisch wird ein Sitzungsschlüssel vereinbart, danach läuft die Datenübertragung symmetrisch (hybrides Verfahren).

Caesar-Verschlüsselung und Häufigkeitsanalyse

Bei der Caesar-Verschlüsselung wird jeder Buchstabe um eine feste Zahl $k$ im Alphabet verschoben. Der Schlüssel ist die Verschiebung $k$. Nach dem Z geht es bei A weiter (Rechnen modulo 26).

Zählen Sie die Buchstaben von $A = 0$ bis $Z = 25$. Dann gilt:

Wie man Caesar knackt

Es gibt nur 25 sinnvolle Verschiebungen (die Verschiebung 0 ändert nichts, 26 ist wieder 0). Der Schlüsselraum ist also winzig: Ein Angreifer probiert einfach alle Schlüssel durch (Brute Force).

Bei längeren Texten geht es noch eleganter mit der Häufigkeitsanalyse: In jeder Sprache kommen Buchstaben unterschiedlich oft vor. Im Deutschen ist E mit etwa 17 % der häufigste Buchstabe, danach folgen N (etwa 10 %) und I (etwa 8 %). Eine Caesar-Verschiebung verändert diese Verteilung nicht, sie verschiebt sie nur. Ist im Geheimtext H der häufigste Buchstabe, so steht H vermutlich für E. Die Verschiebung ist dann $7 - 4 = 3$.

Vigenère-Verfahren

Die Schwäche von Caesar: Ein Klartextbuchstabe wird immer zum selben Geheimtextbuchstaben. Das Vigenère-Verfahren (monoalphabetisch → polyalphabetisch) verwendet statt einer Zahl ein Schlüsselwort. Jeder Buchstabe des Schlüsselworts gibt eine eigene Caesar-Verschiebung vor ($A = 0$, $B = 1$, …). Das Schlüsselwort wird so oft wiederholt, bis es zur Länge des Klartexts passt.

Warum Vigenère lange als sicher galt

Die Häufigkeitsverteilung des Geheimtexts wird „eingeebnet“, weil derselbe Klartextbuchstabe je nach Position unterschiedlich verschlüsselt wird. Der häufigste Buchstabe im Geheimtext ist nicht mehr eindeutig E.

Der Schlüsselraum ist größer: Ein Schlüsselwort der Länge $L$ aus 26 Buchstaben ergibt $26^L$ Möglichkeiten. Für $L = 6$ sind das

Schlüssel, gegenüber 25 (bzw. 26, wenn man die Verschiebung 0 mitzählt) bei Caesar.

Trotzdem ist Vigenère knackbar, wenn man die Schlüssellänge $L$ kennt: Dann bilden die Buchstaben an den Positionen $1, 1+L, 1+2L, \dots$ jeweils eine einfache Caesar-Verschlüsselung, auf die man die Häufigkeitsanalyse anwenden kann. Die Länge $L$ findet man zum Beispiel mit dem Kasiski-Test: Wiederholt sich eine Buchstabenfolge im Geheimtext, so ist ihr Abstand oft ein Vielfaches von $L$. Die gemeinsamen Teiler der Abstände liefern Kandidaten für $L$.

Hashfunktionen

Eine Hashfunktion bildet Daten beliebiger Länge auf einen Hashwert fester Länge ab, zum Beispiel jede Datei auf 256 Bit. Der Hashwert ist wie ein Fingerabdruck der Daten.

Hashwerte sind keine Verschlüsselung: Man kann sie nicht entschlüsseln, denn aus vielen möglichen Daten wird derselbe kurze Wert.

Anwendungen

Integritätsprüfung. Ein Anbieter veröffentlicht neben einem Programm den Hashwert der Datei. Nach dem Download berechnen Sie selbst den Hashwert. Stimmen beide überein, ist die Datei unverändert (kein Übertragungsfehler, keine Manipulation).

Passwörter. Ein Webdienst speichert nur den Hashwert $h(\text{Passwort})$. Beim Login wird das eingegebene Passwort gehasht und mit dem gespeicherten Wert verglichen. Gelangt die Datenbank in falsche Hände, stehen dort keine Passwörter im Klartext. Aus dem Hashwert lässt sich das Passwort nicht direkt ablesen. (Man ergänzt zusätzlich einen zufälligen „Salt“ je Nutzer, damit gleiche Passwörter verschiedene Hashwerte haben.)

RSA mit kleinen Zahlen

RSA ist das bekannteste asymmetrische Verfahren. Es beruht darauf, dass man zwei große Primzahlen leicht multiplizieren, das Produkt aber nur mit riesigem Aufwand wieder in die Faktoren zerlegen kann.

Die Nachricht $m$ ist dabei eine Zahl mit $0 \le m < n$. Ein Angreifer kennt $n$ und $e$, müsste aber $n$ in $p$ und $q$ zerlegen, um $\varphi(n)$ und damit $d$ zu bestimmen. Bei Zahlen mit mehreren Hundert Stellen ist das praktisch unmöglich. Hier rechnen wir mit kleinen Zahlen, damit man es von Hand nachvollziehen kann.

Digitale Signatur

Verschlüsselung schützt vor Mitlesen. Oft will man aber etwas anderes wissen: Stammt das Dokument wirklich von der angegebenen Person, und wurde es unterwegs verändert? Dafür dient die digitale Signatur, die Hashfunktion und asymmetrische Verschlüsselung kombiniert.

Signieren (Alice):

1. Alice berechnet den Hashwert $h$ des Dokuments.

2. Sie verschlüsselt $h$ mit ihrem privaten Schlüssel. Das Ergebnis ist die Signatur $s$.

3. Sie sendet Dokument und $s$.

Prüfen (Bob):

1. Bob berechnet selbst den Hashwert $h'$ des erhaltenen Dokuments.

2. Er entschlüsselt $s$ mit Alices öffentlichem Schlüssel und erhält $h$.

3. Gilt $h = h'$, ist die Signatur gültig.

Damit werden zwei Sicherheitsziele erreicht: Integrität (das Dokument wurde nicht verändert, sonst wäre $h' \neq h$) und Authentizität (nur Alice besitzt den privaten Schlüssel, das Dokument stammt also von ihr). Man spricht auch von Nichtabstreitbarkeit.

Zurück zum Anfang: Auf dem Schulserver sollten nur Hashwerte der Passwörter liegen (Abschnitt Hashfunktionen). Eine geheime Nachricht an eine fremde Person schicken Sie mit deren öffentlichem Schlüssel (RSA).

Auf einen Blick