bigmod

Imports

Imports #

_ "crypto/internal/fips140/check"
"crypto/internal/fips140deps/byteorder"
"errors"
"math/bits"
"crypto/internal/fips140deps/cpu"
"crypto/internal/impl"
"unsafe"
"unsafe"

Constants & Variables

_S const #

_S is the size in bytes of our limbs.

const _S = *ast.BinaryExpr

_W const #

_W is the size in bits of our limbs.

const _W = bits.UintSize

no const #

const no = *ast.CallExpr

preallocLimbs const #

const preallocLimbs = *ast.BinaryExpr

preallocTarget const #

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.

const preallocTarget = 2048

supportADX var #

var supportADX = *ast.BinaryExpr

yes const #

const yes = *ast.CallExpr

Type Aliases

choice type #

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.

type choice uint

Structs

Modulus struct #

Modulus is used for modular arithmetic, precomputing relevant constants. A Modulus can leak the exact number of bits needed to store its value and is stored without padding. Its actual value is still kept secret.

type Modulus struct {
nat *Nat
odd bool
m0inv uint
rr *Nat
}

Nat struct #

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.

type Nat struct {
limbs []uint
}

Functions

Add method #

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. go:norace

func (x *Nat) Add(y *Nat, m *Modulus) *Nat

BitLen method #

BitLen returns the size of m in bits.

func (m *Modulus) BitLen() int

BitLenVarTime method #

BitLenVarTime returns the actual size of x in bits. The actual size of x (but nothing more) leaks through timing side-channels. Note that this is ordinarily secret, as opposed to the announced size of x.

func (x *Nat) BitLenVarTime() int

Bits method #

Bits returns x as a little-endian slice of uint. The length of the slice matches the announced length of x. The result and x share the same underlying array.

func (x *Nat) Bits() []uint

Bytes method #

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 less than or equal to m.

func (x *Nat) Bytes(m *Modulus) []byte

DivShortVarTime method #

DivShortVarTime calculates x = x / y and returns the remainder. It panics if y is zero. go:norace

func (x *Nat) DivShortVarTime(y uint) uint

Equal method #

Equal returns 1 if x == y, and 0 otherwise. Both operands must have the same announced length. go:norace

func (x *Nat) Equal(y *Nat) choice

Exp method #

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. m must be odd, or Exp will panic. go:norace

func (out *Nat) Exp(x *Nat, e []byte, m *Modulus) *Nat

ExpShortVarTime method #

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. m must be odd, or ExpShortVarTime will panic.

func (out *Nat) ExpShortVarTime(x *Nat, e uint, m *Modulus) *Nat

ExpandFor method #

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

GCDVarTime method #

GCDVarTime calculates x = GCD(a, b) where at least one of a or b is odd, and both are non-zero. If GCDVarTime returns an error, x is not modified. The output will be resized to the size of the larger of a and b.

func (x *Nat) GCDVarTime(a *Nat, b *Nat) (*Nat, error)

InverseVarTime method #

InverseVarTime calculates x = a⁻¹ mod m and returns (x, true) if a is invertible. Otherwise, InverseVarTime returns (x, false) and x is not modified. a must be reduced modulo m, but doesn't need to have the same size. The output will be resized to the size of m and overwritten. go:norace

func (x *Nat) InverseVarTime(a *Nat, m *Modulus) (*Nat, bool)

IsMinusOne method #

IsMinusOne returns 1 if x == -1 mod m, and 0 otherwise. The length of x must be the same as the modulus. x must already be reduced modulo m. go:norace

func (x *Nat) IsMinusOne(m *Modulus) choice

IsOdd method #

IsOdd returns 1 if x is odd, and 0 otherwise.

func (x *Nat) IsOdd() choice

IsOne method #

IsOne returns 1 if x == 1, and 0 otherwise. go:norace

func (x *Nat) IsOne() choice

IsZero method #

IsZero returns 1 if x == 0, and 0 otherwise. go:norace

func (x *Nat) IsZero() choice

Mod method #

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. go:norace

func (out *Nat) Mod(x *Nat, m *Modulus) *Nat

Mul method #

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. go:norace

func (x *Nat) Mul(y *Nat, m *Modulus) *Nat

Nat method #

Nat returns m as a Nat.

func (m *Modulus) Nat() *Nat

NewModulus function #

NewModulus creates a new Modulus from a slice of big-endian bytes. The modulus must be greater than one. The number of significant bits and whether the modulus is even is leaked through timing side-channels.

func NewModulus(b []byte) (*Modulus, error)

NewModulusProduct function #

NewModulusProduct creates a new Modulus from the product of two numbers represented as big-endian byte slices. The result must be greater than one. go:norace

func NewModulusProduct(a []byte, b []byte) (*Modulus, error)

NewNat function #

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

SetBytes method #

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. go:norace

func (x *Nat) SetBytes(b []byte, m *Modulus) (*Nat, error)

SetOverflowingBytes method #

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)

SetUint method #

SetUint assigns x = y. The output will be resized to a single limb and overwritten.

func (x *Nat) SetUint(y uint) *Nat

ShiftRightVarTime method #

ShiftRightVarTime sets x = x >> n. The announced length of x is unchanged. go:norace

func (x *Nat) ShiftRightVarTime(n uint) *Nat

Size method #

Size returns the size of m in bytes.

func (m *Modulus) Size() int

Sub method #

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. go:norace

func (x *Nat) Sub(y *Nat, m *Modulus) *Nat

SubOne method #

SubOne computes x = x - 1 mod m. The length of x must be the same as the modulus.

func (x *Nat) SubOne(m *Modulus) *Nat

TrailingZeroBitsVarTime method #

TrailingZeroBitsVarTime returns the number of trailing zero bits in x.

func (x *Nat) TrailingZeroBitsVarTime() uint

add method #

add computes x += y and returns the carry. Both operands must have the same announced length. go:norace

func (x *Nat) add(y *Nat) (c uint)

addMulVVW function #

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. go:norace

func addMulVVW(z []uint, x []uint, y uint) (carry uint)

addMulVVW1024 function #

func addMulVVW1024(z *uint, x *uint, y uint) (c uint)

addMulVVW1024 function #

go:noescape

func addMulVVW1024(z *uint, x *uint, y uint) (c uint)

addMulVVW1024 function #

func addMulVVW1024(z *uint, x *uint, y uint) (c uint)

addMulVVW1536 function #

go:noescape

func addMulVVW1536(z *uint, x *uint, y uint) (c uint)

addMulVVW1536 function #

func addMulVVW1536(z *uint, x *uint, y uint) (c uint)

addMulVVW1536 function #

func addMulVVW1536(z *uint, x *uint, y uint) (c uint)

addMulVVW2048 function #

go:noescape

func addMulVVW2048(z *uint, x *uint, y uint) (c uint)

addMulVVW2048 function #

func addMulVVW2048(z *uint, x *uint, y uint) (c uint)

addMulVVW2048 function #

func addMulVVW2048(z *uint, x *uint, y uint) (c uint)

addMulVVWWasm function #

func addMulVVWWasm(z *uint, x *uint, y uint, n uintptr) (carry uint)

assign method #

assign sets x <- y if on == 1, and does nothing otherwise. Both operands must have the same announced length. go:norace

func (x *Nat) assign(on choice, y *Nat) *Nat

bigEndianUint function #

bigEndianUint returns the contents of buf interpreted as a big-endian encoded uint value.

func bigEndianUint(buf []byte) uint

bitLen function #

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

cmpGeq method #

cmpGeq returns 1 if x >= y, and 0 otherwise. Both operands must have the same announced length. go:norace

func (x *Nat) cmpGeq(y *Nat) choice

ctEq function #

ctEq returns 1 if x == y, and 0 otherwise. The execution time of this function does not depend on its inputs.

func ctEq(x uint, y uint) choice

ctMask function #

ctMask is all 1s if on is yes, and all 0s otherwise.

func ctMask(on choice) uint

expand method #

expand expands x to n limbs, leaving its value unchanged.

func (x *Nat) expand(n int) *Nat

extendedGCD function #

extendedGCD computes u and A such that a = GCD(a, m) and u = A*a - B*m. u will have the size of the larger of a and m, and A will have the size of m. It is an error if either a or m is zero, or if they are both even.

func extendedGCD(a *Nat, m *Nat) (u *Nat, A *Nat, err error)

idx function #

func idx(x *uint, i uintptr) *uint

init function #

func init()

maybeSubtractModulus method #

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. go:norace

func (x *Nat) maybeSubtractModulus(always choice, m *Modulus)

minusInverseModW function #

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

montgomeryMul method #

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. go:norace

func (x *Nat) montgomeryMul(a *Nat, b *Nat, m *Modulus) *Nat

montgomeryReduction method #

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

montgomeryRepresentation method #

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

newModulus function #

func newModulus(n *Nat) (*Modulus, error)

not function #

func not(c choice) choice

reset method #

reset returns a zero nat of n limbs, reusing x's storage if n <= cap(x.limbs).

func (x *Nat) reset(n int) *Nat

resetFor method #

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

resetToBytes method #

resetToBytes assigns x = b, where b is a slice of big-endian bytes, 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) resetToBytes(b []byte) *Nat

rr function #

rr returns R*R with R = 2^(_W * n) and n = len(m.nat.limbs).

func rr(m *Modulus) *Nat

rshift1 function #

go:norace

func rshift1(a *Nat, carry uint)

set method #

set assigns x = y, optionally resizing x to the appropriate size.

func (x *Nat) set(y *Nat) *Nat

setBytes method #

func (x *Nat) setBytes(b []byte) error

shiftIn method #

shiftIn calculates x = x << _W + y mod m. This assumes that x is already reduced mod m. go:norace

func (x *Nat) shiftIn(y uint, m *Modulus) *Nat

sub method #

sub computes x -= y. It returns the borrow of the subtraction. Both operands must have the same announced length. go:norace

func (x *Nat) sub(y *Nat) (c uint)

trim method #

trim reduces the size of x to match its value.

func (x *Nat) trim() *Nat

Generated with Arrow