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}/\phi (N)\mathbb{Z},\odot )$ und $e\cdot d\equiv 1mod\phi (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 mmodN$

Beweis

(Multiplikativität und Satz 1 der) Eulersche $\phi$-Funktion, Kongruenz, Größte gemeinsame Teiler, Teilbarkeit und Satz von Euler
Eulersche $\phi$-Funktion
Für die eulersche $\phi$-Funktion gilt: $\phi (n):=\mid G_n\mid$ mit $G_n:=\{a\in \mathbb{N}|1\le a\le n\wedge \mathrm{ggT}(a,n)=1\}$.
Multiplikativität der eulerschen $\phi$-Funktion für Primzahlen
Seien $p$ und $q$ prim und $p\ne q$, dann gilt $\phi (p\cdot q)=\phi (p)\cdot \phi (q)$.
Satz 1 Eigenschaft der $\phi$-Funktion bei Primzahlen
Sei $p$ prim, dann gilt: $\phi (p)=p-1$.
Kongruenz
Seien $a,b\in \mathbb{Z}$ und $m\in \mathbb{N}$, dann gilt $a\equiv bmodm\iff 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\le 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 $\mathrm{ggT}(a,n)=1$, dann gilt $a^{\phi (n)}\equiv 1modn$.

Laut Voraussetzung gilt:

$e\cdot d\equiv 1mod\phi (N)$

$\iff e\cdot d\equiv 1mod\phi (p\cdot q)$, nach Voraussetzung $N=p\cdot q$

$\iff e\cdot d\equiv 1mod\phi (p)\cdot \phi (q)$, wegen der Multiplikativität der $\phi$-Funktion

$\iff e\cdot d\equiv 1mod(p-1)\cdot (q-1)$, wegen Satz 1 Eigenschaft der $\phi$-Funktion bei Primzahlen

$\iff e\cdot d=1+k\cdot (p-1)\cdot (q-1)(*)$ 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)\ne 1$.

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

$(m^e{)}^{d}modN$

$\iff m^{ed}modN$

$\iff m^{1+\phi (N)}modN$, nach $(*)$ mit $\phi (N)=(p-1)\cdot (q-1)$

$\iff m\cdot m^{\phi (N)}modN$

$\iff m\cdot 1modN$, da nach dem Satz von Euler gilt $m^{\phi (N)}\equiv 1modN$

$\iff mmodN$.

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

Fall 2: Sei $ggT(m,N)\ne 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 bmodm\iff 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\le 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 $\mathrm{ggT}(a,n)=1$, dann gilt $a^{\phi (n)}\equiv 1modn$.
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{modc}_i$ gilt. Darüber hinaus ist jedes $g\in \mathbb{Z}$ genau dann eine Lösung der Kongruenz $b\equiv a_i{modc}_i$, wenn gilt $g\equiv bmodc$ 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)\ne 1$.

Wenn wir jedoch trotzdem zeigen, dass

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

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

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

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

$(m^e{)}^d\equiv mmodp$ und $(m^e{)}^d\equiv mmodq$.

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 mmodp$ für $ggT(m,N)=p$

Dann gilt nach Definition der Kongruenz aber auch $m\equiv 0modp$.

Nun betrachten wir $(m^e{)}^{d}modp$.

$(m^e{)}^{d}modp$

$\iff ((k\cdot p{)}^e{)}^{d}modp$

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

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

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

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

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

$(m^e{)}^{d}modq$

$\iff m^{ed}modq$

$\iff m^{ed-1}\cdot mmodq$

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

$\iff m^{(q-1)\cdot k\cdot (p-1)}\cdot mmodq$

$\iff (m^{(q-1)}{)}^{k\cdot (p-1)}\cdot mmodq$

$\iff (m^{\phi (q)}{)}^{k\cdot (p-1)}\cdot mmodq$

$\iff 1^{k\cdot (p-1)}\cdot mmodq$, nach dem Satz von Euler

$\iff mmodq$.

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

Nun können wir den chinesischen Restsatz anwenden:

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

$\iff (m^e{)}^d\equiv mmodN$, 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)\ne 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