ElGamal署名

ElGamal署名︵エルガマルしょめい︶とは離散対数問題の困難性に基づく電子署名方式である。en:Taher ElGamalによって1984年に提案された^[1]。この記事に書かれているElGamal署名がそのまま実際に使われることはあまりない。NISTが定めたElGamal署名の改良型であるDigital Signature Algorithm (DSA) が用いられることが多い。他にもElGamal署名の改良型が数多く提案されている (例えば, K. Nyberg and R. A. Rueppel^[2])。また、同じくTaher ElGamalによって提案されたElGamal暗号^[1]と混同してはならない。 ElGamal署名では、安全でない通信路によって検証者が得たメッセージと署名の組から、検証者は署名者が送ったメッセージmの正当性を確認することができる。

署名方式[編集]

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

●Hを暗号学的に安全なハッシュ関数とする。 ●pを素数 pを法とする整数の乗法群

Z_{p}^{*}

Z_{p}^{*}

上で離散対数問題が困難であるような大きな素数とする。 ●gを

Z_{p}^{*}

Z_{p}^{*}

のランダムな原始根とする。これらのパラメータはユーザ間で共有される。

鍵生成[編集]

●1 < x< p-1なる整数xをランダムに選ぶ。 ●y = g^xmod 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 は剰余類環

Z_{p-1}

Z_{p-1}

における可逆元 kの逆元である)。 ●r ≡ g^k(mod p) を計算する。 ●s ≡ (H(m) - xr) k^-1 (mod p-1) を計算する。 ●もしs=0であればkを選ぶところからやり直す(これは H(m) - xrが p-1 の倍数の場合に起こる非常なレアケースであり、k を変えることにより rが変わり、s が 0 でなくなる可能性が高い)。 ●整数の組 (r, s)がmに対する署名となる。

検証[編集]

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

完全性[編集]

署名者が正しく署名したメッセージと署名の組は必ず検証を通るという意味で、このアルゴリズムは完全である。署名生成アルゴリズムより、 H(m) ≡ xr+ sk(mod p-1) が成立する。フェルマーの小定理より、 g^H(m) ≡ g^xrg^ks(mod p) が得られる。右辺を計算すると、 g^xr g^ks≡ y^rr^s(mod p) が成立する。

安全性[編集]

署名を偽造するには、 ●署名者の秘密鍵xを求める ●H(m) ≡ H(M) (mod p-1)が成立する(m, M)を得るが必要であると思われる。両者とも難しいと思われている問題である。 1984年の提案ではHは使われていないため、存在的偽造が可能である。署名者は毎回kをランダムに選ぶ必要がある。また、kの情報を部分的にでも漏らしてはいけない。そうでない場合、攻撃者が秘密鍵xを得ることが簡単になり、現実的な時間でxが得られるかも知れない。特に、二つの別々のメッセージに同じ乱数kで署名を行った場合、攻撃者は直接xを得ることが可能になる。

脚注[編集]

^ ^a ^b Elgamal, T. (1985-07). “A public key cryptosystem and a signature scheme based on discrete logarithms” (英語). IEEE Transactions on Information Theory 31 (4): 469–472. doi:10.1109/TIT.1985.1057074. ISSN 0018-9448.
^ Nyberg, Kaisa; Rueppel, Rainer A. (1996-01). “Message recovery for signature schemes based on the discrete logarithm problem” (英語). Designs, Codes and Cryptography 7 (1-2): 61–81. doi:10.1007/BF00125076. ISSN 0925-1022.