safenum

README

safenum

The purpose of this package is to provide a version of arbitrary sized arithmetic, in a safe (i.e. constant-time) way, for cryptography.

This is experimental software, use at your own peril.

Assembly

This code reuses some assembly routines from Go's standard library, inside of the arith*.go. These have been adjusted to remove some non-constant-time codepaths, most of which aren't used anyways.

Integrating with Go

Initially, this code was structured to be relatively straightforwardly patched into Go's standard library. The idea would be to use the arith*.go files already in Go's math/big package, and just add a num.go file.

Unfortunately, this approach doesn't seem to be possible, because of addVWlarge and subVWlarge, which are two non-constant time routines. These are jumped to inside of the assembly code in Go's math/big routines, so using them would require intrusive modification, which rules out this code living alongside math/big, and sharing its routines.

Merging things upstream

The easiest path towards merging this work upstream, in all likelihood, is having this package live in crypto, and duplicating some of the assembly code as necessary.

The rationale here is that math/big's needs will inevitably lead to situations like this, where a routine is tempted to bail towards a non-constant time variant for large or special inputs. Ultimately, having this code live in crypto is much more likely to allow us to ensure its integrity. It would also allow us to add assembly specifically tailored for our operations, such as conditional addition, and things like that.

Benchmarks

Run with assembly routines:

go test -bench=.

Run with pure Go code:

go test -bench=. -tags math_big_pure_go

Licensing

The files arith*.go come from Go's standard library, and are licensed under a BSD license in LICENSE_go. The rest of the code is under an MIT license.

Documentation

Index

• type Modulus
  • func ModulusFromBytes(bytes []byte) Modulus
  • func ModulusFromNat(nat Nat) Modulus
  • func ModulusFromUint64(x uint64) Modulus
  • func (m *Modulus) Bytes() []byte
• type Nat
  • func (z *Nat) Add(x *Nat, y *Nat, cap uint) *Nat
  • func (z *Nat) Bytes() []byte
  • func (z *Nat) Cmp(x *Nat) int
  • func (z *Nat) EqZero() bool
  • func (z *Nat) Exp(x *Nat, y *Nat, m *Modulus) *Nat
  • func (z *Nat) FillBytes(buf []byte) []byte
  • func (z *Nat) Mod(x *Nat, m *Modulus) *Nat
  • func (z *Nat) ModAdd(x *Nat, y *Nat, m *Modulus) *Nat
  • func (z *Nat) ModInverse(x *Nat, m *Modulus) *Nat
  • func (z *Nat) ModInverseEven(x *Nat, m *Nat) *Nat
  • func (z *Nat) ModMul(x *Nat, y *Nat, m *Modulus) *Nat
  • func (z *Nat) Mul(x *Nat, y *Nat, cap uint) *Nat
  • func (z *Nat) SetBytes(buf []byte) *Nat
  • func (z *Nat) SetUint64(x uint64) *Nat
• type Word

Types

type Modulus

type Modulus struct {
	// contains filtered or unexported fields
}

Modulus represents a natural number used for modular reduction

Unlike with natural numbers, the number of bits need to contain the modulus is assumed to be public. Operations are allowed to leak this size, and creating a modulus will remove unnecessary zeros.

func ModulusFromBytes

func ModulusFromBytes(bytes []byte) Modulus

FromBytes creates a new Modulus, converting from big endian bytes

This function will remove leading zeros, thus leaking the true size of the modulus. See the documentation for the Modulus type, for more information about this contract.

func ModulusFromNat

func ModulusFromNat(nat Nat) Modulus

FromNat creates a new Modulus, using the value of a Nat

This will leak the true size of this natural number. Because of this, the true size of the number should not be sensitive information. This is a stronger requirement than we usually have for Nat.

func ModulusFromUint64

func ModulusFromUint64(x uint64) Modulus

SetUint64 sets the modulus according to an integer

func (*Modulus) Bytes

func (m *Modulus) Bytes() []byte

Bytes returns the big endian bytes making up the modulus

type Nat

type Nat struct {
	// contains filtered or unexported fields
}

Nat represents an arbitrary sized natural number.

Different methods on Nats will talk about a "capacity". The capacity represents the announced size of some number. Operations may vary in time *only* relative to this capacity, and not to the actual value of the number.

The capacity of a number is usually inherited through whatever method was used to create the number in the first place.

func (*Nat) Add

func (z *Nat) Add(x *Nat, y *Nat, cap uint) *Nat

Add calculates z <- x + y, modulo 2^cap

The capacity is given in bits, and also controls the size of the result.

func (*Nat) Bytes

func (z *Nat) Bytes() []byte

Bytes creates a slice containing the contents of this Nat, in big endian

This will always fill the output byte slice based on the announced length of this Nat.

func (*Nat) Cmp

func (z *Nat) Cmp(x *Nat) int

Cmp compares two natural numbers, returning 0 if equal, -1 if z < x, and 1 if z > x

This leaks nothing about the values of the numbers, except for their rspective announced lengths.

Be mindful that even though the comparison is done without leaks, branching on the result can introduce a leak of this result. Because of this, be careful with how you use this function.

func (*Nat) EqZero

func (z *Nat) EqZero() bool

EqZero compares z to 0, returning true if they're equal

While calling this function will not leak whether or not this number is equal to zero, an if condition using its result can leak this information. Because of this, be mindful to not misuse this function.

func (*Nat) Exp

func (z *Nat) Exp(x *Nat, y *Nat, m *Modulus) *Nat

Exp calculates z <- x^y mod m

The capacity of the resulting number matches the capacity of the modulus

func (*Nat) FillBytes

func (z *Nat) FillBytes(buf []byte) []byte

FillBytes writes out the big endian bytes of a natural number.

This will always write out the full capacity of the number, without any kind trimming.

This will panic if the buffer's length cannot accomodate the capacity of the number

func (*Nat) Mod

func (z *Nat) Mod(x *Nat, m *Modulus) *Nat

Mod calculates z <- x mod m

The capacity of the resulting number matches the capacity of the modulus.

func (*Nat) ModAdd

func (z *Nat) ModAdd(x *Nat, y *Nat, m *Modulus) *Nat

ModAdd calculates z <- x + y mod m

The capacity of the resulting number matches the capacity of the modulus.

func (*Nat) ModInverse

func (z *Nat) ModInverse(x *Nat, m *Modulus) *Nat

ModInverse calculates z <- x^-1 mod m

This will produce nonsense if the modulus is even.

The capacity of the resulting number matches the capacity of the modulus

func (*Nat) ModInverseEven

func (z *Nat) ModInverseEven(x *Nat, m *Nat) *Nat

ModInverseEven calculates the modular inverse of x, mod m

This routine will work even if m is an even number, unlike ModInverse. Furthermore, it doesn't require the modulus to be truncated to its true size, and will only leak information about the public sizes of its inputs. It is slower than the standard routine though.

This function assumes that x has an inverse modulo m, naturally

func (*Nat) ModMul

func (z *Nat) ModMul(x *Nat, y *Nat, m *Modulus) *Nat

ModMul calculates z <- x * y mod m

The capacity of the resulting number matches the capacity of the modulus

func (*Nat) Mul

func (z *Nat) Mul(x *Nat, y *Nat, cap uint) *Nat

Mul calculates z <- x * y, modulo 2^cap

The capacity is given in bits, and also controls the size of the result.

func (*Nat) SetBytes

func (z *Nat) SetBytes(buf []byte) *Nat

SetBytes interprets a number in big-endian format, stores it in z, and returns z.

The exact length of the buffer must be public information! This length also dictates the capacity of the number returned, and thus the resulting timings for operations involving that number.

func (*Nat) SetUint64

func (z *Nat) SetUint64(x uint64) *Nat

SetUint64 sets z to x, and returns z

This will have the exact same capacity as a 64 bit number

type Word

type Word uint

A Word represents a single digit of a multi-precision unsigned integer.