2.8 – Polyalphabetische Chiffre: Vigenère-Chiffre

2.8.1 Definition

Sei $\Sigma = \left\{ {A, \ldots ,Z} \right\}$ das Alphabet bestehend aus den 26 Großbuchstaben, sei $m \in \mathbb{N}$ die Länge des Klar- und Geheimtextes, sei $l \in \mathbb{N}$ die Länge des Schlüsselwortes. Die Zeichen des Klartextes $p \in \mathcal{P},p = \left( {{p_1}, \ldots ,{p_m}} \right)$ , des Geheimtextes $c \in \mathcal{C},c = \left( {{c_1}, \ldots ,{c_m}} \right)$ und des Schlüsselwortes $k \in \mathcal{K},k = \left( {{k_1}, \ldots ,{k_l}} \right)$ werden mit der Abbildung $f:\Sigma \to {\mathbb{Z}_n}$ kodiert. Klartext und Geheimtext werden in Blöcke der Länge $l$ unterteilt.

Verschlüsselung:

$\left( {{c_1}, \ldots ,{c_l}} \right) = \left( {{p_1}+{k_1}, \ldots ,{p_l}+{k_l}} \right)$

Entschlüsselung:

$\left( {{p_1}, \ldots ,{p_l}} \right) = \left( {{c_1}-{k_1}, \ldots ,{c_l}-{k_l}} \right)$

Beispiel:

Um das Verfahren zu veranschaulichen, verwenden wir folgendes Raster:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
---------------------------------------------------
B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
Z A B C D E F G H I J K L M N O P Q R S T U V W X Y
X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
Y Z A B C D E F G H I J K L M N O P Q R S T U V W X

$p = ANGRIFF,\quad k = KRYPTO$

Für das erste Zeichen verschlüsseln wir das A mit dem K aus dem Schlüssel. Dazu benutzen wir die Spalte mit dem A und die Zeile mit dem K. Wir erhalten ein K. Für die anderen Buchstaben folgt:

$c = KEEGBTP$

2.8.2 Kasiski-Angriff

Zum Brechen der Chiffre kann der Kasiski-Angriff verwendet werden.

Als Beispiel betrachten wir den nachfolgenden Geheimtext.

--01234567890123456789012345678901234567890123456789--
0-SDQTIHODZTKOMYROXVXYSCWSBKYRAHEEBOPOXQGVOSBCGTLGNV-0
1-PVKCOJQIXAKKFTFODZITKROJJPGROJXJFSBJRTGAKCQTBHTRFG-1
2-XBCVGCXVOZKPMGDRBINAKDBTNHCTFTGBKKSGYCBJAWXFUFLVKS-2
3-CJGCUSBCGCMSSCXJGSRDCCLSVSQIOSBJRPXBNCGRAKYCJIXSBE-3
4-GRAHNFPIAWXDMCTHOCYCZVKKRTXFCZAWZSGVGVXFDRZTKOVVVP-4
5-GROITDGVEDZDERDNYGAOBKLPXQUZEVXPVZCQXBLZQTKWXVGCXA-5
6-CTFLTQRVLBHAOERJGRSEBTKVYWDCNBQUCGMOQBYTFSXZCONUOJ-6
7-YVMVKKRTGIXRJHHJOIQIXQUKCHBQRGPDYSCJMGZOEJQXFPOKRP-7
8-EGWZLCTWREYJYTYIBTKHORSUSICKCWXBNZCZNHCTFTPOBKCJGR-8
9-NVPLXUCVGLXWDBJPFAOIRTXFCZAWTBCBGHLSXLLSOSBJSRAHOJ-9
0-CXGSPIYJSIWMCGLQRNGCWSXQSQKWXXCCBBNVKTKRSVYJZSXJAW-0
1-ECCJYALSBJGTPWOUCGHSPWLTMSEEBBBBXRGBFSBEMRARKNYGGO-1
2-XERTXFCZCATSCKGVUSCTFGTSXBRJGRNRQJGUVLCRDGOZLTKGZR-2
3-CIXBTRFGXRKRSRARKJLXVVDYYAYGDICXYHOVPSBSNVAZXOLLLS-3
4-LSDQRTWWOWSTLGORSUWSXSMSXBQIGBFWQLLSGCDUSTKTDZEVXK-4
5-KJAWXBQZLVXFNZCIKSZGCWBBEERTKWWNMWGNSDKTKKKIRTMSCV-5
6-GCLCRECJZSXDGIZSZRAZMSBICXLSDRQRASKCQVTICJGWGGKYZT-6
7-DOWVPTBBOEUJMOXWYAESBQCGUFKTFTBBOEYJYRODDTGGDVPQKS-7
8-DKQIXVOEBTGYBLEHMOWGDIXASKBTFTEJQJGRCTFANUEDQXVVOI-8
9-ZTKIRZEIXGSTFCBQRKCXGAKCYALSEXCCOCXUCGXWXVLJGRWZLC-9
0-TJYEBTKOXUCGXBCVGIXWRICWTSXUCPNTCVGCXGMYSAMSBEJTZH-0
1-OESCWPOKCJXFDVLBTBGVPSXUEKDJXFSYLHHFQVLTKKOIBTUOVU-1
2-UXXROIBPASSDQTBBOJUTKROJMHVVXVJAOCBSCXZSRVLLBSOZLQ-2
3-HSCVPIKOEDCGLHKCQHXWXVSGTZDVKJMHOIYJYUOJRDXFDMMBEO-3
4-OIKPNGSYPTFNSDKTKYKDGWGWXUGTPOXXCZGWPWSCWTBREIXKYU-4
5-CCGWRIRPITOICGCIXXCHXWPRQHMSOIQXVVYYLTASBQJXVVUVGI-5
6-OSBRZHVVSVBTMSOIQXVVFFLBBBXRQTBBOIRDVVDVPJGRNVKYNS-6
7-XXQIXBCFFCLHBZAWXFQVGHMSCRZLXGOEBJXPOIBTGYYGDSTBXC-7
8-GTLGOIQXVVSEBXXYEKQRASRVJUXB-----------------------8
--01234567890123456789012345678901234567890123456789--

Die Zahlen und Trennstriche dienen nur der Übersichtlichkeit.
Wir nehmen an, das Schlüsselwort hat die Länge $\left| k \right| = l$ und schreiben den Klartext in Zeilen der Länge $l$ untereinander.

${p_1}\:{p_2}\: \ldots \:{p_l}$

${p_{l+1}}\:{p_{l+2}}\: \ldots \:{p_{2l}}$

${p_{2l+1}}\:{p_{2l+2}}\: \ldots \:{p_{3l}}$

Es wird klar: Wenn zufällig zwei gleiche Wörter im Klartext genau im Abstand des Schlüssels stehen, dann werden sie auch zum gleichen Geheimtext verschlüsselt.

Wir können also alle Vorkommen von mindestens drei Zeichen suchen und den größten gemeinsamen Teiler des Abstandes berechnen:

kasiski-angriff-vigenere-primfaktorzerlegung

So erhalten wir die Länge des Schlüssels: Die 2 und die 3 kommen überall mindestens ein Mal vor (mit einer Ausnahme, die wohl ein Zufall ist). Die Schlüssellänge ist also wahrscheinlich 6.

2.8.3 Friedman-Test

Idee: Nutzung eines Urne-Kugel-Modells

Länge des Geheimtextes $c$ : $m$

Wir werfen alle Zeichen des Geheimtextes als Kugeln in eine Urne.

Möglichkeiten, zwei Kugeln zu ziehen:

$\# mglk = \frac{{m\left( {m-1} \right)}}{2}$

Wir betrachten nun nur eine Art von Kugeln (z.B. die mit einem R). Wie viele Möglichkeiten gibt es, zwei Kugeln dieser Art zu ziehen?

Häufigkeit der Kugel R: ${h_r}$

Möglichkeiten, zwei R-Kugeln zu ziehen:

$\# mglk\left( {R,R} \right) = \frac{{{h_r}\left( {{h_r}-1} \right)}}{2}$

Wir wechseln nun von Häufigkeiten zu Wahrscheinlichkeiten. Die Wahrscheinlichkeit, zwei R Kugeln zu ziehen, ist „Anzahl der günstigen durch Anzahl der möglichen Fälle“:

$P\left( {R,R} \right) = \frac{{\# mglk\left( {R,R} \right)}}{{\# mglk}} = \frac{{\frac{{{h_r}\left( {{h_r}-1} \right)}}{2}}}{{\frac{{m\left( {m-1} \right)}}{2}}} = \frac{{{h_r}\left( {{h_r}-1} \right)}}{{m\left( {m-1} \right)}}$

Die Wahrscheinlichkeit, zwei gleiche Kugeln (egal welche) zu ziehen:

$P = \sum\limits_{i = 0}^n {\frac{{{h_i}\left( {{h_i}-1} \right)}}{{m\left( {m-1} \right)}}} = \frac{1}{{m\left( {m-1} \right)}}\sum\limits_{i = 0}^n {{h_i}\left( {{h_i}-1} \right)} = :J\left( c \right)$

Die Wahrscheinlichkeit $J\left( c \right)$ hat Friedman als Koinzidenzindex bezeichnet. Dies ist die Wahrscheinlichkeit, dass im Geheimtext zwei gleiche Zeichen neben- bzw. untereinander stehen.

Wenn die Länge des Textes groß genug ist, ist ungefähr ${h_i} \approx {h_i}-1$ . Es folgt

$J\left( c \right) \approx \sum\limits_{i = 0}^n {p_i^2}$
Der Koinzidenzindex für die deutsche Sprache $J\left( {Deutsch} \right)$ ist ungefähr $J\left( {Deutsch} \right) \approx 7,62\%$

Es gilt:

$J\left( x \right) = \sum\limits_{i = 0}^n {p_i^2} = \frac{1}{n}+\sum\limits_{i = 0}^n {{{\left( {{p_i}-\frac{1}{n}} \right)}^2}}$

Es ist also die Anzahl der Zeichen im Kehrwert immer eine untere Schranke für den Koinzidenzindex.
Wenn wir nun den Geheimtext zeilenweise mit Zeilenlänge $l$ untereinander schreiben, müssten wir für den Koinzidenzindex der Spalten jeweils 7,62 erhalten, wenn wir $l$ richtig gewählt haben.
Hier eine Statistik für den Koinzidenzindex bei verschiedenen geratenen Schlüssellängen für den oben abgebildeten Geheimtext:

friedman-koinzidenzindex-schlussellange

Auch hier deutet alles auf die Schlüssellänge 6 hin. Nachdem der Geheimtext in 6 Spalten aufgeschrieben ist, kann für jede Spalte mit Hilfe der Häufigkeitsanalyse die richtige Zuordnung von Geheimtextzeichen zu Klartextzeichen erfolgen. Wir erhalten folgenden Klartext (in lesbarer Form mit Abständen und Zeichensetzung):

Im September achtzehnhundertachtundzwanzig verließ der größte Mathematiker des Landes zum erstenmal seit Jahren seine Heimatstadt, um am Deutschen Naturforscherkongreß in Berlin teilzunehmen. Selbstverständlich wollte er nicht dorthin. Monatelang hatte er sich geweigert, aber Alexander von Humboldt war hartnäckig geblieben, bis er in einem schwachen Moment und in der Hoffnung, der Tag käme nie, zugesagt hatte.
Nun also versteckte sich Professor Gauß im Bett. Als Minna ihn aufforderte aufzustehen, die Kutsche warte und der Weg sei weit, klammerte er sich ans Kissen und versuchte seine Frau zum Verschwinden zu bringen, indem er die Augen schloß. Als er sie wieder öffnete und Minna immer noch da war, nannte er sie lästig, beschränkt und das Unglück seiner späten Jahre. Da auch das nicht half, streifte er die Decke ab und setzte die Füße auf den Boden.
Grimmig und notdürftig gewaschen ging er die Treppe hinunter. Im Wohnzimmer wartete sein Sohn Eugen mit gepackter Reisetasche. Als Gauß ihn sah, bekam er einen Wutanfall: Er zerbracht einen auf dem Fensterbrett stehenden Krug, stampfte mit dem Fuß und schlug um sich. Er beruhigte sich nicht einmal, als Eugen von der einen und Minna von der anderen Seite ihre Hände auf seine Schultern legten und beteuerten, man werde gut für ihn sorgen, er werde bald wieder daheim sein, es werde so schnell vorbeigehen wie ein böser Traum. Erst als seine uralte Mutter, aufgestört vom Lärm, aus ihrem Zimmer kam, ihn in dieWange kniff und fragte, wo denn ihr tapferer Junge sei, faßte er sich. Ohne Herzlichkeit verabschiedete er sich von Minna; seiner Tochter und dem jüngsten Sohn strich er geistesabwesend über den Kopf. Dann ließ er sich in die Kutsche helfen.
aus: Daniel Kehlmann, „Die Vermessung der Welt”.

Zusammenfassung Affine Chiffren:

Wir können die bisher besprochenen Chiffren als Affine Chiffren beschreiben: