e=65537 時教科書 RSA 簽名偽造
搜尋 RSA 簽名偽造我遇到了這個問題。答案中指出
適用於中小型 $ e $ （包含 $ e=3 $ 和 $ e=2^{16}+1 $ ，通常在實踐中使用），可以偽造一大類消息，包括顯示為任何所需的 C 字元串。對於任何 $ m_0 $ , 很容易展示 $ m_1 $ 這樣 $ m=m_0||m_1 $ 是已知整數的（非模）e 次方 $ \sigma $ （計算 $ \sigma=⌈\sqrt[e]{m_0 2^{2e|N|}}⌉ $ 和 $ m_1 = \sigma^e − m_0 2^{2e|n|} $ 大小的 $ 2e|N| $ 少量）; 這個 $ \sigma $ 驗證為簽名 $ m $ ; 和 $ m $ 列印相同 $ m_0 $ 如果 $ m_0 $ 是一個以零結尾的 C 字元串。
實際上，我很難看到它是如何工作的 $ e = 2^{16}+1 $ . 我會這樣說 $ \sigma $ 很可能會大於模數 $ N $ 在這種情況下，減少將使一切崩潰。
是否應該有條件
$ m_1 = \sigma^e − m_0 2^{2e|n|} $ 大小的 $ 2e|N| $ 少量
因此偽造品適用於 $ e = 2^{16}+1 $ 但只有非常大的模數而不是標準的 1024-/2048-/4096 位模數？
任何人都可以對此有所了解嗎？
非常感謝
引用的答案是關於一個問題
為了驗證，接收方檢查 $ \sigma^e \equiv m \pmod N $ . （……）
鑑於 $ m \pmod N $ 但一個未知數 $ m $ (…)
因此在上下文中它不一定成立 $ 0\le m<N $ 就像在原始文章的教科書 RSA 簽名方案中一樣。相反，該問題考慮了一個假設的簽名系統，其中 $ m $ 可以大於 $ N $ ，並且該消息被簽署為附錄 $ \sigma\gets m^d\bmod N $ ，獨立於消息發送。
對於此設置，舊答案中的攻擊線非常複雜。這是一個更簡單的攻擊，適用於任何 $ e $ ，並且如果接收方檢查 $ 0\le\sigma<N $ 除了問題的 $ \sigma^e \equiv m \pmod N $ .
攻擊者
- 選擇 $ \sigma $ 自由地在 $ [0,N) $ ， 包含 $ 0 $ ， 和 $ 1 $ 和 $ N-1 $ 這將簡化計算。
- 決定 $ m_0 $ ，例如以 0x00 字節作為結尾 $ C $ 字元串終止符
- 如果 $ N $ 是 $ n $ -bit，決定 $ m_1 $ [對我來說附加到 $ m_0 $ 成型 $ m=m_0\mathbin|m_1 $ ] 將是一個位串 $ b=8\lceil n/8\rceil $ 少量
- 計算 $ m\gets m_0,2^b+((\sigma^e-m_0,2^b)\bmod N) $ .
我將舉一個例子 $ N= $ RSA-2048 , $ e=2^{16}+1 $ , $ \sigma=3^{1291} $ ， 資訊 $ m $ 以 ASCII 格式列印為 15 字節
A test message.。線上嘗試！.也就是說，舊的答案是虛假的，我修復了它；現在的問題是正確的 $ 0\le m<N $ （在教科書 RSA 中很常見），對於非常小的攻擊是可能的 $ e $ 喜歡 $ e=3 $ 但失敗了 $ e=65537 $ 和通常的大小 $ N $ .