3. 決定論的 DSA および ECDSA
決定論的 (EC)DSA は, 値 k がランダムに生成される代わりに, このセクションで説明されるプロセスを通じて取得されることを除いて, 標準的な (EC)DSA 署名生成プロセス (前のセクションで説明) を使用して, 入力メッセージ m に対する (EC)DSA 署名を生成するプロセスです。
セクション 2 で説明した表記法を使用します。
3.1. 構成要素
3.1.1. HMAC
HMAC [RFC2104] はハッシュ関数と秘密鍵を使用した Message Authentication Code (メッセージ認証コード) の構成です。ここでは, 署名生成または検証の前に入力メッセージを処理するために使用されるものと同じハッシュ関数 H を使用して HMAC を使用します。
データ V に対して鍵 K を使用して HMAC を適用するプロセスを次のように表記します:
HMAC_K(V)
3.2. k の生成
入力メッセージ m が与えられた場合, 次のプロセスが適用されます:
a. メッセージ m をハッシュ関数 H を通して処理し, 次を得ます:
h1 = H(m)
(h1 は hlen ビットのシーケンスです)。
b. 設定します:
V = 0x01 0x01 0x01 ... 0x01
V の長さ (ビット単位) が 8*ceil(hlen/8) に等しくなるようにします。例えば, オクテットベースのシステムで H が SHA-256 の場合, V は値 1 の 32 オクテットのシーケンスに設定されます。このステップおよび後続のすべてのステップでは, 入力メッセージを処理するためにステップ 'a' で使用されたものと同じ H 関数を使用することに注意してください。この選択については Section 3.6 でより詳細に説明します。
c. 設定します:
K = 0x00 0x00 0x00 ... 0x00
K の長さ (ビット単位) が 8*ceil(hlen/8) に等しくなるようにします。
d. 設定します:
K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1))
ここで '||' は連結を示します。言い換えると, 次のものを順番に連結したものに対して, 鍵 K を使用して HMAC を計算します: V の現在の値, 値 0 の 8 ビットのシーケンス, (EC)DSA 秘密鍵 x のエンコーディング, およびハッシュされたメッセージ (bits2octets 変換で指定されたように切り詰められ拡張される可能性があります)。HMAC の結果が K の新しい値です。秘密鍵 x は [1, q-1] の範囲にあり, したがって int2octets の適切な入力であり, rlen ビットの出力, すなわちオクテットの整数個 (rlen は 8 の倍数) が得られることに注意してください。
e. 設定します:
V = HMAC_K(V)
f. 設定します:
K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1))
今回は "内部オクテット" が 0x01 であることに注意してください。
g. 設定します:
V = HMAC_K(V)
h. k の適切な値が見つかるまで次のアルゴリズムを適用します:
-
T を空のシーケンスに設定します。T の長さ (ビット単位) を tlen と表記します。したがって, この時点で tlen = 0 です。
-
tlen < qlen の間, 次を実行します:
V = HMAC_K(V)
T = T || V -
計算します:
k = bits2int(T)k の値が [1,q-1] の範囲内にあり, DSA または ECDSA に適している場合 (すなわち, 0 ではない r 値をもたらす場合。Section 3.4 を参照), k の生成は終了です。取得された k の値は DSA または ECDSA で使用されます。そうでない場合, 計算します:
K = HMAC_K(V || 0x00)
V = HMAC_K(V)そしてループします (新しい T を生成しようとします, など)。
k が T から生成されるとき, bits2int の結果は q と比較されますが, q を法として削減されないことに注意してください。値が 1 から q-1 の間にない場合, プロセスはループします。単純なモジュラー削減を実行すると, 署名のセキュリティに有害となる偏りが生じます。
3.3. k の生成の代替的説明
前のセクションで説明されたプロセスは, 実際には [SP800-90A] および [X9.62] の附属書 D で説明されている "HMAC_DRBG" 疑似乱数生成器に由来します。[SP800-90A] の用語を使用すると, k の生成は次のように説明できます:
a. 署名するメッセージの処理に使用されるものと同じハッシュ関数 H でパラメータ化された HMAC を使用して HMAC_DRBG をインスタンス化します。インスタンス化パラメータは:
requested_instantiation_security_strength このパラメータを, H が基本ハッシュ関数として使用される場合に HMAC_DRBG 実装が受け入れる任意の値に設定します。
prediction_resistance_flag このパラメータを "false" に設定します。
personalization_string このパラメータを "Null" (空のビットシーケンス) に設定します。
entropy_input
エントロピー文字列として int2octets(x) を使用します。
nonce
ノンスとして bits2octets(H(m)) を使用します。
最後の2つのパラメータは HMAC_DRBG インスタンス化関数自体のパラメータではないことに注意してください。むしろ, これらの値はインスタンス化中に内部 Get_entropy_input 関数から要求されます。決定論的 (EC)DSA では, 実際のエントロピーソースにアクセスせずに, 指定したエントロピー文字列とノンスで HMAC_DRBG を実行させたいと考えています。
b. HMAC_DRBG から qlen ビットを要求し, 結果のビットを bits2int 変換を使用して整数に変換することにより, k の候補値を生成します。ゼロではなく, q より小さく, (EC)DSA に適した値が得られるまでこのステップを繰り返します (セクション 3.4 を参照)。
各署名生成プロセスに対して新しい HMAC_DRBG インスタンスをインスタンス化することに注意してください。ビットの生成時に "パーソナライゼーション文字列" も "追加入力" もありません。HMAC_DRBG のリシード関数は, 外部からも内部 HMAC_DRBG 処理の結果としても呼び出されません。
上記のように, 秘密鍵のエンコーディングを "エントロピー文字列" として使用し, ハッシュ化されたメッセージ (bits2octets によって切り捨てられ拡張される) を "ノンス" として使用します。HMAC_DRBG では, エントロピー文字列とノンスは単純に初期シードに連結されるため, "エントロピー" と "ノンス" の分割はかなり恣意的です。それぞれに qlen ビットを使用することは, ほとんどの HMAC_DRBG 実装の入力要件と互換性があるはずです。
3.4. 使用上の注意
DSA または ECDSA の場合, 値 k は署名の前半を計算するために使用され, r と呼ばれます (セクション 2.4 参照)。DSA および ECDSA 標準は, r がゼロの場合, 新しい k を選択する必要があると規定しています。このような状況では, この文書は値 k が "不適切" であり, 生成プロセスはループし続けるべきであると指定しています。
このイベントは極めて起こりにくいです。実際, r のゼロ値につながる秘密鍵とメッセージを見つけるには, かなりの計算作業 (ハッシュ関数の原像抵抗性を破ることに類似) が必要になります。したがって, 純粋な偶然でそのようなケースに遭遇することは起こりそうにないと考えられ, 攻撃者は注意深く作成されたメッセージでそれを強制することはできません。実際には, そのようなコードパスはトリガーされず, したがって最小限の最適化で実装できます。
3.5. 根拠
前のセクションで説明されたプロセスは, [X9.62] の附属書 D で "HMAC_DRBG" 疑似乱数生成器を使用して説明されている k の "承認された" 生成プロセスを模倣しています。主な違いは, 疑似乱数生成器 (PRNG) のシードとして秘密鍵 x とハッシュ化されたメッセージ H(m) の連結を使用することです。n ビットの "セキュリティレベル" を使用する場合, HMAC_DRBG は少なくとも n+64 ビットのシードエントロピーで使用する必要があります。ただし, 鍵 x もそれだけのエントロピーで生成されているべきであり, x の長さは qlen であり, 少なくとも 2*n に等しく, したがって n+64 より大きいです (標準で指定されているように, DSA および ECDSA は qlen >= 160 を必要とします)。したがって, 決定論的 ECDSA は [X9.62] の附属書 D のエントロピー要件を満たすと主張できます。
統合を容易にするために, H(m) の代わりに bits2octets(H(m)) を使用します。実際, 多くの既存の署名システムはメッセージのハッシュをオフロードします。署名エンジン (秘密鍵にアクセスできる) は H(m) のみを受け取ります。データ帯域幅が制限されている一部のアプリケーションでは, bits2int 変換が後続のビットをいずれにせよ無視するという根拠に基づいて, H(m) の最初の qlen ビットのみが署名エンジンに送信されます。おそらく一部のシステムでは, 切り捨てられた H(m) は外部で q を法として削減される可能性があります。これは (EC)DSA がハッシュ化されたメッセージで最初に行うことだからです。bits2octets の定義により, 決定論的 (EC)DSA は同じ入力で適用できます。
3.6. バリアント
決定論的 (EC)DSA の仕様の多くの部分はかなり恣意的ですが, 相互運用性の理由で選択が行われました。このセクションでは, いくつかの可能なバリアントについて説明します。
使用されるハッシュ関数 H は, 署名生成プロセスで2つの異なる目的に使用されます: 最初に入力メッセージを処理し, 次に HMAC の基礎として (それ自体もハッシュ関数です)。この文書では, 両方の用途に同じハッシュ関数を使用することを指定しています。ただし, これは必須ではありません。これら2つの役割に異なる関数を使用することは可能です。主な欠点は, テストベクトルがすべての組み合わせをカバーできないことです。単一のハッシュ関数を使用すると, 相互運用性テストが簡素化されます。
int2octets と bits2octets の定義は rlen ビット (つまり qlen を次の 8 の倍数に切り上げたもの) の出力につながり, 使用時に実際に最大で qlen ビットのエントロピーを生成します。正確に qlen ビットを出力するように同じ関数を定義することは可能でしょう。ただし, 多くのプログラミング言語やフレームワークはビットシーケンスではなくオクテットのシーケンスで動作する傾向があるため, 実装がわずかに複雑になります。一方, qlen の切り上げは最大で 7 ビットを追加し, PRNG シードのコンテキストでは無視できます。
この仕様では, k (bits2int を介して T から取得) が適切な範囲にない場合, または r のゼロ値を生成する場合の特殊なケースでループするプロセスを規定しています。ただし, これらのケースはどちらも実際には発生しません。後者のケース (計算された r がゼロ) は, ソフトウェアバグ (たとえば, プログラム実行中に楕円曲線パラメータが破損する) によってのみ発生する可能性があります。したがって, 実装はループする代わりに, そのようなケースを回復不可能なエラーとして扱い, 署名計算を単純に中止することを選択できます。