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

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

• You never care about $p$ and $q$, because only $d$ is used in the decryption (which is $a \longmapsto a^d \mod\, pq$). If you know about $p,q$, then you can compute $(p-1)(q-1)$ and deduce $d$ very easily. Commented Jan 22, 2019 at 9:27
• oh ok cause its mod (n) and not mod (p-1)(q-1) cool. And when I know p and q, I use Euclid's Algorithm to find d? Just like when you encrypt I guess?
– Shaq
Commented Jan 22, 2019 at 9:37
• Commented Jan 22, 2019 at 9:57
• Knowing $d$ is what breaking RSA means! factoring $n$ is not needed: If you can decrypt you have broken the system. Commented Jan 25, 2019 at 5:25

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

• Ok, I think I am not ready enough for it right now.. I get what you have done in the big picture but didn't really understand it fully for every step. I will get to read and study some more and will come back to your answer later :)
– Shaq
Commented Jan 22, 2019 at 11:15
• @Shaq No problem, just let me know if I can expand on some parts. Commented Jan 22, 2019 at 11:33

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

• You mean de <= k(p-1)(q-1) for some integer k? I dot get it: de = 1 mod(p-1)(q-1) so if de = 1+ (p-1)(q-1), how can you find a k such that de = k(p-1)(q-1)? You mean de-1 = k(p-1)(q-1)?
– Shaq
Commented Jan 22, 2019 at 11:23
• Yes, you are correct. I have fixed my answer. Commented Jan 22, 2019 at 11:53
• Ok it looks nice
– Shaq
Commented Jan 22, 2019 at 11:56

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