RSA-Algorithmus

Nachfolgende Abkürzungen benötigst du für den RSA-Algorithmus:

Abkürzung	Bedeutung
m (message)	Klartext
c (chiffre)	Chiffre
e (encryption)	Verschlüsselungsparameter
d (decryption)	Entschlüsselungsparameter

Am 03.08. reist Bob mittags um 12 Uhr pünktlich mit dem Zug an. Alice hat ihre Recherchen bezüglich RSA erfolgreich abgeschlossen und erläutert Bob nun das RSA-Verfahren, das sie als geeignetes System ausgewählt hat.

Schlüsselerzeugung für das RSA-Public-Key-Kryptosystem:

Wie bereits besprochen, sollten sich Alice und Bob jeweils ein Schlüsselpaar generieren. Dazu wählt man zwei, in etwa gleich große Primzahlen p und q, die jeweils eine Länge von ungefähr 512 - 2048 Bit haben. Anschließend bildet man durch Multiplikation von p und q den Modulus n.
$n = p\cdot q$
Nach dem Satz von Euler gilt also für $n:\ \varphi(n)= \varphi(p\cdot q)=(p-1)\cdot(q-1)$
Nun wählt man sich eine natürliche Zahl e für die gilt:
$ggT(e, \varphi(n))=1$ (Begründung folgt später beim Beweis des RSA-Kryptosystems)
n und e bilden zusammen den öffentlichen Schlüssel.

Der private Schlüssel besteht aus d und n, d wird nun so bestimmt, dass gilt:
$e\cdot d\equiv 1\ (mod \varphi(n))$
$e\cdot d\equiv 1\ (mod\{(p-1)\cdot (q-1)\})$

Folglich bildet d die modulo Inverse zu e und kann, wie in Algorithmus 2.4 beschrieben, bestimmt werden.

Public-Key-RSA-Schlüsselerzeugung:

Public-Key-RSA-Ver- und Entschlüsselung:

Algorithmus 3.0 (1) Alice erzeugt zwei große Primzahlen p und q von ungefähr der gleichen Länge, wobei die Länge der einzelnen Primzahlen zwischen 512 und 2048 Bit betragen sollte. (2) Alice berechnet $n = p\cdot q$ und $\varphi(n)= (p-1)\cdot(q-1)$. (3) Alice wählt eine Zahl $e\ so\ das\ gilt\ 1 <e < < \varphi(n)$, mit $ggT(e, \varphi(n)) =1$ (4) Alice berechnet $d = e^{-1}\ mod\ \varphi(n)$ (5) Der öffentliche Schlüssel von Alice ist (n, e), der private Schlüssel (n, d)

Algorithmus3.1 Zusammenfassung: Bob chiffriert eine Nachricht m für Alice, die diese dechiffriert. (1) Zur Chiffrierung führt Bob die folgenden Schritte aus: (a) Bob besorgt sich den authentischen öffentlichen Schlüssel (n, e) von Alice. (b) Bob berechnet $c = m^e\ mod\ n$ (c) Bob übermittelt c an Alice. (2) Zur Dechiffrierung führt Alice den folgenden Schritt aus: Mit ihrem privaten Schlüssel (n,d) berechnet sie $c^d\ mod\ n = m$

Bob kann sich nicht vorstellen, dass beim Entschlüsseln wirklich der Klartext wieder erscheint. Alice zeigt Bob den zugehörigen Satz und macht einen mathematischen Beweis, um Bob von der Korrektheit des Verfahrens zu überzeugen.

Satz 3.2 Es sei $n = p\cdot q$ mit Primzahlen p und q, wobei $p \neq q$. Weiter gelte $e,d \in \N$ mit $e\cdot d\ mod\ \varphi(n) =1$, und es sei $m\in [0, n-1]$ eine Nachricht. Dann folgt.

$(m^e\ mod\ n)^d\ mod\ n = m$.

Beweis: $c\equiv m^e\ (mod\ n) \Rightarrow c^d\ \equiv m^{ed}\ (mod\ n)$

Wenn ggT (m,p) = 1, so gilt:

$m^{ed} = m^{k\cdot (p-1)\cdot (q-1)+1} = (m^{k\cdot (q-1) )(p-1)} \cdot m$

und daher nach dem Satz von Fermat $m^{ed} \equiv 1\cdot m \equiv m\ (mod\ p)$

Ist m nicht zu p teilerfremd, so folgt $m^{ed} \equiv 0 \equiv m\ (mod\ p)$. Analog ergibt sich $m^{ed} \equiv m\ (mod\ q)$.
Insgesamt folgt, dass sowohl p als auch q und damit auch ihr Produkt $p\cdot q= n$ Teiler von $m^{ed}-m\$ sind. Also gilt:

$m^{ed} -m = k\cdot p\cdot q =k\cdot n\ oder\ (m^{ed} -m) \equiv 0\ (mod\ \{p\cdot q\})$

Damit gilt: $(m^{ed} -m) \equiv (m-m) \equiv 0\ (mod\ \{p\cdot q\})$

Nach den kennen gelernten Modul-Rechenregeln folgt also:

$m^{ed} \equiv m\ (mod\ \{p\cdot q\})\ oder\ m^{ed} \equiv m\ (mod\ n)\ oder\ m^{ed}\ (mod\ n) = m$ □

Nachdem sich Bob nach der „Modulo-Inverse“-Frage von Alice auch mit den mathematischen Grundlagen von RSA beschäftigt hat, erkennt er, dass Alice Recht hat und bei der Dechiffrierung tatsächlich wieder der Klartext erscheint.

Wer einen ausführlicheren Beweis wünscht, der findet diesen hier.