エルガマル署名方式

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

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

ElGamal 署名方式は、離散対数問題とともに、モジュラー指数の代数的特性に基づくデジタル署名方式です。このアルゴリズムでは、公開鍵と秘密鍵で構成される鍵ペアを使用します。秘密鍵はメッセージのデジタル署名を生成するために使用され、署名者の対応する公開鍵を使用して、このような署名を検証できます。デジタル署名は、メッセージ認証 (受信者がメッセージの発信元を検証できる)、整合性 (受信者がメッセージが署名されてから変更されていないことを検証できる)、および否認不可性 (送信者がメッセージに署名していないと虚偽の主張できない) を提供します。

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

この方式には、キー生成 (キー ペアの作成)、キー配布、署名、署名検証の 4 つの操作が含まれます。

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

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

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

一連のパラメータが指定されると、第 2 フェーズでは単一のユーザーのキー ペアが計算されます。

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

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

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

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

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

署名は です。 ${\displaystyle (r,s)}$

次のようにして、署名がメッセージに対して有効な署名であるかどうかを確認できます。 ${\displaystyle (r,s)}$${\displaystyle m}$

• および を確認します。${\displaystyle 0<r<p}$${\displaystyle 0<s<p-1}$
• 署名は、以下の場合にのみ有効です。${\displaystyle g^{H(m)}\equiv y^{r}r^{s}{\pmod {p}}.}$

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

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

${\displaystyle H(m)\,\equiv \,xr+sk{\pmod {p-1}}.}$

はと互いに素なので、 ${\displaystyle g}$${\displaystyle 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 年現在、計算困難性の仮定への厳密な簡約は知られていません。 ${\displaystyle H(m)\equiv H(M){\pmod {p-1}}}$

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

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

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

• モジュラー演算
• デジタル署名アルゴリズム
• 楕円曲線デジタル署名アルゴリズム
• エルガマル暗号
• シュノア署名
• ポインシュヴァル・スターン署名アルゴリズム