Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
4  
I think this answers your question: math.stackexchange.com/questions/12328/… –  mikeazo Mar 8 '13 at 13:56
    
cool, this helps... Thanks! –  user4811 Mar 8 '13 at 14:09
add comment

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.
share|improve this answer
    
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 \;\;$.) –  Ricky Demer Jul 11 '13 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)$. –  minar Jul 11 '13 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)$. –  minar Jul 11 '13 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.) $\;\;\;$ –  Ricky Demer Jul 11 '13 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. –  minar Jul 11 '13 at 19:07
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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