從三個不同的公鑰解密 RSA 加密消息
我有三個具有共同指數的不同 1024 位公鑰 $ e $ 但不同的模數。一個消息 $ m $ 使用三個密鑰加密（無填充），從而產生三個不同的加密消息。
給定三對公鑰 $ (N_i,e) $ 和加密的消息 $ c_i=m^e\bmod N_i $ ，我如何破譯原始消息 $ m $ ?
在該問題中，使用教科書 RSA將同一消息直接加密為三個不同的公鑰。這會產生可怕的後果，包括以下情況（1./2./3. 不使用多個公鑰，答案可能在 5. 或其副檔名 6. 中想到）：
- 它嚴重限制了消息的大小（小於 128 個八位字節）。
- 任何擁有公鑰的人都可以檢查消息的猜測 $ (N_i,e) $ 和密文 $ c_i $ ，根據密碼學的標准假設，其中包括對手。他們只是加密了一個猜測 $ m $ 和 $ (N_i,e) $ 並檢查它 $ c_i $ . 如果消息是班級名冊上的一個名字，一個可猜測的密碼，Poof 會保密。
- 如果 $ m $ 不到說 $ 2^{70} $ , 很有可能退出 $ r<2^{30} $ 和 $ s<2^{40} $ 和 $ m=r\cdot s $ . 這種情況下，不管 $ e $ ，中間相遇攻擊正在恢復 $ m $ : 攻擊者計算 $ c_0/r^e\bmod N_0 $ 對於所有候選人 $ r $ 並將其儲存以進行快速搜尋（10 GiB 的 RAM 用於雜湊表，128 GiB 的很少使用的磁碟就可以了）；然後對於每個候選人 $ s $ 計算 $ s^e\bmod N_0 $ 並蒐索；有比賽， $ m $ 被發現為 $ r\cdot s $ .
- 如果 $ e $ 很小，和/或消息 $ m $ 足夠小（小於約 $ 2^{1023/e} $ ）， 然後 $ m=\sqrt[e]{c_i} $ （在哪裡 $ i $ 是最大的索引 $ N_i $ 它是直接使用的，而不是模運算）。儘管 $ c_i $ 是不同的，這種攻擊仍然可以在手頭的情況下起作用，當 $ m $ 足夠接近極限 $ \sqrt[e]{\max(N_i)} $ . 此外，根攻擊可以很容易地擴展到類似 $ m<2^{1060/e} $ ，以及更多當我們考慮多重加密時，請參見 6。
- 如果 $ e=3 $ ，系統很容易受到典型的RSA 廣播攻擊（也是Håstad 廣播攻擊的最簡單形式）。 $ e=3 $ 是教科書 RSA 中的常見選擇，因為它允許最快的加密，使用模平方和一個模乘；並且盡可能安全 $ m $ 在一個區間內基本上是隨機的 $ [0,N_i) $ 並為每個加密獨立選擇（與手頭相同的情況相反 $ m $ 用了三次）。
我們應該首先檢查這三個 $ \gcd(N_i,N_j)=1 $ 為了 $ 0\le i<j<3 $ . 否則，GCD 是一個不平凡的因素 $ N_i $ 和 $ N_j $ , 我們已經考慮了 $ N_i $ 和 $ N_j $ （至少在兩個因素 RSA 中），並且可以按照教科書 RSA 中的正常方式計算一個有效的私有指數和解密。以這種方式成功是不應該發生的，但是由於隨機數生成器不正確，並且在不同平台上給出了相同的結果，但在不應該發生的情況下，會在這里和那裡取得成功；並在學術練習中。
如此檢查（或盲目假設）我們可以呼叫中國剩餘定理，我們用它來解決 $ x $ 3個方程組 $ x\equiv c_i\pmod{N_i} $ 為了 $ 0\le i<3 $ 和 $ x\in[0,\prod N_i) $ . 這些都不在了：
- $ x\gets c_0 $
- $ N\gets N_0 $
- 對於每個 $ i $ 和 $ 1\le i<3 $
- $ x\gets(((N^{-1}\bmod N_i)\cdot(c_i-x))\bmod N_i)\cdot N+x $
- $ N\gets N\cdot N_i $
- 在那時候 $ N=\prod N_i $ ， 和 $ x $ 是所需的解決方案。然後我們計算 $ m=\sqrt[3]x $ （這將是一個精確的整數）；這是一個非模立方根，因此很容易。這將始終有效，因為 $ m<\min(N_i) $ ， 因此 $ m^3<N $ ， 因此 $ m^3=x $ 因為通過 CRT，沒有其他的 $ m $ 和 $ m^3\equiv c_i\pmod{N_i} $ .
- 攻擊 4. 和 5. 結合起來，對某些人有效 $ e>3 $ . 如果 $ m<\sqrt[e]{\prod N_i} $ ，然後經過計算 $ x $ 就像上面一樣 $ m=\sqrt[e]x $ （這將是一個精確的整數）。
這可以擴展到 $ m $ 高達約 $ (3072+k)/e $ -bit with with $ O(2^k) $ 工作; 和 $ e=5 $ 也許 $ m $ 取決於 $ \approx78 $ 字節（超出最大容量 $ <128 $ 字節）。一個想法是掃描整數 $ r $ 和 $ 0\le r<2^k $ ， 直到 $ \sqrt[e]{r\cdot N+x} $ 是一個精確的整數。
此外，我們可以通過重用 $ \sqrt[e]{r\cdot N+x} $ 為了測試是否 $ \sqrt[e]{(r+1)\cdot N+x} $ 是一個整數，併計算一個近似值 $ \sqrt[e]{(r+1)\cdot N+x} $ .
也許這種攻擊會變得更好；看到這個答案，想知道通過將 Coppersmith 定理與晶格方法相結合來擴展e th根攻擊。
結論：