ElGamal加密算法

在密碼學中，ElGamal加密算法是一個基於迪菲-赫爾曼密鑰交換的非對稱加密算法。它在1985年由塔希爾·蓋莫爾提出。^[1]GnuPG和PGP等很多密碼學系統中都應用到了ElGamal算法。

ElGamal加密算法可以定義在任何循環群${\displaystyle G}$上。它的安全性取決於${\displaystyle G}$上的離散對數難題。

算法

ElGamal加密算法由三部分組成：密鑰生成、加密和解密。

密鑰生成

密鑰生成的步驟如下：

• Alice利用生成元${\displaystyle g}$產生一個${\displaystyle q\,}$階循環群${\displaystyle G\,}$的有效描述。該循環群需要滿足一定的安全性質。
• Alice從${\displaystyle \{1,\ldots ,q-1\}}$中隨機選擇一個${\displaystyle x}$。
• Alice計算${\displaystyle h:=g^{x}}$。
• Alice公開${\displaystyle h\,}$以及${\displaystyle G,q,g\,}$的描述作為其公鑰，並保留${\displaystyle x}$作為其私鑰。私鑰必須保密。

加密

使用Alice的公鑰${\displaystyle (G,q,g,h)}$向她加密一條消息${\displaystyle m}$的加密算法工作方式如下：

• Bob從${\displaystyle \{1,\ldots ,q-1\}}$隨機選擇一個${\displaystyle y}$，然後計算${\displaystyle c_{1}:=g^{y}}$。
• Bob計算共享秘密${\displaystyle s:=h^{y}}$。
• Bob把他要發送的秘密消息${\displaystyle m}$映射為${\displaystyle G}$上的一個元素${\displaystyle m'}$。
• Bob計算${\displaystyle c_{2}:=m'\cdot s}$。
• Bob將密文${\displaystyle (c_{1},c_{2})=(g^{y},m'\cdot h^{y})=(g^{y},m'\cdot (g^{x})^{y})}$發送給Alice。

值得注意的是，如果一個人知道了${\displaystyle m'}$，那麼它很容易就能知道${\displaystyle h^{y}}$的值。因此對每一條信息都產生一個新的${\displaystyle y}$可以提高安全性。所以${\displaystyle y}$也被稱作臨時密鑰（英語：ephemeral key）。

解密

利用私鑰${\displaystyle x}$對密文${\displaystyle (c_{1},c_{2})}$進行解密的算法工作方式如下：

• Alice計算共享秘密${\displaystyle s:=c_{1}{}^{x}}$
• 然後計算${\displaystyle m':=c_{2}\cdot s^{-1}}$，並將其映射回明文${\displaystyle m}$，其中${\displaystyle s^{-1}}$是${\displaystyle s}$在群${\displaystyle G}$上的逆元。（例如：如果${\displaystyle G}$是整數模n乘法群的一個子群，那麼逆元就是模逆元）。

解密算法是能夠正確解密出明文的，因為

${\displaystyle c_{2}\cdot s^{-1}=m'\cdot h^{y}\cdot (g^{xy})^{-1}=m'\cdot g^{xy}\cdot g^{-xy}=m'.}$

實際使用

ElGamal加密系統通常應用在混合加密系統（英語：hybrid cryptosystem）中。例如：用對稱加密體制來加密消息，然後利用ElGamal加密算法傳遞密鑰。這是因為在同等安全等級下，ElGamal加密算法作為一種非對稱密碼學系統，通常比對稱加密體制要慢。對稱加密算法的密鑰和要傳遞的消息相比通常要短得多，所以相比之下使用ElGamal加密密鑰然後用對稱加密來加密任意長度的消息，這樣要更快一些。