ElGamal 簽名 - 表明(c,d)(C,d)(gamma, delta)跡象米米m
我們有一個給定的： $ gcd(j, p − 1) = 1 $ .
$$ γ = \alpha^i \beta^j \bmod p $$ $$ \delta = −\gamma j^{-1} \bmod (p−1) $$ $$ m = i \delta \bmod (p − 1) $$ 我想證明 $ (\gamma; \delta) $ 是消息的 ElGamal 簽名 $ m $ .
在本書中，他們展示了一個例子：
我怎樣才能證明 $ (\gamma, \delta) $ 跡象 $ m $ ?
在您發布的書中的符號中，有效的 ElGamal 簽名滿足：
$$ \beta^\gamma \gamma^\delta = \alpha^m \bmod p $$ 這只是 ElGamal 簽名的定義。您發布的片段不是一個例子，而恰恰證明了 $ (\gamma, \delta) $ 是一個有效的簽名 $ m = i \delta \bmod (p-1) $ . 在這本書的第 68 頁上，它說
( $ \gamma, \delta $ ) 是 x 的有效簽名。它的確是 …
（用英語講： ” $ (\gamma,\delta) $ 是一個有效的簽名 $ x $ . 確實，一個人驗證了……”）
因此，讓我們逐步完成證明。一切都是 $ \bmod p $ :
$$ \beta^\gamma \gamma^\delta = \beta^{\alpha^i \beta^j } (\alpha^i \beta^j)^{-\alpha^i \beta^j j^{-1} } $$ （替換值）
$$ … = \beta^{\alpha^i \beta^j } \alpha^{-i j^{-1} \alpha^i \beta^j } \beta^{-\alpha^i \beta^j} $$ （只需將指數分佈在 $ \alpha^i $ 和 $ \beta^j $ . 在裡面 $ \beta $ 指數，你得到一個 $ j j^{-1} = 1 $ )
$$ …= \alpha^{-i j^{-1} \alpha^i \beta^j } $$ （這 $ \beta $ 條款取消）
$$ …= \alpha^{-\gamma i j^{-1} } $$ （定義 $ \gamma $ )
$$ …= \alpha^m $$ （定義 $ m $ )
這裡， $ i $ 和 $ j $ 是這樣的 $ 0 \leq i,j \leq p-2 $ . 您展示的證據是該方案在存在上是可偽造的（參見第 381 頁，定理 16）。這是一個雙參數偽造（ $ (i,j) $ ).