16

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?

1
  • is there any code in openssl to perform this task Nov 1, 2019 at 8:04

4 Answers 4

16

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.

1
  • 3
    Just nitpicking: all RSA needs is that de = 1 mod p-1 and mod q-1, so that's de = 1 mod lcm(p-1,q-1) which is a strict divisor of phi(N) (using phi(N) is just the way RSA was first described). However, the method described by Boneh works in the general case as well. Apr 22, 2011 at 15:40
9

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

2
  • actually i need a code in openssl to perform this task , can u provide if available Nov 1, 2019 at 8:05
  • 1
    You can look at the file librsaconverter.c from my project RsaConverter on SourceForge: sourceforge.net/p/rsaconverter/code/HEAD/tree/Trunk/src/…. There you will find the implementation of the function SfmToCrt that calculate RSA primes from public modulus and private exponent. Nov 2, 2019 at 12:26
6

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!

0

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 = 2tr with r odd and t ≥ 1. We have gk = 1 for every g ∈ ℤN×, and therefore gk/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 gk/2, gk/4, …, gk/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(n3) where n = log2(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)
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.