/ Kryptographie & Hashing

RSA Verschlüsselung

RSA-Chiffretext durch modulare Potenzierung mit dem öffentlichen Exponenten: C = M^e mod N. Klartext M muss kleiner als der Modul N sein.

RSA Verschlüsselung

01 · Eingabe

RSA Verschlüsselung berechnen

RSA-Chiffretext durch modulare Potenzierung mit dem öffentlichen Exponenten: C = M^e mod N. Klartext M muss kleiner als der Modul N sein.

C = M^e mod N

M Klartext

e Öffentlicher Exponent

N RSA-Modul

Worum geht es?

Die RSA-Verschlüsselung transformiert den Klartext M in den Chiffretext C über die modulare Potenzierung C = M^e mod N. Der öffentliche Schlüssel besteht aus dem Paar (e, N), die Operation ist jedem zugänglich.

Die Sicherheit ergibt sich daraus, dass die Umkehrung (Wurzelziehen modulo N) ohne Kenntnis von p, q bzw. φ(N) praktisch nicht durchführbar ist. M muss kleiner als N sein.

Die Formel

Formel RSA-Verschlüsselung

C = M^e mod N

Die Variablen

Symbol	Bedeutung	Einheit	Erklärung
M	Klartext	—	Klartextwert als Zahl (0 ≤ M < N).
e	Öffentlicher Exponent	—	Teil des öffentlichen Schlüssels.
N	RSA-Modul	—	Öffentlicher Modul N = p · q.
C	Chiffretext	—	Verschlüsselter Wert.

Minimal-Beispiel

M = 65, e = 17, N = 3233:

Rechnung RSA-Beispiel

C = 65^17 mod 3233
  = 2790

Praxis-Beispiele

Beispiel 1 — Lehrbuchwerte

M = 88, e = 7, N = 187:

Rechnung Klein

C = 88^7 mod 187
  = 11

Beispiel 2 — Standard-Exponent e = 65537

In der Praxis wird oft e = 65537 (= 2¹⁶ + 1) gewählt, weil die binäre Darstellung nur zwei gesetzte Bits hat und die Potenzierung daher effizient ist:

Rechnung Effizienz

C = M^65537 mod N
65537 binär: 10000000000000001
→ nur 17 Quadrierungen + 1 Multiplikation

Beispiel 3 — Quadrieren-und-Multiplizieren

M^13 mod N mit 13 = 1101₂:

Rechnung Square-and-Multiply

M^13 = M^8 · M^4 · M^1
     = ((M²)²)² · (M²)² · M
Jeder Schritt mod N gerechnet.