1024 RSA 雜湊簽名攻擊。偽造有效簽名

我有一個 1024 位的 RSA 簽名，我知道以下內容：

1. 公共模數 N
2. 公共指數 (0x03)
3. 密碼消息

概括：

MD5 雜湊是從字節集合中計算出來的，並用作消息 (M)。

擁有一個完美立方體的散列來偽造一個被接受為有效的簽名將很容易。

問題：

有人可以提供建議以找到一種實用的方法來散列消息更改結束直到他們的散列將是一個完美的立方體？

一個隨機的 128 位值有一個很小的 ( $ 2^{-85} $ ) 成為完美立方體的機率，因此這看起來不是一種可行的方法。而且，您無法控制 MD5 的輸出，因此它會為您提供有效的隨機值。

更好的方法可能是收集大量簽名（連同他們的消息）；那是， $ S_i = M_i^3 \bmod N $ 值（其中 $ M_i $ 是 MD5 雜湊 $ i $ 消息）。然後，你會考慮每個 $ M_i $ , 並尋找公因子的線性組合。同時，你會散列大量消息，並尋找帶有 MD5 散列的消息 $ M $ 可以用簽名消息的線性組合來表示 $ M = M_a^{i_a} M_b^{i_b} … M_z^{i_z} $ . 當您找到這樣的線性組合時，您就擁有了該消息的簽名 $ S = S_a^{i_a}S_b^{i_b} … S_z^{i_z} $

引用自：https://crypto.stackexchange.com/questions/29088