Kryptologie

Seitdem Menschen schreiben können, wollen sie einander auch Nachrichten schicken, die nicht jeder lesen können soll. Wenn sich jemand eine «Geheimsprache» ausdenkt und diese nur einer anderen Person mitteilt, können sich diese beiden Personen in der Geheimsprache Briefe schreiben, die sonst niemand lesen kann. Aber was ist, wenn die Geheimsprache doch nicht so geheim ist, wie deren Erfinder sich erhofft haben?

DSC3154

Die Lavalampen bieten eine Quelle echter Zufälligkeit, oder Entropie. In San Francisco, Kalifornien, verschlüsselt eine Wand aus Lavalampen bis zu 10 % des Word Wide Webs. Die Bewegung der Blasen aus heissem Wachs ist unvorhersehbar. Die Verschlüsselung wird durch Schnappschüsse aus einem Video erzeugt, da die "Lavablasen" keine Muster haben, ist jeder Schnappschuss einzigartig. © Museum für Gestaltung Zürich, 2022

Die Wissenschaft vom Untersuchen solcher Geheimsprachen nennt sich die Kryptologie. Sie besteht im Wesentlichen aus der Kryptografie, die sich mit dem Ver- und Entschlüsseln von Nachrichten beschäftigt, und der Kryptoanalyse, die versucht, aus verschlüsselten Nachrichten ohne Kenntnis der Geheimsprache die ursprüngliche Nachricht wiederherzustellen. Der Wortanfang «Krypto-» kommt vom griechischen kryptós, was soviel wie «geheim» bedeutet.

Ein Kryptosystem besteht aus zwei Berechnungsvorschriften (Algorithmen). Der erste Algorithmus, die Verschlüsselung, wandelt eine Nachricht («Klartext») in eine verschlüsselte Nachricht («Chiffre-Text») um. Dazu wird in der Regel ein geheimer Schlüssel benötigt, etwa ein Kennwort. Der zweite Algorithmus ist die Entschlüsselung, die aus Chiffre-Text und geheimem Schlüssel wieder den Klartext zurückholt. Jeder, der das Verfahren sowie den geheimen Schlüssel kennt, kann damit verschlüsseln und entschlüsseln. Deswegen ist es wichtig, dass der geheime Schlüssel auch wirklich geheim bleibt.

Kodierung

Viele Verschlüsselungs-Verfahren arbeiten nicht mit Buchstaben, sondern mit Zahlen. Am Anfang des Verschlüsselungs-Prozesses muss deswegen aus einer Buchstaben-Folge, dem Klartext, eine Folge von Zahlen erzeugt werden. Diesen Prozess nennt man auch Kodierung. Auch wenn dies auf den ersten Blick so aussieht, ist eine Kodierung noch keine Verschlüsselung.

Eine einfache Methode ist die folgende: Dem Buchstaben «A» wird die Zahl 0, dem Buchstaben «B» die Zahl 1 zugewiesen, und so weiter:

DP Krypto Tabelle 05

Der Text «KODIERUNG» wird damit zur Zahlenfolge «10 14 03 08 04 17 20 13 06».

Am Computer werden Texte durch Folgen von Zahlen zwischen 0 und 255 dargestellt. Das sind gerade die Zahlen, die durch ein Byte ausgedrückt werden können. Heutzutage wird meist eine Kodierung namens UTF-8 verwendet. In dieser werden die Gross- und Kleinbuchstaben wie folgt abgebildet:

DP Krypto Tabelle 06
Caesar-Chiffre

Die Caesar-Chiffre geht auf den römischen Feldherrn Julius Caesar zurück, der diese zur Kommunikation mit seinen Truppen verwendete.

Bei dieser Verschlüsselung werden die Buchstaben im Alphabet um drei Stellen verschoben: Aus einem «A» wird ein «D», aus einem «B» ein «E», und so weiter. Am Ende des Alphabets fängt man schliesslich wieder vorne an: Während aus «W» ein «Z» wird, wird aus dem «X» wieder ein «A» und aus «Y» ein «B».

DP Krypto Tabelle 07

Mit dieser Verschlüsselung wird aus «WO SIND DIE GALLIER» der Text «ZR VLQG GLH JDOOLHU».

Zu Zeiten Caesars, wo fast niemand lesen und schreiben konnte, hat dieses Verfahren gut funktioniert. Heutzutage ist es jedoch sehr unsicher.

Substitutions-Chiffre

Bei einer Substitutions-Chiffre, auch Monoalphabetische Substitution genannt, legt man als geheimen Schlüssel eine Zuordnung von Buchstaben auf andere Buchstaben fest. Jeder Buchstabe vom Klartext wird dann mit dieser Zuordnung verschlüsselt. Die Caesar-Chiffre ist ein einfaches Beispiel für eine solche Substitutions-Chiffre. Ein anderes Beispiel ist die folgende Zuordnung:

DP Krypto Tabelle 08

Aus dem Klartext-Wort «GEHEIM» wird damit «QUCUYN».

Insgesamt gibt es 403’291’461’126’605’635’584’000’000 Möglichkeiten für solche Vertauschungen. Man kann also nicht einfach alle Möglichkeiten durchprobieren. Diese Verschlüsselung wurde im Mittelalter in Europa viel genutzt und galt als unknackbar. Jedoch war im arabischen Raum schon seit dem 9. Jahrhundert bekannt, dass solche Verfahren recht einfach angegriffen werden können. Die Araber hatten bemerkt, dass in einem Text nicht jeder Buchstabe gleich häufig auftritt. Manche Buchstaben, wie «E», treten sehr häufig auf, während andere wie etwa «Q» sehr selten auftreten.

Die Buchstabenhäufigkeiten hängen von der Sprache ab. Im Englischen sieht die Verteilung zum Beispiel so aus:

DP Krypto Tabelle 10

Wenn man also im verschlüsselten Text zählt, welche Buchstaben am häufigsten auftreten, kann man damit häufig schnell ein paar Zuweisungen erraten. Und kennt man die ersten paar Buchstaben der Zuordnung, kann man meist schnell weitere Buchstaben herausfinden.

Vigenère-Chiffre

Um das Problem mit der Buchstabenhäufigkeit zu vermeiden, gibt es viele Ansätze. Der wichtigste ist wohl, nicht für jeden Buchstaben die gleiche Substitution zu verwenden.

Eine einfache Möglichkeit, dies zu machen, bietet die Vigenère-Chiffre. Hier «addiert» man zur Verschlüsselung einen geheimen Schlüssel-Text zum Klartext hinzu, und zum Entschlüsseln zieht man ihn wieder ab. Um Buchstaben zu addieren, kann man die von Benediktinerabt Johannes Trithemius (1462–1516) beschriebene Tabula recta verwenden:

DP Krypto Tabelle 13

Man kann dies auch mit der Kodierung von weiter oben beschreiben: um zwei Buchstaben zu addieren, sagen wir «M» und «U», schreibt man diese als Zahl zwischen 0 und 25. Aus «M» wird 12, aus «U» wird 20. Diese addiert man zusammen: das ergibt 32. Ist das Ergebnis 26 oder grösser, so zieht man 26 ab. Aus 32 wird dann 6. Diese Zahl wird wiederum mit der Kodierung zu einem Buchstaben: «G». Mit der obigen Tabelle ist das jedoch einfacher zu machen.

Aber was macht man, wenn der geheime Schlüssel-Text kürzer (oder länger) als der Klartext ist? Dann wiederholt man ihn einfach (oder lässt den Rest weg). Will man etwa «GEHEIMWORT» mit dem Schlüssel-Text «KURZ» verschlüsseln, so berechnet man:

DP Krypto Tabelle 11

Die Entschlüsselung geht ähnlich:

DP Krypto Tabelle 12

Zum Entschlüsseln muss man abziehen. Mit der Tabula recta von oben geht das nicht so einfach, aber man kann auch eine entsprechende Tabelle zum Abziehen aufstellen:

Tabelle X

Leider hat sich gezeigt, dass auch dieses Verfahren nicht sicher ist. Unabhängig voneinander haben der Mathematiker Charles Babbage (1791–1871) und Infanteriemajor Friedrich Kasiski (1805–1881) das Verfahren brechen können. Babbage hat die Lösung Jahre vor Kasiski gefunden, er hat seine Lösung jedoch nie publiziert, sie wurde in seinem Nachlass entdeckt. Diese Angriffe basieren darauf, dass der Geheim-Text meist kurz ist, und oft nur aus einem Wort besteht.

Das Kerckhoffs'sche Prinzip

Im Jahr 1883 stellte der niederländische Linguist und Kryptologe Auguste Kerckhoffs in seiner Arbeit «La Cryptographie militaire» Regeln für die vertrauliche Kommunikation auf. Die wichtigste dieser Regeln lautet: «Das System darf keine Geheimhaltung erfordern». Diese Regel wird häufig als Kerckhoffs'sche Prinzip bezeichnet.

Die Regel besagt, dass die Sicherheit eines Verschlüsselungsverfahren nicht vom Verfahren selber abhängig sein darf, sondern nur vom verwendeten Schlüssel. Man muss bei der Analyse eines Verfahrens nämlich immer davon ausgehen, dass der Angreifer das Verfahren genauestens kennt.

Moderne Verfahren wie der Advanced Encryption Standard (AES) halten sich an dieses Prinzip. Den AES gibt es seit 2001, das zugrundeliegende Verfahren wurde bereits 1998 der Öffentlichkeit vorgestellt. Seitdem haben sich sehr viele Forschende auf diesen Algorithmus gestürzt – aber niemand konnte das Verschlüsselungs-Verfahren bisher brechen. Es gilt nicht zuletzt deswegen als sicher. Es gibt auch einige Beispiele für Verfahren, die sich nicht an dieses Prinzip gehalten und sich nachträglich als unsicher herausgestellt haben. Bekannte Bespiele sind die Verschlüsselung von Filmen auf DVDs (Content Scramble System, kurz CSS) sowie die Verschlüsselungsverfahren A5/1 und A5/2 vom 1990 eingeführten Mobilfunkstandard GSM («2G»).

Einmalverschlüsselung (One-Time-Pad)

Verschiedene Menschen hatten die Idee, die Vigenère-Chiffre zu verbessern, indem sie einen Geheim-Text verwendeten, der mindestens genauso lang ist wie der Klartext. Zuerst wurde dies 1882 von Frank Miller vorgeschlagen. Wichtig ist hierbei, dass man einen Schlüssel-Text nur ein einziges Mal verwendet, weshalb dieses Verfahren auch One-Time-Pad genannt wird.

Es ist auch das erste Verfahren, von dem man zeigen kann, dass es absolut sicher ist. Dazu muss man jedoch rein zufällige Schlüssel-Texte verwenden, und keinen Text in einer menschlichen Sprache. Die Voraussetzungen, dass ein Schlüssel-Text nie zweimal verwendet wird, und dass dieser rein zufällig ist, sind dabei essenziell. Falls dagegen verstossen wird, kann das Verfahren geknackt werden.

Ein Beispiel, wo dies zum Verhängnis wurde, ist das sogenannte VENONA-Projekt. Während des zweiten Weltkriegs und des anschliessenden kalten Krieges wurde die Kommunikation zwischen sowetischen Botschaften und Moskau unter anderem mit One-Time-Pads geschützt – allerdings wurden die Schlüssel-Texte teilweise in verschobener Form wiederverwendet. Dies hat Geheimdiensten der USA und dem britischen Auslandsgeheimdienst ermöglicht, die Kommunikation teilweise zu entschlüsseln.

Das One-Time-Pad ist zwar absolut sicher, aber auch sehr unhandlich. Man muss vorher genügend lange und genügend viele Schlüssel-Texte mit allen Parteien austauschen, mit denen man kommunizieren möchte. Macht man Fehler, sind diese schnell verhängnisvoll – siehe VENONA. Deshalb wird dieses Verfahren nur selten eingesetzt. Das bekannteste Beispiel ist wohl der «Heisse Draht» zwischen Moskau und Washington während des kalten Krieges.

Automatisierung

Sowohl das Ver- wie auch das Entschlüsseln war lange eine mühsame und langwierige Arbeit. Deswegen wurden mechanische und elektrische Hilfsmittel erfunden, die das Ver- und Entschlüsseln teilweise oder vollständig übernahmen. Die bekannteste solche Maschine ist die Enigma, die vor und während dem zweiten Weltkrieg von den Deutschen zur Verschlüsselung der Kommunikation eingesetzt wurde.

Die Verschlüsselung der Enigma konnte schon vor Beginn des zweiten Weltkriegs dank der Zusammenarbeit von französischen, polnischen und englischen Spionen geknackt werden. Denn mit Hilfe von Dokumenten, die ein französischer Spion aus Deutschland beschafft hatte, gelang polnischen Mathematikern ein grosser Durchbruch: Es war ihnen möglich, die ersten Verschlüsselungen der Enigma zu entschlüsseln. Ein wichtiges Hilfsmittel dabei war die «Bomba», eine Maschine zum automatischen Durchprobieren von vielen möglichen Einstellungen.

Dies währte jedoch nicht lange, da die Deutschen die Verschlüsselung der Enigma stetig verbesserten. Aber auch die Entschlüsselung wurde immer verfeinert, allen voran dank britischer Kryptografen und Mathematiker sowie der polnischen Mathematiker, die in der Zwischenzeit nach Frankreich geflohen waren. Die «Turing-Bombe», eine verbesserte Version der polnischen «Bomba», hatte an der Entschlüsselung einen grossen Anteil.

«Bomba» und die «Turing-Bombe» sind somit die ersten im grossen Stil eingesetzten Maschinen, die Teile der Kryptoanalyse automatisiert haben.

Moderne Verschlüsselung

Moderne Verschlüsselungs-Verfahren arbeiten nicht mit Buchstaben, sondern mit Bits. Alle Daten im Computer werden als Sequenzen von Nullen und Einsen abgespeichert, sogenannten Bits. Verschlüsselungsverfahren nehmen eine solche Sequenz von Bits als Eingabe-Daten, erhalten einen geheimen Schlüssel ebenfalls als Sequenz von Bits und berechnen daraus die Verschlüsselung, die wiederum eine Sequenz von Bits ist. Die Operationen, die hierbei durchgeführt werden, sind für einen Computer schnell zu machen – von Hand würde man dagegen sehr lange benötigen.

Eines der Verfahren, was heutzutage am häufigsten verwendet wird, ist der Advanced Encryption Standard (AES) von 2001. Dieses Verfahren ging aus einem Wettbewerb hervor: Viele Forschungsteams hatten Kandidaten für ein Verschlüsselungs-Verfahren vorgeschlagen, und in mehreren Runden wurden diese öffentlich untersucht. Laufend wurden immer mehr Kandidaten aussortiert. Der Gewinner war schliesslich der Algorithmus «Rijndael» der belgischen Kryptografen Joan Daemen und Vincent Rijmen.

Asymmetrische Verschlüsselung

Eine sehr spannende Entwicklung, die in der Praxis ohne Computer nicht durchführbar wäre, ist die Entwicklung von asymmetrischen Verschlüsselungs-Verfahren. Bei klassischen, symmetrischen Verfahren, müssen sich beide Parteien auf einen geheimen Schlüssel einigen, den sonst niemand kennen darf. Bei asymmetrischen Verfahren hat jede Partei zwei Schlüssel: einen geheimen Schlüssel, den sonst niemand kennen darf, und einen öffentlichen Schlüssel, den jeder kennen darf.

Die zwei bekanntesten und immer noch verwendeten Verfahren sind der von Whitfield Diffie und Martin Hellman 1976 vorgestellte Schlüsselaustausch sowie das 1977 von Ronald Rivest, Adi Shamir und Leonard Adleman vorgestellte RSA-Kryptosystem.

Spiel: Knacken Sie die Substitutions-Chiffre!
Beteiligte Kryptologie

Prof. Dr. Joachim Rosenthal, Institut für Mathematik, UZH
Dr. Felix Fontein

Jonas Voegeli, Visual Communication, ZHdK
Hubertus Design: Valentin Kaiser, Kerstin Landis, Nathan Meyer, Jonas Voegeli, Zürich

Mit herzlichem Dank an Mathmos: Erfinder der Lavalampe für das Bereitstellen von 100 Lavalampen.

Wir benutzen 
Cookies