const _W … const _S … type choice … func not(c choice) choice { … } const yes … const no … // ctMask is all 1s if on is yes, and all 0s otherwise. func ctMask(on choice) uint { … } // ctEq returns 1 if x == y, and 0 otherwise. The execution time of this // function does not depend on its inputs. func ctEq(x, y uint) choice { … } type Nat … const preallocTarget … const preallocLimbs … // NewNat returns a new nat with a size of zero, just like new(Nat), but with // the preallocated capacity to hold a number of up to preallocTarget bits. // NewNat inlines, so the allocation can live on the stack. func NewNat() *Nat { … } // expand expands x to n limbs, leaving its value unchanged. func (x *Nat) expand(n int) *Nat { … } // reset returns a zero nat of n limbs, reusing x's storage if n <= cap(x.limbs). func (x *Nat) reset(n int) *Nat { … } // set assigns x = y, optionally resizing x to the appropriate size. func (x *Nat) set(y *Nat) *Nat { … } // setBig assigns x = n, optionally resizing n to the appropriate size. // // The announced length of x is set based on the actual bit size of the input, // ignoring leading zeroes. func (x *Nat) setBig(n *big.Int) *Nat { … } // Bytes returns x as a zero-extended big-endian byte slice. The size of the // slice will match the size of m. // // x must have the same size as m and it must be reduced modulo m. func (x *Nat) Bytes(m *Modulus) []byte { … } // SetBytes assigns x = b, where b is a slice of big-endian bytes. // SetBytes returns an error if b >= m. // // The output will be resized to the size of m and overwritten. func (x *Nat) SetBytes(b []byte, m *Modulus) (*Nat, error) { … } // SetOverflowingBytes assigns x = b, where b is a slice of big-endian bytes. // SetOverflowingBytes returns an error if b has a longer bit length than m, but // reduces overflowing values up to 2^⌈log2(m)⌉ - 1. // // The output will be resized to the size of m and overwritten. func (x *Nat) SetOverflowingBytes(b []byte, m *Modulus) (*Nat, error) { … } // bigEndianUint returns the contents of buf interpreted as a // big-endian encoded uint value. func bigEndianUint(buf []byte) uint { … } func (x *Nat) setBytes(b []byte, m *Modulus) error { … } // Equal returns 1 if x == y, and 0 otherwise. // // Both operands must have the same announced length. func (x *Nat) Equal(y *Nat) choice { … } // IsZero returns 1 if x == 0, and 0 otherwise. func (x *Nat) IsZero() choice { … } // cmpGeq returns 1 if x >= y, and 0 otherwise. // // Both operands must have the same announced length. func (x *Nat) cmpGeq(y *Nat) choice { … } // assign sets x <- y if on == 1, and does nothing otherwise. // // Both operands must have the same announced length. func (x *Nat) assign(on choice, y *Nat) *Nat { … } // add computes x += y and returns the carry. // // Both operands must have the same announced length. func (x *Nat) add(y *Nat) (c uint) { … } // sub computes x -= y. It returns the borrow of the subtraction. // // Both operands must have the same announced length. func (x *Nat) sub(y *Nat) (c uint) { … } type Modulus … // rr returns R*R with R = 2^(_W * n) and n = len(m.nat.limbs). func rr(m *Modulus) *Nat { … } // minusInverseModW computes -x⁻¹ mod _W with x odd. // // This operation is used to precompute a constant involved in Montgomery // multiplication. func minusInverseModW(x uint) uint { … } // NewModulusFromBig creates a new Modulus from a [big.Int]. // // The Int must be odd. The number of significant bits (and nothing else) is // leaked through timing side-channels. func NewModulusFromBig(n *big.Int) (*Modulus, error) { … } // bitLen is a version of bits.Len that only leaks the bit length of n, but not // its value. bits.Len and bits.LeadingZeros use a lookup table for the // low-order bits on some architectures. func bitLen(n uint) int { … } // Size returns the size of m in bytes. func (m *Modulus) Size() int { … } // BitLen returns the size of m in bits. func (m *Modulus) BitLen() int { … } // Nat returns m as a Nat. The return value must not be written to. func (m *Modulus) Nat() *Nat { … } // shiftIn calculates x = x << _W + y mod m. // // This assumes that x is already reduced mod m. func (x *Nat) shiftIn(y uint, m *Modulus) *Nat { … } // Mod calculates out = x mod m. // // This works regardless how large the value of x is. // // The output will be resized to the size of m and overwritten. func (out *Nat) Mod(x *Nat, m *Modulus) *Nat { … } // ExpandFor ensures x has the right size to work with operations modulo m. // // The announced size of x must be smaller than or equal to that of m. func (x *Nat) ExpandFor(m *Modulus) *Nat { … } // resetFor ensures out has the right size to work with operations modulo m. // // out is zeroed and may start at any size. func (out *Nat) resetFor(m *Modulus) *Nat { … } // maybeSubtractModulus computes x -= m if and only if x >= m or if "always" is yes. // // It can be used to reduce modulo m a value up to 2m - 1, which is a common // range for results computed by higher level operations. // // always is usually a carry that indicates that the operation that produced x // overflowed its size, meaning abstractly x > 2^_W*n > m even if x < m. // // x and m operands must have the same announced length. func (x *Nat) maybeSubtractModulus(always choice, m *Modulus) { … } // Sub computes x = x - y mod m. // // The length of both operands must be the same as the modulus. Both operands // must already be reduced modulo m. func (x *Nat) Sub(y *Nat, m *Modulus) *Nat { … } // Add computes x = x + y mod m. // // The length of both operands must be the same as the modulus. Both operands // must already be reduced modulo m. func (x *Nat) Add(y *Nat, m *Modulus) *Nat { … } // montgomeryRepresentation calculates x = x * R mod m, with R = 2^(_W * n) and // n = len(m.nat.limbs). // // Faster Montgomery multiplication replaces standard modular multiplication for // numbers in this representation. // // This assumes that x is already reduced mod m. func (x *Nat) montgomeryRepresentation(m *Modulus) *Nat { … } // montgomeryReduction calculates x = x / R mod m, with R = 2^(_W * n) and // n = len(m.nat.limbs). // // This assumes that x is already reduced mod m. func (x *Nat) montgomeryReduction(m *Modulus) *Nat { … } // montgomeryMul calculates x = a * b / R mod m, with R = 2^(_W * n) and // n = len(m.nat.limbs), also known as a Montgomery multiplication. // // All inputs should be the same length and already reduced modulo m. // x will be resized to the size of m and overwritten. func (x *Nat) montgomeryMul(a *Nat, b *Nat, m *Modulus) *Nat { … } // addMulVVW multiplies the multi-word value x by the single-word value y, // adding the result to the multi-word value z and returning the final carry. // It can be thought of as one row of a pen-and-paper column multiplication. func addMulVVW(z, x []uint, y uint) (carry uint) { … } // Mul calculates x = x * y mod m. // // The length of both operands must be the same as the modulus. Both operands // must already be reduced modulo m. func (x *Nat) Mul(y *Nat, m *Modulus) *Nat { … } // Exp calculates out = x^e mod m. // // The exponent e is represented in big-endian order. The output will be resized // to the size of m and overwritten. x must already be reduced modulo m. func (out *Nat) Exp(x *Nat, e []byte, m *Modulus) *Nat { … } // ExpShortVarTime calculates out = x^e mod m. // // The output will be resized to the size of m and overwritten. x must already // be reduced modulo m. This leaks the exponent through timing side-channels. func (out *Nat) ExpShortVarTime(x *Nat, e uint, m *Modulus) *Nat { … }
Codebase Browser
go