I have an RSA group with modulus $n = p \cdot q$, two safe primes $p=2p'+1$ and $q=2q'+1$ and the "public" and "private" key exponents $d$ and $e$. $\phi(n) = 4p'q'$ is the order of the RSA group. If I know $\phi(n)$ I can calculate $p$ and $q$. I ask myself what is if I know $e$ and $d$ (and $m$ and $n$) with $m^{d \cdot e\ \bmod\ \phi(n)}\ \bmod\ n$. Is it possible to calculate $\phi$ (and then $p$ and $q$)?


1 Answer 1


The relationship between recovering the decryption exponent $d$ and factoring the RSA modulus $n=pq$ is a classical question in cryptography. There are three useful answers:

  1. The first answer deals with a slightly different question but is useful to gain some insight into the problem. Assume that we given a bit more than $e$ and $d$, more precisely that someone gives up $\phi(n)$ [This is more because $e$ and $d$ only gives us a multiple of $\phi(n)$]. Then, we can compute $s=n+1-\phi(n)=p+q$. As a consequence, we know both the sum ($s$) and the product ($n$) of $p$ and $q$. Thus, $p$ and $q$ are the roots of $X^2-sX+n$. EDIT I forgot to mention that if you are using safe primes and small public exponent such as $65537$, then by removing small factors of $ed-1$, you obtain $p'q'$. Since $\phi(n)=4p'q'$, you can thus use this direct method. EDIT 2 For more details about this method, see the related question: Why is it important that phi(n) is kept a secret, in RSA?
  2. The second answer is the classical one, it shows a probabilistic algorithm that factors $n$ given an arbitrary multiple of $\phi(n)$, such as $ed-1$. See http://www.cs.purdue.edu/homes/ninghui/courses/Fall04/lectures/lect14-c.pdf for detailed examples. The basic idea is to rewrite $ed-1$ as $2^t O$, where $O$ is odd. Then take a random element $w$ modulo $n$. We know that $w^\phi{n}\equiv 1 \pmod{n}$, thus $(w^{O})^{2^t}\equiv 1 \pmod{n}$. Compute $w^O$, then (unless it is equal to $1$) square it repeateadly until you reach $1$. If the number $\ell$ that appears before $1$ is not $n-1$, you obtain a non trivial factor of $n$ as $gcd(n,\ell-1)$. If it does not work, try again with a different $w$. EDIT 3: Additional information about this reduction. In fact, this attack is stronger than that: it still work if we are given a multiple $M$ of $lcm(p-1,q-1)$. Moreover, it even works when $M$ is a multiple of either $(p-1)$ or $(q-1)$.
  3. The most recent answer is that the reduction can be made deterministic using Coppersmith's smooth root algorithm. This was showed by Jean-Sébastien Coron and Alexander May in http://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/paper/springer_joc.pdf (see also http://www.iacr.org/archive/crypto2004/31520213/det.pdf). This solution puts a few additional restriction on $p$, $q$, $e$ and $d$. Namely, $p$ and $q$ must have the same bitsizes and $ed$ should be smaller than $n^2$. This last condition is true when $e$ and $d$ are reduced modulo $\phi{n}$ but may become false for a variant of RSA that would use values of $e$ and/or $d$ not fully reduced.
  • $\begingroup$ Note that $\:(e\hspace{-0.03 in}\cdot\hspace{-0.03 in}d\hspace{.02 in})\hspace{-0.03 in}-\hspace{-0.03 in}1\:$ is not always a multiple of $\phi(n)$. $\;\;\;\;$ (For example, $\;\; \langle n,\hspace{-0.02 in}e,\hspace{-0.02 in}d\hspace{.015 in}\rangle \: = \: \langle 391,\hspace{-0.02 in}3,\hspace{-0.03 in}59\rangle \;\;$.) $\endgroup$
    – user991
    Commented Jul 11, 2013 at 10:44
  • $\begingroup$ Yes and no. It indeed suffices to have $ed\equiv 1 \pmod{lcm(p-1,q-1)}$ but usually people compute $d$ as the inverse of $e$ modulo $\phi(n)$. If you know that it has been computed modulo $\phi(n)/2$ as you did, just double $ed-1$ before starting. It is also possible to build contrived examples where $p-1$ and $q-1$ share a large factor. E.g. $n=491063$, $e=5$ and $d=485$. Even in this case, you can still get a multiple of $\phi(n)$ by squaring $(ed-1)$. In the above example, we have $(ed-1)^2=12\phi(n)$. $\endgroup$
    – minar
    Commented Jul 11, 2013 at 11:59
  • $\begingroup$ Moreover, the probabilistic algorithm 2 does not need $ed-1$ to be a multiple of $\phi(n)$, only of $lcm(p-1,q-1)$. $\endgroup$
    – minar
    Commented Jul 11, 2013 at 13:00
  • $\begingroup$ (I actually computed $d$ as the inverse of $e$ modulo $\:\operatorname{lcm}(\hspace{.03 in}p\hspace{-0.03 in}-\hspace{-0.04 in}1\hspace{.01 in},q\hspace{-0.03 in}-\hspace{-0.04 in}1)\:$, $\hspace{2 in}$ although that's obviously equivalent in this case.) $\;\;\;$ $\endgroup$
    – user991
    Commented Jul 11, 2013 at 19:06
  • $\begingroup$ Oups. I mistyped $ed\equiv 1 \pmod{gcd(p-1,q-1)}$ instead of $ed\equiv 1 \pmod{lcm(p-1,q-1)}$. And then I repeated $gcd(p-1,q-1)$ instead of $lcm(p-1,q-1)$ in the next comment. Sorry ... And for some reason, I can't edit my comments to correct that. $\endgroup$
    – minar
    Commented Jul 11, 2013 at 19:07

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.