RSA ist eine asymmetrische Verschlüsselungsmethode, die auf der mathematischen Schwierigkeit beruht, große Primfaktoren von sehr großen Zahlen zu berechnen. Sie verwendet ein Schlüsselkonzept, bei dem zwei verschiedene Schlüssel für den Verschlüsselungs- und den Entschlüsselungsvorgang verwendet werden. Einer der Schlüssel wird als öffentlicher Schlüssel bezeichnet und kann frei verteilt werden, während der andere als privater Schlüssel bezeichnet wird und geheim gehalten werden muss.

Es gibt auch Varianten von RSA, wie beispielsweise die Elgamal-Verschlüsselung, die auf ähnlichen Prinzipien beruhen, aber unterschiedliche Berechnungen und Schlüsselgenerierungsalgorithmen verwenden.

Das RSA-Verfahren basiert auf der Tatsache, dass es sehr schwierig ist, das Produkt zweier großer Primzahlen in ihre einzelnen Primfaktoren zu zerlegen, wenn die Primfaktoren nicht bekannt sind. Der Algorithmus besteht aus den folgenden Schritten:

• Schlüsselerzeugung: Zuerst werden zwei große Primzahlen p und q zufällig gewählt. Das Produkt n = p * q wird berechnet und als Teil des öffentlichen Schlüssels verwendet. Die Eulersche Phi-Funktion (φ(n)) von n wird berechnet, die angibt, wie viele Zahlen kleiner als n und relativ prim zu n sind. Dann wird eine Zahl e gewählt, die relativ prim (wenn ihr größter gemeinsamer Teiler gleich 1 ist) zu φ(n) ist und als öffentlicher Exponent dient. Der öffentliche Schlüssel besteht aus den Werten (n, e). Schließlich wird der private Exponent d berechnet, der als geheimer Schlüssel verwendet wird. Siehe Diffie Hellman Key Exchange.

• Verschlüsselung: Um eine Nachricht m zu verschlüsseln, wird der öffentliche Schlüssel (n, e) verwendet. Die Nachricht wird in eine Zahl umgewandelt und mit der Formel c = m^e mod n verschlüsselt, wobei c die verschlüsselte Nachricht ist.

• Entschlüsselung: Um die verschlüsselte Nachricht c zu entschlüsseln, wird der private Schlüssel d verwendet. Die verschlüsselte Nachricht wird mit der Formel m = c^d mod n entschlüsselt, wobei m die ursprüngliche Nachricht ist.

Die Sicherheit von RSA beruht auf der Annahme, dass es sehr zeitaufwändig ist, die Primfaktoren von n zu berechnen, insbesondere wenn sie sehr groß sind. Mit aktuellen Technologien wäre es praktisch unmöglich, RSA-Verschlüsselungen mit ausreichend großen Schlüsseln zu brechen.