7
$\begingroup$

Given the RSA modulus $N$ the fastest method to factor it is of sub-exponent order. But, now if I know the private key $d$ of RSA, does that mean I can factor $N$ efficiently?. It intuitively seems true as I know the public/private key pair. Can someone help me to prove this?

Please provide references so that I can read further into this subject.

$\endgroup$
  • 2
    $\begingroup$ If you know $e$, $d$ and $n$, you can efficiently factor $n$. Just knowing $d$ is not enough if $e$ is big. $\endgroup$ – CodesInChaos May 6 '14 at 6:44
  • $\begingroup$ @CodesInChaos Do you mean that knowing $(N,e,d)$ if $e$ is big, then we cannot still factor $N$? $\endgroup$ – T.B May 6 '14 at 8:17
  • 3
    $\begingroup$ Knowing $(N,e,d)$, including with big $e$, allows finding the factorization of $N$, by heuristic or deterministic methods pointed in Samuel Neves's nice answer. If $e$ is unknown but small, we can enumerate small values to find $e$, using $(x^d)^e\equiv x\pmod N$ for arbitrary $x$ such as 2 as a test of having reached the right $e$; and then are back to the same problem [reposted with fix]. $\endgroup$ – fgrieu May 6 '14 at 10:12
8
$\begingroup$

Yes, they are (deterministically) equivalent. The original RSA paper (Section IX.C), working off Miller's results (Theorem 3), showed how knowing the secret exponent $d$ was probabilistically equivalent to factoring $n$.

Later, using more advanced techniques, Coron and May showed how to deterministically reduce finding $d$ to factoring $n$.

$\endgroup$
  • $\begingroup$ when we select $e,d$, generally speaking, if they should $e,d <\phi(N)$ ? $\endgroup$ – T.B May 18 '14 at 2:33
3
$\begingroup$

As S.Neves pointed out, Miller proved that if you know a multiple of $\phi(N)$ then you can factor $N$ in time $O((\log_2{N})^4),$ but he assumed the Extended Riemann Hypothesis. Using, his ideas of his algorithm we can get a probabilistic algorithm.

Since you know $e,d$ you can compute $k=ed-1.$ Also $k\equiv 0\pmod{\phi(N)}.$ Thus, $k=r\cdot \phi(N),$ for some positive $r\in {\mathbb{Z}}.$

Since $\phi(N)$ is even, $k=2^{\alpha}b,$ with $b$ some odd number and $\alpha$ a positive integer. Now, we choose uniformly a number $g$ from the set $\{2,...,N-2\}.$ Then, you get two cases. If $\gcd(g, N)=1$ or not. In the first case Euler's theorem gives $g^{k}\equiv 1\pmod{N}.$ Indeed, $g^{k}=g^{r\phi{(N)}}=(g^{\phi(N)})^{r}\equiv 1\pmod{N}.$ If $\gcd(g,N)>1,$ then choose a new $g.$ For simplicity, we can say, choose $g$ form $\mathbb{Z}_N^{*}.$

So always $g^{k}\equiv 1\pmod{N}.$ This means that $x=g^{k/2}$ is a square root of unity $\mod{N}.$ Since $1$ has four roots $\mod N$ (this from CRT) two roots are the trivial ones, $\pm 1\pmod{N}.$ If $x$ is not one of the previous, then $\gcd(x-1,N)$ will recover one prime factor. If not i.e. $g^{k/2}\equiv 1\pmod{N}$ then we set $x=g^{k/4}$ which is a square root of unity $\mod{N}$ and we check again if $\equiv \pm 1\pmod{N}.$ We continue for all $g^{k/8},...,g^{k/2^{\alpha}},$ where $\alpha=O(\log_2{N}),$ until you find one $x$ which is not $1$ or $-1\pmod{N}.$

If all the elements $g^{k/2},...,g^{k/2^{\alpha}},$ fail to recover a prime factor of $N$ then we choose a new $g.$

The previous algorithm will succeed if we manage to find $g$ such that $g^{k/2^\ell}\not\equiv \pm1 \pmod{N}.$ Once we find such a $g$ then the algorithm returns a prime factor in polynomial time $O(\log_2^{3}N).$ So, to complete the analysis we need $$Pr\big{(}g\leftarrow [2,N-2]:g^{k/2^\ell}\not\equiv\pm 1\pmod{N}, \text{for some}, \ell=1,2,...,\alpha\big{)}.$$ But this probability $\geq 1/2$ since $x$ either will be $\equiv \pm 1 \pmod{N}$ or $\not\equiv \pm 1 \pmod{N}$ (with equal probability since x is random because g is random.)

You can see https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf

$\endgroup$
1
$\begingroup$

Provided $(N,e,d)$, i.e. $N=12191$, $e=59$, $d=5267$, we compute $ed=310753$.

We also know $ed-1$ is a multiple ($k$) of ${\phi(n)}$, so identify $k$ by rounding up $k={ed-1\over N}=26.$ If $\phi(n)={ed-1\over k}={310752\over 26}=11952$ results in a integer whole number, which will be less than $N$, we found $\phi(n)$. Otherwise increment $k$ until we get the an integer result for $\phi(n)$. This is sometimes necessary for smaller factors but not generally for large factors.

The $\textit sum$ is $P+Q=N+1-\phi(n)=240.$

We now have the variables $\textit product=N=12191$ and $\textit sum=240$ needed to compute the roots of the quadratic equation, $ax^2+bx+c=0,$ $$x = \frac{-b \pm \sqrt{b^2-4ac}}{2a}$$ simplified as, $$x = {\left(b\over 2\right) \pm \sqrt{\left(b\over 2\right)^2-c}}$$ Where $a=1$, $b=\textit sum$, $c=\textit product$.

${b\over 2}={240\over 2}=120$

$\sqrt{\left(b\over 2\right)^2-c}=\sqrt{\left(240\over 2\right)^2-12191}=\sqrt{14400-12191}=\sqrt{2209}=47$

$\mathbf Roots:$

$P=120+47=167$

$Q=120-47=73$

Confirm $167*73=12191,$ successfully factoring $N$ knowing $e$ and $d$.


EDIT 1:

@CodesInChaos
Correct! I struggled with that statement because "$ed-1$ is a multiple ($k$) of $\phi(n)$" is a special case, using the original RSA method $e \cdot d \equiv 1 \pmod{\varphi(n)}$. Yet I needed an example.

Where $e \cdot d \equiv 1 \pmod{\lambda(n)}$ is used, current RSA method, it is also true that $\varphi(n)$ is a multiple of $\lambda(n)$. In this case, $k$ then becomes a multiplier to find $\varphi(n)$.

Then continue to find the roots of the quadratic equation.

Here is an example, $N=12191$, $e=17$, $d=inverse(e,\phi(n))=11249$, $d'=inverse(e,\lambda(n))=5273$.

Following $ed=191233$, $k=16$, $\varphi(n)=11952$.

Following $ed'=89641 \cdot 2=179282$, $k=15$, $\varphi(n)=11952$.

P and Q are the roots of quadratic equation, where $a=1$, $b=sum$, and $c=product$.

EDIT 2:

Unfortunately, I cannot respond to responses to my post, yet. So forgive the placement of this response.

I should point out that Conron and May are using $e \cdot d \equiv 1 \pmod{\varphi(n)}$ and a few other "satisfying" conditions for their deterministic method. Also, factorization of $N$ with prime factors of unbalanced size is taking 10 minutes.

$\endgroup$
  • $\begingroup$ RSA only needs $e \cdot d \equiv 1 \pmod{\lambda(n)}$ not $e \cdot d \equiv 1 \pmod{\varphi(n)}$ where $\lambda(n)=\operatorname{lcm}(p-1,q-1)$. So your answer only works in a special case. $\endgroup$ – CodesInChaos Jan 23 '17 at 7:35
  • $\begingroup$ @Carl Knox Does this mean I can factor any $N$ efficiently if I had an efficient method of finding $d$? $\endgroup$ – user13741 Jan 23 '17 at 15:49
  • $\begingroup$ As for why it doesn't always work: if $\phi(N) = \lambda(N) \cdot \text{gcd}(p-1, q-1)$, hence if $\text{gcd}(p-1, q-1)$ is large, value $e \cdot d = k \lambda(N) +1$ doesn't give an obvious clue as to $\phi(N)$. You know $\phi(N) = (a/b)(ed-1)$ for potentially large ints $a, b$. However, the methods Samuel pointed to (which rely on actual Number Theory rather than just algebra) do work, even in this case. // @user13741: Carl's method really doesn't work in all cases; however, the methods that Samuel pointed out in his response does, so the A is "Yes, you can factor $N$ if you could find $d$" $\endgroup$ – poncho Jan 23 '17 at 16:44
  • $\begingroup$ Please do not post another answer to respond to comments. I deleted your “comment-posted-as-answer” and added it into your original answer here as “EDIT 1” for your convenience. Also note that the person you’re replying to (@CodesInChaos) won’t be notified when you mention the nickname in your answer. (Mainly, because answers aren’t meant to be used for that.) I understand things are a bit difficult when you‘re new to the site and don’t have the needed reputation score to really interact with people. To give you a bit of a push, I dropped an upvote for your efforts. Hope that helps… $\endgroup$ – e-sushi Jan 24 '17 at 20:10
  • $\begingroup$ One of the first steps here is the estimation $k \approx \left \lceil (ed - 1) / N\right \rceil$. This approximation is similar to Wiener's attack, which can be used to guess $k$ with $e/N \approx k/dg$ with $g = gcd(p-1,q-1)$. Wiener's attack works against small values of $d$, the proposed one here just works for small values of N. $\endgroup$ – tylo Feb 3 '17 at 11:22

protected by e-sushi Jan 24 '17 at 20:02

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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