RSA Grundformel
RSA-Modul aus zwei großen Primzahlen: N = p · q. Daraus folgt φ(N) = (p − 1)(q − 1), Grundlage für die Wahl von öffentlichem Exponenten e und privatem d mit e · d ≡ 1 (mod φ(N)).
RSA Grundformel berechnen
RSA-Modul aus zwei großen Primzahlen: N = p · q. Daraus folgt φ(N) = (p − 1)(q − 1), Grundlage für die Wahl von öffentlichem Exponenten e und privatem d mit e · d ≡ 1 (mod φ(N)).
- N — RSA-Modul
- p — Primzahl p
- q — Primzahl q
Worum geht es?
Der RSA-Modul N ist das Produkt zweier großer Primzahlen p und q. Aus ihm leitet sich die Eulersche Phi-Funktion φ(N) = (p − 1)(q − 1) ab, die wiederum die Wahl von öffentlichem Exponenten e und privatem Exponenten d steuert (e · d ≡ 1 mod φ(N)).
Die Sicherheit von RSA beruht darauf, dass die Faktorisierung eines großen N praktisch unmöglich ist — heute werden Module von mindestens 2048 Bit Länge eingesetzt.
Die Formel
N = p · q
Umstellungen:
p = N / q
q = N / pDie Variablen
| Symbol | Bedeutung | Einheit | Erklärung |
|---|---|---|---|
| p | Primzahl p | — | Erste Primzahl. |
| q | Primzahl q | — | Zweite Primzahl. |
| N | RSA-Modul | — | Öffentlicher Modul N. |
Minimal-Beispiel
p = 61, q = 53:
N = 61 · 53 = 3233
φ(N) = 60 · 52 = 3120Praxis-Beispiele
Beispiel 1 — RSA-Lehrbuchwerte
p = 17, q = 11:
N = 17 · 11 = 187
φ(N) = 16 · 10 = 160Beispiel 2 — Faktorisierung bei bekanntem q
N = 3233, q = 53:
p = N / q = 3233 / 53 = 61Beispiel 3 — Modullänge bei 2048-Bit-RSA
N ≈ 2^2048 ≈ 3,23 · 10⁶¹⁶
p, q jeweils ca. 1024 Bit lang.