RSA-Kryptosystem
Das RSA-Kryptosystem ist ein asymmetrisches Kryptosystem, d.h. es verwendet verschiedene Schlüssel zum Ver- und Entschlüsseln. Es ist nach seinen Erfindern Ronald L. Rivest, Adi Shamir und Leonard Adleman benannt.Nachdem Whitfield Diffie und Martin Hellman eine Theorie zur Public-Key-Kryptografie veröffentlicht hatten, setzten sich die drei Mathematiker hin und versuchten, die Annahmen von Diffie und Hellmann zu widerlegen. Nachdem sie den Beweis bei verschiedenen Verfahren durchführen konnten, stießen sie schließlich auf eines, wo sie keinerlei Angriffspunkte fanden. Hieraus entstand dann RSA.
Das Verfahren wurde 1977 entwickelt und basiert auf der Idee, dass die Faktorisierung einer großen Zahl, also ihre Zerlegung in (mindestens zwei) Faktoren, eine sehr aufwändige Angelegenheit ist, während das Erzeugen einer Zahl durch Multiplikation zweier Primzahlen trivial ist. Wenn nun eine Nachricht einem Empfänger verschlüsselt zugeleitet werden soll, generiert dieser einen öffentlichen Schlüssel. Der Nachrichtenabsender verwendet diesen öffentlich bekanntgemachten Schlüssel, indem er damit seine Botschaft verschlüsselt. Nur der Empfänger kann diese "dekodieren", da nur er die "Zusammensetzung" des von ihm erzeugten (öffentlichen) Schlüssels kennt.
Funktionen wie die Multiplikation/Faktorisierung, bei denen eine Richtung leicht, die andere schwierig zu berechnen ist, bezeichnet man als Einwegfunktionen (engl one way function). Um allerdings die Entschlüsselung tatsächlich möglich zu machen, muss es sich um Falltürfunktionen (engl. trap door function) handeln, die mit Hilfe einer Zusatzinformation auch rückwärts leicht zu berechnen sind. Solche Einweg- und Falltürfunktionen kann es nur geben, wenn ist.
RSA wird u.a. zur Authentisierung französischer Telefonkarten angewendet.
Das Verfahren ist mit dem Rabin-Verschlüsselungsverfahren verwandt.
Jeder kann A eine verschlüsselte Nachricht senden, aber nur A kann sie entschlüsseln.Schlüsselgenerierung
In der Praxis werden diese Primzahlen durch Raten einer Zahl und darauffolgendes Anwenden eines Primzahltests bestimmt.
Die Zahlen N und e werden veröffentlicht (öffentlicher Schlüssel, public key), d, p und q und damit auch φ(N) bilden den geheimen Schlüssel (secret key)Asymmetrische Vorgehensweise:
A wählt zufällig zwei möglichst gleich lange Primzahlen, berechnet daraus N, φ(N) und zwei Zahlen e und d. N und e veröffentlicht er als öffentlichen Schlüssel, d und N sind Bestandteile seines geheimen Schlüssels, und p, q und φ(N) kann A nach belieben vernichten.