エルガマル署名方式
デジタル署名方式

エルガマル署名方式は、離散対数の計算の難しさに基づいたデジタル署名方式です。 1985年にタヘル・エルガマルによって記述されました。[1]

ElGamal署名アルゴリズムは実際にはほとんど使用されていません。NSAで開発され、デジタル署名アルゴリズムとして知られる変種の方がはるかに広く使用されています。他にもいくつかの変種が存在します。[2] ElGamal署名方式は、同じくTaher Elgamalによって発明されたElGamal暗号化と混同しないでください。

概要

エルガマル署名方式は、べき乗剰余の代数的性質と離散対数問題に基づくデジタル署名方式です。このアルゴリズムは、公開鍵と秘密鍵からなる鍵ペアを使用します。秘密鍵はメッセージのデジタル署名を生成するために使用され、署名者の対応する公開鍵を使用して検証できます。デジタル署名は、メッセージ認証（受信者はメッセージの送信元を検証できます）、整合性（受信者は署名以降にメッセージが変更されていないことを検証できます）、および否認不可性（送信者はメッセージに署名していないと虚偽に主張できません）を提供します

歴史

エルガマル署名方式は、1985年にターヘル・エルガマルによって記述されました。 [1]これは、ディフィー・ヘルマン問題に基づいています

操作

この方式には、鍵生成（鍵ペアの作成）、鍵配布、署名、署名検証の4つの操作が含まれます

鍵生成

鍵生成には2つのフェーズがあります。最初のフェーズでは、システムの異なるユーザー間で共有できるアルゴリズムパラメータを選択し、2番目のフェーズでは、1人のユーザーに対して1つの鍵ペアを計算します

パラメータ生成

  • 鍵の長さを選択してください。 N {\displaystyle N}
  • ビットの素数を選択してください N {\displaystyle N} p {\displaystyle p}
  • 出力長が ビットの暗号ハッシュ関数 を選択します。 の場合、ハッシュ出力の左端のビットのみが使用されます。 H {\displaystyle H} L {\displaystyle L} L ＞ N {\displaystyle L>N} N {\displaystyle N}
  • pを法とする整数の乗法群の生成子 を選択します。 g < p {\displaystyle g<p} Z p ∗ {\displaystyle Z_{p}^{*}}

アルゴリズムパラメータは です。これらのパラメータはシステムのユーザー間で共有できます。 （ p 、 g ） {\displaystyle (p,g)}

ユーザーごとの鍵

一連のパラメータが与えられた場合、第2フェーズでは1人のユーザーの鍵ペアを計算します

  • からランダムに整数を選択します。 × {\displaystyle x} { 1 … p − 2 } {\displaystyle \{1\ldots p-2\}}
  • 計算します。 y := g × mod p {\displaystyle y:=g^{x}{\bmod {p}}}

× {\displaystyle x} は秘密鍵、は公開鍵です。 y {\displaystyle y}

鍵配布

署名者は、信頼できる（ただし必ずしも秘密である必要はない）メカニズムを介して公開鍵を受信者に送信する必要があります。署名者は秘密鍵を秘密に保持する必要があります。 y {\displaystyle y} × {\displaystyle x}

署名

メッセージは次のように署名されます。 m {\displaystyle m}

  • から互いに素な整数をランダムに選択します k {\displaystyle k} { 2 … p − 2 } {\displaystyle \{2\ldots p-2\}} k {\displaystyle k} p − 1 {\displaystyle p-1}
  • 計算します。 r := g k mod p {\displaystyle r:=g^{k}{\bmod {p}}}
  • 計算します。 s := （ H （ m ） − × r ） k − 1 mod （ p − 1 ） {\displaystyle s:=(H(m)-xr)k^{-1}{\bmod {(}}p-1)}
  • 万が一、別のランダムで再度開始する場合があります。 s ＝ 0 {\displaystyle s=0} k {\displaystyle k}

署名は です。 （ r 、 s ） {\displaystyle (r,s)}

署名の検証

署名がメッセージに対して有効なものであるかどうかは、次のようにし て検証できます （ r 、 s ） {\displaystyle (r,s)} m {\displaystyle m}

  • および を検証します。 0 < r < p {\displaystyle 0<r<p} 0 < s < p − 1 {\displaystyle 0<s<p-1}
  • 署名は、次の場合にのみ有効です。 g H （ m ） ≡ y r r s （ mod p ） . {\displaystyle g^{H(m)}\equiv y^{r}r^{s}{\pmod {p}}.}

正確性

署名アルゴリズムで生成された署名は検証者によって常に受け入れられるという意味で、アルゴリズムは正しいです

署名生成中 の計算は、 s {\displaystyle s}

H （ m ） ≡ × r + s k （ mod p − 1 ） . {\displaystyle H(m)\,\equiv \,xr+sk{\pmod {p-1}}.}

はと互いに素なので、 g {\displaystyle g} p {\displaystyle p}

g H （ m ） ≡ g × r + s k （ mod p ） ≡ （ g × ） r （ g k ） s （ mod p ） ≡ （ y ） r （ r ） s （ mod p ） . {\displaystyle {\begin{aligned}g^{H(m)}&\equiv g^{xr+sk}{\pmod {p}}\\&\equiv (g^{x})^{r}(g^{k})^{s}{\pmod {p}}\\&\equiv (y)^{r}(r)^{s}{\pmod {p}}.\\\end{aligned}}}

セキュリティ

第三者は、署名者の秘密鍵xを見つけるか、ハッシュ関数の衝突を見つけることで署名を偽造できます。どちらの問題も困難であると考えられています。しかし、2011年現在、計算困難性の仮定への厳密な縮約は知られていません H ( m ) ≡ H ( M ) ( mod p − 1 ) {\displaystyle H(m)\equiv H(M){\pmod {p-1}}}

署名者は、署名ごとに異なるk を一様ランダムに選択し、k、あるいはkに関する部分的な情報でさえも漏洩しないように注意する必要があります。そうでなければ、攻撃者はより低い難易度で秘密鍵x を推測でき、実用的な攻撃が可能になるかもしれません。特に、同じkの値と同じ鍵を用いて2つのメッセージが送信された場合、攻撃者はx を直接計算できます。 [1]

存在偽造

原論文[1]では、ハッシュ関数がシステムパラメータとして含まれていませんでした。メッセージmは、H(m)の代わりにアルゴリズム内で直接使用されていました。これにより、論文のセクションIVで説明されているように、存在偽造と呼ばれる攻撃が可能になります。ポインシュヴァルとスターンはこのケースを一般化し、2つのレベルの偽造について説明しました。[3]

  1. 1パラメータの偽造。となるを選択する。 および を設定する。すると、タプルはメッセージ の有効な署名となる。 e {\displaystyle e} 1 < e < p − 1 {\displaystyle 1<e<p-1} r := g e y mod p {\displaystyle r:=g^{e}y{\bmod {p}}} s := − r mod ( p − 1 ) {\displaystyle s:=-r{\bmod {(p-1)}}} ( r , s ) {\displaystyle (r,s)} m = e s mod ( p − 1 ) {\displaystyle m=es{\bmod {(p-1)}}}
  2. 2パラメータの偽造。、 、 を選択する。 、を設定する。すると、タプルはメッセージ の有効な署名となる。 1パラメータの偽造は、 の場合の2パラメータの偽造の特殊なケースである。 1 < e , v < p − 1 {\displaystyle 1<e,v<p-1} gcd ( v , p − 1 ) = 1 {\displaystyle \gcd(v,p-1)=1} r := g e y v mod p {\displaystyle r:=g^{e}y^{v}{\bmod {p}}} s := − r v − 1 mod ( p − 1 ) {\displaystyle s:=-rv^{-1}{\bmod {(p-1)}}} ( r , s ) {\displaystyle (r,s)} m = e s mod ( p − 1 ) {\displaystyle m=es{\bmod {(p-1)}}} v = 1 {\displaystyle v=1}

参照

参考文献

  1. ^ abcd Taher ElGamal (1985). 「離散対数に基づく公開鍵暗号システムと署名方式」(PDF) . IEEE Transactions on Information Theory . 31 (4): 469– 472. CiteSeerX  10.1.1.476.4791 . doi :10.1109/TIT.1985.1057074. S2CID  2973271（会議版はCRYPTO '84、pp. 10–18に掲載されました）
  2. ^ K. Nyberg, RA Rueppel (1996). 「離散対数問題に基づく署名方式のメッセージ復元」 . Designs, Codes and Cryptography . 7 ( 1–2 ): 61– 81. doi :10.1007/BF00125076. S2CID  123533321.
  3. ^ Pointcheval, David; Stern, Jacques (2000). 「デジタル署名とブラインド署名のセキュリティに関する議論」(PDF) . J Cryptology . 13 (3): 361– 396. CiteSeerX 10.1.1.208.8352 . doi :10.1007/s001450010003. S2CID 1912537. 2021年4月22日時点の オリジナル(PDF)からのアーカイブ。2019年8月17日閲覧。 
Retrieved from "https://en.wikipedia.org/w/index.php?title=ElGamal_signature_scheme&oldid=1300173217"