Wie funktioniert RSA?

RSA (Rivest-Shamir-Adleman) ist ein asymmetrisches Kryptosystem, das zur sicheren Übertragung von Daten verwendet wird. Es basiert auf der mathematischen Schwierigkeit, große Primzahlen zu faktorisieren. Hier sind die grundlegenden Schritte, wie RSA funktioniert:

1 **Schlüsselerzeugung**:
- Wähle zwei große, zufällige Primzahlen \( p \) und \( q \).
- Berechne \( n = p \times q \). Der Wert \( n \) wird als Modulus für die öffentlichen und privaten Schlüssel verwendet.
- Berechne die Eulersche Totient-Funktion \( \phi(n) = (p-1) \times (q-1) \).
- Wähle eine ganze Zahl \( e \) (öffentlich), die teilerfremd zu \( \phi(n) \) ist (häufig wird 65537 gewählt, da es eine kleine, effiziente Zahl ist).
- Berechne den privaten Schlüssel \( d \), der die Bedingung \( d \times e \equiv 1 \mod \phi(n) \) erfüllt. Dies kann durch den erweiterten euklidischen Algorithmus erfolgen.

2. **Öffentlicher und privater Schlüssel**:
- Der öffentliche Schlüssel besteht aus dem Paar \( (e, n) \).
- Der private Schlüssel besteht aus \( (d, n) \).

3. **Verschlüsselung**:
- Um eine Nachricht \( m \) zu verschlüsseln, wird sie in eine Zahl umgewandelt, die kleiner als \( n \) ist.
- Die verschlüsselte Nachricht \( c \) wird berechnet als \( c \equiv m^e \mod n \).

4. **Entschlüsselung**:
- Um die verschlüsselte Nachricht \( c \) zu entschlüsseln, wird die ursprüngliche Nachricht \( m \) wiederhergestellt durch \( m \equiv c^d \mod n \).

Die Sicherheit von RSA beruht auf der Schwierigkeit, \( n \) in seine Faktoren \( p \) und \( q \) zu zerlegen, was bei großen Zahlen sehr rechenintensiv ist.