給定消息和簽名，找到使簽名有效的公鑰
給定消息 $ M $ 和一個簽名 $ S $ , 找到一個 RSA 公鑰是否可行 $ (n,e) $ 這樣 $ S $ 驗證為有效簽名 $ M $ （使用這個公鑰）？
如果我們得到一個公鑰怎麼辦 $ (n,e) $ 簽名驗證的地方（可能是原始簽名者的公鑰），我們想找到第二個公鑰 $ (n’,e’) $ 這也使得 $ S $ 驗證為有效簽名 $ M $ ? 有沒有一種有效的算法來構造這樣的公鑰，如果有，你會怎麼做？（我們可能想要 $ n’ $ 長度相同，以字節為單位，如 $ n $ . 假設 RSA 簽名算法使用適當的填充，例如 PKCS #1。）
實際上，建構這樣一個公鑰似乎是可行的，但需要注意的是：
- 公共指數 $ e $ 會很大。雖然這是合法的，但大多數公鑰都有一個小 $ e $
- 模數可能比通常更容易受到特定（通常不是最佳）分解方法的影響。但是，它的脆弱程度是可以控制的。
（注：我會用 $ N $ 指定模數；我想用 $ n $ 表示“模數內的位數）。
現在，問題可以概括為：給定值 $ S $ 和 $ M $ （和 $ n $ ，這是表示的大小 $ S $ )，找到一個值 $ N $ 和一個值 $ e $ 這樣 $ Pad(M) = S^e \bmod N $ 和 $ S < N < 2^n $
上界的原因 $ N $ 是 RSA 簽名驗證的工作原理；他們期望 $ S $ 是一個與模數長度相同的字節向量；如果我們引入一個大於簽名的模數，驗證過程將失敗，即使數學恰好可以解決。
一種明顯的方法是找到兩個素數 $ p, q $ 和奇數指數 $ e_p, e_q $ 這樣：
- $ Pad(M) \equiv S^{e_p} \bmod p $
- $ Pad(M) \equiv S^{e_q} \bmod q $
- $ S < pq < 2^n $
- 存在一個值 $ e $ 這樣 $ e \equiv e_p \mod p - 1 $ 和 $ e \equiv e_q \mod q-1 $
最後一個是不平凡的條件，因為 $ p-1, q-1 $ 不是相對質數。而且，這以一種明顯的方式推廣到兩個以上的素數；事實證明，兩個素數對我們有用。
現在，如果我們選擇我們的素數 $ p, q $ 首先，我們被困在解決離散日誌問題上 $ e_p, e_q $ . 您可能會認為這很困難；然而，事實證明，如果素數選擇得當，離散對數模以大素數為模很容易；在這種情況下，我們可以選擇素數。
如果 $ p-1 $ 擁有 $ k $ 質因數，其中最大的是 $ r $ ，然後是離散對數問題模 $ p $ 可以解決 $ O(k \sqrt{r}) $ 時間。
我們通過執行以下操作來利用這一點：
- 選擇一組中等大小的素值 $ p_1, p_2, …, p_i $ 併計算 $ p = 2 \prod p_i + 1 $ ，並確保 $ p $ 是素數
- 還要確保 $ Pad(M) $ 和 $ S $ 要麼都是二次餘數，要麼都是二次非餘數模 $ p $ ; 如果它們不同，那麼要麼 $ e_p $ 將不存在，或者甚至會存在，這對我們都不起作用。
- 使用 $ O(k\sqrt{r}) $ 尋找算法 $ e_p $
- 如果 $ e_p $ 恰好是偶數（如果兩者都可能發生 $ Pad(M) $ 和 $ S $ 是二次殘差），然後添加 $ \prod p_i $ 對它；這會使它變得奇怪，並且還會保留關係 $ Pad(M) \equiv S^{e_p} \bmod p $
然後我們執行相同的程序來查找 $ q, e_q $ ，注意我們需要尋找值 $ q $ 大小合適（製作 $ pq $ 在範圍內 $ S < pq < 2^N $ )，並且集合中沒有公共素數 $ p_i $ 和 $ q_i $ ; 這可能會阻止 $ e $ 從現有的。
如果我們按照這些步驟，那麼 $ e $ 將存在，我們已經解決了這個問題。
唯一需要注意的是次貸的規模 $ p_i, q_i $ . 事實證明這有點平衡。如果這些次貸是 $ m $ 位長，那麼上述過程需要大約 $ O(2^{m/2}) $ 時間; 然而，事實證明，Pollard 的 p-1 方法可以將這種形式的模數分解為 $ O(2^m) $ 時間。如果我們擔心有人應用這種特定的分解方法，那麼我們需要選擇 $ m $ 小心。如果我們選擇 $ m=80 $ （也就是說，我們的子質數是 80 位），那麼我們將圍繞 $ 2^{40} $ 計算，這可能處於“可行”的邊緣，而波拉德的方法會採取 $ 2^{80} $ 時間（在我看來，任何人都不太可能投入這種時間）。
$$ revised to better highlight the semi-realistic (2.) where an easy attack might work for $e=3$ by sneaking a forged $N$ of about $368$ bits even if the original modulus is much bigger $$ 似乎可以超越Poncho 的出色答案並製作公鑰 $ (N,e) $ 可以被具有約束的標準實現所接受 $ e $ ; 我將假設一些離散的奇數值在範圍內 $ [3\dots2^{32}] $ . 除了下面的 (1.) 之外，我還將假設 RSASSA-PKCS1-V1_5 的消息填充與PKCS#1中的 SHA-1 一樣： $ \operatorname{Pad}n(M)=2^{8\cdot\lceil n/8\rceil-15}-K+\operatorname{SHA-1}(M) $ 為了 $ n>360 $ ， 和 $ K=2^{288}-2^{160}\cdot3021300906052b0e03021a05000414{16} $ .
問題是：
給定一個或多個簽名 $ S $ ，一條或多條消息 $ M $ （可能取決於 $ S $ ), 允許的整數 $ n $ （也許取決於某些大小的度量 $ S $ ), 允許的整數 $ e $ ，以及如何計算填充消息 $ \operatorname{Pad}_n(M) $ ,
找到可接受的參數 $ (S,M,n,e) $ 和一個奇數 $ N $ 確切地說 $ n $ 位，
這樣 $ N $ 劃分 $ S^e-\operatorname{Pad}_n(M) $ , 和（如果作為簽名驗證的一部分進行檢查） $ N>S $ .
這個問題有多難取決於：
重要的是，在接受簽名之前檢查簽名驗證程序會做什麼 $ S $ 消息的 $ M $ 關於公鑰 $ (N,e) $ ，特別是關於位數 $ n $ 在公共模數中 $ N $ . 這可以是，從最寬鬆的開始：
- 檢查 $ \operatorname{Pad}(M)\equiv S^e\pmod N $ 對於一些獨立的填充 $ n $ . 在這種情況下， $ (N,e)=(5,3) $ 有 20% 的機會成為隨機的解決方案 $ S $ 和留言 $ M $ . 如果這麼小 $ N $ 是允許的，並且有一些自由 $ e $ , 這個問題很簡單，即使是一個人 $ (S,M) $ 對：對手嘗試一些 $ e $ 直到 $ S^e-\operatorname{Pad}(M) $ 有一個（或兩個）小的奇數因子，並使用該因子（或它們的乘積）作為 $ N $ .
- 檢查 $ \operatorname{Pad}_n(M)=S^e\bmod N $ . 注意它暗示 $ N>\operatorname{Pad}_n(M) $ ，但仍然允許對手潛入任何 $ n>360 $ ，而不管原來的公共模數。
- 上述之一，和 $ N>S $ ，這在實踐中將迫使對手使用 $ n $ 幾乎和原來的公共模數一樣大；如果她有 $ i $ 簽名 $ S $ 可供選擇，賠率是最小的 $ S $ 允許降低 $ n $ 在偽造的 $ N $ 大約只有 $ \log_2(i) $ 位與原件相比。這樣的檢查 $ N>S $ 大多數簽名標準（包括 PKCS#1）都強制要求。但是，在通常的設置中 $ N $ 是受信任的，省略該測試不會損害簽名驗證的安全性，並且我已經看到了一個省略它的實現，其理由是：正確的簽名可以從任何允許省略的簽名中輕鬆推導出來。
- 上面的一些，以及檢查 $ n $ 與字節串編碼的大小相比 $ S $ . 這將進一步限制 $ n $ . 例如，PKCS#1 要求 $ S $ 是一個字節串 $ \lceil n/8\rceil $ 字節；然而，一些實現最多將其更改為（可能是因為簽名在某些時候被視為 ASN.1 整數，並且這些會失去它們的前導零位），並且一些實現可能會完全忽略此測試，並根據以下內容決定填充 $ N $ ， 不是 $ S $ .
- 上面的一些，加上一個硬檢查 $ n $ 是一組固定的值。這是某些標準強制要求的，例如FIPS 186-3，它只允許 $ n\in{1024,2048,3072} $ ; 與 (3.) 或 (4.) 結合使用，迫使對手完全使用原始版本 $ n $ .
如果對手有大量供應 $ S $ （我假設她滿足於一個人的成功 $ S $ )，或/和大量供應 $ M $ （問題沒有考慮到這一點，但在某些實際情況下，對手完全有可能在許多消息中自由選擇 $ M $ 適合她的目標，獨立於簽名 $ S $ ).
關於什麼價值觀 $ e $ 是允許的。
除了在 (1.) 中，尋找除數的問題 $ n $ 巨大的比特 $ S^e-\operatorname{Pad}_n(M) $ 是不平凡的。主要取決於允許的 $ n $ 鑑於所執行的檢查，它可能仍然易於處理，如下所示：
- 進行部分因式分解 $ S^e-\operatorname{Pad}_n(M) $ 對於一些允許的參數 $ (S,M,n,e) $ , 使用經過精心打磨的分解技術庫，適用於約 $ \max(e\cdot||S||,||\operatorname{Pad}_n(M)||) $ 位（試用除法，然後是波拉德的 rho，然後是波拉德的 p-1，然後可能是波拉德的 p+1，然後是ECM ，如果剩餘的複合因子有幾百位，則可能是MPQS或GNFS的某種變體），如 $ S^e-\operatorname{Pad}_n(M)=2^i\cdot\prod p_j\cdot\prod c_j $ , 其中 $ p_j $ 是奇數小於 $ 2^n $ , 和 $ c_j $ 是更高的因素。通常情況下 $ c_j $ （如果有的話）要麼是一個單一的巨大的複合材料，它的成本太高而無法分解，要麼是一個巨大的素數；和 $ p_j $ 是低到中等大小的素數，除了最高的 $ p_j $ 當沒有 $ c_j $ （在這種情況下，最高 $ p_j $ 可以是複合的，和/或方法 $ n $ 位）。
- 嘗試找到其中的一個子集 $ p_i $ 這樣 $ n-1<\sum log_2(p_i)<n $ 近似計算（變化 $ n-1 $ 到 $ \log_2(S) $ 如果 $ N>S $ 是一項要求，我們使用 $ S $ 和 $ S\ge2^{n-1} $ ）。這是一個特別鬆散的背包問題，而且通常很容易解決 $ \sum log_2(p_i) $ 甚至略過 $ n $ （小因素作為調整變數）。如果無法做到這一點，請轉到另一位候選人 $ (S,M,n,e) $ .
- 放 $ N=\prod p_i $ 對於那些 $ p_i $ 在所展示的背包子集中。在不太可能的情況下 $ N $ 由於舍入誤差而不能接受，轉移到另一個背包解決方案，或另一個候選 $ (S,M,n,e) $ .
最好的 $ n $ 考慮到我們提供的簽名驗證程序允許的情況，是最低允許的 $ S $ 和 $ M $ .
很大的自由度 $ M $ 和/或有一個池 $ S $ 從中選擇有很大幫助，因為它允許將大部分保理工作集中在少數幾個 $ S^e-\operatorname{Pad}_n(M) $ 其中有很多小的奇怪因素，這使得其他的更少 $ p_j $ 通過更複雜的方法找到，進一步使背包的微調變得相當容易。
有充足的貨源 $ (S,M) $ 攻擊很容易 $ n\in[361\dots368] $ . 我不會賭到什麼 $ n $ 它可能真的有效。然而，GMP-ECM通常用於發現>10000 位數字的 >200 位因子，這似乎是正確的 $ n=768 $ ，也許更多。可行性與隨機 $ m $ -bit 整數至少有一個 $ n $ - 位除數，最多包含所有因數 $ k $ 位，我在這裡問過。
$ e=3 $ 提供最易於管理的 $ S^e-\operatorname{Pad}_n(M) $ ，並且似乎並沒有顯著減少 $ p_i $ 從中選擇。 $ e=2^{16}+1 $ 很煩人，但似乎並非不可克服，特別是如果實現的檢查允許 $ n\in[361\dots368] $ .
我故意沒有做任何檢查 $ \gcd(p_i-1,e)=1 $ ， 或者那個 $ p_i $ 至少是一些界限，所以 $ N $ 不是平凡可分解的，或者 $ N $ 是複合的；對於 RSA 簽名驗證的通常實現，不要檢查任何這些。
該問題可能有實際應用。這是一個合理的研究案例，對手在 $ M $ . 合法使用者下載了一個文件，它的分離簽名（可能包括通過標識符引用公鑰，但不包括雜湊），並擁有真正的公鑰。攻擊者獲得對文件、公鑰的寫訪問權，但不能獲得簽名（合法使用者防寫的簽名）。
攻擊將允許攻擊者修改文件，同時在檢查簽名時保持明顯的完整性。請注意，通過修改偽造文件的結尾，攻擊者有一種廉價的方式來改變 $ \operatorname{Pad}_n(M) $ （只需要重新計算雜湊的末尾）。