commit 82213191adc25137c704df4786a71bce40b6079f
parent f173be36ad736bd342e47e9c7e4767afb394220a
Author: Armin Preiml <apreiml@strohwolke.at>
Date: Tue, 6 Sep 2022 14:56:06 +0200
add crypto::bigint
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>
Signed-off-by: Drew DeVault <sir@cmpwn.com>
Diffstat:
12 files changed, 1345 insertions(+), 0 deletions(-)
diff --git a/crypto/bigint/+test/arithm.ha 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
@@ -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
@@ -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
@@ -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
@@ -0,0 +1,23 @@
+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 [[wordsize]] 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
+[[to_monty]] and [[from_monty]] 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.
diff --git a/crypto/bigint/arithm.ha 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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 \
