帶有兩條消息的 El-Gamal 簽名
Alice 使用基於組的 ElGamal 簽名 $ Z^{107} $ 和參數 $ g=3 $ 有秩序的 $ q=53 $ .Alice 的私鑰是一些 $ x \in {0,1,…..,52} $ 她的公鑰是 $ y=10 $ . 為了簽署消息 m，她計算 $ r=g^k \bmod107 $ 為了 $ k \in {0,1,……,52} $ 和 $ s=(k \cdot h(m)+r\cdot x) \bmod 53 $ . 為了簽署第一條消息，Alice 隨機選擇一個 $ k_1 \in {0,1,……,52} $ . 簽署她使用的第二條消息 $ k_2=(2 \cdot k_1 +1) \bmod 53 $ 通常，如果要簽名 $ i $ - 她使用的第一個消息 $ k_i $ 為了 $ (i+1) $ - 她使用的第一個消息 $ k{i+1}=(2\cdot k_i +1)\bmod 53 $ . 你知道 Alice 的兩個連續簽名： $ (r,s)=(79,7) $ 消息的 $ m $ 和 $ h(m)=2 $ 和簽名 $ (r’,s’)=(105,41) $ 消息的 $ m’ $ 和 $ h(m’)=3 $ . 找到 Alice 的私鑰（當然不用直接計算群中的任何離散對數） $ Z^_{107} $ )
我正在努力解決這個問題。我嘗試應用 ElGamal 算法，但我不知道如何使用 $ h(m) $ 雜湊函式。誰能幫助解決它並幫助我如何使用正確的 ElGamal 簽名？
（來源：2008年數學競賽，法國）
在繼續閱讀此答案之前，請閱讀我上面的提示：
嘗試寫下不同 s 的所有方程，並嘗試求解方程組。
如果您仍然無法解決這個問題，您可以閱讀答案的其餘部分。
首先觀察到 $ s_1 \equiv k_1 \cdot h(m) + r_1\cdot x \pmod {53} $ 和 $ s_2 \equiv k_2 \cdot h(m’) + r_2\cdot x \pmod {53} $ 只有在哪裡 $ k_1,k_2,x $ 是未知的。所以 2 個方程的 3 個變數，這是不可解的，對吧？
這就是特殊關係發揮作用的地方。代替 $ k_2 $ 經過 $ 2k_1+1 $ 產生
$ s_2\equiv (2k_1 + 1) \cdot h(m’) + r_2\cdot x\equiv 2k_1\cdot h(m’) + h(m’) + r_2\cdot x \pmod {53} $
現在將第一個方程減去兩次 $ h(m’) $ 從第二個方程次 $ h(m) $ 產生：
$ s_2\cdot h(m) - 2\cdot h(m’)\cdot s_1 \equiv h(m)\cdot h(m’)+r_2 \cdot h(m)\cdot x - 2r_1 \cdot h(m’) \cdot x \equiv h(m)\cdot h(m’)+ x \cdot (r_2\cdot h(m) - 2r_1\cdot h(m’)) \pmod {53} $
最後乘以倒數 $ r_2\cdot h(m) - 2r_1\cdot h(m’) $ ( $ =(r_2\cdot h(m) - 2r_1\cdot h(m’))^{-1}\bmod 53 $ ) 並減去 $ h(m)\cdot h(m’) $ . 這為我們提供了以下用於檢索的等式 $ x $ :
$ x = (s_2\cdot h(m) - 2\cdot h(m’)\cdot s_1)\cdot (r_2\cdot h(m) - 2r_1\cdot h(m’))^{-1} - h(m)\cdot h(m’) \bmod 53 $
密鑰生成
- 選擇素數 p 和生成器 g；
- 發送者 S 選擇一個隨機整數 r（密鑰），使得
0 < r < p − 1 併計算 K=(g^r)(modp)；
K、g 和 p 屬於公共領域；
簽約
- 為了驗證消息 M，發送者選擇另一個隨機整數 R (0 < R < p − 1 and gcd(R,p-1)=1 併計算
X = (g ^ R) (modp);
- 發送者找到 Y 使得 M=rX+RY mod(p-1); (X,Y) 是 M 的簽名：
M=rX+RY mod(p-1)
Y =？國防部（p-1）
RY = (M – rX) mod (p-1)
Y = (M – rX) R-1 mod (p-1)
確認
- 接收方 B 得到 (M, X, Y) 併計算 A=(K^X)(X^Y)modp；(X,Y) 稱為驗證者。
- B 接受 M 當且僅當 A=g^M(modp)。
希望這可以幫助。