RSA

Eine Erläuterung der verwendeten Symbole findet sich hier: MatheSymbole

Der RSA-Algorithmus (Ronald Rivest, Adi Sharmiv, Len Adelmans, 1976/77) ist ein Verschlüsselungs-Algorithmus und zwar ein sogenannter "Public-Key-Algorithmus". Zum ver- und entschlüsseln werden verschiedene Keys benutzt. Es ist nicht möglich, mit "vertretbarem Aufwand" den einen aus dem anderen Schlüssel zu berechnen. Beide Schlüssel sind natürlich mathematisch verwandt...

Der öffentliche Public-Key (V-Schlüssel) wird öffentlich zugänglich gemacht, der Secret-Key (E-Schlüssel) ist dagegen geheim.

SSL und PGP arbeiten mit dem RSA-Algo.

Die zugrundeliegende Idee ist, das es äusserst schwierig ist, das Produkt zweier großen Primzahlen (z.B. 100 Stellen) in die Primfaktoren zu zerlegen.

Satz 1 (RSA-Algo)

Es seien <math>p</math>, <math>q</math> Primzahlen (<math>\Bbb{P}</math>), <math>q \ne 0</math>, <math>n := p*q</math>, <math>m := (p-1)*(q-1)</math>, <math>e \in \{1, .., m-1\}</math> mit ggT(<math>e</math>, <math>m</math>) = 1 und
<math>d \in \{1, .., m-1\}</math> sei Repräsentant von <math>\overline{d} := \overline{e^{-1}} \in \Bbb{P}_m</math>.

Das Tupel (<math>e</math>, <math>n</math>) ist der V-Key, (<math>d</math>, <math>n</math>) der E-Key.

Sei nun <math>a \in \{1, .., n-1\}</math> die zu übermittelnde Nachricht.

Dann heist der Repräsentant <math>c \in \{1,.., n-1\}</math> von <math> \overline{c} := \overline{a}^e \in \Bbb{Z}_n</math> Chiffre zu <math>a</math>. (Verschlüsseln)

Und es gilt: <math>a \equiv c^d \pmod{n}</math> (Entschlüsseln)

Beispiel

Das Verfahren soll anhand eines Beispiels verdeutlicht werden. Die hier benutzten Primzahlen (1- bzw. 2-stellig) sind natürlich viel zu klein, um das Verfahren sicher zu machen, da ja die Sicherheit eben daher kommt, das die Primzahlen derart groß sind (z.B. 100-stellig), das eine Faktorisierung der Schlüssel praktisch nicht möglich ist.

Key-Paar erzeugen

Sei p := 7, q := 11

damit ist n = 77, m = 60

Wir wählen z.B. e = 7

Nun muss das d bestimmt werden mit Hilfe des Euklidischen Algorithmus:

a₀=60
a₁=7

60=8*7+4 <=> 4 = 60- 8*7 = a₂
7=1*4+3 <=> 3 = 7- 1*4 = a₃
4=1*3+1 <=> 1 = 4- 1*3 = a₄

1=4- 1*3 = 4- 1*(7-1*4) =
2*4 - 1*7 = 2(60-8*7) - 1*7 =
2*60 - 17*7

<math>-17 \equiv 43 \pmod{60} </math>
=>
d = 43

Damit haben wir die Keys:
V-Key (Public) (e, n) = (7, 77)
E-Key (Secret) (d, n) = (43, 77)

Verschlüsseln

Nun will ein Versender die Nachricht a = 42 mit dem V-Key (7, 77) verschlüsseln:

<math>c \equiv 42^7 \pmod{77}</math>

<math>42^4 \equiv 176^4 \equiv -7 \pmod{77}</math>
<math>42^3 \equiv 42 * (-7) \equiv 14 \pmod{77}</math>

Aus <math>42^4 \equiv 49 \pmod{77}</math>
und <math>42^3 \equiv 14 \pmod{77}</math>
folgt nun => <math>42^7 \equiv 14*49 \equiv 70 \pmod{77}</math>

Die Chiffre c = 70 geht nun auf die Reise

Entschlüsseln

Wir haben nun die Chiffre c=70 erhalten und wollen sie entschlüsseln mit Hilfe des E-Key(Secret) (d, n) = (43, 77).

<math>a \equiv 70^43 \pmod{77}</math>
<math>70^43 = 70^\{3*2*7+1\}</math>
<math>70^3 \equiv 42 \pmod{77}</math> (Bemerkung: das hier wieder 42 steht ist Zufall in diesem Beispiel und hat nix mit der Nachricht a=42 zu tun.)
<math>70^6 \equiv 42^2 \equiv -7 \pmod{77}</math>
<math>70^42 \equiv (-7)^7 \equiv -28 \pmod{77}</math>
<math>70^45 \equiv (-28)*70 \equiv 42 \pmod{77}</math>

Damit haben wir die Nachricht a = 42 erhalten.

Sicherheit

Ein böser Bube, der den Public-Key und die Chiffre abgehört hat, kann die Chiffre nicht zur Nachricht entschlüsseln, denn insbesondere fehlt ihm d.

d kann er aus e nur erhalten, wenn er m kennt. Um aber m aus dem Public-Key zu erhalten, müsste er n faktorisieren und das ist für große n auch mit größter Rechenleistung bisher nicht möglich.

Beispiel

Wie lange brauchen 100 Mio StandartPC's um Schlüssel einer gewissen Länge zu knacken?

Länge	Zeit
429	14,5 sek
512	22 Minuten
700	153 Tage
1024	280.000 Jahre

Achtung: In letzter Zeit wurden dann doch Verfahren entdeckt, die diese Faktorisierung schneller als in diesem Beispiel angenommen durchführen können. Effektiv hat sich aber dadurch bei aussreichend langen Schlüsseln nichts an der Sicherheit des RSA-Verfahrens geändert.

Beweiss vom Satz 1

Will den jemand sehen? Ist sehr lang und kompliziert...

Links

Wikipedia:RSA-Kryptosystem

Quotes

"Die Sicherheit von RSA basiert auf der Schwierigkeit der Faktorenberechnugn bei großen Zahlen. Als erstes werden zwei Primzahlen, P und Q gewählt und deren Produkt N ermittelt. N = P * Q. Anschließend muss die Anzahl der Zahlen zwischen 1 und N -1, die relativ zu N Primzahlen sind (zwei Nummern sind relative Primzahlen, wenn ihr größter gemiensamer Divisor 1 ist). Diese Funktion ist unter dem Namen Eulersche Phi-Funktion (engl. totient function) bekannt und wird typischerweise durch den kleinen griechischen Buschstaben Phi dargestellt." (aus: Forbidden Code, Jon Erickson)