Kryptologische Verfahren

RSA

Der RSA-Algorithmus basiert auf folgenden vier Schritten:

• Wähle zwei große Primzahlen p und q, die geheim bleiben.

• Berechne das Produkt n = p*q. n wird als Modulus bezeichnet.

• Um einen öffentlichen Schlüssel zu erzeugen, wähle eine Zahl e kleiner n, die teilerfremd zur Eulerschen Funktion E(n) = (p-1)*(q-1) ist. Das bedeutet, dass e und E(n) keinen gemeinsamen Teiler außer 1 besitzen. [e,n] ist der öffentliche Schlüssel.

• Um den privaten Schlüssel zu erzeugen, bestimme eine Zahl d = e^-1 mod E(n). Dann gilt: e*d = 1 mod E(n). [d,n] ist der private Schlüssel.

Bei der Verschlüsselung kommt der RSA-Algorithmus folgendermaßen zum Einsatz:

• Alice verschlüsselt ihren Klartext m gemäß c = m^e mod n und sendet ihn an Bob. In diesem Fall ist [e,n] der öffentliche Schlüssel von Bob.

• Bob entschlüsselt den Geheimtext c mit seinem privaten Schlüssel [d,n] gemäß m = c^d mod n und erhält auf Grund des Zusammenhangs von d und e den Klartext m.

Wie man sieht, führt der Empfänger bei der Entschlüsselung die gleiche Operation durch wie der Sender bei der Verschlüsselung. In ähnlicher Weise lässt sich der RSA-Algorithmus zur Erzeugung und Überprüfung von Signaturen einsetzen:

• Alice sendet eine signierte Nachricht, indem sie s = m^d mod n erzeugt und überträgt. [d,n] ist in diesem Fall der private Schlüssel von Alice.

• Bob entschlüsselt die Signatur gemäß m = s^e mod n und erhält auf Grund des Zusammenhangs von d und e den Klartext m. [e,n] ist in diesem Fall der öffentliche Schlüssel von Alice. So kann jeder überprüfen, dass nur Alice die Signatur erzeugt hat.