How can I break RSA if I know the private key?

Question

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

Answer 1

You know that $de = k(p-1)(q-1)+1$ for some integer $k$, and you know $n=pq$. Find the first multiple of $n$ that is greater then $de$ - this will be $kn$, and

$kn-de+1 = kpq - k(p-1)(q-1) = k(p+q-1) \\ \Rightarrow p+q=\frac{kn-de+k+1}{k}$

Once you know $p+q$ then you also have

$p-q=\sqrt{(p+q)^2-4n}$

and then you can find $p$ and $q$.

For example, if $n=187$, $d=37$ and $e=13$ then $k=\lceil\frac{de}{n}\rceil=3$ and

$p+q=\frac{3\times187 -481 + 4}{3}=28\\p-q=\sqrt{28^2-4\times187}=6$

and so $p=17$, $q=11$.

Answer 2

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.)

Answer 3

To answer your second question:

Given an RSA encryption with public key $(n,e)$.

If I know $p$ and $q$, how can I generate $d$ to crack the encryption?

Knowing $p​$ and $q​$, we use Euler's totient function, $$ \varphi(n) = (p - 1)(q - 1). $$

Then in order to compute $d$ in text-book RSA we need to use the following congruence relation:

$$ de \equiv_{\varphi(n)} 1 $$

Since we know $\varphi(n)$ and $e$, all you need to do now is use the Extended Eucledian algorithm. First start by computing $\gcd(\varphi(n), e)$, then work your way back to find $d$.