RSA-Algorithmus: Unterschied zwischen den Versionen

Aus RMG-Wiki
Wechseln zu: Navigation, Suche
 
(30 dazwischenliegende Versionen von einem Benutzer werden nicht angezeigt)
Zeile 1: Zeile 1:
 +
<div style="text-align:right;">[[Bild:Buch.PNG]][[Benutzer:Deininger_Matthias/Facharbeit/Fachwortverzeichnis| Fachwortverzeichnis]]</div>
 
===RSA-Algorithmus===
 
===RSA-Algorithmus===
 
<br>
 
<br>
Zeile 14: Zeile 15:
 
<tr>
 
<tr>
 
     <td>c (chiffre)</td>
 
     <td>c (chiffre)</td>
−
     <td>Chiffre</td>
+
     <td>Chiffretext</td>
 
   </tr>
 
   </tr>
 
<tr>
 
<tr>
Zeile 28: Zeile 29:
 
<br>
 
<br>
 
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.<br>
 
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.<br>
−
<br>
 
−
<u>Schlüsselerzeugung für das RSA-Public-Key-Kryptosystem:</u><br>
 
−
<br>
 
−
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.<br>
 
−
<math>n = p\cdot q</math><br>
 
−
Nach dem Satz von Euler gilt also für <math>n:\ \varphi(n)= \varphi(p\cdot q)=(p-1)\cdot(q-1)</math><br>
 
−
Nun wählt man sich eine natürliche Zahl e für die gilt:<br>
 
−
<math>ggT(e, \varphi(n))=1</math> (Begründung folgt später beim Beweis des RSA-Kryptosystems)<br>
 
−
n und e bilden zusammen den öffentlichen Schlüssel. <br>
 
−
<br>
 
−
Der private Schlüssel besteht aus d und n, d wird nun so bestimmt, dass gilt:<br>
 
−
<math> e\cdot d\equiv 1\ (mod \varphi(n))</math><br>
 
−
<math>e\cdot d\equiv 1\ (mod\{(p-1)\cdot (q-1)\})</math><br><br>
 
−
Folglich bildet d die modulo Inverse zu e und kann, wie in Algorithmus 2.4 beschrieben, bestimmt werden.<br>
 
 
<br>
 
<br>
  
Zeile 55: Zeile 41:
 
(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>
−
(3) Alice wählt eine Zahl <math>e\ so\ das\ gilt\ 1 <e < < \varphi(n)</math>, mit <math>ggT(e, \varphi(n)) =1</math><br>
+
(3) Alice wählt eine Zahl <math>e, so\ dass\ gilt\ 1 <e < < \varphi(n)</math>, mit <math>ggT(e, \varphi(n)) =1</math> [Begründung folgt später beim Beweis des RSA-Kryptosystems]<br>
−
(4) Alice berechnet <math>d = e^{-1}\ mod\ \varphi(n)</math><br>
+
(4) Alice berechnet <math>d = e^{-1}\ mod\ \varphi(n)</math><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>\quad e\cdot d\equiv 1\ mod\ \{(p-1)\cdot (q-1)\}</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 (e, n), der private Schlüssel (d, n)<br></div></td>
 
     <td><div style = "text-align: left; padding:10px; width: 500px;height: 200px; border: 2px solid #E5CC00;border-color: orange;">'''Algorithmus 3.1 '''<ref name=W14 /><br>
 
     <td><div style = "text-align: left; padding:10px; width: 500px;height: 200px; border: 2px solid #E5CC00;border-color: orange;">'''Algorithmus 3.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>
 
(1) Zur Chiffrierung führt Bob die folgenden Schritte aus:<br>
 
(1) Zur Chiffrierung führt Bob die folgenden Schritte aus:<br>
−
:(a) Bob besorgt sich den authentischen öffentlichen Schlüssel (n, e) von Alice.<br>
+
:(a) Bob besorgt sich den authentischen öffentlichen Schlüssel (e, n) von Alice.<br>
 
:(b) Bob berechnet <math>c = m^e\ mod\ n</math> <br>
 
:(b) Bob berechnet <math>c = m^e\ mod\ n</math> <br>
 
:(c) Bob übermittelt c an Alice.<br>
 
:(c) Bob übermittelt c an Alice.<br>
 
(2) Zur Dechiffrierung führt Alice den folgenden Schritt aus:<br>
 
(2) Zur Dechiffrierung führt Alice den folgenden Schritt aus:<br>
−
: Mit ihrem privaten Schlüssel (n,d) berechnet sie <math>c^d\ mod\ n = m</math><br></div>
+
: Mit ihrem privaten Schlüssel (d, n) berechnet sie <math>c^d\ mod\ n = m</math><br></div>
 
</td>
 
</td>
 
   </tr>
 
   </tr>
Zeile 73: Zeile 59:
 
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'''<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>
+
<div style = "border: 2px solid red; padding:0.75em;">
 +
'''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>.</div><br>
−
<br>
+
<popup name="Beweis">
−
<u>Beweis:</u><ref>[3, S.6]</ref> <math>c\equiv m^e\ (mod\ n) \Rightarrow c^d\ \equiv m^{ed}\ (mod\ n)</math><br>
+
<u>Beweis:</u><ref>[3, 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>
 
<br>
 
<br>
−
<math>m^{ed} = m^{k\cdot (p-1)\cdot (q-1)+1} = (m^{k\cdot (q-1) )(p-1)} \cdot m </math><br>
+
<math>m^{ed} = m^{k\cdot (p-1)\cdot (q-1)+1} = (m^{k\cdot (q-1) )(p-1)}) \cdot m </math><br>
 
<br>
 
<br>
−
und daher nach dem Satz von Fermat  <math>m^{ed}  \equiv 1\cdot m \equiv m\ (mod\ p)</math><br><br>
+
und daher nach dem Satz von Fermat  <math>m^{ed}  \equiv 1\cdot m \equiv m\ mod\ p</math><br><br>
−
Ist m nicht zu p teilerfremd, so folgt <math>m^{ed}  \equiv 0 \equiv m\ (mod\ p)</math>. Analog ergibt sich <math>m^{ed} \equiv m\ (mod\ q)</math>.<br>
+
Ist m nicht zu p teilerfremd, so folgt <math>m^{ed}  \equiv 0 \equiv m\ mod\ p</math>. Analog ergibt sich <math>m^{ed} \equiv m\ mod\ q</math>.<br>
 
Insgesamt folgt, dass sowohl p als auch q und damit auch ihr Produkt <math>p\cdot q= n</math> Teiler von  
 
Insgesamt folgt, dass sowohl p als auch q und damit auch ihr Produkt <math>p\cdot q= n</math> Teiler von  
 
<math>m^{ed}-m\ </math> sind. Also gilt:<br>
 
<math>m^{ed}-m\ </math> sind. Also gilt:<br>
−
<br> <math>m^{ed} -m = k\cdot p\cdot q =k\cdot n\ oder\ (m^{ed}  -m) \equiv 0\ (mod\ \{p\cdot q\})</math><br>
+
<br> <math>m^{ed} -m = k\cdot p\cdot q =k\cdot n\ oder\ (m^{ed}  -m) \equiv 0\ mod\ \{p\cdot q\}</math><br>
 
<br>
 
<br>
−
Damit gilt: <math>(m^{ed} -m) \equiv (m-m) \equiv 0\  (mod\ \{p\cdot q\})</math><br>
+
Damit gilt: <math>(m^{ed} -m) \equiv (m-m) \equiv 0\  mod\ \{p\cdot q\}</math><br>
 
<br>
 
<br>
−
Nach den kennen gelernten Modul-Rechenregeln folgt also:<br>
+
Daraus folgt:
 
<br>
 
<br>
−
<math>m^{ed} \equiv m\ (mod\ \{p\cdot q\})\ oder\  m^{ed} \equiv m\ (mod\ n)\ oder\ m^{ed}\ (mod\ n) = m</math>  □<br>
+
<math>m^{ed} \equiv m\ mod\ \{p\cdot q\}\ oder\  m^{ed} \equiv m\ mod\ n\ oder\ m^{ed}\ mod\ n = m</math>  □<br>
 +
<br>
 +
</popup>
 
<br>
 
<br>
 
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.<br>
 
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.<br>
Zeile 113: Zeile 102:
 
für <math>\varphi(n)= (p-1)\cdot (q-1)= (5-1)\cdot (17-1)=4\cdot 16 =64</math><br>
 
für <math>\varphi(n)= (p-1)\cdot (q-1)= (5-1)\cdot (17-1)=4\cdot 16 =64</math><br>
 
<br>
 
<br>
−
für e mit 0 < e << 120 wählt er e = 5, so dass gilt ggT(5,64) = 1<br>
+
für e mit 0 < e << 64 wählt er e = 5, so dass gilt ggT(5,64) = 1<br>
 
<br>
 
<br>
 
(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.<br>
 
(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.<br>
 
<br>
 
<br>
−
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.<br>
+
Anschließend bestimmt Bob mittels des [[Benutzer:Deininger_Matthias/Facharbeit/Mathematische_Grundlagen_2| Algorithmus 2.1]] die modulare Inverse d zu e mod n, die zusammen mit dem Modulus n seinen geheimen privaten Schlüssel ergibt.<br>
−
<math>5\cdot d\ (mod\ 64) = 1</math><br>
+
<math>5\cdot d\ mod\ 64 = 1</math><br>
 
<br>
 
<br>
 
Berechnung des größten gemeinsamen Teilers mittels des Euklidischen Algorithmus, welcher zur Bestimmung der Vielfachsummendarstellung benötigt wird.<br>
 
Berechnung des größten gemeinsamen Teilers mittels des Euklidischen Algorithmus, welcher zur Bestimmung der Vielfachsummendarstellung benötigt wird.<br>
Zeile 125: Zeile 114:
 
<math>4\ = 1\cdot 4+0</math><br>
 
<math>4\ = 1\cdot 4+0</math><br>
 
<br>
 
<br>
−
Hieraus bestimmen wir die Vielfachsummendarstellung:<br>
+
Hieraus bestimmt Bob die Vielfachsummendarstellung:<br>
 
<math>1 = 5-1\cdot 4=</math><br>
 
<math>1 = 5-1\cdot 4=</math><br>
 
&nbsp;&nbsp;&nbsp;&nbsp;<math>\quad = 5- 1\cdot (64-5\cdot 12)= 13\cdot 5-1\cdot 64</math><br>
 
&nbsp;&nbsp;&nbsp;&nbsp;<math>\quad = 5- 1\cdot (64-5\cdot 12)= 13\cdot 5-1\cdot 64</math><br>
Zeile 134: Zeile 123:
 
<br>
 
<br>
 
Nun kann Alice die Nachricht m = 20 an Bob verschlüsseln<br>
 
Nun kann Alice die Nachricht m = 20 an Bob verschlüsseln<br>
−
<math>c= m^e\ (mod\ n)</math><br>
+
<math>c= m^e\ mod\ n</math><br>
−
<math>20^5\ (mod\ 85) = 3200000\ (mod\ 85) = 5 = c</math><br>
+
<math>20^5\ mod\ 85 = 3200000\ mod\ 85 = 5 = c</math><br>
 
Anschließend übermittelt Alice die Chiffre c = 5 an Bob.<br>
 
Anschließend übermittelt Alice die Chiffre c = 5 an Bob.<br>
 
<br>
 
<br>
Zeile 141: Zeile 130:
 
<br>
 
<br>
 
Bob entschlüsselt die Nachricht mit seinem privaten Schlüssel, wie folgt:<br>
 
Bob entschlüsselt die Nachricht mit seinem privaten Schlüssel, wie folgt:<br>
−
<math>m= c^d\ (mod\ n)</math><br>
+
<math>m= c^d\ mod\ n</math><br>
−
<math>5^{13}\ (mod\ 85) = 1220703125\ (mod\ 85) = 20 = m </math><br>
+
<math>5^{13}\ mod\ 85 = 1220703125\ mod\ 85 = 20 = m </math><br>
 
<br>
 
<br>
−
Bevor du, gemeinsam mit Alice und Bob, zur praktischen Übung an einem Computerprogramm übergehen kannst, solltest du wissen, was sich hinter ASCII verbirgt.<br>
+
Bevor du gemeinsam mit Alice und Bob zur praktischen Übung an einem Computerprogramm ü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 [http://de.wikipedia.org/wiki/American_Standard_Code_for_Information_Interchange#ASCII-Tabelle ASCII]- Standard (American Standard Code for Information Interchange) von der American Standards Association entwickelt. Mit [http://de.wikipedia.org/wiki/American_Standard_Code_for_Information_Interchange#ASCII-Tabelle ASCII] ist es möglich jede Ziffer und jeden Buchstaben als Zahl zu repräsentieren, dieser [http://de.wikipedia.org/wiki/American_Standard_Code_for_Information_Interchange#ASCII-Tabelle ASCII-Code] kann anschließend verschlüsselt werden. Nach dem Dechiffrieren kann der v, wieder in die entsprechenden Buchstaben und Ziffern umgewandelt werden, so dass man den Klartext zurück erhält.<ref>vgl. [4, S. 394 f.]</ref><br>
+
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 [http://de.wikipedia.org/wiki/American_Standard_Code_for_Information_Interchange#ASCII-Tabelle ASCII]- Standard (American Standard Code for Information Interchange) von der ''American Standards Association'' entwickelt. Mit [http://de.wikipedia.org/wiki/American_Standard_Code_for_Information_Interchange#ASCII-Tabelle ASCII] ist es möglich, jede Ziffer und jeden Buchstaben als Zahl zu repräsentieren. Dieser [http://de.wikipedia.org/wiki/American_Standard_Code_for_Information_Interchange#ASCII-Tabelle ASCII-Code] kann anschließend verschlüsselt werden. Nach dem Dechiffrieren kann der [http://de.wikipedia.org/wiki/American_Standard_Code_for_Information_Interchange#ASCII-Tabelle ASCII-Code], wieder in die entsprechenden Buchstaben und Ziffern umgewandelt werden, so dass man den Klartext zurückerhält.<ref>vgl. [4, 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;  ">
−
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.
+
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.
 
</popup>
 
</popup>
 
<br><br>
 
<br><br>
 
[[Bild:Anwendung2.gif|left|Anwendung des RSA-Algorithmus]]
 
[[Bild:Anwendung2.gif|left|Anwendung des RSA-Algorithmus]]
−
[http://garkbit.wor.net/rsa/ '''Hier kannst du das neu erworbene Wissen praktisch ausprobieren. Viel Spaß!''']
+
[http://garkbit.wor.net/rsa/ '''Hier kannst du das neu erworbene Wissen praktisch ausprobieren. Viel Spaß!''']<br>
 +
[[Bild:Homepage.PNG|400px]]
 
<br>
 
<br>
 
<br>
 
<br>

Aktuelle Version vom 23. Dezember 2010, 02:53 Uhr

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.

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 [Begründung folgt später beim Beweis des RSA-Kryptosystems]
(4) Alice berechnet d = e^{-1}\ mod\ \varphi(n)
                            \quad e\cdot d\equiv 1\ mod\ \{(p-1)\cdot (q-1)\}

(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 << 64 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

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