int BN_solinas2bn(const BN_SOLINAS *solinas, BIGNUM *bn)
{
	int ret = 0;
	BIGNUM *tmp = NULL;

	if (!solinas || !bn) {
		BNerr(BN_F_BN_SOLINAS2BN, ERR_R_MALLOC_FAILURE);
		return 0;
	}

	if (solinas->b <= 0 || solinas->a <= solinas->b
		|| (solinas->s != 1 && solinas->s != -1)
		|| (solinas->c != 1 && solinas->c != -1)) {
		BNerr(BN_F_BN_SOLINAS2BN, BN_R_INVALID_SOLINAS_PARAMETERS);
		return 0;
	}

	if (!(tmp = BN_new())) {
		BNerr(BN_F_BN_SOLINAS2BN, ERR_R_MALLOC_FAILURE);
		goto end;
	}

	BN_one(tmp);

	if (!BN_lshift(bn, tmp, solinas->a)) {
		BNerr(BN_F_BN_SOLINAS2BN, ERR_R_BN_LIB);
		goto end;
	}

	if (!BN_lshift(tmp, tmp, solinas->b)) {
		BNerr(BN_F_BN_SOLINAS2BN, ERR_R_BN_LIB);
		goto end;
	}

	if (!BN_add_word(tmp, solinas->c)) {
		BNerr(BN_F_BN_SOLINAS2BN, ERR_R_BN_LIB);
		goto end;
	}

	if (solinas->s > 0) {
		if (!BN_add(bn, bn, tmp)) {
			BNerr(BN_F_BN_SOLINAS2BN, ERR_R_BN_LIB);
			goto end;
		}
	} else {
		if (!BN_sub(bn, bn, tmp)) {
			BNerr(BN_F_BN_SOLINAS2BN, ERR_R_BN_LIB);
			goto end;
		}
	}

	/* check if it is a prime */

	ret = 1;
end:
	BN_free(tmp);
	return ret;
}

/* rem != m */
int BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
{
#if 0 /* The old slow way */
	int i, nm, nd;
	BIGNUM *dv;

	if(BN_ucmp(m, d) < 0)
		{ return ((BN_copy(rem, m) == NULL) ? 0 : 1); }

	BN_CTX_start(ctx);
	dv = BN_CTX_get(ctx);

	if(!BN_copy(rem, m)) { goto err; }

	nm = BN_num_bits(rem);
	nd = BN_num_bits(d);
	if(!BN_lshift(dv, d, nm - nd)) { goto err; }
	for(i = nm - nd; i >= 0; i--)
	{
		if(BN_cmp(rem, dv) >= 0)
		{
			if(!BN_sub(rem, rem, dv)) { goto err; }
		}
		if(!BN_rshift1(dv, dv)) { goto err; }
	}
	BN_CTX_end(ctx);
	return (1);
err:
	BN_CTX_end(ctx);
	return (0);
#else
	return (BN_div(NULL, rem, m, d, ctx));
#endif
}

BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w)
  {
  BN_ULONG ret = 0;
  int i, j;

  bn_check_top(a);
  w &= BN_MASK2;

  if (!w)
    /* actually this an error (division by zero) */
    return (BN_ULONG)-1;
  if (a->top == 0)
    return 0;

  /* normalize input (so bn_div_words doesn't complain) */
  j = BN_BITS2 - BN_num_bits_word(w);
  w <<= j;
  if (!BN_lshift(a, a, j))
    return (BN_ULONG)-1;

  for (i=a->top-1; i>=0; i--)
    {
    BN_ULONG l,d;
    
    l=a->d[i];
    d=bn_div_words(ret,l,w);
    ret=(l-((d*w)&BN_MASK2))&BN_MASK2;
    a->d[i]=d;
    }
  if ((a->top > 0) && (a->d[a->top-1] == 0))
    a->top--;
  ret >>= j;
  bn_check_top(a);
  return(ret);
  }

int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d,
	   BN_CTX *ctx)
	{
	int i,nm,nd;
	int ret = 0;
	BIGNUM *D;

	bn_check_top(m);
	bn_check_top(d);
	if (BN_is_zero(d))
		{
		BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO);
		return(0);
		}

	if (BN_ucmp(m,d) < 0)
		{
		if (rem != NULL)
			{ if (BN_copy(rem,m) == NULL) return(0); }
		if (dv != NULL) BN_zero(dv);
		return(1);
		}

	BN_CTX_start(ctx);
	D = BN_CTX_get(ctx);
	if (dv == NULL) dv = BN_CTX_get(ctx);
	if (rem == NULL) rem = BN_CTX_get(ctx);
	if (D == NULL || dv == NULL || rem == NULL)
		goto end;

	nd=BN_num_bits(d);
	nm=BN_num_bits(m);
	if (BN_copy(D,d) == NULL) goto end;
	if (BN_copy(rem,m) == NULL) goto end;

	/* The next 2 are needed so we can do a dv->d[0]|=1 later
	 * since BN_lshift1 will only work once there is a value :-) */
	BN_zero(dv);
	if(bn_wexpand(dv,1) == NULL) goto end;
	dv->top=1;

	if (!BN_lshift(D,D,nm-nd)) goto end;
	for (i=nm-nd; i>=0; i--)
		{
		if (!BN_lshift1(dv,dv)) goto end;
		if (BN_ucmp(rem,D) >= 0)
			{
			dv->d[0]|=1;
			if (!BN_usub(rem,rem,D)) goto end;
			}
/* CAN IMPROVE (and have now :=) */
		if (!BN_rshift1(D,D)) goto end;
		}
	rem->neg=BN_is_zero(rem)?0:m->neg;
	dv->neg=m->neg^d->neg;
	ret = 1;
 end:
	BN_CTX_end(ctx);
	return(ret);
	}

int
test_div(BIO *bp, BN_CTX *ctx)
{
	BIGNUM a, b,c, d, e;
	int i;
	int rc = 1;

	BN_init(&a);
	BN_init(&b);
	BN_init(&c);
	BN_init(&d);
	BN_init(&e);

	for (i = 0; i < num0 + num1; i++) {
		if (i < num1) {
			BN_bntest_rand(&a, 400, 0, 0);
			BN_copy(&b, &a);
			BN_lshift(&a, &a, i);
			BN_add_word(&a, i);
		} else
			BN_bntest_rand(&b, 50 + 3*(i - num1), 0, 0);
		a.neg = rand_neg();
		b.neg = rand_neg();
		BN_div(&d, &c, &a, &b, ctx);
		if (bp != NULL) {
			if (!results) {
				BN_print(bp, &a);
				BIO_puts(bp, " / ");
				BN_print(bp, &b);
				BIO_puts(bp, " - ");
			}
			BN_print(bp, &d);
			BIO_puts(bp, "\n");

			if (!results) {
				BN_print(bp, &a);
				BIO_puts(bp, " % ");
				BN_print(bp, &b);
				BIO_puts(bp, " - ");
			}
			BN_print(bp, &c);
			BIO_puts(bp, "\n");
		}
		BN_mul(&e, &d, &b, ctx);
		BN_add(&d, &e, &c);
		BN_sub(&d, &d, &a);
		if (!BN_is_zero(&d)) {
			fprintf(stderr, "Division test failed!\n");
			rc = 0;
			break;
		}
	}
	BN_free(&a);
	BN_free(&b);
	BN_free(&c);
	BN_free(&d);
	BN_free(&e);
	return (rc);
}

/*
 * \fn hit2hit_key
 *
 * \param hit		128-bit Host Identity Tag
 * \param hit_key	buffer for storing HIT_KEY; should be DHT_VAL_SIZE long
 *
 * \brief Create a HIT_KEY from a HIT by taking the middle 100 bits and adding
 *        padding.
 */
void hit2hit_key(hip_hit *hit, __u8 *hit_key)
{
  BIGNUM *hk = BN_bin2bn((const unsigned char *)hit, HIT_SIZE, NULL);
  BN_lshift(hk, hk, 28);       /* truncate to 100-bit number */
  memset(hit_key, 0, DHT_KEY_SIZE);
  bn2bin_safe(hk, hit_key, 16);       /* lower 28-bits now zeroes */
  BN_free(hk);
}

int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_)
	{
	BIGNUM *a,*b,*c,*d;
	int i;

	b=BN_new();
	c=BN_new();
	d=BN_new();
	BN_one(c);

	if(a_)
	    a=a_;
	else
	    {
	    a=BN_new();
	    BN_bntest_rand(a,200,0,0); /**/
	    a->neg=rand_neg();
	    }
	for (i=0; i<num0; i++)
		{
		BN_lshift(b,a,i+1);
		BN_add(c,c,c);
		if (bp != NULL)
			{
			if (!results)
				{
				BN_print(bp,a);
				BIO_puts(bp," * ");
				BN_print(bp,c);
				BIO_puts(bp," - ");
				}
			BN_print(bp,b);
			BIO_puts(bp,"\n");
			}
		BN_mul(d,a,c,ctx);
		BN_sub(d,d,b);
		if(!BN_is_zero(d))
		    {
		    fprintf(stderr,"Left shift test failed!\n");
		    fprintf(stderr,"a=");
		    BN_print_fp(stderr,a);
		    fprintf(stderr,"\nb=");
		    BN_print_fp(stderr,b);
		    fprintf(stderr,"\nc=");
		    BN_print_fp(stderr,c);
		    fprintf(stderr,"\nd=");
		    BN_print_fp(stderr,d);
		    fprintf(stderr,"\n");
		    return 0;
		    }
		}
	BN_free(a);
	BN_free(b);
	BN_free(c);
	BN_free(d);
	return(1);
	}

extern "C" void Java_java_math_NativeBN_BN_1shift(JNIEnv* env, jclass, jlong r, jlong a, int n) {
  if (!twoValidHandles(env, r, a)) return;
  if (n >= 0) {
    BN_lshift(toBigNum(r), toBigNum(a), n);
  } else {
    BN_rshift(toBigNum(r), toBigNum(a), -n);
  }
  throwExceptionIfNecessary(env);
}

static BIGNUM *euclid(BIGNUM *a, BIGNUM *b)
	{
	BIGNUM *t;
	int shifts=0;

	bn_check_top(a);
	bn_check_top(b);

	/* 0 <= b <= a */
	while (!BN_is_zero(b))
		{
		/* 0 < b <= a */

		if (BN_is_odd(a))
			{
			if (BN_is_odd(b))
				{
				if (!BN_sub(a,a,b)) goto err;
				if (!BN_rshift1(a,a)) goto err;
				if (BN_cmp(a,b) < 0)
					{ t=a; a=b; b=t; }
				}
			else		/* a odd - b even */
				{
				if (!BN_rshift1(b,b)) goto err;
				if (BN_cmp(a,b) < 0)
					{ t=a; a=b; b=t; }
				}
			}
		else			/* a is even */
			{
			if (BN_is_odd(b))
				{
				if (!BN_rshift1(a,a)) goto err;
				if (BN_cmp(a,b) < 0)
					{ t=a; a=b; b=t; }
				}
			else		/* a even - b even */
				{
				if (!BN_rshift1(a,a)) goto err;
				if (!BN_rshift1(b,b)) goto err;
				shifts++;
				}
			}
		/* 0 <= b <= a */
		}

	if (shifts)
		{
		if (!BN_lshift(a,a,shifts)) goto err;
		}
	bn_check_top(a);
	return(a);
err:
	return(NULL);
	}

int test_div(BIO *bp, BN_CTX *ctx)
{
    BIGNUM *a, *b, *c, *d, *e;
    int i;

    a = BN_new();
    b = BN_new();
    c = BN_new();
    d = BN_new();
    e = BN_new();

    for (i = 0; i < num0 + num1; i++) {
        if (i < num1) {
            BN_bntest_rand(a, 400, 0, 0);
            BN_copy(b, a);
            BN_lshift(a, a, i);
            BN_add_word(a, i);
        } else
            BN_bntest_rand(b, 50 + 3 * (i - num1), 0, 0);
        a->neg = rand_neg();
        b->neg = rand_neg();
        BN_div(d, c, a, b, ctx);
        if (bp != NULL) {
            if (!results) {
                BN_print(bp, a);
                BIO_puts(bp, " / ");
                BN_print(bp, b);
                BIO_puts(bp, " - ");
            }
            BN_print(bp, d);
            BIO_puts(bp, "\n");

            if (!results) {
                BN_print(bp, a);
                BIO_puts(bp, " % ");
                BN_print(bp, b);
                BIO_puts(bp, " - ");
            }
            BN_print(bp, c);
            BIO_puts(bp, "\n");
        }
        BN_mul(e, d, b, ctx);
        BN_add(d, e, c);
        BN_sub(d, d, a);
        if (!BN_is_zero(d)) {
            fprintf(stderr, "Division test failed!\n");
            return 0;
        }
    }
    BN_free(a);
    BN_free(b);
    BN_free(c);
    BN_free(d);
    BN_free(e);
    return (1);
}

static RSA *
fermat_question_ask(const RSA *rsa)
{
  BIGNUM
    *a = BN_new(),
    *b = BN_new(),
    *a2 = BN_new(),
    *b2 = BN_new();
  BIGNUM *n = rsa->n;
  BIGNUM
    *tmp = BN_new(),
    *rem = BN_new(),
    *dssdelta = BN_new();
  BN_CTX *ctx = BN_CTX_new();
  RSA *ret = NULL;

  BN_sqrtmod(tmp, rem, n, ctx);
  /* Δ = |p - q| = |a + b - a + b| = |2b| > √N  2⁻¹⁰⁰ */
  /* BN_rshift(dssdelta, tmp, 101); */
  BN_one(dssdelta);
  BN_lshift(dssdelta, dssdelta, BN_num_bits(n) / 4 + 10);

  BN_copy(a, tmp);
  BN_sqr(a2, a, ctx);

  do {
    /* a² += 2a + 1 */
    BN_lshift1(tmp, a);
    BN_uiadd1(tmp);
    BN_add(a2, a2, tmp);
    /* a += 1 */
    BN_uiadd1(a);
    /* b² = a² - N */
    BN_usub(b2, a2, n);
    /* b */
    BN_sqrtmod(b, rem, b2, ctx);
  } while (!BN_is_zero(rem) && BN_cmp(b, dssdelta) < 1);

  if (BN_is_zero(rem)) {
    BN_uadd(a, a, b);
    ret = qa_RSA_recover(rsa, a, ctx);
  }

  BN_CTX_free(ctx);
  BN_free(a);
  BN_free(b);
  BN_free(a2);
  BN_free(b2);
  BN_free(dssdelta);
  BN_free(tmp);
  BN_free(rem);
  return ret;
}

/* BN_mod_lshift variant that may be used if  a  is non-negative
 * and less than  m */
int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
	{
	if (r != a)
		{
		if (BN_copy(r, a) == NULL) return 0;
		}

	while (n > 0)
		{
		int max_shift;
		
		/* 0 < r < m */
		max_shift = BN_num_bits(m) - BN_num_bits(r);
		/* max_shift >= 0 */

		if (max_shift < 0)
			{
			BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED);
			return 0;
			}

		if (max_shift > n)
			max_shift = n;

		if (max_shift)
			{
			if (!BN_lshift(r, r, max_shift)) return 0;
			n -= max_shift;
			}
		else
			{
			if (!BN_lshift1(r, r)) return 0;
			--n;
			}

		/* BN_num_bits(r) <= BN_num_bits(m) */

		if (BN_cmp(r, m) >= 0) 
			{
			if (!BN_sub(r, r, m)) return 0;
			}
		}
	bn_check_top(r);
	
	return 1;
	}

void bu256_bn(BIGNUM *vo, const bu256_t *vi)
{
	BN_zero(vo);

	BIGNUM tmp;
	BN_init(&tmp);

	unsigned int i;
	for (i = 0; i < 8; i++) {
		BN_set_word(&tmp, GUINT32_FROM_LE(vi->dword[i]));
		BN_lshift(&tmp, &tmp, (i * 32));

		BN_add(vo, vo, &tmp);
	}

	BN_free(&tmp);
}

EC_POINT *embed(const polypseud_ctx *ctx, const unsigned char *data, const size_t len) {
   BIGNUM *t1 = BN_bin2bn(data, len, NULL);
   BIGNUM *x = BN_new();
   BN_mod(x, t1, ctx->p, ctx->bn_ctx);

   EC_POINT *point = EC_POINT_new(ctx->ec_group);
   unsigned char counter = 0;
   int success = 0;
   while(!success) {
       success = EC_POINT_set_compressed_coordinates_GFp(ctx->ec_group, point, x, 1, ctx->bn_ctx);
       if(!success) {
           if(counter == 0) {
               BN_lshift(x, x, 8);
           }
           BN_add(x, x, BN_value_one());
       }
   }
   BN_free(x);
   BN_free(t1);
   return point;
}

static ssize_t
get_size(const uint8_t *buf, size_t len, BIGNUM *out)
{
    int sz = -1;

    if (len == 0)
        return 1;

    if (BN_set_word(out, 0) <= 0)
        return -ENOMEM;

    for (size_t i = 0; i < len; i++) {
        if (sz > 0) {
            if (BN_lshift(out, out, 8) <= 0)
                return -ENOMEM;

            if (BN_add_word(out, buf[i]) <= 0)
                return -ENOMEM;
        } else if (sz < 0) {
            if (i == 0) {
                if (IS_ID_SHORT(buf[i]))
                    sz++;
            } else if (IS_ID_LAST(buf[i]))
                sz++;
        } else if (sz == 0) {
            sz = buf[i] & ~BIT8;

            if (IS_LEN_SHORT(buf[i]))
                return BN_set_word(out, sz) > 0 ? 0 : -ENOMEM;

            if (i + 1 == len)
                return sz;
        }
    }

    return sz <= 0 ? 1 : 0;
}

static int test_check_public_exponent(void)
{
    int ret = 0;
    BIGNUM *e = NULL;

    ret = TEST_ptr(e = BN_new())
          /* e is too small */
          && TEST_true(BN_set_word(e, 65535))
          && TEST_false(rsa_check_public_exponent(e))
          /* e is even will fail */
          && TEST_true(BN_set_word(e, 65536))
          && TEST_false(rsa_check_public_exponent(e))
          /* e is ok */
          && TEST_true(BN_set_word(e, 65537))
          && TEST_true(rsa_check_public_exponent(e))
          /* e = 2^256 is too big */
          && TEST_true(BN_lshift(e, BN_value_one(), 256))
          && TEST_false(rsa_check_public_exponent(e))
          /* e = 2^256-1 is odd and in range */
          && TEST_true(BN_sub(e, e, BN_value_one()))
          && TEST_true(rsa_check_public_exponent(e));
    BN_free(e);
    return ret;
}

/* BN_div_no_branch is a special version of BN_div. It does not contain
 * branches that may leak sensitive information.
 */
static int BN_div_no_branch(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, 
	const BIGNUM *divisor, BN_CTX *ctx)
	{
	int norm_shift,i,loop;
	BIGNUM *tmp,wnum,*snum,*sdiv,*res;
	BN_ULONG *resp,*wnump;
	BN_ULONG d0,d1;
	int num_n,div_n;

	bn_check_top(dv);
	bn_check_top(rm);
	/* bn_check_top(num); */ /* 'num' has been checked in BN_div() */
	bn_check_top(divisor);

	if (BN_is_zero(divisor))
		{
		BNerr(BN_F_BN_DIV_NO_BRANCH,BN_R_DIV_BY_ZERO);
		return(0);
		}

	BN_CTX_start(ctx);
	tmp=BN_CTX_get(ctx);
	snum=BN_CTX_get(ctx);
	sdiv=BN_CTX_get(ctx);
	if (dv == NULL)
		res=BN_CTX_get(ctx);
	else	res=dv;
	if (sdiv == NULL || res == NULL) goto err;

	/* First we normalise the numbers */
	norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2);
	if (!(BN_lshift(sdiv,divisor,norm_shift))) goto err;
	sdiv->neg=0;
	norm_shift+=BN_BITS2;
	if (!(BN_lshift(snum,num,norm_shift))) goto err;
	snum->neg=0;

	/* Since we don't know whether snum is larger than sdiv,
	 * we pad snum with enough zeroes without changing its
	 * value. 
	 */
	if (snum->top <= sdiv->top+1) 
		{
		if (bn_wexpand(snum, sdiv->top + 2) == NULL) goto err;
		for (i = snum->top; i < sdiv->top + 2; i++) snum->d[i] = 0;
		snum->top = sdiv->top + 2;
		}
	else
		{
		if (bn_wexpand(snum, snum->top + 1) == NULL) goto err;
		snum->d[snum->top] = 0;
		snum->top ++;
		}

	div_n=sdiv->top;
	num_n=snum->top;
	loop=num_n-div_n;
	/* Lets setup a 'window' into snum
	 * This is the part that corresponds to the current
	 * 'area' being divided */
	wnum.neg   = 0;
	wnum.d     = &(snum->d[loop]);
	wnum.top   = div_n;
	/* only needed when BN_ucmp messes up the values between top and max */
	wnum.dmax  = snum->dmax - loop; /* so we don't step out of bounds */

	/* Get the top 2 words of sdiv */
	/* div_n=sdiv->top; */
	d0=sdiv->d[div_n-1];
	d1=(div_n == 1)?0:sdiv->d[div_n-2];

	/* pointer to the 'top' of snum */
	wnump= &(snum->d[num_n-1]);

	/* Setup to 'res' */
	res->neg= (num->neg^divisor->neg);
	if (!bn_wexpand(res,(loop+1))) goto err;
	res->top=loop-1;
	resp= &(res->d[loop-1]);

	/* space for temp */
	if (!bn_wexpand(tmp,(div_n+1))) goto err;

	/* if res->top == 0 then clear the neg value otherwise decrease
	 * the resp pointer */
	if (res->top == 0)
		res->neg = 0;
	else
		resp--;

	for (i=0; i<loop-1; i++, wnump--, resp--)
		{
		BN_ULONG q,l0;
		/* the first part of the loop uses the top two words of
		 * snum and sdiv to calculate a BN_ULONG q such that
		 * | wnum - sdiv * q | < sdiv */
#if defined(BN_DIV3W) && !defined(OPENSSL_NO_ASM)
//.........这里部分代码省略.........

int RSA_recover_crt_params(RSA *rsa) {
  BN_CTX *ctx;
  BIGNUM *totient, *rem, *multiple, *p_plus_q, *p_minus_q;
  int ok = 0;

  if (rsa->n == NULL || rsa->e == NULL || rsa->d == NULL) {
    OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params, RSA_R_EMPTY_PUBLIC_KEY);
    return 0;
  }

  if (rsa->p || rsa->q || rsa->dmp1 || rsa->dmq1 || rsa->iqmp) {
    OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params,
                      RSA_R_CRT_PARAMS_ALREADY_GIVEN);
    return 0;
  }

  /* This uses the algorithm from section 9B of the RSA paper:
   * http://people.csail.mit.edu/rivest/Rsapaper.pdf */

  ctx = BN_CTX_new();
  if (ctx == NULL) {
    OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params, ERR_R_MALLOC_FAILURE);
    return 0;
  }

  BN_CTX_start(ctx);
  totient = BN_CTX_get(ctx);
  rem = BN_CTX_get(ctx);
  multiple = BN_CTX_get(ctx);
  p_plus_q = BN_CTX_get(ctx);
  p_minus_q = BN_CTX_get(ctx);

  if (totient == NULL || rem == NULL || multiple == NULL || p_plus_q == NULL ||
      p_minus_q == NULL) {
    OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params, ERR_R_MALLOC_FAILURE);
    goto err;
  }

  /* ed-1 is a small multiple of φ(n). */
  if (!BN_mul(totient, rsa->e, rsa->d, ctx) ||
      !BN_sub_word(totient, 1) ||
      /* φ(n) =
       * pq - p - q + 1 =
       * n - (p + q) + 1
       *
       * Thus n is a reasonable estimate for φ(n). So, (ed-1)/n will be very
       * close. But, when we calculate the quotient, we'll be truncating it
       * because we discard the remainder. Thus (ed-1)/multiple will be >= n,
       * which the totient cannot be. So we add one to the estimate.
       *
       * Consider ed-1 as:
       *
       * multiple * (n - (p+q) + 1) =
       * multiple*n - multiple*(p+q) + multiple
       *
       * When we divide by n, the first term becomes multiple and, since
       * multiple and p+q is tiny compared to n, the second and third terms can
       * be ignored. Thus I claim that subtracting one from the estimate is
       * sufficient. */
      !BN_div(multiple, NULL, totient, rsa->n, ctx) ||
      !BN_add_word(multiple, 1) ||
      !BN_div(totient, rem, totient, multiple, ctx)) {
    OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params, ERR_R_BN_LIB);
    goto err;
  }

  if (!BN_is_zero(rem)) {
    OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params, RSA_R_BAD_RSA_PARAMETERS);
    goto err;
  }

  rsa->p = BN_new();
  rsa->q = BN_new();
  rsa->dmp1 = BN_new();
  rsa->dmq1 = BN_new();
  rsa->iqmp = BN_new();
  if (rsa->p == NULL || rsa->q == NULL || rsa->dmp1 == NULL || rsa->dmq1 ==
      NULL || rsa->iqmp == NULL) {
    OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params, ERR_R_MALLOC_FAILURE);
    goto err;
  }

  /* φ(n) = n - (p + q) + 1 =>
   * n - totient + 1 = p + q */
  if (!BN_sub(p_plus_q, rsa->n, totient) ||
      !BN_add_word(p_plus_q, 1) ||
      /* p - q = sqrt((p+q)^2 - 4n) */
      !BN_sqr(rem, p_plus_q, ctx) ||
      !BN_lshift(multiple, rsa->n, 2) ||
      !BN_sub(rem, rem, multiple) ||
      !BN_sqrt(p_minus_q, rem, ctx) ||
      /* q is 1/2 (p+q)-(p-q) */
      !BN_sub(rsa->q, p_plus_q, p_minus_q) ||
      !BN_rshift1(rsa->q, rsa->q) ||
      !BN_div(rsa->p, NULL, rsa->n, rsa->q, ctx) ||
      !BN_mul(multiple, rsa->p, rsa->q, ctx)) {
    OPENSSL_PUT_ERROR(RSA, RSA_recover_crt_params, ERR_R_BN_LIB);
    goto err;
  }

//.........这里部分代码省略.........

int
BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
{
	int ret = 0;
	BIGNUM *Ri, *R;

	BN_CTX_start(ctx);
	if ((Ri = BN_CTX_get(ctx)) == NULL)
		goto err;
	R = &(mont->RR);				/* grab RR as a temp */
	if (!BN_copy(&(mont->N), mod))
		 goto err;				/* Set N */
	mont->N.neg = 0;

#ifdef MONT_WORD
	{
		BIGNUM tmod;
		BN_ULONG buf[2];

		BN_init(&tmod);
		tmod.d = buf;
		tmod.dmax = 2;
		tmod.neg = 0;

		mont->ri = (BN_num_bits(mod) +
		    (BN_BITS2 - 1)) / BN_BITS2 * BN_BITS2;

#if defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32)
		/* Only certain BN_BITS2<=32 platforms actually make use of
		 * n0[1], and we could use the #else case (with a shorter R
		 * value) for the others.  However, currently only the assembler
		 * files do know which is which. */

		BN_zero(R);
		if (!(BN_set_bit(R, 2 * BN_BITS2)))
			goto err;

		tmod.top = 0;
		if ((buf[0] = mod->d[0]))
			tmod.top = 1;
		if ((buf[1] = mod->top > 1 ? mod->d[1] : 0))
			tmod.top = 2;

		if ((BN_mod_inverse_ct(Ri, R, &tmod, ctx)) == NULL)
			goto err;
		if (!BN_lshift(Ri, Ri, 2 * BN_BITS2))
			goto err; /* R*Ri */
		if (!BN_is_zero(Ri)) {
			if (!BN_sub_word(Ri, 1))
				goto err;
		}
		else /* if N mod word size == 1 */
		{
			if (bn_expand(Ri, (int)sizeof(BN_ULONG) * 2) == NULL)
				goto err;
			/* Ri-- (mod double word size) */
			Ri->neg = 0;
			Ri->d[0] = BN_MASK2;
			Ri->d[1] = BN_MASK2;
			Ri->top = 2;
		}
		if (!BN_div_ct(Ri, NULL, Ri, &tmod, ctx))
			goto err;
		/* Ni = (R*Ri-1)/N,
		 * keep only couple of least significant words: */
		mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
		mont->n0[1] = (Ri->top > 1) ? Ri->d[1] : 0;
#else
		BN_zero(R);
		if (!(BN_set_bit(R, BN_BITS2)))
			goto err;	/* R */

		buf[0] = mod->d[0]; /* tmod = N mod word size */
		buf[1] = 0;
		tmod.top = buf[0] != 0 ? 1 : 0;
		/* Ri = R^-1 mod N*/
		if ((BN_mod_inverse_ct(Ri, R, &tmod, ctx)) == NULL)
			goto err;
		if (!BN_lshift(Ri, Ri, BN_BITS2))
			goto err; /* R*Ri */
		if (!BN_is_zero(Ri)) {
			if (!BN_sub_word(Ri, 1))
				goto err;
		}
		else /* if N mod word size == 1 */
		{
			if (!BN_set_word(Ri, BN_MASK2))
				goto err;  /* Ri-- (mod word size) */
		}
		if (!BN_div_ct(Ri, NULL, Ri, &tmod, ctx))
			goto err;
		/* Ni = (R*Ri-1)/N,
		 * keep only least significant word: */
		mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
		mont->n0[1] = 0;
#endif
	}
#else /* !MONT_WORD */
	{ /* bignum version */
		mont->ri = BN_num_bits(&mont->N);
//.........这里部分代码省略.........

static void runtest(const char *json_base_fn, const char *ser_in_fn,
		    const char *block_in_hash, const char *tx_in_hash)
{
	/* read wallet data */
	char *json_fn = test_filename(json_base_fn);
	json_t *wallet = read_json(json_fn);
	assert(wallet != NULL);

	/* read block data containing incoming payment */
	char *fn = test_filename(ser_in_fn);
	void *data;
	size_t data_len;
	assert(bu_read_file(fn, &data, &data_len, 1 * 1024 * 1024) == true);

	struct bp_block block_in;
	bp_block_init(&block_in);
	struct const_buffer buf = { data, data_len };

	assert(deser_bp_block(&block_in, &buf) == true);
	bp_block_calc_sha256(&block_in);

	/* verify block-in data matches expected block-in hash */
	bu256_t check_hash;
	assert(hex_bu256(&check_hash, block_in_hash) == true);

	assert(bu256_equal(&block_in.sha256, &check_hash) == true);

	/* load key that has received an incoming payment */
	struct bp_key key;
	assert(bp_key_init(&key) == true);

	load_json_key(wallet, &key);

	/* load key into keyset */
	struct bp_keyset ks;
	bpks_init(&ks);

	assert(bpks_add(&ks, &key) == true);

	/* find key matches in block */
	parr *matches;
	matches = bp_block_match(&block_in, &ks);
	assert(matches != NULL);
	assert(matches->len == 1);

	struct bp_block_match *match = parr_idx(matches, 0);
	assert(match->n == 1);			/* match 2nd tx, index 1 */

	/* get matching transaction */
	struct bp_tx *tx = parr_idx(block_in.vtx, match->n);
	bp_tx_calc_sha256(tx);

	/* verify txid matches expected */
	char tx_hexstr[BU256_STRSZ];
	bu256_hex(tx_hexstr, &tx->sha256);
	assert(strcmp(tx_hexstr, tx_in_hash) == 0);

	/* verify mask matches 2nd txout (1 << 1) */
	BIGNUM tmp_mask;
	BN_init(&tmp_mask);
	BN_one(&tmp_mask);
	BN_lshift(&tmp_mask, &tmp_mask, 1);
	assert(BN_cmp(&tmp_mask, &match->mask) == 0);

	/* build merkle tree, tx's branch */
	parr *mtree = bp_block_merkle_tree(&block_in);
	assert(mtree != NULL);
	parr *mbranch = bp_block_merkle_branch(&block_in, mtree, match->n);
	assert(mbranch != NULL);

	/* verify merkle branch for tx matches expected */
	bu256_t mrk_check;
	bp_check_merkle_branch(&mrk_check, &tx->sha256, mbranch, match->n);
	assert(bu256_equal(&mrk_check, &block_in.hashMerkleRoot) == true);

	/* release resources */
	parr_free(mtree, true);
	parr_free(mbranch, true);
	BN_clear_free(&tmp_mask);
	parr_free(matches, true);
	bpks_free(&ks);
	bp_key_free(&key);
	bp_block_free(&block_in);
	json_decref(wallet);
	free(data);
	free(fn);
	free(json_fn);
}