ElGamal加密算法

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

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

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

密鑰生成的步驟如下：

（1）Alice利用生成元g產生一個q階循環羣G的有效描述。該循環羣需要滿足一定的安全性質。

（2）Alice從

中隨機選擇一個x。

（3）Alice計算

。

（4）Alice公開h以及

的描述作為其公鑰，並保留x作為其私鑰。私鑰必須保密。

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

（1）Bob從

隨機選擇一個y，然後計算

。

（2）Bob計算共享秘密

。

（3）Bob把他要發送的秘密消息m映射為 G上的一個元素 m'。

（4）Bob計算

。

（5）Bob將密文

發送給Alice。

值得注意的是，如果一個人知道了m'，那麼它很容易就能知道

的值。因此對每一條信息都產生一個新的 y可以提高安全性。所以y也被稱作臨時密鑰。

利用私鑰x對密文

進行解密的算法工作方式如下：

Alice計算共享秘密

；

然後計算

，並將其映射回明文m，其中

是s在羣G上的逆元。（例如：如果G是整數模n乘法羣的一個子羣，那麼逆元就是模逆元）。

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

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