求真百科歡迎當事人提供第一手真實資料,洗刷冤屈,終結網路霸凌。

ElGamal加密算法檢視原始碼討論檢視歷史

事實揭露 揭密真相
前往: 導覽搜尋
ElGamal加密算法
圖片來自newton

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

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

實際使用

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

算法

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

密鑰生成

密鑰生成的步驟如下:

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

加密

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

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

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

解密

利用私鑰x對密文(c_1,c_2)進行解密的算法工作方式如下:

  • Alice計算共享秘密s:=c_1{}^x
  • 然後計算m':=c_2 \cdot s^{-1},並將其映射回明文m,其中s^{-1}是s在群G上的逆元。(例如:如果G是整數模n乘法群的一個子群,那麼逆元就是模逆元)。
解密算法是能夠正確解密出明文的,因為
c_2 \cdot s^{-1} = m'\cdot h^y \cdot (g^{xy})^{-1} = m'\cdot g^{xy} \cdot g^{-xy} = m'.

參考文獻