RSA-Algorithmus: Unterschied zwischen den Versionen

Aus RMG-Wiki
Wechseln zu: Navigation, Suche
Zeile 50: Zeile 50:
 
   </tr>
 
   </tr>
 
   <tr>
 
   <tr>
−
     <td><div style = "text-align: left; padding:10px; width: 500px; height: 200px; border: 2px solid #E5CC00;border-color: orange;">'''Algorithmus 3.0''' <br>
+
     <td><div style = "text-align: left; padding:10px; width: 500px; height: 200px; border: 2px solid #E5CC00;border-color: orange;">'''Algorithmus 3.0'''<ref name=W14>Die Algorithmen 3.0 und 3.1, sowie Satz 3.2 wurden aus [14, S.71 f.] übernommen</ref> <br>
 
(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.<br>
 
(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.<br>
 
(2) Alice berechnet <math>n = p\cdot q</math> und <math>\varphi(n)= (p-1)\cdot(q-1)</math>.<br>
 
(2) Alice berechnet <math>n = p\cdot q</math> und <math>\varphi(n)= (p-1)\cdot(q-1)</math>.<br>
Zeile 56: Zeile 56:
 
(4) Alice berechnet <math>d = e^{-1}\ mod\ \varphi(n)</math><br>
 
(4) Alice berechnet <math>d = e^{-1}\ mod\ \varphi(n)</math><br>
 
(5) Der öffentliche Schlüssel von Alice ist (n, e), der private Schlüssel (n, d)<br></div></td>
 
(5) Der öffentliche Schlüssel von Alice ist (n, e), der private Schlüssel (n, d)<br></div></td>
−
     <td><div style = "text-align: left; padding:10px; width: 500px;height: 200px; border: 2px solid #E5CC00;border-color: orange;">'''Algorithmus3.1 '''<br>
+
     <td><div style = "text-align: left; padding:10px; width: 500px;height: 200px; border: 2px solid #E5CC00;border-color: orange;">'''Algorithmus3.1 '''<ref name=W14 /><br>
 
Zusammenfassung: Bob chiffriert eine Nachricht m für Alice, die diese dechiffriert.<br>
 
Zusammenfassung: Bob chiffriert eine Nachricht m für Alice, die diese dechiffriert.<br>
 
<br>
 
<br>
Zeile 71: Zeile 71:
 
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.<br>
 
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.<br>
 
<br>
 
<br>
−
'''Satz 3.2''' Es sei <math>n = p\cdot q</math> mit Primzahlen p und q, wobei <math>p \neq q</math>. Weiter gelte <math>e,d \in \N</math> mit <math> e\cdot d\ mod\ \varphi(n) =1</math>, und es sei <math>m\in  [0, n-1]</math> eine Nachricht. Dann folgt.<br>
+
'''Satz 3.2'''<ref name=W14 /> Es sei <math>n = p\cdot q</math> mit Primzahlen p und q, wobei <math>p \neq q</math>. Weiter gelte <math>e,d \in \N</math> mit <math> e\cdot d\ mod\ \varphi(n) =1</math>, und es sei <math>m\in  [0, n-1]</math> eine Nachricht. Dann folgt.<br>
 
<br>
 
<br>
 
<math>(m^e\ mod\ n)^d\  mod\ n = m</math>.<br>
 
<math>(m^e\ mod\ n)^d\  mod\ n = m</math>.<br>
 
<br>
 
<br>
−
<u>Beweis:</u> <math>c\equiv m^e\ (mod\ n)  \Rightarrow c^d\ \equiv m^{ed}\ (mod\ n)</math><br>
+
<u>Beweis:</u><ref>[5, S.6]</ref> <math>c\equiv m^e\ (mod\ n)  \Rightarrow c^d\ \equiv m^{ed}\ (mod\ n)</math><br>
 
<br>
 
<br>
 
Wenn ggT (m,p) = 1, so gilt:<br>
 
Wenn ggT (m,p) = 1, so gilt:<br>
Zeile 140: Zeile 140:
 
Bevor du, gemeinsam mit Alice und Bob, zur praktischen Übung an einem Computerprogamm übergehen kannst, solltest du wissen, was sich hinter ASCII verbirgt.<br>
 
Bevor du, gemeinsam mit Alice und Bob, zur praktischen Übung an einem Computerprogamm übergehen kannst, solltest du wissen, was sich hinter ASCII verbirgt.<br>
 
<br>
 
<br>
−
Da man gewöhnlich 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ück erhält.<br>
+
Da man gewöhnlich 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ück erhält.<ref>[6, vgl. S. 394 f.]<ref><br>
 
<br>
 
<br>
 
<popup name="Für Interessierte: Die Gefahr des gleichen Modulus &nbsp;&nbsp;  ">
 
<popup name="Für Interessierte: Die Gefahr des gleichen Modulus &nbsp;&nbsp;  ">
Zeile 148: Zeile 148:
 
LINK zur Anwendungsseite folgt.<br>
 
LINK zur Anwendungsseite folgt.<br>
 
<br>
 
<br>
 +
<br>
 +
----
 +
 +
<references />
 +
[[Benutzer:Deininger_Matthias/Facharbeit/Literaturverzeichnis| siehe dazu Literaturverzeichnis]]

Version vom 3. September 2010, 14:53 Uhr

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]

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

Beweis:[2] 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.

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 der ggT mittels Euklidischem 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 bestimmen wir 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 Computerprogamm übergehen kannst, solltest du wissen, was sich hinter ASCII verbirgt.

Da man gewöhnlich 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ück erhält.Referenzfehler: Für ein <ref>-Tag fehlt ein schließendes </ref>-Tag.
Referenzfehler: Es sind <ref>-Tags vorhanden, jedoch wurde kein <references />-Tag gefunden.

Von „http://rmg.zum.de/index.php?title=Benutzer:Deininger_Matthias/Facharbeit/RSA-Algorithmus&oldid=34776“