在 FDH 中使用 ElGamal 而不是 RSA
在 RSA-FDH 中對消息進行簽名 $ m $ ，我們應用一個雜湊函式 $ H $ 然後使用私鑰“解密”它 $ d $ ， 所以 $ Sign(m) = H(m)^d \mod N =: \sigma $ 然後進行驗證，我們使用公鑰，導致 $ H(m) = \sigma^e \mod N $ 如果一切順利。
為什麼我們必須為此使用 RSA 而不是其他東西，例如 ElGamal？是因為 ElGamal 中的密文是明文的兩倍，還是因為使用 RSA-FDH 時不可能進行一些對手偽造？
為了嘗試嘗試的方法，我們必須定義 $ H $ 在所有 ElGamal 密文的集合上輸出。這是可能的，我在下一段中假設這一點。
與教科書 RSA 不同，ElGamal 加密不是一個函式：重複加密給定的明文會產生（以壓倒性的機率）不同的密文。因此，當我們嘗試驗證問題中的簽名時，沒有理由對簽名進行加密會產生原始雜湊，並且（以壓倒性的可能性）簽名驗證會失敗。問題中考慮的簽名系統不健全。
為簡單起見，考慮乘法群模中的 ElGamal $ p $ ， 著名的 $ \mathbb Z_p^* $ ， 和 $ p $ 和 $ (p-1)/2 $ 素數，和 $ G $ 這樣 $ G^{(p-1)/2}\bmod p,=,p-1 $ :
私鑰是隨機秘密 $ x\in[0,p-1) $ , 公鑰是 $ X:=G^x\bmod p\in[1,p) $ .
任意明文的加密 $ M\in[1,p) $ 去
- 生成臨時隨機秘密 $ y\in[0,p-1) $
- 計算 $ Y:=G^y\bmod n $
- 計算 $ Z:=M\cdot X^y\bmod n $
- 輸出密文 $ (Y,Z) $
任意密文的解密 $ (Y,Z)\in[1,p)\times[1,p) $ 輸出 $ M’:=Y^{n-1-x}\cdot Z\bmod n $ .
$ M’=M $ 不管 $ y $ . 證明提示：費馬小定理。
與教科書 RSA 不同，ElGamal 的這種變體接近IND-CPA，但不完全是。證明提示：考慮勒讓德符號之間的關係 $ \left(\frac M p\right) $ , $ \left(\frac X p\right) $ , $ \left(\frac Y p\right) $ . 我們在下文中忽略了這個相對較小的問題。
糾正此答案第二段中提出的問題的最簡單嘗試之一是修復 $ y=1 $ ， 因此 $ Y=G $ . 然後問題的簽名方案可以使用散列 $ H $ 帶輸出 $ H(m) $ 在全域 $ [1,p) $ 如 $$ H(m):=\big(\operatorname{SHAKE256}(m,b)\bmod p-1\big)+1\text{ with }b=64\left\lceil\log_2(p)/64+2\right\rceil $$ 接著
- 私鑰和公鑰與加密相同
- 簽名 $ m $ 是 $ \sigma:=G^{n-1-x}\cdot H(m)\bmod n $
- 驗證檢查 $ \sigma\cdot X\bmod n=H(m) $ .
至少，在沒有改動的情況下，驗證成功，因此這種簽名方案是合理的。但即使按照最簡單的標準UF-KOA也是不安全的。
其他簡單的嘗試也失敗了，包括
- 製造 $ y $ 添加到私鑰的秘密，與 $ Y:=G^y\bmod n $ 和 $ Y’:=X^y\bmod n $ 添加到公鑰
- 製造 $ y $ 消息的雜湊 $ m $
- 製造 $ Y $ 消息的雜湊 $ m $
- 顯然，任何像 ElGamal 加密一樣在任意組中工作的東西，簽名都是作為 ElGamal 解密輸出的組元素。
雖然這不適用於 ElGamal，但在嘗試從通用公鑰加密方案及其密文域上的雜湊構造簽名時會出現另一個問題：任意密文的解密可能會失敗（對於RSA-OAEP等實際系統也是如此） ，RSAES-OAEP，RSAES-PKCS1-v1_5）。這實際上是一個符合IND-CCA安全性的功能。
沒有從安全公鑰加密構造安全簽名的通用方法。甚至 RSA-FDH 簽名也不能以這種方式工作：它從單向陷門排列和排列域上的散列構造簽名。