ElGamal 簽名中的逆

我正在學習 ElGamal 簽名驗證。在簽名生成期間，必須選擇一個k這樣1 < k < p − 1和gcd(k, p − 1) = 1。我正在使用來自 Wikipedia 網站的符號。後來它被用作 的倒數k。我假設這是一個模逆。我發現的學習材料沒有說明這是否是關於p或的模逆p-1。有人可以澄清一下嗎？

在 ElGamal 簽名方案中，我們有：

$$ \beta=\alpha^a \bmod p $$ 價值 $ p,\alpha $ 和 $ \beta $ 是公鑰，並且 $ a $ 是私鑰。

$$ \operatorname{sig_k}(x,k)=(\gamma , \delta) $$

在哪裡 $ \gamma = \alpha^k \bmod p $ 和 $ \delta = (x-a\gamma)k^{-1} \bmod {p-1} $ .

這是 $ p-1 $ . 我現在詳細解釋一下為什麼會這樣：

1.首先，我給出一個推論，用於證明ElGamal簽名驗證。

推論如果 $ a $ 和 $ p $ 是相對素數，並且 $ p $ 是一個素數，那麼 $ a^i \equiv a^j \pmod p $ ,其中 i 和 j 是非負整數，當且僅當 $ i \equiv j \pmod {p-1} $ .

這個推論給出了關係 $ p $ 和 $ p-1 $ .

證明它的方法之一是基於定理。

這個定理可以在Kenneth Rosen (p. 349) 的Elementary Number Theory and Its Application , (6th ed.) 中找到。 定理 9.2。它也可以用來證明 DSA。

定理 9.2如果 $ a $ 和 $ n $ 是相對素數 $ n>0 $ ， 然後 $ a^i \equiv a^j \pmod n $ , 其中 i 和 j 是非負整數，當且僅當 $ i \equiv j \pmod {ord_n^a} $

特別是，當 $ p $ 是一個素數， $ {ord_p^a}=\varphi(p)=p-1 $ ，所以我們證明了推論。

因此：

$$ i \equiv j \pmod {p-1} \Leftrightarrow a^i \equiv a^j \pmod p. $$

2. 現在，我們回顧 ElGamal 簽名，並使用推論證明它。

---

2.1 ElGamal 數字簽名的密鑰生成

1. 選擇大素數 $ p $ .
2. 選擇一個原始元素 $ \alpha $ 的 $ Z_p^* $ .
3. 選擇一個隨機整數 $ d \in {2,3, . . . , p-2} $ .
4. 計算 $ \beta = \alpha^d \pmod p $ .

公鑰是 $ k_{pub}=(p, \alpha, \beta) $ , 和私鑰 $ k_{pr}=d $

2.2 ElGamal 簽名生成

簽名包括兩個主要步驟： 選擇一個隨機值 $ k $ ，它形成一個臨時私鑰，併計算實際的簽名 $ x $ .

1. 選擇一個隨機的臨時密鑰 $ k \in {0,1,2, . . . , p-2} $ 這樣 $ gcd(k, p-1) = 1 $ .
2. 計算簽名參數： $$ r \equiv \alpha^k \pmod p $$ $$ s \equiv (x-d\cdot r)k^{-1} \pmod {p-1} $$

因此，簽名是： $$ sig_{k_{pr}}(x,k)=(r,s) $$

2.3 ElGamal 簽名驗證

1. 計算值 $$ t \equiv \beta^r \cdot r^s \pmod p $$
2. 驗證如下： $$ t\begin{cases} \equiv \ \alpha^x \pmod p\ \ \ \ \Rightarrow \ \ \ \ valid \ \ signature\\ \not \equiv \ \alpha^x \ \pmod p\ \ \ \ \Rightarrow \ \ \ \ invalid \ \ signature \end{cases} $$

2.4 證明

證明： $$ \alpha^x \equiv \beta^r \cdot r^s \pmod p $$ 自從：

$$ \beta^r \cdot r^s \pmod p \equiv (\alpha^d)^r(\alpha^k)^s \pmod p \equiv \alpha^{d\cdot r+k\cdot s} \pmod p $$

所以，我們要求：

$$ \alpha^x \equiv \alpha^{d\cdot r+k\cdot s} \pmod p $$

根據上面顯示的推論，當且僅當 時，該關係成立：

$$ x \equiv d\cdot r+k\cdot s \pmod {p-1} $$

因此，我們得到 $ s $ :

$$ s\equiv (x - d \cdot r)k^{-1} \pmod {p-1} $$

這只是簽名參數的構造規則 $ s $ 從。

條件是 $ gcd(k, p-1) = 1 $ 是必需的，因為我們必須反轉臨時密鑰模 $ p-1 $ 計算時 $ s $ .

三、結論

通過上面的描述，我們現在知道為什麼會這樣了 $ p-1 $ ， 不是 $ p $ .

參考

1. 《羅森，KH (2011)。初等數論及其應用（第 6 版）。皮爾遜》
2. 《Paar, C., & Pelzl, J. (2010)。了解密碼學。施普林格出版社》

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