ElGamal署名

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

ElGamal署名(エルガマルしょめい)とは離散対数問題の困難性に基づく電子署名方式である。en:Taher ElGamalによって1984年に提案された。

この記事に書かれているElGamal署名がそのまま実際に使われることはあまりない。NISTが定めたElGamal署名の改良型であるDigital Signature Algorithm (DSA) が用いられることが多い。 他にもElGamal署名の改良型が数多く提案されている (例えば, K. Nyberg and R. A. Rueppel)。また、同じくTaher ElGamalによって提案されたElGamal暗号と混同してはならない。

ElGamal署名では、安全でない通信路によって検証者が得たメッセージと署名の組から、検証者は署名者が送ったメッセージmの正当性を確認することができる。

暗号方式[編集]

システムパラメータ[編集]

これらのパラメータはユーザ間で共有される。

鍵生成[編集]

  • 1 < x < p-1なる整数xをランダムに選ぶ。
  • y = gx mod pを計算する。
  • 公開鍵は (p, g, y)。
  • 秘密鍵はxである。

署名生成[編集]

署名を付けたい平文をmとする。

  • 0 < k < p-1かつgcd(k,p-1)=1となるkをランダムに選ぶ。
  • rgk mod pを計算する。
  • s ≡ (H(m) - x r) k-1 mod p-1を計算する。
  • もしs=0であればkを選ぶところからやり直す。
  • 整数の組 (r, s)がmに対する署名となる。

検証[編集]

平文 m と署名 (r, s) の検証は以下のように行われる。

  • 0 < r < p かつ 0 < s < p - 1かどうかを確かめる。
  • gH(m)yr rs (mod p)かどうかを確かめる。

もし両方を通れば受理する。そうでなければ拒否する。

完全性[編集]

署名者が正しく署名した平文と署名の組は必ず検証を通るという意味で、このアルゴリズムは完全である。

署名生成アルゴリズムより、

H(m) ≡ x r + s k (mod p-1)

が成立する。 フェルマーの小定理より、

gH(m)gxr gks (mod p)

が得られる。 右辺を計算すると、

gxr gksyr rs (mod p)

が成立する。

安全性[編集]

署名を偽造するには、

  • 署名者の秘密鍵xを求める
  • H(m) ≡ H(M) (mod p-1)が成立する(m, M)を得る

が必要であると思われる。両者とも難しいと思われている問題である。 1984年の提案ではHは使われていないため、存在的偽造が可能である。

署名者は毎回kをランダムに選ぶ必要がある。また、kの情報を部分的にでも漏らしてはいけない。 そうでない場合、攻撃者が秘密鍵xを得ることが簡単になり、現実的な時間でxが得られるかも知れない。 特に、二つの別々のメッセージに同じ乱数kで署名を行った場合、攻撃者は直接xを得ることが可能になる。

脚注[編集]


関連項目[編集]