finitefield

Documentation

Overview

Package finitefield provides a finite field type (Field) that wraps big.Int operations and verifies that all mutations to the value are done within the field.

This implementation IS NOT constant time as it leverages math/big for big number operations.

Index

• type Element
  • func (x Element) Add(y *Element) *Element
  • func (x Element) BigInt() *big.Int
  • func (x Element) Bytes() []byte
  • func (x Element) Clone() *Element
  • func (x Element) Div(y *Element) *Element
  • func (x Element) IsEqual(y *Element) bool
  • func (x Element) Mul(y *Element) *Element
  • func (x Element) Sub(y *Element) *Element
• type Field
  • func New(modulus *big.Int) *Field
  • func (f Field) ElementFromBytes(bytes []byte) *Element
  • func (f Field) IsValid(value *big.Int) bool
  • func (f Field) NewElement(value *big.Int) *Element
  • func (f Field) One() *Element
  • func (f Field) RandomElement(r io.Reader) (*Element, error)
  • func (f Field) ReducedElementFromBytes(bytes []byte) *Element
  • func (f Field) Zero() *Element

Types

type Element

type Element struct {
	*Field
	// contains filtered or unexported fields
}

Element is a group element within a finite field.

func (Element) Add

func (x Element) Add(y *Element) *Element

Add returns the sum x+y

func (Element) BigInt

func (x Element) BigInt() *big.Int

BigInt returns value as a big.Int

func (Element) Bytes

func (x Element) Bytes() []byte

Bytes returns the value as bytes

func (Element) Clone

func (x Element) Clone() *Element

Clone returns a new copy of the element

func (Element) Div

func (x Element) Div(y *Element) *Element

Div returns the quotient x/y

func (Element) IsEqual

func (x Element) IsEqual(y *Element) bool

IsEqual returns x == y

func (Element) Mul

func (x Element) Mul(y *Element) *Element

Mul returns the product x*y

func (Element) Sub

func (x Element) Sub(y *Element) *Element

Sub returns the difference x-y

type Field

type Field struct {
	Modulus *big.Int
}

Field is a finite field.

func New

func New(modulus *big.Int) *Field

New is a constructor for a Field.

func (Field) ElementFromBytes

func (f Field) ElementFromBytes(bytes []byte) *Element

ElementFromBytes initializes a new field element from big-endian bytes

func (Field) IsValid

func (f Field) IsValid(value *big.Int) bool

IsValid returns whether or not the value is within [0, modulus)

func (Field) NewElement

func (f Field) NewElement(value *big.Int) *Element

func (Field) One

func (f Field) One() *Element

func (Field) RandomElement

func (f Field) RandomElement(r io.Reader) (*Element, error)

func (Field) ReducedElementFromBytes

func (f Field) ReducedElementFromBytes(bytes []byte) *Element

ReducedElementFromBytes initializes a new field element from big-endian bytes and reduces it by the modulus of the field.

WARNING: If this is used with cryptographic constructions which rely on a uniform distribution of values, this may introduce a bias to the value of the returned field element. This happens when the integer range of the provided bytes is not an integer multiple of the field order.

Assume we are working in field which a modulus of 3 and the range of the uniform random bytes we provide as input is 5. Thus, the set of field elements is {0, 1, 2} and the set of integer values for the input bytes is: {0, 1, 2, 3, 4}. What is the distribution of the output values produced by this function?

ReducedElementFromBytes(0) => 0
ReducedElementFromBytes(1) => 1
ReducedElementFromBytes(2) => 2
ReducedElementFromBytes(3) => 0
ReducedElementFromBytes(4) => 1

For a value space V and random value v, a uniform distribution is defined as P[V = v] = 1/|V| where |V| is to the order of the field. Using the results from above, we see that P[v = 0] = 2/5, P[v = 1] = 2/5, and P[v = 2] = 1/5. For a uniform distribution we would expect these to each be equal to 1/3. As they do not, this does not return uniform output for that example.

To see why this is okay if the range is a multiple of the field order, change the input range to 6 and notice that now each output has a probability of 2/6 = 1/3, and the output is uniform.

func (Field) Zero

func (f Field) Zero() *Element