Vigenère-Verfahren
Das Vigenère-Verfahren verschiebt nicht alle Buchstaben um denselben Wert, sondern wechselt die Verschiebung von Buchstabe zu Buchstabe nach einem Schlüsselwort. Rund dreihundert Jahre lang galt es als unbrechbar.
Definition
Das Vigenère-Verfahren ist ein symmetrisches Verschlüsselungsverfahren. Der Schlüssel ist ein Wort aus [math]\displaystyle{ l }[/math] Buchstaben. Das Schlüsselwort wird unter den Klartext geschrieben und so oft wiederholt, bis unter jedem Klartextbuchstaben ein Schlüsselbuchstabe steht. Jeder Klartextbuchstabe wird dann mit der Caesar-Verschlüsselung verschoben, und zwar um den Wert des Schlüsselbuchstabens, der unter ihm steht (A = 0, B = 1 und so weiter bis Z = 25).
Der Text wird vorher wie bei der Caesar-Verschlüsselung vorbereitet: nur die Großbuchstaben A bis Z, ohne Leerzeichen und Satzzeichen.
Mit einem Schlüsselwort aus einem einzigen Buchstaben ist das Vigenère-Verfahren eine Caesar-Verschlüsselung.
Vigenère-Quadrat
Das Vigenère-Quadrat (auch Vigenère-Tabelle) enthält in 26 Zeilen alle 26 verschobenen Alphabete. Die Zeile eines Schlüsselbuchstabens beginnt mit diesem Buchstaben.
- Verschlüsseln: Die Spalte des Klartextbuchstabens und die Zeile des Schlüsselbuchstabens aufsuchen. Im Schnittpunkt steht der Geheimtextbuchstabe.
- Entschlüsseln: In der Zeile des Schlüsselbuchstabens den Geheimtextbuchstaben suchen. Über der Spalte steht der Klartextbuchstabe.
Rechnen mit Buchstabenwerten
Die Buchstaben des Klartextes haben die Werte [math]\displaystyle{ m_0; m_1; m_2; \dots }[/math], die des Geheimtextes die Werte [math]\displaystyle{ c_0; c_1; c_2; \dots }[/math], die des Schlüsselwortes die Werte [math]\displaystyle{ k_0; k_1; \dots; k_{l-1} }[/math]. Dann gilt für den Buchstaben an der Stelle [math]\displaystyle{ i }[/math]:
- [math]\displaystyle{ c_i = (m_i + k_j) \bmod 26 \quad \text{mit } j = i \bmod l }[/math]
- [math]\displaystyle{ m_i = (c_i - k_j) \bmod 26 }[/math]
Der Index [math]\displaystyle{ j = i \bmod l }[/math] sorgt dafür, dass das Schlüsselwort nach [math]\displaystyle{ l }[/math] Buchstaben von vorn beginnt. Gezählt wird ab 0. Das Rechnen mit Resten erklärt der Artikel Modulo.
Polyalphabetische Substitution
Das Vigenère-Verfahren ist eine polyalphabetische Substitution: Es verwendet nicht ein Geheimtextalphabet, sondern so viele verschiedene, wie das Schlüsselwort verschiedene Buchstaben hat. Welches gilt, hängt von der Stelle im Text ab.
- Derselbe Klartextbuchstabe wird durch verschiedene Geheimtextbuchstaben ersetzt, je nachdem, auf welchen Schlüsselbuchstaben er trifft.
- Derselbe Geheimtextbuchstabe kann für verschiedene Klartextbuchstaben stehen.
Dadurch gleichen sich die Häufigkeiten der Geheimtextbuchstaben an. Die einfache Häufigkeitsanalyse, mit der sich jede monoalphabetische Substitution in einem längeren Text brechen lässt, scheitert.
Kryptoanalyse
Der Schlüsselraum enthält bei einem Schlüsselwort aus [math]\displaystyle{ l }[/math] Buchstaben [math]\displaystyle{ 26^l }[/math] Schlüssel. Bei einem langen Schlüsselwort ist das Ausprobieren aller Schlüssel aussichtslos. Gebrochen wird das Verfahren dann über seine Schwachstelle: Das Schlüsselwort wiederholt sich.
Kasiski-Test
Gleiche Klartextstücke, die auf dieselbe Stelle des Schlüsselwortes treffen, ergeben gleiche Geheimtextstücke. Der Abstand solcher Wiederholungen ist ein Vielfaches der Schlüssellänge. Der Kasiski-Test bestimmt daraus die Schlüssellänge [math]\displaystyle{ l }[/math]. Eine Schätzung liefert auch der Friedman-Test.
Häufigkeitsanalyse
Ist die Schlüssellänge [math]\displaystyle{ l }[/math] bekannt, zerlegt man den Geheimtext in [math]\displaystyle{ l }[/math] Teiltexte: Jeder Teiltext enthält die Buchstaben, die mit demselben Schlüsselbuchstaben verschlüsselt wurden. Jeder Teiltext ist eine Caesar-Verschlüsselung und wird mit der Häufigkeitsanalyse gebrochen.
Brute-Force-Angriff
Bei einem kurzen Schlüsselwort lassen sich auch alle [math]\displaystyle{ 26^l }[/math] Schlüssel durchprobieren. Mit jedem weiteren Buchstaben wächst der Schlüsselraum auf das 26-fache, ein langes Schlüsselwort verhindert deshalb diesen Angriff.
Varianten
Schlüssel mit dem Klartext fortsetzen
Bei dieser Variante (englisch: autokey) wird das Schlüsselwort nicht wiederholt. Nach dem letzten Buchstaben des Schlüsselwortes geht der Schlüssel mit dem Klartext selbst weiter. Der Schlüssel ist dadurch so lang wie die Nachricht und wiederholt sich nicht, der Kasiski-Test findet keinen Ansatz.
Die Variante hat eigene Schwächen: Der Schlüssel besteht aus lesbarem Text mit den Häufigkeiten der Sprache. Wer ein Wort des Klartextes errät, kennt damit ein Stück des Schlüssels. Außerdem pflanzt sich ein Übertragungsfehler fort: Ein falsch entschlüsselter Buchstabe dient eine Schlüsselwortlänge später selbst als Schlüsselbuchstabe und verfälscht dort den Klartextbuchstaben. Dieser dient wieder als Schlüsselbuchstabe, so setzt sich der Fehler bis zum Ende des Textes fort.
One-Time-Pad
Ist der Schlüssel zufällig, so lang wie die Nachricht und wird er nur ein einziges Mal verwendet, entsteht das One-Time-Pad. Es lässt sich nicht brechen.
Umsetzung in Java
Die Methode setzt voraus, dass Text und Schlüsselwort nur aus Großbuchstaben bestehen. Der Ausdruck i % schluessel.length() ist der Index [math]\displaystyle{ j = i \bmod l }[/math] aus der Formel.
public static String vigenere(String text, String schluessel) {
String ergebnis = "";
for (int i = 0; i < text.length(); i++) {
int wert = text.charAt(i) - 'A';
int verschiebung = schluessel.charAt(i % schluessel.length()) - 'A';
ergebnis = ergebnis + (char) ((wert + verschiebung) % 26 + 'A');
}
return ergebnis;
}
Beispiele
Mit dem Vigenère-Quadrat verschlüsseln
Der Klartext TREFF ENUMA CHTAM HAFEN wird mit dem Schlüsselwort ROSE verschlüsselt. Das Schlüsselwort wird so oft wiederholt, bis unter jedem Klartextbuchstaben ein Schlüsselbuchstabe steht:
| Klartext | T | R | E | F | F | E | N | U | M | A | C | H | T |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Schlüssel | R | O | S | E | R | O | S | E | R | O | S | E | R |
| Geheimtext | K | F | W | J | W | S | F | Y | D | O | U | L | K |
| Klartext | A | M | H | A | F | E | N |
|---|---|---|---|---|---|---|---|
| Schlüssel | O | S | E | R | O | S | E |
| Geheimtext | O | E | L | R | T | W | R |
Erster Buchstabe: In der Spalte T und der Zeile R des Vigenère-Quadrats steht K. So entsteht Buchstabe für Buchstabe der Geheimtext KFWJW SFYDO ULKOE LRTWR.
Mit Buchstabenwerten entschlüsseln
Der Geheimtext JCEQV FXIJH wurde mit dem Schlüsselwort ROSE verschlüsselt. Für jeden Buchstaben wird [math]\displaystyle{ m_i = (c_i - k_j) \bmod 26 }[/math] berechnet:
| Geheimtext | J | C | E | Q | V | F | X | I | J | H |
|---|---|---|---|---|---|---|---|---|---|---|
| Wert | 9 | 2 | 4 | 16 | 21 | 5 | 23 | 8 | 9 | 7 |
| Schlüssel | R | O | S | E | R | O | S | E | R | O |
| Wert | 17 | 14 | 18 | 4 | 17 | 14 | 18 | 4 | 17 | 14 |
| Differenz mod 26 | 18 | 14 | 12 | 12 | 4 | 17 | 5 | 4 | 18 | 19 |
| Klartext | S | O | M | M | E | R | F | E | S | T |
Erster Buchstabe: [math]\displaystyle{ (9 - 17) \bmod 26 = -8 \bmod 26 = 18 }[/math]. Das Ergebnis 18 steht für S. Der Klartext lautet SOMME RFEST.
Polyalphabetische Ersetzung erkennen
Gezählt wird hier ab 1, das erste Zeichen des Textes hat die Position 1. Im ersten Beispiel kommt der Klartextbuchstabe F 3-mal vor:
- an Position 4 wird er zu
J - an Position 5 wird er zu
W - an Position 18 wird er zu
T
Umgekehrt steht der Geheimtextbuchstabe F für verschiedene Klartextbuchstaben:
- an Position 2 steht er für
R - an Position 7 steht er für
N
Deshalb ist das Vigenère-Verfahren polyalphabetisch. Bei einer monoalphabetischen Substitution wäre beides nicht möglich.
Klartext als Fortsetzung des Schlüssels verwenden
Der Klartext SOMME RFEST wird mit dem Schlüsselwort ROSE verschlüsselt. Nach dem Schlüsselwort geht der Schlüssel mit dem Klartext selbst weiter:
| Klartext | S | O | M | M | E | R | F | E | S | T |
|---|---|---|---|---|---|---|---|---|---|---|
| Schlüssel | R | O | S | E | S | O | M | M | E | R |
| Geheimtext | J | C | E | Q | W | F | R | Q | W | K |
Der Geheimtext lautet JCEQW FRQWK. Beim Entschlüsseln liefern die ersten 4 Buchstaben mit dem Schlüsselwort den Klartextanfang SOMM. Dieser Klartextanfang ist der Schlüssel für die nächsten Buchstaben, und so geht es weiter bis zum Ende.