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

4. ユーティリティ関数 (Utility Functions)

本文書のアルゴリズムは、以下に述べるユーティリティ関数に加えて、標準的な算術演算（加算、乗算、剰余簡約など）および楕円曲線の点演算（点の加算とスカラー倍算）を使用します。

セキュリティのため、これらの関数の実装は定数時間であるべきです (SHOULD)。簡潔に言えば、これは実行時間およびメモリアクセスパターンが、秘密の入力、中間値、または出力の値に依存すべきでない (SHOULD NOT) ことを意味します。そのような定数時間実装では、すべての算術演算、比較、および代入もまた定数時間で実装されなければなりません (MUST)。第 10.3 節では定数時間に関するセキュリティ上の論点を簡潔に論じます。

低レベル演算を（定数時間で、あるいはそれ以外の方法で）実装する際の指針は本文書の範囲外です。読者は標準的な参考資料 [MOV96] [CFADLNV05] を参照してください。

  • CMOV(a, b, c): c が False であれば CMOV は a を返し、そうでなければ b を返します。定数時間実装では、この演算は c の値に依存しない時間で実行されなければなりません。

  • AND、OR、NOT、および XOR は標準的なビット単位の論理演算子です。定数時間実装では、短絡評価演算子を避けなければなりません (MUST)。

  • is_square(x): この関数は、値 x が体 F における平方数である場合に常に True を返します。オイラーの規準により、この関数は次のように定数時間で計算できます。

is_square(x) := { True,  x^((q - 1) / 2) が F において 0 または 1 である場合;
                { False, それ以外の場合。

ある種の拡大体では、is_square は上記のべき乗計算によるよりも高速に定数時間で計算できます。[AR13] と [S85] は拡大体に対する最適化手法を記述しています。付録 I.5 では GF(p^2) に対する最適化された直線的手法を示します。

  • sqrt(x): sqrt 演算は多価関数です。すなわち、x が平方数である場合（x = 0 の場合を除く）、体 F において x の根は 2 つ存在します。実装間の互換性を保ちつつ、実装者に最適化の余地を与えるため、本文書は sqrt() が特定の値を返すことを要求しません。その代わりに、第 6.4 節で説明するとおり、sqrt を呼び出す各関数が正しい根をどのように決定するかを併せて規定します。

平方根を計算する望ましい方法は、F に固有の決定的アルゴリズムを定めることです。付録 I ではいくつかのアルゴリズムを示します。

  • sgn0(x): この関数は x の「符号」を示す 0 または 1 のいずれかを返します。ここで sgn0(x) == 1 となるのは x が「負」である場合に限られます。（言い換えれば、この関数は常に 0 を正とみなします。）第 4.1 節ではこの関数を定義し、その実装について論じます。

  • inv0(x): この関数は F における x の乗法逆元を返します。ただし inv0(0) == 0 と定めることで F 全体に拡張されています。inv0 を定数時間で実装する素直な方法は、次を計算することです。

inv0(x) := x^(q - 2).

入力が 0 の場合、出力は要求どおり 0 になることに注意してください。ある種の体では、より高速な逆元計算法が利用できる場合があります。そのような手法の詳細な議論は本文書の範囲外です。

  • I2OSP および OS2IP: これらの関数は、[RFC8017] に記述されているとおり、バイト列と非負整数との間の相互変換に用いられます。（これらの関数はビッグエンディアンのバイト順でバイト列を扱うことに注意してください。）

  • a || b: バイト列 a と b の連結を表します。たとえば "ABC" || "DEF" == "ABCDEF" です。

  • substr(str, sbegin, slen): バイト列 str に対して、この関数は位置 sbegin から始まる slen バイトの部分文字列を返します。位置は 0 始まりの添字です。たとえば substr("ABCDEFG", 2, 3) == "CDE" です。

  • len(str): バイト列 str に対して、この関数は str の長さをバイト単位で返します。たとえば len("ABC") == 3 です。

  • strxor(str1, str2): バイト列 str1 と str2 に対して、strxor(str1, str2) は 2 つの文字列のビット単位 XOR を返します。たとえば strxor("abc", "XYZ") == "9;9" です（この例の文字列は ASCII リテラルですが、strxor は任意のバイト列に対して定義されます）。本文書では、strxor は等しい長さの入力に対してのみ適用されます。

4.1. sgn0 関数 (The sgn0 Function)​

本節では、任意の体 F = GF(p^m) に適用できる汎用の sgn0 実装を定義します。また、F = GF(p) および F = GF(p^2) の場合に対する簡略化された実装も示します。

拡大体に対する sgn0 関数の定義は、体の元の多項式基底表現（ベクトル表現）に依拠しており、入力元のベクトル表現全体にわたって反復します。その結果、sgn0 は多項式基底を定義するために用いられる原始多項式に依存します。この基底についてのさらなる情報は第 8 節を、拡大体の元をベクトルとして表現することについての議論は第 2.1 節を参照してください。

sgn0(x)

パラメータ (Parameters):
- F, 標数 p かつ位数 q = p^m の有限体。
- p, F の標数（直上を参照）。
- m, F の拡大次数, m >= 1（直上を参照）。

入力 (Input): x, F の元。
出力 (Output): 0 または 1。

手順 (Steps):
1. sign = 0
2. zero = 1
3. for i in (1, 2, ..., m):
4.   sign_i = x_i mod 2
5.   zero_i = x_i == 0
6.   sign = sign OR (zero AND sign_i) # 短絡評価の論理演算子を避けること
7.   zero = zero AND zero_i
8. return sign

m == 1 の場合、sgn0 は大幅に簡略化できます。

sgn0_m_eq_1(x)

入力 (Input): x, GF(p) の元。
出力 (Output): 0 または 1。

手順 (Steps):
1. return x mod 2

m == 2 の場合も、わずかに複雑になるだけです。

sgn0_m_eq_2(x)

入力 (Input): x, GF(p^2) の元。
出力 (Output): 0 または 1。

手順 (Steps):
1. sign_0 = x_0 mod 2
2. zero_0 = x_0 == 0
3. sign_1 = x_1 mod 2
4. s = sign_0 OR (zero_0 AND sign_1) # 短絡評価の論理演算子を避けること
5. return s
に最終更新