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, void const 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, void *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, void const 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

void DeleteFfElement ( FfElement ** ff_elem )

Frees a previously allocated FfElement.

Frees memory pointed to by ff_elem. Nulls the pointer.

Parameters

[in] ff_elem The finite field element. Can be NULL.

See also: NewFfElement

void DeleteFiniteField ( FiniteField ** ff )

Frees a previously allocated FiniteField.

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

Parameters

[in] ff The Finite field. Can be NULL.

See also: NewFiniteField

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

Adds two finite field elements.

Parameters

[in]	ff	The finite field.
[out]	a	The first operand to be added.
[out]	b	The second operand to be added.
[out]	r	The result of adding a and b.

Returns: EpidStatus

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

Raises an element of a finite field to a power.

Parameters

[in]	ff	The finite field in which to perform the operation
[in]	a	The base.
[in]	b	The power.
[out]	r	The result of raising a to the power b.

Returns: EpidStatus

See also: NewFiniteField; NewFfElement

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

Generate random finite field element.

Parameters

[in]	ff	The finite field associated with the random finite field element.
[in]	low_bound	Lower bound of the random finite field to be generated.
[in]	rnd_func	Random number generator.
[in]	rnd_param	Pass through context data for rnd_func.
[in,out]	r	The random finite field element.

Returns: EpidStatus

Return values

kEpidRandMaxIterErr the function should be called again with different random data.

See also: NewFfElement; BitSupplier

EpidStatus FfHash	(	FiniteField *	ff,
		void const *	msg,
		size_t	msg_len,
		HashAlg	hash_alg,
		FfElement *	r
	)

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

Parameters

[in]	ff	The finite field.
[in]	msg	The message.
[in]	msg_len	The size of msg in bytes.
[in]	hash_alg	The hash algorithm.
[out]	r	The hashed value.

Returns: EpidStatus

See also: NewFiniteField; NewFfElement

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

Calculates the multiplicative inverse of a finite field element.

Parameters

[in]	ff	The finite field.
[in]	a	The element.
[out]	r	The inverted element.

Returns: EpidStatus

See also: NewFiniteField; NewFfElement

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

Checks if two finite field elements are equal.

Parameters

[in]	ff	The finite field.
[in]	a	An element to check.
[in]	b	Another element to check.
[out]	is_equal	The result of the check.

Returns: EpidStatus

See also: NewEcGroup; NewEcPoint

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

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

Parameters

[in]	ff	The finite field.
[out]	a	The element.
[out]	is_zero	The result of the check.

Returns: EpidStatus

See also: NewFiniteField; NewFfElement

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

Multiplies two finite field elements.

Parameters

[in]	ff	The finite field.
[out]	a	The first operand to be multplied.
[out]	b	The 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]	r	The result of multiplying a and b.

Returns: EpidStatus

See also: NewFiniteField; NewFfElement

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]	ff	The finite field in which to perform the operation
[in]	a	The bases.
[in]	b	The powers.
[in]	m	Number of entries in a and b.
[out]	r	The result of raising each a to the corresponding power b and multiplying the results.

Returns: EpidStatus

See also: NewFiniteField; NewFfElement

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]	ff	The finite field in which to perform the operation
[in]	a	The bases.
[in]	b	The powers.
[in]	m	Number of entries in a and b.
[out]	r	The result of raising each a to the corresponding power b and multiplying the results.

Returns: EpidStatus

See also: NewFiniteField; NewFfElement

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

Calculates the additive inverse of a finite field element.

Parameters

[in]	ff	The finite field.
[in]	a	The element.
[out]	r	The inverted element.

Returns: EpidStatus

See also: NewFiniteField; NewFfElement

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]	ff	The finite field in which to perform the operation
[in]	a	The bases.
[out]	r	The result of raising each a to the corresponding power b and multiplying the results.

Return values

kEpidMathQuadraticNonResidueError No square root could be found.

Returns: EpidStatus

See also: NewFiniteField; NewFfElement

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]	ff	The finite field in which to perform the operation.
[in]	a	The bases.
[in]	b	The powers.
[in]	m	Number of entries in a and b.
[out]	r	The result of raising each a to the corresponding power b and multiplying the results.

Returns: EpidStatus

See also: NewFiniteField; NewFfElement

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]	ff	The finite field.
[out]	a	The first operand to use in subtraction.
[out]	b	The second operand to use in subtraction.
[out]	r	The result of subtracting a and b.

Returns: EpidStatus

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

Initializes an existing FfElement from a BigNum.

Parameters

[in]	ff	The finite field. Must be a Prime Field.
[in]	bn	The value to read.
[out]	ff_elem	The target FfElement.

Returns: EpidStatus

See also: NewFfElement; WriteFfElement

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]	ff	The finite field.
[out]	new_ff_elem	The Newly constructed finite field element.

Returns: EpidStatus

See also: NewFiniteField; DeleteFfElement

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]	prime	The order of the finite field.
[out]	ff	The newly constructed finite field.

Returns: EpidStatus

See also: DeleteFiniteField

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_field	The ground field.
[in]	ground_element	The low-order term of the extension.
[in]	degree	The degree of the extension.
[out]	ff	The newly constructed finite field.

Returns: EpidStatus

See also: DeleteFiniteField

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_field	The ground field.
[in]	irr_polynomial	Array with coefficients of the irreducible polynomial. Number of elements must be equal to the degree of the extension.
[in]	degree	The degree of the extension.
[out]	ff	The newly constructed finite field.

Returns: EpidStatus

See also: DeleteFiniteField

EpidStatus ReadFfElement	(	FiniteField *	ff,
		void const *	ff_elem_str,
		size_t	strlen,
		FfElement *	ff_elem
	)

Deserializes a FfElement from a string.

Parameters

[in]	ff	The finite field.
[in]	ff_elem_str	The serialized value.
[in]	strlen	The size of ff_elem_str in bytes.
[out]	ff_elem	The target FfElement.

Returns: EpidStatus

See also: NewFfElement; WriteFfElement

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

Serializes a finite field element to a string.

Parameters

[in]	ff	The finite field.
[in]	ff_elem	The FfElement to be serialized.
[out]	ff_elem_str	The target string.
[in]	strlen	The size of ff_elem_str in bytes.

Returns: EpidStatus

See also: NewFfElement; FpElemStr; FqElemStr; GtElemStr

Typedefs

Functions

Detailed Description

Function Documentation