ElGamal暗号

1984 年にElGamal が発表した離散対数問題の難しさを利用した公開鍵暗号です。

Diffie-Hellman鍵共有法を利用しています。

以下では、変数に使用する文字をDiffie-Hellman鍵共有法に合わせています。

この説明では有限素体を使用していますが、一般の巡回群でも同様の方式が構成できます。

特に、巡回群に楕円曲線上の加法を用いた方式を楕円暗号といいます。

【鍵生成】

Bob は非常に大きな素数 P と P を法とする原始元 g を公開する。

P 未満の秘密の整数 b をランダムに生成し、B を計算し、( P, g, B ) を公開する。

B = g ^b mod P

【暗号化】

Alice は P 未満の秘密の整数 a をランダムに生成し、A を計算する。

A = g ^a mod P

Alice は平文 M を次式によりC に変換し、暗号文 (A, C) を Bob に送る。

C = M B ^a mod P (= M K mod P )

【復号】

Bob は次式により、平文 M を復号する。

M = C (A^b)^-1 mod P (= C K^-1 mod P )