ElGamal暗号

ElGamal暗号

(サイエンス)
えるがまるあんごう

1982年にElGamalが考案した公開鍵暗号。

方式

鍵生成

  1. 大きな素数pを選ぶ
  2. 位数がpの巡回群Gの生成元gを選ぶ
  3. xを\{1,2,...,p-1\}からランダムに選ぶ
  4. yをy=g^xとする

公開鍵は(p,g,y)。秘密鍵はx。

暗号化

 m \in Gを暗号化する。

  1. kをZ_{p-1}からランダムに選ぶ
  2. c_1 = g^k とする
  3. c_2 = m y^kとする

暗号文は(c_1, c_2)

復号

 (c_1, c_2) \in G \times Gを復号する。

  1. m = c_2 ({c_1}^{-1})^xを計算する

楕円曲線について

巡回群Gとして楕円曲線で定義される素数位数の巡回群を選ぶ場合がある。この場合、楕円曲線ElGamalと呼ばれる(→楕円曲線暗号, ECC)。

安全性

直感的に言えば、c_1によってDiffie-Hellman鍵交換を行い、その鍵を用いて平文mをマスクしている。
暗号解読はCDH問題(Computational Diffie-Hellman問題)と等価である*1。CDH問題とは位数が素数pの群Gとその生成元g, g^a, g^bを入力として, g^{ab}を計算する問題。


*リストリスト::数学関連

*1:暗号を解読できればCDH問題が解けるし、CDH問題が解ければ暗号を解読できる

新着ブログ: ElGamal暗号