0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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)$. $\endgroup$ Commented Jan 28, 2022 at 21:35
  • $\begingroup$ 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 :) $\endgroup$ Commented Jan 28, 2022 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.