/* The secret integers s0 and s1 must be in the range 0 < s < n for
   some n, and must be relatively prime to that n.  We know a priori
   that n is of the form 2**k * p for some small integer k and prime
   p.  Therefore, it suffices to choose a random integer in the range
   [0, n/2), multiply by two and add one (enforcing oddness), and then
   reject values which are divisible by p.  */
static BIGNUM *
random_s(const BIGNUM *n, const BIGNUM *p, BN_CTX *c)
{
  BIGNUM h, m, *r;

  BN_init(&h);
  BN_init(&m);
  FAILZ(r = BN_new());
  FAILZ(BN_copy(&h, n));
  FAILZ(BN_rshift1(&h, &h));

  do {
    FAILZ(BN_rand_range(r, &h));
    FAILZ(BN_lshift1(r, r));
    FAILZ(BN_add(r, r, BN_value_one()));
    FAILZ(BN_nnmod(&m, r, p, c));
  } while (BN_is_zero(&m));

  BN_clear(&h);
  BN_clear(&m);
  return r;

 fail:
  BN_clear(&h);
  BN_clear(&m);
  if (r) BN_clear_free(r);
  return 0;
}

int
MKEM_decode_message(const MKEM *kp, uint8_t *secret, const uint8_t *message)
{
  int use_curve0 = !(message[0] & kp->params->curve_bit);
  const EC_GROUP *ca = use_curve0 ? kp->params->c0 : kp->params->c1;
  const BIGNUM *sa = use_curve0 ? kp->s0 : kp->s1;
  EC_POINT *q = 0, *r = 0;
  uint8_t *unpadded = 0;
  BIGNUM x, y;
  size_t mlen = kp->params->msgsize;
  int rv;

  if (!kp->s0 || !kp->s1) /* secret key not available */
    return -1;

  BN_init(&x);
  BN_init(&y);
  FAILZ(q = EC_POINT_new(ca));
  FAILZ(r = EC_POINT_new(ca));
  FAILZ(unpadded = malloc(mlen + 1));

  /* Copy the message, erase the padding bits, and put an 0x02 byte on
     the front so we can use EC_POINT_oct2point to recover the
     y-coordinate. */
  unpadded[0] = 0x02;
  unpadded[1] = (message[0] & ~(kp->params->pad_mask|kp->params->curve_bit));
  memcpy(&unpadded[2], &message[1], mlen - 1);

  FAILZ(EC_POINT_oct2point(ca, q, unpadded, mlen + 1,
                           kp->params->ctx));
  FAILZ(EC_POINT_mul(ca, r, 0, q, sa, kp->params->ctx));

  FAILZ(EC_POINT_get_affine_coordinates_GF2m(ca, q, &x, &y, kp->params->ctx));
  if (bn2bin_padhi(&x, secret, mlen) != mlen)
    goto fail;

  FAILZ(EC_POINT_get_affine_coordinates_GF2m(ca, r, &x, &y, kp->params->ctx));
  if (bn2bin_padhi(&x, secret + mlen, mlen) != mlen)
    goto fail;

  rv = 0;
 done:
  if (unpadded) {
    memset(unpadded, 0, mlen + 1);
    free(unpadded);
  }
  if (q) EC_POINT_clear_free(q);
  if (r) EC_POINT_clear_free(r);
  BN_clear(&x);
  BN_clear(&y);
  return rv;

 fail:
  rv = -1;
  memset(secret, 0, mlen * 2);
  goto done;
}

/**
 * Validates the format of the boot signature block, and checks that
 * the length in authenticated attributes matches the actual length of
 * the image.
 * @param bs The boot signature block to validate
 * @param length The actual length of the boot image without the signature
 */
static int validate_signature_block(const BootSignature *bs, uint64_t length)
{
    BIGNUM expected;
    BIGNUM value;
    int rc = -1;

    if (!bs) {
        return -1;
    }

    BN_init(&expected);
    BN_init(&value);

    /* Confirm that formatVersion matches our supported version */
    if (!BN_set_word(&expected, FORMAT_VERSION)) {
        ERR_print_errors(g_error);
        goto vsb_done;
    }

    ASN1_INTEGER_to_BN(bs->formatVersion, &value);

    if (BN_cmp(&expected, &value) != 0) {
        printf("Unsupported signature version\n");
        goto vsb_done;
    }

    BN_clear(&expected);
    BN_clear(&value);

    /* Confirm that the length of the image matches with the length in
        the authenticated attributes */
    length = htobe64(length);
    BN_bin2bn((const unsigned char *) &length, sizeof(length), &expected);

    ASN1_INTEGER_to_BN(bs->authenticatedAttributes->length, &value);

    if (BN_cmp(&expected, &value) != 0) {
        printf("Image length doesn't match signature attributes\n");
        goto vsb_done;
    }

    rc = 0;

vsb_done:
    BN_free(&expected);
    BN_free(&value);

    return rc;
}

/**
 * Generate a prime number
 *
 * The internal CPRNG is seeded using the provided seed value.
 *
 * @param prime Pointer for storage of prime number
 * @param s Secret to share
 * @param bits Bit size of prime
 * @param rngSeed Seed value for CPRNG
 * @param rngSeedLength Length of Seed value for CPRNG
 *
 */
static int generatePrime(BIGNUM *prime, const BIGNUM *s, const int bits, unsigned char *rngSeed, const unsigned int rngSeedLength)
{
	int max_rounds = 1000;

	// Seed the RNG
	RAND_seed(rngSeed, rngSeedLength);

	// Clear the prime value
	BN_clear(prime);

	do {
		// Generate random prime
#if OPENSSL_VERSION_NUMBER  >= 0x00908000L /* last parm is BN_GENCB which is null in our case */
		BN_generate_prime_ex(prime, bits, 1, NULL, NULL, NULL);
#else
		BN_generate_prime(prime, bits, 1, NULL, NULL, NULL, NULL );
#endif

	} while ((BN_ucmp(prime, s) == -1) && (max_rounds-- > 0));	// If prime < s or not reached 1000 tries

	if (max_rounds > 0)
		return 0;
	else
		return -1; // We could not find a prime number
}

int
dh_gen_key(DH *dh, int need)
{
	int pbits;
	const BIGNUM *p, *pub_key, *priv_key;

	DH_get0_pqg(dh, &p, NULL, NULL);

	if (need < 0 || p == NULL ||
	    (pbits = BN_num_bits(p)) <= 0 ||
	    need > INT_MAX / 2 || 2 * need > pbits)
		return SSH_ERR_INVALID_ARGUMENT;
	if (need < 256)
		need = 256;
	/*
	 * Pollard Rho, Big step/Little Step attacks are O(sqrt(n)),
	 * so double requested need here.
	 */
	DH_set_length(dh, MIN(need * 2, pbits - 1));
	if (DH_generate_key(dh) == 0) {
		return SSH_ERR_LIBCRYPTO_ERROR;
	}
	DH_get0_key(dh, &pub_key, &priv_key);
	if (!dh_pub_is_valid(dh, pub_key)) {
#if 0
		BN_clear(priv_key);
#endif
		return SSH_ERR_LIBCRYPTO_ERROR;
	}
	return 0;
}

BIGNUM *
BN_bin2bn(const void *s, int len, BIGNUM *bn)
{
    heim_integer *hi = (void *)bn;

    if (len < 0)
	return NULL;

    if (hi == NULL) {
	hi = (heim_integer *)BN_new();
	if (hi == NULL)
	    return NULL;
    }
    if (hi->data)
	BN_clear((BIGNUM *)hi);
    hi->negative = 0;
    hi->data = malloc(len);
    if (hi->data == NULL && len != 0) {
	if (bn == NULL)
	    BN_free((BIGNUM *)hi);
	return NULL;
    }
    hi->length = len;
    memcpy(hi->data, s, len);
    return (BIGNUM *)hi;
}

CHECK_RETVAL_BOOL \
static BOOLEAN selfTestGeneralOps1( void )
	{
	BIGNUM a;

	/* Simple tests that don't need the support of higher-level routines 
	   like importBignum() */
	BN_init( &a );
	if( !BN_zero( &a ) )
		return( FALSE );
	if( !BN_is_zero( &a ) || BN_is_one( &a ) )
		return( FALSE );
	if( !BN_is_word( &a, 0 ) || BN_is_word( &a, 1 ) )
		return( FALSE );
	if( BN_is_odd( &a ) )
		return( FALSE );
	if( BN_get_word( &a ) != 0 )
		return( FALSE );
	if( !BN_one( &a ) )
		return( FALSE );
	if( BN_is_zero( &a ) || !BN_is_one( &a ) )
		return( FALSE );
	if( BN_is_word( &a, 0 ) || !BN_is_word( &a, 1 ) )
		return( FALSE );
	if( !BN_is_odd( &a ) )
		return( FALSE );
	if( BN_num_bytes( &a ) != 1 )
		return( FALSE );
	if( BN_get_word( &a ) != 1 )
		return( FALSE );
	BN_clear( &a );

	return( TRUE );
	}

int
BN_rand(BIGNUM *bn, int bits, int top, int bottom)
{
    size_t len = (bits + 7) / 8;
    heim_integer *i = (heim_integer *)bn;

    BN_clear(bn);

    i->negative = 0;
    i->data = malloc(len);
    if (i->data == NULL && len != 0)
	return 0;
    i->length = len;

    if (RAND_bytes(i->data, i->length) != 1) {
	free(i->data);
	i->data = NULL;
	return 0;
    }

    {
	size_t j = len * 8;
	while(j > bits) {
	    BN_clear_bit(bn, j - 1);
	    j--;
	}
    }

    if (top == -1) {
	;
    } else if (top == 0 && bits > 0) {
	BN_set_bit(bn, bits - 1);
    } else if (top == 1 && bits > 1) {
	BN_set_bit(bn, bits - 1);
	BN_set_bit(bn, bits - 2);
    } else {
	BN_clear(bn);
	return 0;
    }

    if (bottom && bits > 0)
	BN_set_bit(bn, 0);

    return 1;
}

void
vg_exec_context_consolidate_key(vg_exec_context_t *vxcp)
{
	if (vxcp->vxc_delta) {
		BN_clear(&vxcp->vxc_bntmp);
		BN_set_word(&vxcp->vxc_bntmp, vxcp->vxc_delta);
		BN_add(&vxcp->vxc_bntmp2,
		       EC_KEY_get0_private_key(vxcp->vxc_key),
		       &vxcp->vxc_bntmp);
		vg_set_privkey(&vxcp->vxc_bntmp2, vxcp->vxc_key);
		vxcp->vxc_delta = 0;
	}
}

static void
vg_prefix_range_sum(vg_prefix_t *vp, BIGNUM *result, BIGNUM *tmp1)
{
	vg_prefix_t *startp;

	startp = vp;
	BN_clear(result);
	do {
		BN_sub(tmp1, vp->vp_high, vp->vp_low);
		BN_add(result, result, tmp1);
		vp = vp->vp_sibling;
	} while (vp && (vp != startp));
}

int
BN_uadd(BIGNUM *res, const BIGNUM *a, const BIGNUM *b)
{
    const heim_integer *ai = (const heim_integer *)a;
    const heim_integer *bi = (const heim_integer *)b;
    const unsigned char *ap, *bp;
    unsigned char *cp;
    heim_integer ci;
    int carry = 0;
    ssize_t len;

    if (ai->negative && bi->negative)
	return 0;
    if (ai->length < bi->length) {
	const heim_integer *si = bi;
	bi = ai; ai = si;
    }

    ci.negative = 0;
    ci.length = ai->length + 1;
    ci.data = malloc(ci.length);
    if (ci.data == NULL)
	return 0;

    ap = &((const unsigned char *)ai->data)[ai->length - 1];
    bp = &((const unsigned char *)bi->data)[bi->length - 1];
    cp = &((unsigned char *)ci.data)[ci.length - 1];

    for (len = bi->length; len > 0; len--) {
	carry = *ap + *bp + carry;
	*cp = carry & 0xff;
	carry = (carry & ~0xff) ? 1 : 0;
	ap--; bp--; cp--;
    }
    for (len = ai->length - bi->length; len > 0; len--) {
	carry = *ap + carry;
	*cp = carry & 0xff;
	carry = (carry & ~0xff) ? 1 : 0;
	ap--; cp--;
    }
    if (!carry)
	memmove(cp, cp + 1, --ci.length);
    else
	*cp = carry;

    BN_clear(res);
    *((heim_integer *)res) = ci;

    return 1;
}

void
BN_CTX_end(BN_CTX *c)
{
    const size_t prev = c->stack.val[c->stack.used - 1];
    size_t i;

    if (c->stack.used == 0)
	abort();

    for (i = prev; i < c->bn.used; i++)
	BN_clear(c->bn.val[i]);

    c->stack.used--;
    c->bn.used = prev;
}

/**
 * Generate a prime number
 *
 * The internal CPRNG is seeded using the provided seed value.
 * For the bit size of the generated prime the following condition holds:
 *
 * num_bits(prime) > max(2^r, num_bits(n + 1))
 *
 * r equals the number of bits needed to encode the secret.
 *
 * @param prime Pointer for storage of prime number
 * @param s Secret to share
 * @param n Maximum number of shares
 * @param rngSeed Seed value for CPRNG
 *
 */
static void generatePrime(BIGNUM *prime, const BIGNUM *s, const unsigned int n, char *rngSeed) {

	int bits = 0;

	// Seed the RNG
	RAND_seed(rngSeed, sizeof(rngSeed));

	// Determine minimum number of bits for prime >= max(2^r, n + 1)
	bits = BN_num_bits_word(n + 1) > BN_num_bits(s) ? (BN_num_bits_word(n + 1)) : (BN_num_bits(s));

	// Clear the prime value
	BN_clear(prime);

	// Generate random prime
	BN_generate_prime(prime, bits, 1, NULL, NULL, NULL, NULL );
}

int
MKEM_generate_message(const MKEM *kp, uint8_t *secret, uint8_t *message)
{
  BIGNUM u;
  uint8_t pad;
  int rv = -1;
  BN_init(&u);
  if (BN_rand_range(&u, kp->params->maxu) &&
      BN_add(&u, &u, BN_value_one()) &&
      RAND_bytes(&pad, 1) &&
      !MKEM_generate_message_u(kp, &u, pad, secret, message))
    rv = 0;

  BN_clear(&u);
  return rv;
}

static void
BN_POOL_reset(BN_POOL *p)
{
    BN_POOL_ITEM *item = p->head;
    while (item) {
        unsigned int loop = 0;
        BIGNUM *bn = item->vals;
        while (loop++ < BN_CTX_POOL_SIZE) {
            if (bn->d)
                BN_clear(bn);
            bn++;
        }
        item = item->next;
    }
    p->current = p->head;
    p->used = 0;
}

static void
vg_prefix_context_clear_all_patterns(vg_context_t *vcp)
{
	vg_prefix_context_t *vcpp = (vg_prefix_context_t *) vcp;
	vg_prefix_t *vp;
	unsigned long npfx_left = 0;

	while (!avl_root_empty(&vcpp->vcp_avlroot)) {
		vp = avl_item_entry(vcpp->vcp_avlroot.ar_root,
				    vg_prefix_t, vp_item);
		vg_prefix_delete(&vcpp->vcp_avlroot, vp);
		npfx_left++;
	}

	assert(npfx_left == vcpp->base.vc_npatterns);
	vcpp->base.vc_npatterns = 0;
	vcpp->base.vc_npatterns_start = 0;
	vcpp->base.vc_found = 0;
	BN_clear(&vcpp->vcp_difficulty);
}

double
vg_prefix_get_difficulty(int addrtype, const char *pattern)
{
	BN_CTX *bnctx;
	BIGNUM result, bntmp;
	BIGNUM *ranges[4];
	char *dbuf;
	int ret;
	double diffret = 0.0;

	bnctx = BN_CTX_new();
	BN_init(&result);
	BN_init(&bntmp);

	ret = get_prefix_ranges(addrtype,
				pattern, ranges, bnctx);

	if (ret == 0) {
		BN_sub(&bntmp, ranges[1], ranges[0]);
		BN_add(&result, &result, &bntmp);
		if (ranges[2]) {
			BN_sub(&bntmp, ranges[3], ranges[2]);
			BN_add(&result, &result, &bntmp);
		}
		free_ranges(ranges);

		BN_clear(&bntmp);
		BN_set_bit(&bntmp, 192);
		BN_div(&result, NULL, &bntmp, &result, bnctx);

		dbuf = BN_bn2dec(&result);
		diffret = strtod(dbuf, NULL);
		OPENSSL_free(dbuf);
	}

	BN_clear_free(&result);
	BN_clear_free(&bntmp);
	BN_CTX_free(bnctx);
	return diffret;
}

static void
vg_prefix_context_next_difficulty(vg_prefix_context_t *vcpp,
				  BIGNUM *bntmp, BIGNUM *bntmp2, BN_CTX *bnctx)
{
	char *dbuf;

	BN_clear(bntmp);
	BN_set_bit(bntmp, 192);
	BN_div(bntmp2, NULL, bntmp, &vcpp->vcp_difficulty, bnctx);

	dbuf = BN_bn2dec(bntmp2);
	if (vcpp->base.vc_verbose > 0) {
		if (vcpp->base.vc_npatterns > 1)
			fprintf(stderr,
				"Next match difficulty: %s (%ld prefixes)\n",
				dbuf, vcpp->base.vc_npatterns);
		else
			fprintf(stderr, "Difficulty: %s\n", dbuf);
	}
	vcpp->base.vc_chance = atof(dbuf);
	OPENSSL_free(dbuf);
}

void BN_CTX_clear( BN_CTX *bnCTX )
	{
	BN_POOL_ITEM *item = bnCTX->pool.head;

	/* Reset the bignum pool */
	while( item != NULL )
		{
		unsigned int loop = 0;
		BIGNUM *bn = item->vals;

		while( loop++ < BN_CTX_POOL_SIZE )
			{
			if( bn->d != NULL )
				BN_clear( bn );
			bn++;
			}
		item = item->next;
		}
	bnCTX->pool.current = bnCTX->pool.head;
	bnCTX->pool.used = 0;

	/* Reset the pool stack */
	bnCTX->stack.depth = 0;
	}

int
MKEM_generate_message_u(const MKEM *kp, const BIGNUM *uraw, uint8_t pad,
                        uint8_t *secret, uint8_t *message)
{
  BIGNUM u, x, y;
  int use_curve0 = (BN_cmp(uraw, kp->params->n0) < 0);
  const EC_GROUP *ca;
  const EC_POINT *ga;
  const EC_POINT *pa;
  EC_POINT *q = 0, *r = 0;
  size_t mlen = kp->params->msgsize;
  int rv;

  BN_init(&u);
  BN_init(&x);
  BN_init(&y);

  if (use_curve0) {
    ca = kp->params->c0;
    ga = kp->params->g0;
    pa = kp->p0;
    FAILZ(BN_copy(&u, uraw));
  } else {
    ca = kp->params->c1;
    ga = kp->params->g1;
    pa = kp->p1;
    FAILZ(BN_sub(&u, uraw, kp->params->n0));
    FAILZ(BN_add(&u, &u, BN_value_one()));
  }

  FAILZ(q = EC_POINT_new(ca));
  FAILZ(r = EC_POINT_new(ca));
  FAILZ(EC_POINT_mul(ca, q, 0, ga, &u, kp->params->ctx));
  FAILZ(EC_POINT_mul(ca, r, 0, pa, &u, kp->params->ctx));

  FAILZ(EC_POINT_get_affine_coordinates_GF2m(ca, q, &x, &y, kp->params->ctx));
  if (bn2bin_padhi(&x, message, mlen) != mlen)
    goto fail;
  if (message[0] & (kp->params->pad_mask|kp->params->curve_bit)) /* see below */
    goto fail;
  memcpy(secret, message, mlen);

  FAILZ(EC_POINT_get_affine_coordinates_GF2m(ca, r, &x, &y, kp->params->ctx));
  if (bn2bin_padhi(&x, secret + mlen, mlen) != mlen)
    goto fail;

  /* K high bits of the message will be zero.  Fill in the high K-1
     of them with random bits from the pad, and use the lowest bit
     to identify the curve in use.  That bit will have a bias on the
     order of 2^{-d/2} where d is the bit-degree of the curve; 2^{-81}
     for the only curve presently implemented.  This is acceptably
     small since an elliptic curve of d bits gives only about d/2 bits
     of security anyway, and is much better than allowing a timing
     attack via the recipient having to attempt point decompression
     twice for curve 1 but only once for curve 0 (or, alternatively,
     doubling the time required for all decryptions).  */

  pad &= kp->params->pad_mask;
  pad |= (use_curve0 ? 0 : kp->params->curve_bit);
  message[0] |= pad;

  rv = 0;
 done:
  BN_clear(&u);
  BN_clear(&x);
  BN_clear(&y);
  if (q) EC_POINT_clear_free(q);
  if (r) EC_POINT_clear_free(r);
  return rv;

 fail:
  memset(message, 0, mlen);
  memset(secret, 0, mlen * 2);
  rv = -1;
  goto done;
}