Klassische Verfahren und Hash

Caesar-Verschlüsselung

Bei der Caesar-Verschlüsselung wird jeder Buchstabe um dieselbe Anzahl $k$ von Stellen im Alphabet verschoben. Am Ende des Alphabets geht es bei A weiter. Die Zahl $k$ ist der Schlüssel.

Sie verschlüsseln, indem Sie den Buchstaben in der oberen Zeile suchen und den darunterstehenden aufschreiben. Zum Entschlüsseln gehen Sie um $k$ Stellen zurück.

Rechnerisch nummeriert man A = 0, B = 1, …, Z = 25. Dann gilt:

Häufigkeitsanalyse und Schlüsselraum

Der Schlüsselraum ist die Menge aller möglichen Schlüssel. Bei Caesar sind das nur 26 Verschiebungen, wobei $k = 0$ nichts verändert. Ein Angreifer probiert sie alle in Sekunden aus.

Es geht noch eleganter: In jeder Sprache kommen Buchstaben unterschiedlich oft vor. Im Deutschen ist E mit etwa 17 % der häufigste Buchstabe, danach folgen N, I, S und R. Eine Caesar-Verschiebung ändert nur die Namen der Buchstaben, nicht ihre Häufigkeiten. Bei der Häufigkeitsanalyse gehen Sie so vor:

1. Zählen Sie die Buchstaben im Geheimtext (je länger der Text, desto zuverlässiger).

2. Der häufigste Geheimtext-Buchstabe steht vermutlich für E.

3. Die Verschiebung ist der Abstand zwischen beiden Buchstaben.

4. Entschlüsseln Sie probeweise. Ergibt der Text keinen Sinn, nehmen Sie den zweithäufigsten Buchstaben.

Vigenère-Verschlüsselung

Beim Vigenère-Verfahren ist der Schlüssel ein Schlüsselwort. Es wird unter den Klartext geschrieben und wiederholt. Jeder Buchstabe wird um den Wert des darunterstehenden Schlüsselbuchstabens verschoben (A = 0, B = 1, …).

Damit wird derselbe Klartextbuchstabe je nach Position unterschiedlich verschlüsselt. Es ist also eine Folge von Caesar-Verschiebungen, die sich nach der Länge des Schlüsselworts wiederholt.

Warum Vigenère lange als sicher galt und wie man es bricht

Die einfache Häufigkeitsanalyse scheitert, weil ein Geheimtext-Buchstabe nicht mehr für genau einen Klartextbuchstaben steht. Die Häufigkeiten werden „eingeebnet“. Die Schwäche ist die Wiederholung des Schlüssels:

• Ein Angreifer sucht Wiederholungen im Geheimtext (zum Beispiel gleiche Buchstabenfolgen). Ihre Abstände sind oft Vielfache der Schlüssellänge $L$ (Kasiski-Test).

• Kennt er $L$, teilt er den Text in $L$ Spalten (jeder $L$-te Buchstabe). Jede Spalte ist eine Caesar-Verschlüsselung mit festem $k$ und fällt der Häufigkeitsanalyse zum Opfer.

Der Schlüsselraum bei einem Schlüsselwort der Länge $L$ aus 26 Buchstaben beträgt $26^L$. Für $L = 6$ sind das

gegenüber 26 bei Caesar. Das ist deutlich größer. Doch wegen der Spaltenzerlegung muss ein Angreifer nicht alle Schlüssel durchprobieren, sondern nur $6 \cdot 26 = 156$ Verschiebungen.

Symmetrisch, asymmetrisch und RSA

Bei einem symmetrischen Verfahren (Caesar, Vigenère, AES) benutzen Sender und Empfänger denselben geheimen Schlüssel. Das ist schnell, aber der Schlüssel muss vorher sicher übergeben werden (Schlüsselaustauschproblem). Bei $n$ Personen braucht man für paarweise geheime Kommunikation $\frac{n(n-1)}{2}$ Schlüssel.

Bei einem asymmetrischen Verfahren (RSA) hat jeder ein Schlüsselpaar:

• öffentlicher Schlüssel (public key): darf jeder kennen, dient zum Verschlüsseln;

• privater Schlüssel (private key): bleibt geheim, dient zum Entschlüsseln.

Lea verschlüsselt mit dem öffentlichen Schlüssel von Ben. Nur Ben kann mit seinem privaten Schlüssel entschlüsseln. Ein geheimer Austausch vorab ist nicht nötig. Dafür ist das Verfahren langsamer. In der Praxis (HTTPS/TLS) nutzt man daher hybride Verfahren: Ein asymmetrisches Verfahren vereinbart einen Sitzungsschlüssel, mit dem die Daten dann symmetrisch verschlüsselt werden.

RSA mit kleinen Zahlen

Sicherheit beruht darauf, dass man große Zahlen $n = p \cdot q$ nicht effizient in ihre Primfaktoren zerlegen kann.

1. Wählen Sie zwei Primzahlen $p$ und $q$ und berechnen Sie $n = p \cdot q$ und $\varphi(n) = (p-1)(q-1)$.

2. Wählen Sie $e$ teilerfremd zu $\varphi(n)$. Öffentlicher Schlüssel: $(e, n)$.

3. Bestimmen Sie $d$ mit $e \cdot d \equiv 1 \pmod{\varphi(n)}$. Privater Schlüssel: $(d, n)$.

4. Verschlüsseln: $c = m^e \bmod n$. Entschlüsseln: $m = c^d \bmod n$.

Hashfunktionen

Eine Hashfunktion bildet Daten beliebiger Länge auf einen Hashwert fester Länge ab. SHA-256 liefert zum Beispiel immer 256 Bit, das sind 64 Hexadezimalziffern, ob die Eingabe ein Wort oder ein Film ist.

Eine gute kryptografische Hashfunktion hat diese Eigenschaften:

• Deterministisch und schnell: Gleiche Eingabe ergibt immer denselben Hashwert, der sich schnell berechnen lässt.

• Einwegfunktion: Aus dem Hashwert ist die Eingabe praktisch nicht rekonstruierbar.

• Lawineneffekt: Schon die Änderung eines einzigen Bits ändert den Hashwert völlig.

• Kollisionsresistenz: Es ist praktisch unmöglich, zwei verschiedene Eingaben mit demselben Hashwert zu finden.

Kollisionen gibt es immer, denn es gibt mehr mögliche Eingaben als Hashwerte. Man kann sie nur nicht finden.

Anwendung 1, Integrität: Auf einer Download-Seite steht der Hashwert eines Programms. Sie berechnen den Hashwert Ihrer heruntergeladenen Datei und vergleichen. Sind sie gleich, ist die Datei unverändert.

Anwendung 2, Passwörter: Ein Webdienst speichert nur $h(\text{Passwort})$. Beim Login wird das eingegebene Passwort gehasht und verglichen. Wird die Datenbank gestohlen, stehen dort keine Klartext-Passwörter. Wegen der Einwegeigenschaft kann man sie nicht einfach zurückrechnen. Zusätzlich hängt man an jedes Passwort ein zufälliges Salt, damit gleiche Passwörter verschiedene Hashwerte haben.

Digitale Signatur

Eine digitale Signatur beweist, wer ein Dokument erstellt hat und dass es unverändert ist. Sie kombiniert Hashfunktion und asymmetrische Verschlüsselung, aber umgekehrt zur vertraulichen Nachricht: Signiert wird mit dem privaten Schlüssel, geprüft mit dem öffentlichen.

Ablauf:

1. Alice berechnet den Hashwert $h(D)$ des Dokuments $D$ und verschlüsselt ihn mit ihrem privaten Schlüssel. Das ist die Signatur $S$. Sie schickt $D$ und $S$.

2. Bob entschlüsselt $S$ mit Alices öffentlichem Schlüssel und erhält $h_1$. Außerdem berechnet er selbst den Hashwert $h_2$ des empfangenen $D$.

3. Gilt $h_1 = h_2$, ist die Signatur gültig.

Damit werden zwei Sicherheitsziele erreicht:

• Integrität: Wurde $D$ verändert, stimmt $h_2$ nicht mehr mit $h_1$ überein.

• Authentizität: Nur Alice besitzt den privaten Schlüssel, nur sie kann eine passende Signatur erzeugen. Sie kann das auch nicht abstreiten (Nichtabstreitbarkeit).

Ein Hashwert allein reicht nicht: Ein Angreifer könnte Dokument und Hashwert austauschen, und Bob würde nichts bemerken. Erst die Signatur bindet den Hashwert an die Identität des Absenders.

Auf einen Blick

Zurück zum Anfang: Lea verschlüsselt mit Bens öffentlichem Schlüssel, damit nur er mitlesen kann, und signiert mit ihrem privaten Schlüssel, damit Ben weiß, dass die Nachricht von ihr stammt und unverändert ist.