Hơi lạ khi nói nó "phá vỡ RSA", vì tất nhiên kiến thức về khóa bí mật cho phép bạn giải mã tin nhắn - đây là điều bạn sẽ làm trong trường hợp trung thực khi giải mã tin nhắn của chính mình.
Đầu tiên ông tuyên bố rằng điều này tương đương với $k=ed-1$ là bội của bội chung nhỏ nhất của $p-1$ và $q-1$. Tại sao #1? Nỗ lực của tôi: Tôi biết rằng theo định lý Euler, $m^{\varphi(n)}\equiv 1\mod n$ và đó $\varphi(n)=(p-1)(q-1)$ từ $(m,n)=1$. Hơn nữa kể từ khi $(m,n)=1$ chúng ta có thể chia phương trình của mình cho $m$ và có được $m^k\tương đương 1\mod n$. Tôi nghĩ rằng tôi đang thiếu bước cuối cùng ...
Bạn đang đi đúng hướng. Bởi vì $m^{\varphi(n)}\equiv 1\pmod n$, thì điều này ngụ ý rằng nếu chúng ta có thể tìm thấy một $d$ như vậy mà $ed = r\varphi(n) + 1$ cho một số $r$, sau đó
$$m^{ed}\equiv m^{r\varphi(n) + 1} \equiv (m^{\varphi(n)})^r \cdot m^1 \equiv 1^r \cdot m \ tương đương m\pmod n$$
Vì vậy, đối với một khóa mã hóa nhất định $e$, khóa giải mã tương ứng $d$ đơn giản là một giá trị sao cho $ed = r\varphi(n) + 1$. Trong câu hỏi của bạn, $k = r\varphi(n)$.
$k$ sẽ chẵn vì $\varphi(n)$ sẽ là ngay cả trong trường hợp này - $p, q$ đều là các số nguyên tố khác nhau và tất cả các số nguyên tố ngoại trừ 2 đều là số lẻ, do đó ít nhất một trong số $(p-1)$, $(q-1)$ phải là số chẵn (và có lẽ cả hai sẽ là số chẵn, vì số nguyên tố $2$ sẽ không bao giờ được sử dụng trong RSA.
Tuy nhiên, nếu có một $m$ như vậy mà $m^{k/2}\not\equiv 1\mod n$, thì điều tương tự cũng đúng với ít nhất một nửa số $m$'tội $\mathbb Z_n^*$. Tại sao #2? Nỗ lực của tôi: đây phải là hệ quả của thực tế là nếu $m_0$ là một yếu tố như vậy, sau đó đưa ra $m_1\in \mathbb Z_n^*$ sản phẩm $m_0m_1$ cũng là như vậy mà $$(m_0m_1)^{k/2}=m_0^{k/2}m_1^{k/2}\not\equiv1\mod n, $$ nhưng tôi không chắc tại sao điều này có nghĩa là ít nhất một nửa số phần tử chia sẻ thuộc tính này.
xem xét một $m_0$ như vậy mà $m_0^{k/2} \not\equiv 1 \pmod{n}$. Mỗi sức mạnh kỳ lạ $m_0^{2j + 1}$ của $m_0$ sẽ có cùng một vấn đề, bởi vì
$$(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}$$
bởi vì $m_0^k \equiv 1 \pmod{n}$. Vì vậy, mọi lũy thừa lẻ không hoạt động, nhưng mọi lũy thừa chẵn đều hoạt động, do đó chúng ta có 50/50.
thì chúng ta không thể có $k/2\equiv 0\mod (p-1)$ cũng như $k/2\equiv 0\mod (q-1)$. Tại sao #3? Nỗ lực của tôi: điều này đơn giản là bởi vì nếu cả hai đồng dư này giữ nguyên, thì $k/2$ là bội số của cả hai $p-1$ và $q-1$ và do đó của $\phi(n)$, và do đó theo định lý Euler $m^{k/2}$ nên là $1$ $\mod n$ cho tất cả $m\in \mathbb Z_n^*$ chống lại giả thuyết của chúng tôi.
Chính xác.
Vì vậy, một trong hai đồng dư này giữ còn đồng dư kia thì không (ví dụ: $k/2\tương đương 0\mod p-1$ nhưng $k/2\not\equiv 0\mod q-1$) hoặc không giữ. Trong trường hợp đầu tiên, $m^{k/2}$ luôn luôn là $\equiv 1\mod p$ nhưng chính xác $50\%$ của thời gian đồng dạng với $-1$ modulo $q$. Tại sao #4? Nỗ lực của tôi: Tôi khá bối rối bởi cái này. tôi cho rằng $m^{k/2}\equiv 1\mod p$ một lần nữa theo định lý Euler, như $k/2$ là bội số của $p-1$, tức là bội số của $\phi(p)$. Nhưng tôi không hiểu tại sao $m^{k/2}$ đồng dạng với $-1$ modulo $q$ chính xác $50\%$ của thời gian...
Xem xét $(m^{k/2})^2 \pmod n$. Đây là $m^{k} \equiv 1 \pmod{n}$. Nhưng bởi vì $(m^{k/2}) \equiv 1 \pmod{p}$, sau đó $(m^{k/2}) \equiv \pm 1 \pmod{q}$, nếu không nó sẽ không vuông thành $1$. Đối số tương tự như trên để chỉ ra rằng chúng tôi nhận được mỗi trường hợp 50% thời gian (vì bây giờ chúng tôi được đảm bảo rằng nó không đồng nhất với 1 mọi lúc).
