在密碼學中,ElGamal加密算法是一個基於迪菲-赫爾曼密鑰交換的非對稱加密算法。它在1985年由塔希爾·蓋莫爾提出。[1]GnuPG和PGP等很多密碼學系統中都應用到了ElGamal算法。
ElGamal加密算法可以定義在任何循環群
上。它的安全性取決於
上的離散對數難題。
ElGamal加密算法由三部分組成:密鑰生成、加密和解密。
密鑰生成的步驟如下:
- Alice利用生成元
產生一個
階循環群
的有效描述。該循環群需要滿足一定的安全性質。
- Alice從
中隨機選擇一個
。
- Alice計算
。
- Alice公開
以及
的描述作為其公鑰,並保留
作為其私鑰。私鑰必須保密。
使用Alice的公鑰
向她加密一條消息
的加密算法工作方式如下:
- Bob從
隨機選擇一個
,然後計算
。
- Bob計算共享秘密
。
- Bob把他要發送的秘密消息
映射為
上的一個元素
。
- Bob計算
。
- Bob將密文
發送給Alice。
值得注意的是,如果一個人知道了
,那麼它很容易就能知道
的值。因此對每一條信息都產生一個新的
可以提高安全性。所以
也被稱作臨時密鑰。
利用私鑰
對密文
進行解密的算法工作方式如下:
- Alice計算共享秘密
![{\displaystyle s:=c_{1}{}^{x}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/394abfb9534c905fa08a60584139919368e990ab)
- 然後計算
,並將其映射回明文
,其中
是
在群
上的逆元。(例如:如果
是整數模n乘法群的一個子群,那麼逆元就是模逆元)。
- 解密算法是能夠正確解密出明文的,因為
![{\displaystyle c_{2}\cdot s^{-1}=m'\cdot h^{y}\cdot (g^{xy})^{-1}=m'\cdot g^{xy}\cdot g^{-xy}=m'.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cceee23463325d5656c228765a4d7f42dba0b226)
ElGamal加密系統通常應用在混合加密系統中。例如:用對稱加密體制來加密消息,然後利用ElGamal加密算法傳遞密鑰。這是因為在同等安全等級下,ElGamal加密算法作為一種非對稱密碼學系統,通常比對稱加密體制要慢。對稱加密算法的密鑰和要傳遞的消息相比通常要短得多,所以相比之下使用ElGamal加密密鑰然後用對稱加密來加密任意長度的消息,這樣要更快一些。
- ^ Taher ElGamal. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (PDF). IEEE Transactions on Information Theory. 1985, 31 (4): 469–472 [2016-12-14]. doi:10.1109/TIT.1985.1057074. (原始內容存檔 (PDF)於2011-08-13). (conference version appeared in CRYPTO'84, pp. 10–18)