El Gamal 密碼系統證明，需要逐步解釋。我覺得我不明白我在這個證明上有什麼
有人可以對 El Gamal 證明提供良好而徹底的解釋嗎？基本上，我需要逐步分解算法中每個重要部分發生的事情。
我無法在 El Gamala 上找到任何以易於理解的格式解釋證明的好筆記。
這是這張圖片中的證明：
首先，我們應該弄清楚我們在這裡證明了什麼。您展示的推導是ElGamal 加密*正確性證明的一部分，*而不是 security。
公鑰加密方案的完全正確性（也稱為完整性）定義如下。
讓 $ (\mathsf{Gen},\mathsf{Enc},\mathsf{Dec}) $ 是一個公鑰加密方案。如果該方案對於任何安全參數都成立，則該方案被認為是完全正確的 $ n\in\mathbb{N} $ , 任何密鑰對 $ (\mathsf{ek},\mathsf{dk})\gets\mathsf{Gen}(1^n) $ , 任何消息 $ m $ 從消息空間和任何密文 $ c \gets \mathsf{Enc}(\mathsf{ek},m) $ 它認為 $ \mathsf{Dec}(\mathsf{dk},c)=m $ .
要查看 ElGamal 加密是否正確，我們首先回顧一下 ElGamal 加密的定義。我會盡量遵循你筆記中的符號。從註釋中不清楚正在使用什麼樣的組。但 $ e_1 $ 是某個子群的生成器 $ \mathbb{Z}_p^* $ . 讓 $ q $ 是該子組的順序。（如果 $ e_1 $ 是一個生成器 $ \mathbb{Z}_p^* $ ， 然後 $ q=p-1 $ ，如果我們處於安全的素數環境中，那麼 $ q=(p-1)/2 $ 和素數。
$$ \begin{align} &\mathsf{Gen}(1^n) && \mathsf{Enc}(e_2,P) && \mathsf{Dec}(d,(c_1,c_2))\ &d\gets\mathbb{Z}_q&&r \gets \mathbb{Z}_q&&P’ := c_2\cdot (c_1^d)^{-1} \bmod p\ &e_2 := e_1^d \bmod p&&c_1:= e_1^r\bmod p&&\text{return }P’\ &\text{return } (e_2,d)&&c_2 := P\cdot e_2^r\bmod p&\ &&&\text{return } (c_1,c_2)&&\ \end{align} $$
為了驗證方案是否正確，我們需要驗證對於任何選擇的密鑰對，並且消息它始終持有 $ \mathsf{Dec}(d,\mathsf{Enc}(e_2,P)) = P $ . 這就是您要查看的推導的來源。
$$ \begin{align} P’ =& c_2\cdot (c_1^d)^{-1} \bmod p \tag{1}\ =& c_2\cdot (e_1^{rd})^{-1} \bmod p\tag{2}\ =& P\cdot e_2^r\cdot (e_1^{rd})^{-1} \bmod p\tag{3}\ =& P\cdot e_1^{rd}\cdot (e_1^{rd})^{-1} \bmod p\tag{4}\ =& P\cdot e_1^{rd}\cdot e_1^{-rd} \bmod p\tag{5}\ =& P\cdot e_1^{rd-rd} \bmod p\tag{6}\ =& P \bmod p\tag{7}\ \end{align} $$
現在讓我們逐行瀏覽。
- 在第 (1) 行中，我們簡單地定義了解密算法。
- 在第 (2) 行中，我們使用 $ c_1 = e_1^r\bmod p $ 從加密算法和替換 $ c_1 $ 根據其定義。
- 在第 (3) 行中，我們做同樣的事情 $ c_2 $ 並用它的定義替換它 $ c_2 := P\cdot e_2^r\bmod p $ 從加密算法。
- 在第 (4) 行中，我們現在查看密鑰生成算法並替換 $ e_2 $ 根據它的定義 $ e_2 := e_1^d \bmod p $ . 請注意，我們沒有更改任何內容。我們只是簡單地替換了變數 $ c_1,c_2,e_2 $ 根據各自的定義。
- 在第 (5) 行中，我們使用求冪的基本規則，即 $ (x^a)^b = x^{a\cdot b} $ ， 所以 $ (e_1^{rd})^{-1} = e_1^{-rd} $ .
- 在第 (6) 行中，我們再次使用求冪的基本規則，即 $ x^a\cdot x^b = x^{a+ b} $ ， 所以 $ e_1^{rd}\cdot e_1^{-rd} = e_1^{rd-rd} $ .
- 自從 $ rd-rd=0 $ 以及任何提高到 $ 0 $ 次方等於恆等式，我們剩下 $ P\cdot 1 \bmod p $ 因此，由於 $ 1 $ 是組的身份 $ P $ 在第 (7) 行。
因為這個推導沒有做任何假設 $ P,d,e_2,c_1 $ 和 $ c_2 $ ，除了它們是根據上述 ElGamal 加密的定義生成的之外，它適用於任何密鑰對和任何明文的選擇 $ P $ .
因此，推導表明解密始終有效，並產生與加密相同的明文，從而表明加密方案實際上是正確的。
它沒有顯示有關該計劃的安全性的任何內容。