Skip to main content

4. Utility Functions

Algorithms in this document use the utility functions described below, plus standard arithmetic operations (addition, multiplication, modular reduction, etc.) and elliptic curve point operations (point addition and scalar multiplication).

For security, implementations of these functions SHOULD be constant time: in brief, this means that execution time and memory access patterns SHOULD NOT depend on the values of secret inputs, intermediate values, or outputs. For such constant-time implementations, all arithmetic, comparisons, and assignments MUST also be implemented in constant time. Section 10.3 briefly discusses constant-time security issues.

Guidance on implementing low-level operations (in constant time or otherwise) is beyond the scope of this document; readers should consult standard reference material [MOV96] [CFADLNV05].

  • CMOV(a, b, c): If c is False, CMOV returns a; otherwise, it returns b. For constant-time implementations, this operation must run in a time that is independent of the value of c.

  • AND, OR, NOT, and XOR are standard bitwise logical operators. For constant-time implementations, short-circuit operators MUST be avoided.

  • is_square(x): This function returns True whenever the value x is a square in the field F. By Euler's criterion, this function can be calculated in constant time as

is_square(x) := { True,  if x^((q - 1) / 2) is 0 or 1 in F;
                { False, otherwise.

In certain extension fields, is_square can be computed in constant time more quickly than by the above exponentiation. [AR13] and [S85] describe optimized methods for extension fields. Appendix I.5 gives an optimized straight-line method for GF(p^2).

  • sqrt(x): The sqrt operation is a multi-valued function, i.e., there exist two roots of x in the field F whenever x is square (except when x = 0). To maintain compatibility across implementations while allowing implementors leeway for optimizations, this document does not require sqrt() to return a particular value. Instead, as explained in Section 6.4, any function that calls sqrt also specifies how to determine the correct root.

The preferred way of computing square roots is to fix a deterministic algorithm particular to F. We give several algorithms in Appendix I.

  • sgn0(x): This function returns either 0 or 1 indicating the "sign" of x, where sgn0(x) == 1 just when x is "negative". (In other words, this function always considers 0 to be positive.) Section 4.1 defines this function and discusses its implementation.

  • inv0(x): This function returns the multiplicative inverse of x in F, extended to all of F by fixing inv0(0) == 0. A straightforward way to implement inv0 in constant time is to compute

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

Notice that on input 0, the output is 0 as required. Certain fields may allow faster inversion methods; detailed discussion of such methods is beyond the scope of this document.

  • I2OSP and OS2IP: These functions are used to convert a byte string to and from a non-negative integer as described in [RFC8017]. (Note that these functions operate on byte strings in big-endian byte order.)

  • a || b: denotes the concatenation of byte strings a and b. For example, "ABC" || "DEF" == "ABCDEF".

  • substr(str, sbegin, slen): For a byte string str, this function returns the slen-byte substring starting at position sbegin; positions are zero indexed. For example, substr("ABCDEFG", 2, 3) == "CDE".

  • len(str): For a byte string str, this function returns the length of str in bytes. For example, len("ABC") == 3.

  • strxor(str1, str2): For byte strings str1 and str2, strxor(str1, str2) returns the bitwise XOR of the two strings. For example, strxor("abc", "XYZ") == "9;9" (the strings in this example are ASCII literals, but strxor is defined for arbitrary byte strings). In this document, strxor is only applied to inputs of equal length.

4.1. The sgn0 Function​

This section defines a generic sgn0 implementation that applies to any field F = GF(p^m). It also gives simplified implementations for the cases F = GF(p) and F = GF(p^2).

The definition of the sgn0 function for extension fields relies on the polynomial basis or vector representation of field elements, and iterates over the entire vector representation of the input element. As a result, sgn0 depends on the primitive polynomial used to define the polynomial basis; see Section 8 for more information about this basis, and see Section 2.1 for a discussion of representing elements of extension fields as vectors.

sgn0(x)

Parameters:
- 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).

Input: x, an element of F.
Output: 0 or 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) # Avoid short-circuit logic ops
7.   zero = zero AND zero_i
8. return sign

When m == 1, sgn0 can be significantly simplified:

sgn0_m_eq_1(x)

Input: x, an element of GF(p).
Output: 0 or 1.

Steps:
1. return x mod 2

The case m == 2 is only slightly more complicated:

sgn0_m_eq_2(x)

Input: x, an element of GF(p^2).
Output: 0 or 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) # Avoid short-circuit logic ops
5. return s
Last updated on