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$
2
$\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

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