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:

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:

Also gilt

oder auch

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

e und n geben wir bekannt. Jeder kann für jede zu pq teilerfremde Zahl m< pq den Rest berechnen, den m^e 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 m^e sendet (genauer: den Rest bei Teilung durch), so berechnen wir den Klartext m gemäß 

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.

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 m^e bei Teilung durch n. Damit haben wir schon den Geheimtextblock erzeugt.

Wir teilen den Geheimtext in N-Bit Blöcke auf.
Zu jedem Geheimtextblock mit dem Wert c wird der Rest von c^d 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.

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

Vorwort

Einführung

Geschichte

Grundbegriffe

DES

RSA

Protokolle

Signaturen

Abschlußbetrachtung

Quellen