RSA-Algorithmus

Aus RMG-Wiki
Wechseln zu: Navigation, Suche
Buch.PNG 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]

(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 [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[1] 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.


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.

Sehfehler.PNG
© 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.[3]



Anwendung des RSA-Algorithmus

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

weiter weiter zur Sicherheit von RSA

zurück zur Übersicht


  1. 1,0 1,1 1,2 [12, S.71 f.]
  2. [3, S.6]
  3. vgl. [4, S. 394 f.]

siehe dazu Literaturverzeichnis