Suche Home Einstellungen Anmelden Hilfe  

 
Navigation
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.
 

 

Vorwort

Einführung

Geschichte

Grundbegriffe

DES

RSA

Protokolle

Signaturen

Abschlußbetrachtung

Quellen
 
 































































zurück


Benutzer: Gast • Besitzer: mthomas • Zuletzt gešndert am: