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 Choice
- type Modulus
- type Nat
- func (z *Nat) Add(x *Nat, y *Nat, cap int) *Nat
- func (z *Nat) AnnouncedLen() int
- func (z *Nat) Big() *big.Int
- func (z *Nat) Byte(i int) byte
- func (z *Nat) Bytes() []byte
- func (z *Nat) Cmp(x *Nat) (Choice, Choice, Choice)
- func (z *Nat) CmpMod(m *Modulus) (Choice, Choice, Choice)
- func (z *Nat) CondAssign(yes Choice, x *Nat) *Nat
- func (x *Nat) Coprime(y *Nat) int
- func (z *Nat) Div(x *Nat, m *Modulus, cap int) *Nat
- func (z *Nat) Eq(y *Nat) Choice
- func (z *Nat) EqZero() Choice
- 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) ModNeg(x *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 int) *Nat
- func (z *Nat) SetBig(x *big.Int, size int) *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 int) *Nat
- func (z *Nat) TrueLen() int
- func (z *Nat) Uint64() uint64
- type Word
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Choice ¶ added in v0.17.0
type Choice Word
Choice represents a constant-time boolean.
The value of Choice is always either 1 or 0.
We use a separate type instead of bool, in order to be able to make decisions without leaking which decision was made.
You can easily convert a Choice into a bool with the operation c == 1.
In general, logical operations on bool become bitwise operations on choice:
a && b => a & b a || b => a | b a != b => a ^ b !a => 1 ^ a
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) Byte ¶ added in v0.16.0
Byte will access the ith byte in this nat, with 0 being the least significant byte.
This will leak the value of i, and panic if i is < 0.
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 results for (>, =, <) in that order.
Because these relations are mutually exclusive, exactly one of these values will be true.
This function doesn't leak any information about the values involved, only their announced lengths.
func (*Nat) CmpMod ¶ added in v0.4.0
CmpMod compares this natural number with a modulus, returning results for (>, =, <)
This doesn't leak anything about the values of the numbers, only their lengths.
func (*Nat) CondAssign ¶ added in v0.17.0
CondAssign sets z <- yes ? x : z.
This function doesn't leak any information about whether the assignment happened.
The announced size of the result will be the largest size between z and x.
func (*Nat) Div ¶ added in v0.16.0
Div calculates z <- x / m, with m a Modulus.
This might seem like an odd signature, but by using a Modulus, we can achieve the same speed as the Mod method. This wouldn't be the case for an arbitrary Nat.
cap determines the number of bits to keep in the result.
func (*Nat) Eq ¶ added in v0.17.0
Eq checks if z = y.
This is equivalent to looking at the second choice returned by Cmp. But, since looking at equality is so common, this function is provided as an extra utility.
func (*Nat) EqZero ¶ added in v0.2.0
EqZero compares z to 0.
This is more efficient that calling Eq between this Nat and a zero Nat.
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.
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.
func (*Nat) TrueLen ¶ added in v0.5.0
TrueLen calculates the exact number of bits needed to represent z
This function violates the standard contract around Nats and announced length. For most purposes, `AnnouncedLen` should be used instead.
That being said, this function does try to limit its leakage, and should only leak the number of leading zero bits in the number.
Source Files