Kryptoanalysen - wie knacke ich Verschlüsselungen?



  • TL;DR

    In diesem Tutorial lernst du, wie du einfache Verschlüsselungsmethoden wie die Caesar- oder Polybios-Chiffre knacken kannst. Dazu brauchst du nichts weiter als einen Block, einen Stift und einen Webbrowser. An Grundwissen musst du nicht viel mitbringen. Sinnvoll ist es aber, wenn du weißt, was Wahrscheinlichkeiten sind. Wenn du schon einmal von der Caesar- oder Polybios-Verschlüsselung gehört hast - umso besser!

    Dieses Tutorial richtet sich an Anfänger bis Fortgeschrittene und nimmt je nach Vorwissen 15 - 90 Minuten deiner Zeit in Anspruch.


    Inhalt

    1. Grundlagen
      1.1 Caesar
      1.2 Polybios
    2. Knacken der Caesar-Verschlüsselung
      2.1 Rohe Gewalt
      2.2 Echte Kryptoanalyse
    3. Knacken der Polybios-Chiffre
    4. Zusammenfassung und Ausblick
    5. Lösungen der Übungen
    6. Quellen und Links

    1. Grundlagen

    Sowohl bei der Caesar-Chiffre, als auch bei der Polybios-Chiffre handelt es sich um sogenannte "monoalphabetische Substitutionsverfahren". Das bedeutet, dass beim Verschlüsseln je ein Zeichen, durch ein anderes getauscht wird (Substitution). Monoalphabetisch bedeutet, dass das immer gleich geschieht, z. B. wird aus einem "a" im ganzen verschlüselten Text immer ein "g".

    Für Fortgeschrittene:
    Bei polyalphabetischen Substitutionsverfahren - die hier nicht Bestandteil sind - kann sich die Regel ändern. Aus einem "a" wird dann zum Beispiel am Anfang des Textes ein "g", später aber ein "x".

    1.1 Caesar

    Wird ein Text mithilfe der Caesar-Chiffre verschlüsselt, werden alle Zeichen eines Textes um eine bestimmte Anzahl nach rechts verschoben.

    Zum Beispiel so:

    640px-Caesar3.svg.png

    Das Passwort eines mit der Caesar-Methode verschlüsselten Textes ist also die Zahl, um wie viel Stellen alle Zeichen verschoben wurden. Im Beispiel im Bild also 3.

    Um einen Text zu entschlüsseln, braucht man diese Zahl. Verschiebt man im verschlüsselten Text alle Zeichen um <Passwort> nach links, erhält man wieder den Klartext.

    Übung 1: Versuche den folgenden Text mit dem Passwort 5 zu verschlüsseln:

    Kaiser Augustus verwendete das Verfahren

    Übung 2: Versuche den folgenden Text mit dem Passwort 12 zu entschlüsseln:

    ekyyqfdueotqe Hqdeotxgqeeqxgzsehqdrmtdqz


    1.2 Polybios

    Ähnlich wie bei der Caesar-Chiffre werden auch bei Polybios Zeichen durch andere ersetzt. Diesmal ist das Verfahren aber etwas komplexer.

    Man beginnt damit, das Passwort zu bauen. Dazu zeichnet man eine Tabelle mit 6 Zeilen und 6 Spalten. Von links nach rechts und von oben nach unten füllt man nun das gewünschte Passwort in die Zellen. Dabei darf sich aber kein Zeichen wiederholen!

    Lautet das Passwort beispielsweise "Butterkeks" würde die Tabelle zunächst so aussehen:

    1 2 3 4 5 6
    1 B U T E R K
    2 S
    3
    4
    5
    6

    Die restlichen Zellen werden nun einfach mit dem verbleibenden Alphabet und den Zahlen 0-9 aufgefüllt. Wer möchte, kann das auch zufällig tun:

    1 2 3 4 5 6
    1 B U T E R K
    2 S A C D F G
    3 H I J L M N
    4 O P Q V W X
    5 Y Z 0 1 2 3
    6 4 5 6 7 8 9

    Damit ist das Passwort fertig. Möchte man nun einen Text verschlüsseln, muss man nur für jedes Zeichen des Klartextes in der Tabelle die Spalten- und Zeilennummer notieren.

    Aus "Hallo" wird dadurch mit unserem gerade erzeugten Passwort: "13 22 43 43 14".

    Übung 3: Versuche den folgenden Text mit dem Passwort "KATZE" zu verschlüsseln (den Rest des Alphabets in korrekter Reihenfolge auffüllen):

    kryptographische Sicherheit

    Übung 4: Versuche den folgenden Text mit dem Passwort "NIMBUS" zu entschlüsseln (den Rest des Alphabets in korrekter Reihenfolge auffüllen):

    33 35 23 12 24 42 15 11 26 13 12 43 25 21 22 33 24 34 11


    2. Knacken der Caesar-Verschlüsselung

    2.1 Rohe Gewalt

    Die einfachste Möglichkeit einen Caesar-verschlüsselten Text zu knacken ist durch rohe Gewalt - im Englischen Brute Force genannt. Das bedeutet nichts anderes, als einfach alle möglichen Passwörter zu probieren.

    Im Falle der Caesar-Verschlüsselung gibt es 27 mögliche Passwörter, wobei die Passwörter 0 und 26 nichts am Text ändern. Es bleiben also 25 sinnvolle Passwörter. Sie alle für das erste Wort eines verschlüsselten Textes zu probieren ist nicht aufwändig und führt auf jeden Fall zum Erfolg.

    Hier ein Beispiel. Angenommen du hast den folgenden Text empfangen, aber kennst das Passwort nicht:

    Lqmamz Bmfb qab ompmqu

    Probierst du für das erste Wort jedes Passwort, erhältst du:

    1. Kplzly
    2. Jokykx
    3. Injxjw
    4. Hmiwiv
    5. Glhvhu
    6. Fkgugt
    7. Ejftfs
    8. Dieser

    Der 8. Versuch sieht nach einem sinnvollen Wort aus. Nun kann man direkt den ganzen Text versuchen und erhält:

    Dieser Text ist geheim

    Übung 5: Versuche den folgenden Text mit roher Gewalt zu knacken:

    EYD XEJ HAEYDP VQ GJWYGAJ


    2.2 Echte Kryptoanalyse

    Möchte man sich der Lösung etwas klüger nähern, so kann man Wahrscheinlichkeiten und Auffälligkeiten nutzen. Bestimmte Buchstaben kommen in deutschen Texten nämlich häufiger vor als andere und bestimmte Muster im Text können verräterisch sein. Da jedes Zeichen im verschlüsselten Text immer auf den gleichen entsprechenden Klartextbuchstaben zurückzuführen ist, kann man so auf das Passwort schließen. Es genügt also bereits ein Zeichen im Klartext zu kennen, um den Rest entschlüsseln zu können, da dann die Art Verschiebung der Zeichen klar wird.

    Ein Beispiel:

    RVARF GNTRF VZ JNYQ

    Man kann sich dem Problem nun mit Statistik nähern. Zählt man die Vorkommen aller Buchstaben im verschlüsselten Text, erhält man das folgende Ergebnis:

    • 'R': 3
    • 'V': 2, 'F': 2, 'N': 2
    • 'A': 1, 'G': 1, 'T': 1, 'Z': 1, 'J': 1, 'Y': 1, 'Q': 1

    Der Buchstabe 'E' kommt in langen deutschen Texten mit Abstand am häufigsten vor:
    1024px-Buchstabenhäufigkeit_Deutsch.svg.png
    Quelle

    Man kann nun probieren den Text zu entschlüsseln, unter der Annahme, der häufigste Buchstabe wäre ein 'E'. Jedes 'R' wäre damit ein 'E'. 'R' und 'E' liegen im Alphabet 13 Zeichen auseinander. Also muss jedes Zeichen zum Entschlüsseln um 13 Zeichen zurück verschoben werden:
    'R' = 'E':

    EINES TAGES IM WALD

    Das war einfach!

    Hier ein weiteres, schwierigeres Beispiel:

    GQFZPWFZY GQJNGY GQFZPWFZY, GWFZYPQJNI GQJNGY GWFZYPQJNI.

    Was zuerst auffällt ist, dass alle Anfangsbuchstaben aller Wörter gleich sind. Darüber hinaus sind das 1. und 3., und das 4. und. 6. Wort identisch. Genauso das 2. und 5. Wort. Insgesamt kommen in dem Text also nur 3 unterschiedliche Wörter vor.

    GQJNGY

    Wie viele Wörter mit 6 Buchstaben gibt es wohl in der deutschen Sprache, deren Anfangsbuchstabe auch an 5. Stelle wieder vorkommt? Leider lässt sich danach nur schlecht suchen. Insgesamt bietet die deutsche Spache über 800 Wörter, die 6 Zeichen lang sind. Es ist definitiv zu aufwändig, sie alle durchzusehen.

    Ganz allgemein stellt sich die Frage, welche Art von Texten denn normalerweise nur Wörter enthalten, die mit dem gleichen Anfangsbuchstaben beginnen? Ein Zungenbrecher vielleicht?

    Natürlich kann man sich auch diesem Problem mit Statistik nähern. Zählt man wieder die Vorkommen aller Buchstaben im verschlüsselten Text, erhält man das folgende Ergebnis:

    • 'G': 8
    • 'Q': 6, 'F': 6, 'Z': 6, 'Y': 6
    • 'P': 4, 'W': 4, 'J': 4, 'N': 4
    • 'I': 2

    Jedes 'G' wäre also vermutlich ein 'E'. 'G' und 'E' liegen im Alphabet 2 Zeichen auseinander. Also muss jedes Zeichen zum Entschlüsseln um 2 Zeichen zurück verschoben werden:
    'G' = 'E':

    EODXNUDXW EOHLEW EODXNUDXW, EUDXWNOHLG EOHLEW EUDXWNOHLG.

    Das ist es nicht. 'G' ist im Text wohl auch nur der häufigste Buchstabe, weil jedes Wort damit beginnt. Es ist also davon auszugehen, dass eine statistische Analyse schwierig wird, da hier bewusst Wörter ausgewählt wurden. Deren Buchstabenhäufigkeit wird womöglich nicht genau so aussehen, wie man es normalerweise bei deutschen Texten erwarten würde.

    Zum Glück gibt es noch mehr Buchstaben die häufig vorkommen, vielleicht klappt es ja mit denen:

    'Q' = 'E':

    UETNDKTNM UEXBUM UETNDKTNM, UKTNMDEXBW UEXBUM UKTNMDEXBW.

    'F' = 'E':

    FPEYOVEYX FPIMFX FPEYOVEYX, FVEYXOPIMH FPIMFX FVEYXOPIMH.

    'Z' = 'E':

    LVKEUBKED LVOSLD LVKEUBKED, LBKEDUVOSN LVOSLD LBKEDUVOSN.

    'Y' = 'E':

    MWLFVCLFE MWPTME MWLFVCLFE, MCLFEVWPTO MWPTME MCLFEVWPTO.

    Schade, das war nichts.

    Tatsächlich wird man aber beim 'J' fündig, das an 8. Stelle steht.
    'J' = 'E':

    BLAUKRAUT BLEIBT BLAUKRAUT, BRAUTKLEID BLEIBT BRAUTKLEID.

    Jetzt wird auch klar, warum der Versuch mit dem 'E' wenig Erfolg hatte. Die häufigsten Buchstaben im Text sind 'B', 'L', 'A' und 'U'.
    Dennoch konnte innerhalb von 8 Versuchen auf das Passwort geschlossen werden.


    3. Knacken der Polybios-Chiffre

    Ist ein Text mit der Polybios-Chiffre verschlüsselt, gestaltet sich das Knacken etwas schwieriger. Das liegt daran, dass nicht direkt auf das Passwort geschlossen werden kann, wenn ein Buchstabe entschlüsselt wurde. Jeder einzelne Buchstabe muss separat geknackt werden, um auf die 6x6-Passworttabelle schließen zu können. Kontext wird hier also sehr wichtig. Und es wird einfacher, je länger der zu knackende Text ist, da man dann mit den Buchstabenhäufigkeiten arbeiten kann.

    Ein Beispiel:

    14 12 22 15 25 16 33 33 25 41 24 25 11 32 34 35 26 14 34 13 14 43 11 24 22 12 42 42 24 16 25 26 12 25 43 42 15 25 43 11 15 25 11 21 12 11 52 21 22 25 16 13 14 45 12 42 33 12 11 24 16 41 42 12 21 15 22 12 42 42 24 16 13 14 11 16 13 14 15 16 11 45 43 15 23 41 16 11 21 25 11 44 25 41 42 43 13 14 25 52 43 41 12 23 45 25 13 14 42 22 43 11 21 25 16 11 33 12 22 33 16 15 24 25 33 32 34 35 26 52 43 32 12 25 33 35 26 25 11 25 41 16 42 15 21 12 11 52 21 43 15 23 25 16 25 16 11 12 11 24 25 41 12 43 13 14 45 25 11 11 25 41 11 16 13 14 15 22 25 41 11 25 11 45 16 22 22

    Ab diesem Zeitpunkt kann es sinnvoll werden, einen Computer zur Berechnung der Häufigkeiten zu verwenden. Excel kann das ganz gut, mit Bleistift und Papier geht es aber auch. Hier das Ergebnis einer Pivot-Tabelle:
    2020-06-09_16-41.png

    Die häufigsten Zeichen sind also '25', '11', '16' und '12'. Ersetzt man die Ziffern durch ihre wahrscheinlichen Klartextbuchstaben erhält man:

    14 S 22 15 E I 33 33 E 41 24 E N 32 34 35 26 14 34 13 14 43 N 24 22 S 42 42 24 I E 26 S E 43 42 15 E 43 N 15 E N 21 S N 52 21 22 E I 13 14 45 S 42 33 S N 24 I 41 42 S 21 15 22 S 42 42 24 I 13 14 N I 13 14 15 I N 45 43 15 23 41 I N 21 E N 44 E 41 42 43 13 14 E 52 43 41 S 23 45 E 13 14 42 22 43 N 21 E I N 33 S 22 33 I 15 24 E 33 32 34 35 26 52 43 32 S E 33 35 26 E N E 41 I 42 15 21 S N 52 21 43 15 23 E I E I N S N 24 E 41 S 43 13 14 45 E N N E 41 N I 13 14 15 22 E 41 N E N 45 I 22 22

    Das sieht weder sehr falsch, noch sehr richtig aus. Übliche Kombinationen aus 'E', 'N' und 'I' lassen sich aber schon ausmachen wie "EIN", wobei das nicht sonderlich schwer ist. Schwer wird nun die korrekte Zuordnung der restlichen Buchstaben. Das braucht vor allem eines: Geduld. Die Hauptarbeit besteht nun darin mögliche Kandidaten auszuprobieren und zu sehen, ob dabei entstehende Zeichenfolgen Sinn ergeben. Vor allem die Ziffern '14', '15', '42' und '43' werden etwas Knobelarbeit bedeuten, da sie gleich oft vorkommen, aber dennoch ziemlich häufig und damit wichtig sind. Natürlich hält sich auch nicht jeder so kurze Text an die übliche Buchstabenhäufigkeit.

    So wird sich zum Beispiel herausstellen, dass '12' kein 'S' ist, sondern ein 'A'. Nach ein paar Minuten Knobelarbeit zeigt sich außerdem: '14' ist ein 'H', '15' ist ein 'T', '42' ist das 'S' und '43' ist ein 'U'. Damit ergibt sich:

    H A 22 T E I 33 33 E 41 24 E N 32 34 35 26 H 34 13 H U N 24 22 A S S 24 I E 26 A E U S T E U N T E N 21 A N 52 21 22 E I 13 H 45 A S 33 A N 24 I 41 S A 21 T 22 A S S 24 I 13 H N I 13 H T I N 45 U T 23 41 I N 21 E N 44 E 41 S U 13 H E 52 U 41 A 23 45 E 13 H S 22 U N 21 E I N 33 A 22 33 I T 24 E 33 32 34 35 26 52 U 32 A E 33 35 26 E N E 41 I S T 21 A N 52 21 U T 23 E I E I N A N 24 E 41 A U 13 H 45 E N N E 41 N I 13 H T 22 E 41 N E N 45 I 22 22

    Übung 6: Kannst du so auf den Rest schließen?


    4. Zusammenfassung und Ausblick

    Du hast nun gelernt monoalphabetische Substitutionsverfahren mithilfe von Buchstabenhäufigkeiten zu knacken. Du kannst also anhand wahrscheinlicher Kartextzeichen und Wörter auf den Rest des Textes schließen. Diese Art von Angriff nennt man auch "Probable Plaintext Attack". Auch die Enigma, die im Zweiten Weltkrieg zur Verschlüsselung des Nachrichtenverkehrs der Wehrmacht verwendet wurde, wurde so geknackt (auch wenn das natürlich nochmal deutlich komplexer war).

    Wenn du mehr über derartige Angriffe lernen möchtest, kannst du dich hier einlesen:

    Bei Fragen kannst du dich natürlich jederzeit an uns wenden.
    Wenn du möchtest, kannst du dein Können hier unter Beweis stellen und Punkte sammeln! 🎓


    Lösungen der Übungen

    Übung 1:

    Pfnxjw Fzlzxyzx ajwbjsijyj ifx Ajwkfmwjs

    Übung 2:

    symmetrisches Verschluesselungsverfahren

    Übung 3:

    11 42 52 36 13 35 24 42 12 36 25 26 43 21 25 15 43 26 21 25 15 42 25 15 26 13

    Übung 4:

    Kodierung mit Fackeln

    Übung 5:

    ICH BIN LEICHT ZU KNACKEN

    Übung 6:

    „Halte immer den Kopf hoch und lass die Fäuste unten. Ganz gleich, was man dir sagt, lass dich nicht in Wut bringen. Versuche zur Abwechslung einmal mit dem Kopf zu kämpfen… er ist ganz gut beieinander, auch wenn er nicht lernen will.“


    6. Quellen und Links



Anmelden zum Antworten