Module crypto::bignum

#include <std/crypto/bignum.h> source

fixed-width modular arithmetic (Montgomery form).

The multi-precision core std's public-key code shares: RSA (rsa.h) and the NIST curves (ec.h). Numbers are little-endian arrays of 32-bit limbs of a fixed width n (the modulus' width), so a number's length — and the work done on it — never depends on its value. Montgomery multiplication (CIOS) ends with a branch-free conditional subtraction, and the modular add/sub/select helpers are branch-free too; only bn_cmp_ and the public- exponent bn_mod_exp_public look at values, and they are for public data.

BnMont is a modulus with its Montgomery constants, for moduli of up to BN_LIMBS_MAX * 32 bits (RSA-4096 and a little headroom):

struct BnMont m;
if (!m.init(&modulus[0], modLen)) { /* even, zero or too big */ }
bn_mod_exp_public(&m, &sig[0], sigLen, &e[0], eLen, &out[0]);   // out: modLen bytes

The '_'-suffixed raw-limb functions are std-internal (unsafe pointers). Odd moduli only (every RSA modulus and curve prime/order is odd). Freestanding-safe.

Structs

BnMont

Functions

bn_mod_exp_public	out (m.bytes bytes, big-endian) = base^exp mod m, for a public exponent (its bits are looked at: not for private keys). 'base' (big-endian, base_len <= m.bytes) must be < m; 0 if it isn't, 1 otherwise.
bn_mod_exp_secret	out = base^exp mod m in constant time for a secret exponent (fixed 4-bit windows over every exponent bit, table entries read by masked scans). exp_len bytes of exponent are processed regardless of value.

Macros

BN_LIMBS_MAX