ecfsdsa.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/lib_ecc_config.h>
#ifdef WITH_SIG_ECFSDSA

#include <libecc/nn/nn_rand.h>
#include <libecc/nn/nn_mul_public.h>
#include <libecc/nn/nn_logical.h>

#include <libecc/sig/sig_algs_internal.h>
#include <libecc/sig/sig_algs.h>
#include <libecc/sig/ec_key.h>
#ifdef VERBOSE_INNER_VALUES
#define EC_SIG_ALG "ECFSDSA"
#endif
#include <libecc/utils/dbg_sig.h>

int ecfsdsa_init_pub_key(ec_pub_key *out_pub, const ec_priv_key *in_priv)
{
	int ret, cmp;
	prj_pt_src_t G;
	nn_src_t q;

	MUST_HAVE((out_pub != NULL), ret, err);

	/* Zero init public key to be generated */
	ret = local_memset(out_pub, 0, sizeof(ec_pub_key)); EG(ret, err);

	ret = priv_key_check_initialized_and_type(in_priv, ECFSDSA); EG(ret, err);
	q = &(in_priv->params->ec_gen_order);

	/* Sanity check on key compliance */
	MUST_HAVE(!nn_cmp(&(in_priv->x), q, &cmp) && (cmp < 0), ret, err);

	/* Y = xG */
	G = &(in_priv->params->ec_gen);
	/* Use blinding when computing point scalar multiplication */
	ret = prj_pt_mul_blind(&(out_pub->y), &(in_priv->x), G); EG(ret, err);

	out_pub->key_type = ECFSDSA;
	out_pub->params = in_priv->params;
	out_pub->magic = PUB_KEY_MAGIC;

err:
	return ret;
}

int ecfsdsa_siglen(u16 p_bit_len, u16 q_bit_len, u8 hsize, u8 blocksize, u8 *siglen)
{
	int ret;

	MUST_HAVE((siglen != NULL), ret, err);
	MUST_HAVE((p_bit_len <= CURVES_MAX_P_BIT_LEN) &&
		  (q_bit_len <= CURVES_MAX_Q_BIT_LEN) &&
		  (hsize <= MAX_DIGEST_SIZE) && (blocksize <= MAX_BLOCK_SIZE), ret, err);
	(*siglen) = (u8)ECFSDSA_SIGLEN(p_bit_len, q_bit_len);
	ret = 0;

err:
	return ret;
}

/*
 * Generic *internal* ECFSDSA signature functions (init, update and finalize).
 * Their purpose is to allow passing a specific hash function (along with
 * their output size) and the random ephemeral key k, so that compliance
 * tests against test vectors can be made without ugly hack in the code
 * itself.
 *
 * Global EC-FSDSA signature process is as follows (I,U,F provides
 * information in which function(s) (init(), update() or finalize())
 * a specific step is performed):
 *
 *| IUF - ECFSDSA signature
 *|
 *| I	1. Get a random value k in ]0,q[
 *| I	2. Compute W = (W_x,W_y) = kG
 *| I	3. Compute r = FE2OS(W_x)||FE2OS(W_y)
 *| I	4. If r is an all zero string, restart the process at step 1.
 *| IUF 5. Compute h = H(r||m)
 *|   F 6. Compute e = OS2I(h) mod q
 *|   F 7. Compute s = (k + ex) mod q
 *|   F 8. If s is 0, restart the process at step 1 (see c. below)
 *|   F 9. Return (r,s)
 *
 * Implementation notes:
 *
 * a) sig is built as the concatenation of r and s. r is encoded on
 *    2*ceil(bitlen(p)) bytes and s on ceil(bitlen(q)) bytes.
 * b) in EC-FSDSA, the public part of the key is not needed per se during
 *    the signature but - as it is needed in other signature algs implemented
 *    in the library - the whole key pair is passed instead of just the
 *    private key.
 * c) Implementation of EC-FSDSA in an init()/update()/finalize() logic
 *    cannot be made deterministic, in the sense that if s is 0 at step
 *    8 above, there is no way to restart the whole signature process
 *    w/o rehashing m. So, even if the event is extremely unlikely,
 *    signature process may fail to provide a signature of the data
 *    during finalize() call.
 */

#define ECFSDSA_SIGN_MAGIC ((word_t)(0x1ed9635924b48ddaULL))
#define ECFSDSA_SIGN_CHECK_INITIALIZED(A, ret, err) \
	MUST_HAVE((((void *)(A)) != NULL) && \
		  ((A)->magic == ECFSDSA_SIGN_MAGIC), ret, err)

int _ecfsdsa_sign_init(struct ec_sign_context *ctx)
{
	prj_pt_src_t G;
	nn_src_t q;
	nn *k;
	u8 *r;
	prj_pt kG;
	const ec_priv_key *priv_key;
	bitcnt_t p_bit_len;
	u8 i, p_len, r_len;
	int ret;
	kG.magic = WORD(0);

	/* First, verify context has been initialized */
	ret = sig_sign_check_initialized(ctx); EG(ret, err);

	/* Zero init points */
	ret = local_memset(&kG, 0, sizeof(prj_pt)); EG(ret, err);

	/* Additional sanity checks on input params from context */
	ret = key_pair_check_initialized_and_type(ctx->key_pair, ECFSDSA); EG(ret, err);
	MUST_HAVE((ctx->h != NULL) && (ctx->h->digest_size <= MAX_DIGEST_SIZE) &&
		  (ctx->h->block_size <= MAX_BLOCK_SIZE), ret, err);

	/* Make things more readable */
	priv_key = &(ctx->key_pair->priv_key);
	G = &(priv_key->params->ec_gen);
	q = &(priv_key->params->ec_gen_order);
	r = ctx->sign_data.ecfsdsa.r;
	k = &(ctx->sign_data.ecfsdsa.k);
	p_bit_len = priv_key->params->ec_fp.p_bitlen;
	MUST_HAVE(((u32)BYTECEIL(p_bit_len) <= NN_MAX_BYTE_LEN), ret, err);
	p_len = (u8)BYTECEIL(p_bit_len);
	r_len = (u8)ECFSDSA_R_LEN(p_bit_len);

	dbg_nn_print("p", &(priv_key->params->ec_fp.p));
	dbg_nn_print("q", q);
	dbg_priv_key_print("x", priv_key);
	dbg_ec_point_print("G", G);
	dbg_pub_key_print("Y", &(ctx->key_pair->pub_key));

 restart:

	/*  1. Get a random value k in ]0,q[ */
#ifdef NO_KNOWN_VECTORS
	/* NOTE: when we do not need self tests for known vectors,
	 * we can be strict about random function handler!
	 * This allows us to avoid the corruption of such a pointer.
	 */
	/* Sanity check on the handler before calling it */
	MUST_HAVE((ctx->rand == nn_get_random_mod), ret, err);
#endif
	MUST_HAVE((ctx->rand != NULL), ret, err);
	ret = ctx->rand(k, q); EG(ret, err);

	/*  2. Compute W = (W_x,W_y) = kG */
#ifdef USE_SIG_BLINDING
	/* We use blinding for the scalar multiplication */
	ret = prj_pt_mul_blind(&kG, k, G); EG(ret, err);
#else
	ret = prj_pt_mul(&kG, k, G); EG(ret, err);
#endif
	ret = prj_pt_unique(&kG, &kG); EG(ret, err);

	dbg_nn_print("Wx", &(kG.X.fp_val));
	dbg_nn_print("Wy", &(kG.Y.fp_val));

	/*  3. Compute r = FE2OS(W_x)||FE2OS(W_y) */
	ret = fp_export_to_buf(r, p_len, &(kG.X)); EG(ret, err);
	ret = fp_export_to_buf(r + p_len, p_len, &(kG.Y)); EG(ret, err);
	dbg_buf_print("r: ", r, r_len);

	/*  4. If r is an all zero string, restart the process at step 1. */
	ret = 0;
	for (i = 0; i < r_len; i++) {
		ret |= r[i];
	}
	if (ret == 0) {
		goto restart;
	}

	/*  5. Compute h = H(r||m).
	 *
	 * Note that we only start the hash work here by initializing the hash
	 * context and processing r. Message m will be handled during following
	 * update() calls.
	 */
	/* Since we call a callback, sanity check our mapping */
	ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
	ret = ctx->h->hfunc_init(&(ctx->sign_data.ecfsdsa.h_ctx)); EG(ret, err);
	/* Since we call a callback, sanity check our mapping */
	ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
	ret = ctx->h->hfunc_update(&(ctx->sign_data.ecfsdsa.h_ctx), r, r_len); EG(ret, err);

	ctx->sign_data.ecfsdsa.magic = ECFSDSA_SIGN_MAGIC;

 err:
	prj_pt_uninit(&kG);

	PTR_NULLIFY(G);
	PTR_NULLIFY(q);
	PTR_NULLIFY(k);
	PTR_NULLIFY(r);
	PTR_NULLIFY(priv_key);
	VAR_ZEROIFY(i);
	VAR_ZEROIFY(p_len);
	VAR_ZEROIFY(r_len);

	return ret;
}

int _ecfsdsa_sign_update(struct ec_sign_context *ctx,
			 const u8 *chunk, u32 chunklen)
{
	int ret;

	/*
	 * First, verify context has been initialized and private
	 * part too. This guarantees the context is an ECFSDSA
	 * signature one and we do not update() or finalize()
	 * before init().
	 */
	ret = sig_sign_check_initialized(ctx); EG(ret, err);
	ECFSDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.ecfsdsa), ret, err);

	/*  5. Compute h = H(r||m) */
	/* Since we call a callback, sanity check our mapping */
	ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
	ret = ctx->h->hfunc_update(&(ctx->sign_data.ecfsdsa.h_ctx), chunk, chunklen); EG(ret, err);

err:
	return ret;
}

int _ecfsdsa_sign_finalize(struct ec_sign_context *ctx, u8 *sig, u8 siglen)
{
	nn_src_t q, x;
	nn s, e, ex, *k;
	const ec_priv_key *priv_key;
	u8 e_buf[MAX_DIGEST_SIZE];
	bitcnt_t p_bit_len, q_bit_len;
	u8 hsize, s_len, r_len;
	int ret, iszero, cmp;
	u8 *r;

#ifdef USE_SIG_BLINDING
	/* b is the blinding mask */
	nn b, binv;
	b.magic = binv.magic = WORD(0);
#endif /* USE_SIG_BLINDING */

	s.magic = e.magic = ex.magic = WORD(0);

	/*
	 * First, verify context has been initialized and private
	 * part too. This guarantees the context is an ECFSDSA
	 * signature one and we do not finalize() before init().
	 */
	ret = sig_sign_check_initialized(ctx); EG(ret, err);
	ECFSDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.ecfsdsa), ret, err);
	MUST_HAVE((sig != NULL), ret, err);

	/* Make things more readable */
	priv_key = &(ctx->key_pair->priv_key);
	q = &(priv_key->params->ec_gen_order);
	x = &(priv_key->x);
	p_bit_len = ctx->key_pair->priv_key.params->ec_fp.p_bitlen;
	q_bit_len = ctx->key_pair->priv_key.params->ec_gen_order_bitlen;
	k = &(ctx->sign_data.ecfsdsa.k);
	r_len = (u8)ECFSDSA_R_LEN(p_bit_len);
	s_len = (u8)ECFSDSA_S_LEN(q_bit_len);
	hsize = ctx->h->digest_size;
	r = ctx->sign_data.ecfsdsa.r;

	/* Sanity check */
	ret = nn_cmp(x, q, &cmp); EG(ret, err);
	/* This should not happen and means that our
	 * private key is not compliant!
	 */
	MUST_HAVE((cmp < 0), ret, err);

	MUST_HAVE((siglen == ECFSDSA_SIGLEN(p_bit_len, q_bit_len)), ret, err);

#ifdef USE_SIG_BLINDING
	ret = nn_get_random_mod(&b, q); EG(ret, err);
	dbg_nn_print("b", &b);
#endif /* USE_SIG_BLINDING */

	/* Since we call a callback, sanity check our mapping */
	ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
	/*  5. Compute h = H(r||m) */
	/* Since we call a callback, sanity check our mapping */
	ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
	ret = ctx->h->hfunc_finalize(&(ctx->sign_data.ecfsdsa.h_ctx), e_buf); EG(ret, err);
	dbg_buf_print("h(R||m)", e_buf, hsize);

	/*  6. Compute e by converting h to an integer and reducing it mod q */
	ret = nn_init_from_buf(&e, e_buf, hsize); EG(ret, err);
	ret = local_memset(e_buf, 0, hsize); EG(ret, err);
	ret = nn_mod(&e, &e, q); EG(ret, err);

#ifdef USE_SIG_BLINDING
	/* Blind e with b */
	ret = nn_mod_mul(&e, &e, &b, q); EG(ret, err);
#endif /* USE_SIG_BLINDING */
	/*  7. Compute s = (k + ex) mod q */
	ret = nn_mod_mul(&ex, &e, x, q); EG(ret, err);
#ifdef USE_SIG_BLINDING
	/* Blind k with b */
	ret = nn_mod_mul(&s, k, &b, q); EG(ret, err);
	ret = nn_mod_add(&s, &s, &ex, q); EG(ret, err);
#else
	ret = nn_mod_add(&s, k, &ex, q); EG(ret, err);
#endif /* USE_SIG_BLINDING */
#ifdef USE_SIG_BLINDING
	/* Unblind s */
	/* NOTE: we use Fermat's little theorem inversion for
	 * constant time here. This is possible since q is prime.
	 */
	ret = nn_modinv_fermat(&binv, &b, q); EG(ret, err);
	ret = nn_mod_mul(&s, &s, &binv, q); EG(ret, err);
#endif /* USE_SIG_BLINDING */
	dbg_nn_print("s: ", &s);

	/*
	 * 8. If s is 0, restart the process at step 1.
	 *
	 * In practice, as we cannot restart the whole process in
	 * finalize() we just report an error.
	 */
	MUST_HAVE((!nn_iszero(&s, &iszero)) && (!iszero), ret, err);

	/*  9. Return (r,s) */
	ret = local_memcpy(sig, r, r_len); EG(ret, err);
	ret = local_memset(r, 0, r_len); EG(ret, err);
	ret = nn_export_to_buf(sig + r_len, s_len, &s);

 err:
	nn_uninit(&s);
	nn_uninit(&e);
	nn_uninit(&ex);
#ifdef USE_SIG_BLINDING
	nn_uninit(&b);
	nn_uninit(&binv);
#endif

	/*
	 * We can now clear data part of the context. This will clear
	 * magic and avoid further reuse of the whole context.
	 */
	if(ctx != NULL){
		IGNORE_RET_VAL(local_memset(&(ctx->sign_data.ecfsdsa), 0, sizeof(ecfsdsa_sign_data)));
	}

	PTR_NULLIFY(q);
	PTR_NULLIFY(x);
	PTR_NULLIFY(k);
	PTR_NULLIFY(priv_key);
	PTR_NULLIFY(r);
	VAR_ZEROIFY(hsize);
	VAR_ZEROIFY(p_bit_len);
	VAR_ZEROIFY(q_bit_len);
	VAR_ZEROIFY(r_len);
	VAR_ZEROIFY(s_len);

	return ret;
}

/*
 * Generic *internal* ECFSDSA verification functions (init, update and
 * finalize). Their purpose is to allow passing a specific hash function
 * (along with their output size) and the random ephemeral key k, so
 * that compliance tests against test vectors can be made without ugly
 * hack in the code itself.
 *
 * Global EC-FSDSA verification process is as follows (I,U,F provides
 * information in which function(s) (init(), update() or finalize())
 * a specific step is performed):
 *
 *| IUF - ECFSDSA verification
 *|
 *| I	1. Reject the signature if r is not a valid point on the curve.
 *| I	2. Reject the signature if s is not in ]0,q[
 *| IUF 3. Compute h = H(r||m)
 *|   F 4. Convert h to an integer and then compute e = -h mod q
 *|   F 5. compute W' = sG + eY, where Y is the public key
 *|   F 6. Compute r' = FE2OS(W'_x)||FE2OS(W'_y)
 *|   F 7. Accept the signature if and only if r equals r'
 *
 */

#define ECFSDSA_VERIFY_MAGIC ((word_t)(0x26afb13ccd96fa04ULL))
#define ECFSDSA_VERIFY_CHECK_INITIALIZED(A, ret, err) \
	MUST_HAVE((((void *)(A)) != NULL) && \
		  ((A)->magic == ECFSDSA_VERIFY_MAGIC), ret, err)

int _ecfsdsa_verify_init(struct ec_verify_context *ctx,
			 const u8 *sig, u8 siglen)
{
	bitcnt_t p_bit_len, q_bit_len;
	u8 p_len, r_len, s_len;
	int ret, iszero, on_curve, cmp;
	const u8 *r;
	nn_src_t q;
	fp rx, ry;
	nn *s;

	rx.magic = ry.magic = WORD(0);

	/* First, verify context has been initialized */
	ret = sig_verify_check_initialized(ctx); EG(ret, err);

	/* Do some sanity checks on input params */
	ret = pub_key_check_initialized_and_type(ctx->pub_key, ECFSDSA); EG(ret, err);
	MUST_HAVE((ctx->h != NULL) && (ctx->h->digest_size <= MAX_DIGEST_SIZE) &&
		(ctx->h->block_size <= MAX_BLOCK_SIZE), ret, err);
	MUST_HAVE((sig != NULL), ret, err);

	/* Make things more readable */
	q = &(ctx->pub_key->params->ec_gen_order);
	p_bit_len = ctx->pub_key->params->ec_fp.p_bitlen;
	q_bit_len = ctx->pub_key->params->ec_gen_order_bitlen;
	p_len = (u8)BYTECEIL(p_bit_len);
	r_len = (u8)ECFSDSA_R_LEN(p_bit_len);
	s_len = (u8)ECFSDSA_S_LEN(q_bit_len);
	s = &(ctx->verify_data.ecfsdsa.s);

	MUST_HAVE((siglen == ECFSDSA_SIGLEN(p_bit_len, q_bit_len)), ret, err);

	/*  1. Reject the signature if r is not a valid point on the curve. */

	/* Let's first import r, i.e. x and y coordinates of the point */
	r = sig;
	ret = fp_init(&rx, ctx->pub_key->params->ec_curve.a.ctx); EG(ret, err);
	ret = fp_import_from_buf(&rx, r, p_len); EG(ret, err);
	ret = fp_init(&ry, ctx->pub_key->params->ec_curve.a.ctx); EG(ret, err);
	ret = fp_import_from_buf(&ry, r + p_len, p_len); EG(ret, err);

	/* Let's now check that r represents a point on the curve */
	ret = is_on_shortw_curve(&rx, &ry, &(ctx->pub_key->params->ec_curve), &on_curve); EG(ret, err);
	MUST_HAVE(on_curve, ret, err);

	/* 2. Reject the signature if s is not in ]0,q[ */

	/* Import s as a nn */
	ret = nn_init_from_buf(s, sig + r_len, s_len); EG(ret, err);

	/* Check that s is in ]0,q[ */
	ret = nn_iszero(s, &iszero); EG(ret, err);
	ret = nn_cmp(s, q, &cmp); EG(ret, err);
	MUST_HAVE((!iszero) && (cmp < 0), ret, err);

	/* 3. Compute h = H(r||m) */

	/* Initialize the verify context */
	ret = local_memcpy(&(ctx->verify_data.ecfsdsa.r), r, r_len); EG(ret, err);
	/* Since we call a callback, sanity check our mapping */
	ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
	ret = ctx->h->hfunc_init(&(ctx->verify_data.ecfsdsa.h_ctx)); EG(ret, err);

	/* Since we call a callback, sanity check our mapping */
	ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
	ret = ctx->h->hfunc_update(&(ctx->verify_data.ecfsdsa.h_ctx), r, r_len); EG(ret, err);

	ctx->verify_data.ecfsdsa.magic = ECFSDSA_VERIFY_MAGIC;

 err:
	fp_uninit(&rx);
	fp_uninit(&ry);

	if (ret && (ctx != NULL)) {
		/*
		 * Signature is invalid. Clear data part of the context.
		 * This will clear magic and avoid further reuse of the
		 * whole context.
		 */
		IGNORE_RET_VAL(local_memset(&(ctx->verify_data.ecfsdsa), 0,
			     sizeof(ecfsdsa_verify_data)));
	}

	VAR_ZEROIFY(p_len);
	VAR_ZEROIFY(r_len);
	VAR_ZEROIFY(s_len);
	VAR_ZEROIFY(p_bit_len);
	VAR_ZEROIFY(q_bit_len);
	PTR_NULLIFY(r);
	PTR_NULLIFY(q);
	PTR_NULLIFY(s);

	return ret;
}

int _ecfsdsa_verify_update(struct ec_verify_context *ctx,
			   const u8 *chunk, u32 chunklen)
{
	int ret;

	/*
	 * First, verify context has been initialized and public
	 * part too. This guarantees the context is an ECFSDSA
	 * verification one and we do not update() or finalize()
	 * before init().
	 */
	ret = sig_verify_check_initialized(ctx); EG(ret, err);
	ECFSDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.ecfsdsa), ret, err);

	/* 3. Compute h = H(r||m) */
	/* Since we call a callback, sanity check our mapping */
	ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
	ret = ctx->h->hfunc_update(&(ctx->verify_data.ecfsdsa.h_ctx), chunk,
			     chunklen);

err:
	return ret;
}

int _ecfsdsa_verify_finalize(struct ec_verify_context *ctx)
{
	prj_pt_src_t G, Y;
	nn_src_t q;
	nn tmp, e, *s;
	prj_pt sG, eY;
	prj_pt_t Wprime;
	bitcnt_t p_bit_len, r_len;
	u8 r_prime[2 * NN_MAX_BYTE_LEN];
	u8 e_buf[MAX_DIGEST_SIZE];
	u8 hsize, p_len;
	const u8 *r;
	int ret, check;

	tmp.magic = e.magic = WORD(0);
	sG.magic = eY.magic = WORD(0);

	/* NOTE: we reuse sG for Wprime to optimize local variables */
	Wprime = &sG;

	/*
	 * First, verify context has been initialized and public
	 * part too. This guarantees the context is an ECFSDSA
	 * verification one and we do not finalize() before init().
	 */
	ret = sig_verify_check_initialized(ctx); EG(ret, err);
	ECFSDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.ecfsdsa), ret, err);

	/* Zero init points */
	ret = local_memset(&sG, 0, sizeof(prj_pt)); EG(ret, err);
	ret = local_memset(&eY, 0, sizeof(prj_pt)); EG(ret, err);

	/* Make things more readable */
	G = &(ctx->pub_key->params->ec_gen);
	Y = &(ctx->pub_key->y);
	q = &(ctx->pub_key->params->ec_gen_order);
	hsize = ctx->h->digest_size;
	s = &(ctx->verify_data.ecfsdsa.s);
	r = ctx->verify_data.ecfsdsa.r;
	p_bit_len = ctx->pub_key->params->ec_fp.p_bitlen;
	p_len = (u8)BYTECEIL(p_bit_len);
	r_len = (u8)ECFSDSA_R_LEN(p_bit_len);

	/* 3. Compute h = H(r||m) */
	/* Since we call a callback, sanity check our mapping */
	ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
	ret = ctx->h->hfunc_finalize(&(ctx->verify_data.ecfsdsa.h_ctx), e_buf); EG(ret, err);

	/*
	 * 4. Convert h to an integer and then compute e = -h mod q
	 *
	 * Because we only support positive integers, we compute
	 * e = q - (h mod q) (except when h is 0).
	 */
	ret = nn_init_from_buf(&tmp, e_buf, hsize); EG(ret, err);
	ret = local_memset(e_buf, 0, hsize); EG(ret, err);
	ret = nn_mod(&tmp, &tmp, q); EG(ret, err);

	ret = nn_mod_neg(&e, &tmp, q); EG(ret, err);

	/* 5. compute W' = (W'_x,W'_y) = sG + tY, where Y is the public key */
	ret = prj_pt_mul(&sG, s, G); EG(ret, err);
	ret = prj_pt_mul(&eY, &e, Y); EG(ret, err);
	ret = prj_pt_add(Wprime, &sG, &eY); EG(ret, err);
	ret = prj_pt_unique(Wprime, Wprime); EG(ret, err);

	/* 6. Compute r' = FE2OS(W'_x)||FE2OS(W'_y) */
	ret = fp_export_to_buf(r_prime, p_len, &(Wprime->X)); EG(ret, err);
	ret = fp_export_to_buf(r_prime + p_len, p_len, &(Wprime->Y)); EG(ret, err);

	dbg_buf_print("r_prime: ", r_prime, r_len);

	/* 7. Accept the signature if and only if r equals r' */
	ret = are_equal(r, r_prime, r_len, &check); EG(ret, err);
	ret = check ? 0 : -1;

err:
	IGNORE_RET_VAL(local_memset(r_prime, 0, sizeof(r_prime)));

	nn_uninit(&tmp);
	nn_uninit(&e);
	prj_pt_uninit(&sG);
	prj_pt_uninit(&eY);

	/*
	 * We can now clear data part of the context. This will clear
	 * magic and avoid further reuse of the whole context.
	 */
	if(ctx != NULL){
		IGNORE_RET_VAL(local_memset(&(ctx->verify_data.ecfsdsa), 0,
			     sizeof(ecfsdsa_verify_data)));
	}

	/* Clean what remains on the stack */
	PTR_NULLIFY(Wprime);
	PTR_NULLIFY(G);
	PTR_NULLIFY(Y);
	PTR_NULLIFY(q);
	PTR_NULLIFY(s);
	PTR_NULLIFY(r);
	VAR_ZEROIFY(p_len);
	VAR_ZEROIFY(r_len);
	VAR_ZEROIFY(hsize);

	return ret;
}

/*
 * NOTE: among all the EC-SDSA ISO14888-3 variants, only EC-FSDSA supports
 * batch verification as it is the only one allowing the recovery of the
 * underlying signature point from the signature value (other variants make
 * use of a hash of (parts) of this point.
 */
/* Batch verification function:
 * This function takes multiple signatures/messages/public keys, and
 * checks in an optimized way all the signatures.
 *
 * This returns 0 if *all* the signatures are correct, and -1 if at least
 * one signature is not correct.
 *
 */
static int _ecfsdsa_verify_batch_no_memory(const u8 **s, const u8 *s_len, const ec_pub_key **pub_keys,
					   const u8 **m, const u32 *m_len, u32 num, ec_alg_type sig_type,
					   hash_alg_type hash_type, const u8 **adata, const u16 *adata_len)
{
	nn_src_t q = NULL;
	prj_pt_src_t G = NULL;
	prj_pt_t W = NULL, Y = NULL;
	prj_pt Tmp, W_sum, Y_sum;
	nn S, S_sum, e, a;
	u8 hash[MAX_DIGEST_SIZE];
	const ec_pub_key *pub_key, *pub_key0;
	int ret, iszero, cmp;
	prj_pt_src_t pub_key_y;
	hash_context h_ctx;
	const hash_mapping *hm;
	ec_shortw_crv_src_t shortw_curve;
	ec_alg_type key_type = UNKNOWN_ALG;
	bitcnt_t p_bit_len, q_bit_len;
	u8 p_len, q_len;
	u16 hsize;
	u32 i;

	Tmp.magic = W_sum.magic = Y_sum.magic = WORD(0);
	S.magic = S_sum.magic = e.magic = a.magic = WORD(0);

	FORCE_USED_VAR(adata_len);
	FORCE_USED_VAR(adata);

	/* First, some sanity checks */
	MUST_HAVE((s != NULL) && (pub_keys != NULL) && (m != NULL), ret, err);
	/* We need at least one element in our batch data bags */
	MUST_HAVE((num > 0), ret, err);

	/* Zeroize buffers */
	ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err);

	pub_key0 = pub_keys[0];
	MUST_HAVE((pub_key0 != NULL), ret, err);

	/* Get our hash mapping */
	ret = get_hash_by_type(hash_type, &hm); EG(ret, err);
	hsize = hm->digest_size;
	MUST_HAVE((hm != NULL), ret, err);

	for(i = 0; i < num; i++){
		u8 siglen;
		const u8 *sig = NULL;

		ret = pub_key_check_initialized_and_type(pub_keys[i], ECFSDSA); EG(ret, err);

		/* Make things more readable */
		pub_key = pub_keys[i];

		/* Sanity check that all our public keys have the same parameters */
		MUST_HAVE((pub_key->params) == (pub_key0->params), ret, err);

		q = &(pub_key->params->ec_gen_order);
		shortw_curve = &(pub_key->params->ec_curve);
		pub_key_y = &(pub_key->y);
		key_type = pub_key->key_type;
		G = &(pub_key->params->ec_gen);
		p_bit_len = pub_key->params->ec_fp.p_bitlen;
		q_bit_len = pub_key->params->ec_gen_order_bitlen;
		p_len = (u8)BYTECEIL(p_bit_len);
		q_len = (u8)BYTECEIL(q_bit_len);

		/* Check given signature length is the expected one */
		siglen = s_len[i];
		sig = s[i];
		MUST_HAVE((siglen == ECFSDSA_SIGLEN(p_bit_len, q_bit_len)), ret, err);
		MUST_HAVE((siglen == (ECFSDSA_R_LEN(p_bit_len) + ECFSDSA_S_LEN(q_bit_len))), ret, err);

		/* Check the key type versus the algorithm */
		MUST_HAVE((key_type == sig_type), ret, err);

		if(i == 0){
			/* Initialize our sums to zero/point at infinity */
			ret = nn_init(&S_sum, 0); EG(ret, err);
			ret = prj_pt_init(&W_sum, shortw_curve); EG(ret, err);
			ret = prj_pt_zero(&W_sum); EG(ret, err);
			ret = prj_pt_init(&Y_sum, shortw_curve); EG(ret, err);
			ret = prj_pt_zero(&Y_sum); EG(ret, err);
			ret = prj_pt_init(&Tmp, shortw_curve); EG(ret, err);
			ret = nn_init(&e, 0); EG(ret, err);
			ret = nn_init(&a, 0); EG(ret, err);
		}

		/* Get a pseudo-random scalar a for randomizing the linear combination */
		ret = nn_get_random_mod(&a, q); EG(ret, err);

		/***************************************************/
		/* Extract s */
		ret = nn_init_from_buf(&S, &sig[2 * p_len], q_len); EG(ret, err);
		ret = nn_cmp(&S, q, &cmp); EG(ret, err);
		MUST_HAVE((cmp < 0), ret, err);

		dbg_nn_print("s", &S);

		/***************************************************/
		/* Add S to the sum */
		/* Multiply S by a */
		ret = nn_mod_mul(&S, &a, &S, q); EG(ret, err);
		ret = nn_mod_add(&S_sum, &S_sum,
				 &S, q); EG(ret, err);

		/***************************************************/
		/* Compute Y and add it to Y_sum */
		Y = &Tmp;
		/* Copy the public key point to work on the unique
		 * affine representative.
		 */
		ret = prj_pt_copy(Y, pub_key_y); EG(ret, err);
		ret = prj_pt_unique(Y, Y); EG(ret, err);
		dbg_ec_point_print("Y", Y);

		/* Compute e */
		ret = hm->hfunc_init(&h_ctx); EG(ret, err);
		ret = hm->hfunc_update(&h_ctx, &sig[0], (u32)(2 * p_len)); EG(ret, err);
		ret = hm->hfunc_update(&h_ctx, m[i], m_len[i]); EG(ret, err);
		ret = hm->hfunc_finalize(&h_ctx, hash); EG(ret, err);

		ret = nn_init_from_buf(&e, hash, hsize); EG(ret, err);
		ret = nn_mod(&e, &e, q); EG(ret, err);
		ret = nn_mod_neg(&e, &e, q); EG(ret, err);

		dbg_nn_print("e", &e);

		/* Multiply e by 'a' */
		ret = nn_mod_mul(&e, &e, &a, q); EG(ret, err);

		ret = _prj_pt_unprotected_mult(Y, &e, Y); EG(ret, err);
		dbg_ec_point_print("eY", Y);
		/* Add to the sum */
		ret = prj_pt_add(&Y_sum, &Y_sum, Y); EG(ret, err);

		/***************************************************/
		W = &Tmp;
		/* Compute W from rx and ry */
		ret = prj_pt_import_from_aff_buf(W, &sig[0], (u16)(2 * p_len), shortw_curve); EG(ret, err);

		/* Now multiply W by -a */
		ret = nn_mod_neg(&a, &a, q); EG(ret, err);
		ret = _prj_pt_unprotected_mult(W, &a, W); EG(ret, err);

		/* Add to the sum */
		ret = prj_pt_add(&W_sum, &W_sum, W); EG(ret, err);
		dbg_ec_point_print("aW", W);
	}
	/* Sanity check */
	MUST_HAVE((q != NULL) && (G != NULL), ret, err);

	/* Compute S_sum * G */
	ret = _prj_pt_unprotected_mult(&Tmp, &S_sum, G); EG(ret, err);
	/* Add P_sum and R_sum */
	ret = prj_pt_add(&Tmp, &Tmp, &W_sum); EG(ret, err);
	ret = prj_pt_add(&Tmp, &Tmp, &Y_sum); EG(ret, err);
	/* The result should be point at infinity */
	ret = prj_pt_iszero(&Tmp, &iszero); EG(ret, err);
	ret = (iszero == 1) ? 0 : -1;

err:
	PTR_NULLIFY(q);
	PTR_NULLIFY(pub_key);
	PTR_NULLIFY(pub_key0);
	PTR_NULLIFY(shortw_curve);
	PTR_NULLIFY(pub_key_y);
	PTR_NULLIFY(G);
	PTR_NULLIFY(W);
	PTR_NULLIFY(Y);

	prj_pt_uninit(&W_sum);
	prj_pt_uninit(&Y_sum);
	prj_pt_uninit(&Tmp);
	nn_uninit(&S);
	nn_uninit(&S_sum);
	nn_uninit(&e);
	nn_uninit(&a);

	return ret;
}


static int _ecfsdsa_verify_batch(const u8 **s, const u8 *s_len, const ec_pub_key **pub_keys,
				 const u8 **m, const u32 *m_len, u32 num, ec_alg_type sig_type,
				 hash_alg_type hash_type, const u8 **adata, const u16 *adata_len,
				 verify_batch_scratch_pad *scratch_pad_area, u32 *scratch_pad_area_len)
{
	nn_src_t q = NULL;
	prj_pt_src_t G = NULL;
	prj_pt_t W = NULL, Y = NULL;
	nn S, a;
	nn_t e = NULL;
	u8 hash[MAX_DIGEST_SIZE];
	const ec_pub_key *pub_key, *pub_key0;
	int ret, iszero, cmp;
	prj_pt_src_t pub_key_y;
	hash_context h_ctx;
	const hash_mapping *hm;
	ec_shortw_crv_src_t shortw_curve;
	ec_alg_type key_type = UNKNOWN_ALG;
	bitcnt_t p_bit_len, q_bit_len = 0;
	u8 p_len, q_len;
	u16 hsize;
	u32 i;
	/* NN numbers and points pointers */
	verify_batch_scratch_pad *elements = scratch_pad_area;
	u64 expected_len;

	S.magic = a.magic = WORD(0);

	FORCE_USED_VAR(adata_len);
	FORCE_USED_VAR(adata);

	/* First, some sanity checks */
	MUST_HAVE((s != NULL) && (pub_keys != NULL) && (m != NULL), ret, err);

	MUST_HAVE((scratch_pad_area_len != NULL), ret, err);
	MUST_HAVE(((2 * num) >= num), ret, err);
	MUST_HAVE(((2 * num) + 1) >= num, ret, err);

	/* Zeroize buffers */
	ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err);

	/* In oder to apply the algorithm, we must have at least two
	 * elements to verify. If this is not the case, we fallback to
	 * the regular "no memory" version.
	 */
	if(num <= 1){
		if(scratch_pad_area == NULL){
			/* We do not require any memory in this case */
			(*scratch_pad_area_len) = 0;
			ret = 0;
			goto err;
		}
		else{
			ret = _ecfsdsa_verify_batch_no_memory(s, s_len, pub_keys, m, m_len, num, sig_type,
							      hash_type, adata, adata_len);
			goto err;
		}
	}

	expected_len = ((2 * num) + 1) * sizeof(verify_batch_scratch_pad);
	MUST_HAVE((expected_len < 0xffffffff), ret, err);

	if(scratch_pad_area == NULL){
		/* Return the needed size: we need to keep track of (2 * num) + 1 NN numbers
		 * and (2 * num) + 1 projective points, plus (2 * num) + 1 indices
		 */
		(*scratch_pad_area_len) = (u32)expected_len;
		ret = 0;
		goto err;
	}
	else{
		MUST_HAVE((*scratch_pad_area_len) >= expected_len, ret, err);
	}

	pub_key0 = pub_keys[0];
	MUST_HAVE((pub_key0 != NULL), ret, err);

	/* Get our hash mapping */
	ret = get_hash_by_type(hash_type, &hm); EG(ret, err);
	hsize = hm->digest_size;
	MUST_HAVE((hm != NULL), ret, err);

	for(i = 0; i < num; i++){
		u8 siglen;
		const u8 *sig = NULL;

		ret = pub_key_check_initialized_and_type(pub_keys[i], ECFSDSA); EG(ret, err);

		/* Make things more readable */
		pub_key = pub_keys[i];

		/* Sanity check that all our public keys have the same parameters */
		MUST_HAVE((pub_key->params) == (pub_key0->params), ret, err);

		q = &(pub_key->params->ec_gen_order);
		shortw_curve = &(pub_key->params->ec_curve);
		pub_key_y = &(pub_key->y);
		key_type = pub_key->key_type;
		G = &(pub_key->params->ec_gen);
		p_bit_len = pub_key->params->ec_fp.p_bitlen;
		q_bit_len = pub_key->params->ec_gen_order_bitlen;
		p_len = (u8)BYTECEIL(p_bit_len);
		q_len = (u8)BYTECEIL(q_bit_len);

		/* Check given signature length is the expected one */
		siglen = s_len[i];
		sig = s[i];
		MUST_HAVE((siglen == ECFSDSA_SIGLEN(p_bit_len, q_bit_len)), ret, err);
		MUST_HAVE((siglen == (ECFSDSA_R_LEN(p_bit_len) + ECFSDSA_S_LEN(q_bit_len))), ret, err);

		/* Check the key type versus the algorithm */
		MUST_HAVE((key_type == sig_type), ret, err);

		if(i == 0){
			/* Initialize our sums to zero/point at infinity */
			ret = nn_init(&a, 0); EG(ret, err);
			ret = nn_init(&elements[(2 * num)].number, 0); EG(ret, err);
			ret = prj_pt_copy(&elements[(2 * num)].point, G); EG(ret, err);
		}

		/* Get a pseudo-random scalar a for randomizing the linear combination */
		ret = nn_get_random_mod(&a, q); EG(ret, err);

		/***************************************************/
		/* Extract s */
		ret = nn_init_from_buf(&S, &sig[2 * p_len], q_len); EG(ret, err);
		ret = nn_cmp(&S, q, &cmp); EG(ret, err);
		MUST_HAVE((cmp < 0), ret, err);

		dbg_nn_print("s", &S);

		/***************************************************/
		/* Add S to the sum */
		/* Multiply S by a */
		ret = nn_mod_mul(&S, &a, &S, q); EG(ret, err);
		ret = nn_mod_add(&elements[(2 * num)].number, &elements[(2 * num)].number,
				 &S, q); EG(ret, err);

		/***************************************************/
		/* Compute Y */
		Y = &elements[num + i].point;
		/* Copy the public key point to work on the unique
		 * affine representative.
		 */
		ret = prj_pt_copy(Y, pub_key_y); EG(ret, err);
		ret = prj_pt_unique(Y, Y); EG(ret, err);
		dbg_ec_point_print("Y", Y);

		/* Compute e */
		e = &elements[num + i].number;
		ret = nn_init(e, 0); EG(ret, err);
		ret = hm->hfunc_init(&h_ctx); EG(ret, err);
		ret = hm->hfunc_update(&h_ctx, &sig[0], (u32)(2 * p_len)); EG(ret, err);
		ret = hm->hfunc_update(&h_ctx, m[i], m_len[i]); EG(ret, err);
		ret = hm->hfunc_finalize(&h_ctx, hash); EG(ret, err);

		ret = nn_init_from_buf(e, hash, hsize); EG(ret, err);
		ret = nn_mod(e, e, q); EG(ret, err);
		ret = nn_mod_neg(e, e, q); EG(ret, err);

		dbg_nn_print("e", e);

		/* Multiply e by 'a' */
		ret = nn_mod_mul(e, e, &a, q); EG(ret, err);

		/***************************************************/
		W = &elements[i].point;
		/* Compute W from rx and ry */
		ret = prj_pt_import_from_aff_buf(W, &sig[0], (u16)(2 * p_len), shortw_curve); EG(ret, err);
		ret = nn_init(&elements[i].number, 0); EG(ret, err);
		ret = nn_copy(&elements[i].number, &a); EG(ret, err);
		ret = nn_mod_neg(&elements[i].number, &elements[i].number, q); EG(ret, err);
		dbg_ec_point_print("W", W);
	}

	/* Sanity check */
	MUST_HAVE((q != NULL) && (G != NULL) && (q_bit_len != 0), ret, err);

	/********************************************/
	/****** Bos-Coster algorithm ****************/
	ret = ec_verify_bos_coster(elements, (2 * num) + 1, q_bit_len);
	if(ret){
		if(ret == -2){
			/* In case of Bos-Coster time out, we fall back to the
			 * slower regular batch verification.
			 */
			ret = _ecfsdsa_verify_batch_no_memory(s, s_len, pub_keys, m, m_len, num, sig_type,
							      hash_type, adata, adata_len); EG(ret, err);
		}
		goto err;
	}


	/* The first element should contain the sum: it should
	 * be equal to zero. Reject the signature if this is not
	 * the case.
	 */
	ret = prj_pt_iszero(&elements[elements[0].index].point, &iszero); EG(ret, err);
	ret = iszero ? 0 : -1;

err:
	PTR_NULLIFY(q);
	PTR_NULLIFY(e);
	PTR_NULLIFY(pub_key);
	PTR_NULLIFY(pub_key0);
	PTR_NULLIFY(shortw_curve);
	PTR_NULLIFY(pub_key_y);
	PTR_NULLIFY(G);
	PTR_NULLIFY(W);
	PTR_NULLIFY(Y);

	nn_uninit(&S);
	nn_uninit(&a);

	return ret;
}


int ecfsdsa_verify_batch(const u8 **s, const u8 *s_len, const ec_pub_key **pub_keys,
			 const u8 **m, const u32 *m_len, u32 num, ec_alg_type sig_type,
			 hash_alg_type hash_type, const u8 **adata, const u16 *adata_len,
			 verify_batch_scratch_pad *scratch_pad_area, u32 *scratch_pad_area_len)
{
	int ret;

	if(scratch_pad_area != NULL){
		MUST_HAVE((scratch_pad_area_len != NULL), ret, err);
		ret = _ecfsdsa_verify_batch(s, s_len, pub_keys, m, m_len, num, sig_type,
					    hash_type, adata, adata_len,
					    scratch_pad_area, scratch_pad_area_len); EG(ret, err);

	}
	else{
		ret = _ecfsdsa_verify_batch_no_memory(s, s_len, pub_keys, m, m_len, num, sig_type,
						      hash_type, adata, adata_len); EG(ret, err);
	}

err:
	return ret;
}


#else /* WITH_SIG_ECFSDSA */

/*
 * Dummy definition to avoid the empty translation unit ISO C warning
 */
typedef int dummy;
#endif /* WITH_SIG_ECFSDSA */