RSA-Verfahren

RSA-Verfahren

Studium
c=me mod n,m=cd mod n,e⋅d≡1(modφ(n))c = m^{e} \bmod n, \qquad m = c^{d} \bmod n, \qquad e \cdot d \equiv 1 \pmod{\varphi(n)}

Voraussetzung: n=p⋅q,n = p \cdot q, p≠qp \neq q Primzahlen,, φ(n)=(p−1)(q−1),\varphi(n) = (p-1)(q-1), 1<e<φ(n),1 < e < \varphi(n), ggT⁡(e,φ(n))=1,\operatorname{ggT}(e, \varphi(n)) = 1, 0≤m<n0 \leq m < n

p,qp, q
zwei verschiedene, geheime Primzahlen
nn
RSA-Modul, das Produkt p · q, öffentlich
φ(n)\varphi(n)
Eulersche φ-Funktion von n, hier (p − 1)(q − 1), geheim
ee
öffentlicher Exponent, teilerfremd zu φ(n)
dd
privater Exponent, Inverses von e modulo φ(n)
mm
Klartext als Zahl von 0 bis n − 1
cc
Geheimtext, ebenfalls eine Zahl von 0 bis n − 1

Beim RSA-Verfahren verschlüsselt man mit c = mᵉ mod n und entschlüsselt mit m = cᵈ mod n, wobei e·d ≡ 1 modulo φ(n) gilt.

Erklärung

RSA ist ein asymmetrisches Verschlüsselungsverfahren: Jeder darf mit dem öffentlichen Schlüssel (n,e)(n, e) verschlüsseln, entschlüsseln kann nur, wer den privaten Schlüssel dd kennt.

Schlüsselerzeugung:

  1. Zwei große, verschiedene Primzahlen pp und qq wählen und n=p⋅qn = p \cdot q bilden.
  2. φ(n)=(p−1)(q−1)\varphi(n) = (p-1)(q-1) berechnen.
  3. Einen Exponenten ee mit 1<e<φ(n)1 < e < \varphi(n) und ggT⁡(e,φ(n))=1\operatorname{ggT}(e, \varphi(n)) = 1 wählen (in der Praxis meist e=65537e = 65537).
  4. dd als Inverses von ee modulo φ(n)\varphi(n) mit dem erweiterten euklidischen Algorithmus bestimmen.

Öffentlich sind nn und ee; geheim bleiben dd, pp, qq und φ(n)\varphi(n). Die Potenzen berechnet man mit schnellem modularem Potenzieren.

Warum es funktioniert: Wegen e⋅d=1+k φ(n)e \cdot d = 1 + k\,\varphi(n) für eine ganze Zahl kk gilt

cd≡med=m⋅(mφ(n))k≡m(modn)c^d \equiv m^{ed} = m \cdot \left(m^{\varphi(n)}\right)^{k} \equiv m \pmod n

Für ggT⁡(m,n)=1\operatorname{ggT}(m, n) = 1 folgt das direkt aus dem Satz von Euler. Mit dem chinesischen Restsatz zeigt man, dass es auch für die übrigen m<nm < n gilt, weil nn quadratfrei ist.

Sicherheit: Wer nn in pp und qq zerlegen kann, berechnet φ(n)\varphi(n) und damit dd. Für große nn (heute mindestens 2048 Bit) ist kein effizientes Verfahren dafür bekannt. Das reine „Lehrbuch-RSA“ aus der Formel ist trotzdem unsicher, weil gleiche Klartexte gleiche Geheimtexte ergeben; in der Praxis wird der Klartext vorher zufällig aufgefüllt (Padding).

Signieren funktioniert umgekehrt: Die Signatur ist s=md mod ns = m^d \bmod n, jeder prüft mit se mod n=ms^e \bmod n = m.

Beispiele

Schlüssel: p=3p = 3, q=11q = 11, also n=33n = 33 und φ(33)=2⋅10=20\varphi(33) = 2 \cdot 10 = 20. Gewählt wird e=3e = 3, denn ggT⁡(3,20)=1\operatorname{ggT}(3, 20) = 1. Erweiterter euklidischer Algorithmus:

20=6⋅3+2,3=1⋅2+1⇒1=3−2=7⋅3−2020 = 6 \cdot 3 + 2, \qquad 3 = 1 \cdot 2 + 1 \quad\Rightarrow\quad 1 = 3 - 2 = 7 \cdot 3 - 20

Also d=7d = 7, Probe: 3⋅7=21≡1(mod20)3 \cdot 7 = 21 \equiv 1 \pmod{20}.

Verschlüsseln von m=4m = 4:

c=43 mod 33=64 mod 33=31c = 4^3 \bmod 33 = 64 \bmod 33 = 31

Entschlüsseln: Wegen 31≡−2(mod33)31 \equiv -2 \pmod{33} ist

317≡(−2)7=−128≡4(mod33)31^7 \equiv (-2)^7 = -128 \equiv 4 \pmod{33}

Der Klartext 44 ist zurück. Auch m=11m = 11, das nicht zu 3333 teilerfremd ist, wird korrekt zurückgewonnen.

Signieren von m=5m = 5: s=57 mod 33=14s = 5^7 \bmod 33 = 14. Prüfung: 143 mod 33=514^3 \bmod 33 = 5.

Typische Fehler

  • dd modulo nn statt modulo φ(n)\varphi(n) bestimmen. Die Bedingung lautet e⋅d≡1(modφ(n))e \cdot d \equiv 1 \pmod{\varphi(n)}.
  • φ(n)=n−1\varphi(n) = n - 1 setzen. Das gilt nur für Primzahlen; für n=p⋅qn = p \cdot q ist φ(n)=(p−1)(q−1)\varphi(n) = (p-1)(q-1), im Beispiel 2020, nicht 3232.
  • ee nicht teilerfremd zu φ(n)\varphi(n) wählen. Für e=5e = 5 und φ(n)=20\varphi(n) = 20 gibt es kein Inverses dd.
  • Klartexte m≥nm \geq n verschlüsseln. Sie lassen sich nicht eindeutig zurückgewinnen, weil nur der Rest modulo nn übrig bleibt.

Verwandte Formeln