RSA 1024 位從所選消息中偽造新的匹配簽名
我有一個 1024 位密鑰的 RSA 簽名方案，我知道以下內容：
- 公共模數 $ N $
- 公共指數 $ e=3 $
- 很多簽名
概括：
為了計算簽名，MD5 散列是從字節集合中計算出來的，然後將教科書的 RSA 私鑰函式應用於該函式。簽名的驗證程序 $ S $ 是檢查 $ S^e\bmod N $ 是指稱消息的 MD5 雜湊值。
我們的老師給了我們不止一個簽名。
問題：
有人可以提供建議以找到一種實用的方法來從所選消息中找到新的匹配簽名嗎？
我們假設一個帶有附錄的 RSA 簽名方案，其中消息的簽名 $ M $ 是 $ S=\left(\operatorname{MD5}(M)\right)^d\bmod N $ ，並且驗證程序檢查 $ 0\le S<N $ 和 $ \left(S^e\bmod N\right)=\operatorname{MD5}(M) $ ， 和 $ e=3 $ （或其他相對較小的奇數 $ e\ge3 $ ）。夏娃有點得到 $ k $ 合法簽名 $ S_i $ 或許還有相應的消息 $ M_i $ （夏娃無法影響）。夏娃想建造另一個 $ M $ , 和匹配的簽名 $ S $ .
夏娃將進行乘法偽造：她會找到一條消息 $ M $ 和一組匹配的 $ k $ 非負整數 $ e_i $ , 這樣 $ \operatorname{MD5}(M)\cdot\prod\left(\operatorname{MD5}(M_i)\right)^{e_i} $ 是一個 $ e $ 次方，然後計算簽名 $ M $ 作為
$$ S=\left(\sqrt[e]{\operatorname{MD5}(M)\cdot\prod\left(\operatorname{MD5}(M_i)\right)^{e_i}}\right)\cdot\left(\prod S_i^{e_i}\right)^{-1}\bmod N $$ 驗證 $ \left(S^e\bmod N\right)=\operatorname{MD5}(M) $ . 定義 $ m_{i,j} $ 作為素數的多重性 $ p_j $ 在因式分解中 $ \operatorname{MD5}(M_i) $ , 並定義 $ m_j $ 作為素數的多重性 $ p_j $ 在因式分解中 $ \operatorname{MD5}(M) $ . 愛麗絲的目標是 $ \forall j,; m_j+\sum_i m_{i,j}\cdot e_i\equiv0\pmod e $ . 具有未知數的線性方程組 $ e_i $ 相當於 $ \operatorname{MD5}(M)\cdot\prod\left(\operatorname{MD5}(M_i)\right)^{e_i} $ 作為一個 $ e $ 權力。
Eve 計算雜湊值 $ H_i=\operatorname{MD5}(M_i) $ , 直接或作為 $ S_i^e\bmod N $ . 她考慮到 $ H_i $ 至少部分（與 $ H_i<2^{128} $ ，甚至完全分解也是可行的）。她可以無視任何 $ H_i $ 有一個主要因素 $ p_j $ 沒有出現在其他 $ H_i $
$$ and $m_{i,j}\not\equiv0\pmod e$, but that is likely for $k$ large enough to carry the attack $$; 特別是她可以毫不猶豫地忽略那些 $ H_i $ 質因數大於約 $ k^3/\log(k) $ ，這不太可能有任何幫助。 其餘大綱：夏娃反复
- 選擇一條消息 $ M $ 她的選擇$$ that she did not previously select, and distinct from the $M_i$ if these are given $$
- 計算 $ \operatorname{MD5}(M) $ 並至少部分考慮它
- 如果該因式分解完全由出現在至少一個因式分解中的素數組成 $ H_i $ 保留$$ in that screening Eve could exclude primes with multiplicity $m_j\equiv0\pmod e$ in the factorization of $\operatorname{MD5}(M)$, and occurrences with multiplicity $m_{i,j}\equiv0\pmod e$ in the $H_i$, but that won’t make much of a difference for $k$ large enough to carry the attack $$
嘗試求解線性系統，如果可行
- 計算 $ S $ ，注意到 $ e $ th根提取簡化為將指數除以 $ e $ 在已知的因式分解中 $ \operatorname{MD5}(M)\cdot\prod\left(\operatorname{MD5}(M_i)\right)^{e_i} $
- 輸出 $ M $ 和 $ S $ .
這將有助於對線性方程組進行預處理。對於較大的 $ k $ , 求解線性系統將成功 $ M $ 通過篩選；或/並且可以設置 $ p_j $ 早期，使分解更容易，線性系統更小，因此更容易管理。
一個小的 $ e $ 有助於攻擊，但足夠大 $ k $ 它可以攜帶任何 $ e $ . 公共模數的大小 $ N $ RSA 密鑰本質上是無關緊要的；最重要的是散列的寬度，它在 128 位是嚴重不足的。
問題的一個稍微簡單的變體（選擇所有消息，這對於沒有抗碰撞性的雜湊沒有實際意義 $ \operatorname{MD5} $ 是現在）由 Jean-Sébastien Coron、David Naccache 和 Julien P. Stern 在第 2 節中討論：關於 RSA 填充的安全性（在Crypto 1999 的程序中）；或者，當我們設置 $ \mu $ 至 $ \operatorname{MD5} $ ，作者：Don Coppersmith、Jean-Sébastien Coron、François Grieu、Shai Halevi、Charanjit Jutla、David Naccache 和 Julien P. Stern 在第 3 節：ISO/IEC 9796-1的密碼分析（密碼學雜誌，2008 年）。Yvo Desmedt 和 Andrew M. Odlyzko 在A selected text attack on the RSA 密碼系統和一些離散對數方案（在Crypto 1985 的論文集）中介紹了通過求解基於素數多重性的線性系統來建構係數的想法。