Calculate primes p and q from private exponent (d), public exponent (e) and the modulus (n)

How do I calculate the p and q parameters from e (publickey), d (privatekey) and modulus?

I have BigInteger keys at hand I can copy paste into code. One publickey, one privatekey and a modulus.

I need to calculate the RSA parameters p and q from this. But I suspect there is a library for that which I was unable to find with google. Any ideas? Thanks.

This does not have to be brute force, since I'm not after the private key. I just have a legacy system which stores a public, private key pair and a modulus and I need to get them into c# to use with RSACryptoServiceProvider.

So it comes down to calculating (p+q) by

public BigInteger _pPlusq()
    {
        int k = (this.getExponent() * this.getD() / this.getModulus()).IntValue();

        BigInteger phiN = (this.getExponent() * this.getD() - 1) / k;

        return phiN - this.getModulus() - 1;

    }

but this doesn't seem to work. Can you spot the problem?

5 hours later... :)

Ok. How can I select a random number out of Zn* (http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n) in C#?

Let's assume that e is small (that's the common case; the Traditional public exponent is 65537). Let's also suppose that ed = 1 mod phi(n), where phi(n) = (p-1)(q-1) (this is not necessarily the case; the RSA requirements are that ed = 1 mod lcm(p-1,q-1) and phi(n) is only a multiple of lcm(p-1,q-1)).

Now you have ed = k*phi(n)+1 for some integer k. Since d is smaller than phi(n), you know that k < e. So you only have a small number of k to try. Actually, phi(n) is close to n (the difference being on the order of sqrt(n); in other words, when written out in bits, the upper half of phi(n) is identical to that of n) so you can compute k' with: k'=round(ed/n). k' is very close to k (i.e. |k'-k| <= 1) as long as the size of e is no more than half the size of n.

Given k, you easily get phi(n) = (ed-1)/k. It so happens that:

phi(n) = (p-1)(q-1) = pq - (p+q) + 1 = n + 1 - (p+q)

Thus, you get p+q = n + 1 - phi(n). You also have pq. It is time to remember that for all real numbers a and b, a and b are the two solutions of the quadratic equation X²-(a+b)X+ab. So, given p+q and pq, p and q are obtained by solving the quadratic equation:

p = ((p+q) + sqrt((p+q)² - 4*pq))/2

q = ((p+q) - sqrt((p+q)² - 4*pq))/2

In the general case, e and d may have arbitrary sizes (possibly greater than n), because all that RSA needs is that ed = 1 mod (p-1) and ed = 1 mod (q-1). There is a generic (and fast) method which looks a bit like the Miller-Rabin primality test. It is described in the Handbook of Applied Cryptography (chapter 8, section 8.2.2, page 287). That method is conceptually a bit more complex (it involves modular exponentiation) but may be simpler to implement (because there is no square root).

There is a procedure to recover p and q from n, e and d described in NIST Special Publication 800-56B R1 Recommendation for Pair-Wise Key Establishment Schemes Using Integer Factorization Cryptography in Appendix C.

The steps involved are:

1. Let k = de – 1. If k is odd, then go to Step 4.
2. Write k as k = 2^tr, where r is the largest odd integer dividing k, and t ≥ 1. Or in simpler terms, divide k repeatedly by 2 until you reach an odd number.
3. For i = 1 to 100 do:
   1. Generate a random integer g in the range [0, n−1].
   2. Let y = g^r mod n
   3. If y = 1 or y = n – 1, then go to Step 3.1 (i.e. repeat this loop).
   4. For j = 1 to t – 1 do:
      1. Let x = y² mod n
      2. If x = 1, go to (outer) Step 5.
      3. If x = n – 1, go to Step 3.1.
      4. Let y = x.
   5. Let x = y² mod n
   6. If x = 1, go to (outer) Step 5.
   7. Continue
4. Output “prime factors not found” and stop.
5. Let p = GCD(y – 1, n) and let q = n/p
6. Output (p, q) as the prime factors.

I recently wrote an implementation in Java. Not directly useful for C# I realise, but perhaps it can be easily ported:

// Step 1: Let k = de – 1. If k is odd, then go to Step 4
BigInteger k = d.multiply(e).subtract(ONE);
if (isEven(k)) {

    // Step 2 (express k as (2^t)r, where r is the largest odd integer
    // dividing k and t >= 1)
    BigInteger r = k;
    BigInteger t = ZERO;

    do {
        r = r.divide(TWO);
        t = t.add(ONE);
    } while (isEven(r));

    // Step 3
    Random random = new Random();
    boolean success = false;
    BigInteger y = null;

    step3loop: for (int i = 1; i <= 100; i++) {

        // 3a
        BigInteger g = getRandomBi(n, random);

        // 3b
        y = g.modPow(r, n);

        // 3c
        if (y.equals(ONE) || y.equals(n.subtract(ONE))) {
            // 3g
            continue step3loop;
        }

        // 3d
        for (BigInteger j = ONE; j.compareTo(t) <= 0; j = j.add(ONE)) {
            // 3d1
            BigInteger x = y.modPow(TWO, n);

            // 3d2
            if (x.equals(ONE)) {
                success = true;
                break step3loop;
            }

            // 3d3
            if (x.equals(n.subtract(ONE))) {
                // 3g
                continue step3loop;
            }

            // 3d4
            y = x;
        }

        // 3e
        BigInteger x = y.modPow(TWO, n);
        if (x.equals(ONE)) {

            success = true;
            break step3loop;

        }

        // 3g
        // (loop again)
    }

    if (success) {
        // Step 5
        p = y.subtract(ONE).gcd(n);
        q = n.divide(p);
        return;
    }
}

// Step 4
throw new RuntimeException("Prime factors not found");

This code uses a few helper definitions/methods:

private static final BigInteger ONE = BigInteger.ONE;
private static final BigInteger TWO = BigInteger.valueOf(2);
private static final BigInteger ZERO = BigInteger.ZERO;

private static boolean isEven(BigInteger bi) {
    return bi.mod(TWO).equals(ZERO);
}

private static BigInteger getRandomBi(BigInteger n, Random rnd) {
    // From http://stackoverflow.com/a/2290089
    BigInteger r;
    do {
        r = new BigInteger(n.bitLength(), rnd);
    } while (r.compareTo(n) >= 0);
    return r;
}