數位簽章能證明「與某個數位簽章綁定之私鑰的持有者簽署了某則訊息」，且該簽章是真的。

由於除了私鑰持有者之外沒人知道私有指數 d，沒人能從某個值 x 算出簽章 y = x^d mod n；但任何人都能用公開指數 e 驗證 y^e mod n = x。

經驗證的簽章可以在法庭上用來證明私鑰持有者確實簽署了某則特定訊息——這個不可抵賴的性質稱為不可否認性（nonrepudiation）。

簽章不是「用私鑰加密」#

把 RSA 簽章看成加密的反向操作很誘人，但它們並不是。用 RSA 簽章與用私鑰加密不是同一回事。

  • 加密提供機密性。
  • 數位簽章用來防止偽造。

最明顯的差別是：簽章方案洩漏被簽訊息的資訊是可以接受的，因為訊息本來就不是秘密。例如一個會揭露部分訊息的方案可以是安全的簽章方案，卻不會是安全的加密方案。

另一個差別：

  • 由於處理開銷，公鑰加密只能處理短訊息（通常是秘密金鑰而非實際訊息）。
  • 簽章方案可以處理任意大小的訊息，做法是用訊息的雜湊值 Hash(M) 作為代理，而且它可以是確定性的卻仍然安全。

教科書 RSA 簽章為何不安全#

教科書 RSA 簽章是指直接計算 y = x^d mod n 來簽署訊息 x（x 可以是 0 到 n − 1 之間的任何數）。

它簡單易於規範與實作，但面對數種攻擊都不安全。

攻擊一：平凡偽造#

注意到無論私鑰 d 的值為何，都有：

0^d mod n = 0
1^d mod n = 1
(n−1)^d mod n = n−1

攻擊者因此能在不知道 d 的情況下偽造 0、1、n−1 的簽章。

攻擊二：盲化攻擊#

更令人擔心的是盲化攻擊（blinding attack）。

假設你想取得第三方對某則罪證訊息 M 的簽章，而你知道他們絕不會知情地簽署它。攻擊流程：

  1. 找出某個值 R，使得 R^e · M mod n 是一則你的受害者願意簽署的訊息。
  2. 說服他們簽署那則訊息並把簽章給你，那個簽章等於 S = (R^e · M)^d mod n。
  3. 從這個簽章導出 M 的簽章 M^d。

推導：因為 S 可以寫成 (R^e · M)^d = R^(ed) · M^d，而依定義 R^(ed) = R，所以：

S = R · M^d

要取得 M^d，只要把 S 除以 R：

S / R = (R · M^d) / R = M^d

如你所見，這是個實用而強大的攻擊。

PSS 簽章標準#

RSA 機率簽章方案（PSS，Probabilistic Signature Scheme）之於 RSA 簽章，就如同 OAEP 之於 RSA 加密。它藉由加入填充資料，讓訊息簽章更安全。

PSS 把一則比模數窄的訊息，與一些隨機位元和固定位元結合起來，再對填充結果套用 RSA。

圖 10-3：以 (n, d) 為私鑰、用 RSA 與 PSS 標準簽署訊息 M

與所有公鑰簽章方案一樣，PSS 處理的是訊息的雜湊而非訊息本身。

只要雜湊函式具碰撞抗性，簽署 Hash(M) 就是安全的。

PSS 的一個特別好處是：你可以用它簽署任意長度的訊息——因為雜湊之後，無論原始訊息多長，你都會得到同樣長度的雜湊值（典型是 256 位元，用 SHA-256）。

為什麼不直接對 Hash(M) 跑 OAEP 來簽章？很遺憾，不行。

儘管 OAEP 與 PSS 相似，OAEP 只被證明對加密安全，對簽章沒有。

簽署流程#

PSS 需要一個 PRNG 與兩個雜湊函式：Hash1 是輸出 h 位元組的典型雜湊（如 SHA-256），Hash2 是像 OAEP 的 Hash2 那樣的寬輸出雜湊。

對訊息 M 的簽署程序：

  1. 用 PRNG 挑一個 r 位元組的隨機字串 R。
  2. 形成編碼訊息 M′ = 0000000000000000 ‖ Hash1(M) ‖ R，長 h + r + 8 位元組（開頭是八個零位元組）。
  3. 計算 h 位元組字串 H = Hash1(M′)。
  4. 設 L = 00...00 ‖ 01 ‖ R——若干 00 位元組後接一個 01 位元組再接 R，00 的數量使 L 長 m − h − 1 位元組。
  5. 設 L = L ⊕ Hash2(H)，以新值取代 L 的舊值。
  6. 把 m 位元組字串 P = L ‖ H ‖ BC 轉換成一個小於 n 的數 x（BC 是接在 H 之後的固定位元組值）。
  7. 計算 RSA 函式 x^d mod n 得到簽章。

驗證：給定訊息 M，計算 Hash1(M)，用公開指數 e 從簽章取回 L 與 H，再取回 M′，每一步都檢查填充的正確性。

實務上隨機字串 R（在 RSA-PSS 標準中稱為 salt）通常與雜湊值等長。

例如用 n = 2048 位元與 SHA-256，則 L 長 m − h − 1 = 256 − 32 − 1 = 223 位元組，而 R 通常是 32 位元組。

與 OAEP 一樣，PSS 可證明安全、已標準化、被廣泛部署。

但也與 OAEP 一樣，它看起來不必要地複雜，容易出現實作錯誤與處理不當的邊界情況。

Full Domain Hash（FDH）#

不像 RSA 加密，簽章有辦法繞過這些額外複雜度——用一個連 PRNG 都不需要的簽章方案，從而降低「不安全的 PRNG 導致不安全 RSA 簽章」的風險。

**Full Domain Hash（FDH）**是你能想像到最簡單的簽章方案：

把 Hash(M) 轉成數 x，簽章就是 y = x^d mod n

驗證同樣直截了當：給定簽章 y，計算 x = y^e mod n，與 Hash(M) 比對。

圖 10-4：以 Full Domain Hash 技術用 RSA 簽署訊息

那為什麼還要 PSS#

主要原因是 PSS 在 FDH 之後（1996 年）發布，而且它的安全性證明比 FDH 更令人有信心——具體來說，它的證明提供了略高於 FDH 之證明的安全保證，而它對隨機性的使用有助於強化該證明。

這些更強的理論保證是密碼學家偏好 PSS 勝過 FDH 的主要原因，但今日多數使用 PSS 的應用其實可以換成 FDH 而不會有有意義的安全損失。

不過在某些情境下，使用 PSS 而非 FDH 確實有正當理由：PSS 的隨機性保護它免於某些針對實作的攻擊，例如「常見錯誤」中會談到的故障攻擊。

Backward 用 RSA 加密 RSA 的實作 Forward