偽造拉賓簽名
如果攻擊者擁有公鑰並擁有一些消息對，那麼為實現具有完全消息恢復的 Rabin 簽名的系統偽造簽名的機會是什麼？要簽名的消息的最後一個字節是可以自由更改的。攻擊者無權簽署預言機。
我將假設一個系統如下
- $ N=p,q $ 是兩個大的秘密素數的公共乘積，大約均勻隨機且獨立地選擇，因此是不同的（具有壓倒性的可能性）。這樣的 $ N $ 被認為很難考慮。
- 簽名者選擇了有意義的消息 $ m $ 獨立於 $ p $ 和 $ q $ , 表示為驗證小於的非負整數 $ N/256 $ ，並且有些發現 $ k\in[0,255] $ 和 $ c\in[0,N) $ 以便 $ 256m+k=c^2\bmod N $ （有四個這樣的 $ c $ 為了 $ s\approx64 $ 的值 $ k $ ， 和不 $ c $ 為他人 $ k $ ，機率很高）。
- 驗證者收到被指控的 $ c $ 計算 $ m=\lfloor(c^2\bmod N)/256\rfloor $ ，並相信該消息是否有意義。
偽造簽名的機會在很大程度上取決於驗證者認為什麼“有意義”。例如，對手可以設置 $ c=37152 $ , 產生 $ c^2=1380271104=\mathtt{52454400_h} $ , $ m $ 是 $ \mathtt{524544_h} $ , 在 ASCII 中是
RED. 相似地， $ c=33360 $ 產量BUY。我們不能為許多英語單詞使用這個技巧，但這算作偽造，除非我們更好地定義“有意義”。而對於大 $ N $ ，如果“有意義”意味著低位字節 $ c^2\bmod N $ 設置為零以創建終止字元，並且整個內容作為第一個參數傳遞給puts用於顯示，並且必須是精確指定的東西，偽造任何所需的大小約為一半大小仍然是微不足道的 $ N $ . 對於 2048 位，它可以位於任何 127 字節字元串旁邊 $ N $ （這些天推薦的最低最小值）。更新：我們了解到“有意義的字節 $ m $ （是）通過（a）校驗和“耦合在一起”未指定大小。偽造可以通過嘗試各種 $ c $ 直到找到一個這樣的 $ c^2\bmod N $ 通過校驗和檢查。預期試驗次數為 $ 2^s $ （對於最佳校驗和），其中 $ s $ 是校驗和中的位數。對於高達 32 位的校驗和，我們說的是電腦時間的大多數秒。沒有什麼可以強迫我們擁有 $ c>\sqrt N $ ，因此我們可以在不使用的情況下進行攻擊 $ N $ 或範例消息。增加的 $ c $ 會做，因此通過溫和的優化，成本主要由校驗和的計算決定，至少在沒有其他約束的情況下 $ m $ 超出校驗和。即使有這樣的額外約束，仍然可以選擇偽造消息的許多字節而不會增加搜尋成本。高階的特別有延展性：我們選擇 $ c $ 這樣它的平方的高字節就可以了，只需要計算一個平方根。