Informationsrepräsentation

1.2. Informationsrepräsentation#

Um Informationen zu speichern und auszutauschen gibt es verschiedene Möglichkeiten, die je nach Anwendungskontext benutzt werden. Dies kann durch unterschiedliche Formate und Signale geschehen, wie z.B. durch Bilder oder Audiosignale. In der Kryptographie wird in der Regel Text zur Repräsentation von Informationen genutzt. Um Texte zu schreiben benötigt man jedoch zunächst ein zu Grunde liegendes Alphabet, welches wir im Folgenden mathematisch definieren wollen.

Definition 1.1 (Alphabet und Zeichen)

Unter einem Alphabet verstehen wir eine endliche, nicht-leere Menge \(\Sigma\), welche aus unterschiedlichen, gewählten Zeichen (oder auch Buchstaben oder Symbolen) besteht.

Wir bezeichnen die Länge des Alphabets \(|\Sigma|\) als die Anzahl der Zeichen in \(\Sigma\).

Je nach Kulturkreis oder Anwendung können Alphabete sehr unterschiedlich ausfallen, wie folgendes Beispiel klar macht.

Beispiel 1.2 (Verschiedene Alphabete)

Für uns geläufig ist das lateinische Alphabet (Großbuchstaben ohne deutsche Umlaute)

\[\Sigma=\lbrace \texttt{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}\rbrace.\]

Dieses Alphabet besteht aus \(26\) Zeichen, d.h., es gilt \(|\Sigma| = 26\).

Ein etwas größeres Alphabet erhält man, wenn man noch zusätzlich die Kleinbuchstaben a, b, c …, z, Leerzeichen, sowie die Interpunktionszeichen . , ! ? hinzunimmt. Damit erhöht sich die Länge des Alphabets auf \(|\Sigma| = 57\).
In der Mathematik verwenden wir häufig das griechische Alphabet zur Bezeichnung in Formeln. Es ist gegeben durch:

\[\begin{split} \Sigma = \lbrace &\alpha, \beta, \gamma, \delta, \varepsilon, \zeta, \eta, \theta, \iota, \kappa, \lambda, \mu, \nu, \xi, o, \pi, \rho, \sigma, \tau, \upsilon, \varphi, \chi, \psi, \omega,\\ &A, B, \Gamma, \Delta, E, Z, H, \Theta, I, K, \Lambda, M, N, \Xi, O, \Pi, P, \Sigma, T, \Upsilon, \Phi, X, \Psi, \Omega\rbrace \end{split}\]

Dieses Alphabet besteht aus \(48\) Zeichen, d.h., es gilt \(|\Sigma| = 48\).
Zur digitalen Speicherung und Verarbeitung von Informationen in Computern verwendet man eine Repräsentation im Binärsystem, d.h., es existieren für ein Informationsbit nur zwei Zustände. In diesem Fall ist das Alphabet gegeben durch:

\[\Sigma = \lbrace \texttt{0,1} \rbrace.\]

Dieses Alphabet hat offensichtlich die Länge \(|\Sigma| = 2^1 = 2\).

Im Allgemeinen werden jeweils \(8\) Bits zu einem sogenannten Byte (oder auch Oktett) zusammengefasst. Bytes definieren ein eigenes Alphabet, welches gegeben ist durch:

\[\Sigma = \lbrace \texttt{00000000,00000001,\ldots,11111110,11111111} \rbrace.\]

Dieses Alphabet hat die Länge \(|\Sigma| = 2^8 = 256\).
Ein weiteres geläufiges Alphabet für eine textuelle Repräsentation von Informationen nutzt eine hexadezimale Darstellung und ist gegeben durch:

\[\Sigma = \lbrace \texttt{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}\rbrace.\]

Dieses Alphabet besteht wie der Name schon vermuten lässt aus \(16\) Zeichen, d.h., es gilt \(|\Sigma| = 16\).
Der ASCII-Zeichensatz (American Standard Code for Information Interchange) ist ein weiteres geläufiges Alphabet für die digitale Repräsentation von Textinformationen und stellt insgesamt \(128\) Zeichen dar, d.h. es gilt \(|\Sigma| = 128\).

Hiervon sind allerdings \(33\) Zeichen nicht-druckbar (z.B. das Bell-Zeichen zur Erzeugung eines Tons beim Empfängergerät) und \(95\) Zeichen druckbar.

Für eine Auflistung des gesamten ASCII-Alphabets kann man unter Linux, Unix und macOS den Kommandozeilenbefehl man ascii nutzen. In Python liefert ord(z) den ascii-Wert eines Zeichens \(z\), während chr(n) das dem Zahlenwert \(n\) entsprechende Zeichen liefert.

Es wird klar, dass eine große Anzahl an möglichen Alphabeten existiert und somit unzählige Möglichkeiten zur Informationsrepräsentation. Für den Einsatz in der Kryptographie ist es daher essentiell, dass man sich vorher auf ein bestimmtes Alphabet festlegt. Welches Alphabet verwendet wird ist schlussendlich egal, da die repräsentierte Information unabhängig von der Wahl des zu Grunde liegenden Alphabets gleich bleibt.

Hat ein gewähltes Alphabet \(N\in\N\) Zeichen, so kann man eine kanonische Bijektion mit der Menge der natürlichen Zahlen \(\{0,1,2,\dots,N-2,N-1\}\) herstellen. Ist das Alphabet angeordnet, so weist man jedem Zeichen einfach seine Position innerhalb des Alphabets zu. Diese Bijektion erlaubt es uns kryptographische Prinzipien und Methoden mathematisch zu erfassen und zu untersuchen.

Diese Bijektion soll im Folgenden an Hand einiger Alphabete aus Beispiel 1.2 veranschaulicht werden.

Beispiel 1.3 (Bijektion zwischen Alphabet und natürlichen Zahlen)

Wählen wir das lateinische Alphabet (Großbuchstaben ohne deutsche Umlaute), so können wir eine Bijektion \(\Sigma \longleftrightarrow \lbrace 0,\ldots,25 \rbrace\) wie folgt herstellen:

\[\texttt{A} \rightarrow 0, \quad \texttt{B} \rightarrow 1, \quad \ldots, \quad \texttt{Z} \rightarrow 25.\]
Im Fall des hexadezimalen Alphabets erhalten wir eine Bijektion \(\Sigma \longleftrightarrow \lbrace 0,\ldots,15 \rbrace\) wie folgt:

\[\texttt{0} \rightarrow 0, \ \texttt{1} \rightarrow 1, \ \ldots, \ \texttt{9} \rightarrow 9, \ \texttt{A} \rightarrow 10, \ \texttt{B} \rightarrow 11, \ \texttt{C} \rightarrow 12, \ \texttt{D} \rightarrow 13, \ \texttt{E} \rightarrow 14, \ \texttt{F} \rightarrow 15.\]
Werden Informationen mit Hilfe von Bytes repräsentiert, so erhalten wir eine Bijektion indem wir jedes Byte als Binärzahl (ohne Vorzeichen) interpretieren:

\[\texttt{00000000} \rightarrow 0, \ \texttt{00000001} \rightarrow 1, \ \ldots, \ \texttt{11111110} \rightarrow 254, \ \texttt{11111111} \rightarrow 255.\]

Die Darstellung mit Hilfe natürlicher Zahlen hat außerdem den Vorteil, dass sie sich direkt im Computer abbilden lassen durch die Darstellung als Bytes (z.B. im Zweierkomplement). In der computergestützten Kryptographie ist es häufig üblich direkt auf Bytes zu operieren ohne die gespeicherte Information vorher in einer andere Repräsentation zu überführen. In diesem Fall werden andere Alphabete nur verwendet um die repräsentierte Information für uns Menschen lesbar zu machen.

Bemerkung 1.1 (Verwendung von Bytes in Python)

Legt man eine Textdatei mit Namen message.txt an, in der die Nachricht Hallo Welt! (inklusive Zeilenumbruch) steht, und führt man in Python die folgenden Befehle aus
```
with open("message.txt","rb") as file:
    content_bytes = file.read()
number_representation = [char for char in content_bytes]
```
so enthält die Variable number_representation die zugehörige Bytefolge in Dezimaldarstellung, d.h. in Form von natürlichen Zahlen:
```
print(number_representation)
[72, 101, 108, 108, 111, 32, 87, 111, 114, 108, 100, 33, 10]
```
Will man einen Text Hallo Welt! als Bytes (im ASCII-Zeichensatz) in eine Datei mit Namen message.txt schreiben, so lässt sich dies wie folgt in Python realisieren:
```
content = "Hello World!\n"
with open("message.txt","wb") as file:
    file.write(bytes(content,'ascii'))
```

Basierend auf Zeichen eines Alphabets lassen sich nun Wörter über diesem Alphabet einführen.

Definition 1.2 (Wörter eines Alphabets)

Sei \(\Sigma\) ein gewähltes Alphabet.

Als Wort (oder String) über \(\Sigma\) bezeichnet man eine endliche Folge von Zeichen aus \(\Sigma\) einschließlich der leeren Folge, die wir mit \(\epsilon\) notieren und das leere Wort nennen.
Die Länge eines Wortes \(w\) über \(\Sigma\) ist die Anzahl seiner Zeichen. Das leere Wort \(\epsilon\) hat insbesondere die Länge \(0\).
Wir bezeichnen die Menge alle Wörter über \(\Sigma\) (einschließlich des leeren Wortes \(\epsilon\)) mit \(\Sigma^*\). Ist \(n \in \N\), so bezeichnet \(\Sigma^n\) die Menge aller Wörter der Länge \(n\) über \(\Sigma\).

Bemerkung 1.2 (Halbgruppeneigenschaft)

Seien zwei Wörter \(v,w \in \Sigma^*\) gegeben, so lässt sich deren Konkatenation \(v \circ w\) durch Hintereinanderschreiben der beiden Wörter definieren, welches wiederum ein neues Wort erzeugt, d.h. \(v \circ w \coloneqq vw \in \Sigma^*\).

Es lässt sich zeigen, dass es sich bei der mathematischen Struktur \((\Sigma^*, \circ)\) um einen Monoid (d.h. eine Halbgruppe mit neutralem Element) handelt. Das neutrale Element ist hierbei durch das leere Wort \(\epsilon\) gegeben.