Substitution Ciphers

Polyalphabetic substitution

Monoalphabetische Verschlüsselungen einer natürlichen Sprache haben den Nachteil, dass sie aufgrund der Häufigkeitsverteilung (Entropie) der Sprache leicht entschlüsselt werden können.

Bei der polyalphabetischen Verschlüsselung werden gleiche Plaintexte bzw. Klartexte (P) in unterschiedliche Chiffretexte (C) umgewandelt. Ein solches Verfahren wurde u.a. von Blaise de Vigenère (1523-1585) entwickelt.

Beispiel:
asdf -> modf
asdf -> eirf
asdf -> uqld

Vigenère Chiffre

Bei dem Vigenère-Verfahren wird jeder Klartextbuchstabe mit einem anderen Alphabet verschlüsselt. Das jeweilige Alphabet ergibt sich durch das Schlüsselwort, dieses kann im Falle des einfachen Vigenère-Chiffre aus wenigen Zeichen oder im Falle des running-key Vigenère (Gronsfeld Variante) aus Zahlen der Fibonacci-Nummern (K(X) = K(X-N)+ K(X-N+1)) bestehen.

Es gibt noch weitere Varianten des Vigenère-Chiffre, einige variieren die Verwendung des Schlüssels (Gronsfeld, Gromark) andere verwenden leicht veränderte Algorithmen (Beaufort). Ich gehe zuerst auf den klassischen Vigenère Algorithmus ein:

Der klassische Vigenère Algorithmus

Sender und Empfänger vereinbaren ein Schlüsselwort und benutzen zum Ver- und Entschlüsseln das Vigenère-Quadrat, wie es rechts zu sehen ist. Das Verschlüsseln verläuft wie folgt:

Schlüsselwort: geheim, Operations-Modus: Repetitive Key

Key K:          geheimgeh
Klartext P:     hallowelt
Chiffretext C:  nespwikpa

Um z.B. den Buchstaben 'h' mit dem Schlüssel 'g' zu codieren, sucht man im Vigenère-Quadrat die Spalte 'h' und Zeile 'g' und findet als Chiffrezeichen 'n'. Es wird also jeder Klartextbuchstabe, um einen Betrag welcher der Position des entsprechenden Schlüsselwortzeichens entspricht, verschoben.

Das Verschieben über die Grenzen des Alphabets lässt sich wie bei den anderen Chiffren elegant durch die Modulo-Operation formalisieren. K ist das Schlüsselwort der Länge k, dargestellt als Vektor (1 Dim. Matrix), V ist das Vigenère-Quadrat (2 Dim. Matrix) und z die Nummer des zu codierenden Zeichens im Alphabet sowie i die Position von z im Klartext. Es gilt:

E(z, i) = (z + K_mod(k)*i) mod n = V(z, K_mod(k)*i),

wobei n die Länge des Alphabets ist. Durch diesen Formalismus lässt sich die Vigenère-Codierung effizient implementieren.

Varianten

Der Beaufort-Chiffre benutzt einen einfach abgewandelten Algorithmus von Vigenère, hier im Vergleich:

   Chiffre    Verschlüsselung    Entschlüsselung
   Vigenère:  C = P + K          P = C - K
   Beaufort:  C = K - P          P = K - C
   Variante:  C = P - K          P = C + K        (Vigenère umgedreht)

Die anderen Varianten benutzen keinen veränderten Algorithmus, sondern wie oben schon erwähnt andere Schlüssel, die aus Buchstaben und Zahlen bestehen können. Der Gronsfeld Chiffre benutzt dafür die Fibonacci-Zahlen, der Gromark Chiffre verwendet Buchstaben und Zahlen vermischt. Dann gibt es noch die Variante mit binärem Alphabet, die mit XOR arbeitet oder eine Variante, wo K genauso lang ist wie P. Diese nennt man One Time Pad und ist prinzipiell unknackbar, wenn sie perfekt angewandt wird, was allerdings in der Praxis unmöglich ist. Bruce Schneier dazu im Counterpane 10.2002.

Operations-Modi bei der Verwendung des Schlüssels

- Sich wiederholender Schlüssel (Repetitive Key)
Die "klassische" Art den Schlüssel zu verwenden. Der Schlüssel wiederholt sich einfach selber:
Aus "geheim" wird K = "geheimgeheimgeheim...".

- Schlüssel Fortsetzung (Key Progression)
Der Schlüssel wiederholt sich selbst, jedoch jeweils mit dem nachfolgenden Buchstaben im Alphabet:
Aus "geheim" wird K = "geheimhfifjnigjgkojhkhlpkilimq...".

- Autoclave
Der Schlüssel wird einmal benutzt, dann folgt einfach der Klartext der uncodierten Nachricht:
Aus "geheim" und P = "hallowelt" wird K = "geheimhal".

Implementation

Eine mögliche Implementation in C mit den drei Operations-Modi.

Von mir schnell in die Tasten gehackt. Quellcode ist wie immer unter der GPL lizensiert.