6
$\begingroup$

I have an RSA public key (public modulus $N$ and public exponent $e$), and the private exponent $d$ of matching private key.

How can I compute $p$ and $q$, the primes factor of $N$ ?

$\endgroup$
  • 4
    $\begingroup$ First of all, welcome to Crypto Stack exchange. You may want to take a look at di-mgt.com.au/rsa_factorize_n.html. $\endgroup$ – chelsea Sep 19 '18 at 6:14
  • 1
    $\begingroup$ It is not possible that there isn't at least one duplicate of this question on this site. Have you done a search? $\endgroup$ – Thomas Sep 19 '18 at 8:23
  • 1
    $\begingroup$ @Thomas: the closest I found is this question, but it asks whether $N$ can be factored, not how. The accepted answer focuses on that without explicitly giving the algorithms it refers to. Other answers are not algorithm-centric either, and give explanations assuming $e\,d\equiv1\pmod{\phi(N)}$ for one and $d=e^{-1}\bmod\phi(N)$ for another, which does not hold for all valid $(N,e,d)$. $\endgroup$ – fgrieu Sep 19 '18 at 9:51
  • 2
    $\begingroup$ @fgrieu what about this one and this other one and 111's answer to the linked question? $\endgroup$ – SEJPM Sep 19 '18 at 11:43
  • $\begingroup$ Sorry everyone. It's my mistake. Thank you for all $\endgroup$ – user61922 Sep 19 '18 at 12:28
10
$\begingroup$

Algorithm

An RSA modulus $N$ product of large distinct primes can be factored given $(N,e,d)$ per:

  1. Compute $f\gets e\,d-1$, and express $f$ as $2^s\,t$ with $t$ odd
  2. Set $i\gets s$ and $a\gets2$
  3. Compute $b\gets a^t\bmod N$ , and if $b=1$ then
    • set $a$ to the next prime, and proceed at 3
  4. If $i\ne1$ then
    • compute $c\gets b^2\bmod N$ , and if $c\ne1$ then
      • set $b\gets c$, decrease $i$, and proceed at 4
  5. If $b=N-1$ then
    • set $a$ to the next prime, and proceed at 3
  6. Compute and output $p\gets\gcd(b-1,N)$ , and $q\gets N/p$.

For standard RSA where $N$ has 2 distinct factors, we have fully factored $N$. Otherwise, $p$ or/and $q$ won't be prime, just re-run the algorithm from step 2 replacing $N$ by any still unfactored component, until all the prime factors of $N$ have been pulled out.


Justification

In an RSA context, $N$ has no small prime factor, thus the algorithm's $a$ at step 3 will remain small enough that $\gcd(a,N)=1$ will hold (if it did not, $a$ would be a factor of $N$ found by trial division; a trivial modification of the algorithm additionally handles $N$ with such small factors).

For any valid RSA triple $(N,e,d)$, it holds that $\left(a^e\right)^d\bmod N=a$ for any integer $a$ in $[0,n)$ (because textbook RSA decryption works).

Thus for any $a$ used in the algorithm, $a^{e\,d-1}\bmod N=1$ holds, that is $a^f\bmod N=1$ for the $f$ of step 1.

The $t$ and $s$ of step 1 are uniquely defined, with $s>0$, and $\left(a^t\right)^{\left(2^s\right)}\bmod N=1$.

For most $N$, step 3 will quickly find an $a$ with $a^t\bmod N\ne1$. Argument: Since $N$ is squarefree, by the Chineese Remainder Theorem, an $a$ coprime with $N$ is rejected at step 3 iff $a^t\bmod p=1$ for all primes $p$ dividing $N$. Since $t$ is odd, if $a^t\bmod p=1$ holds for $a$, then $\tilde a^t\bmod p=p-1\ne1$ for $\tilde a=-a\bmod p$. Thus for $a$ coprime with $N$ chosen randomly in some large interval, the probability of $a^t\bmod p=1$ is $\le\frac12$. That is independently for each $p$, thus $a^t\bmod N\ne1$ has probability $\ge1-2^{-m}$ where $m\ge2$ is the number of factors of $N$. Using the consecutive primes $a$ (rather than random $a$) works well in practice for random instances of the problem (I have no proof, and one may require the Extended Riemann Hypothesis).

Before each iteration of step 4, it holds $1<b<N$, with $i\ge1$, and $b^{\left(2^i\right)}\bmod N=1$ ; thus after at most $s-1$ computations in step 4 we reach step 5 with $b\bmod N\ne1$ and $b^2\bmod N=1$.

Step 5 excludes the case $b=N-1$, which is rare in practice (I'm looking for an argument).

Thus at step 6, $\gcd(b-1,N)$ is a non-trivial factor of $N$.


References

A similar algorithm was hinted at in the original RSA paper: Ronald L. Rivest, Adi Shamir, and Leonard Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, in CACM 1978; see last two paragraphs of section IX-C. That uses and references the proof of a primality test in Gary L. Miller's Riemann's Hypothesis and tests for primality, in proceedings of STOC 1975.

A more detailed exposition is in Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography, CRC Press 1997; see last paragraph of section 8.2.2 (i).

That answer's algorithm differs by using incremental primes $a$ rather than random $a$. That makes the algorithm deterministic (not its runtime), and works well in practice. As a minor aside, the number of modular squares computed in step 4 is minimized by using a test of $i$ rather than an additional last square.

Note: Simpler variations restrict to $b=a^t\bmod N$ or $b=a^{f/2}\bmod N$, but require testing sizably more $a$ when $s$ is large, which occasionally happens. Some justifications assume $d=e^{-1}\bmod\varphi(N)$ or $e\,d\equiv1\pmod{\varphi(N)}$, which does not consistently hold in modern RSA: for FIPS 186-4 that has probability less than $\frac1 3$, because $d=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$ is required.

For a (different) deterministic polynomial-time algorithm, see Jean-Sebastien Coron and Alexander May's Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring, in JoC 2007.

$\endgroup$
  • 1
    $\begingroup$ that's great. Is there a reference, or some context about where this algorithm appeared? $\endgroup$ – Cédric Van Rompay Sep 19 '18 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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