メインコンテンツまでスキップ

2. DSA および ECDSA の表記法

このセクションでは, DSA および ECDSA を簡潔に説明し, 表記法を定義します。DSA および ECDSA の完全な仕様は, それぞれ [FIPS-186-4] および [X9.62] にあります。

2.1. 鍵パラメータ​

DSA および ECDSA は素数サイズの大きな群に対して動作します。この群では, 群演算は計算が容易ですが, 離散対数は既存および予見可能な技術では計算上実行不可能です。群の定義は "鍵パラメータ" と呼ばれます。鍵パラメータは, セキュリティに悪影響を与えることなく異なる鍵ペア間で共有できます。これは特に ECDSA において通常のケースです。

DSA は以下の鍵パラメータを使用します:

p: 大きな素数 (少なくとも 1024 ビット)

q: 十分に大きな素数 (少なくとも 160 ビット) であり, p-1 の約数でもあります

g: p を法とする整数の位数 q の乗法的部分群の生成元

DSA が計算される群は, 値 'g^j mod p' から構成されます。ここで '^' は冪乗を示し, j は 0 から q-1 (両端を含む) までの範囲です。群のサイズは q です。

ECDSA は以下の鍵パラメータを使用します:

E: 与えられた有限体上で定義された楕円曲線

q: 十分に大きな素数 (少なくとも 160 ビット) であり, 曲線の位数の約数です

G: 位数 q の E の点

ECDSA が計算される群は, 曲線上の点 jG (点 G と整数 j の乗算) から構成されます。ここで j は 0 から q-1 までの範囲です。G は qG = 0 (曲線 E 上の "無限遠点") となるような点です。群のサイズは q です。これらの表記法は [X9.62] に記載されているものとはわずかに異なることに注意してください。DSA に使用される表記法と一致させるためにこれらを使用しています。

2.2. 鍵ペア​

DSA または ECDSA の秘密鍵は, q を法として取られた整数 x です。関連する標準は x が 0 であってはならないと規定しています。したがって, x は範囲 [1, q-1] の整数です。

DSA または ECDSA の公開鍵は, 秘密鍵 x と鍵パラメータから計算されます:

  • DSA の場合, 公開鍵は整数です: y = g^x mod p

  • ECDSA の場合, 公開鍵は曲線上の点です: U = xG

2.3. 整数変換​

qlen を q の2進数の長さとします。qlen は, q が 2^qlen よりも小さくなる最小の整数です。これは符号ビットなしの q の2進表現のサイズです (q は大きな素数であるため奇数であり, 2の累乗に等しい整数の長さに関する曖昧さを回避します)。ビット列, オクテット列, および q を法とする整数に対して動作する5つの変換関数を定義します。qlen はこれらの変換の主要なパラメータです。

以下のサブセクションでは, blen および rlen と呼ばれる2つの他の長さを使用します。rlen は qlen を8の次の倍数に切り上げた値に等しくなります (qlen がすでに8の倍数である場合, rlen は qlen に等しくなります。そうでない場合, rlen はわずかに大きく, qlen+7 まで大きくなります)。rlen は生成された署名の前半である値 r とは無関係であることに注意してください。blen はビットの入力シーケンスの長さ (ビット単位) であり, 呼び出し間で変化する可能性があります。blen は qlen よりも小さい, 等しい, または大きい場合があります。

2.3.1. ビットとオクテット​

形式的には, すべての操作はビットのシーケンスに対して定義されます。シーケンスは順序付けられており, 最初のビットは左端と呼ばれ, 最後のビットは右端と呼ばれます。

ほとんどのソフトウェアシステムでは, ビットはオクテット (8ビットのシーケンス) にグループ化されます。バイナリデータ, 例えばハッシュ関数の出力は, オクテットのシーケンスとして利用可能です。該当する場合, オクテット内のビットは最上位から最下位の順に並んでいると見なします: オクテット内の最初 (左端) のビットは数値 128 を持ち, 最後 (右端) のビットは数値 1 を持ちます。

2.3.2. ビット列から整数へ​

bits2int 変換は, blen ビットのシーケンスを入力として受け取り, 2^qlen よりも小さい非負整数を出力します。これは以下のステップから構成されます:

  1. シーケンスは最初に長さ qlen に切り詰められるか拡張されます:

    • qlen < blen の場合, qlen 個の左端のビットが保持され, 後続のビットは破棄されます。

    • そうでない場合, qlen-blen 個のビット (値ゼロ) がシーケンスの左側に追加されます (つまり, シーケンス順序で入力ビットの前に)。

  2. 結果のシーケンスは, ビッグエンディアン規則を使用して整数値に変換されます: 入力ビットが b_0 (左端) から b_(qlen-1) (右端) と呼ばれる場合, 結果の値は次のようになります:

    b_0*2^(qlen-1) + b_1*2^(qlen-2) + ... + b_(qlen-1)*2^0

bits2int 変換は次の方法でも説明できます: 入力ビットシーケンス (長さ blen) はビッグエンディアン規則を使用して整数に変換されます。次に, blen が qlen よりも大きい場合, 結果の整数は blen-qlen を2で累乗した値で除算されます (ユークリッド除算: 余りは破棄されます)。大きな整数の算術演算の多くのソフトウェア実装では, その除算は blen-qlen ビットによる "右シフト" に相当します。

2.3.3. 整数からオクテット列へ​

q よりも小さい整数値 x (特に, q を法として取られた値) は, rlen ビットのシーケンスに変換できます。ここで rlen = 8*ceil(qlen/8) です。これはビッグエンディアンエンコーディングによって得られるビットのシーケンスです。言い換えると, シーケンスビット x_i (i が 0 から rlen-1 までの範囲) は次のようになります:

x = x_0*2^(rlen-1) + x_1*2^(rlen-2) + ... + x_(rlen-1)

この変換を int2octets と呼びます。rlen は 8 の倍数 (qlen より小さくない 8 の最小の倍数) であるため, 結果のビットシーケンスもオクテットのシーケンスであり, そのため名前がつけられています。

2.3.4. ビット列からオクテット列へ​

bits2octets 変換は, blen ビットのシーケンスを入力として受け取り, rlen ビットのシーケンスを出力します。これは以下のステップから構成されます:

  1. 入力シーケンス b は bits2int 変換を通じて整数値 z1 に変換されます:

    z1 = bits2int(b)

  2. z1 は q を法として削減され, z2 (0 から q-1 の間の整数, 両端を含む) が得られます:

    z2 = z1 mod q

    z1 が 2^qlen よりも小さいため, そのモジュラー削減は単純な条件付き減算で実装できることに注意してください: その値が非負である場合 z2 = z1-q, そうでない場合 z2 = z1。

  3. z2 は int2octets を適用することにより, オクテットのシーケンス (rlen ビットのシーケンス) に変換されます。

2.3.5. 使用法​

int2octets は, 長さ qlen の入力シーケンスに対してさえ, bits2int の逆ではないことに注意する価値があります: int2octets は左側にいくつかのビットを追加し, bits2int は右側のいくつかのビットを破棄します。int2octets が bits2int の逆であるのは, qlen が 8 の倍数であり, ビットシーケンスがすでに長さ qlen を持っている場合のみです。

bits2int は, 標準的な DSA および ECDSA における署名生成および検証中に使用され, ハッシュ値 (入力メッセージに対して計算された) を q を法とする整数に変換します。つまり, bits2int を通じて得られた整数はさらに q を法として削減されます。その整数は 2^qlen よりも小さいため, その削減は最大で1回の減算で実行できます。

int2octets は SEC 1 [SEC1] のセクション 2.3.7 において "Integer-to-OctetString" という名前で定義されています。これは ASN.1 ベースの構造内での ECDSA 秘密鍵 (x) のエンコーディングの仕様で使用されます。

bits2octets は標準的な DSA または ECDSA では使用されません。決定論的 (EC)DSA の仕様で使用します。

2.4. 署名生成​

署名生成は暗号学的ハッシュ関数 H と入力メッセージ m を使用します。メッセージは最初に H によって処理され, 値 H(m) が得られます。これは長さ hlen のビットのシーケンスです。通常, H はその出力長 hlen が qlen にほぼ等しくなるように選択されます。これは署名スキームの全体的なセキュリティが hlen と qlen のうち小さい方に依存するためです。ただし, 関連する標準は hlen と qlen のすべての組み合わせをサポートします。

次のステップが適用されます:

  1. H(m) は bits2int 変換と追加のモジュラー削減を使用して, q を法とする整数に変換されます:

    h = bits2int(H(m)) mod q

    bits2octets の説明で述べたように, 追加のモジュラー削減は条件付き減算以上のものではありません。

  2. k と呼ばれる q を法とするランダム値が生成されます。この値は 0 であってはなりません。したがって, 範囲 [1, q-1] にあります。この文書の残りのほとんどは k を生成するために使用されるプロセスを中心に展開されます。プレーンな DSA または ECDSA では, k は q-1 個の可能な値の中から一様な確率で値を選択するランダム選択を通じて選択されるべきです。

  3. 値 r (q を法とする) が k と鍵パラメータから計算されます:

    • DSA の場合:

      r = g^k mod p mod q

      (冪乗は p を法として実行され, 0 から p-1 の間の数値が得られ, それがさらに q を法として削減されます。)

    • ECDSA の場合: 点 kG が計算されます。その X 座標 (E が定義されている体のメンバー) は整数に変換され, q を法として削減され, r が得られます。

    r がゼロになった場合, 新しい k を選択し, r を再度計算する必要があります (これは極めてありえない発生です)。

  4. 値 s (q を法とする) が計算されます:

    s = (h+x*r)/k mod q

    ペア (r, s) が署名です。署名をどのようにエンコードするかは DSA および ECDSA 標準自体ではカバーされていません。一般的な方法は DER エンコードされた ASN.1 構造 (r と s の2つの INTEGER の SEQUENCE, この順序で) を使用することです。