Beweisarchiv: Kryptografie: Sicherheitsdefinitionen: Äquivalente Definitionen informationstheoretischer Sicherheit

Beweisarchiv: Kryptografie

Sicherheitsdefinitionen: Äquivalente Definitionen informationstheoretischer Sicherheit

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

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

Äquivalente Definitionen informationstheoretischer Sicherheit

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$

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$

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{aligned}W(s)&=\sum _{x}W(x)\cdot W(s|x)\\&=\sum _{x}W(x)\cdot c'\\&=c'\cdot \sum _{x}W(x)\\&=c'\end{aligned}}$

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

${\begin{aligned}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{aligned}}$

Mit $c=c'\cdot |K|$ gilt nun:

$W(s|x)=c=\left|\left\{k\in K|k(x)=s\right\}\right|$

Und damit ist:

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

$\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$

Wikipedia-Verweise

 Satz von Bayes

---

Beweisarchiv: Kryptografie

Sicherheitsdefinitionen: Äquivalente Definitionen informationstheoretischer Sicherheit

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

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