我如何證明 ElGamal 加密在從∗p從p∗mathbb{Z}_p^*使用 OAEP 填充 ind-CPA 是否安全？
我如何證明 ElGamal 加密 $ \mathbb{Z}_p^* $ 具有最佳非對稱加密填充 (OAEP) 的 IND-CPA 是否安全？
這不是一個完整的答案：我只是鼓勵在 ElGamal 加密之上使用 OAEP。
正如現代文獻中所述的 ElGamal 加密，即在決策 Diffie-Hellman 問題很難解決的組中的消息，顯然是CPA 安全的。這不適用於 Taher ElGamal 的A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms中的原始方案，在Crypto 1984 的程序中，即使排除了明顯必要和較小的修正 $ m=0 $ 來自消息空間，我們以後會這樣做。
最初的 ElGamal 加密方案使用一個大素數作為公共參數 $ p $ 和一個原始元素 $ \alpha $ 的 $ \Bbb Z_p^* $ （乘法群模 $ p $ ）。因此 $ x\mapsto \alpha^x\bmod p $ 是一個雙射 $ [1,p) $ . 確保 $ p-1 $ 有一個很大的素數使得反轉這個函式（離散對數問題）變得困難。
接收者 B 選擇一個隨機的秘密私鑰 $ x_B\in[1,p) $ ，計算並發布他的公鑰 $ y_B=\alpha^{x_B}\bmod p $ .
發送者 A，想要加密一個秘密消息 $ m\in[1,p) $ 對 B，隨機選擇一個秘密 $ k\in[1,p) $ , 計算密鑰 $ K={y_B}^k\bmod p $ , 計算 $ c_1=\alpha^k\bmod p $ 然後 $ c_2=K,m\bmod p $ ，並發送密文 $ (c_1,c_2) $ 給 B。
收件人 B 收到 $ (c_1,c_2) $ ，並破譯¹每 $ m={c_1}^{p-1-x_B},c_2\bmod p $ . 這有效，因為 $ K={c_1}^{x_B}\bmod p $ .
觀察給定的 $ y=\alpha^x\bmod p $ 和 $ y\in[1,p) $ , 我們可以確定是否 $ x $ 是奇數還是偶數：我們計算 $ y^{(p-1)/2}\bmod p $ 那就是 $ 1 $ 什麼時候 $ x $ 甚至， $ p-1 $ 什麼時候 $ x $ 很奇怪。用勒讓德符號表示 $ y $ 模組 $ p $ ， 那是 $ \left(\frac yp\right)=+1 $ 什麼時候 $ y^{(p-1)/2}\bmod p=1 $ （甚至 $ x $ ）， 或者 $ \left(\frac yp\right)=-1 $ 什麼時候 $ y^{(p-1)/2}\bmod p=p-1 $ （奇怪的 $ x $ ）。這允許對手通過以下方式確定地贏得IND-CPA 遊戲：
- 選擇兩條消息 $ m_0 $ 和 $ m_1 $ 和 $ \left(\frac{m_0}p\right)=+1 $ 和 $ \left(\frac{m_1}p\right)=-1 $ . 的選擇 $ m_1=1 $ 和 $ m_2=\alpha $ 可以，或者可以通過反複試驗找到有意義的消息，直到兩個具有不同的勒讓德符號。
- 送出 $ m_0 $ 和 $ m_1 $ 挑戰者選擇 $ b\in{0,1} $ 隨機，集合 $ m=m_b $ , 計算並顯示 $ (c_1,c_2) $ 如上。
- 發現 $ b $ 根據下表： $$ \begin{array}{ccc|c} \left(\frac{y_B}p\right)&\left(\frac{c_1}p\right)&\left(\frac{c_2}p\right)&b\ \hline -1&-1&-1&0\ -1&-1&+1&1\ \text{any}&+1&-1&1\ \text{any}&+1&+1&0\ +1&\text{any}&-1&1\ +1&\text{any}&+1&0\ \end{array} $$
這有效，因為 $ \left(\frac{y_B}p\right)=-1\iff x_B\text{ odd} $ 和 $ \left(\frac{c_1}p\right)=-1\iff k\text{ odd} $ . 自從 $ K=\alpha^{x_B,k} $ 這允許確定 $ \left(\frac Kp\right) $ ，即 $ -1 $ 當且僅當兩者 $ \left(\frac{c_1}p\right)=-1 $ 和 $ \left(\frac{c_1}p\right)=-1 $ . 接著 $ \left(\frac{c_2}p\right)=\left(\frac Kp\right),\left(\frac{m_b}p\right) $ 允許結束 $ b $ .
進一步的洩漏可能發生在 $ (p-1)/2 $ 有小的質因數。但是在選擇的時候 $ p $ 這樣 $ (p-1)/2 $ 是素數 ( $ p $ 一個所謂的安全素數），限制策略 $ m $ 和 $ \left(\frac mp\right)=+1 $ 被認為使 ElGamal 加密 IND-CPA 對經典電腦安全²。這可以在沒有迭代過程的情況下完成，將實際資訊轉換為合適的資訊 $ m $ ，然後回到解密方面：在評論中查看 poncho 的漂亮平方技術。
使用 OAEP 填充以準備消息以形成的動機 $ m $ 在 ElGamal 加密中是²：
- 它是非迭代的，甚至比雨披漂亮的平方技術還要快；
- 它應該使 ElGlamal 加密 IND-CPA 安全，因為可能洩漏的部分資訊不足以讓對手撤消填充；
- 除非我再次犯錯，否則它也應該使 ElGlamal 加密IND-CCA1安全（但由於那裡指出的原因而不是 IND-CCA2 安全，即使我們添加範圍檢查 $ c_1 $ 和 $ c_2 $ 解密）。
但我沒有 IND-CPA 和 IND-CCA1 斷言的證據。
¹ 論文計算 $ K={c_1}^{x_B}\bmod p $ ，然後要求“除 $ c_2 $ 經過 $ K $ 恢復 $ m $ ”。這需要計算模逆，也許使用擴展的歐幾里得算法。
² 複雜性被認為是超多項式 $ \log p $ ，包括已知的安全性下降 $ p $ 特殊形式的 $ r^e\pm s $ 和 $ r $ 和 $ s $ 小，啟用SNFS。