Kryptographie, Teil 3: Vigenère und One-Time-Pad

In der vorherigen Folge haben wir uns zunächst mit Chiffren beschäftigt, bei denen die Buchstaben der Klartext-Nachricht nicht geändert, sondern lediglich anders angeordnet wurden: den Transpositionschiffren. Außerdem ging es um klassische Geheimschriften, bei denen die Buchstaben des Klartextes durch andere Zeichen ersetzt wurden: Substitutionschiffren.

Bei der Substitution, die bisher betrachtet wurde, handelt es sich um eine eingeschränkte Form: Jedes bestimmte Zeichen des Klartexts wird im Geheimtext stets durch das selbe Geheim-Zeichen ersetzt. Aus „A“ wird immer „C“, aus „B“ wird immer „D“ und so weiter. Man spricht daher von einer monoalphabetischen Substitution. Wie bereits besprochen, lässt sich eine solche Chiffre leicht durch eine statistische Analyse aushebeln.

Verschlüsselung
Ein verschlüsselter Rechner

Eine Verbesserung lässt sich nun dadurch erreichen, dass ein Klar-Zeichen nicht immer durch das gleiche, sondern durch verschiedene Geheim-Zeichen ersetzt wird. Man spricht dann von einer polyalphabetischen Substitution. Die einfachste Variante ist, häufig vorkommenden Buchstaben wie dem „E“ oder anderen Vokalen mehr als nur ein Geheimzeichen zuzuordnen und nach dem Zufallsprinzip mal das eine und mal das andere zu verwenden. Ziel ist es, eine all zu einfache statistische Analyse auszuhebeln. Dieses Verfahren wird homophone Chiffre genannt. Aber auch mit diesem Verfahren gibt es immer noch genügend Möglichkeiten, allein durch eine statistische Analyse des Geheimtextes den Klartext wiederherzustellen. Es gibt schließlich nicht nur eine Statistik über die Häufigkeit einzelner Buchstaben, man kann auch Buchstabenpaare, Besonderheiten am Wortanfang oder -ende und häufig vorkommende Worte oder Phrasen zur Analyse heranziehen.

Ein Weg, der etwas mehr bringt, ist in Abhängigkeit von der Position eines Klartextzeichens jeweils ein anderes Geheimtextzeichen zu verwenden. Beim Vigenère-Verfahren, benannt nach Blaise de Vigenère (1523–1596), wird in Abhängigkeit eines Passworts für jeden Buchstaben des Klartexts eine andere Caesar-Chiffre verwendet. Ist der Klartext länger als das Passwort, wird das Passwort wiederholt. Am deutlichsten wird das anhand eines Beispiels:

Klartext:   UND DAS WAR ES WORUEBER SIE SPRACHEN
Passwort:   HANSHANSHANSHANSHANSHANSHANSHANSHANS
Geheimtext: COR LBW EBF MT PWSIXJFF AJS AQPTKISG

Zu jedem Klartext-Buchstaben wird beim Verschlüsseln sozusagen ein Buchstabe des Passworts addiert, zum Entschlüsseln geht man umgekehrt vor.

Besonders sicher ist dieser Algorithmus aber immer noch nicht. Der Geheimtext lässt sich nämlich immer noch statistisch analysieren. Ist erst einmal die Länge des Passworts bekannt, ist das sogar sehr leicht, denn dann folgen alle Zeichen, die mit dem selben Passwort-Buchstaben verschlüsselt wurden (im Beispiel also jeder vierte Buchstabe), wieder der selben charakteristischen Häufigkeitsverteilung. Die Länge des Passworts lässt sich durch andere statistische Verfahren, die hier aber nicht erklärt werden sollen (wer möchte, kann nachschlagen, zum Beispiel in dem bereits in der letzten Folge erwähnten Buch von Beutelspacher), oder ganz simpel durch Ausprobieren herausbekommen.

Ein anderer Angriff ist jedoch viel gefährlicher und führt einen Bösewicht, der eine verschlüsselte Nachricht abfangen will, auf einem viel schnelleren Weg zum Ziel. In der Praxis ist es nämlich oft so, dass einem Angreifer Teile des Klartextes schon bekannt sind. Vielleicht ist es der Name eines Ortes oder einer Person oder sonst irgendein Wort, das im Text vorkommt. Hält man sich noch einmal vor Augen, wie beim Vigenère-Verfahren der Geheimtext aus Klartext und Passwort berechnet wird, so wird klar, dass sich umgekehrt aus Geheim- und Klartext auch das Passwort trivial durch Subtraktion berechnen lässt. Im folgenden Beispiel sind die dem Angreifer bisher unbekannten Zeichen des Klartexts noch Fragezeichen, ein Wort und der dazugehörige Geheimtext sind ihm aber bekannt. Das Passwort kann dann an der fraglichen Stelle leicht zurückberechnet werden:

Klartext:   ??? ??? ??? ?? WORUEBER ??? ????????
Passwort:                  SHANSHAN 
Geheimtext: COR LBW EBF MT PWSIXJFF AJS AQPTKISG

Da das Passwort üblicherweise kürzer als der Klartext ist, kann man schon an der entscheidenen Stelle erkennen, dass es sich hier wiederholt. Ist dem Angreifer das Passwort erst einmal bekannt, kann er natürlich jetzt auch den Rest des Geheimtextes entziffern.

Diese Art des Angriffs, bei der dem Angreifer ein Teil des Klartexts bekannt ist, nennt man known plaintext attack. Im Gegensatz dazu heißt ein Angriff, bei dem nur der Geheimtext abgefangen wurde, known ciphertext attack oder auch ciphertext only attack. Bis hier können wir also zusammenfassen, dass sich die einfache monoalphabetische Codierung bereits mit einem known ciphertext-Angriff auf Basis von Statistik sehr leicht brechen lässt. Auch die Vigenère-Chiffre ist anfällig für einen solchen statistischen Angriff, wenn er auch etwas schwieriger durchzuführen ist. Bei einem known plaintext-Angriff dagegen bricht die Sicherheit beider Verfahren direkt zusammen.

Würde man eine Vigenère-Chiffre heutzutage einsetzen und dabei ganze Dateien verschlüsseln, haben wir übrigens geradezu trivialerweise eine known plaintext-Situation vorliegen: Dateien vieler bekannter Dateiformate starten mit sogenannten magic numbers oder sonstigen Zeichenfolgen, die die Art der Datei oder die Versionsnummer des Formats oder ähnliches beschreiben. Ist das Dateiformat der zu entschlüsselnden Datei bekannt, ist also sofort auch ein Teil des Klartextes bekannt und das Vigenère-Verfahren somit völlig wertlos.

Doch warum sind die bisher besprochenen Angriffe bei der Vigenère-Chiffre so gefährlich? Wie bereits erwähnt, besteht die Gefahr darin, dass das Passwort, also der Schlüssel, im Vergleich zum Klartext recht kurz ist und sich daher wiederholen muss. Nur durch die Wiederholung konnten die statistische Analyse und auch der oben gezeigte known plaintext-Angriff überhaupt erst erfolgreich sein: Ist der Schlüssel an einer Stelle berechnet, kann er an allen anderen Stellen eingesetzt werden.

Blaise de Vigenère
Blaise de Vigenère

Doch was wäre, wenn sich das Schlüsselwort nicht wiederholt, wenn also der Schlüssel genau so lang wie der Klartext ist?

In diesem Fall hätten wir durch unsere obigen Angriffe rein gar nichts gewonnen! Eine statistische Analyse wäre nicht möglich, da die einzelnen Zeichen im Geheimtext keiner Häufigkeitsverteilung mehr folgen und eine Zurückberechnung des Schlüsselworts an einer Stelle wie beim known plaintext-Angriff würde zu nichts führen, eben weil sich der Schlüssel ja nirgends wiederholt!

Auf diese Art wird aus dem unsicheren Vigenère-Algorithmus das einzige Verschlüsselungsverfahren, das wirklich unknackbar ist, was man sogar mathematisch beweisen kann: Das One-Time-Pad!

Damit die Sicherheit des One-Time-Pads gewährleistet ist, müssen aber einige Bedinungen erfüllt sein: Zunächst einmal muss der Schlüssel mindestens genau so lang wie der Klartext sein, damit an keiner Stelle eine Wiederholung auftritt. Der Schlüssel selbst sollte außerdem kein Wort oder natürlicher Text sein. Der Grund ist simpel: Die Buchstaben eines Textes folgen ja wie schon bereits besprochen einer statistischen Verteilung und die kann man für einen Angriff ausnutzen.

Der Schlüssel muss also zufällig erzeugt werden. Das ist gar nicht so leicht, wie es sich auf den ersten Blick anhört. Denn wie erzeugt man eine so große Menge an Zufallswerten? Wer etwas programmieren kann, könnte vielleicht auf die Idee kommen, den Zufallsgenerator des Computers in der favorisierten Programmiersprache zu benutzen. Aber Vorsicht: Die Zahlen, die dieser ausspuckt, sind alles andere als zufällig. Sie wiederholen sich irgendwann und folgen einem – wenn auch auf den ersten Blick schwer zu durchschauenden – Muster, sind also für ein Verschlüsselungsverfahren nicht geeignet. Der einzige Weg, echte Zufallszahlen zu erzeugen, ist, sich physikalische Effekte zu nutze zu machen. Man könnte zum Beispiel das Rauschen eines Wasserfalls aufnehmen.

Und der entscheidende Punkt ist: Der Schlüssel des One-Time-Pads darf nur ein einziges Mal verwendet werden! Daher kommt schließlich auch das „One Time“ im Namen des Algorithmus. Das Verfahren hat einen Einmalschlüssel.

Hat man endlich einen Schlüssel, der den Anforderungen entspricht, muss man diesen zu guter letzt noch vor der eigentlichen Kommunikation dem Gesprächspartner zukommen lassen. Das muss über einen sicheren Kanal geschehen, es muss absolut ausgeschlossen sein, dass ein Angreifer eine Kopie des Schlüssels anfertigen kann. Es führt also kein Weg daran vorbei, den Schlüssel vor Ort und persönlich zu übergeben.

Diese vier Anforderungen, die erfüllt sein müssen, um die Sicherheit zu gewährleisten, zeigen eines: Nachweisbar unknackbare Verschlüsselung ist zwar in der Theorie nicht kompliziert, aber in der Durchführung ausgesprochen unhandlich. Und das ist auch der Grund, warum die One-Time-Pad-Verschlüsselung im Internet so gut wie keine Rolle spielt: Sie ist in der Praxis kaum durchführbar. Es gibt allerdings Ausnahmen, nämlich im militärischen Hochsicherheitsbereich. So war zum Beispiel das „rote Telefon“ zwischen den USA und den UdSSR zu Zeiten des kalten Krieges mit einem One-Time-Pad gesichert.

Das grüne Telefon
Das rote Telefon (Abbildung ähnlich)

Trotz der bekannten Unsicherheiten des Vigenère-Verfahrens wurden übrigens Abwandlungen davon noch sehr lange eingesetzt, zum Beispiel Ende der 1990er-Jahre im populären Textverarbeitungsprogramm WordPerfect. Und wahrscheinlich gibt es auch heute noch die ein oder andere von Ahnungslosen geschriebene Software, die diese „Verschlüsselung“ nutzt. Natürlich gibt es heutzutage besseres, aber dazu kommen wir in einer der nächsten Folgen.

Die wichtigsten Punkte der heutigen Folge noch einmal zusammengefasst:

  • Es gibt sogenannte polyalphabetische Verschlüsselungen, zu denen das Vigenère-Verfahren gehört.
  • In der Praxis spielen known plaintext-Angriffe eine große Rolle.
  • Die Vigenère-Chiffre ist äußerst unsicher gegen known plaintext-Angriffe.
  • Das One-Time-Pad oder Einmalschlüssel-Verfahren ist das einzige beweisbar sichere Verfahren, aber in der Praxis nur schwer durchzuführen.

In den nächsten Folgen werden wir uns immer weiter in Richtung Gegenwart bewegen und dabei auch das interessante Thema der Verschlüsselung zu Zeiten des zweiten Weltkriegs betrachten.

 

2 Gedanken zu „Kryptographie, Teil 3: Vigenère und One-Time-Pad

  1. ein riesen lob habe ich abzugeben.
    sehr gut geschrieben und verständlich und für jeden noob nachvollziehbar.
    ein weiteres/weiterer blog dass ich verfolgen werde

Kommentare sind geschlossen.