# Breaking RSA with knowledge of the secret key $(n, d)$

I am following the discussion in Koblitz in the second paragraph in the RSA section (page 94 on my edition).The goal is to show that knowledge of an integer $$d$$ such that $$m^{ed}\equiv m \mod n$$ for all $$m$$ with $$(m,n)=1$$ breaks RSA.The problem is that I'm no mathematician and I need some help to untangle myself at various points.

He first states that this is equivalent to $$k=ed-1$$ being a multiple of the least common multiple of $$p-1$$ and $$q-1$$. Why #1? My attempt: I know that by Euler's theorem, $$m^{\varphi(n)}\equiv 1\mod n$$ and that $$\varphi(n)=(p-1)(q-1)$$ since $$(m,n)=1$$. Moreover since $$(m,n)=1$$ we can divide our equation by $$m$$ and obtain $$m^k\equiv 1\mod n$$. I think I'm missing the final step...

He goes on to suppose that $$m^k\equiv 1\mod n$$ for all $$m$$ prime to $$n$$. $$k$$ must be even, because the equation should hold for $$m=-1$$. So we can check if $$m^{k/2}\equiv 1\mod n$$ as well for all $$m$$ prime to n, that is, for all $$m$$ in $$\mathbb Z_n^*$$. If however there is one $$m$$ such that $$m^{k/2}\not\equiv 1\mod n$$, then the same is true for at least half of the $$m$$'s in $$\mathbb Z_n^*$$. Why #2? My attempt: this should be a consequence of the fact that if $$m_0$$ is such an element, then given $$m_1\in \mathbb Z_n^*$$ the product $$m_0m_1$$ is also such that $$(m_0m_1)^{k/2}=m_0^{k/2}m_1^{k/2}\not\equiv1\mod n,$$ but I'm not sure why this means that at least half of the elements share this property.

As a result, if we test many $$m$$'s and always find $$m^{k/2}\equiv 1\mod n$$, then it is very likely that the congruence holds for all the elements of $$\mathbb Z_n^*$$ and thus we can replace $$k$$ by $$k/2$$. We iterate until this is no more true: then we cannot have $$k/2\equiv 0\mod (p-1)$$ as well as $$k/2\equiv 0\mod (q-1)$$. Why #3? My attempt: this should be simply because if both these congruences hold, then $$k/2$$ is a multiple of both $$p-1$$ and $$q-1$$ and therefore of $$\phi(n)$$, and thus by Euler's theorem $$m^{k/2}$$ should be $$1$$ $$\mod n$$ for all $$m\in \mathbb Z_n^*$$ against our hypothesis.

So, either one of these congruences holds and not the other (for example, $$k/2\equiv 0\mod p-1$$ but $$k/2\not\equiv 0\mod q-1$$) or neither holds. In the first case, $$m^{k/2}$$ is always $$\equiv 1\mod p$$ but exactly $$50\%$$ of the time congruent to $$-1$$ modulo $$q$$. Why #4? My attempt: I'm rather confused by this one. I suppose that $$m^{k/2}\equiv 1\mod p$$ again by Euler's theorem, as $$k/2$$ is some multiple of $$p-1$$, that is, a multiple of $$\phi(p)$$. But I don't see why $$m^{k/2}$$ is congruent to $$-1$$ modulo $$q$$ exactly $$50\%$$ of the time...

The second case should be analogous to the first one, so I'll spare you a fifth question. Could anyone be so patient to clear up these four points for me?

It is a bit strange to say it "breaks RSA", because of course knowledge of the secret key allows you to decrypt the message - this is what you would do in the honest case when decrypting your own messages.

He first states that this is equivalent to $$k=ed-1$$ being a multiple of the least common multiple of $$p-1$$ and $$q-1$$. Why #1? My attempt: I know that by Euler's theorem, $$m^{\varphi(n)}\equiv 1\mod n$$ and that $$\varphi(n)=(p-1)(q-1)$$ since $$(m,n)=1$$. Moreover since $$(m,n)=1$$ we can divide our equation by $$m$$ and obtain $$m^k\equiv 1\mod n$$. I think I'm missing the final step...

You are on the right track. Because $$m^{\varphi(n)}\equiv 1\pmod n$$, then this implies that if we can find a $$d$$ such that $$ed = r\varphi(n) + 1$$ for some $$r$$, then $$m^{ed}\equiv m^{r\varphi(n) + 1} \equiv (m^{\varphi(n)})^r \cdot m^1 \equiv 1^r \cdot m \equiv m\pmod n$$

So for a given encryption key $$e$$, the corresponding decryption key $$d$$ is simply a value such that $$ed = r\varphi(n) + 1$$. In your question, $$k = r\varphi(n)$$.

$$k$$ will be even because $$\varphi(n)$$ will be even in this case - $$p, q$$ are both distinct primes, and all primes except 2 are odd, so at least one of $$(p-1)$$, $$(q-1)$$ must be an even number (and probably both will be, because the prime $$2$$ would never be used in RSA.

If however there is one $$m$$ such that $$m^{k/2}\not\equiv 1\mod n$$, then the same is true for at least half of the $$m$$'s in $$\mathbb Z_n^*$$. Why #2? My attempt: this should be a consequence of the fact that if $$m_0$$ is such an element, then given $$m_1\in \mathbb Z_n^*$$ the product $$m_0m_1$$ is also such that $$(m_0m_1)^{k/2}=m_0^{k/2}m_1^{k/2}\not\equiv1\mod n,$$ but I'm not sure why this means that at least half of the elements share this property.

Consider an $$m_0$$ such that $$m_0^{k/2} \not\equiv 1 \pmod{n}$$. Every odd power $$m_0^{2j + 1}$$ of $$m_0$$ will have the same issue, because $$(m_0^{2j+1})^{k/2} \equiv (m_0^{k/2})^{2j}\cdot m_0^{k/2} \equiv (m_0^k)^j \cdot m_0^{k/2} \equiv 1 \cdot m_0^{k/2} \not\equiv 1 \pmod{n}$$ because $$m_0^k \equiv 1 \pmod{n}$$. So every odd power doesn't work, but every even power does, hence we have 50/50.

then we cannot have $$k/2\equiv 0\mod (p-1)$$ as well as $$k/2\equiv 0\mod (q-1)$$. Why #3? My attempt: this should be simply because if both these congruences hold, then $$k/2$$ is a multiple of both $$p-1$$ and $$q-1$$ and therefore of $$\phi(n)$$, and thus by Euler's theorem $$m^{k/2}$$ should be $$1$$ $$\mod n$$ for all $$m\in \mathbb Z_n^*$$ against our hypothesis.

Correct.

So, either one of these congruences holds and not the other (for example, $$k/2\equiv 0\mod p-1$$ but $$k/2\not\equiv 0\mod q-1$$) or neither holds. In the first case, $$m^{k/2}$$ is always $$\equiv 1\mod p$$ but exactly $$50\%$$ of the time congruent to $$-1$$ modulo $$q$$. Why #4? My attempt: I'm rather confused by this one. I suppose that $$m^{k/2}\equiv 1\mod p$$ again by Euler's theorem, as $$k/2$$ is some multiple of $$p-1$$, that is, a multiple of $$\phi(p)$$. But I don't see why $$m^{k/2}$$ is congruent to $$-1$$ modulo $$q$$ exactly $$50\%$$ of the time...

Consider $$(m^{k/2})^2 \pmod n$$. This is $$m^{k} \equiv 1 \pmod{n}$$. But because $$(m^{k/2}) \equiv 1 \pmod{p}$$, then $$(m^{k/2}) \equiv \pm 1 \pmod{q}$$, otherwise it would not square to $$1$$. The argument is similar to above to show that we get each case 50% of the time (since we are guaranteed now that it is not congruent to 1 every time).

• You are a gentleman and a scholar! Sorry to bother you, I still have a couple of issues. First of all, there may be a small typo in the first equation ($1^k$ instead of $1^r$). Secondly, I'm still not getting why $$(m^{k/2})^2\equiv 1 \ (\text{mod } n) \quad \text{and}\quad m^{k/2}\equiv 1 \ (\text{mod } p)$$ together mean that $m^{k/2}\equiv \pm 1 \ (\text{mod } q)$. Commented Jan 28, 2022 at 21:35
• Good typo spot, fixed! If $(m^{k/2})^2 \equiv 1 \pmod{n}$ and $(m^{k/2})^2 \equiv 1 \pmod{p}$ then $(m^{k/2})^2 \equiv 1 \pmod{q}$, otherwise we'd have a contradiction. The only possible "square roots" of $(m^{k/2})^2 \pmod{q}$ must therefore be $\pm 1$, which are the only square roots of $1 \pmod{q}$. Hope that clarifies! If the answer helped, please remember to upvote and accept it :) Commented Jan 28, 2022 at 21:54