如何正確使用 RSA 進行散列數字簽名？

我正在嘗試了解RSA 數字簽名算法。我計劃按照以下步驟操作：

簽名算法：

1. 取一些消息 $ m $
2. 使用我的私鑰創建數字簽名 $ [d,n] $ : $ s = S_a(m) = m^d \bmod n $
3. 傳遞我的資訊和簽名 $ [m,s] $

驗證算法：

1. 接受 $ [m,s] $
2. 獲取公鑰 $ [e,n] $
3. 檢索消息： $ m’ = P_a(s) = s^e \bmod n $
4. 通過比較檢查簽名的真實性和消息的不變性 $ m $ 和 $ m’ $

---

但我也想使用hashing。我打算簽署而不是消息 $ m $ ，但它的雜湊： $ m_{\rm hashed} $ . 符號算法可能會更改為：

符號算法（帶散列）：

1. 取一些消息 $ m $
2. 生成消息雜湊： $ m_{\rm hashed} $
3. 使用我的私鑰創建數字簽名 $ [d,n] $ : $ s = S_a(m_{\rm hashed}) = m_{\rm hashed}^d \bmod n $
4. 傳遞我的資訊和簽名 $ [m,s] $

我對驗證步驟有疑問。特別是關於在步驟 4 中檢查消息的真實性。

驗證算法（帶散列）：

1. 接受 $ [m,s] $
2. 獲取公鑰 $ [e,n] $
3. 檢索消息： $ m’ = P_a(s) = s^e \bmod n $
4. 通過比較檢查簽名的真實性和消息的不變性 $ m $ 和 $ m’ $ ???

在使用散列之前，我們可以通過比較來檢查真實性和不變性 $ m $ 和 $ m’ $ . 但是在這種情況下，在第 3 步之後，我們會得到 $ m’ $ 作為散列版本（不是原始消息）。我們如何比較 $ m $ 和 $ m’ $ 如果 $ m $ 是原始消息並且 $ m’ $ 是散列版本（考慮到散列是不可逆的並且沒有辦法將散列解密回來）？

---

**我的問題：**什麼是正確的算法？如何正確使用 RSA 進行散列數字簽名？

你錯過了兩件事：

首先，我們不嘗試從雜湊中檢索消息；正如您正確指出的那樣，這是不可能的。相反，我們所做的是（使用您的符號）：

1. 接受 $ [m,s] $
2. 獲取公鑰 $ [e,n] $
3. 檢索散列消息： $ m’_{hashed} = P_a(s) = s^e \bmod(n) $
4. 生成正在驗證的消息的雜湊值 $ m_{hashed} = Hash(m) $
5. 通過比較檢查簽名的真實性和消息的不變性 $ m_{hashed} $ 和 $ m’_{hashed} $

如果我們假設雜湊函式是抗碰撞的，也就是說，找到兩個不同的消息是不可行的 $ M_a, M_b $ 和 $ Hash(M_a) = Hash(M_b) $ , 那麼如果 $ m_{hashed} = m’_{hashed} $ ，那麼要麼我們已經證明了雜湊衝突（我們假設這很困難），要麼 $ m = m’ $ .

您缺少的另一件事是填充。我們（不應該）從不獲取雜湊函式的輸出，將其解釋為整數，然後將其交給 RSA 函式；如果我們這樣做，那麼攻擊者可能會利用 RSA 的同態屬性，即， $ a^e \bmod n \times b^e \bmod n \equiv (ab)^e \bmod n $ ，通過一堆簽名查找恰好具有公因數的雜湊，然後將簽名拼湊到一條新消息（其雜湊由這些公因數組成）。相反，我們總是對雜湊輸出應用一個填充函式，以將其變成一個大的（幾乎與 $ n $ ) 整數，然後對其應用 RSA 函式。

有許多已知的填充方法被認為是安全的，包括PSS 和 RSASSA-PKCS1-v1_5；我給你的參考資料讓你開始。

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