自学教程：C++ BN_mod_exp_mont函数代码示例

static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,                   const BIGNUM *a1_odd, int k, BN_CTX *ctx,                   BN_MONT_CTX *mont){    if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w := w^a1_odd mod a */        return -1;    if (BN_is_one(w))        return 0;               /* probably prime */    if (BN_cmp(w, a1) == 0)        return 0;               /* w == -1 (mod a), 'a' is probably prime */    while (--k) {        if (!BN_mod_mul(w, w, w, a, ctx)) /* w := w^2 mod a */            return -1;        if (BN_is_one(w))            return 1;           /* 'a' is composite, otherwise a previous 'w'                                 * would have been == -1 (mod 'a') */        if (BN_cmp(w, a1) == 0)            return 0;           /* w == -1 (mod a), 'a' is probably prime */    }    /*     * If we get here, 'w' is the (a-1)/2-th power of the original 'w', and     * it is neither -1 nor +1 -- so 'a' cannot be prime     */    bn_check_top(w);    return 1;}

void do_mul_exp(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *c, BN_CTX *ctx)	{	int i,k;	double tm;	long num;	BN_MONT_CTX m;	memset(&m,0,sizeof(m));	num=BASENUM;	for (i=0; i<NUM_SIZES; i++)		{		BN_rand(a,sizes[i],1,0);		BN_rand(b,sizes[i],1,0);		BN_rand(c,sizes[i],1,1);		BN_mod(a,a,c,ctx);		BN_mod(b,b,c,ctx);		BN_MONT_CTX_set(&m,c,ctx);		Time_F(START);		for (k=0; k<num; k++)			BN_mod_exp_mont(r,a,b,c,ctx,&m);		tm=Time_F(STOP);		printf("mul %4d ^ %4d %% %d -> %8.3fms %5.1f/n",sizes[i],sizes[i],sizes[i],tm*1000.0/num,tm*mul_c[i]/num);		num/=7;		if (num <= 0) num=1;		}	}

static int bn_blinding_create_param(BN_BLINDING *b, BN_CTX *ctx,                                    const BN_MONT_CTX *mont_ctx) {  int retry_counter = 32;  do {    if (!BN_rand_range(b->A, b->mod)) {      OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);      return 0;    }    int no_inverse;    if (BN_mod_inverse_ex(b->Ai, &no_inverse, b->A, b->mod, ctx) == NULL) {      /* this should almost never happen for good RSA keys */      if (no_inverse) {        if (retry_counter-- == 0) {          OPENSSL_PUT_ERROR(RSA, RSA_R_TOO_MANY_ITERATIONS);          return 0;        }        ERR_clear_error();      } else {        OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);        return 0;      }    } else {      break;    }  } while (1);  if (!BN_mod_exp_mont(b->A, b->A, b->e, b->mod, ctx, mont_ctx)) {    OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);    return 0;  }  return 1;}

static int dh_bn_mod_exp(DH *dh, BIGNUM *r, BIGNUM *a, const BIGNUM *p,			const BIGNUM *m, BN_CTX *ctx,			BN_MONT_CTX *m_ctx)	{	if (a->top == 1)		{		BN_ULONG A = a->d[0];		return BN_mod_exp_mont_word(r,A,p,m,ctx,m_ctx);		}	else		return BN_mod_exp_mont(r,a,p,m,ctx,m_ctx);	}

static int dh_bn_mod_exp(const DH *dh, BIGNUM *r,                         const BIGNUM *a, const BIGNUM *p,                         const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx){    /*     * If a is only one word long and constant time is false, use the faster     * exponenentiation function.     */    if (a->top == 1 && ((dh->flags & DH_FLAG_NO_EXP_CONSTTIME) != 0)) {        BN_ULONG A = a->d[0];        return BN_mod_exp_mont_word(r, A, p, m, ctx, m_ctx);    } else        return BN_mod_exp_mont(r, a, p, m, ctx, m_ctx);}

static int bn_blinding_create_param(BN_BLINDING *b, const RSA *rsa, BN_CTX *ctx) {  int retry_counter = 32;  do {    if (!BN_rand_range(b->A, rsa->n)) {      OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);      return 0;    }    /* `BN_from_montgomery` + `BN_mod_inverse_no_branch` is equivalent to, but     * more efficient than, `BN_mod_inverse_no_branch` + `BN_to_montgomery`. */    if (!BN_from_montgomery(b->Ai, b->A, rsa->mont_n, ctx)) {      return 0;    }    assert(BN_get_flags(b->A, BN_FLG_CONSTTIME));    int no_inverse;    if (BN_mod_inverse_no_branch(b->Ai, &no_inverse, b->Ai, rsa->n, ctx) ==        NULL) {      /* this should almost never happen for good RSA keys */      if (no_inverse) {        if (retry_counter-- == 0) {          OPENSSL_PUT_ERROR(RSA, RSA_R_TOO_MANY_ITERATIONS);          return 0;        }        ERR_clear_error();      } else {        OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);        return 0;      }    } else {      break;    }  } while (1);  if (!BN_mod_exp_mont(b->A, b->A, rsa->e, rsa->n, ctx, rsa->mont_n)) {    OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);    return 0;  }  if (!BN_to_montgomery(b->A, b->A, rsa->mont_n, ctx)) {    OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);    return 0;  }  return 1;}

static int ec_field_inverse_mod_ord(const EC_GROUP *group, BIGNUM *r,                                    const BIGNUM *x, BN_CTX *ctx){    BIGNUM *e = NULL;    BN_CTX *new_ctx = NULL;    int ret = 0;    if (group->mont_data == NULL)        return 0;    if (ctx == NULL && (ctx = new_ctx = BN_CTX_secure_new()) == NULL)        return 0;    BN_CTX_start(ctx);    if ((e = BN_CTX_get(ctx)) == NULL)        goto err;    /*-     * We want inverse in constant time, therefore we utilize the fact     * order must be prime and use Fermats Little Theorem instead.     */    if (!BN_set_word(e, 2))        goto err;    if (!BN_sub(e, group->order, e))        goto err;    /*-     * Exponent e is public.     * No need for scatter-gather or BN_FLG_CONSTTIME.     */    if (!BN_mod_exp_mont(r, x, e, group->order, ctx, group->mont_data))        goto err;    ret = 1; err:    if (ctx != NULL)        BN_CTX_end(ctx);    BN_CTX_free(new_ctx);    return ret;}

int BN_enhanced_miller_rabin_primality_test(    enum bn_primality_result_t *out_result, const BIGNUM *w, int iterations,    BN_CTX *ctx, BN_GENCB *cb) {  /* Enhanced Miller-Rabin is only valid on odd integers greater than 3. */  if (!BN_is_odd(w) || BN_cmp_word(w, 3) <= 0) {    OPENSSL_PUT_ERROR(BN, BN_R_INVALID_INPUT);    return 0;  }  if (iterations == BN_prime_checks) {    iterations = BN_prime_checks_for_size(BN_num_bits(w));  }  int ret = 0;  BN_MONT_CTX *mont = NULL;  BN_CTX_start(ctx);  BIGNUM *w1 = BN_CTX_get(ctx);  if (w1 == NULL ||      !BN_copy(w1, w) ||      !BN_sub_word(w1, 1)) {    goto err;  }  /* Write w1 as m*2^a (Steps 1 and 2). */  int a = 0;  while (!BN_is_bit_set(w1, a)) {    a++;  }  BIGNUM *m = BN_CTX_get(ctx);  if (m == NULL ||      !BN_rshift(m, w1, a)) {    goto err;  }  BIGNUM *b = BN_CTX_get(ctx);  BIGNUM *g = BN_CTX_get(ctx);  BIGNUM *z = BN_CTX_get(ctx);  BIGNUM *x = BN_CTX_get(ctx);  BIGNUM *x1 = BN_CTX_get(ctx);  if (b == NULL ||      g == NULL ||      z == NULL ||      x == NULL ||      x1 == NULL) {    goto err;  }  /* Montgomery setup for computations mod A */  mont = BN_MONT_CTX_new();  if (mont == NULL ||      !BN_MONT_CTX_set(mont, w, ctx)) {    goto err;  }  /* The following loop performs in inner iteration of the Enhanced Miller-Rabin   * Primality test (Step 4). */  for (int i = 1; i <= iterations; i++) {    /* Step 4.1-4.2 */    if (!BN_rand_range_ex(b, 2, w1)) {      goto err;    }    /* Step 4.3-4.4 */    if (!BN_gcd(g, b, w, ctx)) {      goto err;    }    if (BN_cmp_word(g, 1) > 0) {      *out_result = bn_composite;      ret = 1;      goto err;    }    /* Step 4.5 */    if (!BN_mod_exp_mont(z, b, m, w, ctx, mont)) {      goto err;    }    /* Step 4.6 */    if (BN_is_one(z) || BN_cmp(z, w1) == 0) {      goto loop;    }    /* Step 4.7 */    for (int j = 1; j < a; j++) {      if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) {        goto err;      }      if (BN_cmp(z, w1) == 0) {        goto loop;      }      if (BN_is_one(z)) {        goto composite;      }    }    /* Step 4.8-4.9 */    if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx)) {      goto err;//.........这里部分代码省略.........

/* * test_exp_mod_zero tests that x**0 mod 1 == 0. It returns zero on success. */static int test_exp_mod_zero(){    BIGNUM *a = NULL, *p = NULL, *m = NULL;    BIGNUM *r = NULL;    BN_ULONG one_word = 1;    BN_CTX *ctx = BN_CTX_new();    int ret = 1, failed = 0;    m = BN_new();    if (!m)        goto err;    BN_one(m);    a = BN_new();    if (!a)        goto err;    BN_one(a);    p = BN_new();    if (!p)        goto err;    BN_zero(p);    r = BN_new();    if (!r)        goto err;    if (!BN_rand(a, 1024, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY))        goto err;    if (!BN_mod_exp(r, a, p, m, ctx))        goto err;    if (!a_is_zero_mod_one("BN_mod_exp", r, a))        failed = 1;    if (!BN_mod_exp_recp(r, a, p, m, ctx))        goto err;    if (!a_is_zero_mod_one("BN_mod_exp_recp", r, a))        failed = 1;    if (!BN_mod_exp_simple(r, a, p, m, ctx))        goto err;    if (!a_is_zero_mod_one("BN_mod_exp_simple", r, a))        failed = 1;    if (!BN_mod_exp_mont(r, a, p, m, ctx, NULL))        goto err;    if (!a_is_zero_mod_one("BN_mod_exp_mont", r, a))        failed = 1;    if (!BN_mod_exp_mont_consttime(r, a, p, m, ctx, NULL)) {        goto err;    }    if (!a_is_zero_mod_one("BN_mod_exp_mont_consttime", r, a))        failed = 1;    /*     * A different codepath exists for single word multiplication     * in non-constant-time only.     */    if (!BN_mod_exp_mont_word(r, one_word, p, m, ctx, NULL))        goto err;    if (!BN_is_zero(r)) {        fprintf(stderr, "BN_mod_exp_mont_word failed:/n");        fprintf(stderr, "1 ** 0 mod 1 = r (should be 0)/n");        fprintf(stderr, "r = ");        BN_print_fp(stderr, r);        fprintf(stderr, "/n");        return 0;    }    ret = failed; err:    BN_free(r);    BN_free(a);    BN_free(p);    BN_free(m);    BN_CTX_free(ctx);    return ret;}

static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx){    BIGNUM *r1, *m1, *vrfy, *r2, *m[RSA_MAX_PRIME_NUM - 2];    int ret = 0, i, ex_primes = 0, smooth = 0;    RSA_PRIME_INFO *pinfo;    BN_CTX_start(ctx);    r1 = BN_CTX_get(ctx);    r2 = BN_CTX_get(ctx);    m1 = BN_CTX_get(ctx);    vrfy = BN_CTX_get(ctx);    if (vrfy == NULL)        goto err;    if (rsa->version == RSA_ASN1_VERSION_MULTI        && ((ex_primes = sk_RSA_PRIME_INFO_num(rsa->prime_infos)) <= 0             || ex_primes > RSA_MAX_PRIME_NUM - 2))        goto err;    if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) {        BIGNUM *factor = BN_new();        if (factor == NULL)            goto err;        /*         * Make sure BN_mod_inverse in Montgomery initialization uses the         * BN_FLG_CONSTTIME flag         */        if (!(BN_with_flags(factor, rsa->p, BN_FLG_CONSTTIME),              BN_MONT_CTX_set_locked(&rsa->_method_mod_p, rsa->lock,                                     factor, ctx))            || !(BN_with_flags(factor, rsa->q, BN_FLG_CONSTTIME),                 BN_MONT_CTX_set_locked(&rsa->_method_mod_q, rsa->lock,                                        factor, ctx))) {            BN_free(factor);            goto err;        }        for (i = 0; i < ex_primes; i++) {            pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);            BN_with_flags(factor, pinfo->r, BN_FLG_CONSTTIME);            if (!BN_MONT_CTX_set_locked(&pinfo->m, rsa->lock, factor, ctx)) {                BN_free(factor);                goto err;            }        }        /*         * We MUST free |factor| before any further use of the prime factors         */        BN_free(factor);        smooth = (ex_primes == 0)                 && (rsa->meth->bn_mod_exp == BN_mod_exp_mont)                 && (BN_num_bits(rsa->q) == BN_num_bits(rsa->p));    }    if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)        if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,                                    rsa->n, ctx))            goto err;    if (smooth) {        /*         * Conversion from Montgomery domain, a.k.a. Montgomery reduction,         * accepts values in [0-m*2^w) range. w is m's bit width rounded up         * to limb width. So that at the very least if |I| is fully reduced,         * i.e. less than p*q, we can count on from-to round to perform         * below modulo operations on |I|. Unlike BN_mod it's constant time.         */        if (/* m1 = I moq q */            !bn_from_mont_fixed_top(m1, I, rsa->_method_mod_q, ctx)            || !bn_to_mont_fixed_top(m1, m1, rsa->_method_mod_q, ctx)            /* m1 = m1^dmq1 mod q */            || !BN_mod_exp_mont_consttime(m1, m1, rsa->dmq1, rsa->q, ctx,                                          rsa->_method_mod_q)            /* r1 = I mod p */            || !bn_from_mont_fixed_top(r1, I, rsa->_method_mod_p, ctx)            || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx)            /* r1 = r1^dmp1 mod p */            || !BN_mod_exp_mont_consttime(r1, r1, rsa->dmp1, rsa->p, ctx,                                          rsa->_method_mod_p)            /* r1 = (r1 - m1) mod p */            /*             * bn_mod_sub_fixed_top is not regular modular subtraction,             * it can tolerate subtrahend to be larger than modulus, but             * not bit-wise wider. This makes up for uncommon q>p case,             * when |m1| can be larger than |rsa->p|.             */            || !bn_mod_sub_fixed_top(r1, r1, m1, rsa->p)            /* r1 = r1 * iqmp mod p */            || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx)            || !bn_mul_mont_fixed_top(r1, r1, rsa->iqmp, rsa->_method_mod_p,                                      ctx)            /* r0 = r1 * q + m1 */            || !bn_mul_fixed_top(r0, r1, rsa->q, ctx)            || !bn_mod_add_fixed_top(r0, r0, m1, rsa->n))            goto err;//.........这里部分代码省略.........

int rsa_default_private_transform(RSA *rsa, uint8_t *out, const uint8_t *in,                                  size_t len) {  if (rsa->n == NULL || rsa->d == NULL) {    OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING);    return 0;  }  BIGNUM *f, *result;  BN_CTX *ctx = NULL;  unsigned blinding_index = 0;  BN_BLINDING *blinding = NULL;  int ret = 0;  ctx = BN_CTX_new();  if (ctx == NULL) {    goto err;  }  BN_CTX_start(ctx);  f = BN_CTX_get(ctx);  result = BN_CTX_get(ctx);  if (f == NULL || result == NULL) {    OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);    goto err;  }  if (BN_bin2bn(in, len, f) == NULL) {    goto err;  }  if (BN_ucmp(f, rsa->n) >= 0) {    // Usually the padding functions would catch this.    OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE);    goto err;  }  if (!freeze_private_key(rsa, ctx)) {    OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);    goto err;  }  const int do_blinding = (rsa->flags & RSA_FLAG_NO_BLINDING) == 0;  if (rsa->e == NULL && do_blinding) {    // We cannot do blinding or verification without |e|, and continuing without    // those countermeasures is dangerous. However, the Java/Android RSA API    // requires support for keys where only |d| and |n| (and not |e|) are known.    // The callers that require that bad behavior set |RSA_FLAG_NO_BLINDING|.    OPENSSL_PUT_ERROR(RSA, RSA_R_NO_PUBLIC_EXPONENT);    goto err;  }  if (do_blinding) {    blinding = rsa_blinding_get(rsa, &blinding_index, ctx);    if (blinding == NULL) {      OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);      goto err;    }    if (!BN_BLINDING_convert(f, blinding, rsa->e, rsa->mont_n, ctx)) {      goto err;    }  }  if (rsa->p != NULL && rsa->q != NULL && rsa->e != NULL && rsa->dmp1 != NULL &&      rsa->dmq1 != NULL && rsa->iqmp != NULL) {    if (!mod_exp(result, f, rsa, ctx)) {      goto err;    }  } else if (!BN_mod_exp_mont_consttime(result, f, rsa->d_fixed, rsa->n, ctx,                                        rsa->mont_n)) {    goto err;  }  // Verify the result to protect against fault attacks as described in the  // 1997 paper "On the Importance of Checking Cryptographic Protocols for  // Faults" by Dan Boneh, Richard A. DeMillo, and Richard J. Lipton. Some  // implementations do this only when the CRT is used, but we do it in all  // cases. Section 6 of the aforementioned paper describes an attack that  // works when the CRT isn't used. That attack is much less likely to succeed  // than the CRT attack, but there have likely been improvements since 1997.  //  // This check is cheap assuming |e| is small; it almost always is.  if (rsa->e != NULL) {    BIGNUM *vrfy = BN_CTX_get(ctx);    if (vrfy == NULL ||        !BN_mod_exp_mont(vrfy, result, rsa->e, rsa->n, ctx, rsa->mont_n) ||        !BN_equal_consttime(vrfy, f)) {      OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);      goto err;    }  }  if (do_blinding &&      !BN_BLINDING_invert(result, blinding, rsa->mont_n, ctx)) {    goto err;  }  // The computation should have left |result| as a maximally-wide number, so  // that it and serializing does not leak information about the magnitude of//.........这里部分代码省略.........

//.........这里部分代码省略.........            for (k=0; k<=n; k++)            {                /* obtain "SEED + offset + k" by incrementing: */                for (i=SHA_DIGEST_LENGTH-1; i >= 0; i--)                {                    buf[i]++;                    if (buf[i] != 0) break;                }                EVP_Digest(buf,SHA_DIGEST_LENGTH,md,NULL,HASH, NULL);                /* step 8 */                if (!BN_bin2bn(md,SHA_DIGEST_LENGTH,r0))                    goto err;                if (!BN_lshift(r0,r0,160*k)) goto err;                if (!BN_add(W,W,r0)) goto err;            }            /* more of step 8 */            if (!BN_mask_bits(W,bits-1)) goto err;            if (!BN_copy(X,W)) goto err;            if (!BN_add(X,X,test)) goto err;            /* step 9 */            if (!BN_lshift1(r0,q)) goto err;            if (!BN_mod(c,X,r0,ctx)) goto err;            if (!BN_sub(r0,c,BN_value_one())) goto err;            if (!BN_sub(p,X,r0)) goto err;            /* step 10 */            if (BN_cmp(p,test) >= 0)            {                /* step 11 */                r = BN_is_prime_fasttest_ex(p, DSS_prime_checks,                                            ctx, 1, cb);                if (r > 0)                    goto end; /* found it */                if (r != 0)                    goto err;            }            /* step 13 */            counter++;            /* "offset = offset + n + 1" */            /* step 14 */            if (counter >= 4096) break;        }    }end:    if(!BN_GENCB_call(cb, 2, 1))        goto err;    /* We now need to generate g */    /* Set r0=(p-1)/q */    if (!BN_sub(test,p,BN_value_one())) goto err;    if (!BN_div(r0,NULL,test,q,ctx)) goto err;    if (!BN_set_word(test,h)) goto err;    if (!BN_MONT_CTX_set(mont,p,ctx)) goto err;    for (;;)    {        /* g=test^r0%p */        if (!BN_mod_exp_mont(g,test,r0,p,ctx,mont)) goto err;        if (!BN_is_one(g)) break;        if (!BN_add(test,test,BN_value_one())) goto err;        h++;    }    if(!BN_GENCB_call(cb, 3, 1))        goto err;    ok=1;err:    if (ok)    {        if(ret->p) BN_free(ret->p);        if(ret->q) BN_free(ret->q);        if(ret->g) BN_free(ret->g);        ret->p=BN_dup(p);        ret->q=BN_dup(q);        ret->g=BN_dup(g);        if (ret->p == NULL || ret->q == NULL || ret->g == NULL)        {            ok=0;            goto err;        }        if (seed_in != NULL) memcpy(seed_in,seed,20);        if (counter_ret != NULL) *counter_ret=counter;        if (h_ret != NULL) *h_ret=h;    }    if(ctx)    {        BN_CTX_end(ctx);        BN_CTX_free(ctx);    }    if (mont != NULL) BN_MONT_CTX_free(mont);    return ok;}

static int dsa_bn_mod_exp(DSA *dsa, BIGNUM *r, BIGNUM *a, const BIGNUM *p,				const BIGNUM *m, BN_CTX *ctx,				BN_MONT_CTX *m_ctx){	return BN_mod_exp_mont(r, a, p, m, ctx, m_ctx);}

static int dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig,		  DSA *dsa)	{	BN_CTX *ctx;	BIGNUM u1,u2,t1;	BN_MONT_CTX *mont=NULL;	int ret = -1;	if (!dsa->p || !dsa->q || !dsa->g)		{		DSAerr(DSA_F_DSA_DO_VERIFY,DSA_R_MISSING_PARAMETERS);		return -1;		}	if (BN_num_bits(dsa->q) != 160)		{		DSAerr(DSA_F_DSA_DO_VERIFY,DSA_R_BAD_Q_VALUE);		return -1;		}	if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS)		{		DSAerr(DSA_F_DSA_DO_VERIFY,DSA_R_MODULUS_TOO_LARGE);		return -1;		}	BN_init(&u1);	BN_init(&u2);	BN_init(&t1);	if ((ctx=BN_CTX_new()) == NULL) goto err;	if (BN_is_zero(sig->r) || sig->r->neg || BN_ucmp(sig->r, dsa->q) >= 0)		{		ret = 0;		goto err;		}	if (BN_is_zero(sig->s) || sig->s->neg || BN_ucmp(sig->s, dsa->q) >= 0)		{		ret = 0;		goto err;		}	/* Calculate W = inv(S) mod Q	 * save W in u2 */	if ((BN_mod_inverse(&u2,sig->s,dsa->q,ctx)) == NULL) goto err;	/* save M in u1 */	if (BN_bin2bn(dgst,dgst_len,&u1) == NULL) goto err;	/* u1 = M * w mod q */	if (!BN_mod_mul(&u1,&u1,&u2,dsa->q,ctx)) goto err;	/* u2 = r * w mod q */	if (!BN_mod_mul(&u2,sig->r,&u2,dsa->q,ctx)) goto err;	if (dsa->flags & DSA_FLAG_CACHE_MONT_P)		{		mont = BN_MONT_CTX_set_locked(					(BN_MONT_CTX **)&dsa->method_mont_p,					CRYPTO_LOCK_DSA, dsa->p, ctx);		if (!mont)			goto err;		}#if 0	{	BIGNUM t2;	BN_init(&t2);	/* v = ( g^u1 * y^u2 mod p ) mod q */	/* let t1 = g ^ u1 mod p */	if (!BN_mod_exp_mont(&t1,dsa->g,&u1,dsa->p,ctx,mont)) goto err;	/* let t2 = y ^ u2 mod p */	if (!BN_mod_exp_mont(&t2,dsa->pub_key,&u2,dsa->p,ctx,mont)) goto err;	/* let u1 = t1 * t2 mod p */	if (!BN_mod_mul(&u1,&t1,&t2,dsa->p,ctx)) goto err_bn;	BN_free(&t2);	}	/* let u1 = u1 mod q */	if (!BN_mod(&u1,&u1,dsa->q,ctx)) goto err;#else	{	if (!dsa->meth->dsa_mod_exp(dsa, &t1,dsa->g,&u1,dsa->pub_key,&u2,						dsa->p,ctx,mont)) goto err;	/* BN_copy(&u1,&t1); */	/* let u1 = u1 mod q */	if (!BN_mod(&u1,&t1,dsa->q,ctx)) goto err;	}#endif	/* V is now in u1.  If the signature is correct, it will be	 * equal to R. */	ret=(BN_ucmp(&u1, sig->r) == 0);	err:	if (ret != 1) DSAerr(DSA_F_DSA_DO_VERIFY,ERR_R_BN_LIB);	if (ctx != NULL) BN_CTX_free(ctx);	BN_free(&u1);	BN_free(&u2);	BN_free(&t1);//.........这里部分代码省略.........

BN_BLINDING *BN_BLINDING_create_param(    BN_BLINDING *b, const BIGNUM *e, BIGNUM *m, BN_CTX *ctx,    const BN_MONT_CTX *mont) {  int retry_counter = 32;  BN_BLINDING *ret = NULL;  if (b == NULL) {    ret = BN_BLINDING_new(NULL, NULL, m);  } else {    ret = b;  }  if (ret == NULL) {    goto err;  }  if (ret->A == NULL && (ret->A = BN_new()) == NULL) {    goto err;  }  if (ret->Ai == NULL && (ret->Ai = BN_new()) == NULL) {    goto err;  }  if (e != NULL) {    BN_free(ret->e);    ret->e = BN_dup(e);  }  if (ret->e == NULL) {    goto err;  }  if (mont != NULL) {    ret->mont = mont;  }  do {    if (!BN_rand_range(ret->A, ret->mod)) {      goto err;    }    int no_inverse;    if (BN_mod_inverse_ex(ret->Ai, &no_inverse, ret->A, ret->mod, ctx) == NULL) {      /* this should almost never happen for good RSA keys */      if (no_inverse) {        if (retry_counter-- == 0) {          OPENSSL_PUT_ERROR(RSA, RSA_R_TOO_MANY_ITERATIONS);          goto err;        }        ERR_clear_error();      } else {        goto err;      }    } else {      break;    }  } while (1);  if (!BN_mod_exp_mont(ret->A, ret->A, ret->e, ret->mod, ctx, ret->mont)) {    goto err;  }  return ret;err:  if (b == NULL) {    BN_BLINDING_free(ret);    ret = NULL;  }  return ret;}

static int dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig,		  DSA *dsa)	{	BN_CTX *ctx;	BIGNUM u1,u2,t1;	BN_MONT_CTX *mont=NULL;	int ret = -1;	if ((ctx=BN_CTX_new()) == NULL) goto err;	BN_init(&u1);	BN_init(&u2);	BN_init(&t1);	if (BN_is_zero(sig->r) || sig->r->neg || BN_ucmp(sig->r, dsa->q) >= 0)		{		ret = 0;		goto err;		}	if (BN_is_zero(sig->s) || sig->s->neg || BN_ucmp(sig->s, dsa->q) >= 0)		{		ret = 0;		goto err;		}	/* Calculate W = inv(S) mod Q	 * save W in u2 */	if ((BN_mod_inverse(&u2,sig->s,dsa->q,ctx)) == NULL) goto err;	/* save M in u1 */	if (BN_bin2bn(dgst,dgst_len,&u1) == NULL) goto err;	/* u1 = M * w mod q */	if (!BN_mod_mul(&u1,&u1,&u2,dsa->q,ctx)) goto err;	/* u2 = r * w mod q */	if (!BN_mod_mul(&u2,sig->r,&u2,dsa->q,ctx)) goto err;	if ((dsa->method_mont_p == NULL) && (dsa->flags & DSA_FLAG_CACHE_MONT_P))		{		if ((dsa->method_mont_p=(char *)BN_MONT_CTX_new()) != NULL)			if (!BN_MONT_CTX_set((BN_MONT_CTX *)dsa->method_mont_p,				dsa->p,ctx)) goto err;		}	mont=(BN_MONT_CTX *)dsa->method_mont_p;#if 0	{	BIGNUM t2;	BN_init(&t2);	/* v = ( g^u1 * y^u2 mod p ) mod q */	/* let t1 = g ^ u1 mod p */	if (!BN_mod_exp_mont(&t1,dsa->g,&u1,dsa->p,ctx,mont)) goto err;	/* let t2 = y ^ u2 mod p */	if (!BN_mod_exp_mont(&t2,dsa->pub_key,&u2,dsa->p,ctx,mont)) goto err;	/* let u1 = t1 * t2 mod p */	if (!BN_mod_mul(&u1,&t1,&t2,dsa->p,ctx)) goto err_bn;	BN_free(&t2);	}	/* let u1 = u1 mod q */	if (!BN_mod(&u1,&u1,dsa->q,ctx)) goto err;#else	{	if (!dsa->meth->dsa_mod_exp(dsa, &t1,dsa->g,&u1,dsa->pub_key,&u2,						dsa->p,ctx,mont)) goto err;	/* BN_copy(&u1,&t1); */	/* let u1 = u1 mod q */	if (!BN_mod(&u1,&t1,dsa->q,ctx)) goto err;	}#endif	/* V is now in u1.  If the signature is correct, it will be	 * equal to R. */	ret=(BN_ucmp(&u1, sig->r) == 0);	err:	if (ret != 1) DSAerr(DSA_F_DSA_DO_VERIFY,ERR_R_BN_LIB);	if (ctx != NULL) BN_CTX_free(ctx);	BN_free(&u1);	BN_free(&u2);	BN_free(&t1);	return(ret);	}

int main(int argc, char *argv[]){    BN_CTX *ctx;    BIO *out = NULL;    int i, ret;    unsigned char c;    BIGNUM *r_mont, *r_mont_const, *r_recp, *r_simple, *a, *b, *m;    RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_rand may fail, and we                                           * don't even check its return                                           * value (which we should) */    ERR_load_BN_strings();    ctx = BN_CTX_new();    if (ctx == NULL)        EXIT(1);    r_mont = BN_new();    r_mont_const = BN_new();    r_recp = BN_new();    r_simple = BN_new();    a = BN_new();    b = BN_new();    m = BN_new();    if ((r_mont == NULL) || (r_recp == NULL) || (a == NULL) || (b == NULL))        goto err;    out = BIO_new(BIO_s_file());    if (out == NULL)        EXIT(1);    BIO_set_fp(out, stdout, BIO_NOCLOSE);    for (i = 0; i < 200; i++) {        RAND_bytes(&c, 1);        c = (c % BN_BITS) - BN_BITS2;        BN_rand(a, NUM_BITS + c, 0, 0);        RAND_bytes(&c, 1);        c = (c % BN_BITS) - BN_BITS2;        BN_rand(b, NUM_BITS + c, 0, 0);        RAND_bytes(&c, 1);        c = (c % BN_BITS) - BN_BITS2;        BN_rand(m, NUM_BITS + c, 0, 1);        BN_mod(a, a, m, ctx);        BN_mod(b, b, m, ctx);        ret = BN_mod_exp_mont(r_mont, a, b, m, ctx, NULL);        if (ret <= 0) {            printf("BN_mod_exp_mont() problems/n");            ERR_print_errors(out);            EXIT(1);        }        ret = BN_mod_exp_recp(r_recp, a, b, m, ctx);        if (ret <= 0) {            printf("BN_mod_exp_recp() problems/n");            ERR_print_errors(out);            EXIT(1);        }        ret = BN_mod_exp_simple(r_simple, a, b, m, ctx);        if (ret <= 0) {            printf("BN_mod_exp_simple() problems/n");            ERR_print_errors(out);            EXIT(1);        }        ret = BN_mod_exp_mont_consttime(r_mont_const, a, b, m, ctx, NULL);        if (ret <= 0) {            printf("BN_mod_exp_mont_consttime() problems/n");            ERR_print_errors(out);            EXIT(1);        }        if (BN_cmp(r_simple, r_mont) == 0            && BN_cmp(r_simple, r_recp) == 0            && BN_cmp(r_simple, r_mont_const) == 0) {            printf(".");            fflush(stdout);        } else {            if (BN_cmp(r_simple, r_mont) != 0)                printf("/nsimple and mont results differ/n");            if (BN_cmp(r_simple, r_mont_const) != 0)                printf("/nsimple and mont const time results differ/n");            if (BN_cmp(r_simple, r_recp) != 0)                printf("/nsimple and recp results differ/n");            printf("a (%3d) = ", BN_num_bits(a));            BN_print(out, a);            printf("/nb (%3d) = ", BN_num_bits(b));            BN_print(out, b);            printf("/nm (%3d) = ", BN_num_bits(m));            BN_print(out, m);            printf("/nsimple   =");            BN_print(out, r_simple);            printf("/nrecp     =");            BN_print(out, r_recp);//.........这里部分代码省略.........

//.........这里部分代码省略.........			for (k=0; k<=n; k++)				{				/* obtain "SEED + offset + k" by incrementing: */				for (i=SHA_DIGEST_LENGTH-1; i >= 0; i--)					{					buf[i]++;					if (buf[i] != 0) break;					}				EVP_Digest(buf,SHA_DIGEST_LENGTH,md,NULL,HASH, NULL);				/* step 8 */				if (!BN_bin2bn(md,SHA_DIGEST_LENGTH,r0))					goto err;				if (!BN_lshift(r0,r0,160*k)) goto err;				if (!BN_add(W,W,r0)) goto err;				}			/* more of step 8 */			if (!BN_mask_bits(W,bits-1)) goto err;			if (!BN_copy(X,W)) goto err;			if (!BN_add(X,X,test)) goto err;			/* step 9 */			if (!BN_lshift1(r0,q)) goto err;			if (!BN_mod(c,X,r0,ctx)) goto err;			if (!BN_sub(r0,c,BN_value_one())) goto err;			if (!BN_sub(p,X,r0)) goto err;			/* step 10 */			if (BN_cmp(p,test) >= 0)				{				/* step 11 */				r = BN_is_prime_fasttest(p, DSS_prime_checks, callback, ctx3, cb_arg, 1);				if (r > 0)						goto end; /* found it */				if (r != 0)					goto err;				}			/* step 13 */			counter++;			/* "offset = offset + n + 1" */			/* step 14 */			if (counter >= 4096) break;			}		}end:	if (callback != NULL) callback(2,1,cb_arg);	/* We now need to generate g */	/* Set r0=(p-1)/q */	if (!BN_sub(test,p,BN_value_one())) goto err;	if (!BN_div(r0,NULL,test,q,ctx)) goto err;	if (!BN_set_word(test,h)) goto err;	if (!BN_MONT_CTX_set(mont,p,ctx)) goto err;	for (;;)		{		/* g=test^r0%p */		if (!BN_mod_exp_mont(g,test,r0,p,ctx,mont)) goto err;		if (!BN_is_one(g)) break;		if (!BN_add(test,test,BN_value_one())) goto err;		h++;		}	if (callback != NULL) callback(3,1,cb_arg);	ok=1;err:	if (!ok)		{		if (ret != NULL) DSA_free(ret);		}	else		{		ret->p=BN_dup(p);		ret->q=BN_dup(q);		ret->g=BN_dup(g);		if (ret->p == NULL || ret->q == NULL || ret->g == NULL)			{			ok=0;			goto err;			}		if ((m > 1) && (seed_in != NULL)) memcpy(seed_in,seed,20);		if (counter_ret != NULL) *counter_ret=counter;		if (h_ret != NULL) *h_ret=h;		}	if (ctx != NULL) BN_CTX_free(ctx);	if (ctx2 != NULL)		{		BN_CTX_end(ctx2);		BN_CTX_free(ctx2);		}	if (ctx3 != NULL) BN_CTX_free(ctx3);	if (mont != NULL) BN_MONT_CTX_free(mont);	return(ok?ret:NULL);	}

/* generates ElGamal key pair. returns 0 when generation went ok, and -1 if error occured. 'bits' is the number of bits in p; it should not be too low (at least 512 is recommended, 1024 is more realistic number. you can use precomputed p,g pairs; set bits to the ordinal of the precomputed combination (see table above). generator is either 2 or 5. public_key and secret_key will be malloc()ed and contain keys */int eg_keypair (int bits, int generator, char **public_key, char **secret_key){    BIGNUM       *p, *g, *t1, *t2, *key, *pbk;    BN_CTX       *ctx2;    BN_MONT_CTX  *mont;    char         *buf1, *buf2, *buf3, *buf4, buf[8];    int          rc;    // create things needed for work    ctx2 = BN_CTX_new ();         if (ctx2 == NULL) return -1;    t1   = BN_new ();             if (t1 == NULL)   return -1;    t2   = BN_new ();             if (t2 == NULL)   return -1;    g    = BN_new ();             if (g == NULL)    return -1;    key  = BN_new ();             if (key == NULL)  return -1;    pbk  = BN_new ();             if (pbk == NULL)  return -1;    mont = BN_MONT_CTX_new ();    if (mont == NULL) return -1;    if (bits < 32)    {        if (bits > sizeof(precomp)/sizeof(precomp[0])-1) return -1;        p = NULL;        rc = BN_hex2bn (&p, precomp[bits].prime);        if (rc == 0) return -1;        // put generator into bignum        BN_set_word (g, precomp[bits].generator);    }    else    {        // set values which will be used for checking when generating proper prime        if (generator == 2)        {            BN_set_word (t1,24);            BN_set_word (t2,11);        }        else if (generator == 5)        {            BN_set_word (t1,10);            BN_set_word (t2,3);            /* BN_set_word(t3,7); just have to miss             * out on these ones :-( */        }        else            goto err;            // generate proper prime        p = BN_generate_prime (NULL, bits, 1, t1, t2, NULL, NULL);        if (p == NULL) goto err;        // put generator into bignum        BN_set_word (g, generator);    }    // create random private key    if (!BN_rand (key, BN_num_bits (p)-1, 0, 0)) goto err;    // create public part of the key    BN_MONT_CTX_set (mont, p, ctx2);    if (!BN_mod_exp_mont (pbk, g, key, p, ctx2, mont)) goto err;    // p, g, key, pbk are ready. secret key: p,g:key, public key: p,g:pbk    if (bits < 32)    {        snprintf1 (buf, sizeof(buf), "%d", bits);        buf1 = strdup (buf);    }    else    {        buf1 = BN_bn2hex (p);    }    buf2 = BN_bn2hex (key);    buf3 = BN_bn2hex (pbk);    buf4 = BN_bn2hex (g);    *secret_key = malloc (strlen(buf1) + strlen(buf2) + strlen(buf4) + 4);    *public_key = malloc (strlen(buf1) + strlen(buf3) + strlen(buf4) + 4);    strcpy (*secret_key, buf1);    if (bits >= 32)    {        strcat (*secret_key, ",");        strcat (*secret_key, buf4);    }    strcat (*secret_key, ":");    strcat (*secret_key, buf2);        strcpy (*public_key, buf1);    if (bits >= 32)    {        strcat (*public_key, ",");        strcat (*public_key, buf4);    }    strcat (*public_key, ":");    strcat (*public_key, buf3);    memset (buf2, 0, strlen (buf2));//.........这里部分代码省略.........

static intdh_bn_mod_exp(const DH *dh, BIGNUM *r, const BIGNUM *a, const BIGNUM *p,    const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx){	return BN_mod_exp_mont(r, a, p, m, ctx, m_ctx);}

int RSA_verify_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,                   const uint8_t *in, size_t in_len, int padding) {  if (rsa->n == NULL || rsa->e == NULL) {    OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING);    return 0;  }  const unsigned rsa_size = RSA_size(rsa);  BIGNUM *f, *result;  int r = -1;  if (max_out < rsa_size) {    OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);    return 0;  }  if (in_len != rsa_size) {    OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);    return 0;  }  if (!check_modulus_and_exponent_sizes(rsa)) {    return 0;  }  BN_CTX *ctx = BN_CTX_new();  if (ctx == NULL) {    return 0;  }  int ret = 0;  uint8_t *buf = NULL;  BN_CTX_start(ctx);  f = BN_CTX_get(ctx);  result = BN_CTX_get(ctx);  if (f == NULL || result == NULL) {    OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);    goto err;  }  if (padding == RSA_NO_PADDING) {    buf = out;  } else {    /* Allocate a temporary buffer to hold the padded plaintext. */    buf = OPENSSL_malloc(rsa_size);    if (buf == NULL) {      OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);      goto err;    }  }  if (BN_bin2bn(in, in_len, f) == NULL) {    goto err;  }  if (BN_ucmp(f, rsa->n) >= 0) {    OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);    goto err;  }  if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) ||      !BN_mod_exp_mont(result, f, rsa->e, rsa->n, ctx, rsa->mont_n)) {    goto err;  }  if (!BN_bn2bin_padded(buf, rsa_size, result)) {    OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);    goto err;  }  switch (padding) {    case RSA_PKCS1_PADDING:      r = RSA_padding_check_PKCS1_type_1(out, rsa_size, buf, rsa_size);      break;    case RSA_NO_PADDING:      r = rsa_size;      break;    default:      OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);      goto err;  }  if (r < 0) {    OPENSSL_PUT_ERROR(RSA, RSA_R_PADDING_CHECK_FAILED);  } else {    *out_len = r;    ret = 1;  }err:  BN_CTX_end(ctx);  BN_CTX_free(ctx);  if (buf != out) {    OPENSSL_free(buf);  }  return ret;}

/* * Refer to FIPS 186-4 C.3.2 Enhanced Miller-Rabin Probabilistic Primality Test. * OR C.3.1 Miller-Rabin Probabilistic Primality Test (if enhanced is zero). * The Step numbers listed in the code refer to the enhanced case. * * if enhanced is set, then status returns one of the following: *     BN_PRIMETEST_PROBABLY_PRIME *     BN_PRIMETEST_COMPOSITE_WITH_FACTOR *     BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME * if enhanced is zero, then status returns either *     BN_PRIMETEST_PROBABLY_PRIME or *     BN_PRIMETEST_COMPOSITE * * returns 0 if there was an error, otherwise it returns 1. */int bn_miller_rabin_is_prime(const BIGNUM *w, int iterations, BN_CTX *ctx,                             BN_GENCB *cb, int enhanced, int *status){    int i, j, a, ret = 0;    BIGNUM *g, *w1, *w3, *x, *m, *z, *b;    BN_MONT_CTX *mont = NULL;    /* w must be odd */    if (!BN_is_odd(w))        return 0;    BN_CTX_start(ctx);    g = BN_CTX_get(ctx);    w1 = BN_CTX_get(ctx);    w3 = BN_CTX_get(ctx);    x = BN_CTX_get(ctx);    m = BN_CTX_get(ctx);    z = BN_CTX_get(ctx);    b = BN_CTX_get(ctx);    if (!(b != NULL            /* w1 := w - 1 */            && BN_copy(w1, w)            && BN_sub_word(w1, 1)            /* w3 := w - 3 */            && BN_copy(w3, w)            && BN_sub_word(w3, 3)))        goto err;    /* check w is larger than 3, otherwise the random b will be too small */    if (BN_is_zero(w3) || BN_is_negative(w3))        goto err;    /* (Step 1) Calculate largest integer 'a' such that 2^a divides w-1 */    a = 1;    while (!BN_is_bit_set(w1, a))        a++;    /* (Step 2) m = (w-1) / 2^a */    if (!BN_rshift(m, w1, a))        goto err;    /* Montgomery setup for computations mod a */    mont = BN_MONT_CTX_new();    if (mont == NULL || !BN_MONT_CTX_set(mont, w, ctx))        goto err;    if (iterations == BN_prime_checks)        iterations = BN_prime_checks_for_size(BN_num_bits(w));    /* (Step 4) */    for (i = 0; i < iterations; ++i) {        /* (Step 4.1) obtain a Random string of bits b where 1 < b < w-1 */        if (!BN_priv_rand_range(b, w3) || !BN_add_word(b, 2)) /* 1 < b < w-1 */            goto err;        if (enhanced) {            /* (Step 4.3) */            if (!BN_gcd(g, b, w, ctx))                goto err;            /* (Step 4.4) */            if (!BN_is_one(g)) {                *status = BN_PRIMETEST_COMPOSITE_WITH_FACTOR;                ret = 1;                goto err;            }        }        /* (Step 4.5) z = b^m mod w */        if (!BN_mod_exp_mont(z, b, m, w, ctx, mont))            goto err;        /* (Step 4.6) if (z = 1 or z = w-1) */        if (BN_is_one(z) || BN_cmp(z, w1) == 0)            goto outer_loop;        /* (Step 4.7) for j = 1 to a-1 */        for (j = 1; j < a ; ++j) {            /* (Step 4.7.1 - 4.7.2) x = z. z = x^2 mod w */            if (!BN_copy(x, z) || !BN_mod_mul(z, x, x, w, ctx))                goto err;            /* (Step 4.7.3) */            if (BN_cmp(z, w1) == 0)                goto outer_loop;            /* (Step 4.7.4) */            if (BN_is_one(z))                goto composite;        }        /* At this point z = b^((w-1)/2) mod w *///.........这里部分代码省略.........

//.........这里部分代码省略.........					{					seed[i]++;					if (seed[i] != 0)						break;					}				if (!EVP_Digest(seed, seed_len, md ,NULL, evpmd,									NULL))					goto err;				/* step 8 */				if (!BN_bin2bn(md, mdsize, r0))					goto err;				if (!BN_lshift(r0,r0,(mdsize << 3)*k)) goto err;				if (!BN_add(W,W,r0)) goto err;				}			/* more of step 8 */			if (!BN_mask_bits(W,L-1)) goto err;			if (!BN_copy(X,W)) goto err;			if (!BN_add(X,X,test)) goto err;			/* step 9 */			if (!BN_lshift1(r0,q)) goto err;			if (!BN_mod(c,X,r0,ctx)) goto err;			if (!BN_sub(r0,c,BN_value_one())) goto err;			if (!BN_sub(p,X,r0)) goto err;			/* step 10 */			if (BN_cmp(p,test) >= 0)				{				/* step 11 */				r = BN_is_prime_fasttest_ex(p, DSS_prime_checks,						ctx, 1, cb);				if (r > 0)						goto end; /* found it */				if (r != 0)					goto err;				}			/* step 13 */			counter++;			/* "offset = offset + n + 1" */			/* step 14 */			if (counter >= 4096) break;			}		}end:	if(!BN_GENCB_call(cb, 2, 1))		goto err;	/* We now need to generate g */	/* Set r0=(p-1)/q */	if (!BN_sub(test,p,BN_value_one())) goto err;	if (!BN_div(r0,NULL,test,q,ctx)) goto err;	if (!BN_set_word(test,h)) goto err;	if (!BN_MONT_CTX_set(mont,p,ctx)) goto err;	for (;;)		{		/* g=test^r0%p */		if (!BN_mod_exp_mont(g,test,r0,p,ctx,mont)) goto err;		if (!BN_is_one(g)) break;		if (!BN_add(test,test,BN_value_one())) goto err;		h++;		}	if(!BN_GENCB_call(cb, 3, 1))		goto err;	ok=1;err:	if (ok == 1)		{		if(ret->p) BN_free(ret->p);		if(ret->q) BN_free(ret->q);		if(ret->g) BN_free(ret->g);		ret->p=BN_dup(p);		ret->q=BN_dup(q);		ret->g=BN_dup(g);		if (ret->p == NULL || ret->q == NULL || ret->g == NULL)			{			ok=-1;			goto err;			}		if (counter_ret != NULL) *counter_ret=counter;		if (h_ret != NULL) *h_ret=h;		}	if (seed)		OPENSSL_free(seed);	if(ctx)		{		BN_CTX_end(ctx);		BN_CTX_free(ctx);		}	if (mont != NULL) BN_MONT_CTX_free(mont);	return ok;	}

int rsa_default_encrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,                        const uint8_t *in, size_t in_len, int padding) {  const unsigned rsa_size = RSA_size(rsa);  BIGNUM *f, *result;  uint8_t *buf = NULL;  BN_CTX *ctx = NULL;  int i, ret = 0;  if (max_out < rsa_size) {    OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);    return 0;  }  if (!check_modulus_and_exponent_sizes(rsa)) {    return 0;  }  ctx = BN_CTX_new();  if (ctx == NULL) {    goto err;  }  BN_CTX_start(ctx);  f = BN_CTX_get(ctx);  result = BN_CTX_get(ctx);  buf = OPENSSL_malloc(rsa_size);  if (!f || !result || !buf) {    OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);    goto err;  }  switch (padding) {    case RSA_PKCS1_PADDING:      i = RSA_padding_add_PKCS1_type_2(buf, rsa_size, in, in_len);      break;    case RSA_PKCS1_OAEP_PADDING:      /* Use the default parameters: SHA-1 for both hashes and no label. */      i = RSA_padding_add_PKCS1_OAEP_mgf1(buf, rsa_size, in, in_len,                                          NULL, 0, NULL, NULL);      break;    case RSA_NO_PADDING:      i = RSA_padding_add_none(buf, rsa_size, in, in_len);      break;    default:      OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);      goto err;  }  if (i <= 0) {    goto err;  }  if (BN_bin2bn(buf, rsa_size, f) == NULL) {    goto err;  }  if (BN_ucmp(f, rsa->n) >= 0) {    /* usually the padding functions would catch this */    OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);    goto err;  }  if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) ||      !BN_mod_exp_mont(result, f, rsa->e, rsa->n, ctx, rsa->mont_n)) {    goto err;  }  /* put in leading 0 bytes if the number is less than the length of the   * modulus */  if (!BN_bn2bin_padded(out, rsa_size, result)) {    OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);    goto err;  }  *out_len = rsa_size;  ret = 1;err:  if (ctx != NULL) {    BN_CTX_end(ctx);    BN_CTX_free(ctx);  }  if (buf != NULL) {    OPENSSL_cleanse(buf, rsa_size);    OPENSSL_free(buf);  }  return ret;}

//.........这里部分代码省略.........            return 1;        }        c=(c%BN_BITS)-BN_BITS2;        BN_rand(b,NUM_BITS+c,0,0);        if(errno==ENOMEM)        {            return 1;        }        RAND_bytes(&c,1);        if(errno==ENOMEM)        {            return 1;        }        c=(c%BN_BITS)-BN_BITS2;        BN_rand(m,NUM_BITS+c,0,1);        if(errno==ENOMEM)        {            return 1;        }        BN_mod(a,a,m,ctx);        if(errno==ENOMEM)        {            return 1;        }        BN_mod(b,b,m,ctx);        if(errno==ENOMEM)        {            return 1;        }        ret=BN_mod_exp_mont(r_mont,a,b,m,ctx,NULL);        if (ret <= 0)        {            if(errno==ENOMEM)            {                return 1;            }            fprintf(stdout,"BN_mod_exp_mont() problems/n");            ERR_print_errors(out);            if(errno==ENOMEM)            {                return 1;            }            return 1;        }        ret=BN_mod_exp_recp(r_recp,a,b,m,ctx);        if (ret <= 0)        {            if(errno==ENOMEM)            {                return 1;            }            fprintf(stdout,"BN_mod_exp_recp() problems/n");            ERR_print_errors(out);            if(errno==ENOMEM)            {                return 1;            }            return 1;        }        ret=BN_mod_exp_simple(r_simple,a,b,m,ctx);

int rsa_default_private_transform(RSA *rsa, uint8_t *out, const uint8_t *in,                                  size_t len) {  BIGNUM *f, *result;  BN_CTX *ctx = NULL;  unsigned blinding_index = 0;  BN_BLINDING *blinding = NULL;  int ret = 0;  ctx = BN_CTX_new();  if (ctx == NULL) {    goto err;  }  BN_CTX_start(ctx);  f = BN_CTX_get(ctx);  result = BN_CTX_get(ctx);  if (f == NULL || result == NULL) {    OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);    goto err;  }  if (BN_bin2bn(in, len, f) == NULL) {    goto err;  }  if (BN_ucmp(f, rsa->n) >= 0) {    /* Usually the padding functions would catch this. */    OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);    goto err;  }  if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx)) {    OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);    goto err;  }  /* We cannot do blinding or verification without |e|, and continuing without   * those countermeasures is dangerous. However, the Java/Android RSA API   * requires support for keys where only |d| and |n| (and not |e|) are known.   * The callers that require that bad behavior set |RSA_FLAG_NO_BLINDING|. */  int disable_security = (rsa->flags & RSA_FLAG_NO_BLINDING) && rsa->e == NULL;  if (!disable_security) {    /* Keys without public exponents must have blinding explicitly disabled to     * be used. */    if (rsa->e == NULL) {      OPENSSL_PUT_ERROR(RSA, RSA_R_NO_PUBLIC_EXPONENT);      goto err;    }    blinding = rsa_blinding_get(rsa, &blinding_index, ctx);    if (blinding == NULL) {      OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);      goto err;    }    if (!BN_BLINDING_convert(f, blinding, rsa->e, rsa->mont_n, ctx)) {      goto err;    }  }  if (rsa->p != NULL && rsa->q != NULL && rsa->e != NULL && rsa->dmp1 != NULL &&      rsa->dmq1 != NULL && rsa->iqmp != NULL) {    if (!mod_exp(result, f, rsa, ctx)) {      goto err;    }  } else {    BIGNUM local_d;    BIGNUM *d = NULL;    BN_init(&local_d);    d = &local_d;    BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);    if (!BN_mod_exp_mont_consttime(result, f, d, rsa->n, ctx, rsa->mont_n)) {      goto err;    }  }  /* Verify the result to protect against fault attacks as described in the   * 1997 paper "On the Importance of Checking Cryptographic Protocols for   * Faults" by Dan Boneh, Richard A. DeMillo, and Richard J. Lipton. Some   * implementations do this only when the CRT is used, but we do it in all   * cases. Section 6 of the aforementioned paper describes an attack that   * works when the CRT isn't used. That attack is much less likely to succeed   * than the CRT attack, but there have likely been improvements since 1997.   *   * This check is cheap assuming |e| is small; it almost always is. */  if (!disable_security) {    BIGNUM *vrfy = BN_CTX_get(ctx);    if (vrfy == NULL ||        !BN_mod_exp_mont(vrfy, result, rsa->e, rsa->n, ctx, rsa->mont_n) ||        !BN_equal_consttime(vrfy, f)) {      OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);      goto err;    }    if (!BN_BLINDING_invert(result, blinding, rsa->mont_n, ctx)) {      goto err;    }  }//.........这里部分代码省略.........

static int test_mod_exp(int round){    BN_CTX *ctx;    unsigned char c;    int ret = 0;    BIGNUM *r_mont = NULL;    BIGNUM *r_mont_const = NULL;    BIGNUM *r_recp = NULL;    BIGNUM *r_simple = NULL;    BIGNUM *a = NULL;    BIGNUM *b = NULL;    BIGNUM *m = NULL;    if (!TEST_ptr(ctx = BN_CTX_new()))        goto err;    if (!TEST_ptr(r_mont = BN_new())        || !TEST_ptr(r_mont_const = BN_new())        || !TEST_ptr(r_recp = BN_new())        || !TEST_ptr(r_simple = BN_new())        || !TEST_ptr(a = BN_new())        || !TEST_ptr(b = BN_new())        || !TEST_ptr(m = BN_new()))        goto err;    RAND_bytes(&c, 1);    c = (c % BN_BITS) - BN_BITS2;    BN_rand(a, NUM_BITS + c, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY);    RAND_bytes(&c, 1);    c = (c % BN_BITS) - BN_BITS2;    BN_rand(b, NUM_BITS + c, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY);    RAND_bytes(&c, 1);    c = (c % BN_BITS) - BN_BITS2;    BN_rand(m, NUM_BITS + c, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD);    if (!TEST_true(BN_mod(a, a, m, ctx))        || !TEST_true(BN_mod(b, b, m, ctx))        || !TEST_true(BN_mod_exp_mont(r_mont, a, b, m, ctx, NULL))        || !TEST_true(BN_mod_exp_recp(r_recp, a, b, m, ctx))        || !TEST_true(BN_mod_exp_simple(r_simple, a, b, m, ctx))        || !TEST_true(BN_mod_exp_mont_consttime(r_mont_const, a, b, m, ctx, NULL)))        goto err;    if (!TEST_BN_eq(r_simple, r_mont)        || !TEST_BN_eq(r_simple, r_recp)        || !TEST_BN_eq(r_simple, r_mont_const)) {        if (BN_cmp(r_simple, r_mont) != 0)            TEST_info("simple and mont results differ");        if (BN_cmp(r_simple, r_mont_const) != 0)            TEST_info("simple and mont const time results differ");        if (BN_cmp(r_simple, r_recp) != 0)            TEST_info("simple and recp results differ");        BN_print_var(a);        BN_print_var(b);        BN_print_var(m);        BN_print_var(r_simple);        BN_print_var(r_recp);        BN_print_var(r_mont);        BN_print_var(r_mont_const);        goto err;    }    ret = 1; err:    BN_free(r_mont);    BN_free(r_mont_const);    BN_free(r_recp);    BN_free(r_simple);    BN_free(a);    BN_free(b);    BN_free(m);    BN_CTX_free(ctx);    return ret;}

//.........这里部分代码省略.........			/* more of step 8 */			if (!BN_mask_bits(W, bits - 1))				goto err;			if (!BN_copy(X, W))				goto err;			if (!BN_add(X, X, test))				goto err;			/* step 9 */			if (!BN_lshift1(r0, q))				goto err;			if (!BN_mod(c, X, r0, ctx))				goto err;			if (!BN_sub(r0, c, BN_value_one()))				goto err;			if (!BN_sub(p, X, r0))				goto err;			/* step 10 */			if (BN_cmp(p, test) >= 0) {				/* step 11 */				r = BN_is_prime_fasttest_ex(p, DSS_prime_checks,				    ctx, 1, cb);				if (r > 0)					goto end; /* found it */				if (r != 0)					goto err;			}			/* step 13 */			counter++;			/* "offset = offset + n + 1" */			/* step 14 */			if (counter >= 4096)				break;		}	}end:	if (!BN_GENCB_call(cb, 2, 1))		goto err;	/* We now need to generate g */	/* Set r0=(p-1)/q */	if (!BN_sub(test, p, BN_value_one()))		goto err;	if (!BN_div(r0, NULL, test, q, ctx))		goto err;	if (!BN_set_word(test, h))		goto err;	if (!BN_MONT_CTX_set(mont, p, ctx))		goto err;	for (;;) {		/* g=test^r0%p */		if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont))			goto err;		if (!BN_is_one(g))			break;		if (!BN_add(test, test, BN_value_one()))			goto err;		h++;	}	if (!BN_GENCB_call(cb, 3, 1))		goto err;	ok = 1;err:	if (ok) {		if (ret->p)			BN_free(ret->p);		if (ret->q)			BN_free(ret->q);		if (ret->g)			BN_free(ret->g);		ret->p = BN_dup(p);		ret->q = BN_dup(q);		ret->g = BN_dup(g);		if (ret->p == NULL || ret->q == NULL || ret->g == NULL) {			ok = 0;			goto err;		}		if (counter_ret != NULL)			*counter_ret = counter;		if (h_ret != NULL)			*h_ret = h;		if (seed_out)			memcpy(seed_out, seed, qsize);	}	if (ctx) {		BN_CTX_end(ctx);		BN_CTX_free(ctx);	}	if (mont != NULL)		BN_MONT_CTX_free(mont);	return ok;}

/* * test_mod_exp_zero tests that x**0 mod 1 == 0. It returns zero on success. */static int test_mod_exp_zero(void){    BIGNUM *a = NULL, *p = NULL, *m = NULL;    BIGNUM *r = NULL;    BN_ULONG one_word = 1;    BN_CTX *ctx = BN_CTX_new();    int ret = 1, failed = 0;    if (!TEST_ptr(m = BN_new())        || !TEST_ptr(a = BN_new())        || !TEST_ptr(p = BN_new())        || !TEST_ptr(r = BN_new()))        goto err;    BN_one(m);    BN_one(a);    BN_zero(p);    if (!TEST_true(BN_rand(a, 1024, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY)))        goto err;    if (!TEST_true(BN_mod_exp(r, a, p, m, ctx)))        goto err;    if (!TEST_true(a_is_zero_mod_one("BN_mod_exp", r, a)))        failed = 1;    if (!TEST_true(BN_mod_exp_recp(r, a, p, m, ctx)))        goto err;    if (!TEST_true(a_is_zero_mod_one("BN_mod_exp_recp", r, a)))        failed = 1;    if (!TEST_true(BN_mod_exp_simple(r, a, p, m, ctx)))        goto err;    if (!TEST_true(a_is_zero_mod_one("BN_mod_exp_simple", r, a)))        failed = 1;    if (!TEST_true(BN_mod_exp_mont(r, a, p, m, ctx, NULL)))        goto err;    if (!TEST_true(a_is_zero_mod_one("BN_mod_exp_mont", r, a)))        failed = 1;    if (!TEST_true(BN_mod_exp_mont_consttime(r, a, p, m, ctx, NULL)))        goto err;    if (!TEST_true(a_is_zero_mod_one("BN_mod_exp_mont_consttime", r, a)))        failed = 1;    /*     * A different codepath exists for single word multiplication     * in non-constant-time only.     */    if (!TEST_true(BN_mod_exp_mont_word(r, one_word, p, m, ctx, NULL)))        goto err;    if (!TEST_BN_eq_zero(r)) {        TEST_error("BN_mod_exp_mont_word failed: "                   "1 ** 0 mod 1 = r (should be 0)");        BN_print_var(r);        goto err;    }    ret = !failed; err:    BN_free(r);    BN_free(a);    BN_free(p);    BN_free(m);    BN_CTX_free(ctx);    return ret;}