Kryptologie/Kodierung von Nachrichten

Einleitung

Kryptosystem
Kryptosystem
Verfahren zur Umsetzung von Sicherheitszielen in der Kryptografie.

Wir lernen in den anderen Lerneinheiten Kryptosysteme kennen, die als Eingabe für Ver- und Entschlüsselungsalgorithmus eine Nachricht aus Zahlen benötigen. Bevor wir also ein Kryptosystem auf eine Nachricht anwenden, klären wir zunächst, wie man den Text einer Nachricht mathematisch begreifen kann. Wir unterscheiden dabei vier wichtige Begriffe: Alphabet, Zeichen, Wort und Zeichenkodierung.

Alphabet, Zeichen und Wort

Definition Alphabet

Sei $\mathrm{\Sigma }$ eine endliche, nicht leere Menge. Wir nennen $\mathrm{\Sigma }$ ein Alphabet.

Beispiel 1: ${\mathrm{\Sigma }}_L=\{A,B,...,Z\}$ ist das lateinische Alphabet.

Beispiel 2: ${\mathrm{\Sigma }}_9=\{0,1,...,9\}$ ist das Alphabet des Dezimalsystems.

Definition Zeichen

Die Elemente eines Alphabets heißen Zeichen.

Beispiel 1: $A,B,...,Z$ sind die Zeichen des lateinischen Alphabets ${\mathrm{\Sigma }}_L$.

Beispiel 2: $0,1,...,9$ sind die Zeichen des Alphabets ${\mathrm{\Sigma }}_9$.

Definition Wort

Bilden Zeichen eine endliche Folge, so ergeben sie ein Wort.

Beispiel 1: $WIKIPEDIA$ aus endlich vielen Zeichen des Alphabets ${\mathrm{\Sigma }}_L$ und bildet somit ein Wort.

Beispiel 2: $4291$ besteht aus endlich vielen Zeichen des Alphabets ${\mathrm{\Sigma }}_9$ und bildet somit ein Wort.

Zeichenkodierung

Wie bereits erwähnt, benötigen viele Kryptosysteme den Klartext in Form von numerischen Zeichen. Wir können dennoch Nachrichten mit diesen Kryptosystemen ver- und entschlüsseln, die auf Alphabeten basieren, die nicht numerisch sind. Hierzu ordnen wir jedem Zeichen des ursprünglichen Alphabets genau ein Zeichen des numerischen Alphabets zu. Die Umkehrung gilt dann ebenfalls, d.h. jedes Zeichen des numerischen Alphabets wird genau dem Zeichen des ursprünglichen Alphabets zugeordnet, welches auch diesem numerischen Zeichen zugeordnet wurde.

Definition Zeichenkodierung

Seien $a\in {\mathrm{\Sigma }}_A$ und $b\in {\mathrm{\Sigma }}_B$ Zeichen der entsprechenden Alphabete gleicher Länge und $f$ eine Funktion mit $f:{\mathrm{\Sigma }}_A\to {\mathrm{\Sigma }}_B$, die die Zeichen eines beliebigen Alphabets ${\mathrm{\Sigma }}_A$ auf ein Alphabet ${\mathrm{\Sigma }}_B$ abbildet. Dabei wird auf kein Zeichen von ${\mathrm{\Sigma }}_B$ mehrfach abgebildet, aber jedes Zeichen von ${\mathrm{\Sigma }}_A$ wird auf ein Zeichen von ${\mathrm{\Sigma }}_B$ abgebildet, d.h. $f$ ist bijektiv. Es existiert in dem Fall außerdem die Umkehrfunktion $f^{-1}:{\mathrm{\Sigma }}_B\to {\mathrm{\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 ${\mathrm{\Sigma }}_A$ und ${\mathrm{\Sigma }}_B$.

Wir veranschaulichen dies anhand eines Beispiels.

Beispiel zur Zeichenkodierung

Tabelle 1: Zuordnungstabelle zur Zeichen(de-)kodierung von ${\mathrm{\Sigma }}_{AB}$ und ${\mathrm{\Sigma }}_2$

Zeichen aus ${\mathrm{\Sigma }}_{AB}$	A	B
Zeichen aus ${\mathrm{\Sigma }}_2$	1	2

Wir wählen als ursprüngliches Alphabet ${\mathrm{\Sigma }}_{AB}=\{A,B\}$ und als numerisches Alphabet gleicher Länge ${\mathrm{\Sigma }}_2=\{1,2\}$. Wir definieren die Funktion $f:{\mathrm{\Sigma }}_{AB}\to {\mathrm{\Sigma }}_2$, so dass wir jedem Zeichen von ${\mathrm{\Sigma }}_{AB}$ genau ein Zeichen von ${\mathrm{\Sigma }}_2$ zuordnen. Wir wählen:

$A\mapsto 1$ und $B\mapsto 2$.

Wir übertragen nun das Wort $AB$ in das numerische Alphabet und erhalten das Wort $12$.

Wollen wir oder ein Empfänger das Wort nun wieder in das ursprüngliche Alphabet übertragen, um den Inhalt des Klartextes zu verstehen, so ist es wichtig, dass für die Umkehrfunktion $f^{-1}:{\mathrm{\Sigma }}_2\to {\mathrm{\Sigma }}_{AB}$ mit $1\mapsto A$ und $2\mapsto B$ gilt. Wenn ja, können wir das Wort mittels der Umkehrfunktion übertragen und erhalten $AB$.

Man kann die Zuordnung in einer Zuordnungstabelle darstellen (siehe Tabelle 1).

Lernaufgabe

Aufgabe 1

Bestimmen Sie eine Zeichenkodierung $f_{CV}$, die die lateinischen Buchstaben des Alphabets ${\mathrm{\Sigma }}_L=\{A,B,\dots ,Z\}$ auf das numerische Alphabet ${\mathrm{\Sigma }}_{26}=\{0,1,\dots ,25\}$ abbildet.

Nennen Sie auch die zugehörige Zeichendekodierung $f_{CV}^{-1}$.

Lösungsvorschlag

Start- und Zielalphabet sind bereits definiert: Startalphabet ${\mathrm{\Sigma }}_L=\{A,B,\dots ,Z\}$ und Zielalphabet ${\mathrm{\Sigma }}_{26}=\{0,1,...,25\}$. Wir definieren die Zeichenkodierung $f_{CV}$ wie folgt: $f_{CV}:{\mathrm{\Sigma }}_L\to {\mathrm{\Sigma }}_{26}$, mit $A\mapsto 0$, $B\mapsto 1$, ..., $Z\mapsto 25$. Um die Zeichen des Alphabets ${\mathrm{\Sigma }}_{26}$ erneut in Zeichen des Alphabets ${\mathrm{\Sigma }}_L$ umzuwandeln, wenden wir die Umkehrfunktion $f_{CV}^{-1}$ an. Dabei gilt: $f_{CV}^{-1}:{\mathrm{\Sigma }}_{26}\to {\mathrm{\Sigma }}_L$, mit $0\mapsto A$, $1\mapsto B$, ... $25\mapsto Z$.

Aufgabe 2

Stellen Sie zu Ihrer Lösung aus Aufgabe 1 eine Zuordnungstabelle dar.

Lösungsvorschlag

Zuordnungstabelle zur Zeichen(de-)kodierung von ${\mathrm{\Sigma }}_L$ und ${\mathrm{\Sigma }}_{26}$
${\mathrm{\Sigma }}_L$	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
${\mathrm{\Sigma }}_{26}$	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

Lernempfehlung

Kursübersicht

Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
1: Grundlagen der Kryptologie	2: Kodierung von Nachrichten	3: Symmetrische Kryptosysteme