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}}\qquad n=p\cdot q\qquad m\in \mathbb {Z} /n

Für die Wahl der Schlüssel gilt:

c\in \mathbb {Z} /\phi (n)^{\times }\qquad d\equiv c^{-1}{\pmod {\phi (n)}}

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

Behauptung

RSA entschlüsselt korrekt:

(m^{c})^{d}\equiv m^{c\cdot d}\equiv (m^{d})^{c}\equiv m{\pmod {n}}

Beweis

Laut Voraussetzung gilt:

d\equiv c^{-1}{\pmod {\phi (n)}}

\Leftrightarrow \quad c\cdot d\equiv 1{\pmod {(p-1)\cdot (q-1)}}

\Leftrightarrow \quad c\cdot d=1+k\cdot (p-1)\cdot (q-1)\qquad k\in \mathbb {Z} \qquad (*)

Der Satz von Euler-Fermat besagt:

m^{\phi (n)}\equiv 1{\pmod {n}}

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

{\begin{aligned}m^{\phi (p)}&\equiv 1{\pmod {p}}&\qquad m^{\phi (q)}&\equiv 1{\pmod {q}}\\m^{(p-1)}&\equiv 1{\pmod {p}}&\qquad m^{(q-1)}&\equiv 1{\pmod {q}}\\m^{k\cdot (p-1)\cdot (q-1)}&\equiv 1^{k\cdot (q-1)}{\pmod {p}}&\qquad m^{k\cdot (p-1)\cdot (q-1)}&\equiv 1^{k\cdot (p-1)}{\pmod {q}}\\m^{k\cdot (p-1)\cdot (q-1)}&\equiv 1{\pmod {p}}&\qquad m^{k\cdot (p-1)\cdot (q-1)}&\equiv 1{\pmod {q}}\\m^{1+k\cdot (p-1)\cdot (q-1)}&\equiv m{\pmod {p}}&\qquad m^{1+k\cdot (p-1)\cdot (q-1)}&\equiv m{\pmod {q}}\qquad (**)\\\end{aligned}}

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.