Rechnernetze

Chiffren mit polyalphabetischer Substitution

Als polyalphabetische Substitutionschiffren bezeichnet man Chiffren, die die Häufigkeitsverteilung einzelner Buchstaben verbergen, indem sie verschiedene Substitutionen benutzen. Dabei werden die Buchstaben m_i des Klartextes H durch die Buchstaben c_ij, j=0..n-1, aus verschiedenen Alphabeten C₀, C₁,...,C_n-1 ersetzt; wir schreiben im folgenden C_j(m_i), wenn der i-te Buchstabe m_i eines Klartexts mit jenem Zeichen kodiert wird, das dem Zeichen m_i in dem Alphabet C_j zugeordnet ist. Bei einigen Chiffren, den sogenannten periodischen polyalphabetischen Substitutionschiffren, werden die Alphabete in einer festen Reihenfolge verwendet; nach dem letzten Alphabet wird wieder das erste Alphabet benutzt usw. Es ist also j = i mod n.

Ein Klartext m = m₀ m₁ m₂ … m_i m_i+1 … wird chiffriert durch

E(m) = C₀(m₀) C₁(m₁) C₂(m₂) … C_{i modn}(m_i) C_{i+1 modn}(m_i+1) …

Durch diese Art der Verschlüsselung wird dem Kryptoanalytiker die Möglichkeit genommen, durch eine einfache Häufigkeitsanalyse den Chriffretext zu entschlüsseln; es müssen wesentlich kompliziertere Verfahren angewendet werden. Eine große Hilfe ist dabei die Kenntnis der Anzahl der verwendeten Alphabete, zu deren Bestimmung verschiedene Techniken entwickelt worden sind. Eine Technik bedient sich dabei der Eigenschaft, dass gewisse Buchstabenkombinationen in den natürlichen Sprachen sehr viel häufiger auftreten als andere. Der Kryptoanalytiker kann – falls ein sehr langer Text vorliegt – bestimmte wiederkehrende Kombinationen von Buchstaben erkennen und so zunächst auf die Anzahl der verwendeten Alphabete schließen. Diese Methode zur Entschlüsselung periodischer polyalphabetischer Substitutionschiffren wurde 1863 von dem Preußischen Offizier Friedrich W. Kasiski veröffentlicht. Nachdem die Periode n der Alphabete bekannt ist, kann die Entschlüsselung nach dem bereits vorgestellten Verfahren zur Entschlüsselung einfacher Substitutionschiffren durchgeführt werden, indem jeweils mit den n-ten Chiffretextzeichen eine Häufigkeitsanalyse durchgeführt wird.

In der Vigenère Chiffre (de Vigenère 1523 - 1596, nach Ideen von Cardano) betrachtet man den Klartext – wie bei der Caesar Chiffre – als eine Folge der Zahlen 0, ..., 25. Ein vom Sender und Empfänger vereinbarter Schlüssel K = k1 ... kn (Folge von Buchstaben), wobei k_i (1 < i < n) die Größe des Shiftes im i-ten Alphabet angibt, wird dann gliedweise modulo 26 auf die Klartextfolge addiert (f_i(m) = (m + k_i) mod 26). Im nächsten Beispiel wird für die Chiffrierung jeweils das gleiche Alphabet verwendet.

Ein Angriff auf diese Chiffre lässt sich einfach durchführen, wenn ein Wort aus dem Klartext bekannt ist. Wird zum Beispiel vermutet, dass das Wort 'Anfang' in dem Klartext vorhanden ist, so lässt sich einfach ausprobieren.

Ein weiteres Verfahren, um Chiffren mit periodischer Substitution zu analysieren (d.h. die Periode zu bestimmen), ist die Koinzidenzindex-Methode. Bei dieser Methode wird die Variation der Häufigkeit der Buchstaben in einem Chiffretext gemessen. Wird in einem Substitutionschiffre nur ein Alphabet verwendet, so wird eine große Streuung der Häufigkeit der einzelnen Buchstaben (Koinzidenzindex) festgestellt; sind jedoch alle Buchstaben zufällig verteilt, weil für jeden Buchstaben ein eigenes, zufälliges Alphabet gewählt wird, so ist jeder Buchstabe gleichwahrscheinlich, die Streuung der Buchstabenhäufigkeiten also null. Daher ist durch eine Analyse der Häufigkeiten der Buchstaben eine Aussage über die Periode einer Chiffre möglich. Bei einem Angriff wird zunächst die Varianz der Häufigkeit der Buchstaben relativ zu einer gleichmäßigen Verteilung gemessen.

Besteht die Chiffre aus zwei Alphabeten, so lässt sich zeigen, dass die Varianz nur halb so groß ist wie die Varianz eines Alphabets, welche in der Regel bekannt ist. Entsprechend lässt sich die Varianz mehrere Alphabete bestimmen und mit der gemessenen Varianz des Chiffretexts vergleichen. Aus diesen Werten lässt sich dann abschätzen, wie viele Alphabete verwendet werden und daraus dann eine Häufigkeitsanalyse für die jeweiligen Zeichen durchführen