RSA-Algorithmus

Fachwortverzeichnis

RSA-Algorithmus

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

Abkürzung	Bedeutung
m (message)	Klartext
c (chiffre)	Chiffretext
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)
e und n 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\ dass\ 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 (e, n), der private Schlüssel (d, n)

Algorithmus 3.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 (e, n) 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 (d, n) 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 anzeigen

Beweis verstecken

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\}$

Daraus folgt:
$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.

© Klaus Schmeh aus "Kryptografie. Verfahren–Protokolle–Infrastrukturen"

Nachfolgend möchten Alice und Bob das Verfahren zum ersten Mal testen und wählen daher als Klartext die Zahl 20. Da sie noch kein Computerprogramm haben, mit dessen Hilfe sich das Verfahren auch mit großen Moduli n einfach umsetzen lässt, wählen sie zu Übungszwecken kleine Primzahlen p und q.

Schlüsselerzeugung:
Bob wählt:
p = 5
q = 17
$\Rightarrow n = p\cdot q = 5\cdot 17=85$
für $\varphi(n)= (p-1)\cdot (q-1)= (5-1)\cdot (17-1)=4\cdot 16 =64$

für e mit 0 < e << 120 wählt er e = 5, so dass gilt ggT(5,64) = 1

(5,85) ist damit der öffentliche Schlüssel von Bob, den er Alice übergibt, so dass sie damit die Nachricht an ihn verschlüsseln kann.

Anschließend bestimmt Bob mittels des Algorithmus 2.1 die modulare Inverse d zu e mod n, die zusammen mit dem Modulus n seinen geheimen privaten Schlüssel ergibt.
$5\cdot d\ mod\ 64 = 1$

Berechnung des größten gemeinsamen Teilers mittels des Euklidischen Algorithmus, welcher zur Bestimmung der Vielfachsummendarstellung benötigt wird.
$64 = 5\cdot 12+4$
$5\ = 4\cdot 1+1$
$4\ = 1\cdot 4+0$

Hieraus bestimmt Bob die Vielfachsummendarstellung:
$1 = 5-1\cdot 4=$
    $\quad = 5- 1\cdot (64-5\cdot 12)= 13\cdot 5-1\cdot 64$

d= 13 => Der private Schlüssel von Bob lautet (13,85)

Verschlüsselung:

Nun kann Alice die Nachricht m = 20 an Bob verschlüsseln
$c= m^e\ mod\ n$
$20^5\ mod\ 85 = 3200000\ mod\ 85 = 5 = c$
Anschließend übermittelt Alice die Chiffre c = 5 an Bob.

Entschlüsselung:

Bob entschlüsselt die Nachricht mit seinem privaten Schlüssel, wie folgt:
$m= c^d\ mod\ n$
$5^{13}\ mod\ 85 = 1220703125\ mod\ 85 = 20 = m$

Bevor du gemeinsam mit Alice und Bob zur praktischen Übung an einem Computerprogramm übergehen kannst, solltest du wissen, was sich hinter ASCII verbirgt.

Da man in der Regel Texte, also Ansammlungen von Buchstaben und Zahlen, verschlüsseln möchte, Programme aber nur Zahlen chiffrieren können, wurde bereits in den 1960er Jahren der ASCII- Standard (American Standard Code for Information Interchange) von der American Standards Association entwickelt. Mit ASCII ist es möglich, jede Ziffer und jeden Buchstaben als Zahl zu repräsentieren. Dieser ASCII-Code kann anschließend verschlüsselt werden. Nach dem Dechiffrieren kann der ASCII-Code, wieder in die entsprechenden Buchstaben und Ziffern umgewandelt werden, so dass man den Klartext zurückerhält.

Für Interessierte: Die Gefahr des gleichen Modulus    anzeigen

Für Interessierte: Die Gefahr des gleichen Modulus    verstecken

Wenn zwei Benutzer den gleichen Modulus n besitzen, also auch gleiche Primzahlen p und q haben, könnten sie mithilfe des öffentlichen Schlüssels e des Anderen, dessen privaten Schlüssel d (= modulare Inverse zu e) berechnen und somit die verschlüsselten Nachrichten des anderen lesen. Es ist deshalb darauf zu achten, dass niemals zwei Personen den gleichen Modulus n besitzen, bei 200-stelligen Moduli, die in der Praxis eingesetzt werden, ist dies aber ohnehin unrealistisch.

Hier kannst du das neu erworbene Wissen praktisch ausprobieren. Viel Spaß!


weiter zur Sicherheit von RSA

zurück zur Übersicht

---

siehe dazu Literaturverzeichnis