crypto::bigint
Bigint provides constant time operations on big integers. This module is limited in scope, therefore the user must exercise caution and read the documentation carefully to avoid misuse. Restrictions apply to the compatibility of differently-sized big integers, and some functions require an uneven modulo.
A big integer is an array of word and must be encoded using encode, encodemod or encodereduce. See encodelen on how to calculate the required size of the array. The big integer will also store its announced bit length, i.e. the number of bits that are actually used to store its value; and the effective word length, i.e. the number of words that are actually used to store the value. The value may be decoded back to its byte format by decode.
Repeated modular multiplication is supported via montgomery multiplication. See tomonty and frommonty on how to convert from and back to this format and montymul for the actual multiplication operation.
This is a low-level module which implements cryptographic primitives. Direct use of cryptographic primitives is not recommended for non-experts, as incorrect use of these primitives can easily lead to the introduction of security vulnerabilities. Non-experts are advised to use the high-level operations available in the top-level crypto:: module.
Be advised that Hare's cryptography implementations have not been audited.
Index
Types
type word = u32;
Constants
def WORD_BITMASK: word = 2147483647;
def WORD_BITSZ: u32 = 31;
Functions
fn add(a: []word, b: const []word, ctl: u32) u32;
fn decode(dest: []u8, src: const []word) void;
fn decodelen(src: const []word) size;
fn decrodd(x: []word) void;
fn encode(dest: []word, src: const []u8) void;
fn encodelen(x: []u8) size;
fn encodemod(dest: []word, src: const []u8, m: const []word) u32;
fn encodereduce(dest: []word, src: const []u8, m: const []word) void;
fn ewordlen(x: const []word) u32;
fn frommonty(x: []word, m: const []word, m0i: word) void;
fn iszero(x: []word) u32;
fn modpow(x: []word, e: const []u8, m: const []word, m0i: u32, tmp: []word) u32;
fn montymul(d: []word, x: const []word, y: const []word, m: const []word, m0i: u32) void;
fn mulacc(d: []word, a: const []word, b: const []word) void;
fn ninv(m0: word) word;
fn reduce(x: []word, a: const []word, m: const []word) void;
fn rshift(x: []word, count: word) void;
fn sub(a: []word, b: const []word, do: u32) u32;
fn tomonty(x: []word, m: const []word) void;
fn zero(x: []word, ebitlen: word) void;
Types
type word
type word = u32;
A big integer is stored in an array of words. The first word holds information about the effective size of the big integer. The subsequend words encode the value in little-endian order. The WORD_BITMASK masks the bits that are actually used to store the value in each word.
Constants
def WORD_BITMASK
def WORD_BITMASK: word = 2147483647;
Bitmask for bits that are used for storing the value in a word.
def WORD_BITSZ
def WORD_BITSZ: u32 = 31;
Number of bits that are used for storing the value in a word.
Functions
fn add
fn add(a: []word, b: const []word, ctl: u32) u32;
Adds 'b' to 'a', if 'ctl' is 1. If 'ctl' is 0, the result will be discarded. Returns the carry, if the addition overflows.
'a' and 'b' must have the same effective word length.
fn decode
fn decode(dest: []u8, src: const []word) void;
Decode 'src' into a big-endian unsigned byte array. The caller must ensure that 'dest' has enough space to store the decoded value. See decodelen on how to determine the required length.
fn decodelen
fn decodelen(src: const []word) size;
Returns the number of bytes required to store a big integer given by 'src'.
For static allocation following expression may be used:
((len(src) - 1) * WORD_BITSZ + 7) / 8
fn decrodd
fn decrodd(x: []word) void;
Decrements 1 from an odd integer 'x'.
fn encode
fn encode(dest: []word, src: const []u8) void;
Encode 'src' from its big-endian unsigned encoding into the internal representation. The caller must make sure that 'dest' has enough space to store 'src'. See encodelen for how to calculate the required size.
This function runs in constant time for given 'src' length.
fn encodelen
fn encodelen(x: []u8) size;
Minimal required words to encode 'x' into an []word. To statically allocate resources, following expression may be used:
((number_of_bits + WORD_BITSZ - 1) / WORD_BITSZ) + 1
fn encodemod
fn encodemod(dest: []word, src: const []u8, m: const []word) u32;
Encodes an integer from its big-endian unsigned encoding. 'src' must be lower than 'm'. If not 'dest' will be set to 0. 'dest' will have the announced bit length of 'm' after decoding.
The return value is 1 if the decoded value fits within 'm' or 0 otherwise.
This function runs in constant time for a given 'src' length and announced bit length of m, independent of whether the value fits within 'm' or not.
fn encodereduce
fn encodereduce(dest: []word, src: const []u8, m: const []word) void;
Encode an integer from its big-endian unsigned representation, and reduce it modulo the provided modulus 'm'. The announced bit length of the result is set to be equal to that of the modulus.
'dest' must be distinct from 'm'.
fn ewordlen
fn ewordlen(x: const []word) u32;
Get the effective word lenght of 'x'. The effective wordlen is the number of words that are used to represent the actual value. Eg. the number 7 will have an effective word length of 1, no matter of len(x). The first element containing the encoded word len is not added to the result.
fn frommonty
fn frommonty(x: []word, m: const []word, m0i: word) void;
Convert a modular integer back from Montgomery representation. The integer 'x' must be less than 'm', but with the same announced bit length. The 'm0i' parameter is equal to -(1/m0) mod 2^32, where m0 is the least significant value word of 'm' (this works only if 'm' is an odd integer). See ninv for how to get this value.
fn iszero
fn iszero(x: []word) u32;
Checks whether the effective words of 'x' are zero. Returns 1 if so, or 0 otherwise.
fn modpow
fn modpow(x: []word, e: const []u8, m: const []word, m0i: u32, tmp: []word) u32;
Compute a modular exponentiation. 'x' must be an integer modulo 'm' (same announced bit length, lower value). 'm' must be odd. The exponent is in big-endian unsigned notation, over len(e) bytes. The 'm0i' parameter is equal to -(1/m0) mod 2^31, where m0 is the least significant value word of 'm' (this works only if 'm' is an odd integer). See ninv on how to get this value. The 'tmp' array is used for temporaries and MUST be large enough to accommodate at least two temporary values with the same size as 'm' (including the leading 'bit length' word). If there is room for more temporaries, then this function may use the extra room for window-based optimisation, resulting in faster computations.
Returned value is 1 on success, 0 on error. An error is reported if the provided 'tmp' array is too short.
fn montymul
fn montymul(d: []word, x: const []word, y: const []word, m: const []word, m0i: u32) void;
Compute a modular Montgomery multiplication. 'd' is filled with the value of 'x'*'y'/R modulo 'm' (where R is the Montgomery factor). The array 'd' must be distinct from 'x', 'y' and 'm'. 'x' and 'y' must be numerically lower than 'm'. 'x' and 'y' may be the same array. The 'm0i' parameter is equal to
- (1/m0) mod 2^32, where m0 is the least significant value word of 'm' (this works only if 'm' is an odd integer). See ninv for how to get this value.
fn mulacc
fn mulacc(d: []word, a: const []word, b: const []word) void;
Compute 'd' + 'a' * 'b', result in 'd'. The initial announced bit length of 'd' MUST match that of 'a'. The 'd' array MUST be large enough to accommodate the full result, plus (possibly) an extra word. The resulting announced bit length of 'd' will be the sum of the announced bit lengths of 'a' and 'b' (therefore, it may be larger than the actual bit length of the numerical result).
'a' and 'b' may be the same array. 'd' must be disjoint from both 'a' and 'b'.
fn ninv
fn ninv(m0: word) word;
Calculates "m0i" which is equal to -(1/'m0') mod 2^WORD_BITSZ. 'm0' is the the first significant word of a big integer, which is the word at index 1.
fn reduce
fn reduce(x: []word, a: const []word, m: const []word) void;
Reduce an integer 'a' modulo another 'm'. The result is written in 'x' and its announced bit length is set to be equal to that of 'm'.
'x' must be distinct from 'a' and 'm'.
This function runs in constant time for given announced bit lengths of 'a' and 'm'.
fn rshift
fn rshift(x: []word, count: word) void;
Right-shift an integer 'x' by 'count'. The shift amount must be less than WORD_BITSZ.
fn sub
fn sub(a: []word, b: const []word, do: u32) u32;
Subtracts 'b' from 'a', if 'ctl' is 1. If 'ctl' is 0, the result will be discared. Returns the carry, if the subtraction overflows.
'a' and 'b' must be of the same effective word length.
fn tomonty
fn tomonty(x: []word, m: const []word) void;
Convert a modular integer to Montgomery representation. The integer 'x' must be lower than 'm', but with the same announced bit length.
fn zero
fn zero(x: []word, ebitlen: word) void;
Sets encoded bitlen of 'x' to 'ebitlen' and then zeroes its effective words.