finitefield

Finite field operations. More...

Typedefs

typedef struct FiniteField FiniteField
 A finite field.
 
typedef struct FfElement FfElement
 An element in a finite field.
 

Functions

EpidStatus NewFiniteField (BigNumStr const *prime, FiniteField **ff)
 Creates new finite field. More...
 
EpidStatus NewFiniteFieldViaBinomalExtension (FiniteField const *ground_field, FfElement const *ground_element, int degree, FiniteField **ff)
 Creates a new finite field using binomial extension. More...
 
EpidStatus NewFiniteFieldViaPolynomialExtension (FiniteField const *ground_field, BigNumStr const *irr_polynomial, int degree, FiniteField **ff)
 Creates a new finite field using polynomial extension. More...
 
void DeleteFiniteField (FiniteField **ff)
 Frees a previously allocated FiniteField. More...
 
EpidStatus NewFfElement (FiniteField const *ff, FfElement **new_ff_elem)
 Creates a new finite field element. More...
 
void DeleteFfElement (FfElement **ff_elem)
 Frees a previously allocated FfElement. More...
 
EpidStatus ReadFfElement (FiniteField *ff, ConstOctStr ff_elem_str, size_t strlen, FfElement *ff_elem)
 Deserializes a FfElement from a string. More...
 
EpidStatus InitFfElementFromBn (FiniteField *ff, BigNum *bn, FfElement *ff_elem)
 Initializes an existing FfElement from a BigNum. More...
 
EpidStatus WriteFfElement (FiniteField *ff, FfElement const *ff_elem, OctStr ff_elem_str, size_t strlen)
 Serializes a finite field element to a string. More...
 
EpidStatus FfNeg (FiniteField *ff, FfElement const *a, FfElement *r)
 Calculates the additive inverse of a finite field element. More...
 
EpidStatus FfInv (FiniteField *ff, FfElement const *a, FfElement *r)
 Calculates the multiplicative inverse of a finite field element. More...
 
EpidStatus FfAdd (FiniteField *ff, FfElement const *a, FfElement const *b, FfElement *r)
 Adds two finite field elements. More...
 
EpidStatus FfSub (FiniteField *ff, FfElement const *a, FfElement const *b, FfElement *r)
 Subtracts two finite field elements. More...
 
EpidStatus FfMul (FiniteField *ff, FfElement const *a, FfElement const *b, FfElement *r)
 Multiplies two finite field elements. More...
 
EpidStatus FfIsZero (FiniteField *ff, FfElement const *a, bool *is_zero)
 Checks if given finite field element is the additive identity (zero). More...
 
EpidStatus FfExp (FiniteField *ff, FfElement const *a, BigNum const *b, FfElement *r)
 Raises an element of a finite field to a power. More...
 
EpidStatus FfMultiExp (FiniteField *ff, FfElement const **a, BigNumStr const **b, size_t m, FfElement *r)
 Multi-exponentiates finite field elements. More...
 
EpidStatus FfMultiExpBn (FiniteField *ff, FfElement const **a, BigNum const **b, size_t m, FfElement *r)
 Multi-exponentiates finite field elements. More...
 
EpidStatus FfSscmMultiExp (FiniteField *ff, FfElement const **a, BigNumStr const **b, size_t m, FfElement *r)
 Software side-channel mitigated implementation of FfMultiExp. More...
 
EpidStatus FfIsEqual (FiniteField *ff, FfElement const *a, FfElement const *b, bool *is_equal)
 Checks if two finite field elements are equal. More...
 
EpidStatus FfHash (FiniteField *ff, ConstOctStr msg, size_t msg_len, HashAlg hash_alg, FfElement *r)
 Hashes an arbitrary message to an element in a finite field. More...
 
EpidStatus FfGetRandom (FiniteField *ff, BigNumStr const *low_bound, BitSupplier rnd_func, void *rnd_param, FfElement *r)
 Generate random finite field element. More...
 
EpidStatus FfSqrt (FiniteField *ff, FfElement const *a, FfElement *r)
 Finds a square root of a finite field element. More...
 

Detailed Description

Finite field operations.

provides APIs for working with finite fields. Finite fields allow simple mathematical operations based on a finite set of discrete values. The results of these operations are also contained in the same set.

A simple example of a finite field is all integers from zero that are less than a given value.

The elements (FfElement) of a finite field can be used in a variety of simple mathematical operations that result in elements of the same field.

Function Documentation

◆ DeleteFfElement()

void DeleteFfElement ( FfElement **  ff_elem)

Frees a previously allocated FfElement.

Frees memory pointed to by ff_elem. Nulls the pointer.

Parameters
[in]ff_elemThe finite field element. Can be NULL.
See also
NewFfElement

◆ DeleteFiniteField()

void DeleteFiniteField ( FiniteField **  ff)

Frees a previously allocated FiniteField.

Frees memory pointed to by finite field. Nulls the pointer.

Parameters
[in]ffThe Finite field. Can be NULL.
See also
NewFiniteField

◆ FfAdd()

EpidStatus FfAdd ( FiniteField ff,
FfElement const *  a,
FfElement const *  b,
FfElement r 
)

Adds two finite field elements.

Parameters
[in]ffThe finite field.
[out]aThe first operand to be added.
[out]bThe second operand to be added.
[out]rThe result of adding a and b.
Returns
EpidStatus

◆ FfExp()

EpidStatus FfExp ( FiniteField ff,
FfElement const *  a,
BigNum const *  b,
FfElement r 
)

Raises an element of a finite field to a power.

Parameters
[in]ffThe finite field in which to perform the operation
[in]aThe base.
[in]bThe power.
[out]rThe result of raising a to the power b.
Returns
EpidStatus
See also
NewFiniteField
NewFfElement

◆ FfGetRandom()

EpidStatus FfGetRandom ( FiniteField ff,
BigNumStr const *  low_bound,
BitSupplier  rnd_func,
void *  rnd_param,
FfElement r 
)

Generate random finite field element.

Parameters
[in]ffThe finite field associated with the random finite field element.
[in]low_boundLower bound of the random finite field to be generated.
[in]rnd_funcRandom number generator.
[in]rnd_paramPass through context data for rnd_func.
[in,out]rThe random finite field element.
Returns
EpidStatus
Return values
kEpidRandMaxIterErrthe function should be called again with different random data.
See also
NewFfElement
BitSupplier

◆ FfHash()

EpidStatus FfHash ( FiniteField ff,
ConstOctStr  msg,
size_t  msg_len,
HashAlg  hash_alg,
FfElement r 
)

Hashes an arbitrary message to an element in a finite field.

Parameters
[in]ffThe finite field.
[in]msgThe message.
[in]msg_lenThe size of msg in bytes.
[in]hash_algThe hash algorithm.
[out]rThe hashed value.
Returns
EpidStatus
See also
NewFiniteField
NewFfElement

◆ FfInv()

EpidStatus FfInv ( FiniteField ff,
FfElement const *  a,
FfElement r 
)

Calculates the multiplicative inverse of a finite field element.

Parameters
[in]ffThe finite field.
[in]aThe element.
[out]rThe inverted element.
Returns
EpidStatus
See also
NewFiniteField
NewFfElement

◆ FfIsEqual()

EpidStatus FfIsEqual ( FiniteField ff,
FfElement const *  a,
FfElement const *  b,
bool is_equal 
)

Checks if two finite field elements are equal.

Parameters
[in]ffThe finite field.
[in]aAn element to check.
[in]bAnother element to check.
[out]is_equalThe result of the check.
Returns
EpidStatus
See also
NewEcGroup
NewEcPoint

◆ FfIsZero()

EpidStatus FfIsZero ( FiniteField ff,
FfElement const *  a,
bool is_zero 
)

Checks if given finite field element is the additive identity (zero).

Parameters
[in]ffThe finite field.
[out]aThe element.
[out]is_zeroThe result of the check.
Returns
EpidStatus
See also
NewFiniteField
NewFfElement

◆ FfMul()

EpidStatus FfMul ( FiniteField ff,
FfElement const *  a,
FfElement const *  b,
FfElement r 
)

Multiplies two finite field elements.

Parameters
[in]ffThe finite field.
[out]aThe first operand to be multplied.
[out]bThe second operand to be multiplied. If ff is an extension field of a field F then this parameter may be an element of either ff or F.
[out]rThe result of multiplying a and b.
Returns
EpidStatus
See also
NewFiniteField
NewFfElement

◆ FfMultiExp()

EpidStatus FfMultiExp ( FiniteField ff,
FfElement const **  a,
BigNumStr const **  b,
size_t  m,
FfElement r 
)

Multi-exponentiates finite field elements.

Calculates FfExp(p[0],b[0]) * ... * FfExp(p[m-1],b[m-1]) for m > 1

Parameters
[in]ffThe finite field in which to perform the operation
[in]aThe bases.
[in]bThe powers.
[in]mNumber of entries in a and b.
[out]rThe result of raising each a to the corresponding power b and multiplying the results.
Returns
EpidStatus
See also
NewFiniteField
NewFfElement

◆ FfMultiExpBn()

EpidStatus FfMultiExpBn ( FiniteField ff,
FfElement const **  a,
BigNum const **  b,
size_t  m,
FfElement r 
)

Multi-exponentiates finite field elements.

Calculates FfExp(p[0],b[0]) * ... * FfExp(p[m-1],b[m-1]) for m > 1

Parameters
[in]ffThe finite field in which to perform the operation
[in]aThe bases.
[in]bThe powers.
[in]mNumber of entries in a and b.
[out]rThe result of raising each a to the corresponding power b and multiplying the results.
Returns
EpidStatus
See also
NewFiniteField
NewFfElement

◆ FfNeg()

EpidStatus FfNeg ( FiniteField ff,
FfElement const *  a,
FfElement r 
)

Calculates the additive inverse of a finite field element.

Parameters
[in]ffThe finite field.
[in]aThe element.
[out]rThe inverted element.
Returns
EpidStatus
See also
NewFiniteField
NewFfElement

◆ FfSqrt()

EpidStatus FfSqrt ( FiniteField ff,
FfElement const *  a,
FfElement r 
)

Finds a square root of a finite field element.

This function calculates the square root by the method of false position.

Parameters
[in]ffThe finite field in which to perform the operation
[in]aThe bases.
[out]rThe result of raising each a to the corresponding power b and multiplying the results.
Return values
kEpidMathQuadraticNonResidueErrorNo square root could be found.
Returns
EpidStatus
See also
NewFiniteField
NewFfElement

◆ FfSscmMultiExp()

EpidStatus FfSscmMultiExp ( FiniteField ff,
FfElement const **  a,
BigNumStr const **  b,
size_t  m,
FfElement r 
)

Software side-channel mitigated implementation of FfMultiExp.

Calculates FfExp(p[0],b[0]) * ... * FfExp(p[m-1],b[m-1]) for m > 1

Attention
The reference implementation of FfSscmMultiExp calls FfMultiExp directly because the implementation of FfMultiExp is already side channel mitigated. Implementers providing their own versions of this function are responsible for ensuring that FfSscmMultiExp is side channel mitigated per section 8 of the Intel(R) EPID 2.0 spec.
Parameters
[in]ffThe finite field in which to perform the operation.
[in]aThe bases.
[in]bThe powers.
[in]mNumber of entries in a and b.
[out]rThe result of raising each a to the corresponding power b and multiplying the results.
Returns
EpidStatus
See also
NewFiniteField
NewFfElement

◆ FfSub()

EpidStatus FfSub ( FiniteField ff,
FfElement const *  a,
FfElement const *  b,
FfElement r 
)

Subtracts two finite field elements.

Note
Only needed for Intel(R) EPID 1.1 verification.
Parameters
[in]ffThe finite field.
[out]aThe first operand to use in subtraction.
[out]bThe second operand to use in subtraction.
[out]rThe result of subtracting a and b.
Returns
EpidStatus

◆ InitFfElementFromBn()

EpidStatus InitFfElementFromBn ( FiniteField ff,
BigNum bn,
FfElement ff_elem 
)

Initializes an existing FfElement from a BigNum.

Parameters
[in]ffThe finite field. Must be a Prime Field.
[in]bnThe value to read.
[out]ff_elemThe target FfElement.
Returns
EpidStatus
See also
NewFfElement
WriteFfElement

◆ NewFfElement()

EpidStatus NewFfElement ( FiniteField const *  ff,
FfElement **  new_ff_elem 
)

Creates a new finite field element.

Allocates memory and creates a new finite field element.

Use DeleteFfElement() to free memory.

Parameters
[in]ffThe finite field.
[out]new_ff_elemThe Newly constructed finite field element.
Returns
EpidStatus
Attention
It is the responsibility of the caller to ensure that ff exists for the entire lifetime of the new FfElement.
See also
NewFiniteField
DeleteFfElement

◆ NewFiniteField()

EpidStatus NewFiniteField ( BigNumStr const *  prime,
FiniteField **  ff 
)

Creates new finite field.

Allocates memory and creates a new finite field GF(prime).

Use DeleteFiniteField() to free memory.

Parameters
[in]primeThe order of the finite field.
[out]ffThe newly constructed finite field.
Returns
EpidStatus
See also
DeleteFiniteField

◆ NewFiniteFieldViaBinomalExtension()

EpidStatus NewFiniteFieldViaBinomalExtension ( FiniteField const *  ground_field,
FfElement const *  ground_element,
int  degree,
FiniteField **  ff 
)

Creates a new finite field using binomial extension.

Allocates memory and creates a finite field using binomial extension.

Use DeleteFiniteField() to free memory.

Parameters
[in]ground_fieldThe ground field.
[in]ground_elementThe low-order term of the extension.
[in]degreeThe degree of the extension.
[out]ffThe newly constructed finite field.
Returns
EpidStatus
Attention
It is the responsibility of the caller to ensure that ground_field exists for the entire lifetime of the new FiniteField.
See also
DeleteFiniteField

◆ NewFiniteFieldViaPolynomialExtension()

EpidStatus NewFiniteFieldViaPolynomialExtension ( FiniteField const *  ground_field,
BigNumStr const *  irr_polynomial,
int  degree,
FiniteField **  ff 
)

Creates a new finite field using polynomial extension.

Allocates memory and creates a finite field using polynomial extension.

Use DeleteFiniteField() to free memory.

Note
Only needed for Intel(R) EPID 1.1 verification.
Parameters
[in]ground_fieldThe ground field.
[in]irr_polynomialArray with coefficients of the irreducible polynomial. Number of elements must be equal to the degree of the extension.
[in]degreeThe degree of the extension.
[out]ffThe newly constructed finite field.
Returns
EpidStatus
Attention
It is the responsibility of the caller to ensure that ground_field exists for the entire lifetime of the new FiniteField.
See also
DeleteFiniteField

◆ ReadFfElement()

EpidStatus ReadFfElement ( FiniteField ff,
ConstOctStr  ff_elem_str,
size_t  strlen,
FfElement ff_elem 
)

Deserializes a FfElement from a string.

Parameters
[in]ffThe finite field.
[in]ff_elem_strThe serialized value.
[in]strlenThe size of ff_elem_str in bytes.
[out]ff_elemThe target FfElement.
Returns
EpidStatus
See also
NewFfElement
WriteFfElement

◆ WriteFfElement()

EpidStatus WriteFfElement ( FiniteField ff,
FfElement const *  ff_elem,
OctStr  ff_elem_str,
size_t  strlen 
)

Serializes a finite field element to a string.

Parameters
[in]ffThe finite field.
[in]ff_elemThe FfElement to be serialized.
[out]ff_elem_strThe target string.
[in]strlenThe size of ff_elem_str in bytes.
Returns
EpidStatus
See also
NewFfElement
FpElemStr
FqElemStr
GtElemStr