楕円曲線ElGamal署名
5.のページ分割
5. 楕円曲線ElGamal署名 Elliptic Curve ElGamal Signatures
5.1. 背景
5.2. ハッシュ関数
ElGamal署名は、任意の長さのメッセージに署名でき、存在偽造攻撃を回避できるように、衝突耐性ハッシュ関数を使用する必要があります。10.4節を参照してください。（これはすべてのElGamalバリアントHMP1994に当てはまります。）ハッシュ関数をh()と表記します。入力は任意長のビット文字列であり、出力は非負整数です。 H()は、出力が固定長ビット文字列であるハッシュ関数を表します。ElGamal署名方式でHを使用するには、その出力と非負整数との間のマッピングを定義します。これにより、前述の関数h()が実現されます。ビット文字列mが与えられた場合、関数h(m)は次のように計算されます。
1. H(m)が評価され、結果は固定長ビット文字列です。
2. 結果のビット文字列の左端 (最初) のビットを i の最上位ビットとして扱い、右端 (最後) のビットを i の最下位ビットとして扱って、結果のビット文字列を整数 i に変換します。
5.3. KT-IV署名
小山と鶴岡は、楕円曲線エルガマルに基づく署名方式を報告した。この方式では、署名の第一要素は楕円曲線上の点のx座標をqを法として縮約したものであるKT1994。本節では、この方式をKT-IVと呼ぶ。 このアルゴリズムは、3.3節で述べたように、素体位数pと曲線方程式パラメータaおよびbを持つ楕円曲線群を用いる。生成元(generator)をalpha、生成元位数(order of the generator)をqとする。例外ケースのチェックはFIPS186に従う。 5.3.1. 鍵ペアの生成
秘密鍵 z は 1 から q-1 までの整数であり、一様ランダムに生成されます。(ランダムな整数については付録 B を参照してください。) 公開鍵は群元 $ Y = alpha^z です。各公開鍵は、セクション 3.3 に従って特定のパラメータセットに関連付けられます。
5.3.2. 署名生成
秘密鍵 z を用いてメッセージ m の KT-IV 署名を計算するには、以下の手順を実行する。
1. 1 から q-1 までのすべての整数の集合から、一様ランダムに整数 k を選択する。(ランダムな整数については付録 B を参照。)
2. $ R = (r_x, r_y) = alpha^k を計算する。
3. $ s1 = r_x \mod q を計算する。
4. h(m) + z * s1 = 0 mod q であるかどうかを確認する。もしそうであれば、k の新しい値を生成し、署名を再計算する必要がある。オプションとして、s1 = 0 であるかどうかを確認することもできる。もしそうであれば、k の新しい値を生成し、署名を再計算する必要がある。 （署名が適切に生成された場合、s1 = 0 または h(m) + z * s1 = 0 mod q となる可能性は極めて低い。）
5. $ s2 = k/(h(m) + z*s1) \mod q を計算する。
署名は順序付きペア (s1, s2) である。署名の両要素は非負の整数である。
5.3.3. 署名検証
メッセージ m、生成子 g、群の位数 q、公開鍵 Y、署名 (s1, s2) が与えられた場合、検証は以下のとおりです。
1. 0 < s1 < q かつ 0 < s2 < q であることを確認します。いずれかの条件に違反する場合、署名は拒否されます。
2. 非負整数 u1 および u2 を計算します。ここで、
u1 = h(m) * s2 mod q、および
u2 = s1 * s2 mod q です。
3. 楕円曲線上の点 $ R' = alpha^{u1} * Y^{u2} を計算します。
4. R' mod q の x 座標が s1 と等しい場合、署名とメッセージは検証に合格します。そうでない場合、検証は不合格となります。
5.4. KT-I署名
Horster、Michels、およびPetersenは、多くの異なるElGamal署名方式を分類し、それらの等価性を実証し、あるタイプの署名を別のタイプの署名に変換する方法を示しましたHMP1994。彼らの用語では、5.3節およびKT1994の署名方式はタイプIV方式であるため、KT-IVと表記されます。 タイプIのKT署名方式には、デジタル署名アルゴリズムと同じ方法で計算される第2の要素があります。本節では、KT-Iと呼ばれるこの方式について説明します。
5.4.1. 鍵ペア生成
鍵ペアと鍵ペア生成は、セクション5.3.1と全く同じです。
5.4.2. 署名生成
秘密鍵zを用いてメッセージmのKT-I署名を計算するには、以下の手順に従います。
1. 1からq-1までのすべての整数の集合から、一様ランダムに整数kを選択します。(ランダムな整数については、付録Bを参照してください。)
2. $ R = (r_x, r_y) = alpha^kを計算します。
3. $ s1 = r_x \mod qを計算します。
4. $ s2 = (h(m) + z*s1)/k \mod qを計算します。
5. オプションとして、s1 = 0 または s2 = 0 かどうかをチェックしてもよい（MAY）。s1 = 0 または s2 = 0 のいずれかの場合、k の新しい値を生成し、署名を再計算する必要がある（SHOULD）。（署名が適切に生成された場合、s1 = 0 または s2 = 0 となる可能性は極めて低い。）
署名は順序付きペア（s1, s2）である。署名のどちらの要素も非負の整数である。
5.4.3. 署名検証
メッセージ m、公開鍵 Y、署名 (s1, s2) が与えられた場合、検証は以下の手順で行われます。
1. 0 < s1 < q かつ 0 < s2 < q であることを確認します。いずれかの条件に違反する場合、署名は拒否されます。
2. s2_inv = 1/s2 mod q を計算します。
3. 非負整数 u1 と u2 を計算します。ただし、
u1 = h(m) * s2_inv mod q かつ
u2 = s1 * s2_inv mod q です。
4. 楕円曲線上の点 $ R' = alpha^{u1} * Y^{u2} を計算します。
5. R' mod q の x 座標が s1 と等しい場合、署名とメッセージは検証に合格します。そうでない場合、検証は不合格となります。
5.5. KT-IV署名からKT-I署名への変換
メッセージmと公開鍵Yに対するKT-IV署名は、同じメッセージと公開鍵Yに対するKT-I署名に簡単に変換できます。(s1, s2)がメッセージmに対するKT-IV署名である場合、(s1, 1/s2 mod q)は同じメッセージに対するKT-I署名です（HMP1994）。
この変換操作は公開情報のみを使用し、変換前のKT-IV署名の作成者、変換後のKT-I署名の検証者、またはその他の任意のエンティティによって実行できます。
実装は、KT-I署名を計算するためにこの方法を使用してもよい（MAY）。
5.6. 根拠
この節は本仕様の規範的なものではなく、背景情報としてのみ提供されています。
HMP1994 は、ElGamal署名の多くの一般化を提示しています。 同文献の式 (5) は、一般的な署名式を示しています。
A = x_A * B + k * C (mod q)
ここで、x_A は秘密鍵、k は秘密値であり、A、B、C は HMP1994 の表 1 に示されているように、式の型によって決定されます。DSA FIPS186 は、KT-I と同様に EG-I.1 署名方式であり、A = m、B = -r、C = s です。 （ここでは、HMP1994の表記法を用い、第一署名要素をr、第二署名要素をsとする。KT-IおよびKT-IVでは、これらの要素はそれぞれs1およびs2と表記される。秘密鍵x_Aは秘密鍵zに対応する。）署名方程式は m = -r * z + s * k (mod q)である。
KT1994および5.3節の署名法は、EG-IV.1法であり、A = m * s、B = -r * s、C = 1である。署名方程式は m * s = -r * s * z + k (mod q)である。
HMP1994の表1に記載されている関数fおよびgは、単に乗算であり、「第五の一般化」の見出しで説明されている。 上記の式では、メッセージmをビット列から整数へ暗黙的に変換することを利用して計算している。これらの式にはハッシュ関数は示されていないが、10.4節で述べたように、存在偽造攻撃を防ぐために、署名前にメッセージにハッシュ関数を適用する必要がある。
2つの署名方式は、秘密鍵を知らなくても、最初の方式の署名を2番目の方式の署名に効率的に変換でき、またその逆も可能である場合、強い等価性を持つと呼ばれる。
KT-I署名とKT-IV署名は明らかに強い等価性を持つ。
s2=0の有効な署名は、z = -h(m) / s1 mod qとなるため、秘密鍵を漏洩する。この例外的なケースとs1=0の場合のチェックについては、FIPS186に従う。s2=0のチェックはRivest R1992によって提案され、BS1992で議論されている。 KT1994では、楕円曲線点R = (r_x, r_y)のx座標r_xから署名要素s1を計算する際に、「qを超えない正の整数q'」が用いられています。q'の値は、署名検証において、算出された楕円曲線点のx座標とs1の値を比較する際にも用いられます。本稿では、簡略化のためq' = qと表記します。