Kryptologie: Klassische Kryptographie

Verschlüsselungsverfahren existieren bereits seit Altertum. Diese frühen Verfahren wurden per Hand ausgeführt. Sie halten der heutigen Kryptoanalyse und zur Verfügung stehenden Rechenleistung nicht mehr stand. Dennoch sei jedem angeraten sich mit diesen zu beschäftigen, da sie einen leichten Zugang bieten zu den grundlegenden Verfahren in der Kryptologie.

Das Grundproblem bleibt immer gleich:

Wie kann ich mit jemanden vertraulich kommunizieren, ohne, daß Unbefugte Kenntnis von der übermittelten Nachricht erlangen?

Es sind verschiedene Möglichkeiten denkbar, etwa die der organisatorischen, physikalischen oder kryptographischen Art.

Beispiele für Organisatorische Maßnahmen sind:

Ein Gespräch während eines einsamen Waldspaziergangs
Übermittlung durch einen (vertrauenswürdigen) Erklärungsboten
Kennzeichnung vertraulicher Dokumente als Verschlusssache (und damit einhergehende gesonderte Handhabung; ein Stempel allein bringt nichts)

Beispiele für Physikalische Maßnahmen wären:

Das Verstecken der Nachricht in einem Tresor
Versiegeln des Briefkuverts
Verheimlichen der Existenz der Nachricht, zB durch Geheimtinte (Steganographische Maßnahmen)

Wir wollen uns aber die der Kryptographie zuwenden. Dies bedeutet, daß die Nachrichten verändert bzw entstellt werden durch verschlüsseln. Wird die Nachricht verschlüsselt transportiert, so kann ein Außenstehender die zugrundeliegende Klartext-Nachricht nicht ohne weiteres lesen, ein zum Empfang berechtigter kann diese aber wieder herstellen.

Klassische Chiffren

Caesar-Verschlüsselung

Die Caesar-Verschlüsselung ist nach dem römischen Feldherrn Gaius Julius Caesar benannt, der die strategische Bedeutung in Kriegszeiten erkannte.

Das Prinzip ist wie folgt: Die Römer hatten 21 Buchstaben und nur Majuskel

A B C D E F G H I K L M N O P Q R S T V X

War nun die Nachricht

ANGRIFFIMMORGENGRAVEN

zu verschlüsseln, wurde jeder Buchstabe im Klartext mithilfe eines Schlüssels durch einen anderen Buchstaben ersetzt. Angenommen Caesar war so selbstverliebt und nahm deswegen gerne den Anfangsbuchstaben seines Namens “C”. C ist und war der dritte Buchstabe im Alphabet: Jeder Buchstabe wird durch den dritten darauffolgenden Buchstaben ersetzt. Dies wird vor allem durch folgende Umsetzungstabelle deutlich:

A B C D E F G H I K L M N O P Q R S T V X
D E F G H I K L M N O P Q R S T V X A B C

Aus der obigen Nachricht wird so schnell

DQKVMIIMPPRVKHQKVDBHQ

Empfing nun der Kompaniekommandant die Nachricht, so erfolgte die Entschlüsselung in umgekehrter Reihenfolge: Jeder Buchstabe der verschlüsselten Botschaft wird durch den entsprechenden Buchstaben in der oberen Zeile getauscht.

Es sind folgende Merkmale zu erkennen:

Sowohl für den Klartext als auch in der verschlüsselten Form wird das gleiche Alphabet verwendet.
Für die Verschlüsselung und Entschlüsselung wird der gleichen Schlüssel (durch x-ten Buchstaben ersetzen) verwendet.
Die Reihenfolge bleibt die gleiche: Der erste Buchstabe im Klartext hat sein Äquivalent im chiffrierten Text, ebenfalls an erster Position.

Da lediglich eine Verschiebung des Alphabets erfolgt, wird die Caesar-Verschlüsselung auch Caesar-Verschiebung genannt. Sie lässt sich natürlich auch aufs heutige Alphabet anwenden, mit Umlauten, Sonderzeichen usw., und die Verschiebung ist nicht auf ‘3’ beschränkt.

Sonderfall rot13

Eine (heute noch) praktische Anwendung der Caesar-Verschlüsselung ist rot13 (6): Rot13 (englisch ausgesprochen mit kurzem O) steht kurz für Rotation13 und bedeutet nichts anderes als die Caesar-Verschlüsselung mit dem Schlüssel 13. Die 13 soll nicht Unglück bringen, sondern hat den ganz einfachen Hintergrund: Beim heutigen lateinischen Alphabet mit 26 Buchstaben, funktionieren sowohl die Verschlüsselung als auch Entschlüsselung gleich:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
N O P Q R S T U V W X Y Z A B C D E F G H I J K L M

Ist der Buchstabe C zur Verschlüsseln, ergibt dies P. Will man später den Buchstaben P entschlüsseln, geht dies genauso gut, als wie wenn man P verschlüsseln wolle. Beide Buchstabenpaare sind oben hervorgehoben. Kommen im Klartext andere Buchstaben als die der 26 des lateinischen Alphabets, so bleiben diese unbehandelt, also Sonderzeichen, Interpunktion etc bleiben nach Verschlüsselung im Geheimtext bestehen. Insbesondere im Informatikumfeld ist rot13 beliebt, um den Leser vor versehentlichen Lesen zB von Quizantworten oder spoilern (Auflösung Handlung am Filmende) zu schützen.

Trivia

Ab und zu ergeben sich im Zusammenhang mit der Caesar-Chiffre lustige Zufälle: Zum Beispiel der Name des Bordcomputers in Stanley Kubricks Klassiker 2001, Odyssee im Weltraum ist HAL. Der Name könnte durch Anwendung der Caesar-Chiffre mit $k=-1$ auf das Akronym des Computerherstellers IBM entstanden sein. Diese Vermutung ist sehr umstritten und MGM (Produktionsfirma des Films) streitet dieses ab. Laut MGM und dem Autor der Romanvorlage von 2001 ist HAL einfach nur eine Abkürzung für “HalbALgorythmischer Rechner”. MGM zeigte sich dieses Vorwurfs sehr betroffen, da der Computer HAL im Film eher negativ dargestellt wird, IBM aber bei der Produktion des Films mitgeholfen hat. Man kann also eher davon ausgehen, das diese angebliche Rot-1 Verschiebung keine ist, sondern ein Zufall. Dasgleiche wird vom Kürzel des Betriebssystems WNT (Windows-NT) behauptet, dieses Kürzel entspricht dem Kürzel des Betriebsystemes VMS (ebenfalls Rot-1).

Skytale

Mit die erste krytographische Methode war die Skytale. Dies ist ein Holzstab definierten (geheimen) Durchmessers. Auf diesen wird ein Papierstreifen schraubenförmig aufgewickelt und dann die Nachricht quer zum Papierstreifen längs der Rotationsachse aufgeschrieben. Zu kurze Nachrichten werden mit beliebigen Buchstaben des Alphabets aufgefüllt, also ggf auch mit Leerzeichen. Für den Transport wird der Papierstreifen, bzw damals bei den Spartanern noch Pergamentstreifen oder Lederband, wieder abgenommen, sodaß sich ein Buchstabensalat ergibt und die Nachricht damit unleserlich wird. Zum Entschlüsseln braucht der Empfänger Kenntnis vom verwendeten Holzstabdurchmesser und braucht den Streifen nur noch entsprechend aufzuwickeln..

Beispielsweise die Nachricht “Ich liebe dich über alles” als Matrix aufgeschrieben

Ich l
iebe 
dich 
über 
alles

wobei eine Spalte der Länge nach des Papierstreifens entspricht, ergibt nach dem Abwickeln “Iidüaceiblhbcel˽ehrel˽˽˽s”. Die Buchstaben der ersten Zeilen sind hervorgehoben.

Im Gegensatz zur Caesar-Verschlüsselung sind folgende Unterschiede anzumerken:

die Klartext- und Geheimtextbuchstaben bleiben, in der Anzahl als auch welche überhaupt vorkommen, die gleichen
es ändern sich lediglich die Positionen.

Klassifizierung oben vorgestellter Chiffren

Wie bereits oben jeweils erwähnt, benutzen die vorgestellten Chiffren jeweils ein gemeinsames Alphabet für den Klartext als auch den Geheimtext. Eine derartige Verschlüsselung nennen wir monoalphabetische Verschlüsselung. Mono heißt altgriechisch soviel wie “einzig” oder “allein”: Es gibt ein einziges Alphabet. Alphabete werden iA mit Groß-Sigma $\Sigma$ bezeichnet.

Dann hört es jedoch mit den Gemeinsamkeiten auf. Wir haben festgestellt, daß die eine Chiffrierung die Buchstaben umordnet. Eine Umordnung, eine Permutation einer gegebenen Zeichenfolge, nennt man Permutationschiffre. Dies trifft in diesem Fall auf die Skytale zu. Permutationschiffren werden auch als Transposition bezeichnet. Die Skytale ist ein Spezialfall der Transposition. Denkbar wäre nämlich eine Permutationschiffre, die zur Erstellung des Geheimtextes erst den ersten, dann den 47-ten, danach den 32-ten Buchstaben nimmt, usw usf. Bei der Skytale wird jedoch, wie oben als Matrix betrachtet, die Nachricht zeilenweise aufgetragen und chiffriert liegt diese spaltenweise vor. Die Skytale ist also letztendlich eine einfache Matrixtransposition.

Im Gegensatz dazu werden bei der Caesar-Verschlüsselung die Buchstaben nicht umgeordnet. Sie werden ersetzt. Eine Verschlüsselung die auf Ersetzung beruht heißt Substitutitonschiffre. Die Caesar-Verschlüsselung substituiert ein jeden einzelnen Buchstaben mit seinem Äquivalent im Geheimtextalphabet. Da dabei nur ein Alphabet genutzt wird, ist lässt sich die Caesar-Verschlüsselung als monoalphabetische Substitutionschiffre klassifizieren. Ebenso die Skytale, die eine monoalphabetische Permutationschiffre ist.

Fazit: Substitutions- und Permutationschiffren sind zwei grundlegende Arten der Verschlüsselung. Bei der Permutation wechseln die Buchstaben ihren Platz, bleiben an sich aber vorhanden. Beim Substitutionsverfahren verändern sich unabhängig von deren Position die Buchstaben, wechseln hingegen im Chiffrat nicht ihren Platz. Wir werden feststellen, daß die Substitution die gängigere Verschlüsselungsmethode ist.

Variation von Substitutionchiffren

Die Caesar-Verschlüsselung hat, wie wir uns sicher denken können, einen gravierenden Nachteil: Es gibt nur soviele Schlüssel, wie es Buchstaben gibt, wobei eine “Verschiebung” um null Buchstaben ziemlich zwecklos ist. Wollte nun Caesar den Inhalt einer abgefangenen feindlichen Nachricht erfahren, so verdonnerte er wohl einfach 19 Sklaven, ein jeder der auswendig die Caesar-Entschlüsselung für einen bestimmten Buchstaben konnte, mit der Entschlüsselung des Chiffrats. So fand sich nach kurzer Zeit der richtige Schlüssel. Formal aufgeschrieben existieren für die Caesar-Verschlüsselung Betrag Sigma $|\Sigma |$ -verschiedene Schlüssel. Da $\Sigma$ eine Menge von Buchstaben ist, wird dessen “Betrag” auch Kardinalität oder Mächtigkeit der Menge genannt.

Will man nun eine solche brute-force-Attacke erschweren, könnte man im Geheimtextalphabet anstatt den gleichen im Klartextalphabet auch Sonderzeichen wie Dollar, Prozent, Tilde oder auch selbst ausgedachte Symbole verwenden. Die Sklaven wären da schnell ratlos geworden. Allerdings wie später vorgestellt werden wird, bietet diese Methode keinen Schutz vor einer statistischen Kryptoanalyse, war also höchstens zu Zeiten Nicht-vorhandenseins von Computern zielführend.

Anders verhält es sich dabei, wenn man die Schlüsselmenge erweitert. Die Caesar-Verschlüsselung hat nur deswegen sowenige Schlüssel, weil das Alphabet immer nur um eine bestimmte Anzahl verschoben wird. Dabei ist es doch genauso möglich A durch I und B durch A zu ersetzen:

A B C D E F G H I K L M N O P Q R S T V X
I A S K R L Q T B N O P B C D T V X E F G

Dies könnte sich ab und zu als unpraktikabel erweisen, da hierbei der ganze Schlüssel mit 20 Buchstaben übermittelt werden müßte. Eine wesentlich merkbarere Methode, die keine für den Menschen schwer erinnerbare Buchstabenfolge ergibt, ist die Erzeugung mithilfe eines Kennwortes. Bei der Erzeugung des Geheimalphabets wird zB zuerst ein Kennwort aufgeschrieben und danach mit den verbleibenden nicht zugeordneten Buchstaben aufgefüllt:

A B C D E F G H I K L M N O P Q R S T V X
P L A T O N B C D E F G H I K M Q R S V X

So muß nur noch das Kennwort und die Bildungsregel weitergegeben werden. Angemerkt sei, daß in dem Kennwort kein Buchstabe mehrfach auftreten darf, da so eine Mehrdeutigkeit entstehen würde. Ist dennoch ein Kennwort wie Aristoteles gewünscht, so müßten die wiederauftretenden Buchstaben herausgestrichen werden, sodaß das Kennwort bei der Erzeugung des Geheimtextalphabets etwa nur noch Aristoel lauten würde.

Es gibt schier unendlich verschiedene Möglichkeiten zur Wahl des Geheimtextalphabets. Insgesamt gibt es bei der monoalphabetische Substitution $|\Sigma |!$ Schlüssel, wobei die 1:1 Abbildung mangels Zweckmäßigkeit herausfällt, und auch viele andere, die noch eine zu große Übereinstimmung mit der ursprünglichen Klartext mit sich bringen. Das Ausrufezeichen bezeichnet die Fakultät, was $n!=\prod _{i=1}^{n}i$ der Multiplikation aller $n$ vorangehenden Faktoren entspricht. Für drei Fakultät $3!=1\cdot 2\cdot 3=6$ und für $26!=403291461126605635584000000$ .

Zurück zu Geschichte |

Hoch zum Start |

Vor zu Einfache Kryptoanalyse

Start | Polyalphabetische Kryptographie