How to factor RSA modulus given the public and private exponent?

Question

I have a RSA private key with modulus m, public exponent e and private exponent d, but the program I am using needs the modulus's prime factors p and q.

Is it possible to use e and d to get p and q?

Answer 1

I put in the effort to dig through Boneh's paper. The "algorithm" for deriving (p, q) from (n, d) is buried at the end of §1.1, coded in maths jargon, and left as an exercise for the reader to render out of his (rather terse) proof that it's efficient to do so.

Let 〈N, e〉 be an RSA public key. Given the private key d, one can efficiently factor the modulus N = pq.

Proof. Compute k = de − 1. By definition of d and e we know that k is a multiple of φ(N). Since φ(N) is even, k = 2^tr with r odd and t ≥ 1. We have g^k = 1 for every g ∈ ℤ_N^×, and therefore g^k/2 is a square root of unity modulo N. By the Chinese Remainder Theorem, 1 has four square roots modulo N = pq. Two of these square roots are ±1. The other two are ±x where x satisfies x = 1 mod p and x = −1 mod q. Using either one of these last two square roots, the factorization of N is revealed by computing gcd(x − 1, N). A straightforward argument shows that if g is chosen at random from ℤ_N^× then with probability at least 1/2 (over the choice of g) one of the elements in the sequence g^k/2, g^k/4, …, g^k/2t mod N is a square root of unity that reveals the factorization of N. All elements in the sequence can be efficiently computed in time O(n³) where n = log₂(N).

Obviously, this is pretty close to meaningless for anyone who doesn't know what $Z_N^\ast$ is, and has a pretty nonlinear structure that takes a good deal of time to twist into a linear algorithm.

So here is the worked solution:

from random import randrange
from math import gcd


def ned_to_pqe(secret_key):
    """
    https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf#:~:text=Given%20d%2C,reveals%20the%20factorization%20of%20N%2E
    """
    n, e, d = secret_key
    k = d * e - 1
    t = bit_scan1(k)
    trivial_sqrt1 = {1, n - 1}
    while True:
        g = randrange(2, n - 1)
        for j in range(1, t + 1):
            x = pow(g, k >> j, n)
            if pow(x, 2, n) == 1:
                if x in trivial_sqrt1: continue
                p = gcd(x - 1, n)
                q = n // p
                if q > p: p, q = q, p
                return p, q, e


def pqe_to_ned(secret_key):
    p, q, e = secret_key
    n = p * q
    l = (p - 1) * (q - 1)
    d = pow(e, -1, l)
    return n, e, d


def bit_scan1(i):
    """
    https://gmpy2.readthedocs.io/en/latest/mpz.html#mpz.bit_scan1
    """
    # https://stackoverflow.com/a/63552117/1874170
    return (i & -i).bit_length() - 1


def test():
    secret_key = (
        # https://en.wikipedia.org/wiki/RSA_numbers#RSA-100
        # Should take upwards of an hour to factor on a consumer desktop ca. 2022
        1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139,
        65537,
        1435319569480661473883310243084583371347212233430112391255270984679722445287591616684593449660400673
    )
    if secret_key != pqe_to_ned(ned_to_pqe(secret_key)):
        raise ValueError


if __name__ == '__main__':
    test()
    print("Self-test OK")

Live demo (JS):

function ned_to_pqe({n, e, d}) {
  // https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf#:~:text=Given%20d%2C,reveals%20the%20factorization%20of%20N%2E
  let k = d * e - 1n;
  let t = scan1(k);
  let trivial_sqrt1 = new Set([1n, n - 1n]);
  while (true) {
    let g = insecure_randrange(2n, n - 1n);
    for ( let j = t ; j > 0 ; --j ) {
      let x = bn_powMod(g, k >> j, n);
      if (bn_powMod(x, 2n, n) === 1n) {
        if (trivial_sqrt1.has(x)) continue;
        let p = gcd(x - 1n, n), q = n/p;
        if (q > p) [p, q] = [q, p];
        return {p, q, e};
      }
    }
  }
}


function pqe_to_ned({p, q, e}) {
  let n = p * q;
  let l = (p - 1n) * (q - 1n);
  let d = bn_modInv(e, l);
  return {n, e, d};
}


function bn_powMod(x, e, m) {
  // h/t https://umaranis.com/2018/07/12/calculate-modular-exponentiation-powermod-in-javascript-ap-n/
  if (m === 1n) return 0n;
  let y = 1n;
  x = x % m;
  while (e > 0n) {
    if (e % 2n === 1n)  //odd number
      y = (y * x) % m;
    e = e >> 1n;  //divide by 2
    x = (x * x) % m;
  }
  return y;
}


function bn_modInv(x, m) {
  // TOY IMPLEMENTATION
  // DO NOT USE IN GENERAL-PURPOSE CODE
  // h/t https://rosettacode.org/wiki/Modular_inverse#C
  let m0 = m, t, q;
  let x0 = 0n, y = 1n;
  if (m === 1n) return 1n;
  while (x > 1n) {
    q = x / m;
    t = m;
    m = x % m;
    x = t;
    t = x0;
    x0 = y - q * x0;
    y = t;
  }
  if (y < 0n) y += m0;
  return y;
}


function gcd(a, b) {
  // h/t https://stackoverflow.com/a/17445304/1874170
  while (b) {
    [a, b] = [b, a % b];
  }
  return a;
}


function scan1(i) {
  // https://gmplib.org/manual/Integer-Logic-and-Bit-Fiddling#mpz_scan1
  let k = 0n;
  if ( i !== 0n ) {
    while( (i & 1n) === 0n ) {
      i >>= 1n;
      k += 1n;
    }
  }
  return k;
}


function insecure_randrange(a, b) {
  // h/t https://arxiv.org/abs/1304.1916
  let numerator = 0n;
  let denominator = 1n;
  let n = (b - a);
  while (true) {
    numerator <<= 1n;
    denominator <<= 1n;
    numerator |= BigInt(Math.random()>1/2);
    if (denominator >= n) {
      if (numerator < n)
        return a + numerator;
      numerator -= n;
      denominator -= n;
    }
  }
}

<form action="javascript:" onsubmit="(({target:form,submitter:{value:action}})=>{eval(action)(form)})(event)">
<p>
<label for="p">p=</label><input name="p" value="37975227936943673922808872755445627854565536638199" /><br />
<label for="q">q=</label><input name="q" value="40094690950920881030683735292761468389214899724061" /><br />
<label for="n">n=</label><input name="n" /><br />
<label for="e">e=</label><input name="e" placeholder="65537" /><br />
<label for="d">d=</label><input name="d" /><br />
</p>
<p>
<button type="submit" value="pqe2nd">Get (n,d) from (p,q,e)</button><br />
<button type="submit" value="delpq">Forget (p,q)</button><br />
<button type="submit" value="ned2pq">Get (p,q) from (n,e,d)</button>
</form>

<script>
function pqe2nd({elements}) {
  if (!elements['e'].value) elements['e'].value = elements['e'].placeholder;
  let p = BigInt(elements['p'].value||undefined);
  let q = BigInt(elements['q'].value||undefined);
  let e = BigInt(elements['e'].value||undefined);
  let {n, d} = pqe_to_ned({p,q,e});
  elements['n'].value = n.toString();
  elements['d'].value = d.toString();
}
function ned2pq({elements}) {
  if (!elements['e'].value) elements['e'].value = elements['e'].placeholder;
  let n = BigInt(elements['n'].value||undefined);
  let e = BigInt(elements['e'].value||undefined);
  let d = BigInt(elements['d'].value||undefined);
  let {p, q} = ned_to_pqe({n,e,d});
  elements['p'].value = p.toString();
  elements['q'].value = q.toString();
}
function delpq({elements}) {
  elements['p'].value = null;
  elements['q'].value = null;
}
</script>

---

To answer the question as-stated in the title: factoring N entails finding N. But you cannot, in the general case, derive N from (e, d). Therefore, you cannot, in the general case, derive the factors of N from (e, d); QED.

finding n from (e, d) is computationally feasible with fair probability, or even certainty, for a small but observable fraction of RSA keys of practical interest

If you want to try to do so anyway, you'll need to be able to factorize e * d - 1 (if I understand the above-linked answer correctly):

from itertools import permutations


def ed_to_pq(e, d):
    # NOT ALWAYS POSSIBLE -- the number e*d-1 must be small enough to factorize
    # h/t https://crypto.stackexchange.com/a/81620/8287
    factors = factorize(e * d - 1)
    factors.sort()
    # Unimplemented optimization:
    #   if two factors are larger than (p * q).bit_length()//4
    #   and the greater of (p, q) is not many times bigger than the lesser,
    #   then you can safely assume that the large factors belong to (p-1) and (q-1)
    #   and thereby reduce the number of iterations in the following loops
    # Unimplemented optimization:
    #   permutations are overkill for this partitioning scheme;
    #   a clever mathematician could come up with something more efficient
    # Unimplemented optimization:
    #   prune permutations based on "sanity" factor of logarithm knapsacking
    l = len(factors)
    for arrangement in permutations(factors):
        for l_pm1 in range(1, l - 1):
            for l_qm1 in range(1, l_pm1):
                pm1 = prod(arrangement[:l_pm1])
                qm1 = prod(arrangement[l_pm1:l_pm1+l_qm1])
                try:
                    if pow(e, -1, pm1 * qm1) == d:
                        return (pm1 + 1, qm1 + 1)
                except Exception:
                    pass


from functools import reduce
from operator import mul


def prod(l):
    return reduce(mul, l)

Answer 2

I posted a response on the crypto stack exchange answering the same question here. It uses the same approach as outlined in Boneh's paper, but does a lot more explanation as to how it actually works. I also try to assume a minimal amount of prior knowledge.

Hope this helps!

Answer 3

You can use the open source tool I have developed in 2009 that converts RSA keys between the SFM format (n,e,d) and CRT format (p,q,dp,dq,u), and the other way around. It is on SourceForge : http://rsaconverter.sourceforge.net/

The algorithm I implemented is based on ideas presented by Dan Boneh, as described by the previous answer.

I hope this will be useful.

Mounir IDRASSI - IDRIX

Answer 4

Yes -- once you know the modulus N, and public/private exponents d and e, it is not too difficult to obtain p and q such that N=pq.

This paper by Dan Boneh describes an algorithm for doing so. It relies on the fact that, by definition,

de = 1 mod phi(N).

For any randomly chosen "witness" in (2,N), there is about a 50% chance of being able to use it to find a nontrivial square root of 1 mod N (call it x). Then gcd(x-1,N) gives one of the factors.