README
¶
saferith
The purpose of this package is to provide a version of arbitrary sized arithmetic, in a safer (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 Int
- func (z *Int) Abs() *Nat
- func (z *Int) Add(x *Int, y *Int, cap int) *Int
- func (z *Int) AnnouncedLen() int
- func (z *Int) Big() *big.Int
- func (z *Int) CheckInRange(m *Modulus) Choice
- func (z *Int) Clone() *Int
- func (z *Int) Eq(x *Int) Choice
- func (z *Int) IsNegative() Choice
- func (i *Int) MarshalBinary() ([]byte, error)
- func (z *Int) Mod(m *Modulus) *Nat
- func (z *Int) Mul(x *Int, y *Int, cap int) *Int
- func (z *Int) Neg(doit Choice) *Int
- func (z *Int) Resize(cap int) *Int
- func (z *Int) SetBig(x *big.Int, size int) *Int
- func (z *Int) SetBytes(data []byte) *Int
- func (z *Int) SetInt(x *Int) *Int
- func (z *Int) SetModSymmetric(x *Nat, m *Modulus) *Int
- func (z *Int) SetNat(x *Nat) *Int
- func (z *Int) SetUint64(x uint64) *Int
- func (z *Int) String() string
- func (z *Int) TrueLen() int
- func (i *Int) UnmarshalBinary(data []byte) error
- type Modulus
- func (m *Modulus) Big() *big.Int
- func (m *Modulus) BitLen() int
- func (m *Modulus) Bytes() []byte
- func (m *Modulus) Cmp(n *Modulus) (Choice, Choice, Choice)
- func (m *Modulus) Hex() string
- func (i *Modulus) MarshalBinary() ([]byte, error)
- func (m *Modulus) Nat() *Nat
- func (m *Modulus) String() string
- func (i *Modulus) UnmarshalBinary(data []byte) error
- 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) Clone() *Nat
- 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) Choice
- 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) ExpI(x *Nat, i *Int, m *Modulus) *Nat
- func (z *Nat) FillBytes(buf []byte) []byte
- func (z *Nat) Hex() string
- func (x *Nat) IsUnit(m *Modulus) Choice
- func (z *Nat) Lsh(x *Nat, shift uint, cap int) *Nat
- func (i *Nat) MarshalBinary() ([]byte, error)
- 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) Resize(cap int) *Nat
- func (z *Nat) Rsh(x *Nat, shift uint, cap int) *Nat
- func (z *Nat) SetBig(x *big.Int, size int) *Nat
- func (z *Nat) SetBytes(buf []byte) *Nat
- func (z *Nat) SetHex(hex string) (*Nat, error)
- func (z *Nat) SetNat(x *Nat) *Nat
- func (z *Nat) SetUint64(x uint64) *Nat
- func (z *Nat) String() string
- func (z *Nat) Sub(x *Nat, y *Nat, cap int) *Nat
- func (z *Nat) TrueLen() int
- func (z *Nat) Uint64() uint64
- func (i *Nat) UnmarshalBinary(data []byte) error
- type Word
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Choice ¶
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 Int ¶
type Int struct {
// contains filtered or unexported fields
}
Int represents a signed integer of arbitrary size.
Similarly to Nat, each Int comes along with an announced size, representing the number of bits need to represent its absolute value. This can be larger than its true size, the number of bits actually needed.
func (*Int) Add ¶
Add calculates z <- x + y.
The cap determines the number of bits to use for the absolute value of the result.
If cap < 0, cap gets set to max(x.AnnouncedLen(), y.AnnouncedLen()) + 1
func (*Int) AnnouncedLen ¶
AnnouncedLen returns the announced size of this int's absolute value.
See Nat.AnnouncedLen
func (*Int) Big ¶
Big will convert this number into a big.Int, including sign.
This will leak the true size of this number, and its sign, because of the leakiness of big.Int, so caution should be exercises when using this function.
func (*Int) CheckInRange ¶
CheckInRange checks whether or not this Int is in the range for SetModSymmetric.
func (*Int) Clone ¶
Clone returns a copy of this Int.
The copy can safely be mutated without affecting the original value.
func (*Int) Eq ¶
Eq checks if this Int has the same value as another Int.
Note that negative zero and positive zero are the same number.
func (*Int) IsNegative ¶
IsNegative checks if this value is negative
func (*Int) MarshalBinary ¶
MarshalBinary implements encoding.BinaryMarshaler. The retrned byte slice is always of length 1 + len(i.Abs().Bytes()), where the first byte encodes the sign.
func (*Int) Mod ¶
Mod calculates z mod M, handling negatives correctly.
As indicated by the types, this function will return a number in the range 0..m-1.
func (*Int) Mul ¶
Mul calculates z <- x * y, returning z.
This will truncate the resulting absolute value, based on the bit capacity passed in.
If cap < 0, then capacity is x.AnnouncedLen() + y.AnnouncedLen().
func (*Int) Resize ¶
Resize adjust the announced size of this number, possibly truncating the absolute value.
func (*Int) SetBig ¶
SetBig will set the value of this number to the value of a big.Int, including sign.
The size dicates the number of bits to use for the absolute value. This is important, in order to include additional padding that the big.Int might have stripped off.
Since big.Int stores its sign as a boolean, it's likely that this conversion will leak the value of the sign.
func (*Int) SetBytes ¶
SetBytes interprets a number in big-endian form, stores it in z, and returns z.
This number will be positive.
func (*Int) SetModSymmetric ¶
SetModSymmetric takes a number x mod M, and returns a signed number centered around 0.
This effectively takes numbers in the range:
{0, .., m - 1}
And returns numbers in the range:
{-(m - 1)/2, ..., 0, ..., (m - 1)/2}
In the case that m is even, there will simply be an extra negative number.
func (*Int) SetNat ¶
SetNat will set the absolute value of z to x, and the sign to zero, returning z.
func (*Int) String ¶
String formats this number as a signed hex string.
This isn't a format that Int knows how to parse. This function exists mainly to help debugging, and whatnot.
func (*Int) TrueLen ¶
TrueLen returns the actual number of bits need to represent this int's absolute value.
This leaks this value.
See Nat.TrueLen
func (*Int) UnmarshalBinary ¶
UnmarshalBinary implements encoding.BinaryUnmarshaler. Returns an error when the length of data is 0, since we always expect the first byte to encode the sign.
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 ¶
ModulusFromBytes 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 ModulusFromHex ¶
ModulusFromHex creates a new modulus from a hex string.
The same rules as Nat.SetHex apply.
Additionally, this function will remove leading zeros, 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 ¶
ModulusFromUint64 sets the modulus according to an integer
func (*Modulus) BitLen ¶
BitLen returns the exact number of bits used to store this Modulus
Moduli are allowed to leak this value.
func (*Modulus) Cmp ¶
Cmp compares two moduli, returning results for (>, =, <).
This will not leak information about the value of these relations, or the moduli.
func (*Modulus) Hex ¶
Hex will represent this Modulus as a Hex string.
The hex string will hold a multiple of 8 bits.
This shouldn't leak any information about the value of the modulus, beyond the usual leakage around its size.
func (*Modulus) MarshalBinary ¶
MarshalBinary implements encoding.BinaryMarshaler.
func (*Modulus) Nat ¶
Nat returns the value of this modulus as a Nat.
This will create a copy of this modulus value, so the Nat can be safely mutated.
func (*Modulus) String ¶
String will represent this Modulus as a convenient Hex string
This shouldn't leak any information about the value of the modulus, only its length.
func (*Modulus) UnmarshalBinary ¶
UnmarshalBinary implements encoding.BinaryUnmarshaler.
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.
If cap < 0, the capacity will be max(x.AnnouncedLen(), y.AnnouncedLen()) + 1
func (*Nat) AnnouncedLen ¶
AnnouncedLen returns the number of bits this number is publicly known to have
func (*Nat) Big ¶
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 ¶
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) Clone ¶
Clone returns a copy of this value.
This copy can safely be mutated without affecting the original.
func (*Nat) Cmp ¶
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 ¶
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 ¶
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 ¶
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. If cap < 0, then the number of bits will be x.AnnouncedLen() - m.BitLen() + 2
func (*Nat) Eq ¶
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 ¶
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) ExpI ¶
ExpI calculates z <- x^i mod m.
This works with negative exponents, but requires x to be invertible mod m, of course.
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) Hex ¶
Hex converts this number into a hexadecimal string.
This string will be a multiple of 8 bits.
This shouldn't leak any information about the value of this Nat, only its length.
func (*Nat) IsUnit ¶
IsUnit checks if x is a unit, i.e. invertible, mod m.
This so happens to be when gcd(x, m) == 1.
func (*Nat) Lsh ¶
Lsh calculates z <- x << shift, producing a certain number of bits
This method will leak the value of shift.
If cap < 0, the number of bits will be x.AnnouncedLen() + shift.
func (*Nat) MarshalBinary ¶
MarshalBinary implements encoding.BinaryMarshaler. Returns the same value as Bytes().
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 ¶
ModSqrt calculates the square root of x modulo p
p must be an odd 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.
If cap < 0, the capacity will be x.AnnouncedLen() + y.AnnouncedLen()
func (*Nat) Rsh ¶
Rsh calculates z <- x >> shift, producing a certain number of bits
This method will leak the value of shift.
If cap < 0, the number of bits will be x.AnnouncedLen() - shift.
func (*Nat) SetBig ¶
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) SetHex ¶
SetHex modifies the value of z to hold a hex string, returning z
The hex string must be in big endian order. If it contains characters other than 0..9, A..F, the value of z will be undefined, and an error will be returned.
The value of the string shouldn't be leaked, except in the case where the string contains invalid characters.
func (*Nat) SetNat ¶
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) String ¶
String will represent this nat as a convenient Hex string
This shouldn't leak any information about the value of this Nat, only its length.
func (*Nat) Sub ¶
Sub calculates z <- x - y, modulo 2^cap
The capacity is given in bits, and also controls the size of the result.
If cap < 0, the capacity will be max(x.AnnouncedLen(), y.AnnouncedLen())
func (*Nat) TrueLen ¶
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.
func (*Nat) Uint64 ¶
Uint64 represents this number as uint64
The behavior of this function is undefined if the announced length of z is > 64.
func (*Nat) UnmarshalBinary ¶
UnmarshalBinary implements encoding.BinaryUnmarshaler. Wraps SetBytes
Source Files