Brechen einer Vigenere Chiffre mittels Schlüsselrekonstruktion

Nachdem man die Art der Chiffre bestimmt hat und sicher ist, dass es sich um eine polyalphabetischen Substitutions-Chiffre handelt, hat man als nächstes die Schlüssellänge des Chiffrats bestimmt.

Für einen mittels Vigenere-Verschlüsselung erzeugten Geheimtext JUKVMXTXQWJEBSEVSXHRWAEDMXTBDJORLBLXEXKEQMNRWDEXHRKRFDVTUGFIRIGZYCGXGIXUGCLYLSZYPEBMIWSVGPSTMDRROEDRGIXDVOSGTRJULZQWEGFICUVGXENWZYPGXKENEGGEDTXVSVLMDIBWXHPORLNIBFKNVONPZVXOVGRSCASRKCAGEESZDLONLNRNEKMIBSMEIEEKZRWAVGIXUGCWSCADMXBBRWMHXMAKEKLIXDTRGRAKQXOEKCIXSVGROEPDKENWVMOEKRSNEGDVNBHCIXANEVKENLXOFTMHORXHRONDKISNXMKYLWDRONLBLVUXRWOLGTRQLTTFDEXQAYDXQWMHETICSXKAKEKDQEELRXOANBLNALRGRLHRWNASTWOIGFVEBBMHORXQHOUGCJKNWDMXEBRIBNXROKELSGREGVIXNWDVCCAKYOSLDPXUKOECSMCEMHMDIBELRMXDZDASSLJSCTUZVOSTBLONBMHOMDZICTVGIXEKRYMHMDELEKDWGAKJISNLBLVUXRWOLENGRDTDRNLBBLONMCIMKMDIBEBMWKBXQWYKEDMXDTRWWAGDWUANLWOHXMOYNGSIORIQSLIXQXOUGCHORLBLVUXRWOLIZWCTXFPEEVJPSCACENRXGXOEKDMXMTKLORNLYXDGTRWUXRWONPHVGAKSIXBBRIBVHKPONWREEFZDWMHENWCEGTRNDXMHOCDDPKUYFIWAVGXRAMCEXNPDVNEGVMBEKEERRXMAKSYTIBWNMHORUZVOSTBLONBMHOMDZICTVGIXLTFIX wurde die Schlüssellänge bereits bestimmt. Sie lautet 5.

Die folgende Kryptoanalyse-Methode zielt darauf ab, ein Kennwort zu rekonstruieren, indem es die Verschiebungen der Einzelalphabete herauszufinden versucht. Denn bei Vigenere gibt jeder Schlüsselbuchstabe die Verschiebung des Klartextbuchstaben an: Schlüsselbuchstabe "A" = +0, Schlüsselbuchstabe "B" = +1, Schlüsselbuchstabe "C" = +3, ... Schlüsselbuchstabe "Z" = +25.

Dazu werden die Buchstaben der Einzelbuchstaben zu einem Einzelalphabet zusammen gefasst, bei einer Schlüssellänge von 5 also A1. der 1., 6., 11., 16. ... A2. der 2., 7., 12., 17. ... A3. der 3., 8., 13., 18. ... A4. der 4., 9., 14., 19. ... A5. der 5., 10., 15., 20. ... Da diese Einzelalphabete alle mit dem selben Offset verschlüsselt wurden, weisen sie jeweils den Koinzidenzindex der im Klartext verwendeten Sprache auf, d. h. die Häufigkeitsverteilung ist natürlich und eben um den Offset des Schlüsselbuchstaben verschoben. Das machen wir uns zunutze, indem wir das Häufigkeitsgebirge des Einzelalphabets mit dem der Sprache vergleichen und es solange verschieben, bis eine Übereinstimmung herrscht. Da der Offset dem Schlüsselbuchstaben entspricht, haben wir mit jedem Schritt davon einen gelöst.

Beispiel:

A1 würde folgende Buchstaben enthalten: JXJVWXOXQDKTRCXYPWSRGOJWCEPNDVBOBOXSKEONBEWXSXMKXROXOEONNXKOOOSYOVOQDYMCKEONRNOEOOKXBKRXCOXCMBXSCOOOCXMLGSVORNOMBKYXWUOYOLOOVOCESNOXOXWOGXBOEMCNOKWRXNBRKBOOOOCXX A1 enthält nur ein Fünftel des ursprünglichen Chiffrats, darum wird die Häufigkeitsverteilung nicht so genau sein.

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

Verteilung für Einzelalphabet A1

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

Zum Vergleich: Normalverteilung deutsch

Es ist aber ausreichend, um das O als weitaus häufigsten Buchstaben zu identifizieren. Das Geheimtext-O wird als dem Klartext-e entsprechen (im weiterem werden Geheimtextbuchstaben GROSS und Klartext klein geschrieben). Bringen wir es der Übersicht halber zur Deckung, indem wir es 10 Stellen nach links verschieben.

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

Verteilung für Einzelalphabet A1, beginnend bei K


Wir erkennen eine sehr gute Übereinstimmung der Gebirgszüge: die b-c-d / L-M-N - Treppe, das Tal bei pq bzw. ZA und das Tal bei vwxyz bzw. FGHIJ. Der erste Schlüsselbuchstabe können wir direkt ablesen: es ist das K, mit dem das verschobene Einzelalphabet beginnt. Dies können wir aber auch schon vorher ausrechnen: O entspricht e. e - O = 4-14 = -10 = 10 = K, oder einfach, indem man die Balken nach links abzählt. Nach A muss man rechts bei Z wieder anfangen. 1 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 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 K - - - - Wenden wir uns dem 2. Einzelalphabet A2 zu. Dort sieht das Häufigkeitsgebirge folgendermaßen aus:

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

Verteilung für Text aus Eingabefeld, Periode 5

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

Zum Vergleich: Normalverteilung deutsch

Die Übereinstimmung sticht sofort ohne Verschiebung der Grafiken ins Auge. Der 2. Schlüsselbuchstabe muss also ein A sein K A - - - Fahren wir mit A3 fort. Geben Sie dazu im unteren Tool als Parameter "5,3" ein und wählen Sie "Häufigkeitsgebirge erstellen" aus. Sie erhalten:

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

Verteilung für Text aus Eingabefeld, Periode 5

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

Zum Vergleich: Normalverteilung deutsch

Nun ist der häufigsten Buchstabe das X. Es sollte also X=e sein. Y-Z-A-B passen gut zur nachfolgenden f-g-h-i-Treppe. Wir rechnen e-X = 4-23 = -19 = 19 = T. K A T - - Weiter mit A4 (Parameter "5,4"):

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

Verteilung für Text aus Eingabefeld, Periode 5

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

Zum Vergleich: Normalverteilung deutsch

Wieder können wir das e leicht bei D ausmachen. Auch der Rest sieht um eine Stelle nach rechts verschoben aus. Wir rechnen e-D = 4-3 = 1 = 26-1 = 25 = Z K A T Z - Nun kann man das Kennwort bereits gut erraten. Es lautet KATZE. Damit lässt sich das Chiffrat mit Vigenere entschlüsseln. K A T Z E Dies ist ein Vorteil dieser Methode. Man kann, sollte es sich um ein natursprachliches Kennwort handeln, dieses erraten und evtl. fehlende Buchstaben, die nicht ganz eindeutig anhand der Häufigkeitsgebirge identifizierbar sind, durch Raten ergänzen. Und selbst wenn es ein Kennwort aus wirren Buchstaben ist und vielleicht nur ein Buchstabe fehlt, dann hat man eine gute Grundlage für einen Brute-Force-Angriff, da es nur 26 Möglichkeiten gibt - bei 2 fehlenden Buchstaben sind es allerdings schon 676 und bei drei schon 17576.

Code / Chiffre online dekodieren / entschlüsseln bzw. kodieren / verschlüsseln (DeCoder / Encoder / Solver-Tool)

Sie können beim Häufigkeitsgebirge als Parameter Periode (p, angenommene Schlüssellänge), Start (s) und Ausgabeverschiebung (v, optional), durch Kommata getrennt, angeben. Dann wird die Verteilung nur für die Untergruppe der Zeichen an Position s, s+p, s+p*2... errechnet. Ist eine Ausgabeverschiebung angegeben, so beginnt die Tabelle mit dem v. Buchstaben für einen besseren Vergleich der Balken.

Quellen, Literaturverweise und weiterführende Links

Kasiski, Friedrich Wilhelm: Die Geheimschriften und die Dechiffrir-Kunst, Mittler & Sohn Verlag Berlin 1863, S. 27-31
Singh, Simon: Geheime Botschaften, Hanser Verlag 2000, S. 91
Kippenhahn, Rudolf: Verschlüsselte Botschaften, Nikol Verlag 2006, S. 148
Gómez, Joan: Geheimsprachen und Decodierung, Librero Verlag 2016, S. 49
Beutelspacher, Neumann und Schwarzpaul: Kryptografie in Theorie und Praxis, Vieweg Verlag 2005, S. 16
Ertel, Wolfgang: Angewandte Kryptographie, Hanser Verlag 2012, S. 40
Gaines, Helen Fouché: Cryptanalysis, Dover Verlag New York 1956, S. 112