~sircmpwn/hare-dev

This thread contains a patchset. You're looking at the original emails, but you may wish to use the patch review UI. Review patch
3 3

[PATCH hare v2] add crypto::bigint

Details
Message ID
<20220906125606.48171-1-apreiml@strohwolke.at>
DKIM signature
pass
Download raw message
Patch: +1352 -0
Most of the BearSSL functions are ported, except notably moddiv. Which
will be sent later in a separate patch, once it's ready for use.

Signed-off-by: Armin Preiml <apreiml@strohwolke.at>
---
v2:
 * add asserts where appropriate
 * fixed a bug to properly count bits during encode, if dest is non-zero
 * minor doc fixes

 crypto/bigint/+test/arithm.ha   | 111 ++++++++
 crypto/bigint/+test/encoding.ha |  91 +++++++
 crypto/bigint/+test/monty.ha    |  51 ++++
 crypto/bigint/+test/utils.ha    |  41 +++
 crypto/bigint/README            |  30 +++
 crypto/bigint/arithm.ha         | 446 ++++++++++++++++++++++++++++++++
 crypto/bigint/encoding.ha       | 289 +++++++++++++++++++++
 crypto/bigint/monty.ha          | 150 +++++++++++
 crypto/bigint/types.ha          |  14 +
 crypto/bigint/util.ha           |  67 +++++
 scripts/gen-stdlib              |  18 ++
 stdlib.mk                       |  44 ++++
 12 files changed, 1352 insertions(+)
 create mode 100644 crypto/bigint/+test/arithm.ha
 create mode 100644 crypto/bigint/+test/encoding.ha
 create mode 100644 crypto/bigint/+test/monty.ha
 create mode 100644 crypto/bigint/+test/utils.ha
 create mode 100644 crypto/bigint/README
 create mode 100644 crypto/bigint/arithm.ha
 create mode 100644 crypto/bigint/encoding.ha
 create mode 100644 crypto/bigint/monty.ha
 create mode 100644 crypto/bigint/types.ha
 create mode 100644 crypto/bigint/util.ha

diff --git a/crypto/bigint/+test/arithm.ha b/crypto/bigint/+test/arithm.ha
new file mode 100644
index 00000000..29930acd
--- /dev/null
+++ b/crypto/bigint/+test/arithm.ha
@@ -0,0 +1,111 @@
use bytes;

@test fn add() void = {
	let result: [4]u8 = [0...];

	let bx = fromhex("002132a0");
	let by = fromhex("00ff3201");

	let carry = add(bx, by, 0);

	assert(carry == 0);

	decode(result, bx);
	assert(bytes::equal([0x00, 0x21, 0x32, 0xa0], result));

	let carry = add(bx, by, 1);

	assert(carry == 0);
	decode(result, bx);
	assert(bytes::equal([0x01, 0x20, 0x64, 0xa1], result));
};

@test fn muladd_small() void = {
	const mod = fromhex("0100");
	let x = fromhex("0100");

	muladd_small(x, 3, mod);
	assert(equalshex(x, "03"));

	free(mod);
	free(x);

	const mod = fromhex("1000000000");
	let x = fromhexmod("0000000001", mod);
	muladd_small(x, 27, mod);
	assert(equalshex(x, "8000001b"));

	free(mod);
	free(x);
};

@test fn mulacc() void = {
	let d = fromhex("0000000000000000");
	let a = fromhex("0010");
	let b = fromhex("0014");

	defer free(d);
	defer free(a);
	defer free(b);

	mulacc(d, a, b);
	assert(equalshex(d, "0140"));

	mulacc(d, a, b);
	assert(equalshex(d, "0280"));
};

@test fn rshift() void = {
	let x = fromhex("1020304050");
	rshift(x, 1);
	assert(equalshex(x, "0810182028"));
	free(x);

	let x = fromhex("00");
	rshift(x, 1);
	assert(equalshex(x, ""));
	free(x);
};

@test fn reduce() void = {
	let m = fromhex("87654321");

	let a = fromhex("1234");
	let x = fromhex("00000000");
	reduce(x, a, m);
	assert(equalshex(x, "1234"));
	free(a);
	free(x);

	let a = fromhex("0123456789abcdef");
	let x = fromhex("00000000");
	reduce(x, a, m);
	assert(equalshex(x, "14786ead"));
	free(a);
	free(x);

	free(m);
};

@test fn modpow() void = {
	let m = fromhex("87654321");
	let x = fromhexmod("00f03202", m);

	let e: [_]u8 = [0x00, 0x00, 0xc1, 0xf4];
	const m0i = ninv31(m[1]);

	let tmp: [10]word = [0...];
	modpow(x, e, m, m0i, tmp);

	assert(equalshex(x, "3de073fc"));
	free(x);

	let x = fromhexmod("00f03202", m);
	let tmp: [20]word = [0...];

	modpow(x, e, m, m0i, tmp);
	assert(equalshex(x, "3de073fc"));

	free(m);
	free(x);
};
diff --git a/crypto/bigint/+test/encoding.ha b/crypto/bigint/+test/encoding.ha
new file mode 100644
index 00000000..f2e50eb9
--- /dev/null
+++ b/crypto/bigint/+test/encoding.ha
@@ -0,0 +1,91 @@
use bytes;

@test fn encode() void = {
	const decoded: [12]u8 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];
	let result: [12]u8 = [0...];

	let buf: [5]word = [0...];

	encode(buf, decoded);
	decode(result, buf);

	assert(bytes::equal(result, decoded));
};

@test fn encodebigger() void = {
	const decoded: [25]u8 = [
		0x8c, 0x99, 0xc4, 0x51, 0x53, 0x75, 0x86, 0x20, 0x73, 0x02,
		0x2a, 0x08, 0xf6, 0x01, 0xcd, 0x8a, 0xc8, 0x39, 0xa8, 0xb3,
		0x95, 0xb4, 0x27, 0xa1, 0xbb,
	];
	let result: [25]u8 = [0...];

	let buf: []word = alloc([0...], wordsize(decoded));
	defer free(buf);

	encode(buf, decoded);
	decode(result, buf);

	assert(bytes::equal(result, decoded));
};


@test fn encmoddec() void = {
	const input: [4]u8 = [0, 0, 0, 10];

	let mod = fromhex("00190000");
	let resultbuf: []word = alloc([0...], wordsize(input));
	let result: [4]u8 = [0...];

	let ret = encodemod(resultbuf[..], input, mod);

	decode(result[..], resultbuf);
	assert(ret == 1);
	assert(bytes::equal(result, input));

	const input: [4]u8 = [0, 25, 0, 0];
	let ret = encodemod(resultbuf[..], input, mod);
	assert(ret == 0);
	assert(iszero(resultbuf) == 1);

	const input: [4]u8 = [0, 26, 0, 0];
	let ret = encodemod(resultbuf[..], input, mod);
	assert(ret == 0);
	assert(iszero(resultbuf) == 1);
};


@test fn encreddec() void = {
	const input: [4]u8 = [0, 0, 0, 0x0a];

	let mod = fromhex("190000");
	defer free(mod);
	let resultbuf: []word = alloc([0...], wordsize(input));
	let result: [4]u8 = [0...];

	encodereduce(resultbuf, input, mod);
	decode(result, resultbuf);
	assert(bytes::equal(result, input));

	const input: [4]u8 = [0, 0x19, 0, 0];
	let resultbuf: []word = alloc([0...], wordsize(input));
	encodereduce(resultbuf, input, mod);
	decode(result, resultbuf);
	assert(iszero(resultbuf) == 1);

	const input: [4]u8 = [0x24, 0x17, 0x01, 0x05];
	let resultbuf: []word = alloc([0...], wordsize(input));
	encodereduce(resultbuf, input, mod);
	decode(result, resultbuf);
	assert(bytes::equal(result, [0x00, 0x0e, 0x01, 0x05]));
};

@test fn word_countbits() void = {
	assert(word_countbits(0) == 0);
	assert(word_countbits(1) == 1);
	assert(word_countbits(2) == 2);
	assert(word_countbits(4) == 3);
	assert(word_countbits(7) == 3);
	assert(word_countbits(8) == 4);
	assert(word_countbits(1131) == 11);
};
diff --git a/crypto/bigint/+test/monty.ha b/crypto/bigint/+test/monty.ha
new file mode 100644
index 00000000..b62d23f6
--- /dev/null
+++ b/crypto/bigint/+test/monty.ha
@@ -0,0 +1,51 @@

@test fn montyencode() void = {
	let m = fromhex("0010000061");
	let x = fromhexmod("0000010064", m);

	defer free(x);
	defer free(m);

	const m0i = ninv31(m[1]);

	to_monty(x, m);
	from_monty(x, m, m0i);

	assert(equalshex(x, "010064"));
};

@test fn montymul() void = {
	let m = fromhex("10000061");
	let x = fromhexmod("00000123", m);
	let y = fromhexmod("000003cf", m);
	let d = fromhexmod("00000000", m);

	const m0i = ninv31(m[1]);

	to_monty(x, m);
	to_monty(y, m);
	montymul(d, x, y, m, m0i);
	from_monty(d, m, m0i);

	assert(equalshex(d, "04544d"));

	free(d);
	free(x);
	free(y);

	d = fromhexmod("00000000", m);
	x = fromhexmod("0f98b7cf", m);
	y = fromhexmod("04216b9c", m);

	to_monty(x, m);
	to_monty(y, m);
	montymul(d, x, y, m, m0i);
	from_monty(d, m, m0i);

	assert(equalshex(d, "0d031f49"));

	free(x);
	free(y);
	free(m);
	free(d);
};
diff --git a/crypto/bigint/+test/utils.ha b/crypto/bigint/+test/utils.ha
new file mode 100644
index 00000000..8ca321fb
--- /dev/null
+++ b/crypto/bigint/+test/utils.ha
@@ -0,0 +1,41 @@
use encoding::hex;

// The caller must free the result.
export fn fromhex(h: str) []word = {
	let n: []u8 = hex::decodestr(h)!;
	defer free(n);

	let i: []word = alloc([0...], wordsize(n));
	encode(i, n);
	return i;
};

// 'h' must be lower than 'm'
export fn fromhexmod(h: str, m: []word) []word = {
	let r = fromhex(h);
	r[0] = m[0];
	return r;
};

// The caller must free the result.
export fn tohex(x: []word) str = {
	let buf: []u8 = alloc([0...], (len(x) - 1) * size(word));
	defer free(buf);

	decode(buf, x);

	let i = 0z;
	for (i < len(buf); i += 1) {
		if (buf[i] != 0) {
			break;
		};
	};

	return hex::encodestr(buf[i..]);
};

export fn equalshex(x: []word, h: str) bool = {
	let result = tohex(x);
	defer free(result);
	return result == h;
};
diff --git a/crypto/bigint/README b/crypto/bigint/README
new file mode 100644
index 00000000..98fa76e8
--- /dev/null
+++ b/crypto/bigint/README
@@ -0,0 +1,30 @@
Bigint provides constant time operations on big integers. This module is
limited in scope therefore heed must be taken to the documentation of
individual functions to avoid misusage. Restrictions apply to the sizes of big
integers that work together and some functions require an unenven modulo.

A big integer is an array of [[word]] and must be encoded using [[encode]],
[[encodemod]] or [[encodereduce]]. See [[wordsize]] on how to calculate the
required size of the array. The big integer will also store its announced bit
length, the number of bits that are actually used to store its value, and the
effective word length, the number of words that are actually used to store the
value. The value can be decoded back to its byte format by [[decode]].

[[add]] and [[sub]] are used for addition and subtraction of big integers. They
work without a modulo. [[mulacc] can be used to multiply and add. [[rshift]]
shifts a big integer to the right. [[reduce]] will reduce an encoded integer
modulo another one.

Repeated modular multiplication can be done using montgomery multiplication.
See [[to_monty]] and [[from_monty]] on how to convert from and back to this
format and [[montymul]] for the actual multiplication operation.

Modular exponentiation is done with [[modpow]].

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.
diff --git a/crypto/bigint/arithm.ha b/crypto/bigint/arithm.ha
new file mode 100644
index 00000000..58c305c1
--- /dev/null
+++ b/crypto/bigint/arithm.ha
@@ -0,0 +1,446 @@
// The following code was initially ported from BearSSL.
//
// Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
// 
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
// 
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
use crypto::math::*;

// 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.
export fn add(a: []word, b: const []word, ctl: u32) u32 = {
	const l = ewordlen(a);
	assert(equ32(l, ewordlen(b)) == 1);

	let carry: u32 = 0;
	for (let i = 1z; i <= l; i += 1) {
		const n: u32 = a[i] + b[i] + carry;
		carry = n >> WORD_BITSIZE;
		a[i] = muxu32(ctl, n & WORD_BITMASK, a[i]): word;
	};
	return carry;
};

// 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.
export fn sub(a: []word, b: const []word, do: u32) u32 = {
	const l = ewordlen(a);
	assert(equ32(l, ewordlen(b)) == 1);

	let carry: u32 = 0;
	for (let i = 1z; i <= l; i += 1) {
		let n: u32 = a[i] - b[i] - carry;
		carry = n >> WORD_BITSIZE;
		a[i] = muxu32(do, n & WORD_BITMASK, a[i]): word;
	};
	return carry;
};

// Right-shift an integer 'x' by 'count'. The shift amount must be less than
// [[WORD_BITSIZE]].
export fn rshift(x: []word, count: word) void = {
	assert(ltu32(count, WORD_BITSIZE) == 1);

	const l = ewordlen(x);
	if (l == 0) {
		return;
	};

	let r = x[1] >> count;
	for (let i = 2z; i <= l; i += 1) {
		const w = x[i];
		x[i - 1] = (w << (WORD_BITSIZE - count) | r) & WORD_BITMASK;
		r = w >> count;
	};
	x[l] = r;
};

// Multiply 'x' by 2^WORD_BITSIZE and then add integer 'z', modulo 'm'. This
// function assumes that 'x' and 'm' have the same announced bit length, and the
// announced bit length of 'm' matches its true bit length.
// 
// 'x' and 'm' may not refer to the same array.
//
// This function runs in constant time for a given announced bit length of 'x'
// and 'm'.
fn muladd_small(x: []word, z: word, m: const []word) void = {
	assert(&x[0] != &m[0], "'x' and 'm' may not refer to the same array");

	let hi: u32 = 0;

	// We can test on the modulus bit length since we accept to leak that
	// length.
	const m_bitlen = m[0];
	if (m_bitlen == 0) {
		return;
	};

	if (m_bitlen <= WORD_BITSIZE) {
		hi = x[1] >> 1;
		const lo = (x[1] << WORD_BITSIZE) | z;
		x[1] = divu32(hi, lo, m[1]).1: word;
		return;
	};

	let mlen = ewordlen(m);
	let mblr = m_bitlen & WORD_BITSIZE: word;

	// Principle: we estimate the quotient (x*2^31+z)/m by
	// doing a 64/32 division with the high words.
	// 
	// Let:
	//   w = 2^31
	//   a = (w*a0 + a1) * w^N + a2
	//   b = b0 * w^N + b2
	// such that:
	//   0 <= a0 < w
	//   0 <= a1 < w
	//   0 <= a2 < w^N
	//   w/2 <= b0 < w
	//   0 <= b2 < w^N
	//   a < w*b
	// I.e. the two top words of a are a0:a1, the top word of b is
	// b0, we ensured that b0 is "full" (high bit set), and a is
	// such that the quotient q = a/b fits on one word (0 <= q < w).
	// 
	// If a = b*q + r (with 0 <= r < q), we can estimate q by
	// doing an Euclidean division on the top words:
	//   a0*w+a1 = b0*u + v  (with 0 <= v < b0)
	// Then the following holds:
	//   0 <= u <= w
	//   u-2 <= q <= u

	let a0: u32 = 0, a1: u32 = 0, b0: u32 = 0;
	hi = x[mlen];
	if (mblr == 0) {
		a0 = x[mlen];
		x[2..mlen+1] = x[1..mlen];
		x[1] = z;
		a1 = x[mlen];
		b0 = m[mlen];
	} else {
		a0 = ((x[mlen] << (WORD_BITSIZE: word - mblr))
			| (x[mlen - 1] >> mblr)) & WORD_BITMASK;
		x[2..mlen+1] = x[1..mlen];
		x[1] = z;
		a1 = ((x[mlen] << (WORD_BITSIZE: word - mblr))
			| (x[mlen - 1] >> mblr)) & WORD_BITMASK;
		b0 = ((m[mlen] << (WORD_BITSIZE: word - mblr))
			| (m[mlen - 1] >> mblr)) & WORD_BITMASK;
	};

	// We estimate a divisor q. If the quotient returned by br_div()
	// is g:
	// -- If a0 == b0 then g == 0; we want q = 0x7FFFFFFF.
	// -- Otherwise:
	//    -- if g == 0 then we set q = 0;
	//    -- otherwise, we set q = g - 1.
	// The properties described above then ensure that the true
	// quotient is q-1, q or q+1.
	// 
	// Take care that a0, a1 and b0 are 31-bit words, not 32-bit. We
	// must adjust the parameters to br_div() accordingly.
	// 
	const (g, _) = divu32(a0 >> 1, a1 | (a0 << 31), b0);
	const q = muxu32(equ32(a0, b0), WORD_BITMASK,
		muxu32(equ32(g, 0), 0, g - 1));

	// We subtract q*m from x (with the extra high word of value 'hi').
	// Since q may be off by 1 (in either direction), we may have to
	// add or subtract m afterwards.
	// 
	// The 'tb' flag will be true (1) at the end of the loop if the
	// result is greater than or equal to the modulus (not counting
	// 'hi' or the carry).
	let cc: u32 = 0;
	let tb: u32 = 1;
	for (let u = 1z; u <= mlen; u += 1) {
		const mw = m[u];
		const zl = mul31(mw, q) + cc;
		cc = (zl >> WORD_BITSIZE): word;
		const zw = zl: word & WORD_BITMASK;
		const xw = x[u];
		let nxw = xw - zw;
		cc += nxw >> WORD_BITSIZE;
		nxw &= WORD_BITMASK;
		x[u] = nxw;
		tb = muxu32(equ32(nxw, mw), tb, gtu32(nxw, mw));
	};

	// If we underestimated q, then either cc < hi (one extra bit
	// beyond the top array word), or cc == hi and tb is true (no
	// extra bit, but the result is not lower than the modulus). In
	// these cases we must subtract m once.
	// 
	// Otherwise, we may have overestimated, which will show as
	// cc > hi (thus a negative result). Correction is adding m once.
	const over = gtu32(cc, hi);
	const under = ~over & (tb | ltu32(cc, hi));
	add(x, m, over);
	sub(x, m, under);
};


// Multiply two 31-bit integers, with a 62-bit result. This default
// implementation assumes that the basic multiplication operator
// yields constant-time code.
fn mul31(x: u32, y: u32) u64 = x: u64 * y: u64;
fn mul31_lo(x: u32, y: u32) u32 = (x: u32 * y: u32) & 0x7FFFFFFF;

// Calculate "m0i" which is equal to -(1/m0) mod 2^WORD_BITSIZE, where m0 is the
// least significant value word of m: []word. 
fn ninv31(m0: u32) u32 = {
	let y: u32 = 2 - m0;
	y *= 2 - y * m0;
	y *= 2 - y * m0;
	y *= 2 - y * m0;
	y *= 2 - y * m0;
	return muxu32(m0 & 1, -y, 0) & 0x7FFFFFFF;
};

// Calculates "m0i" which is equal to -(1/'m0') mod 2^WORD_BITSIZE. 'm0' is the
// the first significant word of a big integer, which is the word at index 1.
export fn ninv(m0: word) word = ninv31(m0);


// 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'.
export fn mulacc(d: []word, a: const []word, b: const []word) void = {
	assert(&a[0] != &d[0] && &b[0] != &d[0]);

	const alen = ewordlen(a);
	const blen = ewordlen(b);

	// We want to add the two bit lengths, but these are encoded,
	// which requires some extra care.
	const dl: u32 = (a[0] & WORD_BITSIZE) + (b[0] & WORD_BITSIZE);
	const dh: u32 = (a[0] >> WORD_SHIFT) + (b[0] >> WORD_SHIFT);
	d[0] = (dh << WORD_SHIFT) + dl
		+ (~(dl - WORD_BITSIZE): u32 >> 31);

	for (let u = 0z; u < blen; u += 1) {
		// Carry always fits on 31 bits; we want to keep it in a
		// 32-bit register on 32-bit architectures (on a 64-bit
		// architecture, cast down from 64 to 32 bits means
		// clearing the high bits, which is not free; on a 32-bit
		// architecture, the same operation really means ignoring
		// the top register, which has negative or zero cost).
		const f: u32 = b[1 + u];
		let cc: u64 = 0; // TODO #if BR_64 u32

		for (let v = 0z; v < alen; v += 1) {

			let z: u64 = d[1 + u + v]: u64 + mul31(f, a[1 + v]) + cc;
			cc = z >> WORD_BITSIZE;
			d[1 + u + v] = z: word & WORD_BITMASK;
		};
		d[1 + u + alen] = cc: word;
	};
};

// 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'.
export fn reduce(x: []word, a: const []word, m: const []word) void = {
	assert(&x[0] != &a[0] && &x[0] != &m[0]);

	const m_bitlen = m[0];
	const mlen = ewordlen(m);

	x[0] = m_bitlen;
	if (m_bitlen == 0) {
		return;
	};

	// If the source is shorter, then simply copy all words from a[]
	// and zero out the upper words.
	const a_bitlen = a[0];
	const alen = ewordlen(a);
	if (a_bitlen < m_bitlen) {
		x[1..1 + alen] = a[1..1 + alen];
		for (let u = alen; u < mlen; u += 1) {
			x[u + 1] = 0;
		};
		return;
	};

	// The source length is at least equal to that of the modulus.
	// We must thus copy N-1 words, and input the remaining words
	// one by one.
	x[1..mlen] = a[2 + (alen - mlen).. 1 + mlen];
	x[mlen] = 0;
	for (let u = 1 + alen - mlen; u > 0; u -= 1) {
		muladd_small(x, a[u], m);
	};
};

// Copies 'src' to 'dest' if ctl is 1. The length of 'src' must match the length
// of 'dest'.
fn ccopyu32(ctl: u32, dest: []u32, src: const []u32) void = {
	for (let i = 0z; i < len(dest); i += 1) {
		const x = src[i];
		const y = dest[i];

		dest[i] = muxu32(ctl, x, y);
	};
};

// 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.
export fn modpow(
	x: []word,
	e: const []u8,
	m: const []word,
	m0i: u32,
	tmp: []word,
) u32 = {
	assert(m[1] & 1 == 1, "'m' must be odd");
	assert(equ32(x[0], m[0]) == 1);

	// Get modulus size.
	let mwlen = ewordlen(m) + 1;
	const tmplen = (mwlen & 1) + mwlen;
	let t1 = tmp[..tmplen];
	let t2 = tmp[tmplen..];

	const twlen = len(tmp);
	if (twlen < (mwlen << 1)) {
		return 0;
	};

	// Compute possible window size, with a maximum of 5 bits.
	// When the window has size 1 bit, we use a specific code
	// that requires only two temporaries. Otherwise, for a
	// window of k bits, we need 2^k+1 temporaries.
	let win_len: word = 5;
	for (win_len > 1; win_len -= 1) {
		if (((1u32 << win_len: u32) + 1) * mwlen <= twlen) {
			break;
		};
	};

	// Everything is done in Montgomery representation.
	to_monty(x, m);

	// Compute window contents. If the window has size one bit only,
	// then t2 is set to x; otherwise, t2[0] is left untouched, and
	// t2[k] is set to x^k (for k >= 1).
	if (win_len == 1) {
		t2[..mwlen] = x[..mwlen];
	} else {
		let base = t2[mwlen..];
		base[..mwlen] = x[..mwlen];
		for (let u = 2z; u < (1u << win_len: uint); u += 1) {
			montymul(base[mwlen..2 * mwlen],
				base[..mwlen], x, m, m0i);
			base = base[mwlen..];
		};
	};

	// We need to set x to 1, in Montgomery representation. This can
	// be done efficiently by setting the high word to 1, then doing
	// one word-sized shift.
	zero(x, m[0]);
	x[ewordlen(m)] = 1;
	muladd_small(x, 0, m);

	let elen = len(e);
	let e = e[..];

	// We process bits from most to least significant. At each
	// loop iteration, we have acc_len bits in acc.
	let acc: word = 0;
	let acc_len = 0i;
	for (acc_len > 0 || elen > 0) {
		// Get the next bits.
		let k = win_len;
		if (acc_len: u32 < win_len) {
			if (elen > 0) {
				acc = (acc << 8) | e[0];
				e = e[1..];
				elen -= 1;
				acc_len += 8;
			} else {
				k = acc_len: u32;
			};
		};

		let bits: u32 = (acc >> (acc_len: u32 - k: u32))
			& ((1u32 << k: u32) - 1u32);
		acc_len -= k: int;

		// We could get exactly k bits. Compute k squarings.
		for (let i = 0z; i < k: size; i += 1) {
			montymul(t1, x, x, m, m0i);
			// memcpy(x, t1, mlen);
			x[..mwlen] = t1[..mwlen];
		};

		// Window lookup: we want to set t2 to the window
		// lookup value, assuming the bits are non-zero. If
		// the window length is 1 bit only, then t2 is
		// already set; otherwise, we do a constant-time lookup.
		if (win_len > 1) {
			zero(t2, m[0]);
			let base = t2[mwlen..];
			for (let u = 1u32; u < (1 << k): size; u += 1) {
				let mask: u32 = -equ32(u, bits);
				for (let v = 1z; v < mwlen; v += 1) {
					t2[v] |= mask & base[v];
				};
				base = base[mwlen..];
			};
		};

		// Multiply with the looked-up value. We keep the
		// product only if the exponent bits are not all-zero.
		montymul(t1, x, t2, m, m0i);

		ccopyu32(nequ32(bits, 0), x[..mwlen], t1[..mwlen]);
	};

	// Convert back from Montgomery representation, and exit.
	from_monty(x, m, m0i);
	return 1;
};
diff --git a/crypto/bigint/encoding.ha b/crypto/bigint/encoding.ha
new file mode 100644
index 00000000..ea7fe736
--- /dev/null
+++ b/crypto/bigint/encoding.ha
@@ -0,0 +1,289 @@
// The following code was initially ported from BearSSL.
//
// Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
// 
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
// 
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
use crypto::math::*;

// Minimal required words to store x into an []word. To statically allocate
// resources, following expression may be used:
//
//     ((number_of_bits + WORD_BITSIZE - 1) / WORD_BITSIZE) + 1
export fn wordsize(x: []u8) size = {
	return (((len(x) * 8) + WORD_BITSIZE - 1) / WORD_BITSIZE) + 1;
};

// 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 [[wordsize]] for how to calculate the required size.
//
// This function runs in constant time for given 'src' length.
export fn encode(dest: []word, src: const []u8) void = {
	let acc: u32 = 0;
	let accbits: u32 = 0;
	let didx: size = 1;

	for (let i = len(src) - 1; i < len(src); i -= 1) {
		acc |= (src[i] << accbits);
		accbits += 8;

		if (accbits >= WORD_BITSIZE) {
			dest[didx] = (acc & WORD_BITMASK): word;
			accbits -= WORD_BITSIZE;
			acc = src[i] >> (8 - accbits);
			didx += 1;
		};
	};

	dest[didx] = acc: word;

	dest[0] = countbits(dest[1..didx + 1]): word;
};

// Get the announced bit length of 'n' in encoded form.
fn countbits(n: const []word) u32 = {
	let tw: u32 = 0;
	let twk: u32 = 0;

	for (let i = len(n) - 1; i < len(n); i -= 1) {
		const c = equ32(tw, 0);
		const w = n[i];
		tw = muxu32(c, w, tw);
		twk = muxu32(c, i: u32, twk);
	};

	return (twk << WORD_SHIFT) + word_countbits(tw);
};

// Counts the number of bits until including the highest bit set to 1.
fn word_countbits(x: u32) u32 = {
	let k: u32 = nequ32(x, 0);
	let c: u32 = 0;

	c = gtu32(x, 0xffff);
	x = muxu32(c, x >> 16, x);
	k += c << 4;

	c = gtu32(x, 0x00ff);
	x = muxu32(c, x >>  8, x);
	k += c << 3;

	c = gtu32(x, 0x000f);
	x = muxu32(c, x >>  4, x);
	k += c << 2;

	c = gtu32(x, 0x0003);
	x = muxu32(c, x >>  2, x);
	k += c << 1;

	k += gtu32(x, 0x0001);

	return k;
};

// Get the encoded bit length of a word.
fn ebitlen(x: const []word) u32 = {
	return x[0];
};

// 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).
fn ewordlen(x: const []word) u32 = {
	return (x[0] + WORD_BITSIZE) >> WORD_SHIFT;
};

// 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.
export fn decode(dest: []u8, src: const []word) void = {
	let acc: u64 = 0;
	let accbits: u64 = 0;
	let sidx: size = 1;
	for (let i = len(dest) - 1; i < len(dest); i -= 1) {
		if (accbits < 8) {
			if (sidx < len(src)) {
				acc |= ((src[sidx]: u64) << accbits: u64): u64;
				sidx += 1;
			};
			accbits += WORD_BITSIZE;
		};
		dest[i] = acc: u8;
		acc >>= 8;
		accbits -= 8;
	};
};

// 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_BITSIZE + 7) / 8
export fn decodelen(src: const []word) size = {
	return ((len(src) - 1) * WORD_BITSIZE + 7) / 8;
};

// 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.
export fn encodemod(dest: []word, src: const []u8, m: const []word) u32 = {
	// Two-pass algorithm: in the first pass, we determine whether the
	// value fits; in the second pass, we do the actual write.
	//
	// During the first pass, 'r' contains the comparison result so
	// far:
	//  0x00000000   value is equal to the modulus
	//  0x00000001   value is greater than the modulus
	//  0xFFFFFFFF   value is lower than the modulus
	//
	// Since we iterate starting with the least significant bytes (at
	// the end of src[]), each new comparison overrides the previous
	// except when the comparison yields 0 (equal).
	//
	// During the second pass, 'r' is either 0xFFFFFFFF (value fits)
	// or 0x00000000 (value does not fit).
	//
	// We must iterate over all bytes of the source, _and_ possibly
	// some extra virtual bytes (with value 0) so as to cover the
	// complete modulus as well. We also add 4 such extra bytes beyond
	// the modulus length because it then guarantees that no accumulated
	// partial word remains to be processed.

	let mlen = 0z, tlen = 0z;

	mlen = ewordlen(m);
	tlen = mlen << (WORD_SHIFT - 3); // mlen in bytes
	if (tlen < len(src)) {
		tlen = len(src);
	};
	tlen += 4;
	let r: u32 = 0;
	for (let pass = 0z; pass < 2; pass += 1) {
		let v: size = 1;
		let acc: u32 = 0, acc_len: u32 = 0;

		for (let u = 0z; u < tlen; u += 1) {
			// inner loop is similar to encode until the mlen check
			let b: u32 = 0;

			if (u < len(src)) {
				b = src[len(src) - 1 - u];
			};
			acc |= (b << acc_len);
			acc_len += 8;
			if (acc_len >= WORD_BITSIZE) {
				const xw: u32 = acc & WORD_BITMASK;
				acc_len -= WORD_BITSIZE;
				acc = b >> (8 - acc_len);
				if (v <= mlen) {
					if (pass == 1) {
						dest[v] = (r & xw): word;
					} else {
						let cc = cmpu32(xw, m[v]: u32): u32;
						r = muxu32(equ32(cc, 0), r, cc);
					};
				} else {
					if (pass == 0) {
						r = muxu32(equ32(xw, 0), r, 1);
					};
				};
				v += 1;
			};
		};

		// When we reach this point at the end of the first pass:
		// r is either 0, 1 or -1; we want to set r to 0 if it
		// is equal to 0 or 1, and leave it to -1 otherwise.
		// 
		// When we reach this point at the end of the second pass:
		// r is either 0 or -1; we want to leave that value
		// untouched. This is a subcase of the previous.
		r >>= 1;
		r |= (r << 1);
	};

	dest[0] = m[0];
	return r & 1;
};

// 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'.
export fn encodereduce(dest: []word, src: const []u8, m: const []word) void = {
	assert(&dest[0] != &m[0], "'dest' and 'm' must be distinct");

	// Get the encoded bit length.
	const m_ebitlen = m[0];

	// Special case for an invalid (null) modulus.
	if (m_ebitlen == 0) {
		dest[0] = 0;
		return;
	};

	zero(dest, m_ebitlen);

	// First decode directly as many bytes as possible. This requires
	// computing the actual bit length.
	let m_rbitlen = m_ebitlen >> WORD_SHIFT;
	m_rbitlen = (m_ebitlen & WORD_BITSIZE)
		+ (m_rbitlen << WORD_SHIFT) - m_rbitlen;
	const mblen: size = (m_rbitlen + 7) >> 3;
	let k: size = mblen - 1;
	if (k >= len(src)) {
		encode(dest, src);
		dest[0] = m_ebitlen;
		return;
	};
	encode(dest, src[..k]);
	dest[0] = m_ebitlen;

	// Input remaining bytes, using 31-bit words.
	let acc: word = 0;
	let acc_len: word = 0;
	for (k < len(src)) {
		const v = src[k];
		k += 1;
		if (acc_len >= 23) {
			acc_len -= 23;
			acc <<= (8 - acc_len);
			acc |= v >> acc_len;
			muladd_small(dest, acc, m);
			acc = v & (0xFF >> (8 - acc_len));
		} else {
			acc = (acc << 8) | v;
			acc_len += 8;
		};
	};

	// We may have some bits accumulated. We then perform a shift to
	// be able to inject these bits as a full 31-bit word.
	if (acc_len != 0) {
		acc = (acc | (dest[1] << acc_len)) & WORD_BITMASK;
		rshift(dest, WORD_BITSIZE - acc_len);
		muladd_small(dest, acc, m);
	};
};
diff --git a/crypto/bigint/monty.ha b/crypto/bigint/monty.ha
new file mode 100644
index 00000000..14dc0481
--- /dev/null
+++ b/crypto/bigint/monty.ha
@@ -0,0 +1,150 @@
// The following code was initially ported from BearSSL.
//
// Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
// 
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
// 
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
use crypto::math::*;

// Convert a modular integer to Montgomery representation. The integer 'x' must
// be lower than 'm', but with the same announced bit length.
export fn to_monty(x: []word, m: const []word) void = {
	assert(equ32(x[0], m[0]) == 1);
	for (let k: u32 = ewordlen(m); k > 0; k -= 1) {
		muladd_small(x, 0, m);
	};
};

// 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.
export fn from_monty(x: []word, m: const []word, m0i: word) void = {
	assert(equ32(x[0], m[0]) == 1);
	const mlen = ewordlen(m);
	for (let u = 0z; u < mlen; u += 1) {
		const f: u32 = mul31_lo(x[1], m0i);
		let cc: u64 = 0;
		for (let v = 0z; v < mlen; v += 1) {
			const z: u64 = x[v + 1]: u64 + mul31(f, m[v + 1]) + cc;
			cc = z >> 31;
			if (v != 0) {
				x[v] = z: word & WORD_BITMASK;
			};
		};
		x[mlen] = cc: u32;
	};

	// We may have to do an extra subtraction, but only if the
	// value in x[] is indeed greater than or equal to that of m[],
	// which is why we must do two calls (first call computes the
	// carry, second call performs the subtraction only if the carry
	// is 0).
	sub(x, m, notu32(sub(x, m, 0)));
};

// 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.
export fn montymul(
	d: []word,
	x: const []word,
	y: const []word,
	m: const []word,
	m0i: u32
) void = {
	// Each outer loop iteration computes:
	//   d <- (d + xu*y + f*m) / 2^31
	// We have xu <= 2^31-1 and f <= 2^31-1.
	// Thus, if d <= 2*m-1 on input, then:
	//   2*m-1 + 2*(2^31-1)*m <= (2^32)*m-1
	// and the new d value is less than 2*m.
	//
	// We represent d over 31-bit words, with an extra word 'dh'
	// which can thus be only 0 or 1.
	let v: size = 0;

	const mlen = ewordlen(m);
	const len4 = mlen & ~3: size;
	zero(d, m[0]);
	let dh: u32 = 0;
	for (let u = 0z; u < mlen; u += 1) {
		// The carry for each operation fits on 32 bits:
		//   d[v+1] <= 2^31-1
		//   xu*y[v+1] <= (2^31-1)*(2^31-1)
		//   f*m[v+1] <= (2^31-1)*(2^31-1)
		//   r <= 2^32-1
		//   (2^31-1) + 2*(2^31-1)*(2^31-1) + (2^32-1) = 2^63 - 2^31
		// After division by 2^31, the new r is then at most 2^32-1
		//
		// Using a 32-bit carry has performance benefits on 32-bit
		// systems; however, on 64-bit architectures, we prefer to
		// keep the carry (r) in a 64-bit register, thus avoiding some
		// "clear high bits" operations.

		const xu: u32 = x[u + 1];
		const f: u32 = mul31_lo((d[1] + mul31_lo(x[u + 1], y[1])), m0i);

		let r: u64 = 0; // TODO if !BR_64 u32
		v = 0;
		for (v < len4; v += 4) {
			let z: u64 = d[v + 1]: u64 + mul31(xu, y[v + 1])
				+ mul31(f, m[v + 1]) + r;
			r = z >> 31;
			d[v + 0] = z: u32 & 0x7FFFFFFF;
			z = d[v + 2]: u64 + mul31(xu, y[v + 2])
				+ mul31(f, m[v + 2]) + r;
			r = z >> 31;
			d[v + 1] = z: u32 & 0x7FFFFFFF;
			z = d[v + 3]: u64 + mul31(xu, y[v + 3])
				+ mul31(f, m[v + 3]) + r;
			r = z >> 31;
			d[v + 2] = z: u32 & 0x7FFFFFFF;
			z = d[v + 4]: u64 + mul31(xu, y[v + 4])
				+ mul31(f, m[v + 4]) + r;
			r = z >> 31;
			d[v + 3] = z: u32 & 0x7FFFFFFF;
		};
		for (v < mlen; v += 1) {
			const z: u64 = d[v + 1]: u64 + mul31(xu, y[v + 1])
				+ mul31(f, m[v + 1]) + r;
			r = z >> 31;
			d[v] = z: u32 & 0x7FFFFFFF;
		};

		// Since the new dh can only be 0 or 1, the addition of
		// the old dh with the carry MUST fit on 32 bits, and
		// thus can be done into dh itself.
		dh += r: u32;
		d[mlen] = dh & 0x7FFFFFFF;
		dh >>= 31;
	};

	// We must write back the bit length because it was overwritten in
	// the loop (not overwriting it would require a test in the loop,
	// which would yield bigger and slower code).
	d[0] = m[0];

	// d[] may still be greater than m[] at that point; notably, the
	// 'dh' word may be non-zero.
	sub(d, m, nequ32(dh, 0) | notu32(sub(d, m, 0)));
};
diff --git a/crypto/bigint/types.ha b/crypto/bigint/types.ha
new file mode 100644
index 00000000..6666662c
--- /dev/null
+++ b/crypto/bigint/types.ha
@@ -0,0 +1,14 @@
// 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.
export type word = u32;

// Number of bits that are used for storing the value in a word.
export def WORD_BITSIZE: u32 = 31;

// Bitmask for bits that are used for storing the value in a word.
export def WORD_BITMASK: word = 0x7fffffff;

// full_bitlen(word) == 1 << WORD_SHIFT
def WORD_SHIFT: u32 = 5;
diff --git a/crypto/bigint/util.ha b/crypto/bigint/util.ha
new file mode 100644
index 00000000..023e2622
--- /dev/null
+++ b/crypto/bigint/util.ha
@@ -0,0 +1,67 @@
// The following code was initially ported from BearSSL.
//
// Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
// 
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
// 
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
use bytes;

// Sets encoded bitlen of 'x' to 'ebitlen' and then zeroes its effective words.
export fn zero(x: []word, ebitlen: word) void = {
	x[0] = ebitlen;
	const ewordlen = ewordlen(x);
	bytes::zero((x: *[*]u8)[size(word)..(1 + ewordlen) * size(word)]);
};

@test fn zero() void = {
	let w: [4]word = [0xffffffff...];

	// set effective word len to 2 words.
	const elen = countbits(w[1..3]);
	w[0] = elen;

	zero(w[..3], elen);

	// check if zero does not overwrite more or less than elen
	assert(w[0] == elen);
	assert(w[3] == 0xffffffff);
};

// Checks whether the effective words of 'x' are zero. Returns 1 if so, or 0
// otherwise.
fn iszero(x: []word) u32 = {
	let z: u32 = 0;

	for (let i = ewordlen(x); i > 0; i -= 1) {
		z |= x[i];
	};
	return ~(z | -(z: i32): u32) >> 31;
};

@test fn iszero() void = {
	let x = fromhex("210032a0");
	let y = fromhex("00000000");

	assert(iszero(x) == 0);
	assert(iszero(y) == 1);

	free(x);
	free(y);
};


diff --git a/scripts/gen-stdlib b/scripts/gen-stdlib
index f8bbc2dd..14e366b3 100755
--- a/scripts/gen-stdlib
+++ b/scripts/gen-stdlib
@@ -320,6 +320,23 @@ crypto_blowfish() {
	gen_ssa crypto::blowfish bytes crypto::cipher endian
}

gensrcs_crypto_bigint() {
		gen_srcs crypto::bigint arithm.ha encoding.ha monty.ha types.ha \
            util.ha $*
}

crypto_bigint() {
	if [ $testing -eq 0 ]
	then
		gensrcs_crypto_bigint
        gen_ssa crypto::bigint bytes crypto::math
	else
		gensrcs_crypto_bigint +test/arithm.ha +test/encoding.ha \
            +test/monty.ha +test/utils.ha
        gen_ssa crypto::bigint bytes crypto::math encoding::hex
	fi
}

crypto_chacha() {
	if [ $testing -eq 0 ]
	then
@@ -1436,6 +1453,7 @@ crypto::argon2
crypto::bcrypt
crypto::blake2b
crypto::blowfish
crypto::bigint
crypto::chacha
crypto::cipher
crypto::hkdf
diff --git a/stdlib.mk b/stdlib.mk
index 9dd5dee2..1f3b0125 100644
--- a/stdlib.mk
+++ b/stdlib.mk
@@ -190,6 +190,12 @@ stdlib_deps_any += $(stdlib_crypto_blowfish_any)
stdlib_crypto_blowfish_linux = $(stdlib_crypto_blowfish_any)
stdlib_crypto_blowfish_freebsd = $(stdlib_crypto_blowfish_any)

# gen_lib crypto::bigint (any)
stdlib_crypto_bigint_any = $(HARECACHE)/crypto/bigint/crypto_bigint-any.o
stdlib_deps_any += $(stdlib_crypto_bigint_any)
stdlib_crypto_bigint_linux = $(stdlib_crypto_bigint_any)
stdlib_crypto_bigint_freebsd = $(stdlib_crypto_bigint_any)

# gen_lib crypto::chacha (any)
stdlib_crypto_chacha_any = $(HARECACHE)/crypto/chacha/crypto_chacha-any.o
stdlib_deps_any += $(stdlib_crypto_chacha_any)
@@ -854,6 +860,20 @@ $(HARECACHE)/crypto/blowfish/crypto_blowfish-any.ssa: $(stdlib_crypto_blowfish_a
	@HARECACHE=$(HARECACHE) $(HAREC) $(HAREFLAGS) -o $@ -Ncrypto::blowfish \
		-t$(HARECACHE)/crypto/blowfish/crypto_blowfish.td $(stdlib_crypto_blowfish_any_srcs)

# crypto::bigint (+any)
stdlib_crypto_bigint_any_srcs = \
	$(STDLIB)/crypto/bigint/arithm.ha \
	$(STDLIB)/crypto/bigint/encoding.ha \
	$(STDLIB)/crypto/bigint/monty.ha \
	$(STDLIB)/crypto/bigint/types.ha \
	$(STDLIB)/crypto/bigint/util.ha

$(HARECACHE)/crypto/bigint/crypto_bigint-any.ssa: $(stdlib_crypto_bigint_any_srcs) $(stdlib_rt) $(stdlib_bytes_$(PLATFORM)) $(stdlib_crypto_math_$(PLATFORM))
	@printf 'HAREC \t$@\n'
	@mkdir -p $(HARECACHE)/crypto/bigint
	@HARECACHE=$(HARECACHE) $(HAREC) $(HAREFLAGS) -o $@ -Ncrypto::bigint \
		-t$(HARECACHE)/crypto/bigint/crypto_bigint.td $(stdlib_crypto_bigint_any_srcs)

# crypto::chacha (+any)
stdlib_crypto_chacha_any_srcs = \
	$(STDLIB)/crypto/chacha/chacha20.ha
@@ -2366,6 +2386,12 @@ testlib_deps_any += $(testlib_crypto_blowfish_any)
testlib_crypto_blowfish_linux = $(testlib_crypto_blowfish_any)
testlib_crypto_blowfish_freebsd = $(testlib_crypto_blowfish_any)

# gen_lib crypto::bigint (any)
testlib_crypto_bigint_any = $(TESTCACHE)/crypto/bigint/crypto_bigint-any.o
testlib_deps_any += $(testlib_crypto_bigint_any)
testlib_crypto_bigint_linux = $(testlib_crypto_bigint_any)
testlib_crypto_bigint_freebsd = $(testlib_crypto_bigint_any)

# gen_lib crypto::chacha (any)
testlib_crypto_chacha_any = $(TESTCACHE)/crypto/chacha/crypto_chacha-any.o
testlib_deps_any += $(testlib_crypto_chacha_any)
@@ -3041,6 +3067,24 @@ $(TESTCACHE)/crypto/blowfish/crypto_blowfish-any.ssa: $(testlib_crypto_blowfish_
	@HARECACHE=$(TESTCACHE) $(HAREC) $(TESTHAREFLAGS) -o $@ -Ncrypto::blowfish \
		-t$(TESTCACHE)/crypto/blowfish/crypto_blowfish.td $(testlib_crypto_blowfish_any_srcs)

# crypto::bigint (+any)
testlib_crypto_bigint_any_srcs = \
	$(STDLIB)/crypto/bigint/arithm.ha \
	$(STDLIB)/crypto/bigint/encoding.ha \
	$(STDLIB)/crypto/bigint/monty.ha \
	$(STDLIB)/crypto/bigint/types.ha \
	$(STDLIB)/crypto/bigint/util.ha \
	$(STDLIB)/crypto/bigint/+test/arithm.ha \
	$(STDLIB)/crypto/bigint/+test/encoding.ha \
	$(STDLIB)/crypto/bigint/+test/monty.ha \
	$(STDLIB)/crypto/bigint/+test/utils.ha

$(TESTCACHE)/crypto/bigint/crypto_bigint-any.ssa: $(testlib_crypto_bigint_any_srcs) $(testlib_rt) $(testlib_bytes_$(PLATFORM)) $(testlib_crypto_math_$(PLATFORM)) $(testlib_encoding_hex_$(PLATFORM))
	@printf 'HAREC \t$@\n'
	@mkdir -p $(TESTCACHE)/crypto/bigint
	@HARECACHE=$(TESTCACHE) $(HAREC) $(TESTHAREFLAGS) -o $@ -Ncrypto::bigint \
		-t$(TESTCACHE)/crypto/bigint/crypto_bigint.td $(testlib_crypto_bigint_any_srcs)

# crypto::chacha (+any)
testlib_crypto_chacha_any_srcs = \
	$(STDLIB)/crypto/chacha/chacha20.ha \
-- 
2.37.3

[hare/patches] build success

builds.sr.ht <builds@sr.ht>
Details
Message ID
<CMPC3WSLV85G.20BPNHPZRQQAL@cirno>
In-Reply-To
<20220906125606.48171-1-apreiml@strohwolke.at> (view parent)
DKIM signature
missing
Download raw message
hare/patches: SUCCESS in 1m51s

[add crypto::bigint][0] v2 from [Armin Preiml][1]

[0]: https://lists.sr.ht/~sircmpwn/hare-dev/patches/35153
[1]: apreiml@strohwolke.at

✓ #839527 SUCCESS hare/patches/freebsd.yml https://builds.sr.ht/~sircmpwn/job/839527
✓ #839526 SUCCESS hare/patches/alpine.yml  https://builds.sr.ht/~sircmpwn/job/839526
Details
Message ID
<621c72aa-ac2d-bea2-2c2a-15a20524170d@strohwolke.at>
In-Reply-To
<20220906125606.48171-1-apreiml@strohwolke.at> (view parent)
DKIM signature
pass
Download raw message
I'm still not happy about the following function names. Ideas and 
suggestions are very welcome:

wordsize: The function returns the length of the []word array required 
to store a bigint. Maybe encodelen, similar to decodelen, if decodelen 
is a agreeable name.

from_monty and to_monty: Maybe just leave out the underscore.
Details
Message ID
<CN2U3HQAAG7Y.SB9VD1P0GVH7@taiga>
In-Reply-To
<20220906125606.48171-1-apreiml@strohwolke.at> (view parent)
DKIM signature
pass
Download raw message
Thanks!

To git@git.sr.ht:~sircmpwn/hare
   10cf8c9d..82213191  master -> master
Reply to thread Export thread (mbox)