1984 年にElGamal が発表した離散対数問題の難しさを利用した公開鍵暗号です。
Diffie-Hellman鍵共有法を利用しています。
以下では、変数に使用する文字をDiffie-Hellman鍵共有法に合わせています。
この説明では有限素体を使用していますが、一般の巡回群でも同様の方式が構成できます。
特に、巡回群に楕円曲線上の加法を用いた方式を楕円暗号といいます。
【鍵生成】
Bob は非常に大きな素数 P と P を法とする原始元 g を公開する。
P 未満の秘密の整数 b をランダムに生成し、B を計算し、( P, g, B ) を公開する。
【暗号化】
Alice は P 未満の秘密の整数 a をランダムに生成し、A を計算する。
Alice は平文 M を次式によりC に変換し、暗号文 (A, C) を Bob に送る。
【復号】
Bob は次式により、平文 M を復号する。