crypto::bigint+x86_64 +linux

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;

Constants

const WORD_BITMASK: word;
const WORD_BITSZ: u32;

Functions

fn add([]word, const []word, u32) u32;
fn decode([]u8, const []word) void;
fn decodelen(const []word) size;
fn decrodd([]word) void;
fn encode([]word, const []u8) void;
fn encodelen([]u8) size;
fn encodemod([]word, const []u8, const []word) u32;
fn encodereduce([]word, const []u8, const []word) void;
fn frommonty([]word, const []word, word) void;
fn modpow([]word, const []u8, const []word, u32, []word) u32;
fn montymul([]word, const []word, const []word, const []word, u32) void;
fn mulacc([]word, const []word, const []word) void;
fn ninv(word) word;
fn reduce([]word, const []word, const []word) void;
fn rshift([]word, word) void;
fn sub([]word, const []word, u32) u32;
fn tomonty([]word, const []word) void;
fn zero([]word, word) void;

Types

type word[link] 

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[link] 

def WORD_BITMASK: word;

Bitmask for bits that are used for storing the value in a word.

def WORD_BITSZ[link] 

def WORD_BITSZ: u32;

Number of bits that are used for storing the value in a word.

Functions

fn add[link] 

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[link] 

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[link] 

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[link] 

fn decrodd(x: []word) void;

Decrements 1 from an odd integer 'x'.

fn encode[link] 

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[link] 

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[link] 

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[link] 

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 frommonty[link] 

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 modpow[link] 

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[link] 

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[link] 

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[link] 

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[link] 

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[link] 

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[link] 

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[link] 

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[link] 

fn zero(x: []word, ebitlen: word) void;

Sets encoded bitlen of 'x' to 'ebitlen' and then zeroes its effective words.