bignum

nimony/lib/std/crypto/bignum.nim

Fixed-capacity unsigned big integers and Montgomery arithmetic, for SIGNATURE VERIFICATION.

Everything a verifier computes is public — the signature, the message digest, the public key — so this module is deliberately not constant time: modExp skips zero bits and sub branches on a comparison. Do not use it with a secret.

A number is at most MaxBits wide (RSA-4096 plus headroom for the Montgomery product), held in a fixed array of 32-bit limbs together with a range-typed limb count, which is what lets every index in here be proven rather than checked.

const MaxBits: int64
const MaxLimbs: int64
Two spare limbs: the Montgomery product keeps n + 2 words of state.
type Limbs = array[0..129, uint32]
type LimbCount = 1..128

type BigNum = object
  limbs: array[0..129, uint32]
  n: 1..128

type Mont = object
  m: BigNum
  m0inv: uint32
  r2: array[0..129, uint32]

func bitLen(a: BigNum): int64
func isZero(a: BigNum): bool
func fromBytesBE(data: openArray[uint8]; res: var BigNum): bool
Reads a big-endian unsigned number. Leading zero bytes are free; false when the number does not fit in MaxBits.
func toBytesBE`body(a`b: BigNum; outLen`b: int64): seq[uint8]
The low outLen bytes of a, big-endian, zero padded on the left.
func toBytesBE(a: BigNum; outLen: int64): seq[uint8]
The low outLen bytes of a, big-endian, zero padded on the left.
func cmp(a: BigNum; b: BigNum): int64
func initMont(m: BigNum; res: var Mont): bool
false for an even or trivially small modulus.
func montMul(ctx: Mont; a: array[0..129, uint32]; b: array[0..129, uint32]): array[0..129, uint32]
a * b * R^-1 mod m (CIOS). Operands must be below m.
func toMont(ctx: Mont; a: array[0..129, uint32]): array[0..129, uint32]
func fromMont(ctx: Mont; a: array[0..129, uint32]): array[0..129, uint32]
func reduce(ctx: Mont; a: BigNum): array[0..129, uint32]
a mod m for any a of at most m.n limbs below 2 * m... and more generally for any a that fits m.n limbs: subtract until below.
func modAdd(ctx: Mont; a: array[0..129, uint32]; b: array[0..129, uint32]): array[0..129, uint32]
func modSub(ctx: Mont; a: array[0..129, uint32]; b: array[0..129, uint32]): array[0..129, uint32]
func montPow(ctx: Mont; base: array[0..129, uint32]; exp: BigNum): array[0..129, uint32]
base^exp with base and the result in Montgomery form. Left-to-right square-and-multiply: variable time, for public exponents only.
func modExp(base: BigNum; exp: BigNum; ctx: Mont): BigNum
base^exp mod m.
func montInverse(ctx: Mont; a: array[0..129, uint32]): array[0..129, uint32]
a^-1 for a PRIME modulus by Fermat, Montgomery form in and out.
proc fromHex(hex: string): BigNum
For curve and test constants written as hex. Panics on a malformed or oversized literal, which is a programming error, not input.