Der RSA-Alogrithmus (Ronald Rivest, Adi Sharmiv, Len Adelmans, 1976/77) ist ein Verschlüsselungs-Alog und zwar ein sogenannter "Public-Key-Algo". 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 öffnetliche 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 p, q Primzahlen (P), q nicht gleich 0, n def durch pq, m def durch (p-1)(q-1), e aus 1,.., m-1 mit ggT(e,m)=1 und d aus 1,.., m-1 sei Representant von Restklasse d def durch Restklasse e-1 aus Pm.
(e, n) ist der V-Key, (d, n) der E-Key.
Sei nun a aus 1,.., n-1 die zu übermittelnde Nachricht.
Dann heist der Representant c Chiffre zu a. c ist aus 1,.., n-1 von Restklasse c def durch (Restklasse a)e element von Zn. (Verschlüsseln)
und es gilt: a ist kongurent zu cd bzgl modulo n (Entschlüsseln)
Beispiel
Key-Paar erzeuigen:
p sei def durch 7, q def durch 11
damit ist n=77, m=60
Wir wählen zB e=7
Nun muss das d bestimmt werden mit Hilfe des euklidischen Algo:
a0=60
a1=7
60=8*7+4 <=> 4 = 60- 8*7 = a2
7=1*4+3 <=> 3 = 7- 1*4 = a3
4=1*3+1 <=> 1 = 4- 1*3 = a4
1=4- 1*3 = 4- 1*(7-1*4) =
2*4 - 1*7 = 2(60-8*7) - 1*7 =
2*60 - 17*7
-17 ist kongurent zu 43 bzgl. modulo 60
=> d=43
Damit haben wir die Keys:
V-Key (Public) (e, n) = (7, 77)
E-Key (Secret) (d, n) = (43, 77)
Nun will ein Versender die Nachricht a=42 mit dem V-Key (7, 77) verschlüsseln:
c \equiv 427 \pmod{77}
424 \equiv 1764 \equiv -7 \pmod{77}
423 \equiv 42* (-7) \equiv 14 \pmod{77}
Aus 424 \equiv 49 \pmod{77}
und 423 \equiv 14 \pmod{77}
folgt nun => 427 \equiv 14*49 \equiv 70 \pmod{77}
Die Chiffre c=70 geht nun auf die Reise
Wir haben nun die Chiffre c=70 erhalten und wollen si eentschlüsseln mit Hilfe des E-Key(Secret) (d, n) = (43, 77).
a \equiv 7043 \pmod{77}
7043 = 703*2*7+1
703 \equiv 42 \pmod{77} (Bemerkung: das hier wieder 42 steht ist Zufall in diesem Beispiel und hat nix mit der Nachricht a=42 zu tuen.)
706 \equiv 422 \equiv -7 \pmod{77}
7042 \equiv (-7)7 \equiv -28 \pmod{77}
7045 \equiv (-28)*70 \equiv 42 \pmod{77}
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=43.
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...