ElGamal加密算法

佇密碼學中，ElGamal 加密算法是一个是對迪菲-赫爾曼密鎖交換的非對稱加密算法。伊一九八五年由塔希爾 ・ 蓋不要而已提出。GnuPG 和 PGP 等真濟密碼學系統中攏應用著矣 ElGamal 算法。

ElGamal 加密算法會當定義佇任何循環群 $ G $ 上。伊的安全性就著矣 $ G $ 上的離散對數難題。

算法

ElGamal 加密算法由三部份的組成：密鎖生成、加密佮解密。

密鎖生成

密鎖生成的步驟之下：

• Alice 利用生成元 $ g $ 產生一个 $ q \ , $ 階循環群 $ G \ , $ 的這个有效去描寫講。該循環群需要滿足一定的安全性質。
• Alice 對 $ \ { 一 , \ ldots , q 影一 \ } $ 隨機選擇一个 $ x $。
• Alice 計算 $ h :=g ^ { x } $。
• Alice 公開 $ h \ , $ 以及 $ G , q , g \ , $ 欲描述做其他的公鎖，並保留 $ x $ 做其實私鎖。私鎖著愛保密。

加密

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

• Bob 對 $ \ { 一 , \ ldots , q 影一 \ } $ 隨機選擇一个 $ y $，然後計算 $ c _ { 一 } :=g ^ { y } $。
• Bob 計算共享祕密 $ s :=h ^ { y } $。
• Bob 共伊欲發送的祕密消息 $ m $ 炤做 $ G $ 上的一个元素 $ m'$。
• Bob 計算 $ c _ { 二 } :=m'\ cdot s $。
• Bob 共密文 $ ( c _ { 一 } , c _ { 二 } )=( g ^ { y } , m'\ cdot h ^ { y } )=( g ^ { y } , m'\ cdot ( g ^ { x } ) ^ { y } ) $ 來發送予 Alice。

值得注意的是，若一个人知影矣 $ m'$，按呢伊真容易就會當知影講 $ h ^ { y } $ 的值。因此對每一條信息攏產生一个新的 $ y $ 會當提高安全性。所以乎 $ y $ 嘛予人號做臨時密鎖。

解密

利用私鎖 $ x $ 嘿密文 $ ( c _ { 一 } , c _ { 二 } ) $ 進行解密的算法工作方式如下：

• Alice 計算共享祕密 $ s :=c _ { 一 } { } ^ { x } $
• 然後計算 $ m':=c _ { 二 } \ cdot s ^ { 影一 } $，閣共伊映射回明文 $ m $，其中 $ s ^ { 影一 } $ 是 $ s $ 在群 $ G $ 上的逆元。（比如講：若是 $ G $ 是整數模 n 乘法群的一个子群，遐爾仔逆元就是模逆元）。

解密算法是會當正確解密出明文的，因為乎

: $ c _ { 二 } \ cdot s ^ { 影一 }=m'\ cdot h ^ { y } \ cdot ( g ^ { xy } ) ^ { 影一 }=m'\ cdot g ^ { xy } \ cdot g ^ {-xy }=m'. $

實際使用

ElGamal 加密系統通常應用佇透濫加密系統內底。比如講：用對稱加密體制來加密消息，然後利用 ElGamal 加密算法傳遞密鎖。這是因為佇同等安全等級之下，ElGamal 加密算法做一種非對稱密碼學系統，通常比對加密的體制愛慢。對稱加密算法的密鎖佮欲傳達的消息相比通常愛短較濟，所以比起來就使用 ElGamal 加密鎖然後用對稱加密來加密任意長度的消息，按呢愛較緊一下。