Das RSA-Verfahren

2a. Kryptographische Basistechniken

Das RSA-Verfahren

[RSAlogo] ehemaliges Firmenlogo der RSA Data Security, das die Idee der beiden verschiedenen, aber zueinander passenden Schlüssel symbolisiert.

Die Idee des RSA-Verfahrens

Ronald Rivest, Adi Shamir, Leonard Adleman [Bilder] 1978:

A Method for Obtaining Digital Signatures and Public-Key Cryptosystems.

Prinzip: Mathematische Operation

(modulares Potenzieren c = m^e mod n).

Geschwindigkeit (für 2048-Bit-Schlüssel):

Software-Implementationen mindestens 500 ms pro modulare Potenz;
RSA-Chips ca. 10 Kbit/sec (Standard, z. B. in Chipkarten), bis 100 Kbit/sec mit Spezialchips.

RSA-Schlüsselerzeugung

p, q	große Primzahlen - zufällig gewählt, geheim gehalten, übliche (heute kaum noch notwendige) Nebenbedingungen: Die Bitlängen von p und q unterscheiden sich höchstens um 2. Auch die Differenz p-q hat ungefähr diese Bitlänge. p-1 und q-1 enthalten jeweils einen großen Primfaktor. Sinn: n = pq soll nicht leicht faktorisierbar sein.
n = pq	Dann ist (Z/nZ)^×, die multiplikative Gruppe des Restklassenrings Z/nZ, eine Gruppe von der Ordnung f(n) = (p-1)(q-1), also gilt m^x º m^{x mod f(n)} (mod n) für alle ganzen Zahlen m.
e	teilerfremd zu f(n); oft wird die Primzahl e = 2¹⁶+1 genommen - dann ist die Verschlüsselung relativ schnell.
d	mit de º 1 (mod f(n)); mit dem Euklidischen Algorithmus effizient bestimmbar, wenn f(n), also auch p und q bekannt sind.

Anmerkung: Etwas effizienter ist die Schlüsselbestimmung, wenn man statt der Euler-Funktion f(n) (= Gruppenordnung) die Carmichael-Funktion l(n) (= Gruppenexponent) verwendet. Siehe Kryptologie-Vorlesung.

RSA-Ver- und -Entschlüsselung

Parameter

n	Modul
e	öffentlicher Exponent
d	privater Exponent
mit	m^ed º m (mod n) für alle m Î [0...n-1].

Verschlüsselung

Klartext in Bitblöcke m₁, ..., m_r der Länge < ²log(n) einteilen;
jeden Block m_i als Zahl Î [0...n-1] deuten (Codierungsschritt);
c_i = m_i^e (mod n) bilden.

(Dies entspricht der Betriebsart ECB. Natürlich wählt man in der Praxis besser CBC.)

Entschlüsselung

m_i = c_i^d (mod n).

Genauere Beschreibung des Verfahrens und der nötigen Algorithmen im Kapitel Das RSA-Verfahren und seine algorithmischen Grundlagen der Kryptologie-Vorlesung.

Ver- und Entschlüsselung sind effizient durchführbar mit dem binären Potenzalgorithmus.

Die Sicherheit des RSA

Vorlesung Datenschutz und Datensicherheit
Autor: Klaus Pommerening, 31. März 1999; letzte Änderung: 8. Juni 2004.
E-Mail an Pommerening »AT« imbei.uni-mainz.de.