在知道密鑰的情況下破解 RSA(n,d)(n,d)(n, d)
我正在關注 RSA 部分（我的版本的第 94 頁）第二段中 Koblitz 中的討論。目標是展示整數的知識 $ d $ 這樣$$ m^{ed}\equiv m \mod n $$對所有人 $ m $ 和 $ (m,n)=1 $ 打破了 RSA。問題是我不是數學家，我需要一些幫助來解開自己在各個方面的糾結。
他首先指出，這相當於 $ k=ed-1 $ 是最小公倍數的倍數 $ p-1 $ 和 $ q-1 $ . 為什麼是#1？ 我的嘗試：我知道根據歐拉定理， $ m^{\varphi(n)}\equiv 1\mod n $ 然後 $ \varphi(n)=(p-1)(q-1) $ 自從 $ (m,n)=1 $ . 此外，由於 $ (m,n)=1 $ 我們可以將方程除以 $ m $ 並獲得 $ m^k\equiv 1\mod n $ . 我想我錯過了最後一步……
他繼續假設 $ m^k\equiv 1\mod n $ 對所有人 $ m $ 素數 $ n $ . $ k $ 必須是偶數，因為等式應該成立 $ m=-1 $ . 所以我們可以檢查是否 $ m^{k/2}\equiv 1\mod n $ 也適用於所有人 $ m $ n的素數，即對所有 $ m $ 在 $ \mathbb Z_n^* $ . 但是，如果有一個 $ m $ 這樣 $ m^{k/2}\not\equiv 1\mod n $ , 那麼至少一半的情況也是如此 $ m $ 是在 $ \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 $ 的並且總能找到 $ m^{k/2}\equiv 1\mod n $ ，那麼很可能同餘對所有的元素都成立 $ \mathbb Z_n^* $ 因此我們可以替換 $ k $ 經過 $ k/2 $ . 我們迭代直到這不再是真的：那麼我們不能有 $ k/2\equiv 0\mod (p-1) $ 也 $ k/2\equiv 0\mod (q-1) $ . 為什麼是#3？ 我的嘗試：這應該僅僅是因為如果這兩個全等都成立，那麼 $ k/2 $ 是兩者的倍數 $ p-1 $ 和 $ q-1 $ 因此 $ \phi(n) $ ，因此由歐拉定理 $ m^{k/2} $ 應該 $ 1 $ $ \mod n $ 對所有人 $ m\in \mathbb Z_n^ $ 反對我們的假設。*
因此，這些全等中的任何一個都成立，而另一個則不成立（例如， $ k/2\equiv 0\mod p-1 $ 但 $ k/2\not\equiv 0\mod q-1 $ ) 或都不成立。在第一種情況下， $ m^{k/2} $ 總是 $ \equiv 1\mod p $ 但確切地說 $ 50% $ 時間一致 $ -1 $ 模組 $ q $ . 為什麼是#4？ 我的嘗試：我對此感到很困惑。我想 $ m^{k/2}\equiv 1\mod p $ 再次由歐拉定理，如 $ k/2 $ 是一些倍數 $ p-1 $ , 也就是 的倍數 $ \phi(p) $ . 但我不明白為什麼 $ m^{k/2} $ 是一致的 $ -1 $ 模組 $ q $ 確切地 $ 50% $ 當時…
第二種情況應該與第一種情況類似，所以我給你第五個問題。誰能這麼耐心的幫我理清這四點？
說它“破壞 RSA”有點奇怪，因為當然知道密鑰可以讓您解密消息 - 這是您在解密自己的消息時會做的誠實情況。
他首先指出，這相當於 $ k=ed-1 $ 是最小公倍數的倍數 $ p-1 $ 和 $ q-1 $ . 為什麼是#1？ 我的嘗試：我知道根據歐拉定理， $ m^{\varphi(n)}\equiv 1\mod n $ 然後 $ \varphi(n)=(p-1)(q-1) $ 自從 $ (m,n)=1 $ . 此外，由於 $ (m,n)=1 $ 我們可以將方程除以 $ m $ 並獲得 $ m^k\equiv 1\mod n $ . 我想我錯過了最後一步……
你在正確的軌道上。因為 $ m^{\varphi(n)}\equiv 1\pmod n $ , 那麼這意味著如果我們能找到一個 $ d $ 這樣 $ ed = r\varphi(n) + 1 $ 對於一些 $ r $ ， 然後 $$ 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 $$
所以對於給定的加密密鑰 $ e $ ，對應的解密密鑰 $ d $ 只是一個值，使得 $ ed = r\varphi(n) + 1 $ . 在你的問題中， $ k = r\varphi(n) $ .
$ k $ 甚至會因為 $ \varphi(n) $ 即使在這種情況下 - $ p, q $ 都是不同的素數，並且除了 2 之外的所有素數都是奇數，所以至少有一個 $ (p-1) $ , $ (q-1) $ 必須是偶數（可能兩者都是，因為素數 $ 2 $ 永遠不會在 RSA 中使用。
但是，如果有一個 $ m $ 這樣 $ m^{k/2}\not\equiv 1\mod n $ , 那麼至少一半的情況也是如此 $ m $ 是在 $ \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} \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} $$ 因為 $ m_0^k \equiv 1 \pmod{n} $ . 所以每個奇數次冪都不起作用，但每個偶數次冪都起作用，因此我們有 50/50。
那麼我們不能擁有 $ k/2\equiv 0\mod (p-1) $ 也 $ k/2\equiv 0\mod (q-1) $ . 為什麼是#3？ 我的嘗試：這應該僅僅是因為如果這兩個全等都成立，那麼 $ k/2 $ 是兩者的倍數 $ p-1 $ 和 $ q-1 $ 因此 $ \phi(n) $ ，因此由歐拉定理 $ m^{k/2} $ 應該 $ 1 $ $ \mod n $ 對所有人 $ m\in \mathbb Z_n^ $ 反對我們的假設。*
正確的。
因此，這些全等中的任何一個都成立，而另一個則不成立（例如， $ k/2\equiv 0\mod p-1 $ 但 $ k/2\not\equiv 0\mod q-1 $ ) 或都不成立。在第一種情況下， $ m^{k/2} $ 總是 $ \equiv 1\mod p $ 但確切地說 $ 50% $ 時間一致 $ -1 $ 模組 $ q $ . 為什麼是#4？ 我的嘗試：我對此感到很困惑。我想 $ m^{k/2}\equiv 1\mod p $ 再次由歐拉定理，如 $ k/2 $ 是一些倍數 $ p-1 $ , 也就是 的倍數 $ \phi(p) $ . 但我不明白為什麼 $ m^{k/2} $ 是一致的 $ -1 $ 模組 $ q $ 確切地 $ 50% $ 當時…
考慮 $ (m^{k/2})^2 \pmod n $ . 這是 $ m^{k} \equiv 1 \pmod{n} $ . 但是因為 $ (m^{k/2}) \equiv 1 \pmod{p} $ ， 然後 $ (m^{k/2}) \equiv \pm 1 \pmod{q} $ ，否則它不會平方 $ 1 $ . 論證與上麵類似，表明我們得到每個案例 50% 的時間（因為我們現在保證它不是每次都與 1 一致）。