Der erste Algorithmus zur Chiffrierung mit öffentlichem Schlüssel (asymmetrische Chiffriue) wurde 1977 entwickelt, von R.Merckle und M.Hellman es war schnell überholt, durch die Arbeiten von Shamir, Zippel und Herlestman, allesamt bekannte Kryptoanalysten.
1978 erschien der Algorithmus mit öffentlichem Schlüssel von Rivest, Shamir, und Adelman (daher der Name RSA) Dieser Algorithmus wurde noch 2002 zum Schützen der Nuclearcodes der Amerikanischen und Russischen Armeen verwendet.
Das Funktionsprinzip des Kryptosystems RSA basiert auf der Schwierigkeit, große Ganzzahlen zu faktorisieren.
Sind p und q zwei Primzahlen, und d eine ganze Zahl, sodass gilt d ist relativ prim zu(p-1)*(q-1)). Das Dreier-Paar (p,q,d) bildet so den Privatschlüssel.
Der öffentliche Schlüssel ist dann das Paar (n,e), das durch folgende Transformationen mit Hilfe des privaten Schlüssels berechnet wird :
n = p * q e = 1/d mod((p-1)(q-1))
Es sei M, die zu versendende Nachricht. Die Nachricht M muss relativ Prim zu dem Schlüssel n sein. Die Dechiffrierung beruht auf dem Euler-Theorem, das besagt, dass, wenn M und n relativ prim sind, also :
Mphi(n) = 1 mod(n)Phi(n) ist der Euler-Indikator, und entspricht in diesem Fall (p-1)*(q-1).
Daher ist es nötig, dass M kein Vielfaches von p; q , oder n ist. Eine Lösung besteht darin, die Nachricht M in Stücke zu zerschneiden, nämlich Mi , so dass die Ziffernanzahl jedes Mi immer geringer ist, als die von p und q. Daher wird angenommen dass p und q groß sind, was zutrifft, da das ganze Prinzip von RSA in der Schwierigkeit liegt, in annehmbarer Zeit p und q herauszufinden, wenn man n kennt, dadurch ergibt sich, dass p und q groß sein müssen.
Angenommen ein User Bob) möchte eine Nachricht M an eine Person senden (nennen wir sie Alice), er muss sich lediglich ihren öffentlichen Schlüssel (n,e) beschaffen, und dann die chiffrierte Nachricht c berechnen :
c = Me mod(n)
Bob sendet dann die chiffrierte Nachricht c an Alice, die sie mit ihrem privaten Schlüssel (p,q,d) entschlüsseln kann :
M = Me*d mod(n) = cd mod(n)