NAME

BN_GF2m_add, BN_GF2m_sub, BN_GF2m_cmp, BN_GF2m_mod_arr, BN_GF2m_mod, BN_GF2m_mod_mul_arr, BN_GF2m_mod_mul, BN_GF2m_mod_sqr_arr, BN_GF2m_mod_sqr, BN_GF2m_mod_inv, BN_GF2m_mod_inv_arr, BN_GF2m_mod_div, BN_GF2m_mod_div_arr, BN_GF2m_mod_exp_arr, BN_GF2m_mod_exp, BN_GF2m_mod_sqrt_arr, BN_GF2m_mod_sqrt, BN_GF2m_mod_solve_quad_arr, BN_GF2m_mod_solve_quad, BN_GF2m_poly2arr, BN_GF2m_arr2poly — arithmetic in Galois fields of power-of-2 order

SYNOPSIS

#include <openssl/bn.h> int
BN_GF2m_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); int
BN_GF2m_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); int
BN_GF2m_cmp(const BIGNUM *a, const BIGNUM *b); int
BN_GF2m_mod_arr(BIGNUM *r, const BIGNUM *a, const int p[]); int
BN_GF2m_mod(BIGNUM *r, const BIGNUM *a, const BIGNUM *p); int
BN_GF2m_mod_mul_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const int p[], BN_CTX *ctx); int
BN_GF2m_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *p, BN_CTX *ctx); int
BN_GF2m_mod_sqr_arr(BIGNUM *r, const BIGNUM *a, const int p[], BN_CTX *ctx); int
BN_GF2m_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx); int
BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *b, const BIGNUM *p, BN_CTX *ctx); int
BN_GF2m_mod_inv_arr(BIGNUM *r, const BIGNUM *b, const int p[], BN_CTX *ctx); int
BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *p, BN_CTX *ctx); int
BN_GF2m_mod_div_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const int p[], BN_CTX *ctx); int
BN_GF2m_mod_exp_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *exponent, const int p[], BN_CTX *ctx); int
BN_GF2m_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *exponent, const BIGNUM *p, BN_CTX *ctx); int
BN_GF2m_mod_sqrt_arr(BIGNUM *r, const BIGNUM *a, const int p[], BN_CTX *ctx); int
BN_GF2m_mod_sqrt(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx); int
BN_GF2m_mod_solve_quad_arr(BIGNUM *r, const BIGNUM *a, const int p[], BN_CTX *ctx); int
BN_GF2m_mod_solve_quad(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx); int
BN_GF2m_poly2arr(const BIGNUM *poly_in, int arr_out[], int arr_size); int
BN_GF2m_arr2poly(const int arr_in[], BIGNUM *poly_out);

DESCRIPTION

Two fields containing the same, finite number of elements are isomorphic, and the number of elements is called their order. The unique field of a given finite order is called the Galois field of that order. $$ The following functions perform arithmetic operations on $\mathrm{GF}\left(2^m\right)$ , the Galois fields of order $2^m$ , where $m$ is a natural number. The $2^m$ elements of $\mathrm{GF}\left(2^m\right)$ are usually represented by the $2^m$ polynomials of a degrees less than $m$ with binary coefficients. Such a polynomial can either be specified by storing the coefficients in a BIGNUM object, using the $m$ lowest bits with bit numbers corresponding to degrees, or by storing the degrees that have coefficients of 1 in an integer array of at most $m+1$ elements. For the functions below, the array needs to be sorted in decreasing order and terminated by the delimiter element -1. A specific representation of $\mathrm{GF}\left(2^m\right)$ is selected by choosing a polynomial of degree $m$ that is irreducible with binary coefficients, called the reducing polynomial. Making sure that $p$ is of the correct degree and indeed irreducible is the responsibility of the user. Typically, the following functions silently produce nonsensical results when given a p argument that is of the wrong degree or that is reducible. Storing the reducing polynomial requires $m+1$ bits in a BIGNUM object or an int array of up to $m+2$ elements, including the terminating -1 element. All functions produce correct results even if some or all of the arguments r, a, and b point to the same object. BN_GF2m_add() adds the two polynomials a and b with binary coefficients, which is equivalent to a pairwise exclusive OR operation on the coefficients, and places the result into r. In particular, if a and b are elements of the same representation of the same $\mathrm{GF}\left(2^m\right)$ field, the sum of both in that representation of that field is computed ( $r=a+b$ ). In contrast to most of the other functions described here, no modulo operation is performed. Consequently, if the degree of at least one of the arguments may be larger than or equal to $m$ , a follow-up call to BN_GF2m_mod_arr() or BN_GF2m_mod() may occasionally be useful. BN_GF2m_sub() calculates the difference of a and b ( $r=a-b=a+b$ ). Since -1 is the same as 1 in binary arithmetic, BN_GF2m_sub() does exactly the same as BN_GF2m_add(). It is implemented as a macro. BN_GF2m_cmp() is an alias for BN_ucmp(3). Despite its name, it does not attempt to find out whether the two polynomials belong to the same congruence class with respect to some Galois field. BN_GF2m_mod_arr() and its wrapper BN_GF2m_mod() divide the polynomial with binary coefficients a by the polynomial with binary coefficients p and place the remainder into r ( $r=a(\mathrm{mod}p)$ ). If r and a point to the same object, the modular reduction is done in place. BN_GF2m_mod_mul_arr() and its wrapper BN_GF2m_mod_mul() multiply a and b, divide the result by p, and place the remainder in r ( $r=a*b(\mathrm{mod}p)$ ). BN_GF2m_mod_sqr_arr() and its wrapper BN_GF2m_mod_sqr() divide the square of a by p and place the remainder in r ( $r=a*a(\mathrm{mod}p)$ ). BN_GF2m_mod_inv() and its wrapper BN_GF2m_mod_inv_arr() reduce b modulo p, find the multiplicative inverse element in $\mathrm{GF}\left(2^m\right)$ using the reducing polynomial $p$ , and place the result into r ( $r=1/b(\mathrm{mod}p)$ ). BN_GF2m_mod_div() and its wrapper BN_GF2m_mod_div_arr() reduce a and b modulo p, compute their quotient in $\mathrm{GF}\left(2^m\right)$ using the reducing polynomial $p$ , and place the result into r ( $r=a/b(\mathrm{mod}p)$ ). BN_GF2m_mod_exp_arr() and its wrapper BN_GF2m_mod_exp() reduce a modulo p, raise it to the power of exponent in $\mathrm{GF}\left(2^m\right)$ using the reducing polynomial $p$ , and place the result into r ( $r=a^{\mathrm{exponent}}(\mathrm{mod}p)$ ). BN_GF2m_mod_sqrt_arr() and its wrapper BN_GF2m_mod_sqrt() reduce a modulo p, calculate the square root in $\mathrm{GF}\left(2^m\right)$ using the reducing polynomial $p$ by raising it to the power of $2^{m-1}$ , and place the result into r ( $r=\sqrt{a}(\mathrm{mod}p)$ ). This works because of the identity $a^{2^m}=a$ which holds for all field elements $a$ . BN_GF2m_mod_solve_quad_arr() and its wrapper BN_GF2m_mod_solve_quad() reduce a modulo p, solve the quadratic equation $r^2+r=a(\mathrm{mod}p)$ in $\mathrm{GF}\left(2^m\right)$ using the reducing polynomial $p$ , and place the solution into r. BN_GF2m_poly2arr() converts a polynomial from a bit string stored in the BIGNUM object poly_in to an array containing the degrees of the non-zero terms. It is the responsibility of the caller to provide an array arr_out of sufficient size and to provide the number of elements that can be stored in the array as the arr_size argument. The array is filled with the degrees in decreasing order, followed by an element with the value -1. BN_GF2m_arr2poly() converts a polynomial from the array arr_in containing degrees to a bit string placed in the BIGNUM object poly_out. It is the responsibility of the caller to provide the storage for poly_out and to make sure that arr_in is terminated with a -1 element.

RETURN VALUES

BN_GF2m_cmp() interprets a and b as integer numbers and returns -1 if $\left|a\right|<\left|b\right|$ , 0 if $\left|a\right|=\left|b\right|$ , or 1 if $\left|a\right|>\left|b\right|$ . BN_GF2m_poly2arr() returns:

• 0 if poly_in has the value 0;
• a number in the range from 2 to arr_size, inclusive, in case of success, specifying the number of elements that have been stored into the array;
• a number greater than arr_size if the function failed because the array was too small, specifying the array size that would have been needed.

The other functions return 1 for success or 0 for failure.

ERRORS

After some cases of failure, the following diagnostics can be retrieved with ERR_get_error(3), ERR_GET_REASON(3), and ERR_reason_error_string(3):

BN_R_NO_SOLUTION “no solution”

No solution exists for the equation that BN_GF2m_mod_solve_quad_arr() or BN_GF2m_mod_solve_quad() attempted to solve.

BN_R_INVALID_LENGTH “invalid length”

In one of the functions wrapping an *_arr() variant, the BIGNUM *p argument had a value of zero.

SEE ALSO

BN_add(3), BN_CTX_new(3), BN_new(3), BN_set_bit(3), EC_POINT_new(3) Darrel Hankerson, Julio López Hernandez, and Alfred Menezes, Software Implementation of Elliptic Curve Cryptography over Binary Fields, CHES 2000: International Workshop on Cryptographic Hardware and Embedded Systems, Springer, Lecture Notes in Computer Science, vol 1965, https://doi.org/10.1007/3-540-44499-8_1, Worcester, MA, USA, August 2000, Algorithm 10: Modified Almost Inverse Algorithm for inversion in FP(2^m). Specifications for Public-Key Cryptography, IEEE Standard 1363, https://doi.org/10.1109/IEEESTD.2000.92292, August 29, 2000, square-and-multiply algorithm A.5.1 for exponentiation, exponentiation algorithm A.4.1 for square roots, and algorithms A.4.7 and A.4.6 for the quadratic equation.