2.4.3 RSA Factoring with known secret key

Factoring of an integer n = p ⋅ q, where p,q are primes is very difficult. If you are dealing with the RSA problem you can simplify that quite much if you know the secret key a.

Relevant numbers for RSA:
n = p ⋅ q
Φ(n) = (p-1) ⋅ (q-1)
a ⋅ b ≡ 1 (mod Φ(n))
n and b are public, while p, q and a are secret.

For the following algorithm we assume that the secret key a is given by another algorithm A:

Choose random w with 1 ≤ w ≤ n-1. If we are lucky, so gcd(w, n) > 1, so we already have a factor of n. If not, we can compute w^r , w^2r , w^4r,..., w^{2t r} ≡ 1 (mod n) for a special t, if w is prime with respect to n. Since a⋅b - 1 = 2^s ⋅ r ≡ 0 (mod Φ(n)) we know that w^{2s r} ≡ 1 (mod n). So we find a value v₀ with v₀² ≡ 1 (mod n) but v₀ ≠ 1 (mod n). If v₀ ≡ -1 (mod n) the algorithm fails. Otherwise v₀ is a non-trivial root of 1 modulo n and we may factorize n.

Example

Let be n = 29329 and b = 1859. One knows that a = 15059. Now choose a random w e.g w = 21.
1. One computes gcd(w, n) = gcd(21, 29329) = 1
2. It is 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 = gcd(v + 1, n) = 139 hence q = 29329 / 139 = 211

Applet RSA factoring

Quellcode:
RSAFacSF.java - Surface
RSAFac.java - Algorithm

2.4.4 Quadratic Sieve