ElGamal署名

ElGamal署名（エルガマルしょめい）とは離散対数問題の困難性に基づく電子署名方式である。によって1984年に提案された。
この記事に書かれているElGamal署名がそのまま実際に使われることはあまりない。NISTが定めたElGamal署名の改良型であるDigital Signature Algorithm (DSA) が用いられることが多い。他にもElGamal署名の改良型が数多く提案されている (例えば, K. Nyberg and R. A. Rueppel)。また、同じくTaher ElGamalによって提案されたElGamal暗号と混同してはならない。
ElGamal署名では、安全でない通信路によって検証者が得たメッセージと署名の組から、検証者は署名者が送ったメッセージ"m"の正当性を確認することができる。
署名方式.
システムパラメータ.
これらのパラメータはユーザ間で共有される。
署名生成.
署名を付けたいメッセージを"m"とする。
検証.
メッセージ "m" と署名 ("r", "s") の検証は以下のように行われる。
もし両方を通れば受理する。そうでなければ拒否する。
完全性.
署名者が正しく署名したメッセージと署名の組は必ず検証を通るという意味で、このアルゴリズムは完全である。
署名生成アルゴリズムより、
が成立する。
フェルマーの小定理より、
が得られる。
右辺を計算すると、
が成立する。
安全性.
署名を偽造するには、
が必要であると思われる。両者とも難しいと思われている問題である。
1984年の提案では"H"は使われていないため、存在的偽造が可能である。
署名者は毎回"k"をランダムに選ぶ必要がある。また、"k"の情報を部分的にでも漏らしてはいけない。
そうでない場合、攻撃者が秘密鍵"x"を得ることが簡単になり、現実的な時間で"x"が得られるかも知れない。
特に、二つの別々のメッセージに同じ乱数"k"で署名を行った場合、攻撃者は直接"x"を得ることが可能になる。