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;
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
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;
Bitmask for bits that are used for storing the value in a word.
def WORD_BITSZ
def WORD_BITSZ: u32;
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 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 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.