Einleitung

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

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

Für die Wahl der Schlüssel gilt:

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

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

Behauptung

RSA entschlüsselt korrekt:

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

Beweis

Laut Voraussetzung gilt:

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

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

${\displaystyle \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:

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

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

${\displaystyle {\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 ${\displaystyle \mathbb {Z} /n}$. Deshalb muss noch gezeigt werden, dass (**) auch für die teilerfremden Elemente in ${\displaystyle \mathbb {Z} /p}$ und ${\displaystyle \mathbb {Z} /q}$ gilt. Das einzige teilerfremde Element in beiden Ringen ist die Null.

Da

${\displaystyle {\begin{aligned}0^{1+k\cdot (p-1)\cdot (q-1)}&\equiv 0{\pmod {p}}&\qquad 0^{1+k\cdot (p-1)\cdot (q-1)}&\equiv 0{\pmod {q}}\\\end{aligned}}}$

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

Nach dem Chinesischem Restsatz folgt daraus:

${\displaystyle {\begin{aligned}m\cdot m^{k\cdot (p-1)\cdot (q-1)}&\equiv m\cdot 1{\pmod {p\cdot q}}\\m\cdot m^{k\cdot (p-1)\cdot (q-1)}&\equiv m\cdot 1{\pmod {n}}\\m^{1+k\cdot (p-1)\cdot (q-1)}&\equiv m{\pmod {n}}\\\end{aligned}}}$

Nun erhält man durch Einsetzen von ${\displaystyle (*)}$:

${\displaystyle m^{c\cdot d}\equiv m{\pmod {n}}}$