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

Question

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?

Answer 1

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