|
Voraussetzungen für eine geheime Übermittlung sind, dass
. der Empfänger den Schlüssel kennt, den der Sender verwendet hat
. niemand sonst den Schlüssel kennt
. es ohne Kenntnis des Schlüssels unmöglich oder zumindest außerordentlich schwierig ist, den Klartext zurückzugewinnen
Die Schwierigkeiten liegen darin, dass Sender und Empfänger
. einen gemeinsamen Schlüssel vereinbaren müssen, bevor sie geheime Botschaften austauschen können
. den Schlüssel geheimhalten müssen
. ein sicheres Verschlüsselungsverfahren finden müssen
Verschlüsselungsverfahren
Caesar-Chiffre
Gegeben sei ein Alphabet mit 26 Buchstaben (A ... Z). Der Klartext Abendzeit soll verschlüsselt werden. Die einfachste Form der Verschlüsselung ist, jeden Buchstaben des Klartextes durch z. B. den übernächsten Buchstaben im Alphabet zu ersetzten (gemäß der alphabetischen Reihenfolge und zyklisch, d.h. auf Z folgt wieder A). Das Ergebnis ist der Geheimtext Cdgpfbgkv !
Mathematisch entspricht diese Verschlüsselung einer buchstabenweise \"Addition\" des Textes CCCCCCCCC zum Klartext. Werden die Buchstaben entsprechend der alphabetischen Reihenfolge von 0 bis 25 numeriert, so ergibt sich die Summe zweier Buchstaben aus der Summe dieser Nummern modulo 26.
C C C C C C C C C
+ A B E N D Z E I T
C D G P F B G K V
Der Empfänger kann aus dem Geheimtext den Klartext wieder zurückgewinnen. Er muss dazu wissen, mit welchem Algorithmus die Verschlüsselung vorgenommen wurde (hier: Addition), und er muss den Schlüssel C kennen. Durch Umkehrung des Verschlüsselungsalgorithmus (also hier: Subtraktion) unter Verwendung des richtigen Schlüssels ergibt sich wieder der Klartext
C D G P F B G K V
- C C C C C C C C C
A B E N D Z E I T
Dieses Verschlüsselungsverfahren bezeichnet man als Caesar-Chiffrierung !
Die Entschlüsselung des Geheimtextes ohne Kenntnis des Schlüssels bezeichnet man als Kryptanalyse.
Im einfachsten Fall gelingt die Kryptanalyse durch Ausprobieren alles Möglichkeiten. Im Falle der Caesar-Chiffre gibt es nur 26 verschiedene Schlüssel. Woher will man aber wissen, dass k = C und der Klartext Abendzeit, nicht jedoch k = D und der Klartext Zadmcydhs ist ? Dies liegt offenbar an der sogenannten Redundanz der Sprache. In unserer Sprache sind nicht alle Zeichenfolgen gleich wahrscheinlich, sondern die Zeichenfolge Abendzeit z. B. ist sehr wahrscheinlicher als Zadmcydhs !
Aufgrund der Wahrscheinlichkeit ergibt sich ein Ansatzpunkt für die Entschlüsselung von Wörtern. Wählt man für den Algorithmus f anstelle einer Verschiebung um i Symbole im Alphabet eine beliebige Permutation (Vertauschung) des Alphabets, so gibt es hierfür 26! 1026 Möglichkeiten. Diese kann man natürlich nicht alle ausprobieren. Des weiteren kann man nun die Wahrscheinlichkeit bestimmter Buchstaben einer Sprache hinzuziehen. E ist der häufigste Buchstabe in der deutschen Sprache. Nimmt man nun den am meisten vorkommenden Buchstaben im Geheimtext (G) und verschiebt diesen auf E, so erhält man bereits den Schlüssel C. Die nächsthäufigsten Buchstaben sind N, I, S, R, A und T. Oft kann man aufgrund dieser Entsprechungen den Klartext bereits erraten.
Kann für die Kryptanalyse lediglich der Geheimtext herangezogen werden, wird dies als Ciphertext-only-attack bezeichnet. Ist auch ein Teil des Klartextes bekannt, so wird die Kryptanalyse Known-plaintext-attack bezeichnet.
Häufig ist es auch möglich, den Klartext zu erraten. So ist es z. B. wahrscheinlich, dass in einem kirchlichen Text das Wort \"Amen\" häufiger vorkommt oder dass eine persönliche eMail mit dem Wort \"Hallo\" beginnt !
Im Falle der Caesar-Chiffre genügt die Kenntnis eines einzigen Klartextzeichens zusammen mit dem entsprechenden Geheimtextzeichen, um den Schlüssel k bestimmen zu können. Bei Verschlüsselung mit einer beliebigen Zuordnung von Buchstaben zu anderen Buchstaben (z. B. A D ; B V, usw.) benötigt man einen Klartext, in dem die wichtigsten Buchstaben mindestens einmal vorkommen. Dadurch kann man die Zuordnung zu den entsprechenden Geheimtextzeichen ermitteln. Die restlichen Buchstaben ergeben sich aus dem Sinnzusammenhang.
Polyalphabetische Verschlüsselung
One Time Pad
Werden bei der Verschlüsselung die Buchstaben des Klartextes nicht immer durch denselben Buchstaben ersetzt, also beispielsweise A nicht immer durch C, sondern mal durch Z, mal durch E, mal durch B usw., so ist eine statistische Analyse nach obigem Muster nicht möglich. Eine solche Verschlüsselung bezeichnet man als polyalphabetische Verschlüsselung.
T X E D U B N H W
+ A B E N D Z E I T
T Y I Q X A R P P
Ist der Schlüssel eine gleich verteilte Zufallsfolge von Buchstaben, so ist dieses Verschlüsselungsverfahren sogar absolut sicher. Dies liegt daran, dass es genauso viele mögliche Schlüssel wie mögliche Klartexte gibt, jeder Schlüssel gleichwahrscheinlich ist und somit auch jeder aus dem Geheimtext rekonstruierte Klartext gleich wahrscheinlich ist. Niemand kann sagen, ob der Schlüssel Txedubnhw oder Ykrephypi war. Im einen Falle wird der Geheimtext Tyiqxarpp zu Abendzeit entschlüsselt, im anderen Fall zu Vormittag.
Eine Verschlüsselung durch Addition einer Zufallsfolge heißt Vernam-Chiffre oder One-Time-Pad.
Vigenère-Chiffre
Eine weitere Methode der Verschlüsselung ist, einen periodischen Schlüssel zu verwenden, der durch Aneinanderreihung eines kurzen Wortes entsteht, z. B. das Wort "Zebra". Diese Art der Verschlüsselung wird Vigenère-Chiffre genannt.
Z E B R A Z E B R
+ A B E N D Z E I T
Z F F E D Y I J K
Auch bei diesem Verfahren wird z. B. das E mal auf F und mal auf I abgebildet, so dass eine statistische Analyse nicht zum Ziel führt.
Dennoch ist bei periodischen Schlüsseln eine statistische Kryptanalyse möglich. Bei einem Schlüsselwort der Länge 2 beispielsweise müssen 2 Statistiken erhoben werden - eine für die ungeraden und eine für die geraden Positionen des Geheimtextes. Die Länge des Schlüsselwortes wird durch Ausprobieren ermittelt.
Produkt-Chiffre
Die Periode des Schlüssels lässt sich verlängern, indem der Schlüssel in Teilschlüssel der Länge 2, 3, 5, 7, 11 ... zerlegt wird und der Klartext nacheinander mit diesen Teilschlüsseln verschlüsselt wird. Dies ist gleichbedeutend damit, dass aus den Teilschlüsseln zunächst ein Produktschlüssel gewonnen wird, mit dem dann der Klartext verschlüsselt wird. Die Periode des Produktschlüssels ist das Produkt der Teilschlüssellängen, die Schlüssellänge selbst ist aber nur gleich der Summe der Teilschlüssellängen. Bereits mit einem Schlüssel der Länge 77 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 lässt sich ein Produktschlüssel der Periode 107 erzeugen.
Beispiel
Der Schlüssel sei Woistreval, Teilschlüssel sind demzufolge Wo, ist und Reval. Der Produktschlüssel hat die Periode 30. Er errechnet sich wie folgt:
W O W O W O W O W O W O W O W O W O W O
+ I S T I S T I S T I S T I S T I S T I S
+ R E V A L R E V A L R E V A L R E V A L
V K K W Z Y I B P H F L Z G A N S C E R
(Aus Platzgründen sind hier nur die ersten 20 Zeichen aufgeführt)
Autokey-Verfahren
Die Idee beim Autokey-Verfahren ist, einen kurzen Schlüssel durch den Klartext selber zu verlängern.
Beispiel
Der Schlüssel sei Argo
A R G O E I N G E H E I M
+ E I N G E H E I M T E X T
E Z T U I P R O Q A I F F
Dieses Verfahren ist natürlich gegenüber einer known-plaintext-attack extrem unsicher. Aber auch durch statistische Analyse des Geheimtextes lässt sich der Klartext rekonstruieren. Der am häufigsten vorkommende Buchstabe im Geheimtext (im obigen Beispiel das I) entspricht an den meisten Positionen der Kombination E und E. Ist die Länge s des Schlüssels bekannt, so läßt sich ausgehend von diesen Positionen jedes s-te Klartextzeichen entschlüsseln.
Summen-Verfahren
Eine ähnliche Methode wie die des Autokey-Systems wird bei dem Summen-Verfahren angewandt. Jeder Klartextbuchstabe wird durch die Summe der s vorhergehenden Buchstaben und des Buchstabens selber verschlüsselt. Dadurch sollen die unterschiedlichen Buchstabenhäufigkeiten über einen Bereich der Länge s +1 gemittelt werden, so dass eine statistische Analyse zu keinem Ergebnis führt. Die so vorhergehenden Buchstaben des ersten klartextbuchstabens werden wiederum durch einen Schlüssel der Länge s gebildet.
Beispiel
Der Schlüssel sei Key
K E Y E I N G E H E I M T
+ E Y E I N G E H E I M T E
+ Y E I N G E H E I M T E X
+ E I N G E H E I M T E X T
Q O X F F E V X F R R G N
Enigma
Wenn die Periode des Schlüssels sehr lang wird, ist eine Entzifferung schwierig oder sogar unmöglich. Das Problem liegt jedoch darin, dass sehr lange Schlüssel in der Praxis schwer zu handhaben sind. Als Lösung wird versucht, einen langen Schlüssel aus einem kurzen zu erzeugen, aber nicht durch bloße Aneinanderreihung des kurzen Schlüssels, sondern auf komplizierte Art und Weise. In der im Zweiten Weltkrieg verwendeten deutschen Verschlüsselungsmaschine Enigma befinden sich drei Rotoren, die sich ähnlich wie ein Kilometerzähler bei jedem Buchstaben weiterdrehen. In jedem Rotor ist eine Permutation des Alphabets fest verdrahtet. Die Permutationen aller drei Rotoren sind hintereinander geschaltet. Auf diese Weise entsteht eine große Zahl unterschiedlicher Kombinationen und jedes Symbol des Klartextes wird mit einer anderen Permutation verschlüsselt. Als Parameter dieses Verschlüsselungsverfahrens war lediglich die Anfangsstellung der Rotoren zu übermitteln.
Lediglich aus Kenntnis des Geheimtextes ist dieser Code nicht zu entschlüsseln. Das Problem ist jedoch, dass nicht nur der Schlüssel, sondern insbesondere die Rotoren geheimzuhalten sind. Außerdem ist dieses Verfahren ebenfalls nicht gegenüber einer known-plaintext-attack sicher. Der Enigma wurde übrigens von den Polen sowie den Engländern recht schnell geknackt.
Pseudozufallsfolgen
Die zuletzt erläuterten Verfahren haben alle das Problem, dass aus einem relativ kurzen Schlüssel ein langer erzeugt wird. Gelingt es, die Systematik der Schlüsselgenerierung herauszufinden, so ist der lange Schlüssel nicht sicherer als der kurze.
Nur wenn der lange Schlüssel keiner Systematik unterliegt, wie dies beim One-Time-Pad der Fall ist, ist das Verfahren absolut sicher. Der Nachteil ist, wie bereits erwähnt, der lange Schlüssel, der hierfür notwendig ist.
Naheliegend ist daher die Idee, anstelle der beim One-Time-Pad verwendeten Zufallsfolge eine Pseudozufallsfolge zu verwenden. Sender und Empfänger verwenden denselben Zufallszahlengenerator. Sie brauchen nur den Startwert des Zufallszahlengenerators zu vereinbaren und können somit dieselbe Zufallsfolge erzeugen. Das Problem des Austauschs eines langen Schlüssels entfällt !
Allerdings beinhaltet eine Pseudozufallsfolge, auch wenn sie zufällig aussieht, eine sehr starke Systematik, nämlich die des Zufallszahlengenerators. Schon wenige Zeichen des Klartextes zusammen mit dem entsprechenden Geheimtext reichen aus, um diese Systematik zu durchschauen und alle weiteren und vorhergehenden Zufallszeichen zu erzeugen.
|
