2.4.3 RSA-Faktorisierung bei bekanntem Secret-Key

Die Faktorisierung einer Zahl n = p ⋅ q, wobei p,q prim ist äußerst schwierig. Handelt es sich dabei um das RSA-Problem könnte man bei bekanntem a dieses Problem deutlich vereinfachen.

kurze Benennung der relevanten Zahlen des RSA-Verfahrens:
n = p ⋅ q
Φ(n) = (p-1) ⋅ (q-1)
a ⋅ b ≡ 1 (mod Φ(n))
Öffentlich sind nun n und b, während p, q und a geheim sind.

Bei folgendem Algorithmus geht man davon aus, dass der geheime Schlüssel a gegeben sei, oder durch einen anderen Algorithmus vorher ermittelt wurde:

Man wähle ein w mit 1 ≤ w ≤ n-1, beliebig. Hat man Glück und wählt ein w mit ggT(w, n) > 1, so hat man bereits einen Faktor von n. Falls nicht, so kann man falls w bezüglich n prim ist, w solange quadrieren bis w^r , w^2r , w^4r,..., w^{2t r} ≡ 1 (mod n) für ein t ist. Da a⋅b - 1 = 2^s ⋅ r ≡ 0 (mod Φ(n)) wissen wir, dass w^{2s r} ≡ 1 (mod n) ist. Dadurch finden wir einen Wert v₀ mit v₀² ≡ 1 (mod n) aber v₀ ≠ 1 (mod n). Falls v₀ ≡ -1 (mod n) so scheitert der Algorithmus. Sonst ist v₀ eine nicht-triviale Wurzel von 1 modulo n und wir können n Faktorisieren.

Beispiel

Sei n = 29329 und b = 1859. Man wisse, dass a = 15059 ist. Nun wähle man ein w, etwa w = 21.
1. Man berechne ggT(w, n) = ggT(21, 29329) = 1
2. Es ist a⋅b - 1 = 2^s ⋅ r = 8 ⋅ 3499335
3. v = w^r mod n = 21^34499335 mod 29329 = 5698
4. v² = 1 mod n
5. p = ggT(v + 1, n) = 139 und damit q = 29329 / 139 = 211

Applet RSA-Faktorisierung

Quellcode:
RSAFacSF.java - Appletoberfläche
RSAFac.java - Algorithmenklasse

2.4.4 Quadratisches Sieb