Kryptologie/Caesar-Verschlüsselungsverfahren

Einleitung

Das Beispiel des Caesar-Verschlüsselungsverfahrens in der Lerneinheit zu Symmetrische Verschlüsselungsverfahren hat das Prinzip hinter dem Caesar-Verschlüsselungsverfahren bereits veranschaulicht. Wenn Sie die Seite studiert haben, sollten Sie bereits selbst einen Text mithilfe des Verfahrens verschlüsseln können. Es lohnt sich aber trotzdem das Verfahren auch aus einer verstärkt mathematischen Perspektive zu betrachten. Die mathematischen Grundlagen dieses Verfahren sind nämlich ebenfalls wichtige Grundlagen für komplexere und modernere (asymmetrische) Kryptosysteme, wie beispielsweise dem RSA-Kryptosystem. Wir nutzen diese Lerneinheit daher, um in wichtige Grundlagen der Zahlentheorie einzuführen und somit die Stofffülle bei weiteren Lerneinheiten zu reduzieren.

Zeichenkodierung des Caesar-Verschlüsselungsverfahrens

Zeichenkodierung und Anzahl der Elemente einer Menge
Zeichenkodierung
Seien $a\in \Sigma _{A}$ und $b\in \Sigma _{B}$ Zeichen der entsprechenden Alphabete und $f$ eine Funktion mit $f:\Sigma _{A}\rightarrow \Sigma _{B}$ , die die Zeichen eines beliebigen Alphabets $\Sigma _{A}$ auf ein Alphabet $\Sigma _{B}$ gleicher Länge. Dabei wird auf kein Zeichen von $\Sigma _{B}$ mehrfach abgebildet, aber jedes Zeichen von $\Sigma _{A}$ wird auf ein Zeichen von $\Sigma _{B}$ abgebildet. Es existiert außerdem die Umkehrfunktion $f^{-1}:\Sigma _{B}\rightarrow \Sigma _{A}$ mit $f^{-1}(b)=a$ genau dann, wenn $f(a)=b$ . Wir nennen die Funktion $f$ Zeichenkodierung und die Umkehrfunktion $f^{-1}$ Zeichendekodierung von $\Sigma _{A}$ und $\Sigma _{B}$ ^[1].
Anzahl der Elemente einer Menge
Sei $M$ eine endliche Menge, dann ist $\mid M\mid =$ Anzahl der Elemente von $M$ ^[2].

Besteht das Alphabet $\Sigma _{A}$ des Klartexten nicht nur aus numerischen Zeichen, so übertragen wir diese zunächst für das Caesar-Verschlüsselungsverfahren in ein numerisches Alphabet $\Sigma _{B}$ . Wir wählen hierfür ein Alphabet $\Sigma _{B}$ , das die gleiche Anzahl an Zeichen wie $\Sigma _{A}$ aufweist^[3]. Wir zeigen dies anhand einer beispielhaften Zeichenkodierung, die wir im Folgenden auch verwenden werden.

Wir definieren Start- und Zielalphabet:

Startalphabet $\Sigma _{A}:=\{z_{1},z_{2},...,z_{\mid \Sigma _{A}\mid }\}$

Zielalphabet $\Sigma _{B}:=\{0,1,...,\mid \Sigma _{A}\mid -1\}$

Bemerkung: $|\Sigma _{A}|$ bezeichnet die Anzahl der Elemente von $\Sigma _{A}$ .

Die zugehörige Zeichenkodierung $f_{CV}$ lautet:

$f_{CV}:\Sigma _{A}\rightarrow \Sigma _{B}$ ,

mit $z_{1}\mapsto 0$ , $z_{2}\mapsto 1$ , ..., $z_{\mid \Sigma _{A}\mid }\mapsto \mid \Sigma _{A}\mid -1$ .

Um die Zeichen des Alphabets $\Sigma _{B}$ erneut in Zeichen des Alphabets $\Sigma _{A}$ umzuwandeln, wenden wir die Umkehrfunktion $f_{CV}^{-1}$ an. Dabei gilt:

$f_{CV}^{-1}:\Sigma _{B}\rightarrow \Sigma _{A}$ ,

mit $0\mapsto z_{1}$ , $1\mapsto z_{2}$ , ... $\mid \Sigma _{A}\mid -1\mapsto z_{\mid \Sigma _{A}\mid }$ ^[1].

Algorithmus

Sei $k\in K$ mit $1\leq k\leq |\Sigma _{A}|-1$ ein Schlüssel, $m\in \mathbb {Z} /|\Sigma _{A}|\mathbb {Z}$ sei ein Klartext und $c\in \mathbb {Z} /|\Sigma _{A}|\mathbb {Z}$ der zugehörige Geheimtext. Beide bestehen aus Zeichen des Alphabets $\Sigma _{A}$ .

Der Algorithmus der Caesar-Verschlüsselung lautet:

Schlüsselerzeugung

Anzahl der Elemente einer Menge, Kongruenz, Restklasse und Repräsentant
Anzahl der Elemente einer Menge
Sei $M$ eine endliche Menge, dann ist $\mid M\mid =$ Anzahl der Elemente von $M$ ^[2].
Kongruenz
Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$ , dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$ ^[4].
Restklasse
Sei $a\in \mathbb {Z}$ modulo einer Zahl $m\in \mathbb {Z}$ die Menge aller ganzen Zahlen, die den gleichen Rest bei Division durch $m$ aufweisen wie $a$ . Dann ist $[a]_{m}=\{b\in \mathbb {Z} \mid b\equiv a{\bmod {m}}\}$ die Restklasse zu $a$ ^[5].
Repräsentant (einer Restklasse)
Ein Element einer Restklasse nennen wir Repräsentant der Restklasse^[6]. Die Elemente $0,\dots ,m-1$ modulo $m$ nennen wir Standardrepräsentant.

Wähle $k\in K$ mit $1\leq k\leq |\Sigma _{A}|-1$ zufällig und gleichverteilt.

Verschlüsselungsalgorithmus $E_{CV}$

$E_{CV}(m)=(m+k){\bmod {|}}\Sigma _{A}|=c$ .

Entschlüsselungsalgorithmus $D_{CV}$

$D_{CV}(c)=(c-k){\bmod {|}}\Sigma _{A}|=m$ ^[7].

Korrektheit des Caesar-Verschlüsselungsverfahren

Voraussetzung

Sei $m\in M$ und $k\in K$

Zu zeigen

Für alle $m\in M$ und $k\in K$ gilt $D(E(m))=m$ (da Ver- und Entschlüsselungsfunktion den identischen Schlüssel verwenden)

Beweis

$D_{CV}(E_{CV}(m))$

$\Rightarrow (E_{CV}(m)-k){\bmod {|}}\Sigma _{A}|$ , nach Definition $D_{CV}$

$\Leftrightarrow ((m+k){\bmod {|}}\Sigma _{A}|)-k){\bmod {|}}\Sigma _{A}|$ , nach Definition $E_{CV}$

$\Leftrightarrow (m+k-k){\bmod {|}}\Sigma _{A}|$

$\Leftrightarrow m{\bmod {|}}\Sigma _{A}|$

$\Rightarrow D_{CV}(E_{CV}(m))=m$ , da $0\leq m\leq |\Sigma _{A}|$

Bemerkung

In der Praxis muss der entsprechende Algorithmus auf jedes Zeichen des Klar- oder Geheimtextes einzeln angewandt werden (siehe Beispiel).
Wir definieren den Caesar-Algorithmus mit Hilfe der Modulo-Funktion, da wir diese für den RSA-Algorithmus ebenfalls benötigen.
Theoretisch sind auch Schlüssel größer als $25$ denkbar, aber da die Algorithmen mit Modulo $26$ arbeiten, sind beispielsweise $26+2$ und $2$ Repräsentanten der gleichen Restklasse im Restklassenring $(\mathbb {Z} /26\mathbb {Z} ,\oplus ,\odot )$
Wollen wir einen Klartext mit lateinischen Buchstaben verschlüsseln, so müssen wir zunächst eine Zeichenkodierung des Klartextes in ein numerisches Alphabet vornehmen. Analog dazu, müssen wir den Geheimtext in das lateinische Alphabet übertragen, wenn unserer Geheimtext aus Buchstaben bestehen soll.

Beispiel

Wir wollen den Klartext "ASTERIX" mit dem Schlüssel $k=7$ aus der Menge $K=\{1,2,\dots ,25\}$ verschlüsseln und einen Geheimtext mit lateinischen Buchstaben erhalten. Da es sich bei unserem Klartext ein Wort mit Zeichen des lateinischen Alphabets handelt, müssen wir eine Zeichenkodierung durchführen.

Zeichenkodierung

Zeichenkodierung und Anzahl der Elemente einer Menge
Zeichenkodierung
Seien $a\in \Sigma _{A}$ und $b\in \Sigma _{B}$ Zeichen der entsprechenden Alphabete und $f$ eine Funktion mit $f:\Sigma _{A}\rightarrow \Sigma _{B}$ , die die Zeichen eines beliebigen Alphabets $\Sigma _{A}$ auf ein Alphabet $\Sigma _{B}$ . Dabei wird auf kein Zeichen von $\Sigma _{B}$ mehrfach abgebildet, aber jedes Zeichen von $\Sigma _{A}$ wird auf ein Zeichen von $\Sigma _{B}$ abgebildet. Es existiert außerdem die Umkehrfunktion $f^{-1}:\Sigma _{B}\rightarrow \Sigma _{A}$ mit $b\mapsto a$ genau dann, wenn $a\mapsto b$ für $f$ . Wir nennen die Funktion $f$ Zeichenkodierung und die Umkehrfunktion $f^{-1}$ Zeichendekodierung von $\Sigma _{A}$ und $\Sigma _{B}$ ^[1].
Anzahl der Elemente einer Menge
Sei $M$ eine endliche Menge, dann ist $\mid M\mid =$ Anzahl der Elemente von $M$ ^[2].

Wir definieren zunächst Definitions- und Zielmenge:

$\Sigma _{L}:=\{A,B,C,...,Z\}$ mit $\mid \Sigma _{L}\mid =26$

$\Sigma _{26}:=\{0,1,...,25\}$

und unsere Zeichenkodierung $f_{CV}$ :

$f_{CV}:\Sigma _{L}\rightarrow \Sigma _{26}$ ,

mit $A\mapsto 0$ , $B\mapsto 1$ , ..., $Z\mapsto 25$ (vgl. Tabelle 2).

Die Umkehrung lautet:

$f_{CV}^{-1}:\Sigma _{26}\mapsto \Sigma _{L}$

mit $0\mapsto A$ , $1\mapsto B$ , ..., $25\mapsto Z$ (vgl. Tabelle 2).

Tabelle 2: Zuordnung der Zeichenkodierung $f_{CV}$
Klartext (Definitionsmenge)	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
Zugeordnete Zahl (Zielmenge)	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

Verschlüsselungsalgorithmus $E_{CV}$

Kongruenz
Kongruenz
Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$ , dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$ ^[4].

$E_{CV}(a)=(a+k){\bmod {|}}\Sigma _{A}|=b$

Entschlüsselungsalgorithmus

$D_{CV}(b)=(b-k){\bmod {|}}\Sigma _{A}|=a$

Verschlüsselung des Wortes "ASTERIX"

1. Zeichen A

$E_{CV}(f_{CV}(A))=(f_{CV}(A)+7){\bmod {2}}6=(0+7)\equiv 7{\bmod {2}}6$

2. Zeichen S

$E_{CV}(f_{CV}(S))=(f_{CV}(S)+7){\bmod {2}}6=(18+7)\equiv 25{\bmod {2}}6$

3. Zeichen T

$E_{CV}(f_{CV}(T))=(f_{CV}(T)+7){\bmod {2}}6=(19+7)\equiv 26\equiv 0{\bmod {2}}6$

4. Zeichen E

$E_{CV}(f_{CV}(E))=(f_{CV}(E)+7){\bmod {2}}6=(4+7)\equiv 11{\bmod {2}}6$

5. Zeichen R

$E_{CV}(f_{CV}(R))=(f_{CV}(R)+7){\bmod {2}}6=(17+7)\equiv 24{\bmod {2}}6$

6. Zeichen I

$E_{CV}(f_{CV}(I))=(f_{CV}(I)+7){\bmod {2}}6=(8+7)\equiv 15{\bmod {2}}6$

7. Zeichen X

$E_{CV}(f_{CV}(X))=(f_{CV}(X)+7){\bmod {2}}6=(23+7)\equiv 30\equiv 4{\bmod {2}}6$

Repräsentant (einer Restklasse)
Repräsentant (einer Restklasse)
Ein Element einer Restklasse nennen wir Repräsentant der Restklasse^[6]. Die Elemente $0,\dots ,m-1$ modulo $m$ nennen wir Standardrepräsentant.

Nun haben wir für jedes Zeichen des Klartextes die zum Zeichen des Geheimtextes zugehörige Zahl berechnet. Wir müssen nun noch die Umkehrfunktion $f_{CV}^{-1}$ von $f_{CV}$ auf die Standardrepräsentanten der Restklassen anwenden, wenn wir den Geheimtext im lateinische Alphabet erhalten wollen.

$f_{CV}^{-1}(7)=H$ , $f_{CV}^{-1}(25)=Z$ , $f_{CV}^{-1}(0)=A$ , $f_{CV}^{-1}(11)=L$ , $f_{CV}^{-1}(24)=Y$ , $f_{CV}^{-1}(15)=P$ und $f_{CV}^{-1}(4)=E$ .

Der Geheimtext lautet also "HZALYPE".

Entschlüsselung des Wortes "HZALYPE"

1. Zeichen H

Kongruenz
Kongruenz
Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$ , dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$ ^[4].

$D_{CV}(f_{CV}(H))=(f_{CV}(H)-7){\bmod {2}}6=(7-7)\equiv 0{\bmod {2}}6$

2. Zeichen Z

$D_{CV}(f_{CV}(Z))=(f_{CV}(Z)-7){\bmod {2}}6=(25-7)\equiv 18{\bmod {2}}6$

3. Zeichen A

$D_{CV}(f_{CV}(A))=(f_{CV}(A)-7){\bmod {2}}6=(0-7)\equiv -7\equiv 19{\bmod {2}}6$

4. Zeichen L

$D_{CV}(f_{CV}(L))=(f_{CV}(L)-7){\bmod {2}}6=(11-7)\equiv 4{\bmod {2}}6$

5. Zeichen Y

$D_{CV}(f_{CV}(Y))=(f_{CV}(Y)-7){\bmod {2}}6=(24-7)\equiv 17{\bmod {2}}6$

6. Zeichen P

$D_{CV}(f_{CV}(P))=(f_{CV}(P)-7){\bmod {2}}6=(15-7)\equiv 8{\bmod {2}}6$

7. Zeichen E

$E_{CV}(f_{CV}(E))=(f_{CV}(E)-7){\bmod {2}}6=(4-7)\equiv -3\equiv 23{\bmod {2}}6$

Analog zur Verschlüsselung müssen wir nun erneut die Umkehrfunktion $f_{CV}^{-1}$ auf die Standardrepräsentanten der Restklassen anwenden.

$f_{CV}^{-1}(0)=A$ , $f_{CV}^{-1}(18)=S$ , $f_{CV}^{-1}(19)=T$ , $f_{CV}^{-1}(4)=E$ , $f_{CV}^{-1}(17)=R$ , $f_{CV}^{-1}(8)=I$ und $f_{CV}^{-1}(23)=X$ .

Der Klartext lautet nach dem Entschlüsselungsalgorithmus "ASTERIX" und stimmt somit mit dem verschlüsselten Klartext überein.

Sicherheit

Tabelle 3: Top 5 der Buchstabenhäufigkeit in deutschsprachigen Texten^[8]
Platz	Buchstabe	Relative Häufigkeit
1.	E	17,48%
2.	N	9,84%
3.	I	7,73%
4.	R	7,54%
5.	S	6,83%

Die Caesar-Verschlüsselung stellt ein besonders unsicheres Verschlüsselungsverfahren dar, weil es nur 25 unterschiedliche Restklassen als Schlüssel gibt Wäre nämlich $k\in [0]_{26}$ , dann würde der Klartext zu einem identischen Geheimtext verschlüsselt^[9]. Ist einem Angreifer das Verschlüsselungsverfahren bekannt, so muss er also nur alle 25 relevanten Schlüssel in die Entschlüsselungsfunktion einsetzen und kontrollieren, bei welchem Schlüssel der Geheimtext in den Klartext entschlüsselt wird. Man nennt diese Art des Angriffs Brute-Force-Attacke^[10]^[11]. Es ergeben sich noch weitere Angriffsmöglichkeiten, wie beispielsweise die Häufigkeitsanalyse. Diese beruht bei dem Caesar-Verschlüsselungsverfahren darauf, dass die einzelnen Buchstaben der Definitionsmenge immer durch die selben Buchstaben der Zielmenge ersetzt werden. Die Häufigkeitsverteilung Buchstaben in Texten ist je nach Sprache unterschiedlich^[8]. Beispielsweise ist der Buchstabe E mit ca. 18% der am häufigsten verwendete Buchstabe in deutschsprachigen Texten (vgl. Tabelle 3)^[8]. Wird ein deutscher Klartext verschlüsselt und der Geheimtext enthält besonders häufig den Buchstaben L, so kann man zunächst vermuten, dass der Buchstabe E des Klartextes durch den Verschlüsselungsalgorithmus durch ein L im Geheimtext ersetzt wurde. Dies entspricht dem Schlüssel $k=7$ , da der Abstand zwischen E und L im Alphabet 7 ist. Der Text kann anschließend mit der Entschlüsselungsfunktion mit $k=7$ getestet werden^[12].

Bemerkung: Warum konnte Caesar seine Klartexte guten Gewissens mit diesem Verschlüsselungsverfahren verschlüsseln? Die Antwort ergibt ich aus der Zeit, zu der Caesar lebte. Das Verfahren war zu dieser Zeit nämlich weitgehend unbekannt und es war eine legitime Annahme, dass Dritte den Geheimtext für eine Nachricht in einer ihnen unbekannten Sprache halten würden. Für die Sicherheit der Caesar-Verschlüsselung war es also wichtig, den Algorithmus und nicht nur den Schlüssel geheim zu halten^[12]^[13].

Lernaufgabe

Aufgabe 1

Berechnen Sie die Entschlüsselung von folgendem Geheimtext mit der Entschlüsselungsfunktion des Caesar-Verschlüsselungsverfahrens und $k=13$ .

"QVRFCVAARAQVREBRZRE"

Lösung
Wir wenden den Entschlüsselungsalgorithmus $D_{CV}(f_{CV}(a))=(f_{CV}(a)-13){\bmod {2}}6$ mit $a\in \Sigma _{L}$ und anschließend die Umkehrfunktion der Zeichenkodierung an, um den Klartext für $k=13$ zu erhalten: $D_{CV}(f_{CV}(Q))=(f_{CV}(Q)-13){\bmod {2}}6=(16-13)\equiv 3{\bmod {2}}6\Rightarrow f_{CV}^{-1}(3)=D$ $D_{CV}(f_{CV}(V))=...=8{\bmod {2}}6\Rightarrow f_{CV}^{-1}(8)=I$ $D_{CV}(f_{CV}(R))=...=4{\bmod {2}}6\Rightarrow f_{CV}^{-1}(4)=E$ $D_{CV}(f_{CV}(F))=...=18{\bmod {2}}6\Rightarrow f_{CV}^{-1}(18)=S$ $D_{CV}(f_{CV}(C))=...=15{\bmod {2}}6\Rightarrow f_{CV}^{-1}(15)=P$ $D_{CV}(f_{CV}(V))=...=8{\bmod {2}}6\Rightarrow f_{CV}^{-1}(8)=I$ $D_{CV}(f_{CV}(A))=...=13{\bmod {2}}6\Rightarrow f_{CV}^{-1}(13)=N$ $D_{CV}(f_{CV}(A))=...=13{\bmod {2}}6\Rightarrow f_{CV}^{-1}(13)=N$ $D_{CV}(f_{CV}(R))=...=4{\bmod {2}}6\Rightarrow f_{CV}^{-1}(4)=E$ $D_{CV}(f_{CV}(A))=...=13{\bmod {2}}6\Rightarrow f_{CV}^{-1}(13)=N$ $D_{CV}(f_{CV}(Q))=...=3{\bmod {2}}6\Rightarrow f_{CV}^{-1}(3)=D$ $D_{CV}(f_{CV}(V))=...=8{\bmod {2}}6\Rightarrow f_{CV}^{-1}(8)=I$ $D_{CV}(f_{CV}(R))=...=4{\bmod {2}}6\Rightarrow f_{CV}^{-1}(4)=E$ $D_{CV}(f_{CV}(E))=...=17{\bmod {2}}6\Rightarrow f_{CV}^{-1}(17)=R$ $D_{CV}(f_{CV}(B))=...=14{\bmod {2}}6\Rightarrow f_{CV}^{-1}(14)=O$ $D_{CV}(f_{CV}(R))=...=4{\bmod {2}}6\Rightarrow f_{CV}^{-1}(4)=E$ $D_{CV}(f_{CV}(Z))=...=12{\bmod {2}}6\Rightarrow f_{CV}^{-1}(12)=M$ $D_{CV}(f_{CV}(R))=...=4{\bmod {2}}6\Rightarrow f_{CV}^{-1}(4)=E$ $D_{CV}(f_{CV}(E))=...=17{\bmod {2}}6\Rightarrow f_{CV}^{-1}(17)=R$ Der Klartext für $k=13$ lautet: DIESPINNENDIEROEMER Der Klartext scheint Sinn zu ergeben. Ob es tatsächlich der gesuchte Klartext ist, können wir auf Anhieb nicht sicher sagen, da der Geheimtext mit einem anderen $k$ ebenfalls einen sinnvollen Klartext ergeben hätte.

Aufgabe 2

Wir haben unbemerkt folgenden Geheimtext abgefangen:

RLWWTPYTYDPTYPCRPDLXESPTETDETYOCPTEPTWPLFQRPEPTWEOPCPYPTYPYOTPMPWRPCMPHZSYPYPTYPYLYOPCPYOTPLBFTELYPCFYOOPYOCTEEPYOTPUPYTRPYOTPTYTSC
PCPTRPYPYDACLNSPVPWEPYTYFYDPCPCRLWWTPCRPYLYYEHPCOPYOTPDPLWWPFYEPCDNSPTOPYDTNSFYEPCPTYLYOPCOFCNSTSCPDACLNSPOFCNSTSCPPTYCTNSEFYRPYFYO
TSCPRPDPEKPOTPRLWWTPCHPCOPYGZYOPYLBFTELYPCYOFCNSOPYQWFDDRLCFYYLGZYOPYMPWRPCYOFCNSXLECLYLFYODPBFLYLRPEPTWEOTPELAQPCDEPYGZYOTPDPYGZPW
VPCYDTYOOTPMPWRPCHPTWDTPGZYOPCKTGTWTDLETZYFYOOPCVFWEFCOPDCZPXTDNSPYGZWVPDPYEQPCYEDTYOFYOHPTWLXHPYTRDEPYZQEVLFQWPFEPKFTSYPYVZXXPYFYO
OLDPTYQFPSCPYHLDOTPWPFEPGPCHPTNSWTNSEFYOHPTWDTPOPYRPCXLYPYLXYLPNSDEPYHZSYPYOTPLFQOPCLYOPCPYDPTEPOPDCSPTYPDHZSYPYFYOXTEOPYPYDTPTXXPC
VCTPRQFPSCPYOLSPCMPCECPQQPYLFNSOTPSPWGPETPCOTPFPMCTRPYRLWWTPCLYELAQPCVPTEHPTWDTPTYQLDEELPRWTNSPYDNSWLNSEPYXTEOPYRPCXLYPYVLPXAQPYTYO
PXDTPDTPPYEHPOPCGZYTSCPXRPMTPELMHPSCPYZOPCDPWMDETYOPCPYRPMTPEVCTPRQFPSCPYGZYTSYPYPTYEPTWOPYHTPRPDLREOTPRLWWTPCTYYPSLMPYMPRTYYELYOPC
CSZYPPCHTCOMPRCPYKEGZYOPCRLCZYYPOPXZKPLYFYOGZYOPXWLYOPOPCMPWRPCPCMPCFPSCELFNSGZYOPCDPTEPOPCDPBFLYPCFYOSPWGPETPCLFDOPYCSPTYPCWTPREYL
NSYZCOPYKFOLDRPMTPEOPCMPWRPCMPRTYYELYOPYLFPDDPCDEPYRCPYKPYRLWWTPYDPDPCDECPNVEDTNSMTDKFXFYEPCPYEPTWPOPDCSPTYPDPDDNSLFEYLNSYZCOZDEPYL
BFTELYTPYPCDECPNVEDTNSGZYOPCRLCZYYPMTDKFXAJCPYLPPYRPMTCRPFYOOPXUPYTRPYEPTWOPDZKPLYDOPCMPTDALYTPYTDEPDDNSLFEYLNSYZCOHPDEPY

Berechnen Sie die Entschlüsselung von folgendem Geheimtext mit einer Häufigkeitsanalyse und der Entschlüsselungsfunktion der Caesar-Verschlüsselung. Geben Sie an, welchen Wert der zugehörige Schlüssel hat.

Hinweis
Tabelle 1: Häufigkeiten der einzelnen Buchstaben im Geheimtext und relative Häufigkeit der Buchstaben in der deutschen Sprachen
Buchstabe	Absolute Häufigkeit im Geheimtext	Relative Häufigkeit im Geheimtext	Relative Häufigkeit in der deutschen Sprache^[14]
A	7	0,54%	6,47%
B	5	0,38%	1,93%
C	101	7,77%	2,68%
D	66	5,08%	4,83%
E	69	5,31%	17,48%
F	49	3,77%	1,65%
G	16	1,23%	3,06%
H	17	1,31%	4,23%
I	0	0%	7,73%
J	1	0,08%	0,27%
K	10	0,77%	1,46%
L	69	5,31%	3,49%
M	22	1,69%	2,58%
N	27	2,08%	9,84%
O	80	6,15%	2,98%
P	268	20,62%	0,96%
Q	15	1,15%	0,02%
R	42	3,23%	7,54%
S	49	3,77%	6,83%
T	113	8,69%	6,13%
U	2	0,15%	4,17%
V	12	0,92%	0,94%
W	45	3,46%	1,48%
X	21	1,62%	0,04%
Y	165	12,69%	0,08%
Z	29	2,23%	1,14%

Hinweis 2
Tabelle 2: Verschiebungstabelle des lateinischen Alphabets
Buchstabe	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
Position	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26

Lösung
Wir wenden zur Entschlüsselung eine Häufigkeitsanalyse auf den Geheimtext an, d.h. wir vergleichen die relative Buchstabenhäufigkeit der deutschen Sprache mit der Buchstabenhäufigkeit des Geheimtextes. Die Ergebnisse werden in Tabelle 1 (siehe Hinweis) festgehalten. Vergleicht man die relative Häufigkeit der am meisten vorkommenden Buchstaben in Tabelle 1, so sieht man, dass der Buchstabe P mit 20,13% am häufigsten vorkommt. Dies legt die Vermutung nahe, dass der Buchstabe im $P$ im Geheimtext dem häufigsten Buchstaben der deutschen Sprachen im Klartext entspricht. Wir können Tabelle 1 entnehmen, dass dieser Buchstabe $E$ ist. Da es sich bei der Caesar-Verschlüsselung um eine Verschiebung des Alphabets um $k$ Buchstaben handelt, betrachten wir den Abstand zwischen $E$ und $P$ . Wir stellen hierfür eine Verschiebungstabelle der lateinischen Buchstaben und den Zahlen von 1 bis 26 auf (siehe Hinweis 2). $P$ ist der 16. Buchstabe und $E$ der fünfte. Der Abstand ist also folglich $16-5=11$ und der Schlüssel $k$ verschiebt die Buchstaben um $11$ Stellen nach rechts. Wir probieren den Geheimtext mit $k=11$ zu entschlüsseln und erhalten den Klartext: GALLIENINSEINERGESAMTHEITISTINDREITEILEAUFGETEILTDERENEINENDIEBELGERBEWOHNENEINENANDERENDIEAQUITANERUNDDENDRITTENDIEJENIGENDIEINIH REREIGENENSPRACHEKELTENINUNSERERGALLIERGENANNTWERDENDIESEALLEUNTERSCHEIDENSICHUNTEREINANDERDURCHIHRESPRACHEDURCHIHREEINRICHTUNGENU NDIHREGESETZEDIEGALLIERWERDENVONDENAQUITANERNDURCHDENFLUSSGARUNNAVONDENBELGERNDURCHMATRANAUNDSEQUANAGETEILTDIETAPFERSTENVONDIESENV OELKERNSINDDIEBELGERWEILSIEVONDERZIVILISATIONUNDDERKULTURDESROEMISCHENVOLKESENTFERNTSINDUNDWEILAMWENIGSTENOFTKAUFLEUTEZUIHNENKOMME NUNDDASEINFUEHRENWASDIELEUTEVERWEICHLICHTUNDWEILSIEDENGERMANENAMNAECHSTENWOHNENDIEAUFDERANDERENSEITEDESRHEINESWOHNENUNDMITDENENSIE IMMERKRIEGFUEHRENDAHERBERTREFFENAUCHDIEHELVETIERDIEUEBRIGENGALLIERANTAPFERKEITWEILSIEINFASTTAEGLICHENSCHLACHTENMITDENGERMANENKAEMP FENINDEMSIESIEENTWEDERVONIHREMGEBIETABWEHRENODERSELBSTINDERENGEBIETKRIEGFUEHRENVONIHNENEINTEILDENWIEGESAGTDIEGALLIERINNEHABENBEGIN NTANDERRHONEERWIRDBEGRENZTVONDERGARONNEDEMOZEANUNDVONDEMLANDEDERBELGERERBERUEHRTAUCHVONDERSEITEDERSEQUANERUNDHELVETIERAUSDENRHEINE RLIEGTNACHNORDENZUDASGEBIETDERBELGERBEGINNTANDENAUESSERSTENGRENZENGALLIENSESERSTRECKTSICHBISZUMUNTERENTEILEDESRHEINESESSCHAUTNACHN ORDOSTENAQUITANIENERSTRECKTSICHVONDERGARONNEBISZUMPYRENAEENGEBIRGEUNDDEMJENIGENTEILDESOZEANSDERBEISPANIENISTESSCHAUTNACHNORDWESTEN ^[15]^[16] Aufgrund der Länge und Komplexität des ermittelten Klartexten ist nicht anzunehmen, dass mit einem anderen Schlüssel ein zweiter möglicher Klartext ermittelt werden könnte und wir gehen davon aus, dass wir den von den Kommunikationspartnern verwendeten Schlüssel $k=11$ gefunden haben.

Aufgabe 3

Erläutern Sie, warum wir annehmen können, dass der Schlüssel auch für weitere Nachrichten zwischen den Kommunikationspartnern verwendet wird?

Lösung
Da die Caesar-Verschlüsselung ein symmetrisches Verfahren ist und die Schlüssel zwischen Kommunikationspartnern nur schwer sicher ausgetauscht werden können, wird der Schlüssel wahrscheinlich für mehrere Texte verwendet werden, solange er als sicher von den Kommunikationspartnern wahrgenommen wird. Wir werden also wahrscheinlich auch weitere Geheimtexte zwischen diesen beiden Kommunikationspartnern mit dem Schlüssel $k=11$ entschlüsseln können.

Lernempfehlung

Kursübersicht
Übergeordnete Lerneinheit
3: Symmetrische Kryptosysteme
Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
3: Symmetrische Kryptosysteme	4: Caesar-Verschlüsselungsverfahren	5: Asymmetrische Kryptosysteme
Grundlagen der aktuellen Lerneinheit
4.1: Teilbarkeit und Teilerfremdheit	4.2: Größte gemeinsame Teiler	4.3: Kongruenzen
4.4: Division mit Rest	4.5: Restklassen	4.6: (Halb-)Gruppen und Ringe
4.7: Restklassenring

Literatur

↑ ^a ^b ^c Bauer, F. L. (2000). Entzifferte Geheimnisse: Methoden und Maximen der Kryptologie (3., überarb. und erw. Aufl). Springer. S. 34.
↑ ^a ^b ^c Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 30.
↑ Schüller, A., Trottenberg, U., Wienands, R., Koziol, M., & Schneider, R. (2017). RSA – Primzahlen zur Verschlüsselung von Nachrichten. S. 5.
↑ ^a ^b ^c Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.
↑ Schüller, A., Trottenberg, U., Wienands, R., Koziol, M., & Schneider, R. (2017). RSA – Primzahlen zur Verschlüsselung von Nachrichten. S. 6.
↑ ^a ^b Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 86.
↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 75.
↑ ^a ^b ^c Bauer, F. L. (1997). Entzifferte Geheimnisse: Methoden und Maximen der Kryptologie (2., erw. Aufl). Springer. S. 286.
↑ Miller, M. (2003). Symmetrische Verschlüsselungsverfahren. Vieweg+Teubner Verlag. S. 3.
↑ Seite „Brute-Force-Methode“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 26. November 2019, 12:49 UTC. URL: https://de.wikipedia.org/w/index.php?title=Brute-Force-Methode&oldid=194393293 (Abgerufen: 20. Januar 2020, 13:54 UTC)
↑ Beutelspacher, A., Neumann, H. B., & Schwarzpaul, T. (2010). Kryptografie in Theorie und Praxis: Mathematische Grundlagen für Internetsicherheit, Mobilfunk und elektronisches Geld (2., überarb. Aufl). Vieweg + Teubner. S. 67.
↑ ^a ^b "Caesar-Verschlüsselung". In: Serlo Education e.V. Bearbeitungsstand: 67331. URL: https://de.serlo.org/informatik/verschluesselung/caesar-verschluesselung-48121 (abgerufen am 11.12.2019; Formulierung verändert)
↑ Pieprzyk, J., Hardjono, T., & Seberry, J. (2003). Fundamentals of Computer Security. Springer-Verlag. S. 6.
↑ Bauer, F. L. (2013). Entzifferte geheimnisse: methoden und maximen der kryptologie. Springer-Verlag. S. 304.
↑ De Bello Gallico: Liber I - Kapitel I. (17. Juli 2018). Wikibooks, Die freie Bibliothek. Abgerufen am 19. Februar 2020, 13:27 von https://de.wikibooks.org/w/index.php?title=De_Bello_Gallico:_Liber_I_-_Kapitel_I&oldid=854827. (Form verändert)
↑ Caesar. De Bello Gallico. Buch 1. Kapitel 1.

[:12-1] Bauer, F. L. (2000). Entzifferte Geheimnisse: Methoden und Maximen der Kryptologie (3., überarb. und erw. Aufl). Springer. S. 34.

[:0-2] Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 30.

[3] Schüller, A., Trottenberg, U., Wienands, R., Koziol, M., & Schneider, R. (2017). RSA – Primzahlen zur Verschlüsselung von Nachrichten. S. 5.

[:322-4] Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.

[5] Schüller, A., Trottenberg, U., Wienands, R., Koziol, M., & Schneider, R. (2017). RSA – Primzahlen zur Verschlüsselung von Nachrichten. S. 6.

[:074-6] Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 86.

[7] Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 75.

[:2-8] Bauer, F. L. (1997). Entzifferte Geheimnisse: Methoden und Maximen der Kryptologie (2., erw. Aufl). Springer. S. 286.

[9] Miller, M. (2003). Symmetrische Verschlüsselungsverfahren. Vieweg+Teubner Verlag. S. 3.

[10] Seite „Brute-Force-Methode“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 26. November 2019, 12:49 UTC. URL: https://de.wikipedia.org/w/index.php?title=Brute-Force-Methode&oldid=194393293 (Abgerufen: 20. Januar 2020, 13:54 UTC)

[11] Beutelspacher, A., Neumann, H. B., & Schwarzpaul, T. (2010). Kryptografie in Theorie und Praxis: Mathematische Grundlagen für Internetsicherheit, Mobilfunk und elektronisches Geld (2., überarb. Aufl). Vieweg + Teubner. S. 67.

[:02-12] "Caesar-Verschlüsselung". In: Serlo Education e.V. Bearbeitungsstand: 67331. URL: https://de.serlo.org/informatik/verschluesselung/caesar-verschluesselung-48121 (abgerufen am 11.12.2019; Formulierung verändert)

[13] Pieprzyk, J., Hardjono, T., & Seberry, J. (2003). Fundamentals of Computer Security. Springer-Verlag. S. 6.

[14] Bauer, F. L. (2013). Entzifferte geheimnisse: methoden und maximen der kryptologie. Springer-Verlag. S. 304.

[15] De Bello Gallico: Liber I - Kapitel I. (17. Juli 2018). Wikibooks, Die freie Bibliothek. Abgerufen am 19. Februar 2020, 13:27 von https://de.wikibooks.org/w/index.php?title=De_Bello_Gallico:_Liber_I_-_Kapitel_I&oldid=854827. (Form verändert)

[16] Caesar. De Bello Gallico. Buch 1. Kapitel 1.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]