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

5. 有限体へのハッシュ

hash_to_field 関数は、任意の長さのバイト文字列 msg を体 F の1つ以上の要素にハッシュします。この関数は2つのステップで動作します。まず、入力バイト文字列をハッシュして一様ランダムなバイト文字列を生成し、次にこのバイト文字列を F の1つ以上の要素として解釈します。

最初のステップでは、hash_to_field は補助関数 expand_message を呼び出します。この文書では、expand_message の2つのバリアントを定義しています。1つは SHA-2 [FIPS180-4] や SHA-3 [FIPS202] などのハッシュ関数に適したもの、もう1つは SHAKE128 [FIPS202] などの拡張可能出力関数（XOF）に適したものです。各 expand_message バリアントのセキュリティ上の考慮事項については後述します（第5.3.1節および第5.3.2節）。

実装者は、hash_to_field 関数が定数時間（constant-time）実装に適していることを保証するために、F の一様ランダムな要素を生成する際に棄却サンプリング（rejection sampling）を使用してはなりません（MUST NOT）。その理由は、棄却サンプリングの手順を定数時間で実装することは困難であり、後の良かれと思った「最適化」によって実装が気づかないうちに非定数時間になってしまう可能性があるためです。これは、棄却サンプリングに基づく hash_to_field 関数は、定数時間の実装と互換性がないことを意味します。

hash_to_field 関数は、スカラーへの安全なハッシュにも適しています。例えば、素数位数 r の楕円曲線（部分）群のスカラー体へハッシュする場合、ターゲット体 GF(r) を使用して hash_to_field をインスタンス化するだけで十分です。

expand_message（第5.3節）がランダムオラクルとしてモデル化されている場合、hash_to_field 関数はランダムオラクル [MRH04] と識別不能になるように設計されています（識別不能性の詳細については第10.5節を参照）。識別不能性の確保には注意が必要です。その理由を知るために、3/4 * 2^256 に近い素数 p を考えてみましょう。ランダムな 256 ビット整数をこの p でモジュロ削減すると、[0, p / 3] の範囲の値がおよそ 1/2 の確率で得られます。これは、その値が [0, p - 1] において統計的に一様分布から遠いことを意味します。

バイアスを制御するために、hash_to_field は代わりに、少なくとも ceil(log2(p)) + k ビットの長さを持つランダムな整数を使用します。ここで k はスイートのターゲットセキュリティレベル（ビット単位）です。このような整数を p でモジュロ削減すると、任意の p に対して最大で 2^-k のバイアスが生じます。このバイアスは、k ビットのセキュリティをターゲットとする場合に適切です。各整数に対して、hash_to_field は expand_message を使用して L バイトの一様なバイトを取得します。ここで、

L = ceil((ceil(log2(p)) + k) / 8)

です。その後、これらの一様なバイトを OS2IP によって整数として解釈します。例えば、255 ビットの素数 p と k = 128 ビットのセキュリティの場合、L = ceil((255 + 128) / 8) = 48 バイトとなります。

k は対応する曲線のセキュリティレベルの上限であることに注意してください。詳細については第10.8節、特定の曲線に対する k の選択ガイドラインについては第8.9節を参照してください。

5.1. 拡大体における効率の考慮​

この節で説明する hash_to_field 関数は、一部の拡大体に対して非効率的です。具体的には、拡大体 GF(p^m) の要素にハッシュする場合、hash_to_field は msg を m * L バイト（上記で定義された L）に拡張する必要があります。log2(p) がセキュリティレベル k より大幅に小さい拡大体の場合、このアプローチは非効率的です。なぜなら、GF(p^m) の要素を生成し、バイアスを最大で 2^-k に抑えるには m * log2(p) + k バイトで十分であるのに対し、expand_message に約 m * log2(p) + m * k ビットの出力を要求するためです。このような場合、以下のセキュリティ要件を満たすのであれば、アプリケーションは代替の hash_to_field 関数を使用できます。

  • 関数は、最大で 2^-k のバイアスを除いて一様ランダムな体要素を1つ以上出力しなければならない。

  • 関数は棄却サンプリングを使用してはならない。

  • 関数は直線実装（straight-line implementation）に適しているべきである。

例えば、Pornin [P20] は、これらの要件を満たしつつ、hash_to_field がその体に使用するよりも少ない expand_message 出力ビットを使用して GF(9767^19) にハッシュする方法を説明しています。

5.2. hash_to_field の実装​

以下の手順で hash_to_field を実装します。

この関数の expand_message 引数は、第5.3節で示される要件に準拠しなければなりません。第3.1節では、DST（ドメイン分離タグ）を構築するために必要な方法について説明しています。expand_message が失敗した場合、hash_to_field は中断（ABORT）する可能性があることに注意してください。

hash_to_field(msg, count)

Parameters:
- DST, a domain separation tag (see Section 3.1).
- F, a finite field of characteristic p and order q = p^m.
- p, the characteristic of F (see immediately above).
- m, the extension degree of F, m >= 1 (see immediately above).
- L = ceil((ceil(log2(p)) + k) / 8), where k is the security
  parameter of the suite (e.g., k = 128).
- expand_message, a function that expands a byte string and
  domain separation tag into a uniformly random byte string
  (see Section 5.3).

Input:
- msg, a byte string containing the message to hash.
- count, the number of elements of F to output.

Output:
- (u_0, ..., u_(count - 1)), a list of field elements.

Steps:
1. len_in_bytes = count * m * L
2. uniform_bytes = expand_message(msg, DST, len_in_bytes)
3. for i in (0, ..., count - 1):
4.   for j in (0, ..., m - 1):
5.     elm_offset = L * (j + i * m)
6.     tv = substr(uniform_bytes, elm_offset, L)
7.     e_j = OS2IP(tv) mod p
8.   u_i = (e_0, ..., e_(m - 1))
9. return (u_0, ..., u_(count - 1))

5.3. expand_message​

expand_message は、一様ランダムなバイト文字列を生成するための関数です。これは3つの引数を受け取ります。

  1. msg：ハッシュするメッセージを含むバイト文字列、

  2. DST：ドメイン分離タグとして機能するバイト文字列、および

  3. len_in_bytes：生成するバイト数。

この文書では、expand_message の以下の2つのバリアントを定義しています。

  • expand_message_xmd（第5.3.1節）は、SHA-2 [FIPS180-4]、SHA-3 [FIPS202]、BLAKE2 [RFC7693] などを含む様々なハッシュ関数に適しています。
  • expand_message_xof（第5.3.2節）は、SHAKE [FIPS202] や BLAKE2X [BLAKE2X] ファミリーの関数などの拡張可能出力関数（XOF）に適しています。

これらのバリアントは大多数のユースケースに十分であるはずですが、他のバリアントが存在する場合もあります。第5.3.4節で要件について説明します。

5.3.1. expand_message_xmd​

expand_message_xmd 関数は、b ビットを出力する暗号ハッシュ関数 H を使用して、一様ランダムなバイト文字列を生成します。セキュリティのため、H は以下の要件を満たさなければなりません。

  • H の出力ビット数は b >= 2 * k でなければならず（k はビット単位のターゲットセキュリティレベル）、b は 8 で割り切れなければならない。最初の要件は k ビットの衝突耐性を保証し、2番目の要件は expand_message_xmd 出力の一様性を保証する。

  • H は SHA-2 のような Merkle-Damgaard ハッシュ関数であってもよい。その場合、基礎となる圧縮関数がランダムオラクルとしてモデル化されているとき、セキュリティが維持される [CDMP05]。（議論については第10.6節を参照。）

  • H は SHA-3 や BLAKE2 のようなスポンジベースのハッシュ関数であってもよい。その場合、内部関数がランダム置換またはランダム置換としてモデル化されているとき、セキュリティが維持される [BDPV08]。

  • それ以外の場合、H は妥当な暗号学的仮定の下でランダムオラクルと識別不能であることが証明されている [MRH04] ハッシュ関数でなければならない。

SHA-2 [FIPS180-4] および SHA-3 [FIPS202] は典型的かつ推奨される選択肢です。例えば、128 ビットのセキュリティレベルの場合、b >= 256 ビットとなり、SHA-256 または SHA3-256 が適切な選択肢となります。

ハッシュ関数 H は、固定長のデータブロックを繰り返し取り込むことで動作すると想定されます。これらのブロックのビット長を「入力ブロックサイズ (s)」と呼びます。例えば、SHA-512 [FIPS180-4] の場合は s = 1024、SHA3-512 [FIPS202] の場合は s = 576 です。正当性のために、H は b <= s を要求します。

以下の手順で expand_message_xmd を実装します。

expand_message_xmd(msg, DST, len_in_bytes)

Parameters:
- H, a hash function (see requirements above).
- b_in_bytes, b / 8 for b the output size of H in bits.
  For example, for b = 256, b_in_bytes = 32.
- s_in_bytes, the input block size of H, measured in bytes (see
  discussion above). For example, for SHA-256, s_in_bytes = 64.

Input:
- msg, a byte string.
- DST, a byte string of at most 255 bytes.
  See below for information on using longer DSTs.
- len_in_bytes, the length of the requested output in bytes,
  not greater than the lesser of (255 * b_in_bytes) or 2^16-1.

Output:
- uniform_bytes, a byte string.

Steps:
1.  ell = ceil(len_in_bytes / b_in_bytes)
2.  ABORT if ell > 255 or len_in_bytes > 65535 or len(DST) > 255
3.  DST_prime = DST || I2OSP(len(DST), 1)
4.  Z_pad = I2OSP(0, s_in_bytes)
5.  l_i_b_str = I2OSP(len_in_bytes, 2)
6.  msg_prime = Z_pad || msg || l_i_b_str || I2OSP(0, 1) || DST_prime
7.  b_0 = H(msg_prime)
8.  b_1 = H(b_0 || I2OSP(1, 1) || DST_prime)
9.  for i in (2, ..., ell):
10.    b_i = H(strxor(b_0, b_(i - 1)) || I2OSP(i, 1) || DST_prime)
11. uniform_bytes = b_1 || ... || b_ell
12. return substr(uniform_bytes, 0, len_in_bytes)

b_0 を計算する前（ステップ7）に、文字列 Z_pad（ステップ6）が msg の前に付加されることに注意してください。H が Merkle-Damgaard ハッシュ（SHA-2 など）である場合、これはセキュリティのために必要です（第10.6節を参照）。これらの追加データをハッシュすることは、b_0 の計算コストが単に H(msg) を計算するコストよりも高くなることを意味します。ほとんどの設定では、H を評価するコストは楕円曲線へのハッシュに関わる他のコストよりもはるかに小さいため、このオーバーヘッドは無視できます。

ただし、Z_pad が H にのみ依存し、expand_message_xmd のパラメータには依存しないという事実を利用することで、このオーバーヘッドを完全に回避できます。そのためには、まず Z_pad を取り込んだ後の H の内部状態を事前計算して保存しておきます。その後、b_0 を計算する際に、保存された状態を使用して H を初期化します。さらなる詳細は実装に依存し、この文書の範囲外です。

5.3.2. expand_message_xof​

expand_message_xof 関数は、拡張可能出力関数（XOF）H を使用して、一様ランダムなバイト文字列を生成します。セキュリティのため、H は以下の基準を満たさなければなりません。

  • H の衝突耐性は少なくとも k ビットでなければならない。

  • H は、妥当な暗号学的仮定の下でランダムオラクルと識別不能であることが証明されている XOF でなければならない。

SHAKE XOF ファミリー [FIPS202] は典型的かつ推奨される選択肢です。例えば、128 ビットのセキュリティの場合、SHAKE128 が適切な選択肢となります。

以下の手順で expand_message_xof を実装します。

expand_message_xof(msg, DST, len_in_bytes)

Parameters:
- H(m, d), an extendable-output function that processes
  input message m and returns d bytes.

Input:
- msg, a byte string.
- DST, a byte string of at most 255 bytes.
  See below for information on using longer DSTs.
- len_in_bytes, the length of the requested output in bytes.

Output:
- uniform_bytes, a byte string.

Steps:
1. ABORT if len_in_bytes > 65535 or len(DST) > 255
2. DST_prime = DST || I2OSP(len(DST), 1)
3. msg_prime = msg || I2OSP(len_in_bytes, 2) || DST_prime
4. uniform_bytes = H(msg_prime, len_in_bytes)
5. return uniform_bytes

5.3.3. 255 バイトを超える DST の使用​

この節で定義された expand_message バリアントは、最大 255 バイトのドメイン分離タグを受け入れます。アプリケーションが呼び出しプロトコルによって課される要件などのために 255 バイトを超えるドメイン分離タグを必要とする場合、実装者は以下のようにハッシュによって短いドメイン分離タグを計算しなければなりません。

  • ハッシュ関数 H を使用する expand_message_xmd の場合、DST は次のように計算されます。

    DST = H("H2C-OVERSIZE-DST-" || a_very_long_DST)

  • 拡張可能出力関数 H を使用する expand_message_xof の場合、DST は次のように計算されます。

    DST = H("H2C-OVERSIZE-DST-" || a_very_long_DST, ceil(2 * k / 8))

ここで、a_very_long_DST は 255 バイトを超える長さの DST であり、"H2C-OVERSIZE-DST-" は 17 バイトの ASCII 文字文字列リテラル、k はビット単位のターゲットセキュリティレベルです。

5.3.4. 他の expand_message バリアントの定義​

新しい expand_message バリアントを定義する際の最も重要な考慮事項は、hash_to_field が expand_message をランダムオラクルとしてモデル化することです。したがって、実装者は基礎となる暗号プリミティブに関する適切な仮定の下でランダムオラクルと識別不能であることを証明すべきです。詳細については第10.5節を参照してください。

さらに、expand_message バリアントは以下の要件を満たさなければなりません。

  • ターゲットとなる楕円曲線のセキュリティレベルに見合った衝突耐性を提供しなければならない。

  • 暗号学的なランダム性を必要とするアプリケーション向けに設計されたプリミティブの上に構築されなければならない。例えば、安全なストリーム暗号は適切なプリミティブですが、メルセンヌ・ツイスタ疑似乱数生成器 [MT98] は不適切です。

  • 棄却サンプリングを使用してはならない。

  • 異なる (msg, DST, length) の入力に対して独立した値を与えなければならない。この要件を満たすことは微妙です。簡単な例として、msg || DST をハッシュすることは機能しません。なぜなら、この場合、連結すると等しくなる異なる (msg, DST) のペアは同じ出力を返すためです（例えば、("AB", "CDEF") と ("ABC", "DEF")）。この文書で定義されているバリアントでは、この問題を避けるために DST のプレフィックスなしエンコーディングを使用しています。

  • ドメイン分離タグ DST を使用して、expand_message 内部の暗号プリミティブの呼び出しが expand_message 外部の呼び出しとドメイン分離されていることを保証しなければならない。例えば、expand_message バリアントがハッシュ関数 H を使用する場合、DST のエンコーディングを H の各呼び出しの入力のプレフィックスまたはサフィックスとして追加しなければならない。DST はサフィックスとして追加することを推奨する。

  • msg が長い場合、効率のために msg を一度だけ読み取るべきである。

さらに、各 expand_message バリアントは、スイート ID でそのバリアントを識別するために使用される一意の EXP_TAG を指定しなければなりません。詳細については第8.10節を参照してください。

に最終更新