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) Bytes() []byte
- func (z *Nat) CmpEq(x *Nat) int
- 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
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.
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
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) 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) CmpEq ¶
CmpEq compares two natural numbers, returning 1 if they're equal and 0 otherwise
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) ModInverseEven ¶
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 ¶
ModMul calculates z <- x * y mod m
The capacity of the resulting number matches the capacity of the modulus
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.
Source Files