Grundlagen

Assymetrische Verschlüsselungsverfahren (auch: Public Key Encryption) gehen von zwei, nicht auseinanderableitbaren Schlüsseln jedes Teilnehmers aus: Dem öffentlichen allgemein zugänglichen Schlüssel für die Ver- und dem privaten Schlüssel für die Entschlüsselung. Im weiteren Verlauf wird zur Analyse angenommen, daß das mit mit den Schlüsseln verwendete Verfahren sicher, d.h. nicht auflösbar ist. Zuerst zur Definition einiger Grundlagen die sich in der Notation größtenteils an [3] orientieren.

Definition 1 (Alphabet, Buchstaben, Wort)
Sei $\Sigma$ eine endliche, nichtleere Menge. Ein Wort ist eine endliche Folge von Elementen aus $\Sigma$. Die Elemente von $\Sigma$ werden auch Buchstaben oder Symbole genannt. $W(\Sigma)$ ist die Menge aller Wörter über dem Alphabet $\Sigma$.

Definition 2 (Wortlänge)
Sei $\Sigma$ ein Alphabet. Die Abbildung:

$$l:\;W(\Sigma)\;\rightarrow\;I\!N$$

bezeichne die Länge eines Wortes über $\Sigma$.

Definition 3 (leeres Wort)
Das Wort $\lambda$ mit $l(\lambda) = 0$ und $lt(\lambda) = \emptyset$ heißt das leere Wort und $W^+(\Sigma) = W(\Sigma)-\{\lambda\}$ ist die Menge der nichtleeren Wörter über dem Alphabet $\Sigma$.

Definition 4 (Wortsymbole)
Sei $\Sigma$ ein Alphabet und $\gamma \in W(\Sigma)$, dann ist

$$lt(\gamma) \subseteq W(\Sigma)$$

die Menge der in $\gamma$ vorkommenden Symbole.

Definition 5 (Konkatinationen, Präfix, Suffix)
Seien $\phi$ und $\tau$ Wörter über dem Alphabet $\Sigma$. Dann ist das Wort $\gamma = \phi\tau$ die Konkatination (Verkettung) von $\phi$ und $\tau$. $\phi = p(\gamma)$ nennt man dann auch Präfix und $\tau = s(\gamma)$ Suffix von $\phi\tau$. Die Menge $W(\Sigma)^\star$ ist dann die Menge aller Konkatinationen von Wörtern über dem Alphabet $\Sigma$.

Definition 6 (Ver- u. Entschlüsselungsfunktion)
Sei X ein Teilnehmer innerhalb eines kryptographisches Protokolls und $\Sigma$ ein Alphabet, dann bezeichnet die Abbildung:

$$E_x:\;W(\Sigma)\;\rightarrow\;W(\Sigma)$$

die Verschlüsselungsfunktion von X und:

$$D_x:\;W(\Sigma)\;\rightarrow\;W(\Sigma)$$

dessen Entschlüsselungsfunktion mit

$$\forall_{M \in W(\Sigma)}:\;E_x(D_x(M)) = D_x(E_x(M)) = M$$

Seien $E$ und $D$ die Mengen der Ver- und Entschlüsselungsfunktionen aller beteiligten Teilnehmer.

Bemerkung Bei allen im folgenden eingeführten Operatoren und Funktionen, so auch bei den Ver- und Entschlüsselungsfunktionen, ist die Schreibweise $E_xM$ für $X$ Teilnehmer und $M \in W(\Sigma)$ Klartext über Alphabet $\Sigma$ identisch zu $E_x(M)$. Außerdem wird der Teilnehmer eines Protokolls und das Wort seines Namens synonym gebraucht.

Definition 7 (vollständig reduzierte Form)
Sei $\gamma$ ein Wort über dem Alphabet $\Sigma$ und $X$ ein Teilnehmer. Dann ist $\gamma\vert _x$ die gegenüber $X$ vollständig reduzierte Form von $\gamma$, dergestalt, daß iterativ alle Teilwörter $E_x(D_x(\sigma))$ respektive $D_x(E_x(\sigma))$ zu $\sigma$ reduziert wurden.

Das Wort $\overline{\gamma}$ ist dann die gegenüber allen Nutzern des Systems vollständig reduzierte Form von $\gamma$.

Definition 8 (Komplement von Ver- u. Entschlüsselungsfunktionen)
Sei $\gamma$ ein Wort über dem Alphabet $\Sigma$ und $X$ ein Teilnehmer. Das Komplement der Ent- und Verschlüsselungsfunktionen von $X$ ist $E_x^c = D_x$ respektive $D_x^c = E_x$ Das Wort $\gamma^c$ bezeichnet dann das Wort $\gamma$ in dem alle Vorkommen von $E_x$ und $D_x$ durch ihr Komplement ersetzt wurden.

Für die im folgenden betrachteten Protokolle wird angenommen, daß für alle Teilnehmer $X$ die Funktionen aus $E$ frei zugänglich sind während $D_x$ nur dem Teilnehmer $X$ bekannt ist. Die Verschlüsselung wird wie bereits eingangs erwähnt als sicher vorausgesetzt, d.h. die Kenntnis von $E_x(M)$ für $M \in W(\Sigma)$ darf keinerlei Rückschlüsse auf $M$ zulassen.