Kryptologie/Korrektheit des RSA-Verschlüsselungsverfahrens

Einleitung

Wir haben nun die drei Algorithmen des RSA-Verschlüsselungsverfahren kennengelernt und beispielhaft durchgeführt. Nun bleibt zu zeigen, warum das Verfahren korrekt ist. Es muss für alle Klartexte $m\in M$ also gelten, dass der Entschlüsselungsalgorithmus $D$ den verschlüsselten Klartext in den ursprünglichen Klartext $m$ umwandelt. Die wichtigste Grundlage für den Ver- und Entschlüsselungsalgorithmus des RSA-Algorithmus ist der Satz von Euler.

Beweis Korrektheit des RSA-Verfahrens

Voraussetzung

Seien $p,q$ prim, $N=p\cdot q$ $m\in \mathbb {Z} /N\mathbb {Z}$, $e\in (\mathbb {Z} /\varphi (N)\mathbb {Z} ,\odot )$ und $e\cdot d\equiv 1{\bmod {\varphi (N)}}$

Zu zeigen

RSA-Algorithmus entschlüsselt korrekt, d.h. für alle $m\in \mathbb {Z} /N\mathbb {Z}$ gilt $c^{d}\equiv (m^{e})^{d}\equiv m^{e\cdot d}\equiv (m^{d})^{e}\equiv m{\bmod {N}}$

Beweis

(Multiplikativität und Satz 1 der) Eulersche $\varphi$-Funktion, Kongruenz, Größte gemeinsame Teiler, Teilbarkeit und Satz von Euler
Eulersche $\varphi$-Funktion
Für die eulersche $\varphi$-Funktion gilt: $\varphi (n)\;:=\mid G_{n}\mid$ mit $G_{n}:=\;\{a\in \mathbb {N} \,|\,1\leq a\leq n\land \operatorname {ggT} (a,n)=1\}$.
Multiplikativität der eulerschen $\varphi$-Funktion für Primzahlen
Seien $p$ und $q$ prim und $p\neq q$, dann gilt $\varphi (p\cdot q)=\varphi (p)\cdot \varphi (q)$.
Satz 1 Eigenschaft der $\varphi$-Funktion bei Primzahlen
Sei $p$ prim, dann gilt: $\varphi (p)=p-1$.
Kongruenz
Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$, dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$.
Größte gemeinsame Teiler
Seien $a,b\in \mathbb {Z}$, wobei mindestens eine der beiden Zahlen ungleich Null. Wir bezeichnen $d:=ggT(a,b)$ mit $d\in \mathbb {N}$ als den größten gemeinsamen Teiler der Zahlen $a$ und $b$, falls gilt: $(1)$: $d\mid a$ und $d\mid b$ und $(2)$: Für alle $c\in \mathbb {Z}$ mit $c\mid a$ und $c\mid b\Rightarrow c\leq d$.
Teilbarkeit
Eine ganze Zahl $a$ teilt eine ganze Zahl $b$ genau dann, wenn es eine ganze Zahl $n$ gibt, für die $a\cdot k=b$ ist. Wir schreiben $a\mid b$.
Satz von Euler
Seien $a,n\in \mathbb {N}$ und $\operatorname {ggT} (a,n)=1$, dann gilt $a^{\varphi (n)}\equiv 1{\bmod {n}}$.

Laut Voraussetzung gilt:

$e\cdot d\equiv 1{\bmod {\varphi (N)}}$

$\Leftrightarrow e\cdot d\equiv 1{\bmod {\varphi (p\cdot q)}}$, nach Voraussetzung $N=p\cdot q$

$\Leftrightarrow e\cdot d\equiv 1{\bmod {\varphi (p)\cdot \varphi (q)}}$, wegen der Multiplikativität der $\varphi$-Funktion

$\Leftrightarrow e\cdot d\equiv 1{\bmod {(p-1)\cdot (q-1)}}$, wegen Satz 1 Eigenschaft der $\varphi$-Funktion bei Primzahlen

$\Leftrightarrow e\cdot d=1+k\cdot (p-1)\cdot (q-1)\quad (*)$ mit $k\in \mathbb {Z}$ und wegen der Definition der Kongruenz und Teilbarkeit.

Wir unterscheiden zunächst zwei Fälle:

$ggT(m,N)=1$ und $ggT(m,N)\neq 1$.

Fall 1: Sei $ggT(m,N)=1$:

$(m^{e})^{d}{\bmod {N}}$

$\Leftrightarrow m^{ed}{\bmod {N}}$

$\Leftrightarrow m^{1+\varphi (N)}{\bmod {N}}$, nach $(*)$ mit $\varphi (N)=(p-1)\cdot (q-1)$

$\Leftrightarrow m\cdot m^{\varphi (N)}{\bmod {N}}$

$\Leftrightarrow m\cdot 1{\bmod {N}}$, da nach dem Satz von Euler gilt $m^{\varphi (N)}\equiv 1{\bmod {N}}$

$\Leftrightarrow m{\bmod {N}}$.

Wir müssen nun also nur noch den zweitem Fall betrachten.

Fall 2: Sei $ggT(m,N)\neq 1$.

Kongruenz, Größte gemeinsame Teiler, Teilbarkeit, Satz von Euler und chinesischer Restsatz
Kongruenz
Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$, dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$.
Größte gemeinsame Teiler
Seien $a,b\in \mathbb {Z}$, wobei mindestens eine der beiden Zahlen ungleich Null. Wir bezeichnen $d:=ggT(a,b)$ mit $d\in \mathbb {N}$ als den größten gemeinsamen Teiler der Zahlen $a$ und $b$, falls gilt: $(1)$: $d\mid a$ und $d\mid b$ und $(2)$: Für alle $c\in \mathbb {Z}$ mit $c\mid a$ und $c\mid b\Rightarrow c\leq d$.
Teilbarkeit
Eine ganze Zahl $a$ teilt eine ganze Zahl $b$ genau dann, wenn es eine ganze Zahl $n$ gibt, für die $a\cdot k=b$ ist. Wir schreiben $a\mid b$.
Satz von Euler
Seien $a,n\in \mathbb {N}$ und $\operatorname {ggT} (a,n)=1$, dann gilt $a^{\varphi (n)}\equiv 1{\bmod {n}}$.
Chinesische Restsatz
Seien $c_{1},c_{2},\dots ,c_{v}\in \mathbb {N}$ paarweise teilerfremd in $\mathbb {Z}$, $v\in \mathbb {N}$ und $a_{1},a_{2},\dots ,a_{v}\in \mathbb {Z}$. Dann existiert eine Lösung $b\in \mathbb {Z}$, sodass für jedes $i\in \{1,2,\dots ,v\}$ die Kongruenz $b\equiv a_{i}{\bmod {c}}_{i}$ gilt. Darüber hinaus ist jedes $g\in \mathbb {Z}$ genau dann eine Lösung der Kongruenz $b\equiv a_{i}{\bmod {c}}_{i}$, wenn gilt $g\equiv b{\bmod {c}}$ mit $c=c_{1}\cdot c_{2}\cdot \dots \cdot c_{v}$.

Wegen $N=p\cdot q$ gilt dann also entweder $ggT(m,N)=p$ oder $ggT(m,N)=q$.

Hier ist der Satz von Euler nicht anwendbar, wegen $ggT(m,N)\neq 1$.

Wenn wir jedoch trotzdem zeigen, dass

$(m^{e})^{d}\equiv m{\bmod {p}}$ und $(m^{e})^{d}\equiv m{\bmod {q}}$, dann können wir (wegen $ggT(p,q)=1$) den chinesischen Restsatz anwenden und erhalten:

$(m^{e})^{d}\equiv m{\bmod {(}}p\cdot q)$

$\Leftrightarrow (m^{e})^{d}\equiv m{\bmod {N}}$, wegen $N=p\cdot q$.

Wir zeigen dies nun für den Fall $ggT(m,N)=p$, dass gilt:

$(m^{e})^{d}\equiv m{\bmod {p}}$ und $(m^{e})^{d}\equiv m{\bmod {q}}$.

Sei $ggT(m,N)=p$.

Es gilt dann nach Definition der größten gemeinsamen Teilers $p\mid m$ bzw. nach Definition der Teilbarkeit $m=k\cdot p$ mit $k>0$.

Wir zeigen zunächst $(m^{e})^{d}\equiv m{\bmod {p}}$ für $ggT(m,N)=p$

Dann gilt nach Definition der Kongruenz aber auch $m\equiv 0{\bmod {p}}$.

Nun betrachten wir $(m^{e})^{d}{\bmod {p}}$.

$(m^{e})^{d}{\bmod {p}}$

$\Leftrightarrow ((k\cdot p)^{e})^{d}{\bmod {p}}$

$\Leftrightarrow 0{\bmod {p}}$, da $((k\cdot p)^{e})^{d}$ ein Vielfaches von $p$ ist.

Also gilt $(m^{e})^{d}\equiv 0{\bmod {p}}$ und insgesamt

$m\equiv (m^{e})^{d}\equiv 0{\bmod {p}}$.

Nun bleibt noch zu zeigen, dass $(m^{e})^{d}\equiv m{\bmod {q}}$ für $ggT(m,N)=p$.

Da $ggT(m,q)=1$, kann man den Satz von Euler anwenden.

$(m^{e})^{d}{\bmod {q}}$

$\Leftrightarrow m^{ed}{\bmod {q}}$

$\Leftrightarrow m^{ed-1}\cdot m{\bmod {q}}$

$\Leftrightarrow m^{k\cdot (p-1)\cdot (q-1)}\cdot m{\bmod {q}}$, nach $(*)$: $e\cdot d-1=k\cdot (p-1)\cdot (q-1)$ (in umgestellter Form)

$\Leftrightarrow m^{(q-1)\cdot k\cdot (p-1)}\cdot m{\bmod {q}}$

$\Leftrightarrow (m^{(q-1)})^{k\cdot (p-1)}\cdot m{\bmod {q}}$

$\Leftrightarrow (m^{\varphi (q)})^{k\cdot (p-1)}\cdot m{\bmod {q}}$

$\Leftrightarrow 1^{k\cdot (p-1)}\cdot m{\bmod {q}}$, nach dem Satz von Euler

$\Leftrightarrow m{\bmod {q}}$.

Also gilt für $ggT(m,N)=p$: $(m^{e})^{d}\equiv m{\bmod {q}}$.

Nun können wir den chinesischen Restsatz anwenden:

$(m^{e})^{d}\equiv m{\bmod {(}}p\cdot q)$

$\Leftrightarrow (m^{e})^{d}\equiv m{\bmod {N}}$, wegen $N=p\cdot q$.

Wir haben also nun gezeigt, dass das RSA-Verschlüsselungsverfahren für $ggT(m,N)=p$ korrekt ist. Dies können wir für $ggT(m,N)=q$ analog zeigen, indem wir in der Notation $p$ und $q$ vertauschen. Sie können dies freiwillig eigenständig durchführen.

Damit haben wir die Korrektheit des RSA-Verschlüsselungsverfahrens für alle Fälle, nämlich $ggT(m,N)=1$ und $ggT(m,N)\neq 1$, gezeigt■

Lernempfehlung

Kursübersicht

Übergeordnete Lerneinheit
6: RSA-Kryptosystem
Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
7.3: Entschlüsselungsalgorithmus des RSA-Verschlüsselungsverfahrens	8: Korrektheit des RSA-Verschlüsselungsverfahrens	9: RSA-Signatur
Grundlagen der aktuellen Lerneinheit
8.1: Satz von Euler	8.2: Chinesischer Restsatz