/*
* Copyright (C) 2022 - This file is part of libecc project
*
* Authors:
* Ryad BENADJILA <ryadbenadjila@gmail.com>
* Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr>
*
* 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>
#if defined(WITH_SIG_BIP0340)
/* BIP0340 needs SHA-256: check it */
#if !defined(WITH_HASH_SHA256)
#error "Error: BIP0340 needs SHA-256 to be defined! Please define it in libecc config file"
#endif
#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 "BIP0340"
#endif
#include <libecc/utils/dbg_sig.h>
/*
* The current implementation is for the BIP0340 signature as described
* in https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki
*
* The BIP0340 signature is only compatible with SHA-256 and secp256k1,
* but we extend it to any hash function or curve.
*
*/
/* The "hash" function static prefixes */
#define BIP0340_AUX "BIP0340/aux"
#define BIP0340_NONCE "BIP0340/nonce"
#define BIP0340_CHALLENGE "BIP0340/challenge"
ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_hash(const u8 *tag, u32 tag_len,
const u8 *m, u32 m_len,
const hash_mapping *hm, hash_context *h_ctx)
{
int ret;
u8 hash[MAX_DIGEST_SIZE];
MUST_HAVE((h_ctx != NULL), ret, err);
ret = hash_mapping_callbacks_sanity_check(hm); EG(ret, err);
ret = hm->hfunc_init(h_ctx); EG(ret, err);
ret = hm->hfunc_update(h_ctx, tag, tag_len); EG(ret, err);
ret = hm->hfunc_finalize(h_ctx, hash); EG(ret, err);
/* Now compute hash(hash(tag) || hash(tag) || m) */
ret = hm->hfunc_init(h_ctx); EG(ret, err);
ret = hm->hfunc_update(h_ctx, hash, hm->digest_size); EG(ret, err);
ret = hm->hfunc_update(h_ctx, hash, hm->digest_size); EG(ret, err);
ret = hm->hfunc_update(h_ctx, m, m_len); EG(ret, err);
ret = 0;
err:
return ret;
}
/* Set the scalar value depending on the parity bit of the input
* point y coordinate.
*/
ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_set_scalar(nn_t scalar,
nn_src_t q,
prj_pt_src_t P)
{
int ret, isodd, isone;
/* Sanity check */
ret = prj_pt_check_initialized(P); EG(ret, err);
/* This operation is only meaningful on the "affine" representative.
* Check it.
*/
ret = nn_isone(&(P->Z.fp_val), &isone); EG(ret, err);
MUST_HAVE((isone), ret, err);
/* Check if Py is odd or even */
ret = nn_isodd(&(P->Y.fp_val), &isodd); EG(ret, err);
if(isodd){
/* Replace the input scalar by (q - scalar)
* (its opposite modulo q)
*/
ret = nn_mod_neg(scalar, scalar, q); EG(ret, err);
}
err:
return ret;
}
/*
* Generic *internal* helper for BIP340 public key initialization
* functions. The function returns 0 on success, -1 on error.
*/
int bip0340_init_pub_key(ec_pub_key *out_pub, const ec_priv_key *in_priv)
{
prj_pt_src_t G;
int ret;
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, BIP0340); EG(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 = BIP0340;
out_pub->params = in_priv->params;
out_pub->magic = PUB_KEY_MAGIC;
err:
return ret;
}
/*
* Generic *internal* helper for BIP0340 signature length functions.
*/
int bip0340_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)BIP0340_SIGLEN(p_bit_len, q_bit_len);
ret = 0;
err:
return ret;
}
/*
* Generic *internal* helper for BIP0340 signature.
* NOTE: because of the semi-deterministinc nonce generation
* process, streaming mode is NOT supported for signing.
* Hence the following all-in-one signature function.
*
* The function returns 0 on success, -1 on error.
*/
int _bip0340_sign(u8 *sig, u8 siglen, const ec_key_pair *key_pair,
const u8 *m, u32 mlen, int (*rand) (nn_t out, nn_src_t q),
ec_alg_type sig_type, hash_alg_type hash_type,
const u8 *adata, u16 adata_len)
{
prj_pt_src_t G;
prj_pt Y;
nn_src_t q;
nn k, d, e;
prj_pt kG;
const ec_priv_key *priv_key;
const ec_pub_key *pub_key;
bitcnt_t p_bit_len, q_bit_len;
u8 i, p_len, q_len;
int ret, cmp, iszero;
hash_context h_ctx;
const hash_mapping *hm;
u8 buff[MAX_DIGEST_SIZE];
#ifdef USE_SIG_BLINDING
/* b is the blinding mask */
nn b, binv;
b.magic = binv.magic = WORD(0);
#endif /* USE_SIG_BLINDING */
k.magic = d.magic = e.magic = kG.magic = Y.magic = WORD(0);
FORCE_USED_VAR(adata_len);
/* No ancillary data is expected with BIP0340 */
MUST_HAVE((key_pair != NULL) && (sig != NULL) && (adata == NULL), ret, err);
/* Check our algorithm type */
MUST_HAVE((sig_type == BIP0340), ret, err);
/* Check that keypair is initialized */
ret = key_pair_check_initialized_and_type(key_pair, BIP0340); EG(ret, err);
/* Get the hash mapping */
ret = get_hash_by_type(hash_type, &hm); EG(ret, err);
MUST_HAVE((hm != NULL), ret, err);
ret = hash_mapping_callbacks_sanity_check(hm); EG(ret, err);
/* Make things more readable */
priv_key = &(key_pair->priv_key);
pub_key = &(key_pair->pub_key);
G = &(priv_key->params->ec_gen);
q = &(priv_key->params->ec_gen_order);
p_bit_len = priv_key->params->ec_fp.p_bitlen;
q_bit_len = priv_key->params->ec_gen_order_bitlen;
q_len = (u8)BYTECEIL(q_bit_len);
p_len = (u8)BYTECEIL(p_bit_len);
/* 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);
ret = nn_init(&d, 0); EG(ret, err);
ret = nn_copy(&d, &(priv_key->x)); EG(ret, err);
dbg_nn_print("d", &d);
/* Check signature size */
MUST_HAVE((siglen == BIP0340_SIGLEN(p_bit_len, q_bit_len)), ret, err);
MUST_HAVE((p_len == BIP0340_R_LEN(p_bit_len)), ret, err);
MUST_HAVE((q_len == BIP0340_S_LEN(q_bit_len)), ret, err);
/* Fail if d = 0 or d >= q */
ret = nn_iszero(&d, &iszero); EG(ret, err);
ret = nn_cmp(&d, q, &cmp); EG(ret, err);
MUST_HAVE((!iszero) && (cmp < 0), ret, err);
/* Adjust d depending on public key y */
ret = _bip0340_set_scalar(&d, q, &Y); EG(ret, err);
/* Compute the nonce in a deterministic way.
* First, we get the random auxilary data.
*/
#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((rand == nn_get_random_mod), ret, err);
#endif
ret = nn_init(&e, 0); EG(ret, err);
ret = nn_one(&e); EG(ret, err);
ret = nn_lshift(&e, &e, (bitcnt_t)(8 * q_len)); EG(ret, err);
if(rand == NULL){
rand = nn_get_random_mod;
}
ret = rand(&k, &e); EG(ret, err);
dbg_nn_print("a", &k);
MUST_HAVE((siglen >= q_len), ret, err);
ret = nn_export_to_buf(&sig[0], q_len, &k); EG(ret, err);
/* Compute the seed for the nonce computation */
ret = _bip0340_hash((const u8*)BIP0340_AUX, sizeof(BIP0340_AUX) - 1,
&sig[0], q_len, hm, &h_ctx); EG(ret, err);
ret = hm->hfunc_finalize(&h_ctx, buff); EG(ret, err);
ret = nn_export_to_buf(&sig[0], q_len, &d); EG(ret, err);
if(q_len > hm->digest_size){
for(i = 0; i < hm->digest_size; i++){
sig[i] ^= buff[i];
}
ret = _bip0340_hash((const u8*)BIP0340_NONCE, sizeof(BIP0340_NONCE) - 1,
&sig[0], q_len, hm, &h_ctx); EG(ret, err);
}
else{
for(i = 0; i < q_len; i++){
buff[i] ^= sig[i];
}
ret = _bip0340_hash((const u8*)BIP0340_NONCE, sizeof(BIP0340_NONCE) - 1,
&buff[0], hm->digest_size, hm, &h_ctx); EG(ret, err);
}
ret = fp_export_to_buf(&sig[0], p_len, &(Y.X)); EG(ret, err);
ret = hm->hfunc_update(&h_ctx, &sig[0], p_len); EG(ret, err);
ret = hm->hfunc_update(&h_ctx, m, mlen); EG(ret, err);
ret = hm->hfunc_finalize(&h_ctx, buff); EG(ret, err);
/* Now import the semi-deterministic nonce modulo q */
ret = nn_init_from_buf(&k, buff, hm->digest_size); EG(ret, err);
ret = nn_mod(&k, &k, q); EG(ret, err);
dbg_nn_print("k", &k);
/* Fail if the nonce is zero */
ret = nn_iszero(&k, &iszero); EG(ret, err);
MUST_HAVE((!iszero), ret, err);
/* Proceed with the modulation exponentiation 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_ec_point_print("(k G)", &kG);
/* Update k depending on the kG y coordinate */
ret = _bip0340_set_scalar(&k, q, &kG); EG(ret, err);
/* Compute e */
/* We export our r here */
ret = fp_export_to_buf(&sig[0], p_len, &(kG.X)); EG(ret, err);
ret = _bip0340_hash((const u8*)BIP0340_CHALLENGE, sizeof(BIP0340_CHALLENGE) - 1,
&sig[0], p_len, hm, &h_ctx); EG(ret, err);
/* Export our public key */
ret = fp_export_to_buf(&sig[0], p_len, &(Y.X)); EG(ret, err);
ret = hm->hfunc_update(&h_ctx, &sig[0], p_len); EG(ret, err);
/* Update with the message */
ret = hm->hfunc_update(&h_ctx, m, mlen); EG(ret, err);
ret = hm->hfunc_finalize(&h_ctx, buff); EG(ret, err);
ret = nn_init_from_buf(&e, buff, hm->digest_size); EG(ret, err);
ret = nn_mod(&e, &e, q); EG(ret, err);
dbg_nn_print("e", &e);
/* Export our r in the signature */
dbg_nn_print("r", &(kG.X.fp_val));
ret = fp_export_to_buf(&sig[0], p_len, &(kG.X)); EG(ret, err);
/* Compute (k + ed) mod n */
#ifdef USE_SIG_BLINDING
ret = nn_get_random_mod(&b, q); EG(ret, err);
dbg_nn_print("b", &b);
#endif /* USE_SIG_BLINDING */
#ifdef USE_SIG_BLINDING
/* Blind e with b */
ret = nn_mod_mul(&e, &e, &b, q); EG(ret, err);
/* Blind k with b */
ret = nn_mod_mul(&k, &k, &b, q); EG(ret, err);
#endif /* USE_SIG_BLINDING */
ret = nn_mod_mul(&e, &e, &d, q); EG(ret, err);
ret = nn_mod_add(&e, &k, &e, q); EG(ret, err);
#ifdef USE_SIG_BLINDING
/* Unblind */
/* 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(&e, &e, &binv, q); EG(ret, err);
#endif /* USE_SIG_BLINDING */
/* Export our s in the signature */
dbg_nn_print("s", &e);
ret = nn_export_to_buf(&sig[p_len], q_len, &e); EG(ret, err);
err:
PTR_NULLIFY(G);
PTR_NULLIFY(q);
PTR_NULLIFY(priv_key);
PTR_NULLIFY(pub_key);
PTR_NULLIFY(hm);
prj_pt_uninit(&Y);
nn_uninit(&k);
nn_uninit(&e);
nn_uninit(&d);
return ret;
}
/* local helper for context sanity checks. Returns 0 on success, -1 on error. */
#define BIP0340_VERIFY_MAGIC ((word_t)(0x340175910abafcddULL))
#define BIP0340_VERIFY_CHECK_INITIALIZED(A, ret, err) \
MUST_HAVE((((const void *)(A)) != NULL) && \
((A)->magic == BIP0340_VERIFY_MAGIC), ret, err)
/*
* Generic *internal* helper for BIP0340 verification initialization functions.
* The function returns 0 on success, -1 on error.
*/
int _bip0340_verify_init(struct ec_verify_context *ctx,
const u8 *sig, u8 siglen)
{
bitcnt_t p_bit_len, q_bit_len;
u8 p_len, q_len;
int ret, cmp;
nn_src_t q;
prj_pt Y;
fp *rx;
nn *s;
u8 Pubx[NN_MAX_BYTE_LEN];
/* 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, BIP0340); 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);
/* Since we call a callback, sanity check our mapping */
ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(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);
q_len = (u8)BYTECEIL(q_bit_len);
s = &(ctx->verify_data.bip0340.s);
rx = &(ctx->verify_data.bip0340.r);
MUST_HAVE((siglen == BIP0340_SIGLEN(p_bit_len, q_bit_len)), ret, err);
MUST_HAVE((p_len == BIP0340_R_LEN(p_bit_len)), ret, err);
MUST_HAVE((q_len == BIP0340_S_LEN(q_bit_len)), ret, err);
/* Copy the public key point to work on the unique
* affine representative.
*/
ret = prj_pt_copy(&Y, &(ctx->pub_key->y)); EG(ret, err);
ret = prj_pt_unique(&Y, &Y); EG(ret, err);
/* Extract r and s */
ret = fp_init(rx, ctx->pub_key->params->ec_curve.a.ctx); EG(ret, err);
ret = fp_import_from_buf(rx, &sig[0], p_len); EG(ret, err);
ret = nn_init_from_buf(s, &sig[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("r", &(rx->fp_val));
dbg_nn_print("s", s);
/* Initialize our hash context */
ret = _bip0340_hash((const u8*)BIP0340_CHALLENGE, sizeof(BIP0340_CHALLENGE) - 1,
&sig[0], p_len, ctx->h,
&(ctx->verify_data.bip0340.h_ctx)); EG(ret, err);
ret = fp_export_to_buf(&Pubx[0], p_len, &(Y.X)); EG(ret, err);
ret = ctx->h->hfunc_update(&(ctx->verify_data.bip0340.h_ctx), &Pubx[0], p_len); EG(ret, err);
ret = local_memset(Pubx, 0, sizeof(Pubx)); EG(ret, err);
ctx->verify_data.bip0340.magic = BIP0340_VERIFY_MAGIC;
err:
PTR_NULLIFY(q);
PTR_NULLIFY(rx);
PTR_NULLIFY(s);
prj_pt_uninit(&Y);
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.bip0340), 0,
sizeof(bip0340_verify_data)));
}
return ret;
}
/*
* Generic *internal* helper for BIP0340 verification update functions.
* The function returns 0 on success, -1 on error.
*/
int _bip0340_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 BIP0340
* verification one and we do not update() or finalize()
* before init().
*/
ret = sig_verify_check_initialized(ctx); EG(ret, err);
BIP0340_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.bip0340), 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.bip0340.h_ctx), chunk,
chunklen);
err:
return ret;
}
/*
* Generic *internal* helper for BIP0340 verification finalization
* functions. The function returns 0 on success, -1 on error.
*/
int _bip0340_verify_finalize(struct ec_verify_context *ctx)
{
prj_pt_src_t G;
nn_src_t s, q;
fp_src_t r;
nn e;
prj_pt sG, eY, Y;
u8 e_buf[MAX_DIGEST_SIZE];
u8 hsize;
int ret, iszero, isodd, cmp;
ret = sig_verify_check_initialized(ctx); EG(ret, err);
BIP0340_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.bip0340), ret, err);
/* Since we call a callback, sanity check our mapping */
ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(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);
hsize = ctx->h->digest_size;
q = &(ctx->pub_key->params->ec_gen_order);
s = &(ctx->verify_data.bip0340.s);
r = &(ctx->verify_data.bip0340.r);
/* Copy the public key point to work on the unique
* affine representative.
*/
ret = prj_pt_copy(&Y, &(ctx->pub_key->y)); EG(ret, err);
ret = prj_pt_unique(&Y, &Y); EG(ret, err);
/* Compute e */
ret = ctx->h->hfunc_finalize(&(ctx->verify_data.bip0340.h_ctx),
&e_buf[0]); EG(ret, err);
ret = nn_init_from_buf(&e, e_buf, hsize); EG(ret, err);
ret = nn_mod(&e, &e, q); EG(ret, err);
dbg_nn_print("e", &e);
/* Compute s G - e Y */
ret = prj_pt_mul(&sG, s, G); EG(ret, err);
ret = nn_mod_neg(&e, &e, q); EG(ret, err); /* compute -e = (q - e) mod q */
/* Do we have to "lift" Y the public key ? */
ret = nn_isodd(&(Y.Y.fp_val), &isodd); EG(ret, err);
if(isodd){
/* If yes, negate the y coordinate */
ret = fp_neg(&(Y.Y), &(Y.Y)); EG(ret, err);
}
ret = prj_pt_mul(&eY, &e, &Y); EG(ret, err);
ret = prj_pt_add(&sG, &sG, &eY); EG(ret, err);
ret = prj_pt_unique(&sG, &sG); EG(ret, err);
dbg_ec_point_print("(s G - e Y)", &sG);
/* Reject point at infinity */
ret = prj_pt_iszero(&sG, &iszero); EG(ret, err);
MUST_HAVE((!iszero), ret, err);
/* Reject non even Y coordinate */
ret = nn_isodd(&(sG.Y.fp_val), &isodd); EG(ret, err);
MUST_HAVE((!isodd), ret, err);
/* Check the x coordinate against r */
ret = nn_cmp(&(r->fp_val), &(sG.X.fp_val), &cmp); EG(ret, err);
ret = (cmp == 0) ? 0 : -1;
err:
PTR_NULLIFY(G);
PTR_NULLIFY(s);
PTR_NULLIFY(q);
PTR_NULLIFY(r);
nn_uninit(&e);
prj_pt_uninit(&sG);
prj_pt_uninit(&eY);
prj_pt_uninit(&Y);
/*
* 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.bip0340), 0,
sizeof(bip0340_verify_data)));
}
return ret;
}
/*
* Helper to compute the seed to generate batch verification randomizing scalars.
*
*/
/****************************************************/
/*
* 32-bit integer manipulation macros (big endian)
*/
#ifndef GET_UINT32_LE
#define GET_UINT32_LE(n, b, i) \
do { \
(n) = ( ((u32) (b)[(i) + 3]) << 24 ) \
| ( ((u32) (b)[(i) + 2]) << 16 ) \
| ( ((u32) (b)[(i) + 1]) << 8 ) \
| ( ((u32) (b)[(i) ]) ); \
} while( 0 )
#endif
#ifndef PUT_UINT32_LE
#define PUT_UINT32_LE(n, b, i) \
do { \
(b)[(i) + 3] = (u8) ( (n) >> 24 ); \
(b)[(i) + 2] = (u8) ( (n) >> 16 ); \
(b)[(i) + 1] = (u8) ( (n) >> 8 ); \
(b)[(i) ] = (u8) ( (n) ); \
} while( 0 )
#endif
#ifndef PUT_UINT32_BE
#define PUT_UINT32_BE(n, b, i) \
do { \
(b)[(i) ] = (u8) ( (n) >> 24 ); \
(b)[(i) + 1] = (u8) ( (n) >> 16 ); \
(b)[(i) + 2] = (u8) ( (n) >> 8 ); \
(b)[(i) + 3] = (u8) ( (n) ); \
} while( 0 )
#endif
#define _CHACHA20_ROTL_(x, y) (((x) << (y)) | ((x) >> ((sizeof(u32) * 8) - (y))))
#define CHACA20_ROTL(x, y) ((((y) < (sizeof(u32) * 8)) && ((y) > 0)) ? (_CHACHA20_ROTL_(x, y)) : (x))
#define CHACHA20_QROUND(a, b, c, d) do { \
(a) += (b); \
(d) ^= (a); \
(d) = CHACA20_ROTL((d), 16); \
(c) += (d); \
(b) ^= (c); \
(b) = CHACA20_ROTL((b), 12); \
(a) += (b); \
(d) ^= (a); \
(d) = CHACA20_ROTL((d), 8); \
(c) += (d); \
(b) ^= (c); \
(b) = CHACA20_ROTL((b), 7); \
} while(0)
#define CHACHA20_INNER_BLOCK(s) do { \
CHACHA20_QROUND(s[0], s[4], s[ 8], s[12]); \
CHACHA20_QROUND(s[1], s[5], s[ 9], s[13]); \
CHACHA20_QROUND(s[2], s[6], s[10], s[14]); \
CHACHA20_QROUND(s[3], s[7], s[11], s[15]); \
CHACHA20_QROUND(s[0], s[5], s[10], s[15]); \
CHACHA20_QROUND(s[1], s[6], s[11], s[12]); \
CHACHA20_QROUND(s[2], s[7], s[ 8], s[13]); \
CHACHA20_QROUND(s[3], s[4], s[ 9], s[14]); \
} while(0)
#define CHACHA20_MAX_ASKED_LEN 64
ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_chacha20_block(const u8 key[32], const u8 nonce[12], u32 block_counter, u8 *stream, u32 stream_len){
int ret;
u32 state[16];
u32 initial_state[16];
unsigned int i;
MUST_HAVE((stream != NULL), ret, err);
MUST_HAVE((stream_len <= CHACHA20_MAX_ASKED_LEN), ret, err);
/* Initial state */
state[0] = 0x61707865;
state[1] = 0x3320646e;
state[2] = 0x79622d32;
state[3] = 0x6b206574;
for(i = 4; i < 12; i++){
GET_UINT32_LE(state[i], key, (4 * (i - 4)));
}
state[12] = block_counter;
for(i = 13; i < 16; i++){
GET_UINT32_LE(state[i], nonce, (4 * (i - 13)));
}
/* Core loop */
ret = local_memcpy(initial_state, state, sizeof(state)); EG(ret, err);
for(i = 0; i < 10; i++){
CHACHA20_INNER_BLOCK(state);
}
/* Serialize and output the block */
for(i = 0; i < 16; i++){
u32 tmp = (u32)(state[i] + initial_state[i]);
PUT_UINT32_LE(tmp, (u8*)(&state[i]), 0);
}
ret = local_memcpy(stream, &state[0], stream_len);
err:
return ret;
}
ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_compute_batch_csprng_one_scalar(const u8 *seed, u32 seedlen,
u8 *scalar, u32 scalar_len, u32 num)
{
int ret;
u8 nonce[12];
/* Sanity check for ChaCha20 */
MUST_HAVE((seedlen == SHA256_DIGEST_SIZE) && (scalar_len <= CHACHA20_MAX_ASKED_LEN), ret, err);
/* NOTE: nothing in the BIP340 specification fixes the nonce for
* ChaCha20. We simply use 0 here for the nonce. */
ret = local_memset(nonce, 0, sizeof(nonce)); EG(ret, err);
/* Use our CSPRNG based on ChaCha20 to generate the scalars */
ret = _bip0340_chacha20_block(seed, nonce, num, scalar, scalar_len);
err:
return ret;
}
ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_compute_batch_csprng_scalars(const u8 *seed, u32 seedlen,
u8 *scalar, u32 scalar_len,
u32 *num, nn_src_t q,
bitcnt_t q_bit_len, u8 q_len,
nn_t a)
{
int ret, iszero, cmp;
u32 size, remain;
MUST_HAVE((seed != NULL) && (scalar != NULL) && (num != NULL) && (a != NULL), ret, err);
MUST_HAVE((scalar_len >= q_len), ret, err);
gen_scalar_again:
size = remain = 0;
while(size < q_len){
MUST_HAVE((*num) < 0xffffffff, ret, err);
remain = ((q_len - size) < CHACHA20_MAX_ASKED_LEN) ? (q_len - size): CHACHA20_MAX_ASKED_LEN;
ret = _bip0340_compute_batch_csprng_one_scalar(seed, seedlen,
&scalar[size], remain,
(*num)); EG(ret, err);
(*num)++;
size += remain;
}
if((q_bit_len % 8) != 0){
/* Handle the cutoff when q_bit_len is not a byte multiple */
scalar[0] &= (u8)((0x1 << (q_bit_len % 8)) - 1);
}
/* Import the scalar */
ret = nn_init_from_buf(a, scalar, q_len); EG(ret, err);
/* Check if the scalar is between 1 and q-1 */
ret = nn_iszero(a, &iszero); EG(ret, err);
ret = nn_cmp(a, q, &cmp); EG(ret, err);
if((iszero) || (cmp >= 0)){
goto gen_scalar_again;
}
ret = 0;
err:
return ret;
}
ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_compute_batch_csprng_seed(const u8 **s, const u8 *s_len,
const ec_pub_key **pub_keys,
const u8 **m, const u32 *m_len, u32 num,
u8 p_len, u8 *seed, u32 seedlen)
{
int ret;
u32 i;
hash_context h_ctx;
u8 Pubx[NN_MAX_BYTE_LEN];
const hash_mapping *hm;
/* NOTE: sanity checks on inputs are performed by the upper layer */
ret = local_memset(Pubx, 0, sizeof(Pubx)); EG(ret, err);
/* Get our hash mapping for SHA-256 as we need a fixed 256-bit key
* for keying our ChaCha20 CSPRNG
*/
ret = get_hash_by_type(SHA256, &hm); EG(ret, err);
MUST_HAVE((hm != NULL), ret, err);
MUST_HAVE((seedlen == hm->digest_size), ret, err);
/* As per specification, seed = seed_hash(pk1..pku || m1..mu || sig1..sigu), instantiated
* with SHA-256 */
ret = hm->hfunc_init(&h_ctx); EG(ret, err);
for(i = 0; i < num; i++){
ret = fp_export_to_buf(&Pubx[0], p_len, &(pub_keys[i]->y.X)); EG(ret, err);
ret = hm->hfunc_update(&h_ctx, &Pubx[0], p_len); EG(ret, err);
}
for(i = 0; i < num; i++){
ret = hm->hfunc_update(&h_ctx, m[i], m_len[i]); EG(ret, err);
}
for(i = 0; i < num; i++){
ret = hm->hfunc_update(&h_ctx, s[i], s_len[i]); EG(ret, err);
}
ret = hm->hfunc_finalize(&h_ctx, seed);
err:
return ret;
}
/* 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 _bip0340_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 R = NULL, Y = NULL;
prj_pt Tmp, R_sum, P_sum;
nn S, S_sum, e, a;
fp rx;
u8 hash[MAX_DIGEST_SIZE];
u8 Pubx[NN_MAX_BYTE_LEN];
const ec_pub_key *pub_key, *pub_key0;
int ret, iszero, isodd, 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;
u8 chacha20_seed[SHA256_DIGEST_SIZE];
u8 chacha20_scalar[BYTECEIL(CURVES_MAX_Q_BIT_LEN)];
u32 chacha20_scalar_counter = 1;
Tmp.magic = R_sum.magic = P_sum.magic = WORD(0);
S.magic = S_sum.magic = e.magic = a.magic = WORD(0);
rx.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);
ret = local_memset(Pubx, 0, sizeof(Pubx)); EG(ret, err);
ret = local_memset(chacha20_seed, 0,sizeof(chacha20_seed)); EG(ret, err);
ret = local_memset(chacha20_scalar, 0,sizeof(chacha20_scalar)); 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], BIP0340); 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 == BIP0340_SIGLEN(p_bit_len, q_bit_len)), ret, err);
MUST_HAVE((siglen == (BIP0340_R_LEN(p_bit_len) + BIP0340_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(&R_sum, shortw_curve); EG(ret, err);
ret = prj_pt_zero(&R_sum); EG(ret, err);
ret = prj_pt_init(&P_sum, shortw_curve); EG(ret, err);
ret = prj_pt_zero(&P_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);
/* Compute the ChaCha20 seed */
ret = _bip0340_compute_batch_csprng_seed(s, s_len, pub_keys, m, m_len, num,
p_len, chacha20_seed,
sizeof(chacha20_seed)); EG(ret, err);
}
else{
/* Get a pseudo-random scalar a for randomizing the linear combination */
ret = _bip0340_compute_batch_csprng_scalars(chacha20_seed, sizeof(chacha20_seed),
chacha20_scalar, sizeof(chacha20_scalar),
&chacha20_scalar_counter, q,
q_bit_len, q_len, &a); EG(ret, err);
}
/***************************************************/
/* Extract r and s */
ret = fp_init(&rx, pub_key->params->ec_curve.a.ctx); EG(ret, err);
ret = fp_import_from_buf(&rx, &sig[0], p_len); EG(ret, err);
ret = nn_init_from_buf(&S, &sig[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("r", &(rx.fp_val));
dbg_nn_print("s", &S);
/***************************************************/
/* Add S to the sum */
/* Multiply S by a */
if(i != 0){
ret = nn_mod_mul(&S, &a, &S, q); EG(ret, err);
}
ret = nn_mod_add(&S_sum, &S_sum, &S, q); EG(ret, err);
/***************************************************/
R = &Tmp;
/* Compute R from rx */
ret = fp_copy(&(R->X), &rx); EG(ret, err);
ret = aff_pt_y_from_x(&(R->Y), &(R->Z), &rx, shortw_curve); EG(ret, err);
/* "Lift" R by choosing the even solution */
ret = nn_isodd(&(R->Y.fp_val), &isodd); EG(ret, err);
if(isodd){
ret = fp_copy(&(R->Y), &(R->Z)); EG(ret, err);
}
ret = fp_one(&(R->Z)); EG(ret, err);
/* Now multiply R by a */
if(i != 0){
ret = _prj_pt_unprotected_mult(R, &a, R); EG(ret, err);
}
/* Add to the sum */
ret = prj_pt_add(&R_sum, &R_sum, R); EG(ret, err);
dbg_ec_point_print("aR", R);
/***************************************************/
/* Compute P and add it to P_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);
/* Do we have to "lift" Y the public key ? */
ret = nn_isodd(&(Y->Y.fp_val), &isodd); EG(ret, err);
if(isodd){
/* If yes, negate the y coordinate */
ret = fp_neg(&(Y->Y), &(Y->Y)); EG(ret, err);
}
dbg_ec_point_print("Y", Y);
/* Compute e */
ret = _bip0340_hash((const u8*)BIP0340_CHALLENGE, sizeof(BIP0340_CHALLENGE) - 1,
&sig[0], p_len, hm,
&h_ctx); EG(ret, err);
ret = fp_export_to_buf(&Pubx[0], p_len, &(Y->X)); EG(ret, err);
ret = hm->hfunc_update(&h_ctx, &Pubx[0], 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);
dbg_nn_print("e", &e);
/* Multiply e by 'a' */
if(i != 0){
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(&P_sum, &P_sum, Y); EG(ret, err);
}
/* Sanity check */
MUST_HAVE((q != NULL) && (G != NULL), ret, err);
/* Compute S_sum * G */
ret = nn_mod_neg(&S_sum, &S_sum, q); EG(ret, err); /* -S_sum = q - S_sum*/
ret = _prj_pt_unprotected_mult(&Tmp, &S_sum, G); EG(ret, err);
/* Add P_sum and R_sum */
ret = prj_pt_add(&Tmp, &Tmp, &R_sum); EG(ret, err);
ret = prj_pt_add(&Tmp, &Tmp, &P_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(R);
PTR_NULLIFY(Y);
prj_pt_uninit(&R_sum);
prj_pt_uninit(&P_sum);
prj_pt_uninit(&Tmp);
nn_uninit(&S);
nn_uninit(&S_sum);
nn_uninit(&e);
nn_uninit(&a);
fp_uninit(&rx);
return ret;
}
static int _bip0340_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 R = NULL, Y = NULL;
nn S, a;
nn_t e = NULL;
fp rx;
u8 hash[MAX_DIGEST_SIZE];
u8 Pubx[NN_MAX_BYTE_LEN];
const ec_pub_key *pub_key, *pub_key0;
int ret, iszero, isodd, 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;
u8 chacha20_seed[SHA256_DIGEST_SIZE];
u8 chacha20_scalar[BYTECEIL(CURVES_MAX_Q_BIT_LEN)];
u32 chacha20_scalar_counter = 1;
S.magic = a.magic = WORD(0);
rx.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);
ret = local_memset(Pubx, 0, sizeof(Pubx)); EG(ret, err);
ret = local_memset(chacha20_seed, 0,sizeof(chacha20_seed)); EG(ret, err);
ret = local_memset(chacha20_scalar, 0,sizeof(chacha20_scalar)); 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 = _bip0340_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;
}
}
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], BIP0340); 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 == BIP0340_SIGLEN(p_bit_len, q_bit_len)), ret, err);
MUST_HAVE((siglen == (BIP0340_R_LEN(p_bit_len) + BIP0340_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);
/* Compute the ChaCha20 seed */
ret = _bip0340_compute_batch_csprng_seed(s, s_len, pub_keys, m, m_len, num,
p_len, chacha20_seed,
sizeof(chacha20_seed)); EG(ret, err);
}
else{
/* Get a pseudo-random scalar a for randomizing the linear combination */
ret = _bip0340_compute_batch_csprng_scalars(chacha20_seed, sizeof(chacha20_seed),
chacha20_scalar, sizeof(chacha20_scalar),
&chacha20_scalar_counter, q,
q_bit_len, q_len, &a); EG(ret, err);
}
/***************************************************/
/* Extract r and s */
ret = fp_init(&rx, pub_key->params->ec_curve.a.ctx); EG(ret, err);
ret = fp_import_from_buf(&rx, &sig[0], p_len); EG(ret, err);
ret = nn_init_from_buf(&S, &sig[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("r", &(rx.fp_val));
dbg_nn_print("s", &S);
/***************************************************/
/* Add S to the sum */
/* Multiply S by a */
if(i != 0){
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);
/***************************************************/
/* Initialize R */
R = &elements[i].point;
ret = prj_pt_init(R, shortw_curve); EG(ret, err);
/* Compute R from rx */
ret = fp_copy(&(R->X), &rx); EG(ret, err);
ret = aff_pt_y_from_x(&(R->Y), &(R->Z), &rx, shortw_curve); EG(ret, err);
/* "Lift" R by choosing the even solution */
ret = nn_isodd(&(R->Y.fp_val), &isodd); EG(ret, err);
if(isodd){
ret = fp_copy(&(R->Y), &(R->Z)); EG(ret, err);
}
ret = fp_one(&(R->Z)); EG(ret, err);
if(i != 0){
ret = nn_init(&elements[i].number, 0); EG(ret, err);
ret = nn_copy(&elements[i].number, &a); EG(ret, err);
}
else{
ret = nn_init(&elements[i].number, 0); EG(ret, err);
ret = nn_one(&elements[i].number); EG(ret, err);
}
dbg_ec_point_print("R", R);
/***************************************************/
/* Compute P and add it to P_sum */
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);
/* Do we have to "lift" Y the public key ? */
ret = nn_isodd(&(Y->Y.fp_val), &isodd); EG(ret, err);
if(isodd){
/* If yes, negate the y coordinate */
ret = fp_neg(&(Y->Y), &(Y->Y)); EG(ret, err);
}
dbg_ec_point_print("Y", Y);
/* Compute e */
/* Store the coefficient */
e = &elements[num + i].number;
ret = nn_init(e, 0); EG(ret, err);
ret = _bip0340_hash((const u8*)BIP0340_CHALLENGE, sizeof(BIP0340_CHALLENGE) - 1,
&sig[0], p_len, hm,
&h_ctx); EG(ret, err);
ret = fp_export_to_buf(&Pubx[0], p_len, &(Y->X)); EG(ret, err);
ret = hm->hfunc_update(&h_ctx, &Pubx[0], 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);
dbg_nn_print("e", e);
/* Multiply e by 'a' */
if(i != 0){
ret = nn_mod_mul(e, e, &a, q); EG(ret, err);
}
}
/* 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 = _bip0340_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(R);
PTR_NULLIFY(Y);
/* Unitialize all our scratch_pad_area */
if((scratch_pad_area != NULL) && (scratch_pad_area_len != NULL)){
IGNORE_RET_VAL(local_memset((u8*)scratch_pad_area, 0, (*scratch_pad_area_len)));
}
nn_uninit(&S);
nn_uninit(&a);
fp_uninit(&rx);
return ret;
}
int bip0340_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 = _bip0340_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 = _bip0340_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 /* defined(WITH_SIG_BIP0340) */
/*
* Dummy definition to avoid the empty translation unit ISO C warning
*/
typedef int dummy;
#endif /* defined(WITH_SIG_BIP0340) */