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.根据欧拉判据 (Euler's criterion),此函数可以在常数时间内计算为

is_square(x) := { True,  如果 x^((q - 1) / 2) 在 F 中为 0 或 1;
                { False, 否则.

在某些扩展域中,is_square 可以比上述指数运算更快地在常数时间内计算.[AR13] 和 [S85] 描述了扩展域的优化方法.附录 I.5 给出了 GF(p^2) 的优化直线方法.

sqrt(x): sqrt 运算是一个多值函数 (multi-valued function),即,当 x 是平方数时,在域 F 中存在 x 的两个根(除非 x = 0).为了在保持实现之间兼容性的同时允许实现者进行优化,本文档不要求 sqrt() 返回特定值.相反,如第 6.4 节所述,任何调用 sqrt 的函数还指定如何确定正确的根.

计算平方根的首选方法是固定特定于 F 的确定性算法.我们在附录 I 中给出了几种算法.

sgn0(x): 此函数返回 0 或 1,表示 x 的"符号",其中 sgn0(x) == 1 表示 x 为"负".(换句话说,此函数始终将 0 视为正.)第 4.1 节定义了此函数并讨论了其实现.
inv0(x): 此函数返回 x 在 F 中的乘法逆元,通过固定 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 字节子串;位置从零开始索引.例如,substr("ABCDEFG", 2, 3) == "CDE".
len(str): 对于字节串 str,此函数返回 str 的字节长度.例如,len("ABC") == 3.
strxor(str1, str2): 对于字节串 str1 和 str2,strxor(str1, str2) 返回两个字符串的按位异或.例如,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

4.1. sgn0 函数 (The sgn0 Function)​

4.1. sgn0 函数 (The sgn0 Function)