Brechen der Substitutionsverschlüsselung
Dieser Onlinerechner versucht die Substitutionverschlüsselung zu dekodieren, ohne den Schlüssel zu kennen. Er nutzt den genetischen Algorithmus über die Text-Fitnessfunktion, um den verschlüsselten Text zu brechen.
Diese Webseite exisiert dank der Arbeit von den folgenden Menschen:
 | Timur
|
Stefan Roesner
|
Der untenstehende Rechner versucht den mit einer Substitution verschlüsselten Text automatisch zu entschlüsseln, ohne den Schlüssel zu kennen. Die Logik des Rechners wird weiter unten erklärt.
Bitte beachten Sie, dass dieser Rechner nur mit englischen verschlüssekten Texten funktioniert.
Brechen der Substitutionsverschlüsselung
In der Kryptographie versteht man unter der Substitutionsverschlüsselung ein Verfahren, indem ein Klartext durch einen Verschlüsselungstext nach einem fixen System ersetz wird: die „Einheit“ kann ein einzelner Buchstabe (häufigste Art), ein Buchstabenpaar, eine Reihe von 3 Buchstaben, eine Mischung von den obigen usw. bestehen. Der Empfänger entschlüsselt den Text durch eine inverse Substitution. Die separate Substitution von einzelnen Buchstaben — einfache Substitution — kann man beweisen, indem man das Alphabet in einer gewissen Reihenfolge schreibt, um die Substitution darzustellen. Es ist ein Chiffre-Schlüssel, den man auch als Substitutionsalphabet bezeichnet. 1
Für eine einfache Substitutionsverschlüsselung ist der Satz von allem möglichen Schlüssel gleich des Satz aller möglichen Vertauschungen. Das heißt für das englische Alphabet ist die Anzahl der Schlüssel 26! (Faktorisierung von 26), was ungefähr ist. Daher ist die Brute-Force-Methode für die Entschlüsselung ohne Schlüssel nicht nutzbar.
Jedoch gilt die Substitutionsverschlüsselung allgemein als die schwächste Verschlüsselung, da sie anfällig ist für die Kryptoanalyse. Erstens ändert sich bei der Substitution die Frequenz der Buchstaben nicht. Das heißt, wenn man eine gewisse Anzahl von verschlüsselten Texten hat und die genutzte Sprache kennt, kann man eine Frequenzanalyse durchführen. In der Englischen Sprache ist zum Beispiel das E der häufigste genutzte Buchstabe, was bedeutet das der häufigste genutzte Buchstabe im verschlüsselten Text wahrscheinlich die Substitution für das E ist. Analysten beachten aber auch die Frequenzen von Bigrammen und Trigrammen, da einige Monogramm-Frequenzen zu ähnlich sind, um sich darauf zu verlassen. Anhand von Frequenzen kann ein Analyst mehrere Schlüssel erstellen und testen, um dann zu bestimmen, ob diese einzelne Wörter und Phrasen aufdeckt.
Aber dieses Verfahren ist sehr Zeit-intensive, daher ist das Ziel der automatischen Lösung, jegliche menschliche Tätigkeit vom Brechen der Verschlüsselung zu entfernen. Und dies ist dank einer weiteren Schwäche der Substitutionsverschlüsselung möglich – und zwar der Nützlichkeit einer Teillösung.
In other words, if there are many pairs of keys in the keyspace where the decryption of the ciphertext by the key more similar to the correct key more closely resembles the plaintext than the decryption of the ciphertext by the other key, the cipher has Utility of Partial Solutions... If there is a correlation between the degree to which a key resembles the correct key and the degree to which that key's decryption of the ciphertext resembles the plaintext, it should be possible to search the keyspace efficiently by quickly discarding keys that are "worse" than whatever key is the closest match at any moment, climbing ever closer to the optimal key without knowing it initially. More specially, these keyspaces can be searched via Stochastic Optimization Algorithms.2
Der schwierige Teil hier ist, wie man messen kann, ob ein Schlüssel schlechter ist als ein anderer. Um dies zu lösen, benötigen wir „Textfitness“. Dieses Verfahren gibt eine Art von Punkten an, um anzuzeigen ob der Text wie ein typischer englischer Text aussieht. Es gibt dafür verschiedene Optionen, und ich habe diese and jene ausprobiert. Aber das Verfahren, das am besten für mich gearbeitet hat, ist: Text fitness (version 3). Diese Option nutzt die Summe von der Logarithmus-Wahrscheinlichkeit von Tetragraph, und vergleicht dies mit der Summe des „normalen“ englischen Text (kreiert als Logarithmus-Wahrscheinlichkeit für die häufigsten englischen Tetragraphen. Hier möchte ich mich bei Jens Guballa (Seite), Autor einer anderen Substitution-Lösung, bedanken, der mir freundlicherweise den Tipp gegeben hat, die Textfitness-Funktion zu normalisieren.
Der Rechner nutzt den genetischen Algorithmus, um den korrekten Schlüssel zu finden. Falls dies nicht funktioniert, kann man es mehrmals wiederholen (jedes Mal fängt der Rechner mit einem Satz von beliebigen Schlüsseln an) oder man ändert ein wenig die Einstellung, zum Beispiel die Anzahl von Schlüsselerzeugungen. Wählen Sie einfach „Details“ aus, um die weiteren Einstellungen zu sehen. In diesem Modus zeigt der Rechner den besten Schlüssel für jede Möglichkeit an, was sehr interessant sein kann.
Falls Sie einen Schlüssel gefunden haben, der dem korrekten Schlüssel sehr nahe ist, aber einige Buchstaben ändern wollen, können Sie den Substitutionsverschlüsselung Rechner verwenden, um den Schlüssel manuell zu testen.
Kommentare