Rivest-Shamir-Adleman (RSA)

Dieses Verfahren ist wohl das verbreitetste Public-Key-Verfahren. Es wurde 1977/78 von Ron Rivest, Adi Shamir und Len Adleman entwickelt. RSA wurde 1983 bis ins Jahr 2000 für die USA patentiert. Das Patent wurde nicht verlängert.

Bei diesen Verfahren benutzt man bekannte Probleme aus der Numerik. Die Sicherheit von RSA basiert auf dem Problem, eine große ganze Zahl in ihre Primfaktoren zu zerlegen. Daher darf die Schlüssellänge auch nicht zu klein gewählt werden. Die beiden Schlüssel werden wie folgt erzeugt:

-Es werden zwei verschieden, große Primzahlen p und q zufällig gewählt, wobei die Differenz nicht zu klein sein sollte, und das Produkt der beiden berechnet: n = p * q

-Dann wird ein zufälliger Wert e ermittelt, der kleiner m und teilerfremd zu (p-1) * (q-1) ist. Zu diesem wird das modular Inverse d berechnet, so dass gilt: (e * d) mod ((p-1)*(q-1)) = 1

Als öffentlicher Schlüssel gilt dann: e und n und der private Schlüssel ist: d und n. Die Primzahlen p und q dürfen niemals bekannt werden.

Die Stärke dieses Verfahrens liegt im Schlüssel, bzw. dessen Erzeugung. Die Chiffrierung und Dechiffrierung der Nachrichten ist vergleichsweise einfach und gestaltet sich wie folgt:

-Das RSA-Verfahren verschlüsselt und entschlüsselt nur Zahlen in Zahlen, daher muss der Klartext mit einem öffentlich bekannten Alphabet in eine Zahlenfolge übersetzt werden.

-Zunächst wird die Nachricht in numerische Blöcke zerlegt, die kleiner als n sein müssen.

-C: Geheimtext, M: Klartext, n: große Zahl, e: öffentlicher Schlüssel, d: privater Schlüssel

-Zur Verschlüsselung benutzt man die Funktion:

  C = M e mod n
-Die Entschlüsselung erreicht man mit:

  M = C d mod n
Öffentlich zugänglich ist natürlich das Verfahren zur Ver- und Entschlüsselung, was eine Forderung für alle kryptografisch starken Verfahren ist. Unbedingt öffentlich muss der Schlüssel e und das Primzahlprodukt (n) sein. Der verschlüsselte Text kann nur vom Empfänger entschlüsselt werden, da dieser als einziger den geheimen, privaten Schlüssel hat.

RSA kann nur so lange als sicheres Verfahren gelten, wie es nicht möglich ist eine Zerlegung der Primzahl n in p und q zu erreichen, um dann den geheimen Schlüssel zu berechen. Noch 1993 schätzte man, dass die Zerlegung einer 130-stelligen Zahl in ihre zwei Primzahlen Millionen von Jahren benötigen würden. Tatsächlich gelang bereits ein Jahr später die Auflösung. Shamir selbst entwarf einen Computer, der einen 512-Bit-Schlüssel in 3 Tagen knacken kann.

Ständig wird die Grenze der faktorierbaren Zahlen höher gesetzt, sei es durch verbesserte Berechnungstechniken oder durch bessere Rechner. Eine RSA-codierte Nachricht kann nur für eine begrenzte Zeit sicher sein, nämlich solange, bis diese Rechenleistung die Höhe erreicht, die das n ihrer Verschlüsselung hatte.