Немного странно говорить, что это "ломает RSA", потому что, конечно, знание секретного ключа позволяет вам расшифровать сообщение - это то, что вы сделали бы в честном случае при расшифровке своих собственных сообщений.
Сначала он утверждает, что это эквивалентно $k=ed-1$ быть кратным наименьшему общему кратному $p-1$ и $q-1$. Почему №1? Моя попытка: я знаю, что по теореме Эйлера $ м ^ {\ varphi (п)} \ эквив 1 \ мод п $ и что $\varphi(n)=(p-1)(q-1)$ поскольку $(м,п)=1$. Более того, поскольку $(м,п)=1$ мы можем разделить наше уравнение на $м$ и получить $ м ^ к \ экв 1 \ мод п $. Я думаю, что пропустил последний шаг...
Ты на правильном пути. Так как $ м ^ {\ varphi (n)} \ эквив 1 \ pmod п $, то это означает, что если мы можем найти $д$ такой, что $ed = r\varphi(n) + 1$ для некоторых $г$, тогда
$$m^{ed}\equiv m^{r\varphi(n) + 1} \equiv (m^{\varphi(n)})^r\cdot m^1\equiv 1^r\cdot m\ эквивалент m\pmod n$$
Итак, для заданного ключа шифрования $е$, соответствующий ключ расшифровки $д$ просто такое значение, что $ed = r\varphi(n) + 1$. В вашем вопросе, $k = г\varphi(n)$.
$к$ будет даже потому что $\varphi(n)$ будет даже в этом случае - $р, д$ являются различными простыми числами, и все простые числа, кроме 2, нечетны, поэтому по крайней мере одно из $(p-1)$, $(q-1)$ должно быть четным числом (и, вероятно, оба будут четными, потому что простое число $2$ никогда не будет использоваться в RSA.
Если же есть один $м$ такой, что $m^{k/2}\not\equiv 1\mod n$, то то же самое верно как минимум для половины $м$в $\mathbb Z_n^*$. Почему #2? Моя попытка: это должно быть следствием того, что если $m_0$ является таким элементом, то задано $m_1\in\mathbb Z_n^*$ продукт $m_0m_1$ также таков, что $$(m_0m_1)^{k/2}=m_0^{k/2}m_1^{k/2}\not\equiv1\mod n, $$ но я не уверен, почему это означает, что по крайней мере половина элементов имеет это свойство.
Рассмотрим $m_0$ такой, что $m_0^{k/2} \not\equiv 1 \pmod{n}$. Каждая нечетная сила $m_0^{2j + 1}$ из $m_0$ будет та же проблема, потому что
$$(m_0^{2j+1})^{k/2} \эквив (m_0^{k/2})^{2j}\cdot m_0^{k/2} \эквив (m_0^k)^j \cdot m_0^{k/2} \equiv 1 \cdot m_0^{k/2} \not\equiv 1 \pmod{n}$$
так как $m_0^k \экв 1 \pmod{n}$. Таким образом, каждая нечетная степень не работает, но работает любая четная степень, поэтому у нас есть 50/50.
тогда у нас не может быть $k/2\экв 0\mod (p-1)$ а также $k/2\экв 0\mod (q-1)$. Почему №3? Моя попытка: это должно быть просто потому, что если выполняются оба этих сравнения, то $к/2$ кратно обоим $p-1$ и $q-1$ и, следовательно, $\фи(п)$, и, следовательно, по теореме Эйлера $м^{к/2}$ должно быть $1$ $\мод п$ для всех $m\in\mathbb Z_n^*$ против нашей гипотезы.
Правильный.
Таким образом, выполняется одно из этих сравнений, а не другое (например, $k/2\экв 0\mod p-1$ но $k/2\not\equiv 0\mod q-1$) или ни то, ни другое. В первом случае $м^{к/2}$ является всегда $\эквив 1\мод р$ но точно $50\%$ времени, соответствующего $-1$ по модулю $q$. Почему №4? Моя попытка: я довольно смущен этим. Я полагаю, что $m^{k/2}\эквив 1\mod p$ снова по теореме Эйлера, так как $к/2$ является некоторым кратным $p-1$, то есть кратное $\фи(р)$. Но я не понимаю, почему $м^{к/2}$ соответствует $-1$ по модулю $q$ точно $50\%$ времени...
Рассмотреть возможность $(m^{k/2})^2 \pmod n$. Это $m^{k} \эквив 1 \pmod{n}$. Но потому что $(m^{k/2}) \эквив 1 \pmod{p}$, тогда $(m^{k/2}) \эквив\pm 1 \pmod{q}$, иначе это не соответствовало бы $1$. Аргумент аналогичен приведенному выше, чтобы показать, что мы получаем каждый случай в 50% случаев (поскольку теперь мы гарантируем, что он не сравним с 1 каждый раз).
