數字簽名偽造
我對數字簽名的理解如下： Alice 用單向加密雜湊函式對消息進行雜湊處理，其輸出稱為消息摘要。然後她用她的私鑰對摘要進行加密，然後將原始的未散列/未加密消息與加密的散列版本（即數字簽名）一起發送給 Bob。Bob 對消息使用相同的散列函式，並使用 Alice 的公鑰解密數字簽名。如果雜湊匹配 Bob 可以確定他正在與 Alice 通信。
如果他包含愛麗絲的公鑰，黑客就不可能偽造愛麗絲的簽名嗎？難道他不能選擇一個數字簽名，這樣當用 Alice 的公鑰解密它時，它會返回與他的偽造消息相同的雜湊值，因為他同時控制了消息和簽名？
符號表示：設數字簽名為s，消息為m，Alice的公鑰為pk，驗證函式為verify，散列函式為hash。
黑客選擇 m 和 s 使得 hash(m) == verify(s, pk)
TLDR：所考慮的攻擊並不容易。有沒有可能，取決於未陳述的假設。
首先，我們將重新表述問題¹。
我們假設一個非對稱加密系統，類似於教科書 RSA，具有
- 公鑰/私鑰對的密鑰生成 $ (\mathrm{pk},\mathrm{sk}) $ ,
- 加密 $ c:=E_\mathrm{pk}(p) $ 在哪裡 $ p $ 是明文， $ c $ 是密文
- 匹配解密 $ p:=D_\mathrm{sk}(c) $ 適合所有人 $ c $ 獲得為 $ E_\mathrm{pk}(p) $
- 在哪裡 $ p $ 和 $ c $ 來自一個共同的區間 $ [0,n) $ ， 和 $ n $ 嵌入 $ \mathrm{pk} $ 和 $ \mathrm{sk} $ .
我們假設這個加密系統在已知的明文攻擊下是安全的。
我們假設一個理想的散列函式 $ \operatorname{Hash} $ 輸出在 $ [0,h) $ ， 和 $ h\le n $ 對所有人 $ (\mathrm{pk},\mathrm{sk}) $ 加密系統生成。
我們推導出一個數字簽名方案，其中
- 密鑰生成與加密一樣
- 消息的簽名 $ m $ 是 $ s=D_\mathrm{sk}(\operatorname{Hash}(m)) $
- 驗證程序 $ \mathrm{Vrfy}\mathrm{pk}(m,s) $ 輸出通過如果 $ \operatorname{Hash}(m)=E\mathrm{pk}(s) $ ，否則失敗。
我強調這不是建構簽名的常用方法：沒有廣泛使用的簽名方案完全匹配²，並且許多像 DSA、ECDSA、EdDSA 非常不同。
問題詢問黑客是否可以選擇 $ m $ 和 $ s $ 這樣 $ \mathrm{Vrfy}\mathrm{pk}(m,s) $ 輸出Pass，就是這樣 $ \operatorname{Hash}(m)=E\mathrm{pk}(s) $ .
好消息：當消息和簽名不變時，簽名系統驗證成功。參數：自加密的輸入輸出集 $ E_\mathrm{pk} $ 都是一樣的，還有解密功能 $ D_\mathrm{sk} $ 反轉 $ E_\mathrm{pk} $ 對所有人 $ p $ ， 兩個都 $ E_\mathrm{pk} $ 和 $ D_\mathrm{sk} $ 是該集合的排列，一個是另一個的逆。因此對於所有人 $ c $ 在它持有的那個集合中 $ E_\mathrm{pk}(D_\mathrm{sk}(c))=c $ . 應用這個 $ c=\operatorname{Hash}(m) $ ，其中條件 $ h\le n $ 使所有人成為可能 $ m $ ，我們明白了 $ E_\mathrm{pk}(s)=E_\mathrm{pk}(D_\mathrm{sk}(\operatorname{Hash}(m)))=\operatorname{Hash}(m) $ ， 所以 $ \mathrm{Vrfy}_\mathrm{pk}(m,s) $ 輸出通過。
更多好消息：對手持有 $ \mathrm{pk} $ 選擇 $ m $ 和 $ s $ 這樣 $ \operatorname{Hash}(m)=E_\mathrm{pk}(s) $ . 似乎沒有什麼簡單的方法起作用：
- 當對手首先選擇任意 $ m $ , 併計算 $ c=\operatorname{Hash}(m) $ ， 那 $ c $ 是隨機的，除了在較低的子集中 $ [0,h) $ 的 $ [0,n) $ . 當他們下次嘗試尋找 $ s $ 和 $ c=E_\mathrm{pk}(s) $ ，他們本質上面臨著解密任意密文的問題，這很難（可以證明，在我們對密文所做的 KPA 假設下，解密任意密文一定很困難）。
- 當對手首先選擇任意 $ s $ 併計算 $ E_\mathrm{pk}(s) $ , 他們得到一個任意值 $ c $ 在 $ [0,n) $ . 沒有這樣的保險 $ c $ 在範圍內 $ [0,h) $ （如果不是，它不能是任何消息的雜湊 $ m $ ）。即使對手可以通過選擇來繞過這個障礙 $ s $ 以便 $ c $ 在範圍內 $ [0,h) $ （教科書 RSA 允許，例如通過製作 $ s=0 $ 或者 $ s=1 $ )，理想的散列函式在計算上很難找到 $ m $ 散列到任意給定值 $ c $ 在雜湊的輸出範圍內：這是雜湊的第一個原像電阻。
- 當對手抓住一個 $ (m,s) $ 通過驗證的配對，他們可以嘗試找到 $ m’ $ 以外 $ m $ 和 $ \operatorname{Hash}(m’)=\operatorname{Hash}(m) $ ，這將確保 $ (m’,s) $ 通過驗證。但是理想的散列函式在計算上很難做到這一點：這是散列的第二個原像阻力。
- 對手可能會嘗試製作兩種不同的資訊 $ m $ 和 $ m’ $ 和 $ \operatorname{Hash}(m)=\operatorname{Hash}(m’) $ , 獲得簽名 $ s $ 的 $ m $ ，因此會偽造另一個 $ (m’,s) $ 通過驗證。這比以前的攻擊要容易得多（例如，使用 SHA-1 作為 $ \operatorname{Hash} $ ，當先前的攻擊都不可行時），但理想的散列函式仍然是這樣的，它在計算上很難做到這一點：這就是散列的抗碰撞性。
以上不構成有效的安全證明，更糟糕的是：得出簽名系統安全的結論顯然是錯誤的。特別是，與 $ h=2^{256} $ （例如散列是 SHA-256）並且當加密系統是教科書 RSA 時，這個簽名系統很容易受到可以想像的偽造。假設有優惠券的系統 $ m $ 形式
Coupon worth $123,456.78, reference 4C0D5F62CAF6AF32假設簽名者檢查一個提議的 $ m $ 是格式良好的優惠券，其參考是唯一的，獲得所示價格的付款，並在這些條件下標誌 $ m $ . Desmedt和 Odlyzko 攻擊讓攻擊者通過購買低價值優惠券的簽名並使用這些簽名找到高價值優惠券的簽名來博弈該系統。
更好的消息：通過一些額外的假設，可以證明這個簽名系統是安全的。一個適用於 RSA 的假設是 $ h $ 有幾乎一樣多的位 $ n $ . 這個簽名系統被稱為全域雜湊。證明很困難，以至於當 Mihir Bellare 和 Peter Rogaway 首次考慮 FDH：數字簽名的精確安全性 - 如何使用 RSA 和 Rabin 簽名時，在Eurocrypt 1996 的程序中，他們無法證明令人滿意的安全級別（並設計了一個更複雜的簽名系統：RSA-PSS，這是廣泛使用的RSASSA-PSS的基礎）。幾年後，讓-塞巴斯蒂安·科隆（Jean-Sébastien Coron）獲得了更好的安全級別：On the Exact Security of Full Domain Hash，在Crypto 2000 的程序中（但 RSA 簽名已經穩定，FDH 並未廣泛使用）。
¹ 與問題表述的主要區別：
- 我們使用解密而不是加密進行簽名，因為使用私鑰加密並且能夠使用公鑰解密與加密的目標相矛盾。即使我們刪除填充步驟，它在實踐中也不起作用，包括實現的 RSA：公鑰的格式是 $ (n,e) $ 通常有大小限制 $ e $ , 私鑰的格式為 $ (n,e,d,p,q,d_p,d_q,q_\text{inv}) $ ，並試圖將公鑰推到預期私鑰的位置，反之亦然，將失敗。
- 我們指定一個與明文集大小相同的密文有限集，因此是確定性加密，否則簽名生成或驗證有時會在正常使用下失敗。
- 我們將消息作為驗證過程的輸入，因為這就是簽名在理論和現代實際實現中的定義方式。
² RSASSA-PKCS1-v1_5是我所知道的唯一一個接近的，但它是 $ \operatorname{Hash} $ 是通過根據位大小連接前綴來構造的 $ n $ 和 $ H(m) $ ， 在哪裡 $ H $ 是標準雜湊值，例如 SHA-256，因此 $ \operatorname{Hash} $ 不是一個理想的散列函式，因為它預計在它的輸出域上看起來像隨機一樣。