nn_add.c

/*
 *  Copyright (C) 2017 - This file is part of libecc project
 *
 *  Authors:
 *      Ryad BENADJILA <[email protected]>
 *      Arnaud EBALARD <[email protected]>
 *      Jean-Pierre FLORI <[email protected]>
 *
 *  Contributors:
 *      Nicolas VIVET <[email protected]>
 *      Karim KHALFALLAH <[email protected]>
 *
 *  This software is licensed under a dual BSD and GPL v2 license.
 *  See LICENSE file at the root folder of the project.
 */
#include <libecc/nn/nn_add.h>
#include <libecc/nn/nn.h>

/*
 * This module provides conditional addition and subtraction functions between
 * two nn:
 *
 *  o out = in1 +/- in2 if cnd is not zero.
 *  o out = in1 if cnd is zero.
 *
 * The time taken by the operation does not depend on cnd value, i.e. it is
 * constant time for that specific factor, nor on the values of in1 and in2.
 * It still depends on the maximal length of in1 and in2.
 *
 * Common addition and subtraction functions are derived from those conditional
 * versions.
 */

/*
 * Conditionally adds 'in2' to 'in1' according to "cnd", storing the result
 * in "out" and returning the carry in 'carry' parameter on success. This
 * is the lowest level function for conditional addition. The function
 * returns 0 on success, -1 on error.
 *
 * Note that unlike "usual" addition, the function is *in general* not
 * commutative, i.e. "_nn_cnd_add(cnd, out, in1, in2)"  is not equivalent
 * to "_nn_cnd_add(cnd, out, in2, in1)". It is commutative though if "cnd"
 * is not zero or 'in1' == 'in2'.
 *
 * Aliasing of inputs and output is possible. "out" is initialized if needed,
 * that is if not aliased to 'in1' or 'in2'. The length of "out" is set to
 * the maximal length of 'in1' and 'in2'. Note that both 'in1' and 'in2' will
 * be read to this maximal length. As our memory managment model assumes that
 * storage arrays only contains zeros past the "wlen" index, correct results
 * will be produced. The length of 'out' is not normalized on return.
 *
 * The runtime of this function should not depend on:
 *  o the value of "cnd",
 *  o the data stored in 'in1' and 'in2'.
 * It depends on:
 *  o the maximal length of 'in1' and 'in2'.
 *
 * This function is for internal use only.
 */
ATTRIBUTE_WARN_UNUSED_RET static int _nn_cnd_add(int cnd, nn_t out, nn_src_t in1, nn_src_t in2,
		       word_t *carry)
{
	word_t tmp, carry1, carry2, _carry = WORD(0);
	word_t mask = WORD_MASK_IFNOTZERO(cnd);
	u8 i, loop_wlen;
	int ret;

	MUST_HAVE((carry != NULL), ret, err);
	ret = nn_check_initialized(in1); EG(ret, err);
	ret = nn_check_initialized(in2); EG(ret, err);

	/* Handle aliasing */
	loop_wlen = LOCAL_MAX(in1->wlen, in2->wlen);
	if ((out != in1) && (out != in2)) {
		ret = nn_init(out, (u16)(loop_wlen * WORD_BYTES)); EG(ret, err);
	} else {
		ret = nn_set_wlen(out, loop_wlen); EG(ret, err);
	}

	/* Perform addition one word at a time, propagating the carry. */
	for (i = 0; i < loop_wlen; i++) {
		tmp = (word_t)(in1->val[i] + (in2->val[i] & mask));
		carry1 = (word_t)(tmp < in1->val[i]);
		out->val[i] = (word_t)(tmp + _carry);
		carry2 = (word_t)(out->val[i] < tmp);
		/* There is at most one carry going out. */
		_carry = (word_t)(carry1 | carry2);
	}

	(*carry) = _carry;

err:
	return ret;
}

/*
 * Conditionally adds 'in2' to 'in1' according to "cnd", storing the result
 * in "out", including the potential carry overflowing past the maximal
 * length of 'in1' and 'in2'. It is user responsibility to ensure that the
 * resulting nn will not be higher than what can be supported. This is
 * for instance guaranteed if both in1->wlen and in2->wlen are less than
 * NN_MAX_WORD_LEN. Otherwise the function will error out which could leak
 * information.
 *
 * Note that the length of the output depends the lengths of the inputs,
 * but also on their values.
 * It is the user responsibility to use this function carefully when
 * constant time of an algorithm using this function is seeked.
 * This choice was preferred above unconditionally increasing
 * the length of the output by one, to ease the management of length
 * explosion when multiple additions are performed.
 * For finer carry propagation and length control the internal "_nn_cnd_add"
 * function can be used.
 *
 * See "_nn_cnd_add" documentation above for further details.
 *
 * The function returns 0 on success, -1 on error.
 */
int nn_cnd_add(int cnd, nn_t out, nn_src_t in1, nn_src_t in2)
{
	word_t carry;
	int ret;

	ret = _nn_cnd_add(cnd, out, in1, in2, &carry); EG(ret, err);

	/* We cannot allow a non-zero carry if out->wlen is at its limit */
	MUST_HAVE(((out->wlen != NN_MAX_WORD_LEN) || (!carry)), ret, err);

	if (out->wlen != NN_MAX_WORD_LEN) {
		/*
		 * To maintain constant time, we perform carry addition in all
		 * cases. If carry is 0, no change is performed in practice,
		 * neither to 'out' value, nor to its length.
		 * Note that the length of the output can vary and make
		 * the time taken by further operations on it also vary.
		 */
		out->val[out->wlen] = carry;
		out->wlen = (u8)(out->wlen + carry);
	}

err:
	return ret;
}

/*
 * Unconditionally adds 'in2' to 'in1', storing the result in "out",
 * including the potential carry overflowing past the maximal length of
 * 'in1' and 'in2'. The function returns 0 on success, -1 on error.
 *
 * Note that the length of the output depends the lengths of the inputs,
 * but also on their values.
 * It is the user responsibility to use this function carefully when
 * constant time of an algorithm using this function is seeked.
 *
 * See "_nn_cnd_add" documentation for further details.
 *
 */
int nn_add(nn_t out, nn_src_t in1, nn_src_t in2)
{
	return nn_cnd_add(1, out, in1, in2);
}

/*
 * Compute out = in1 + w where 'in1' is an initialized nn and 'w' a word. It is
 * caller responsibility to ensure that the result will fit in a nn (This is
 * for instance guaranteed if 'in1' wlen is less than NN_MAX_WORD_LEN). The
 * function returns 0 on succes, -1 on error.
 *
 * The result is stored in 'out' parameter. 'out' is initialized if needed (i.e.
 * in case aliasing is not used) and is not normalized on return.
 *
 * Note that the length of the output depends the lengths of the inputs,
 * but also on their values.
 * It is the user responsibility to use this function carefully when
 * constant time of an algorithm using this function is seeked.
 *
 * This function is for internal use only.
 */
ATTRIBUTE_WARN_UNUSED_RET static int nn_add_word(nn_t out, nn_src_t in1, word_t w)
{
	word_t carry, tmp;
	u8 i, n_wlen;
	int ret;

	ret = nn_check_initialized(in1); EG(ret, err);

	/* Handle aliasing */
	n_wlen = in1->wlen;
	if (out != in1) {
		ret = nn_init(out, (u16)(n_wlen * WORD_BYTES)); EG(ret, err);
	} else {
		ret = nn_set_wlen(out, n_wlen); EG(ret, err);
	}

	/* No matter its value, propagate the carry. */
	carry = w;
	for (i = 0; i < n_wlen; i++) {
		tmp = (word_t)(in1->val[i] + carry);
		carry = (word_t)(tmp < in1->val[i]);
		out->val[i] = tmp;
	}

	MUST_HAVE(((out->wlen != NN_MAX_WORD_LEN) || (!carry)), ret, err);
	if (out->wlen != NN_MAX_WORD_LEN) {
		/*
		 * To maintain constant time, we perform carry addition in all
		 * cases. If carry is 0, no change is performed in practice,
		 * neither to 'out' value, nor to its length.
		 * Note that the length of the output can vary and make
		 * the time taken by further operations on it will vary.
		 */
		out->val[out->wlen] = carry;
		out->wlen = (u8)(out->wlen + carry);
	}

err:
	return ret;
}

/*
 * Compute out = in1 + 1. Aliasing is supported i.e. nn_inc(in1, in1) works as
 * expected and provides in1++. It is caller responsibility to ensure that the
 * result will fit in a nn (This is for instance guaranteed if 'in1' wlen is
 * less than NN_MAX_WORD_LEN). The function returns 0 on success, -1 on error.
 *
 * Note that the length of the output depends the lengths of the inputs,
 * but also on their values.
 * It is the user responsibility to use this function carefully when
 * constant time of an algorithm using this function is seeked.
 */
int nn_inc(nn_t out, nn_src_t in1)
{
	return nn_add_word(out, in1, WORD(1));
}

/*
 * Conditionally subtracts 'in2' from 'in1' according to "cnd",
 * storing the result in "out":
 *  o out = in1 - in2 if cnd is not zero.
 *  o out = in1 if cnd is zero.
 *
 * 'in1' and 'in2' must point to initialized nn, such that the value of 'in1'
 * is larger than 'in2'. Aliasing is supported, i.e. 'out' can point to the
 * same nn as 'in1' or 'in2'. If aliasing is not used, 'out' is initialized by
 * the function. The length of 'out' is set to the length of 'in1'
 * and is not normalized on return.
 *
 * The function returns 0 on success, -1 on error.
 */
int nn_cnd_sub(int cnd, nn_t out, nn_src_t in1, nn_src_t in2)
{
	word_t tmp, borrow1, borrow2, borrow = WORD(0);
	word_t mask = WORD_MASK_IFNOTZERO(cnd);
	u8 loop_wlen, i;
	int ret;

	ret = nn_check_initialized(in1); EG(ret, err);
	ret = nn_check_initialized(in2); EG(ret, err);

	/* Handle aliasing */
	loop_wlen = LOCAL_MAX(in1->wlen, in2->wlen);
	if ((out != in1) && (out != in2)) {
		ret = nn_init(out, (u16)(loop_wlen * WORD_BYTES)); EG(ret, err);
	} else {
		ret = nn_set_wlen(out, in1->wlen); EG(ret, err);
	}

	/* Perform subtraction one word at a time, propagating the borrow. */
	for (i = 0; i < loop_wlen; i++) {
		tmp = (word_t)(in1->val[i] - (in2->val[i] & mask));
		borrow1 = (word_t)(tmp > in1->val[i]);
		out->val[i] = (word_t)(tmp - borrow);
		borrow2 = (word_t)(out->val[i] > tmp);
		/* There is at most one borrow going out. */
		borrow = (word_t)(borrow1 | borrow2);
	}

	/* We only support the in1 >= in2 case */
	ret = (borrow != WORD(0)) ? -1 : 0;

err:
	return ret;
}

/* Same as the one above, but the subtraction is performed unconditionally. */
int nn_sub(nn_t out, nn_src_t in1, nn_src_t in2)
{
	return nn_cnd_sub(1, out, in1, in2);
}

/*
 * Compute out = in1 - 1 where in1 is a *positive* integer. Aliasing is
 * supported i.e. nn_dec(A, A) works as expected and provides A -= 1.
 * The function returns 0 on success, -1 on error.
 */
int nn_dec(nn_t out, nn_src_t in1)
{
	const word_t w = WORD(1);
	word_t tmp, borrow;
	u8 n_wlen, i;
	int ret;

	ret = nn_check_initialized(in1); EG(ret, err);
	n_wlen = in1->wlen;
	ret = nn_set_wlen(out, n_wlen); EG(ret, err);

	/* Perform subtraction w/ provided word and propagate the borrow */
	borrow = w;
	for (i = 0; i < n_wlen; i++) {
		tmp = (word_t)(in1->val[i] - borrow);
		borrow = (word_t)(tmp > in1->val[i]);
		out->val[i] = tmp;
	}

	ret = (borrow != WORD(0)) ? -1 : 0;

err:
	return ret;
}

/*
 * The following functions handle modular arithmetic. Our outputs sizes do not
 * need a "normalization" since everything will be bounded by the modular number
 * size.
 *
 * Warning: the following functions are only useful when the inputs are < p,
 * i.e. we suppose that the input are already reduced modulo p. These primitives
 * are mostly useful for the Fp layer. Even though they give results when
 * applied to inputs >= p, there is no guarantee that the result is indeed < p
 * or correct whatsoever.
 */

/*
 * Compute out = in1 + in2 mod p. The function returns 0 on success, -1 on
 * error.
 *
 * Aliasing not fully supported, for internal use only.
 */
static int _nn_mod_add(nn_t out, nn_src_t in1, nn_src_t in2, nn_src_t p)
{
	int ret, larger, cmp;

	ret = nn_check_initialized(in1); EG(ret, err);
	ret = nn_check_initialized(in2); EG(ret, err);
	ret = nn_check_initialized(p); EG(ret, err);
	MUST_HAVE((p->wlen < NN_MAX_WORD_LEN), ret, err); /* otherwise carry could overflow */
	SHOULD_HAVE((!nn_cmp(in1, p, &cmp)) && (cmp < 0), ret, err); /* a SHOULD_HAVE as documented above */
	SHOULD_HAVE((!nn_cmp(in2, p, &cmp)) && (cmp < 0), ret, err); /* a SHOULD_HAVE as documented above */

	ret = nn_add(out, in1, in2); EG(ret, err);
	/*
	 * If previous addition extends out->wlen, this may have an effect on
	 * computation time of functions below. For that reason, we always
	 * normalize out->wlen to p->wlen + 1. Its length is set to that of
	 * p after the computations.
	 *
	 * We could also use _nn_cnd_add to catch the carry and deal
	 * with p's of size NN_MAX_WORD_LEN.
	 * It is still painful because we have no constraint on the lengths
	 * of in1 and in2 so getting a carry out does not necessarily mean
	 * that the sum is larger than p...
	 */
	ret = nn_set_wlen(out, (u8)(p->wlen + 1)); EG(ret, err);
	ret = nn_cmp(out, p, &cmp); EG(ret, err);
	larger = (cmp >= 0);
	ret = nn_cnd_sub(larger, out, out, p); EG(ret, err);
	ret = nn_set_wlen(out, p->wlen);

err:
	return ret;
}

/*
 * Compute out = in1 + in2 mod p. The function returns 0 on success, -1 on
 * error.
 *
 * Aliasing is supported.
 */
int nn_mod_add(nn_t out, nn_src_t in1, nn_src_t in2, nn_src_t p)
{
	int ret;

	if(out == p){
		nn p_cpy;
		p_cpy.magic = WORD(0);

		ret = nn_copy(&p_cpy, p); EG(ret, err1);
		ret = _nn_mod_add(out, in1, in2, &p_cpy);

err1:
		nn_uninit(&p_cpy);
		EG(ret, err);
	}
	else{
		ret = _nn_mod_add(out, in1, in2, p);
	}

err:
	return ret;
}

/*
 * Compute out = in1 + 1 mod p. The function returns 0 on success, -1 on error.
 *
 * Aliasing not fully supported, for internal use only.
 */
static int _nn_mod_inc(nn_t out, nn_src_t in1, nn_src_t p)
{
	int larger, ret, cmp;

	ret = nn_check_initialized(in1); EG(ret, err);
	ret = nn_check_initialized(p); EG(ret, err);
	MUST_HAVE((p->wlen < NN_MAX_WORD_LEN), ret, err); /* otherwise carry could overflow */
	SHOULD_HAVE((!nn_cmp(in1, p, &cmp)) && (cmp < 0), ret, err); /* a SHOULD_HAVE as documented above */

	ret = nn_inc(out, in1); EG(ret, err);
	ret = nn_set_wlen(out, (u8)(p->wlen + 1)); EG(ret, err); /* see comment in nn_mod_add() */
	ret = nn_cmp(out, p, &cmp); EG(ret, err);
	larger = (cmp >= 0);
	ret = nn_cnd_sub(larger, out, out, p); EG(ret, err);
	ret = nn_set_wlen(out, p->wlen);

err:
	return ret;
}

/*
 * Compute out = in1 + 1 mod p. The function returns 0 on success, -1 on error.
 *
 * Aliasing supported.
 */
int nn_mod_inc(nn_t out, nn_src_t in1, nn_src_t p)
{
	int ret;

	if(out == p){
		nn p_cpy;
		p_cpy.magic = WORD(0);

		ret = nn_copy(&p_cpy, p); EG(ret, err1);
		ret = _nn_mod_inc(out, in1, &p_cpy);

err1:
		nn_uninit(&p_cpy);
		EG(ret, err);
	}
	else{
		ret = _nn_mod_inc(out, in1, p);
	}

err:
	return ret;

}

/*
 * Compute out = in1 - in2 mod p. The function returns 0 on success, -1 on
 * error.
 *
 * Aliasing not supported, for internal use only.
 */
static int _nn_mod_sub(nn_t out, nn_src_t in1, nn_src_t in2, nn_src_t p)
{
	int smaller, ret, cmp;
	nn_src_t in2_;
	nn in2_cpy;
	in2_cpy.magic = WORD(0);

	ret = nn_check_initialized(in1); EG(ret, err);
	ret = nn_check_initialized(in2); EG(ret, err);
	ret = nn_check_initialized(p); EG(ret, err);
	MUST_HAVE((p->wlen < NN_MAX_WORD_LEN), ret, err); /* otherwise carry could overflow */
	SHOULD_HAVE((!nn_cmp(in1, p, &cmp)) && (cmp < 0), ret, err); /* a SHOULD_HAVE as documented above */
	SHOULD_HAVE((!nn_cmp(in2, p, &cmp)) && (cmp < 0), ret, err); /* a SHOULD_HAVE as documented above */

	/* Handle the case where in2 and out are aliased */
	if (in2 == out) {
		ret = nn_copy(&in2_cpy, in2); EG(ret, err);
		in2_ = &in2_cpy;
	} else {
		ret = nn_init(&in2_cpy, 0); EG(ret, err);
		in2_ = in2;
	}

	/* The below trick is used to avoid handling of "negative" numbers. */
	ret = nn_cmp(in1, in2_, &cmp); EG(ret, err);
	smaller = (cmp < 0);
	ret = nn_cnd_add(smaller, out, in1, p); EG(ret, err);
	ret = nn_set_wlen(out, (u8)(p->wlen + 1)); EG(ret, err);/* See Comment in nn_mod_add() */
	ret = nn_sub(out, out, in2_); EG(ret, err);
	ret = nn_set_wlen(out, p->wlen);

err:
	nn_uninit(&in2_cpy);

	return ret;
}

/*
 * Compute out = in1 - in2 mod p. The function returns 0 on success, -1 on
 * error.
 *
 * Aliasing supported.
 */
int nn_mod_sub(nn_t out, nn_src_t in1, nn_src_t in2, nn_src_t p)
{
	int ret;

	if(out == p){
		nn p_cpy;
		p_cpy.magic = WORD(0);

		ret = nn_copy(&p_cpy, p); EG(ret, err1);
		ret = _nn_mod_sub(out, in1, in2, &p_cpy);

err1:
		nn_uninit(&p_cpy);
		EG(ret, err);
	}
	else{
		ret = _nn_mod_sub(out, in1, in2, p);
	}

err:
	return ret;
}

/*
 * Compute out = in1 - 1 mod p. The function returns 0 on success, -1 on error
 *
 * Aliasing not supported, for internal use only.
 */
static int _nn_mod_dec(nn_t out, nn_src_t in1, nn_src_t p)
{
	int ret, iszero, cmp;

	ret = nn_check_initialized(in1); EG(ret, err);
	ret = nn_check_initialized(p); EG(ret, err);
	MUST_HAVE((p->wlen < NN_MAX_WORD_LEN), ret, err); /* otherwise carry could overflow */
	FORCE_USED_VAR(cmp); /* nop to silence possible warning with macro below */
	SHOULD_HAVE((!nn_cmp(in1, p, &cmp)) && (cmp < 0), ret, err);  /* a SHOULD_HAVE; Documented above */

	/* The below trick is used to avoid handling of "negative" numbers. */
	ret = nn_iszero(in1, &iszero); EG(ret, err);
	ret = nn_cnd_add(iszero, out, in1, p); EG(ret, err);
	ret = nn_set_wlen(out, (u8)(p->wlen + 1)); EG(ret, err); /* See Comment in nn_mod_add() */
	ret = nn_dec(out, out); EG(ret, err);
	ret = nn_set_wlen(out, p->wlen);

err:
	return ret;
}

/*
 * Compute out = in1 - 1 mod p. The function returns 0 on success, -1 on error
 *
 * Aliasing supported.
 */
int nn_mod_dec(nn_t out, nn_src_t in1, nn_src_t p)
{
	int ret;

	if(out == p){
		nn p_cpy;
		p_cpy.magic = WORD(0);

		ret = nn_copy(&p_cpy, p); EG(ret, err1);
		ret = _nn_mod_dec(out, in1, &p_cpy);

err1:
		nn_uninit(&p_cpy);
		EG(ret, err);
	}
	else{
		ret = _nn_mod_dec(out, in1, p);
	}

err:
	return ret;
}

/*
 * Compute out = -in mod p. The function returns 0 on success, -1 on error.
 * Because we only support positive integers, we compute
 * out = p - in (except when value is 0).
 *
 * We suppose that in is already reduced modulo p.
 *
 * Aliasing is supported.
 *
 */
int nn_mod_neg(nn_t out, nn_src_t in, nn_src_t p)
{
	int ret, cmp, iszero;

	FORCE_USED_VAR(cmp);

	ret = nn_check_initialized(in); EG(ret, err);
	ret = nn_check_initialized(p); EG(ret, err);

	SHOULD_HAVE((!nn_cmp(in, p, &cmp)) && (cmp < 0), ret, err);  /* a SHOULD_HAVE; Documented above */

	ret = nn_iszero(in, &iszero); EG(ret, err);
	if (iszero) {
		ret = nn_init(out, 0); EG(ret, err);
		ret = nn_zero(out); EG(ret, err);
	} else {
		ret = nn_sub(out, p, in); EG(ret, err);
	}

err:
	return ret;
}