ElGamal署名のソースを表示

{{出典の明記|date=2020年1月23日 (木) 13:37 (UTC)}}
'''ElGamal署名'''（エルガマルしょめい）とは[[離散対数]]問題の困難性に基づく[[電子署名]]方式である。[[:en:Taher ElGamal]]によって[[1984年]]に提案された<ref name="#1">{{Cite journal|last=Elgamal|first=T.|date=1985-07|title=A public key cryptosystem and a signature scheme based on discrete logarithms|url=http://ieeexplore.ieee.org/document/1057074/|journal=IEEE Transactions on Information Theory|volume=31|issue=4|pages=469–472|language=en|doi=10.1109/TIT.1985.1057074|issn=0018-9448}}</ref>。

この記事に書かれているElGamal署名がそのまま実際に使われることはあまりない。NISTが定めたElGamal署名の改良型である[[Digital Signature Algorithm]] (DSA) が用いられることが多い。他にもElGamal署名の改良型が数多く提案されている (例えば, K. Nyberg and R. A. Rueppel<ref>{{Cite journal|last=Nyberg|first=Kaisa|last2=Rueppel|first2=Rainer A.|date=1996-01|title=Message recovery for signature schemes based on the discrete logarithm problem|url=http://link.springer.com/10.1007/BF00125076|journal=Designs, Codes and Cryptography|volume=7|issue=1-2|pages=61–81|language=en|doi=10.1007/BF00125076|issn=0925-1022}}</ref>)。また、同じくTaher ElGamalによって提案された[[ElGamal暗号]]<ref name="#1"/>と混同してはならない。

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

== 署名方式 ==
=== システムパラメータ ===
*''H''を暗号学的に安全な[[ハッシュ関数]]とする。
*''p''を[[素数]] ''p'' を[[法]]とする[[整数]]の[[乗法群]]<math>Z_p^*</math>上で[[離散対数]]問題が困難であるような大きな素数とする。
*''g''を<math>Z_p^*</math>のランダムな[[原始根]]とする。

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

=== 鍵生成 ===
*1 &lt; ''x'' &lt; ''p''-1なる整数''x''をランダムに選ぶ。
*''y'' = ''g''<sup>''x''</sup> mod ''p''を計算する。
*公開鍵は (''p'', ''g'', ''y'')。
*秘密鍵は''x''である。

=== 署名生成 ===
署名を付けたいメッセージを''m''とする。
*0 &lt; ''k'' &lt; ''p''-1かつgcd(''k'',''p''-1)=1となる''k''をランダムに選ぶ。
*gcd(''k'',''p''-1) を計算する際に[[ユークリッドの互除法#拡張された互除法|拡張されたユークリッドの互除法]]を使用すれば、''bk'' + ''c'' (''p''-1) = 1 を満たす整数 ''b'',''c''も同時に得られる。この式を書き換えれば ''bk'' ≡ 1 (mod ''p''-1) であり、''b'' を ''k''<sup>-1</sup>と置く(つまり、''k''<sup>-1</sup> は[[剰余類環]]<math>Z_{p-1}</math> における [[可逆元]] ''k'' の逆元である)。
*''r'' ≡ ''g''<sup>''k''</sup> (mod ''p'') を計算する。
*''s'' ≡ (''H''(''m'') - ''x'' ''r'') ''k''<sup>-1</sup> (mod ''p''-1) を計算する。
*もし''s''=0であれば''k''を選ぶところからやり直す(これは ''H''(''m'') - ''x'' ''r'' が ''p''-1 の倍数の場合に起こる非常なレアケースであり、''k'' を変えることにより ''r'' が変わり、''s'' が 0 でなくなる可能性が高い)。
*整数の組 (''r'', ''s'')が''m''に対する署名となる。

=== 検証 ===
メッセージ ''m'' と署名 (''r'', ''s'') の検証は以下のように行われる。
*0 &lt; ''r'' &lt; ''p'' かつ 0 &lt; s &lt; ''p'' - 1かどうかを確かめる。
*''g''<sup>''H''(''m'')</sup> ≡ ''y''<sup>''r''</sup> ''r''<sup>''s''</sup> (mod ''p'')かどうかを確かめる。
もし両方を通れば受理する。そうでなければ拒否する。

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

署名生成アルゴリズムより、
: ''H''(''m'') ≡ ''x'' ''r'' + ''s'' ''k'' (mod ''p''-1)
が成立する。
フェルマーの小定理より、
: ''g''<sup>''H''(''m'')</sup> ≡ ''g''<sup>''xr''</sup> ''g''<sup>''ks''</sup> (mod ''p'')
が得られる。
右辺を計算すると、
: ''g''<sup>''xr''</sup> ''g''<sup>''ks''</sup> ≡ ''y''<sup>''r''</sup> ''r''<sup>''s''</sup> (mod ''p'')
が成立する。

== 安全性 ==
署名を偽造するには、
*署名者の秘密鍵''x''を求める
*''H''(''m'') ≡ ''H''(''M'') (mod ''p''-1)が成立する(''m'', ''M'')を得る
が必要であると思われる。両者とも難しいと思われている問題である。
1984年の提案では''H''は使われていないため、存在的偽造が可能である。

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

== 脚注 ==
<references />

== 関連項目 ==
*[[Digital Signature Algorithm]]
*[[楕円曲線DSA]]
*[[ElGamal暗号]]

{{cryptography navbox|public-key}}
{{DEFAULTSORT:Elgamalしよめい}}
[[Category:暗号技術]]
[[Category:コンピュータ・ネットワーク・セキュリティ]]
[[Category:エポニム]]
[[Category:数学に関する記事]]