Beweisarchiv: Kryptografie: Sicherheitsdefinitionen: Äquivalente Definitionen informationstheoretischer Sicherheit

Aus Wikibooks

Wechseln zu: Navigation, Suche

Beweisarchiv: Kryptografie

Sicherheitsdefinitionen: Äquivalente Definitionen informationstheoretischer Sicherheit

Kryptosysteme: Korrektheit des RSA-Kryptosystems · Sicherheit des GMR-Signatursystems

Pseudozufall: Sicherheit des s²-mod-n-Generators

Inhaltsverzeichnis

1 Äquivalente Definitionen informationstheoretischer Sicherheit
2 Wikipedia-Verweise

[Bearbeiten] Äquivalente Definitionen informationstheoretischer Sicherheit

[Bearbeiten] Definitionen

Informell: Der Schlüsseltext eines informationstheoretisch sicher verschlüsselten Klartextes liefert einem Angreifer keine Informationen über die Wahrscheinlichkeit eines bestimmten Klartextes. Bei ungleichmäßiger Verteilung der Klartexte, aber gleichmäßiger Verteilung der Schlüssel ist also auch eine gleichmäßige Verteilung der Schlüsseltexte garantiert.

Es sei $X$ die Menge aller möglichen Klartexte, $S$ die Menge aller Schlüsseltexte und $K$ die Menge aller Schlüssel.

Definition 1:

$(1) \qquad \forall s \in S \quad \forall x \in X: W(x) = W(x|s)$

Definition 2:

$(2) \qquad \forall s \in S \quad \forall x \in X \quad \exists c \in \mathbb{N}: \left| \left\{k \in K | k(x) = s \right\} \right| = c$

[Bearbeiten] Behauptung

Beide Definitionen sind äquivalent, also ist zu zeigen, dass:

$\forall s \in S \quad \forall x \in X: W(x) = W(x|s)$

$\Leftrightarrow \quad \forall s \in S \quad \forall x \in X \quad \exists c \in \mathbb{N}: \left| \left\{k \in K | k(x) = s \right\} \right| = c$

[Bearbeiten] Beweis

$W(a|b) = \frac{W(a) \cdot W(b|a)}{W(b)}$ (Satz von Bayes)

Daraus folgt:

$(3) \qquad \forall s \in S \quad \forall x \in X: W(x) = W(x|s)$

$\Leftrightarrow \quad \forall s \in S \quad \forall x \in X: W(s) = W(s|x)$

Nun zeigt man, dass dies äquivalent ist zu:

$(4) \qquad \forall s \in S \quad \forall x \in X \quad \exists c' \in \mathbb{R}: W(s|x) = c'$

Dazu zeigt man beide Richtungen der Äquivalenz getrennt.

$(3) \Rightarrow (4)$ :

Da alle Schlüsseltexte gleich verteilt sind, sei

c': = W (s)

.

$(3) \Leftarrow (4)$ :

$W(x) \cdot W(s|x)$ ist die Wahrscheinlichkeit, dass ein bestimmter Klartext in einen bestimmten Schlüsseltext verschlüsselt wird.

$\begin{align} W(s) & = \sum_{x} W(x) \cdot W(s|x)\\ & = \sum_{x} W(x) \cdot c' \\ & = c' \cdot \sum_{x} W(x) \\ & = c' \end{align}$

Nun muss man noch zeigen, dass $(4)$ äquivalent zu $(2)$ ist:

$\begin{align} W(s|x) & = W(k \in K: k(x) = s) \\ & = \frac{ \left| \left\{ k \in K | k(x) = s \right\} \right| }{ \left| K \right| } \\ c' & = \frac{ \left| \left\{ k \in K | k(x) = s \right\} \right| }{ \left| K \right| } \\ c' \cdot \left| K \right| & = \left| \left\{ k \in K | k(x) = s \right\} \right|\\ \end{align}$