Package-Level Type Names (total 3, in which 2 are exported)
/* sort exporteds by: | */
Modulus is used for modular arithmetic, precomputing relevant constants.
Moduli are assumed to be odd numbers. Moduli can also leak the exact
number of bits needed to store their value, and are stored without padding.
Their actual value is still kept secret. // number of leading zeros in the modulus // -nat.limbs[0]⁻¹ mod _W The underlying natural number for this modulus.
This will be stored without any padding, and shouldn't alias with any
other natural number being used. // R*R for montgomeryRepresentation BitLen returns the size of m in bits. Nat returns m as a Nat. The return value must not be written to. Size returns the size of m in bytes.
func NewModulusFromBig(n *big.Int) (*Modulus, error)
func (*Nat).Add(y *Nat, m *Modulus) *Nat
func (*Nat).Bytes(m *Modulus) []byte
func (*Nat).Exp(x *Nat, e []byte, m *Modulus) *Nat
func (*Nat).ExpandFor(m *Modulus) *Nat
func (*Nat).ExpShort(x *Nat, e uint, m *Modulus) *Nat
func (*Nat).Mod(x *Nat, m *Modulus) *Nat
func (*Nat).Mul(y *Nat, m *Modulus) *Nat
func (*Nat).SetBytes(b []byte, m *Modulus) (*Nat, error)
func (*Nat).SetOverflowingBytes(b []byte, m *Modulus) (*Nat, error)
func (*Nat).Sub(y *Nat, m *Modulus) *Nat
func rr(m *Modulus) *Nat
func (*Nat).maybeSubtractModulus(always choice, m *Modulus)
func (*Nat).montgomeryMul(a *Nat, b *Nat, m *Modulus) *Nat
func (*Nat).montgomeryReduction(m *Modulus) *Nat
func (*Nat).montgomeryRepresentation(m *Modulus) *Nat
func (*Nat).resetFor(m *Modulus) *Nat
func (*Nat).setBytes(b []byte, m *Modulus) error
func (*Nat).shiftIn(y uint, m *Modulus) *Nat
Nat represents an arbitrary natural number
Each Nat has an announced length, which is the number of limbs it has stored.
Operations on this number are allowed to leak this length, but will not leak
any information about the values contained in those limbs. limbs is little-endian in base 2^W with W = bits.UintSize. 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. 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. Equal returns 1 if x == y, and 0 otherwise.
Both operands must have the same announced length. 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. ExpShort 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 exact bit size of the exponent. 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. IsZero returns 1 if x == 0, and 0 otherwise. 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. 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. 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. 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. 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. add computes x += y and returns the carry.
Both operands must have the same announced length. assign sets x <- y if on == 1, and does nothing otherwise.
Both operands must have the same announced length. cmpGeq returns 1 if x >= y, and 0 otherwise.
Both operands must have the same announced length. expand expands x to n limbs, leaving its value unchanged. 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. 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. 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. 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. reset returns a zero nat of n limbs, reusing x's storage if n <= cap(x.limbs). resetFor ensures out has the right size to work with operations modulo m.
out is zeroed and may start at any size. set assigns x = y, optionally resizing x to the appropriate size. 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.(*Nat) setBytes(b []byte, m *Modulus) error shiftIn calculates x = x << _W + y mod m.
This assumes that x is already reduced mod m. sub computes x -= y. It returns the borrow of the subtraction.
Both operands must have the same announced length.
func NewNat() *Nat
func (*Modulus).Nat() *Nat
func (*Nat).Add(y *Nat, m *Modulus) *Nat
func (*Nat).Exp(x *Nat, e []byte, m *Modulus) *Nat
func (*Nat).ExpandFor(m *Modulus) *Nat
func (*Nat).ExpShort(x *Nat, e uint, m *Modulus) *Nat
func (*Nat).Mod(x *Nat, m *Modulus) *Nat
func (*Nat).Mul(y *Nat, m *Modulus) *Nat
func (*Nat).SetBytes(b []byte, m *Modulus) (*Nat, error)
func (*Nat).SetOverflowingBytes(b []byte, m *Modulus) (*Nat, error)
func (*Nat).Sub(y *Nat, m *Modulus) *Nat
func rr(m *Modulus) *Nat
func (*Nat).assign(on choice, y *Nat) *Nat
func (*Nat).expand(n int) *Nat
func (*Nat).montgomeryMul(a *Nat, b *Nat, m *Modulus) *Nat
func (*Nat).montgomeryReduction(m *Modulus) *Nat
func (*Nat).montgomeryRepresentation(m *Modulus) *Nat
func (*Nat).reset(n int) *Nat
func (*Nat).resetFor(m *Modulus) *Nat
func (*Nat).set(y *Nat) *Nat
func (*Nat).setBig(n *big.Int) *Nat
func (*Nat).shiftIn(y uint, m *Modulus) *Nat
func crypto/ecdsa.randomPoint[Point](c *ecdsa.nistCurve[Point], rand io.Reader) (k *Nat, p Point, err error)
func (*Nat).Add(y *Nat, m *Modulus) *Nat
func (*Nat).Equal(y *Nat) choice
func (*Nat).Exp(x *Nat, e []byte, m *Modulus) *Nat
func (*Nat).ExpShort(x *Nat, e uint, m *Modulus) *Nat
func (*Nat).Mod(x *Nat, m *Modulus) *Nat
func (*Nat).Mul(y *Nat, m *Modulus) *Nat
func (*Nat).Sub(y *Nat, m *Modulus) *Nat
func (*Nat).add(y *Nat) (c uint)
func (*Nat).assign(on choice, y *Nat) *Nat
func (*Nat).cmpGeq(y *Nat) choice
func (*Nat).montgomeryMul(a *Nat, b *Nat, m *Modulus) *Nat
func (*Nat).montgomeryMul(a *Nat, b *Nat, m *Modulus) *Nat
func (*Nat).set(y *Nat) *Nat
func (*Nat).sub(y *Nat) (c uint)
func crypto/ecdsa.hashToNat[Point](c *ecdsa.nistCurve[Point], e *Nat, hash []byte)
func crypto/ecdsa.inverse[Point](c *ecdsa.nistCurve[Point], kInv, k *Nat)
choice represents a constant-time boolean. The value of choice is always
either 1 or 0. We use an int instead of bool in order to make decisions in
constant time by turning it into a mask.
func (*Nat).Equal(y *Nat) choice
func (*Nat).IsZero() choice
func ctEq(x, y uint) choice
func ctGeq(x, y uint) choice
func not(c choice) choice
func (*Nat).cmpGeq(y *Nat) choice
func ctMask(on choice) uint
func not(c choice) choice
func (*Nat).assign(on choice, y *Nat) *Nat
func (*Nat).maybeSubtractModulus(always choice, m *Modulus)
const no
const yes
Package-Level Functions (total 14, in which 2 are exported)
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.
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.
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.
bigEndianUint returns the contents of buf interpreted as a
big-endian encoded uint value.
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.
ctEq returns 1 if x == y, and 0 otherwise. The execution time of this
function does not depend on its inputs.
ctGeq returns 1 if x >= y, and 0 otherwise. The execution time of this
function does not depend on its inputs.
ctMask is all 1s if on is yes, and all 0s otherwise.
minusInverseModW computes -x⁻¹ mod _W with x odd.
This operation is used to precompute a constant involved in Montgomery
multiplication.
preallocTarget is the size in bits of the numbers used to implement the most
common and most performant RSA key size. It's also enough to cover some of
the operations of key sizes up to 4096.
The pages are generated with Goldsv0.6.7. (GOOS=linux GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu.
PR and bug reports are welcome and can be submitted to the issue list.
Please follow @Go100and1 (reachable from the left QR code) to get the latest news of Golds.
