|
|
RSA (asymmetrisches
Verfahren)
Geschichte:
1978 veröffentlichten
Rivest,
Shamir,
Adleman einen Algorithmus genannt RSA.
Das Verfahren: Es ist bekanntermaßen
außerordentlich schwierig, aus einem Produkt n=pq zweier großer
Primzahlen die Primfaktoren p und q zu ermitteln. Das Problem heißt
Faktorisierung von n. Die Schwierigkeit steigt mit wachsender Stellenanzahl
rasant an. Vielleicht können wir daraus einen asymmetrischen Algorithmus
bauen: n ist bekannt, und irgendwie können wir mit Hilfe dieser Zahl
auch etwas verschlüsseln, aber ohne Kenntnis von p und q nicht wieder
entschlüsseln.
Zunächst überlegen wir uns, daß für alle Primzahlen p und q die Eulersche Funktion so aussieht: f(pq) = (p-1)(q-1)
Der Beweis ist einfach: Es gibt insgesamt pq Zahlen 1,..,pq. Von diesen sind nicht teilerfremd zu pq: Die p durch q teilbaren Zahlen sowie die q durch p teilbaren Zahlen, also zusammen p+q. Wir müssen dabei beachten, daß wir pq zweimal berücksichtigt haben, denn es ist ja durch p und q teilbar. Alle anderen Zahlen, die weder durch p noch durch q teilbar sind, müssen zu pq teilerfremd sein (denn p und q sind Primzahlen). Somit folgt: f(pq) = pq - (p+q-1) = (p-1)(q-1)
Also gilt m(p-1)(q-1) = 1 mod pq
oder auch m(p-1)(q-1)+1 = m mod pq
für alle m, die weder durch p noch durch q teilbar sind. Das könnte das gesuchte Verfahren sein: Wir bestimmen zwei natürliche Zahlen d und e mit de = (p-1)(q-1)+1 und d,e > 1.
e und n geben wir bekannt. Jeder kann für jede zu pq teilerfremde Zahl m< pq den Rest berechnen, den me bei Teilung durch pq läßt. Diesen Rest fassen wir als Geheimtext auf. M sehen wir als Klartext an, n=pq und e als öffentlichen Schlüssel (also zwei Zahlen!). Nur wir kennen d, den privaten Schlüssel. Wenn uns jemand den Geheimtext me sendet (genauer: den Rest bei Teilung durch), so berechnen wir den Klartext m gemäß (me)d = med = m(p-1)(q-1)+1 = m mod pq.
Die Berechnung von d aus e
und n läuft über die Faktorisierung von n=pq. Wer n nicht faktorisiert,
kann auch d nicht ermitteln.
Anwendung von RSA
Bisher haben wir nur Variablen gesehen, wie entsteht daraus ein Chiffrierverfahren? Wir legen eine Schlüssellänge
fest. Aktuell gelten 1024 Bit als sicher. Wir erzeugen zwei verschiedene
Primzahlen p, q mit mindestens 1024 /2 = 512 Bit Länge.
Wir legen einen Exponenten
e fest. e muß zu p-1 und q-1 teilerfremd sein. Wenn nicht, dann müssen
wir e bzw. q und p anders wählen.
Nun ermitteln wir mit dem
sogenannten erweiterten Euklidischen Algorithmus ein d mit de = 1 mod (p-1)(q-1).
D ist der private Schlüssel. Das Produkt n=pq geben wir zusammen mit
dem Exponenten e als öffentlichen Schlüssel bekannt.
Damit sind die Schlüssel
erzeugt. Die Chiffrierung sieht so aus:
Wenn der Schlüssel n=qp
genau N Bit lang ist, teilen wir den Text in Blöcke zu N-1 Bit auf
(zur Not müssen wir auffüllen).
Von jedem Block mit dem Wert
m berechnen wir den Rest me bei Teilung durch n. Damit haben
wir schon den Geheimtextblock erzeugt.
Bei der Dechiffrierung gehen
wir umgekehrt vor:
Wir teilen den Geheimtext
in N-Bit Blöcke auf.
Zu jedem Geheimtextblock
mit dem Wert c wird der Rest von cd bei Teilung durch n berechnet.
Es entsteht ein N-1 bit langer Klartextblock, wobei das erste Bit eine
Null sein muß, sonst liegt ein Fehler vor. Dieses erste Bit streichen
wir.
Nachteil des Verfahren
Es leuchtet ein, daß
das Verfahren sehr langsam ist, da Multiplikation und Restberechnung 1000
Bit langer Zahlen Zeit braucht. Ein weiterer Nachteil ist das finden so
großer Primzahlen. (Bsp. Sieb des Erathostenes)
Wie sicher ist RSA? Hier gibt es verschieden Methoden zum Knacken gleiche Primzahlen in verschiedene
Moduln
Angriff mit ausgewähltem
Geheimtext
Angriff bei gemeinsamen Moduln
Angriff gegen kleine Werte von e neue Methoden bei der Faktorisierung großer Zahlen Die ersten 4 Risiken lassen
sich durch geeignete Implementierungen ausschließen. Für die
letzte Methode gilt dies jedoch nicht. Die Kryptanalyse wäre erfolgreich,
wenn man das Modul n faktorisieren könnte. Man vermutet, daß
die Ermittlung des Klartextes aus dem öffentlichen Schlüssel
äquivalent zum Problem der Faktorisierung von n ist.
|
|
|