Beweisarchiv: Kryptografie: Kryptosysteme: Korrektheit des RSA-Kryptosystems

Korrektheit des RSA-Kryptosystems

Einleitung

Das RSA-Kryptosystem verschlüsselt einen Klartext $m$, indem dieser mit dem öffentlichen Schlüssel $c$ exponentiert wird. Der Schlüsseltext $m^c$ kann durch Exponentieren mit dem geheimen Schlüssel $d$ wieder entschlüsselt werden. Es gelten dabei folgende Voraussetzungen:

$p,q\text{ prim}n=p\cdot qm\in \mathbb{Z}/n$

Für die Wahl der Schlüssel gilt:

$c\in \mathbb{Z}/\varphi (n{)}^{\times }d\equiv c^{-1}(\mathrm{mod}\varphi (n))$

$\varphi (n)$ bezeichnet die eulersche φ-Funktion.

Behauptung

RSA entschlüsselt korrekt:

$(m^c{)}^d\equiv m^{c\cdot d}\equiv (m^d{)}^c\equiv m(\mathrm{mod}n)$

Beweis

Laut Voraussetzung gilt:

$d\equiv c^{-1}(\mathrm{mod}\varphi (n))$

$\iff c\cdot d\equiv 1(\mathrm{mod}(p-1)\cdot (q-1))$

$\iff c\cdot d=1+k\cdot (p-1)\cdot (q-1)k\in \mathbb{Z}(*)$

Der Satz von Euler-Fermat besagt:

$m^{\varphi (n)}\equiv 1(\mathrm{mod}n)$

Also gilt $\text{mod }p$ und $\text{mod }q$:

$\begin{array}{cccc}{m}^{\varphi (p)}& \equiv 1(\mathrm{mod}p)& m^{\varphi (q)}& \equiv 1(\mathrm{mod}q)\\ m^{(p-1)}& \equiv 1(\mathrm{mod}p)& m^{(q-1)}& \equiv 1(\mathrm{mod}q)\\ m^{k\cdot (p-1)\cdot (q-1)}& \equiv 1^{k\cdot (q-1)}(\mathrm{mod}p)& m^{k\cdot (p-1)\cdot (q-1)}& \equiv 1^{k\cdot (p-1)}(\mathrm{mod}q)\\ m^{k\cdot (p-1)\cdot (q-1)}& \equiv 1(\mathrm{mod}p)& m^{k\cdot (p-1)\cdot (q-1)}& \equiv 1(\mathrm{mod}q)\\ m^{1+k\cdot (p-1)\cdot (q-1)}& \equiv m(\mathrm{mod}p)& m^{1+k\cdot (p-1)\cdot (q-1)}& \equiv m(\mathrm{mod}q)(**)\\ \end{array}$

Der Satz von Euler-Fermat gilt nur für die Einheiten in $\mathbb{Z}/n$. Deshalb muss noch gezeigt werden, dass (**) auch für die teilerfremden Elemente in $\mathbb{Z}/p$ und $\mathbb{Z}/q$ gilt. Das einzige teilerfremde Element in beiden Ringen ist die Null.

Da

$\begin{array}{cccc}{0}^{1+k\cdot (p-1)\cdot (q-1)}& \equiv 0(\mathrm{mod}p)& 0^{1+k\cdot (p-1)\cdot (q-1)}& \equiv 0(\mathrm{mod}q)\\ \end{array}$

gilt (**) für alle Elemente aus $\mathbb{Z}/p$ und $\mathbb{Z}/q$

Nach dem Chinesischen Restsatz folgt daraus:

$\begin{array}{cc}m\cdot m^{k\cdot (p-1)\cdot (q-1)}& \equiv m\cdot 1(\mathrm{mod}p\cdot q)\\ m\cdot m^{k\cdot (p-1)\cdot (q-1)}& \equiv m\cdot 1(\mathrm{mod}n)\\ m^{1+k\cdot (p-1)\cdot (q-1)}& \equiv m(\mathrm{mod}n)\\ \end{array}$

Nun erhält man durch Einsetzen von $(*)$:

$m^{c\cdot d}\equiv m(\mathrm{mod}n)$

Wikipedia-Verweise

Vorlage:W
Vorlage:W
Vorlage:W
Vorlage:W

---