Beweisarchiv: Kryptografie: Kryptosysteme: Korrektheit des RSA-Kryptosystems

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

[Bearbeiten] Korrektheit des RSA-Kryptosystems

[Bearbeiten] 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)}$

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

[Bearbeiten] Behauptung

RSA entschlüsselt korrekt:

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

[Bearbeiten] 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 $mod p$ und $mod q$ :

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

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{align} 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{align}$

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

Nach dem Chinesischem Restsatz folgt daraus:

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