Kryptologie/Grundlagen der Kryptologie

Einleitung

Die moderne Kryptologie ist eine Wissenschaft, die sich mit der Entwicklung und Bewertung einer Vielzahl von Verfahren zum Schutz von Informationen beschäftigt. Dabei geht es nicht nur um Geheimhaltung von Informationen in Nachrichten. Stattdessen werden auch weitere Sicherheitsziele verfolgt, wie nachweisen zu können, von wem eine bestimmte Nachricht stammt. Die Entwicklung und Bewertung dieser Verfahren wird in zwei wissenschaftliche Disziplinen unterteilt: Kryptografie und Kryptoanalyse.Die Wissenschaft, die sich mit der Entwicklung solcher Verfahren beschäftigt, nennen wir Kryptografie. Die Suche nach Möglichkeit kryptografische Verfahren zu umgehen oder aber auch deren Sicherheit zu bestätigen ist die Wissenschaft der Kryptoanalyse.

Grundlegender Ablauf

Der grundlegende Ablauf der Verschlüsselung kann in folgende Schritte eingeteilt werden.

Visualisierung des grundlegenden Ablaufs bei Public-Key-Verfahren

• (Verschlüsselungsverfahrens) Auswahl eines Verschlüsselungsverfahrens, über das sich Sender und Empfänger verständigt haben und das für beide bekannt ist. Dabei können Sender und Empfänger unterschiedliche Informationen über das Verschlüsselungsverfahren besitzen.
• (Klartext) Der Sender erstellt oder besitzt eine Klartextnachricht, die sie/er an den Empfänger versenden möchte.
• (Verschlüsselung) Der Sender verschlüsselt die Nachricht (Klartext) und erhält eine veschlüsselte Nachricht (Geheimtext). Die Verschlüsselung erfolgt mit einem Schlüssel, der entweder von Empänger und Sender vertraulich behandelt wird oder (wie bei Public-Key-Verfahren) der Allgemeinheit bekannt ist,
• (Nachrichtenübermittlung) Der Sender übermittelt die verschlüsselte Nachricht an dem Empfänger.
• (Entschlüsselung) Der Empfänger entschlüsselt die verschlüsselte Nachricht (Geheimtext) und erhält dann wieder den Klartext, der vorher von dem Empfänger versschlüsselt wurde.

Bemerkung - Ablauf

In dem obigen Ablauf werden einige wichtige Begriffe der Kryptologie verwendet, die in kryptografischen Lerneinheiten wieder auftauchen. Falls Sie noch weitere Informationen zu den Definitionen benötigen, finden Sie diese als Link angegeben. Im Anschluss an die Definition versuchen Sie dann eine Lernaufgabe zum Einüben der Begriffe.

Aufgaben

Sender-Empfänger-Modell nach Shannon und Weaver

Caesar-Entschlüsselung mit demselben Schlüssel wie oben.

• In dem obigen Ablauf treten die Begriffe "Sender" und "Empfänger" auf. Diese sollten zunächst in ein allgemeineres Sender-Empfänger-Modell nach Shannon und Weaver eingebettet werden. Untersuchen und beschreiben Sie die Gemeinsamkeiten und Unterschiede im dem Modell. Welche weiterführende Aspekte werden durch das Kommunikationmodell von Shannon/Weaver nicht abgedeckt?
• Die Caesar-Verschlüsselung ist eine sehr elementare Verschlüsselungsmethode, die ohne Kenntnis des Schlüssels dekodiert werden kann.
  • Wie viele Kombinationsmöglickeiten gibt es für den unten angegebenen Caesar-Schlüssel.
  • Untersuchen und beschreiben Sie, wie die Caesar-Verschlüsselung funktioniert.

Beispiel für eine Verschiebung um drei Zeichen:

Klar:    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
Geheim:  D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

• Geben Sie die minimalen Informationen an, die Sender und Empfänger benötigen, um die Informationen über den verwendeten Schlüssel auszutauschen.
• Verschlüsseln Sie den folgenden Text:

 alice und bob fahren im urlaub an die nordsee.

Konvention: Der Klartext ist klein geschrieben und der Geheimtext wird groß geschrieben.

Sicherheitsziele

Das obige Beispiel zur Caesar-Verschlüsselung. Selbst wenn man von der Verschiebung des Alphabets (oben und 3 Zeichen) zu einer beliebigen bijektiven Abbildung von einem Klartextalphabet in das Geheimtextalphabet übergeht, so liefert die Häufigkeitsverteilung von Buchstaben in einer Sprache dennoch Hinweise darüber, welche Klartextbuchstaben in welchen Geheimtextbuchstaben verschlüsselt wurde. Daher ist es notwendig, zunächst die Sicherheitsziele bei der Anwendung der Verschlüsselung zu definieren, damit man dann mit Kenntnissen der Kryptoanalyse einschätzen kann, wie gut diese Sicherheitsziele mit bestimmten Verfahren erreicht werden können.

Definition Vertraulichkeit

Höchstens Sender und Empfänger können den Inhalt des Klartextes einer übermittelten Nachricht verstehen.

Definition Authentizität

Der Empfänger einer Nachricht kann sich davon überzeugen, dass die erhaltene Nachricht von einem eindeutigen Sender stammt.

Definition Verbindlichkeit

Der Empfänger der Nachricht kann Dritten gegenüber nachweisen, dass die Nachricht von einem bestimmten Sender stammt.

Aufgabe - Anwendungsgebiete

Nennen Sie Anwendungsgebiete der Kryptologie (z.B. in der Medizin oder Finanzsystem), wobei die Verschlüsselung von Informationen ein wesentliches Mittel ist, um bestimmte Sicherheitsziele zu erreichen!

Kryptosystem

Der oben genannte Ablauf bei der Verschüsselung wird nun durch eine mathematische Definition präzisiert, um die Umsetzung von Sicherheitszielen z.B. in einer Programmierspache nach den mathematischen Vorgaben umsetzen zu können. Die Geheimhaltung von Informationen erfordert einige Eigenschaften, die in der Kryptografie als Kryptosystem bezeichnet werden.

Definition - Kryptosystem

Mathematisch ist ein Kryptosystem als das Tupel $(M,C,K,E,D)$ definiert, welches folgende Eigenschaften besitzt.

• $M$ ist die Menge der möglichen Klartexte
• $C$ ist die Menge der möglichen Geheimtexte
• $K$ ist die Menge der erlaubten Schlüssel
• $E=\{E_{k}:k\in K\}$ mit der Funktion $E_{k}:M\rightarrow C$
• $D=\{D_{k}:k\in K\}$ mit der Funktion $D_{k}:C\rightarrow M$
• Für alle $m\in M$ und $e\in K$ gibt es ein $d\in K$, dass $D_{d}(E_{e}(m))=m$

Bemerkung - Variablennamen

• M = Message/Nachricht (engl: Plaintext)
• C = Ciphertext/Geheimtext
• K = Keys/Schlüssel
• E = Encoder/Verschlüsselung
• D = Decoder/Entschlüsselung

Verkettung von 2 Abbildung als Identität

Die letzte Eigenschaft $D_{d}(E_{e}(m))=m$ liefert die Korrektheit des Verfahrens, d.h. wird eine $m$ mit einem erlaubter Schlüssel $e\in K$ zu $E_{e}(m)$ kodiert und dann mit einem Dekodierschlüssel $d\in K$ über den Dekodierer $D_{d}$ dann wieder entschlüsselt, muss wieder der ursprüngliche Klartext $m=D_{d}(E_{e}(m))$ entstehen.

Bemerkung zu bijektiven Abbildungen

In der Mathematik erscheint diese Prinzip zunächst Ähnlichkeit mit der Verkettung von zwei bijektiven Abbildungen zu haben.

• $E_{e}:\mathbb {R} \to \mathbb {R} ^{+}$ mit $E_{e}(x):=exp(x)$ (Exponentialfunktion)
• $D_{d}:\mathbb {R} ^{+}\to \mathbb {R}$ mit $D_{d}(x):=ln(x)$

Mit einer solchen Definition gilt nämlich für jedes $m\in \mathbb {R}$ auch $m=D_{d}(E_{e}(m))$.

Mit Kryptosystemen kann man diese Eigenschaft $D_{d}(E_{e}(m))=m$ aber auch mit einer Verschlüsselungsfunktion $E_{e}$ erhalten, die zufällig Buchstaben aus dem Klartextalphabet Buchstaben aus dem Geheimtextalphabet zuordnet.

Einführende stochastische Aspekte der Verschlüsselung

• $E_{e}:\mathbb {R} ^{+}{\stackrel {P}{\to }}\mathbb {R}$ mit $E_{e}(x):=(-1)^{X(\omega )}\cdot {\sqrt {x}}$ (Randomisierte Wurzelfunktion). Dabei ist $X:\Omega$ eine Bernoulli-Experiment, das festlegt, ob die Wurzel ein positives oder negatives Vorzeichen bekommt. Diese Abbildung ist also keine deterministische Abbildung sondern nicht-deterministische Abbildung, dessen Ergebnis von dem Ausgang eines Zufallsexperimentes abhängt, Als Beispiel sei hier die Verschlüsselung der Zahl $x=4$ genannt, die z.B. je nach Ausgang des Bernoulli-Experimentes (z.B. Münzwurf) entweder die $-2$ bei Kopf oder $+2$ bei Zahl zugeordnet wird.
• $D_{d}:\mathbb {R} ^{+}\to \mathbb {R}$ mit $D_{d}(x):=x^{2}$

Bei der Überprüfung der Eigenschaft $D_{d}(E_{e}(m))=m$ stellt man fest, dass diese Eigenschaft trotz eines durchgeführten Zufallsexperiments, von dem man den Ausgang bei jedem kodierten Buchstaben nicht kennt, dennoch erfüllt ist.

Stochastische Verschlüsselung

Verwenden Sie die ersten 27 Quadratzahlen aus $\mathbb {N}$ (also 1,4,9,16,25, ...) und verschlüsseln Sie den Klartext

 die band abba singt am abend

Das Geheimzextalphabet sind die Zahlenwert

$...,-5,-4,-3,-2,-1,1,2,3,4,5,...$

Zunächst müssen die Buchstaben mit dem Encoder zunächst in Zahlenwert kodiert werden. Das erfolgt mit der folgenden Tabelle:

Klar-Buchstabe: a b c d e ....

Klar-Zahl:          1  4  9 16 25 ....
Geheim 0 - X(w)=0   1  2  3  4  5 ....
Geheim 1 - X(w)=1  -1 -2 -3 -4 -5 ....

Der so entstehende Geheimtext besteht aus positiven und negativen ganzen Zahlen aus $\mathbb {Z}$.

Aufgabe - Stochastische Abbildungen

Geben Sie zu dem obigen Verfahren an, wie man mit einem gewählten Schlüssel $e$ das Vorgehen so verallgemeinern kann, dass man zu jedem Buchstaben $b$ aus dem Klartextalphabet eine Menge von Zahlen $Z(b)\subset \mathbb {Z}$ zuordnet, wobei der Buchstabe $b$ mit einer stochastischen Gleichverteilung auf $Z(b)$ eine Zahl $b_{e}\in Z(b)$ zugeordnet wird. Wenn die Zahlenmenge $Z(b)\subset \mathbb {Z}$ aus 6 Zahlen besteht, kann man z.B. mit einem Würfelexperiment zufällig die Zahl aus $Z(b)\subset \mathbb {Z}$ auswählen.

• Geben Sie zu dieser Verschlüsselung an, welche Informationen der Empfänger braucht, damit dieser den Geheimtext eindeutig dekodieren kann?
• Was liefet in diesem Fall die Eigenschaft

$b_{1}\not =b_{2}\Longrightarrow Z(b_{1})\cap Z(b_{2})=\emptyset$

für die Dekodierung mit einem passenden Schlüssel $d$?

Bemerkung

Auf mathematischer Ebene umfasst also ein Kryptosystem die Menge aller möglichen Klar- und Geheimtexte, die erlaubten Schlüssel sowie die Verschlüsselungs- und Entschlüsselungsfunktion. Zusätzlich wird verlangt, dass das Verfahren eindeutig den Geheimtext wieder zum Klartext dekodiert. Die Abbildungen zur Verschlüsselung müssen dabei nicht deterministisch im Sinne eine klassischen mathematischen Abbildung funktionieren, sondern können auch von Zufallsexperimenten bei der Verschlüsselung abhängen.

Unterscheidung von Kryptosystemen

Wir können zwei Arten von Kryptosystemen unterscheiden:

• symmetrische Kryptosysteme
• asymmetrische Kryptosysteme

Kryptosysteme können wir außerdem anhand ihrer Sicherheitsziele unterscheiden:

• Verschlüsselungsverfahren
  • Verfolgen das Sicherheitsziel der Vertraulichkeit
• Digitale Signaturen
  • Verfolgen das Sicherheitsziele der Authentizität und Verbindlichkeit

Lernempfehlung

Kursübersicht

Aktuelle Lerneinheit	Empfohlene Lerneinheit
1: Grundlagen der Kryptologie	2: Kodierung von Nachrichten

Siehe auch

• Klartext
• Geheimtext
• Verschlüsselungsverfahrens
• Public-Key-Verfahren
• Schlüssel
• Entschlüsselung
• Tupel
• Kurs:Mathematische Modellbildung