Given an RSA encryption with public key $(n,e)$. Let say I found out the private key $d$.
So I know $d\cdot e = 1(mod (p-1)(q-1))$ for the primes $p\neq q$ that generate $n$ by $p\cdot q=n$
but from here, how can I efficiency find $p$ and $q$?
And on the other way, I assume the answer is similar. If I know $p$ and $q$, how can I generate $d$ to crack the encryption?
Thanks
Best Answer
Compute $de-1 = 2^r s$ such that $s$ is odd. Pick random $2\leq a \leq N-1$ so that $$ b:=a^s\not\equiv 1\pmod N $$ If this fails, try another $a$. We also check that $\gcd(a,N)=1$, otherwise we have found $p$ or $q$. Now try $$ \gcd(b-1,N),\gcd(b^2-1,N),\dots,\gcd(b^{2^r}-1,N) $$ (This can terminate early once $b^{2^i}\equiv 1\pmod N$.) One of the $\gcd$'s might give you $p$ or $q$ and you are done.
This procedure is expected to terminate fast, within a couple of tries.
We have $$ de\equiv 1 \pmod{(p-1)(q-1)} \implies de-1 = k(p-1)(q-1) = k\cdot \phi(N) $$ where $\phi(\cdot)$ is the Euler Phi function. For any integers $a$ coprime to $N$, they must satisfy $$ a^m\equiv (a^{\phi(N)})^k \equiv 1^k\equiv 1 \pmod N $$ We started with $$ b\equiv a^s \pmod N $$ As we square $b$ iteratively, at some point it must become $1$. This is because $$ b^{2^r}\equiv a^{2^rs} \equiv a^m \equiv 1 \pmod N $$ but it could happen earlier. Since the starting $b$ is not $1$, we have precisely $$ b^{2^i}\not\equiv 1\pmod N,\quad b^{2^{i+1}}\equiv 1 \pmod N $$ for some $i$. Now the RHS becomes $$ (b^{2^i}+1)(b^{2^i}-1) \equiv 0 \pmod N $$ This means $p,q$ divides $(b^{2^i}+1)(b^{2^i}-1)$. As long as they don't both divide the same factor, $$ \gcd(b^{2^i}-1,N)=p \text{ or } q $$ The condition $b^{2^i}\not\equiv 1\pmod N$ ensures that $p,q$ cannot both divide $(b^{2^i}-1)$, so the only way to fail is if $$ b^{2^i}+1 \equiv 0 \pmod N $$ The chances of this happening is very low. (For some $N$ it might not even be possible.)