構造另一個密文，在不知道 Elgamal 中的密鑰的情況下解密為相同的消息
我從各種資源中閱讀了有關 ElGamal 的資訊，我想知道以下是否屬實。如果您能詳細說明一下，我將不勝感激，以便我能更好地理解：
給定加密消息，是否可以構造 $ c_1=E(m) $ , 另一個加密密文 $ c_2 $ 將在不知道用於加密的密鑰的情況下解密為相同的消息？我的意思是創建一個 $ D(c_2)=m $ 在哪裡 $ c_1 \neq c_2 $
我問這個是因為 ElGamal 據我了解，這個密碼系統沒有被定義為單射的，因為加密的結果取決於一些隨機值。
進一步闡述我的想法：我認為 ElGamal 在每條消息可以有幾種合法加密的方式上不是確定性的：對於每個 $ p-1 $ 的 $ k $ ，會有不同的加密，但當然，解密將是可靠的並返回相同的解密消息：它將返回相同的 $ x $ 不依賴於選擇 $ k $ . 所以基本上，
$ x\bmod p = x\cdot b^k\cdot (b^k)^{-1} $ 但 $ x\cdot b^k =y_2 $ 和
$ (b^k)^{-1} = (\alpha^{k\cdot a})^{-1} $ ， 和 $ (y_1^\alpha)^{-1}=(\alpha^{k\cdot a})^{-1} $ .
所以我們得到 $ x \bmod p =(y_2)(y_1^\alpha) $ . 基本上加密我們只需要 $ (p,\alpha,b) $ 並解密我們需要私鑰 $ a $ .
我非常感謝理解這一點。
關鍵在這裡是機率加密
機率加密是在加密算法中使用隨機性，因此當對同一消息進行多次加密時，通常會產生不同的密文
第一個機率加密是由 Shafi Goldwasser 和 Silvio Micali於 1982 年提出的機率加密以及如何玩心理撲克來保密所有部分資訊。您使用隨機數對每條消息進行隨機加密，這樣即使相同的消息也會得到不同的加密。
這就是為什麼我們稱加密可以是機率性的，但解密是確定性的。明文可以有不同的加密，但都必須解密為原始明文
為了在語義上是安全的，也就是說，為了隱藏關於明文的部分資訊，加密算法必須是機率的。
- 我認為 ElGamal 在每條消息可以有幾種合法加密的方式上並不確定：
是的，ElGamal 不是確定性的。在加密過程中，我們為加密選擇一個隨機值，使相同密文的每個加密不同。在計算共享密鑰的過程中，我們隨機選擇一個 $ k \in{1\ldots q-1} $ 並繼續以下參數； $ (G,q,\alpha,b) $ 作為公鑰；
- $ G $ 是循環群
- $ q $ 是大小 $ G $
- $ \alpha $ 是生成器 $ G $
- $ b=\alpha^a $ 在哪裡 $ a $ 是私鑰。
然後加密執行如下；
- 隨機選擇 $ k \in{1\ldots q-1} $
- 計算 $ s = b^k $ -共享的秘密
- 計算 $ c_1 = \alpha^k $
- 計算 $ c_2 = m\cdot s $
如果我們加密 $ m $ 與隨機 $ k $ 比密文對是；$$ (c_1,c_2)= (\alpha^k, m\cdot s) $$用另一個隨機加密 $ k’ \neq k $ 會產生不同的密文；$$ (c’_1,c’_2)= (\alpha^{k’}, m\cdot s’=b^{k’}) $$
- 重新隨機化：如何在不知道明文和私鑰的情況下創建此密文的新加密。
要重新隨機化密文，請取一個新的隨機數 $ k’ \in{1\ldots q-1} $ 併計算 $ b^{k’} $ 和 $ \alpha^{k’} $ 現在將這對相乘。
$$ (c_1 \cdot \alpha^{k’},c_2 \cdot b^{k’}) = (\alpha^k \cdot \alpha^{k’}, m \cdot b^{k} \cdot b^{k’}) = (\alpha^{k+k’}, m \cdot b^{k+k’}) = (c_1’’, m \cdot s’’) $$
因此，新的加密基於組合的共享秘密，即 $ b^{k+k’} $ . 當然，有一個問題是 $ k+k’ $ 可以超過 $ q-1 $ ，但是自從小費馬定理以來，這沒有問題。
這兩個密文是不同的，因為 $ \alpha^{k+k’} \neq \alpha^{k} $ .
解密：
- $ s’’ = (c_1’’)^a $ , $ c_1’’ = \alpha^{k’’} $ 然後 $ (c_1’’)^a = \alpha^{xk’’} = \alpha^{k’’} $
- 計算 $ s’’^{-1} $ 通過 ext-GCD。
- 計算 $ m=c_{2}\cdot s’’^{-1} = m \cdot s’’ \cdot s’’^{-1} =m $
因此，重新隨機化有效。