# Is it possible to determine the group order by knowing the "public" and "private" key exponents in an RSA group?

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$)?

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.
• 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 \;\;$.)
– user991
Jul 11, 2013 at 10:44
• 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)$. Jul 11, 2013 at 11:59
• Moreover, the probabilistic algorithm 2 does not need $ed-1$ to be a multiple of $\phi(n)$, only of $lcm(p-1,q-1)$. Jul 11, 2013 at 13:00
• (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.) $\;\;\;$
– user991
Jul 11, 2013 at 19:06
• 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. Jul 11, 2013 at 19:07