PMG inf3/Das RSA Verfahren

Wiki-Quelltext dieser Seite.

<language>Javascript</language>
=== Der Algorithmus ===

<ol>
<li>
Lege zwei (große) Primzahlen $p$ und $q$ fest mit $p \neq q$.<br />
Bilde das Produkt $N = p \cdot q$.<br />
Suche eine weitere Zahl $e$, für die gilt:
* $e$ ist Primzahl und größer als $p$ und $q$ <u>oder</u>
* $e$ ist teilerfremd zu $(p-1) \cdot (q-1)$.
Die Zahlen $e$ und $N$ bilden den ''öffentlichen Schlüssel''.
</li>
<li>
Ermittle den ''privaten Schlüssel'' $d$ mit:
* $d \le (p-1) \cdot (q-1)$ <u>und</u>
* $(d \cdot e) \bmod [(p-1) \cdot (q-1)] = 1$
</li>
<li>
Ein Klartext-Zeichen mit dem Code $m$ wird mit
<blockquote>$m^e \bmod N = c$</blockquote>
zu $c$ ''verschlüsselt''.
</li>
<li>
Der verschlüsselte Code $c$ wird mit
<blockquote>$c^d \bmod N = m$</blockquote>
zum Code $m$ des Klartext-Zeichens ''entschlüsselt''.
</li>
</ol>

[[Datei:Rivest_Shamir_Adleman.jpg|miniatur|Ron Rivest, Adi Shamir, Leonard Adleman, 2003]]

Das RSA-Verfahren wurde 1977 von '''Ronald L. Rivest''', '''Adi Shamir''' und '''Leonard Adleman''' am MIT in Boston entwickelt und galt damals als das erste ''asymmetrische'' Verschlüsselungsverfahren.<br />
Es nutzt die Tatsache, dass es praktisch unmöglich ist, eine Primfaktorenzerlegung sehr großer Zahlen (ca. 200 Stellen und mehr) in einem vertretbaren (Zeit-)Aufwand vorzunehmen.


Bei diesem Verfahren gibt es öffentliche und geheime Schlüssel.

Die Sicherheit dieses Verfahrens beruht darauf, dass die Mathematik bisher noch '''keine''' Formel gefunden hat, mit der Primzahlen einfach und schnell berechnet werden können. 
Nach wie vor stehen hier nur Probiermethoden zur Verfügung. 
'''Aufgrund der großen Anzahl der Zahlenwerte führt dieses Probieren bei langen Schlüsselwerten nicht mehr in vernünftiger Zeit zum Ergebnis.'''

In diesem Zusammenhang wird von sogenannten '''<font color="darkred">Einwegfunktionen</font>''' gesprochen, die in einer Richtung einfach anzuwenden, in anderer Richtung (Umkehrung) gar nicht oder extrem schwierig funktionieren.
<br><br>

<ul><font color="darkred">Primzahlen</font> 41 und 211: '''Produkt''' <u>einfach</u> zu bestimmen:	8651</ul>

<ul>Aus dem Produkt 8651 sind die Primzahlen durch '''Faktorisieren''' <u>schwer</u> zu ermitteln! Dies wird umso schwieriger, je größer die zu faktorisierende Zahl ist!
<br><br>

=== Das Grundprinzip ===



<li>man wähle <u>zwei möglichst große Primzahlen</u> $p$ und $q$
<li>Verschlüsseln mit '''öffentlichem''' Schlüssel $(e, N)$, wobei $N = p * q$ und $e$ eine beliebige Zahl ist aber <u>teilerfremd</u> zu $(p - 1)*(q - 1)$</li>
<li>Entschlüsseln mit '''privatem''' Schlüssel $d$, den man aus $(d*e)mod((p - 1)*(q - 1)) = 1$ erhält</li>
<br>
'''<font color="green">Es gelten also die Formeln:

<ul>für das Verschlüsseln der Nachricht M zum chiffrierten Text C: $C = M^e(mod N)$ </ul>
<ul>sowie für das Dechiffrieren von C in die Ausgangsnachricht M: $M = C^d(mod N)$ </ul></font>'''
<br><br>
<font color="red">Ein Beispiel:</font>

Bob will an Alice eine Nachricht schicken.
Alice hat einen öffentlichen Schlüssel wie folgt gewählt:
Die Primzahlen seien $p$=17 und $q$=11.
Damit ist $N$=187, für $e$ wird 7 gewählt. Dieser Schlüssel wird ''veröffentlicht''.
<br>
Es soll die Nachricht ''X'' gesendet werden. Dazu müssen die Buchstaben in ASCII-Code umgewandelt werden.<br>
<br>Betrachten wir zunächst das ''X'', so wird diese in ASCII durch $1011000$ dargestellt. Dies entspricht der Dezimalzahl 88, damit sei die (Teil-)Nachricht $M=88$.
<br>
''<font size="1">Ascii-Listen finden sich z.B. unter [http://www.torsten-horn.de/techdocs/ascii.htm] oder [http://www.asciitable.com/] </font>''
<br>
<br>

Für die Verschlüsselung ergibt sich nun $C = 88^7(mod 187)$
Dies ist 11 (nachprüfen!), damit schickt Bob die geheime Nachricht $C=11$ an Alice.
<br><br>

 Windows - wissenschaftlicher Rechner
 oder
 über CAS: dann Eingabe ''mod(88^7,187)''

Nur wer die passenden Primzahlen kennt, mit denen der öffentliche Schlüssel erzeugt wurde, kann die Botschaft entschlüsseln. Das ist allein Alice. <br>Ihr privater Schlüssel folgt aus<br> 
$(d*e) mod ((p - 1)*(q - 1)) = 1$<br>
$(d*7) mod (16*10) = 1$<br>
$(d*7) mod (160))= 1$<br>
$d = 23$, weil $23*7 = 161$(!?)<br><br>
'' mod (160) heißt: Der <u>Rest</u> bei Divison mit 160 soll 1 sein, also 1, 161, 321, 481, ...
Durch "Probieren" erhält man also 161:7=23; 1281 funktioniert auch wieder mit d=183)''

<br><br>
Nun braucht nur noch die Nachricht entschlüsselt werden:
$M = C^d(mod N)$<br>
$M = 11^{23}(mod 187)$<br>
$M = 88 =$  ''X''.



'''<font color="darkgreen">Aufgabe:</font>'''<br>

 Verschlüsseln Sie die Nachricht ''OSTERN'' und geben Sie Ihre Lösung in der Box in ''" "'' ein.
 Betätigen Sie den ''speichern & ausführen'' Schaltfläche!
 Also: <u>angemeldet sein</u>!

<run id="67ecf188d32fd">

</run>

=== Zusammenfassung ===

<ul>
<li>
Mit der Idee der asymmetrischen Verschlüsselung entfällt beim RSA-Verfahren der unsichere Schlüsselaustausch.  
</li>
<li>
Die Verschlüsselung ''einzelner'' Zeichen entspricht einer monoalphabetischen Verschlüsselung und wäre durch Häufigkeitsanalysen sehr schnell zu "knacken". In der Praxis wird man deshalb die Codes mehrere Zeichen vor der RSA-Verschlüsselung zusammenfassen.<br />
'''Beispiel:'''
<pre>
"Informatik" --> unverschlüsselte Codeliste: (9 40 32 41 44 39 27 46 35 37)
             --> modifizierte Codeliste    : (940 3241 4439 2746 3537)
</pre>
</li> 
<li>
Der RSA-Algorithmus gilt als sehr sicher, wenn große Primzahlen verwendet werden.
Es gibt aber nach wie vor intensive Bemühungen, Produkte großer Primzahlen effizient zu faktorisieren.
</li>
<li>
Das RSA-Verfahren wird heute in der Regel mit ''symmetrischen'' Verschlüsselungsverfahren ''kombiniert''. Dabei wird ein Schlüssel für eine symmetrische Verschlüsselung generiert, der dann per RSA-Algorithmus verschlüsselt und zusammen mit der Nachricht übertragen wird.
</li>
</ul>