4.2. VIGENERE-Verschlüsselung

In diesem Abschnitt diskutieren wir eine Stromchiffre, die den Vorteil hat, dass man sich nicht einen langen Text als Schlüsselstrom merken muss, sondern ein möglicherweise kurzes geheimes Schlüsselwort ausreicht, das den Schlüsselstrom induziert. Die sogenannte VIGENERE-Verschlüsselung, die unter anderem auf Blaise de Vigenère im 16. Jahrhundert zurückzuführen ist, ist eine Strom-Verschlüsselung, bei der das Schlüsselwort immer wieder aneinandergehängt wird um den Schlüsselstrom zu erzeugen.

Algorithmus 4.2 (VIGENÈRE-Verschlüsselung:)

1. Wir wählen als zu Grunde liegendes Alphabet \(\Sigma\) die lateinischen Großbuchstaben (ohne deutsche Umlaute) A,…,Z und nutzen als Klartext- und Chiffretextraum \(\mathcal{P} = \mathcal{C} = \Sigma^*\), d.h. die Menge aller Wörter über dem Alphabet \(\Sigma\).

2. Schlüsselraum: Als Schlüssel dient ein geheimes Schlüsselwort \(k \in \mathcal{K} = \Sigma^*\) mit \(k=k_1k_2k_3\dots k_n\). Der für die Stromchiffre benötigte Schlüsselstrom \(s \in \Sigma^*\) entsteht aus dem Schlüsselwort durch periodische Konkatenation des Schlüsselworts \(k\):

   \[k_1k_2\dots k_nk_1k_2\dots k_nk_1k_2\dots k_nk_1k_2\dots k_n\dots.\]

   Dieser Schlüsselstrom \(s = s_1 s_2 s_3 \dots\) lässt sich nach einer Identifikation mit den Zahlen \(0,\ldots,25\) über die kanonische Bijektion und die Konvention \(k_0 := k_n\) kompakt schreiben als:

   \[s_i \ = \ k_{i\bmod n}.\]

3. Verschlüsselung: Den zu verschlüsselnden Klartext \(m \in \mathcal{P}\) fassen wir als Zahlenfolge \(m = a_1,a_2,a_3,\dots\) mit \(0\le a_i\le 25\) auf. Dieser wird analog zu Algorithmus 4.1 mittels modularer Arithmetik durch

   \[b_i = a_i+k_{i\bmod n} \bmod 26\]

   zur Zahlenfolge des Chiffretexts \(c = b_1,b_2,b_3,\dots\) verschlüsselt. Stellen wir uns das geheime Schlüsselwort periodisch fortgesetzt als Schlüsselstrom \(s\) vor, so lautet die Verschlüsselungsvorschrift einfach \(b_i=a_i+s_i\bmod 26\).

4. Entschlüsselung: Die Entschlüsselung funktioniert analog zu Algorithmus 4.1 mittels modularer Arithmetik durch

   \[a_i=b_i-k_{i\bmod n}\bmod 26\]

   oder im Fall des periodischen Schlüsselstroms \(s\) einfach durch \(a_i=b_i+s_i\bmod 26\).

Wir wollen die Anwendung von Algorithmus 4.2 im Folgenden an einem Beispiel illustrieren.

Beispiel 4.2 (VIGENÈRE-Verschlüsselung)

Mit dem Schlüsselwort FREITAG verschlüsseln wir den Klartext AUCH IM OKTOBER KANN ES REGNEN mit der VIGENERE-Verschlüsselung und erhalten somit:

Text

A

U

C

H

I

M

O

K

T

O

B

E

R

K

A

N

N

E

S

R

E

G

N

E

N

Schlüssel

F

R

E

I

T

A

G

F

R

E

I

T

A

G

F

R

E

I

T

A

G

F

R

E

I

Chiffretext

F

L

G

P

B

M

U

P

K

S

J

X

R

Q

F

E

R

M

L

R

K

L

E

I

V

Bemerkung 4.2 (Kryptoanalyse für die VIGENERE-Verschlüsselung)

Bei der VIGENERE-Verschlüsselung handelt es sich um eine polyalphabetische Substitutionschiffre, da der Schlüsselstrom eine Folge von sich ändernden Chiffretext-Alphabeten induziert. Dies erschwert einen Angriff auf das Kryptosystem mittels Häufigkeitsanalyse enorm. Daher galt diese Verschlüsselung für lange Zeit als sicher. Mitte des 19. Jahrhunderts hatten Friedrich Wilhelm Kasiski und Charles Babbage unabhängig voneinander eine interessante Idee, wie man die VIGENERE-Verschlüsselung mittels statistischer Analyse doch erfolgreich angreifen kann. Diese als Kasiski-Test bekannte Methode wird im nächsten Abschnitt näher erläutert.