3.1. Substitutionschiffren

Wir beschäftigen uns zunächst mit sogenannten Substitutionschiffren bei denen jeder Buchstabe des Klartexts durch ein anderes Zeichen ersetzt (d.h. substitutiert) wird. Hierbei wird jedoch die Position des Zeichens innerhalb des Chiffretexts nicht verändert.

3.1.1. CAESAR-Verschlüsselung

Wir betrachten zunächst das einführende Beispiel der CAESAR-3-Verschlüsselung aus Algorithmus 1.1. Dieses lässt sich durch eine geeignete Parametrisierung und die Verwendung der Modulo-Operation leicht verallgemeinern.

Algorithmus 3.1 (CAESAR-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. Als Schlüsselraum wählen wir die Menge der ganzen Zahlen \(\mathcal{K} = \Z\). Ein Schlüssel \(k \in \mathcal{K}\) besteht also lediglich aus einer gewählten ganzen Zahl. Die Größe des Schlüsselraums \(|\mathcal K|\) entspricht der Größe des gewählten Alphabets \(|\Sigma|\).

3. Wir definieren eine durch den Schlüssel \(k \in \mathcal{K}\) parametrisierte Verschlüsselungsfunktion \(f_k\) wie folgt:

   \[f_k(x) \ := \ x + k \bmod 26,\]

   wobei \(x+k\bmod 26\) den Rest der Division von \(x+k\) durch \(26\) bezeichnet, der per Definition zwischen \(0\) und \(25\) liegt. \(f_k\) realisiert also eine zyklische Verschiebung des Alphabets um \(k\in\Z\) Stellen.

4. Verschlüsselung: Ein Klartext \(m \in \mathcal{P}\) mit \(m = a_1a_2a_3\dots\) wird verschlüsselt, indem man jeden Buchstaben \(a_i \in \Sigma\) des Textes sukzessiv durch \(f_k(a_i) \in \Sigma\) mittels obiger Verschlüsselungsfunktion ersetzt. Somit erhält man also den Chiffretext \(c \in \mathcal{C}\) mit

   \[c = f_k(a_1)f_k(a_2)f_k(a_3)\dots.\]

5. Entschlüsselung: Die Entschlüsselung eines Chiffretexts \(c = c_1,c_2,c_3,\dots\) funktioniert analog wie die Verschlüsselung, nur dass man statt \(f_k\) die Umkehrfunktion \(f_k^{-1}\) verwendet, d.h.

   \[m = f_k^{-1}(c_1)f_k^{-1}(c_2)f_k^{-1}(c_3)\dots\]

   Die Umkehrfunktion \(f^{-1}\) erhält man direkt, wenn man direkt indem man das Vorzeichen des Schlüssels \(k \in \Z\) umkehrt und als Parameter der Verschlüsselungsfunktion nutzt, d.h. es gilt

   \[f_k^{-1} \ = \ f_{-k}.\]

Wir wollen das Prinzip der verallgemeinertern CAESAR-Verschlüsselung kurz an einem Beispiel illustrieren.

Beispiel 3.1 (CAESAR-Verschlüsselung)

Mit Hilfe der in Algorithmus 3.1 eingeführten CAESAR-Verschlüsselung und dem gewählten Schlüssel \(k=37\) wird der Klartext

WIR BEGINNEN GANZ LEICHT

zum folgenden Chiffretext verschlüsselt:

HTC MPRTYYPY RLYK WPTNSE

Nutzt man nun den Schlüssel \(k=-37\) und wendet wiederum die CAESAR-Verschlüsselung an, so erhält man den ursprünglichen Klartext zurück.

Natürlich überträgt sich die CAESAR-Verschlüsselung auch auf andere Alphabete \(\Sigma\). Beispielsweise kann man Dateien CAESAR-verschlüsseln, wenn man die Datei als Bytefolge \(a_1,a_2,a_3,\dots\) auffasst mit \(0\le a_i\le 255\) und die folgende Verschlüsselungsfunktionen verwendet:

\[f_k(x)=x+k\bmod 256\]

Hierdurch erweitert sich der Schlüsselraum auf 256 mögliche Schlüssel.

Wir wollen im Folgenden noch kurz die Sicherheit des CAESAR-Kryptosystems diskutieren.

Bemerkung 3.1 (Kryptoanalyse für CAESAR-Verschlüsselung)

1. Es handelt sich bei der CAESAR-Verschlüsselung um ein symmetrisches Kryptosystem, das auf einer einfachen Blockchiffrierung für Blöcke der Größe 1 basiert.

2. Haben \(k_1 \in \Z\) und \(k_2 \in \Z\) den gleichen Divisionsrest bei der Division durch \(26\), d.h. gilt \(k_1\bmod 26=k_2\bmod 26\), so gilt \(f_{k_1}=f_{k_2}\). Daher gibt es eigentlich nur 26 verschiedene Schlüssel dieser CAESAR-Verschlüsselung, was ein einfaches Durchprobieren der möglichen Klartexte ermöglicht. Vermutet man, dass die aus Großbuchstaben bestehende, verschlüsselte Nachricht \(c \in \mathcal{C}\) CAESAR-verschlüsselt wurde, so kann man für alle Schlüssel \(k\in \{0,1,\dots,25\}\) den möglichen Klartext \(m = f_{-k}(c)\) bestimmen und prüfen, ob etwas Sinnvolles dabei herauskommt.

Wir wollen das Brechen der CAESAR-Verschlüsselung mit einem einfachen Beispiel kurz illustrieren.

Beispiel 3.2 (Angriff auf die CAESAR-Verschlüsselung)

Wir vermuten, dass IEPPSKYD CAESAR-verschlüsselt ist. Wir verschieben die Buchstaben jeweils um eine Stelle weiter und betrachten das Ergebnis, bis ein sinnvoller Text entsteht:

IEPPSKYD -> JFQQTLZE -> KGRRUMAF -> LHSSVNBG -> MITTWOCH

Vermutlich war der Klartext also MITTWOCH verschlüsselt mit einer CAESAR-22-Verschlüsselung.

Bemerkung 3.2 (Lösungshinweise als CAESAR-Chiffretext)

Hinweise für Übungsaufgaben, die in Großbuchstaben geschrieben sind, werden wir meist CAESAR-13-verschlüsseln. Man kann dann eine Aufgabe zunächst ohne Hinweis versuchen zu lösen.

Bei der CAESAR-Chiffrierung werden die einzelnen Zeichen einer Zeichenkette mit einer Funktion \(f_K:\Sigma\to \Sigma\) (wie oben) verschlüsselt. Die Funktionen \(f_K\) sind dabei bijektive Abbildung zwischen dem Klartextraum \(\mathcal{P} = \Sigma^*\) und dem Chiffretextraum \(\mathcal{C} = \Sigma^*\). Somit können wir die CAESAR-Verschlüsselung also als spezielle Permutation des Alphabets \(\Sigma\) interpretieren, bei denen nur Verschiebungen um \(k \in \lbrace{1,25}\) erlaubt sind.

3.1.2. MASC-Verschlüsselung

Wir haben in CAESAR-Verschlüsselung gesehen, dass die CAESAR-Verschlüsselung einen sehr kleinen Schlüsselraum der Mächtigkeit \(|\mathcal{K}| = |\Sigma|\) besitzt, wobei \(\Sigma\) das zu Grunde liegende Alphabet darstellt. Dies macht die Kryptoanalyse für dieses Verfahren trivial, da man nur alle möglichen Schlüssel testen und den potentiellen Klartext prüfen muss.

Um dieses Problem zu lösen wollen wir also eine Substitutionschiffre einführen, die einen wesentlich größeren Schlüsselraum als die CAESAR-Verschlüsselung besitzt. Daher diskutieren wir in diesem Abschnitt die sogenannte monoalphabetische Substitutionschiffrierung (kurz: MASC). Die grundlegende Idee ist es hierbei die CAESAR-Chiffrierung zu verallgemeinern, indem wir für die Funktionen \(f_k:\Sigma\to\Sigma\) beliebige Permutationen des Alphabets \(\Sigma\) zulassen.

Wir beschreiben im Folgenden eine praktikable Version der MASC-Chiffrierung für das aus den 26 Großbuchstaben bestehende Alphabet.

Algorithmus 3.2 (MASC-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: Der Schlüssel wird durch ein Wort \(K \in \Sigma^*\) gegeben, also eine Zeichenfolge \(K=k_1k_2k_3\dots k_n\) mit Zeichen \(k_i \in \Sigma\) für \(i=1,\ldots,n\). Wir testen für \(i=1,\dots,n\), ob der Buchstabe \(k_i\) an einer späteren Stelle \(j>i\) im Wort nochmal vorkommt, d.h. ob \(k_i=k_j\) gilt. Falls ja, wird das Zeichen \(k_j\) an der späteren Stelle \(j\) herausgestrichen. Das (eventuell abgeänderte) Wort \(K\) besteht danach aus paarweise verschiedenen Buchstaben.

   An das Schlüsselwort \(K\) wird nun das (zyklisch permutierte) Alphabet angehängt, wobei mit dem nach \(k_n\) folgenden Buchstaben begonnen wird und alle Buchstaben weggelassen werden, die schon im gekürzten Schlüsselwort \(K\) vorkamen. Es bleibt schließlich ein Wort \(K = K=k_1k_2\dots k_{26} \in \Sigma^26\) mit 26 verschiedenen Buchstaben übrig.

3. Verschlüsselung:

   Die bijektive Verschlüsselungsabbildung \(f_K:\{\text{A,B,C,\dots,Z}\}\to \{\text{A,B,C,\dots,Z}\}\) wird explizit durch \(f_K(\text{A})=k_1\), \(f_K(\text{B})=k_2\), \(f_K(\text{C})=k_3, \ldots, f_K(\text{Z})=k_{26}\) definiert und kann kompakt mit folgender Tabelle angegeben werden:

   \(x\)	A	B	C	…	Z
   \(f_K(x)\)	\(k_1\)	\(k_2\)	\(k_3\)	…	\(k_{26}\)

   Das bedeutet, dass man einfach das erweiterte Schlüsselwort \(k_1k_2k_3\dots k_{26} \in \Sigma^26\) unter das Alphabet schreibt. Auf den zu verschlüsselnden Klartext \(m = a_1a_2a_3\dots \in \mathcal{P}\) wendet man dann zeichenweise die Verschlüsselungsfunktion \(f_K\) an und erhält so den Chiffretext

   \[c = f_K(a_1)f_K(a_2)f_K(a_3)\dots\]

4. Entschlüsselung: Da es sich bei der Verschlüsselungsabbildung \(f_K\) um eine Bijektion handelt liest man die entsprechende Tabelle von unten nach oben und erhält so die inverse Funktion \(f_K^{-1}\) für die Entschlüsselung. Auf den Chiffretext \(c = b_1b_2b_3\dots \in \mathcal{C}\) wendet man zeichenweise die Entschlüsselungsfunktion \(f_K^{-1}\) an und erhält somit den Klartext \(m = a_1a_2a_3\ldots \in \mathcal{P}\) durch:

   \[f_K(b_1)f_K(b_2)f_K(b_3)\dots \: = \: a_1a_2a_3\dots\]

Wir betrachten zunächst ein einfaches Beispiel für die MASC-Verschlüsselung eines Klartexts.

Beispiel 3.3 (MASC-Verschlüsselung)

Das Schlüsselwort ERLANGEN wird zuerst zu ERLANG verkürzt, dann zu ERLANGHIJKMOPQSTUVWXYZBCDF ergänzt. Dies liefert dann die folgende Bijektion \(f_k\):

\(x\)

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

\(f_k(x)\)

E

R

L

A

N

G

H

I

J

K

M

O

P

Q

S

T

U

V

W

X

Y

Z

B

C

D

F

Damit wird der Klartext HEUTE IST FREITAG zum Chiffretext INYXN JWX GVNJXEH verschlüsselt.

Bisher haben wir für Klartext und Geheimtext immer das gleiche Alphabet benutzt. Das muss im Allgemeinen in der Kryptographie jedoch nicht der Fall sein. Wir sprechen bei verschiedenen Alphabeten für den Klartext und den Chiffretext entsprechend vom Klartextalphabet und dem Geheimtextalphabet. Das folgende Beispiel nutzt ein unterschiedliches Klartext- und Geheimtextalphabet.

Beispiel 3.4 (MASC-Verschlüsselung mit unterschiedlichen Alphabeten)

Das Klartextalphabet \(\Sigma_1=\{\text{A,\dots,Z}\}\) bestehe aus den Zeichen mit ASCII-Werten zwischen 65 und 90, während das Geheimtextalphabet \(\Sigma_2=\{\text{',\dots,@}\}\) aus den Zeichen mit den ASCII-Werten zwischen 39 und 64 bestehe. Die Verschlüsselungsabbildung werde dann für die ASCII-Werte durch die mathematische Abbildung \(f(x)=x-26\) definiert, also

\(x\)

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

\(f(x)\)

‚

(

)

*

,

.

/

0

1

2

3

4

5

6

7

8

9

:

;

\(<\)

=

\(>\)

?

@

Aus dem Klartext DEPARTMENT MATHEMATIK wird dann der Chiffretext *+6’8:3+4: 3’:.+3’:/1.

Wie der (abgekürzte) Name MASC schon verrät handelt es sich bei Algorithmus 3.2 um ein monoalphabetisches Kryptosystem. Dies bedeutet, dass für die Verschlüsselung nur ein einziges (fest gewähltes) Geheimalphabet für die Verschlüsselung jedes Zeichens des Klartexts genutzt wird. Wir werden später noch sogenannte polyalphabetische Substitutionschiffren kennenlernen, die ein anderes Prinzip verfolgen und mehrere Geheimtextalphabete für die Verschlüsselung nutzen.

Beispiel 3.5 (MASC-Entschlüsselung)

In der Erzählung *The Gold-Bug * von Edgar Allan Poe kommt folgender Chiffretext vor:

53|\ddag\ddag\dag|305))6*;4826)4|\ddag|.)4|\ddag|);806*;48|\dag|8|\P|60))85;1|\ddag|(;:|\ddag|*8|\dag|83(88)
5*|\dag|;46(;88*96*?;8)*|\ddag|(;485);5*|\dag|2:*|\ddag|(;4956*2(5*-4)8|\P|8*;40692
85);)6|\dag|8)4|\ddag\ddag|;1(|\ddag|9;48081;8:8|\ddag|1;48|\dag|85;4)485|\dag|528806*81(|\ddag|9;48;(8
8;4(|\ddag|?34;48)4|\ddag|;161;:188;|\ddag|?;

Es handelt sich um eine monoalphabetische Substitutionschiffrierung (MASC), wobei aber das Klartextalphabet nicht mit dem Geheimtextalphabet übereinstimmt. Die zugehörige Verschlüsselungsabbildung \(f_K\) ergibt sich aus folgender Tabelle:

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

5

2

8

1

3

4

6

0

9

*

.

(

)

;

?

¶

:

Wendet man die entsprechende Entschlüsselungsfunktion \(f_K^{-1}\) an, so erhält man:

AGOODGLASSINTHEBISHOPSHOSTELINTHEDEVILSSEATFORTYONEDEGREESANDTHIRTEEN
MINUTESNORTHEASTANDBYNORTHMAINBRANCHSEVENTHLIMBEASTSIDESHOOTFROMTHE
LEFTEYEOFTHEDEATHSHEADABEELINEFROMTHETREETHROUGHTHESHOTFIFTYFEETOUT

In der Erzählung von Poe wird der Chiffretext auch systematisch entschlüsselt und das Ergebnis angegeben:

A GOOD GLASS IN THE BISHOP'S HOSTEL IN THE DEVIL'S SEAT - FORTY-ONE
DEGREES AND THIRTEEN MINUTES - NORTHEAST AND BY NORTH - MAIN BRANCH
SEVENTH LIMB EAST SIDE - SHOOT FROM THE LEFT EYE OF THE DEATH'S HEAD 
- A BEELINE FROM THE TREE THROUGH THE SHOT FIFTY FEET OUT.

Im Folgenden wollen wir einige Beobachtungen zur Sicherheit des MASC-Kryptosystems festhalten.

Bemerkung 3.3 (Kryptoanalyse für MASC-Verschlüsselung)

1. Die CAESAR-Verschlüsselung ist ein Spezialfall der MASC-Chiffrierung, indem man als Schlüsselwort nur einen einzelnen Großbuchstaben wählt. Der ergänzte Schlüssel ist dann durch die Vorgaben in Algorithmus 3.2 ein zyklisch permutiertes Alphabet.

2. Durch die Vorgabe eines erweiterten Schlüsselsworts \(K \in \Sigma^{26}\) mit paarweise verschiedenen Zeichen, lassen sich alle möglichen Permutation des zu Grunde liegenden Alphabets aus 26 Großbuchstaben realisieren. Damit ist die Größe des Schlüsselraums \(\mathcal{K}\) wesentlich größer als beim CAESAR-Verschlüsselungsverfahren. Wegen der kombinatorischen Möglichkeiten der möglichen Permutationen von 26 Buchstaben ergibt sich nämlich

   \[|\mathcal{K}| = 26! = 403291461126605635584000000 \approx 0.4\cdot 10^{27}\]

3. Trotz des wesentlich größeren Schlüsselraums kann eine MASC-Verschlüsselung insbesondere für längere Chiffretexte relativ zuverlässig geknackt werden. Hierbei verwendet man statistische Verfahren wie z.B. eine Häufigkeitsanalyse, welche wir in Häufigkeitsanalyse disktutieren wollen.

3.1.3. Häufigkeitsanalyse

Eine gängige Methoden um monoalphabetische Substitutionschiffren (wie die CAESAR- und die MASC-Verschlüsselung) zu brechen ist mit Hilfe einer statistischen Analyse der vorkommenden Zeichen im Geheimtextalphabet. Bei der sogenannten Häufigkeitsanalyse zählt man in einem vorgegebenen Chiffretext, wie häufig einzelne Zeichen einzelne Zeichen vorkommen.

Wenden wir die Häufigkeitsanalyse an einem realistischen Beispieltext an, so ergeben sich statistisch relevante Beobachtungen.

Beispiel 3.6 (Häufigkeitsanalyse eines deutschen Texts)

Wir haben den Abschnitt Ankunft  des ersten Kapitels von *Der Zauberberg * von Thomas Mann hergenommen, Umlaute umgewandelt (ä in ae, ö in oe, ü in ue, ß in ss), dann alles in lateinische Großbuchstaben umgewandelt und die Sonderzeichen weggelassen. Es blieben dann insgesamt 15442 Großbuchstaben übrig, was eine genügend große Stichprobe für eine statistische Analyse darstellt. Wir haben den resultierenden Text in 5 Teile \(T_1,\dots,T_5\) aufgeteilt zu 3000, 3000, 3000, 3000 und 3442 Zeichen und für die einzelnen sowie für den gesamten Abschnitt die relativen Häufigkeiten der einzelnen Buchstaben (d.h. der Monogramme des Texts) bestimmt. Das Ergebnis findet sich in folgender Tabelle, wobei die Zahlen in Prozent angegeben sind:

	\(T_1\)	\(T_2\)	\(T_3\)	\(T_4\)	\(T_5\)	gesamt
A	6.13	5.80	6.53	7.23	6.07	6.35
B	2.07	1.93	1.83	2.03	1.92	1.96
C	2.93	2.97	3.60	3.60	3.63	3.35
D	4.17	4.43	5.47	4.67	4.79	4.71
E	18.60	18.80	15.67	16.80	16.56	17.26
F	1.63	1.70	1.23	1.20	1.54	1.46
G	3.27	3.50	2.47	3.20	2.73	3.02
H	5.27	4.93	5.70	5.90	5.98	5.57
I	7.37	7.33	7.30	7.00	8.11	7.44
J	0.23	0.17	0.43	0.57	0.49	0.38
K	1.00	1.00	1.27	0.93	1.02	1.04
L	3.83	3.30	2.13	3.50	3.11	3.17
M	2.37	3.07	2.77	2.20	2.59	2.60
N	10.57	11.03	11.03	9.00	9.33	10.17
O	2.23	2.37	3.57	2.63	3.14	2.80
P	0.63	0.73	0.70	0.73	0.73	0.71
Q	0.07	0.03	0.00	0.03	0.00	0.03
R	7.03	6.40	6.73	6.23	6.80	6.64
S	6.80	6.63	7.50	7.43	7.93	7.28
T	5.37	5.13	5.67	7.13	6.30	5.93
U	4.43	4.77	4.53	4.47	3.95	4.42
V	0.93	0.70	0.83	0.80	0.46	0.74
W	1.63	2.10	1.83	1.63	1.51	1.74
X	0.00	0.10	0.00	0.00	0.00	0.02
Y	0.00	0.00	0.03	0.00	0.12	0.03
Z	1.43	1.07	1.17	1.07	1.19	1.19

Wenn wir die Buchstaben der Häufigkeit nach ordnen, erhalten wir für die Teile \(T_1,\dots,T_5\) folgende Tabelle:

\(T_1\)

E

N

I

R

S

A

T

H

U

D

L

G

C

M

O

B

F

W

Z

K

V

P

J

Q

X

Y

\(T_2\)

E

N

I

S

R

A

T

H

U

D

G

L

M

C

O

W

B

F

Z

K

P

V

J

X

Q

Y

\(T_3\)

E

N

S

I

R

A

H

T

D

U

C

O

M

G

L

B

W

K

F

Z

V

P

J

Y

Q

X

\(T_4\)

E

N

S

A

T

I

R

H

D

U

C

L

G

O

M

B

W

F

Z

K

V

P

J

Q

X

Y

\(T_5\)

E

N

I

S

R

T

A

H

D

U

C

O

L

G

M

B

F

W

Z

K

P

J

V

Y

Q

X

Man sieht also, dass E der häufigste Buchstabe ist. Mit einigem Abstand folgt dann der Buchstabe N.

Im Folgenden stellen wir die Häufigkeitsverteilungen auch graphisch in Form eines sogenannten Häufigkeitsgebirges dar.

\[\includegraphics[width=7cm]{./atelier/img/TM1.png} \hspace{1cm} \includegraphics[width=7cm]{./atelier/img/TM2.png}\]

\[\includegraphics[width=7cm]{./atelier/img/TM3.png} \hspace{1cm} \includegraphics[width=7cm]{./atelier/img/TM4.png}\]

\[\includegraphics[width=7cm]{./atelier/img/TM5.png} \hspace{1cm} \includegraphics[width=7cm]{./atelier/img/TM_ZB.png}\]

Auch bei Auswertung anderer deutscher Texte beobachtet man, dass E und dann N die häufigsten Buchstaben sind [Bau00]. Bei [Bau00] findet sich auch folgende Tabelle mit hypothetischen Zeichenwahrscheinlichkeiten  der englischen und deutschen Sprache, die durch Auswertung längerer Texte erstellt wurde:

Zeichen	englisch	deutsch	Zeichen	englisch	deutsch
A	8.04	6.47	N	7.09	9.84
B	1.54	1.93	O	7.60	2.98
C	3.06	2.68	P	2.00	0.96
D	3.99	4.83	Q	0.11	0.02
E	12.51	17.48	R	6.12	7.54
F	2.30	1.65	S	6.54	6.83
G	1.96	3.06	T	9.25	6.13
H	5.49	4.23	U	2.71	4.17
I	7.26	7.73	V	0.99	0.94
J	0.16	0.27	W	1.92	1.48
K	0.67	1.46	X	0.19	0.04
L	4.14	3.49	Y	1.73	0.08
M	2.53	2.58	Z	0.09	1.14

Natürlich kann man nicht erwarten, dass sich jeder einzelne Text an eine solche Verteilung hält. Jedoch liefert diese Tabelle gute Annäherungswerte zum Brechen von monoalphabetischen Substitutionschiffren.

Vermutet man, dass ein deutscher Text durch eine Substitutionschiffre verschlüsselt ist, wie zum Beispiel mit Hilfe der CAESAR-Chiffre, so bestimmt man das häufigste Zeichen \(b \in \Sigma\) des Chiffretexts und anschließend die Translation \(k \in \lbrace 0,\ldots,25\rbrace\), so dass \(f_k(\texttt{E})=c\) gilt. Anschließend testet man, ob sich durch Anwendung von \(f_{-k}\) auf den gesamten Chiffretext ein sinnvoller Text ergibt. Dieses Vorgehen wird in folgendem Beispiel illustriert.

Beispiel 3.7 (Häufigkeitsanalyse für CAESAR-Verschlüsselung)

Wir vermuten, dass folgender Text Caesar-chiffriert ist:

RLQFNRBBWRLQCFJBBXUUNBKNMNDCNWMJBBRLQBXCAJDARPKRWNRWVJNALQNWJDBJUCNWIN
RCNWMJBTXVVCVRAWRLQCJDBMNVBRWW

Die häufigsten Buchstaben sind B und N, die jeweils 12-mal vorkommen. Es ist \(f_{23}(\text{E})=\text{B}\) und \(f_{9}(\text{E})=\text{N}\). Wendet man zunächst \(f_{-23}\) auf den Chiffretext an, erhält man die (nicht recht sinnvolle) Zeichenfolge

UOTIQUEEZUOTFIMEEAXXQENQPQGFQZPMEEUOTEAFDMGDUSNUZQUZYMQDOTQZMGEMXFQZLQ
UFQZPMEWAYYFYUDZUOTFMGEPQYEUZZ

Wendet man hingegen die Entschlüsselungsfunktion \(f_{-9}\) an, so erhält man die sinnvolle Buchstabenfolge

ICHWEISSNICHTWASSOLLESBEDEUTENDASSICHSOTRAURIGBINEINMAERCHENAUSALTENZE
ITENDASKOMMTMIRNICHTAUSDEMSINN

Es handelt sich um die ersten Zeilen des Gedichts Die Loreley von Heinrich Heine.

Wir haben bisher nur die Verteilung von Großbuchstaben betrachtet. Werden auch andere Zeichen, wie zum Beispiel Sonder- und Interpunktionszeichen, verschlüsselt, sollte man auch hier Häufigkeitsverteilungen studieren. Wir betrachten auch hierzu im Folgenden ein Beispiel.

Beispiel 3.8 (Häufigkeitsanalyse für TeX-Dateien)

Wir haben 4 TeX-Dateien betrachtet und die vorkommenden Zeichen gezählt. Die Häufigkeit ist jeweils in Prozent angegeben. Wir haben nur die 10 häufigsten Zeichen aufgelistet, wobei (Nr. 32) als ASCII-Zeichen für Leerzeichen und (Nr. 10) für Return/Wagenrücklauf steht.

Datei
198407 Bytes
(Nr. 32)	12.52
e	4.81
n	3.02
1	2.83
i	2.77
0	2.49
(Nr. 10)	2.39
2	2.35
3	2.21
9	2.18

Datei
117364 Bytes
(Nr. 32)	8.19
\(\backslash\)	6.31
e	5.60
a	5.32
i	4.93
n	3.71
$	3.50
t	3.42
r	3.29
{	2.86

Datei
96471 Bytes
(Nr. 32)	13.59
e	3.24
1	3.13
0	3.06
A	2.66
4	2.64
9	2.59
3	2.53
8	2.44
D	2.40

Datei
74909 Bytes
(Nr. 32)	10.53
e	7.12
i	5.41
n	5.12
\(\backslash\)	4.23
a	3.83
$	3.65
t	3.50
r	3.10
(Nr. 10)	2.77

Mit Abstand ist also das Leerzeichen das häufigste verwendete Zeichen in diesen Dateien.

Neben der Häufigkeitsverteilung einzelner Zeichen ist auch die Häufigkeitsverteilung von Buchstabenkombinationen, also von sogenannten \(n\)-Grammen interessant.

Definition 3.1 (n-Gramme)

Sei \(\Sigma\) ein gewähltes Alphabet und \(n\in \N\). Wir bezeichnen ein Wort \(w = w_1w_2\ldots w_n \in \Sigma^n\) der Länge \(|w| = n\) über dem Alphabet \(\Sigma\) als \(\mathbf{n}\)-Gramm.

Für \(n=1\) spricht man von einem Monogramm, für \(n=2\) von einem Bigramm (oder auch Digramm, für \(n=3\) von einem Trigramm, usw.

Wir wollen die Häufigkeitsanalyse für Buchstabenkombinationen in folgendem Beispiel kurz erklären.

Beispiel 3.9 (Häufigkeitsanalyse für Bigramme)

Wir betrachten wieder den zuvor verwendeteten Text von Thomas Mann in Beispiel 3.6. Die folgenden Bigramme kommen mit einer Häufigkeit von mehr als einem Prozent vor:

EN	ER	CH	TE	ND	EI	IN	DE	GE	IE	ES	UN	NE	IC	SE	ST	BE
3.82	3.62	2.99	2.17	2.14	1.94	1.85	1.78	1.60	1.51	1.45	1.42	1.26	1.24	1.24	1.22	1.15

Dies sind die häufigsten Trigramme:

ICH	EIN	UND	SCH	DER	NDE	INE	END	CHT	GEN	CHE	ENS	TEN	TER	DIE	ERS
1.20	1.04	0.82	0.81	0.78	0.67	0.60	0.59	0.56	0.55	0.54	0.49	0.48	0.47	0.45	0.40

Die 10 häufigsten \(4\)-Gramme (Tetragramme) sind gezählt in absoluten Häufigkeiten:

EINE (83), ICHT (61), SICH (52), SEIN (48), NICH (45),
LICH (44), NDER (42), CHEN (40), SCHE (36), ENDE (36)

Bei [Bau00] findet sich eine Liste von häufigen Bigrammen in der deutschen Sprache. Als die zehn häufigsten deutschen Wörter werden genannt:

die, der, und, den, am, in, zu, ist, dass, es.

Es werden darüber hinaus noch viele weitere sprachliche Eigenschaften zusammengestellt. Dies kann helfen, eine monoalphabetische Substitutionschiffrierung recht zuverlässig zu entschlüsseln.