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
- type Nat
- func (z *Nat) Add(x *Nat, y *Nat, cap uint) *Nat
- func (z *Nat) AnnouncedLen() uint
- func (z *Nat) Big() *big.Int
- func (z *Nat) Bytes() []byte
- func (z *Nat) Cmp(x *Nat) int
- func (z *Nat) CmpMod(m *Modulus) 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) ModMul(x *Nat, y *Nat, m *Modulus) *Nat
- func (z *Nat) ModSqrt(x *Nat, p *Modulus) *Nat
- func (z *Nat) ModSub(x *Nat, y *Nat, m *Modulus) *Nat
- func (z *Nat) Mul(x *Nat, y *Nat, cap uint) *Nat
- func (z *Nat) SetBig(x *big.Int, size uint) *Nat
- func (z *Nat) SetBytes(buf []byte) *Nat
- func (z *Nat) SetNat(x *Nat) *Nat
- func (z *Nat) SetUint64(x uint64) *Nat
- func (z *Nat) Sub(x *Nat, y *Nat, cap uint) *Nat
- func (z *Nat) TrueLen() uint
- func (z *Nat) Uint64() uint64
- type Word
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
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.
Operations on a Modulus may leak whether or not a Modulus is even.
func ModulusFromBytes ¶
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 ¶
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 ¶
SetUint64 sets the modulus according to an integer
func (*Modulus) BitLen ¶ added in v0.5.0
BitLen returns the exact number of bits used to store this Modulus
Moduli are allowed to leak this value.
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 ¶
Add calculates z <- x + y, modulo 2^cap
The capacity is given in bits, and also controls the size of the result.
func (*Nat) AnnouncedLen ¶ added in v0.5.0
AnnouncedLen returns the number of bits this number is publicly known to have
func (*Nat) Big ¶ added in v0.13.0
Big converts a Nat into a big.Int
This will leak information about the true size of z, so caution should be exercised when using this method with sensitive values.
func (*Nat) Bytes ¶
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 ¶ added in v0.2.0
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) CmpMod ¶ added in v0.4.0
CmpMod compares this natural number with a modulus, returning 0 if z == m, -1 if z < m, and 1 if z > m
This doesn't leak anything about the values of the numbers, but the same warnings as for Cmp apply.
func (*Nat) EqZero ¶ added in v0.2.0
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 ¶
Exp calculates z <- x^y mod m
The capacity of the resulting number matches the capacity of the modulus
func (*Nat) FillBytes ¶
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 ¶
Mod calculates z <- x mod m
The capacity of the resulting number matches the capacity of the modulus.
func (*Nat) ModAdd ¶
ModAdd calculates z <- x + y mod m
The capacity of the resulting number matches the capacity of the modulus.
func (*Nat) ModInverse ¶
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) ModMul ¶
ModMul calculates z <- x * y mod m
The capacity of the resulting number matches the capacity of the modulus
func (*Nat) ModSqrt ¶ added in v0.11.0
ModSqrt calculates the square root of x modulo p
p must be a prime number, and x must actually have a square root modulo p. The result is undefined if these conditions aren't satisfied
This function will leak information about the value of p. This isn't intended to be used in situations where the modulus isn't publicly known.
func (*Nat) Mul ¶
Mul calculates z <- x * y, modulo 2^cap
The capacity is given in bits, and also controls the size of the result.
func (*Nat) SetBig ¶ added in v0.13.0
SetBig modifies z to contain the value of x
The size parameter is used to pad or truncate z to a certain number of bits.
func (*Nat) SetBytes ¶
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) SetNat ¶ added in v0.9.0
SetNat copies the value of x into z
z will have the same announced length as x.
func (*Nat) SetUint64 ¶
SetUint64 sets z to x, and returns z
This will have the exact same capacity as a 64 bit number
func (*Nat) Sub ¶ added in v0.8.0
Sub calculates z <- x - y, modulo 2^cap
The capacity is given in bits, and also controls the size of the result.
Source Files