ElGamal署名

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

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

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

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

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

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

 署名生成 
署名を付けたいメッセージをmとする。
0 < k < 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-1と置く(つまり、k-1 は剰余類環 における 可逆元 k の逆元である)。
r ≡ gk (mod p) を計算する。
s ≡ (H(m) - x r) k-1 (mod p-1) を計算する。
もしs=0であればkを選ぶところからやり直す(これは H(m) - x r が p-1 の倍数の場合に起こる非常なレアケースであり、k を変えることにより r が変わり、s が 0 でなくなる可能性が高い)。
整数の組 (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 gks ≡ yr rs (mod p)
が成立する。

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

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

 脚注 

 関連項目 
Digital Signature Algorithm
楕円曲線DSA
ElGamal暗号

Category:暗号技術
Category:コンピュータ・ネットワーク・セキュリティ
Category:エポニム
Category:数学に関する記事