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問題が解ければ暗号を解読できる