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

/* * pr_fact - print the factors of a number * * Print the factors of the number, from the lowest to the highest. * A factor will be printed multiple times if it divides the value * multiple times. * * Factors are printed with leading tabs. */static voidpr_fact(BIGNUM *val){	const ubig *fact;	/* The factor found. */	/* Firewall - catch 0 and 1. */	if (BN_is_zero(val))	/* Historical practice; 0 just exits. */		exit(0);	if (BN_is_one(val)) {		printf("1: 1/n");		return;	}	/* Factor value. */	if (hflag) {		fputs("0x", stdout);		BN_print_fp(stdout, val);	} else		BN_print_dec_fp(stdout, val);	putchar(':');	for (fact = &prime[0]; !BN_is_one(val); ++fact) {		/* Look for the smallest factor. */		do {			if (BN_mod_word(val, (BN_ULONG)*fact) == 0)				break;		} while (++fact <= pr_limit);		/* Watch for primes larger than the table. */		if (fact > pr_limit) {#ifdef HAVE_OPENSSL			BIGNUM *bnfact;			bnfact = BN_new();			BN_set_word(bnfact, *(fact - 1));			if (!BN_sqr(bnfact, bnfact, ctx))				errx(1, "error in BN_sqr()");			if (BN_cmp(bnfact, val) > 0 ||			    BN_is_prime(val, PRIME_CHECKS,					NULL, NULL, NULL) == 1)				pr_print(val);			else				pollard_pminus1(val);#else			pr_print(val);#endif			break;		}		/* Divide factor out until none are left. */		do {			printf(hflag ? " 0x%lx" : " %lu", *fact);			BN_div_word(val, (BN_ULONG)*fact);		} while (BN_mod_word(val, (BN_ULONG)*fact) == 0);		/* Let the user know we're doing something. */		fflush(stdout);	}	putchar('/n');}

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 );	}

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 test_lehmer_thm(void){  BIGNUM    *v = BN_new(),    *v2 = BN_new(),    *h = BN_new(),    *n = BN_new(),    *p = BN_new(),    *q = BN_new(),    *g = BN_new();  BN_CTX *ctx = BN_CTX_new();  BN_dec2bn(&v, "2");  BN_dec2bn(&p,            "181857351165158586099319592412492032999818333818932850952491024"            "131283899677766672100915923041329384157985577418702469610834914"            "6296393743554494871840505599");  BN_dec2bn(&q,            "220481921324130321200060036818685031159071785249502660004347524"            "831733577485433929892260897846567483448177204481081755191897197"            "38283711758138566145322943999");  BN_mul(n, p, q, ctx);  /* p + 1 */  BN_dec2bn(&h,            "181857351165158586099319592412492032999818333818932850952491024"            "131283899677766672100915923041329384157985577418702469610834914"            "6296393743554494871840505600");  lucas(v, h, n, ctx);  BN_sub(v2, v, BN_value_two());  BN_gcd(g, v2, n, ctx);  assert(!BN_is_one(g));  /* another test */  BN_dec2bn(&v, "3");  BN_dec2bn(&p,            "181857351165158586099319592412492032999818333818932850952491024"            "131283899677766672100915923041329384157985577418702469610834914"            "62963937435544948718405055999");  BN_generate_prime(q, 512, 1, NULL, NULL, NULL, NULL);  BN_mul(n, p, q, ctx);  BN_sub(h, p, BN_value_one());  BN_mul(h, h, BN_value_two(), ctx);  lucas(v, h, n, ctx);  BN_mod_sub(v2, v, BN_value_two(), n, ctx);  BN_gcd(g, v2, n, ctx);  assert(!BN_is_one(g));  assert(BN_cmp(g, n));  BN_free(q);  BN_free(p);  BN_free(v);  BN_free(v2);  BN_free(h);  BN_CTX_free(ctx);}

/* * pr_fact - print the factors of a number * * If the number is 0 or 1, then print the number and return. * If the number is < 0, print -1, negate the number and continue * processing. * * Print the factors of the number, from the lowest to the highest. * A factor will be printed numtiple times if it divides the value * multiple times. * * Factors are printed with leading tabs. */static voidpr_fact(BIGNUM *val){	const ubig *fact;		/* The factor found. */	/* Firewall - catch 0 and 1. */	if (BN_is_zero(val) || BN_is_one(val))		errx(1, "numbers <= 1 aren't permitted.");	/* Factor value. */	BN_print_dec_fp(stdout, val);	putchar(':');	for (fact = &prime[0]; !BN_is_one(val); ++fact) {		/* Look for the smallest factor. */		while (fact <= pr_limit) {			if (BN_mod_word(val, (BN_ULONG)*fact) == 0)				break;			fact++;		}		/* Watch for primes larger than the table. */		if (fact > pr_limit) {#ifdef HAVE_OPENSSL			BIGNUM *bnfact;			bnfact = BN_new();			BN_set_word(bnfact, (BN_ULONG)*(fact - 1));			BN_sqr(bnfact, bnfact, ctx);			if (BN_cmp(bnfact, val) > 0			    || BN_is_prime(val, PRIME_CHECKS, NULL, NULL,					   NULL) == 1) {				putchar(' ');				BN_print_dec_fp(stdout, val);			} else				pollard_rho(val);#else			printf(" %s", BN_bn2dec(val));#endif			break;		}		/* Divide factor out until none are left. */		do {			printf(" %lu", *fact);			BN_div_word(val, (BN_ULONG)*fact);		} while (BN_mod_word(val, (BN_ULONG)*fact) == 0);		/* Let the user know we're doing something. */		fflush(stdout);	}	putchar('/n');}

/* pollard p-1, algorithm from Jim Gillogly, May 2000 */static voidpollard_pminus1(BIGNUM *val){	BIGNUM *base, *rbase, *num, *i, *x;	base = BN_new();	rbase = BN_new();	num = BN_new();	i = BN_new();	x = BN_new();	BN_set_word(rbase, 1);newbase:	if (!BN_add_word(rbase, 1))		errx(1, "error in BN_add_word()");	BN_set_word(i, 2);	BN_copy(base, rbase);	for (;;) {		BN_mod_exp(base, base, i, val, ctx);		if (BN_is_one(base))			goto newbase;		BN_copy(x, base);		BN_sub_word(x, 1);		if (!BN_gcd(x, x, val, ctx))			errx(1, "error in BN_gcd()");		if (!BN_is_one(x)) {			if (BN_is_prime(x, PRIME_CHECKS, NULL, NULL,			    NULL) == 1)				pr_print(x);			else				pollard_pminus1(x);			fflush(stdout);			BN_div(num, NULL, val, x, ctx);			if (BN_is_one(num))				return;			if (BN_is_prime(num, PRIME_CHECKS, NULL, NULL,			    NULL) == 1) {				pr_print(num);				fflush(stdout);				return;			}			BN_copy(val, num);		}		if (!BN_add_word(i, 1))			errx(1, "error in BN_add_word()");	}}

static int verifystep1(const JPakeUser * us, const JPakeUserPublic * them,                       const JPakeParameters * params){    printf("/n%s verifies %s:/n/n", us->p.name, them->name);    // verify their ZKP(xc)    if (!VerifyZKP(&us->p.s1c.zkpx, us->p.s1c.gx, them, params->g, params,                   them->base, ""))        return 0;    // verify their ZKP(xd)    if (!VerifyZKP(&us->p.s1d.zkpx, us->p.s1d.gx, them, params->g, params,                   them->base + 1, ""))        return 0;    // g^xd != 1    printf("  g^{x%d} != 1: ", them->base + 1);    if (BN_is_one(us->p.s1d.gx)) {        puts("FAIL");        return 0;    }    puts("OK");    return 1;}

/** * /brief Test for a pair of moduluses having a prime factor in common. * */int test(BIGNUM *n, BIGNUM *m){  BIGNUM *g;  BN_CTX *ctx;  int ret = 0;  if (!BN_cmp(n, m)) return 1;  g = BN_new();  ctx = BN_CTX_new();  BN_gcd(g, n, m, ctx);  if (!BN_is_one(g)) {    fprintf(stdout, "%-8s: ", PRIME);    BN_print_fp(stdout, n);    fprintf(stdout, "  ");    BN_print_fp(stdout, m);    fprintf(stdout, "/n");    ret = 1;  }  BN_CTX_free(ctx);  BN_free(g);  return ret;}

int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group,        EC_POINT *point,        const BIGNUM *x,        const BIGNUM *y,        const BIGNUM *z,        BN_CTX *ctx){    BN_CTX *new_ctx = NULL;    int ret = 0;    if (ctx == NULL) {        ctx = new_ctx = BN_CTX_new();        if (ctx == NULL)            return 0;    }    if (x != NULL) {        if (!BN_nnmod(&point->X, x, &group->field, ctx))            goto err;        if (group->meth->field_encode) {            if (!group->meth->field_encode(group, &point->X, &point->X, ctx))                goto err;        }    }    if (y != NULL) {        if (!BN_nnmod(&point->Y, y, &group->field, ctx))            goto err;        if (group->meth->field_encode) {            if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx))                goto err;        }    }    if (z != NULL) {        int Z_is_one;        if (!BN_nnmod(&point->Z, z, &group->field, ctx))            goto err;        Z_is_one = BN_is_one(&point->Z);        if (group->meth->field_encode) {            if (Z_is_one && (group->meth->field_set_to_one != 0)) {                if (!group->meth->field_set_to_one(group, &point->Z, ctx))                    goto err;            } else {                if (!group->                        meth->field_encode(group, &point->Z, &point->Z, ctx))                    goto err;            }        }        point->Z_is_one = Z_is_one;    }    ret = 1;err:    if (new_ctx != NULL)        BN_CTX_free(new_ctx);    return ret;}

int main(int argc, char ** argv) {	/* Generate 2 big random numbers (512 bits) */	primitive_p = initialize("1011011");	initialize_rand(SEED);	BIGNUM *p = get_long_prime_number(RSA_KEY_LENGTH);	printf("p=%s/n", BN_bn2hex(p));	BIGNUM *q = get_long_prime_number(RSA_KEY_LENGTH);	printf("q=%s/n", BN_bn2hex(q));	/* Compute phi = (p-1)*(q-1) and n = p*q */	BIGNUM *phi, *n;	BN_CTX *tmp;	tmp = BN_CTX_new();	n = BN_new();	phi = BN_new();	BN_copy(n, p);	BN_mul(n, n, q, tmp);	printf("n=%s/n", BN_bn2dec(n));	BN_sub_word(p, 1);	printf("p-1=%s/n", BN_bn2dec(p));	BN_sub_word(q, 1);	printf("q-1=%s/n", BN_bn2dec(q));	phi = BN_new();	BN_init(tmp);	BN_mul(phi, p, q, tmp);	printf("(p-1)(q-1)=%s/n", BN_bn2dec(phi));	/* Find the smallest integer coprime with phi */	BIGNUM * e = BN_new();	BIGNUM *gcd = BN_new();	BN_add_word(e, 3);	for ( ; ; BN_add_word(e, 2)) {		tmp = BN_CTX_new();		BN_gcd(gcd, e, phi, tmp);		if (BN_is_one(gcd))			break;	}	printf("e=%s/n", BN_bn2dec(e));	/* Find d, the inverse of e in Z_phi */	BIGNUM * d = BN_new();	BIGNUM * i = BN_new();	BIGNUM * rem = BN_new();	BIGNUM * prod = BN_new();	BN_add_word(i, 1);	for ( ; ; BN_add_word(i, 1)) {		BN_copy(prod, phi);		tmp = BN_CTX_new();		BN_mul(prod, prod, i, tmp);		BN_add_word(prod, 1);		BN_div(d, rem, prod, e, tmp);		if (BN_is_zero(rem)) {			break;		}	}	printf("d=%s/n", BN_bn2dec(d));	return 0;}

static int dss_paramcheck(int nmod, BIGNUM *p, BIGNUM *q, BIGNUM *g,                          BN_CTX *ctx){    BIGNUM *rem = NULL;    if (BN_num_bits(p) != nmod)        return 0;    if (BN_num_bits(q) != 160)        return 0;    if (BN_is_prime_ex(p, BN_prime_checks, ctx, NULL) != 1)        return 0;    if (BN_is_prime_ex(q, BN_prime_checks, ctx, NULL) != 1)        return 0;    rem = BN_new();    if (!BN_mod(rem, p, q, ctx) || !BN_is_one(rem)            || (BN_cmp(g, BN_value_one()) <= 0)            || !BN_mod_exp(rem, g, q, p, ctx) || !BN_is_one(rem)) {        BN_free(rem);        return 0;    }    /* Todo: check g */    BN_free(rem);    return 1;}

int DH_check_pub_key(const DH *dh, const BIGNUM *pub_key, int *ret) {  *ret = 0;  BN_CTX *ctx = BN_CTX_new();  if (ctx == NULL) {    return 0;  }  BN_CTX_start(ctx);  int ok = 0;  /* Check |pub_key| is greater than 1. */  BIGNUM *tmp = BN_CTX_get(ctx);  if (tmp == NULL ||      !BN_set_word(tmp, 1)) {    goto err;  }  if (BN_cmp(pub_key, tmp) <= 0) {    *ret |= DH_CHECK_PUBKEY_TOO_SMALL;  }  /* Check |pub_key| is less than |dh->p| - 1. */  if (!BN_copy(tmp, dh->p) ||      !BN_sub_word(tmp, 1)) {    goto err;  }  if (BN_cmp(pub_key, tmp) >= 0) {    *ret |= DH_CHECK_PUBKEY_TOO_LARGE;  }  if (dh->q != NULL) {    /* Check |pub_key|^|dh->q| is 1 mod |dh->p|. This is necessary for RFC 5114     * groups which are not safe primes but pick a generator on a prime-order     * subgroup of size |dh->q|. */    if (!BN_mod_exp(tmp, pub_key, dh->q, dh->p, ctx)) {      goto err;    }    if (!BN_is_one(tmp)) {      *ret |= DH_CHECK_PUBKEY_INVALID;    }  }  ok = 1;err:  BN_CTX_end(ctx);  BN_CTX_free(ctx);  return ok;}

static boolbsqrt_stop(const BIGNUM *x, const BIGNUM *y, u_int *onecount){	BIGNUM *r;	bool ret;	r = BN_new();	bn_checkp(r);	bn_check(BN_sub(r, x, y));	if (BN_is_one(r))		(*onecount)++;	ret = BN_is_zero(r);	BN_free(r);	return (ret || *onecount > 1);}

/* g^x is a legal value */static int is_legal(const BIGNUM *gx, const JPAKE_CTX *ctx)    {    BIGNUM *t;    int res;        if(BN_is_negative(gx) || BN_is_zero(gx) || BN_cmp(gx, ctx->p.p) >= 0)	return 0;    t = BN_new();    BN_mod_exp(t, gx, ctx->p.q, ctx->p.p, ctx->ctx);    res = BN_is_one(t);    BN_free(t);    return res;    }

static int check_mod_inverse(int *out_ok, const BIGNUM *a, const BIGNUM *ainv,                             const BIGNUM *m, int check_reduced, BN_CTX *ctx) {  BN_CTX_start(ctx);  BIGNUM *tmp = BN_CTX_get(ctx);  int ret = tmp != NULL &&            bn_mul_consttime(tmp, a, ainv, ctx) &&            bn_div_consttime(NULL, tmp, tmp, m, ctx);  if (ret) {    *out_ok = BN_is_one(tmp);    if (check_reduced && (BN_is_negative(ainv) || BN_cmp(ainv, m) >= 0)) {      *out_ok = 0;    }  }  BN_CTX_end(ctx);  return ret;}

int EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator,                           const BIGNUM *order, const BIGNUM *cofactor) {  if (group->curve_name != NID_undef || group->generator != NULL) {    // |EC_GROUP_set_generator| may only be used with |EC_GROUP|s returned by    // |EC_GROUP_new_curve_GFp| and may only used once on each group.    return 0;  }  // Require a cofactor of one for custom curves, which implies prime order.  if (!BN_is_one(cofactor)) {    OPENSSL_PUT_ERROR(EC, EC_R_INVALID_COFACTOR);    return 0;  }  group->generator = EC_POINT_new(group);  return group->generator != NULL &&         EC_POINT_copy(group->generator, generator) &&         BN_copy(&group->order, order);}

int JPAKE_STEP1_process(JPAKE_CTX *ctx, const JPAKE_STEP1 *received)    {    if(!is_legal(received->p1.gx, ctx))	{	JPAKEerr(JPAKE_F_JPAKE_STEP1_PROCESS, JPAKE_R_G_TO_THE_X3_IS_NOT_LEGAL);	return 0;	}    if(!is_legal(received->p2.gx, ctx))	{	JPAKEerr(JPAKE_F_JPAKE_STEP1_PROCESS, JPAKE_R_G_TO_THE_X4_IS_NOT_LEGAL);	return 0;	}   /* verify their ZKP(xc) */    if(!verify_zkp(&received->p1, ctx->p.g, ctx))	{	JPAKEerr(JPAKE_F_JPAKE_STEP1_PROCESS, JPAKE_R_VERIFY_X3_FAILED);	return 0;	}   /* verify their ZKP(xd) */    if(!verify_zkp(&received->p2, ctx->p.g, ctx))	{	JPAKEerr(JPAKE_F_JPAKE_STEP1_PROCESS, JPAKE_R_VERIFY_X4_FAILED);	return 0;	}   /* g^xd != 1 */    if(BN_is_one(received->p2.gx))	{	JPAKEerr(JPAKE_F_JPAKE_STEP1_PROCESS, JPAKE_R_G_TO_THE_X4_IS_ONE);	return 0;	}   /* Save the bits we need for later */    BN_copy(ctx->p.gxc, received->p1.gx);    BN_copy(ctx->p.gxd, received->p2.gx);    return 1;    }

uint8_t sane_key(RSA *rsa) { // checks sanity of a RSA key (PKCS#1 v2.1)    uint8_t sane = 1;    BN_CTX *ctx = BN_CTX_new();    BN_CTX_start(ctx);    BIGNUM *p1     = BN_CTX_get(ctx), // p - 1            *q1     = BN_CTX_get(ctx), // q - 1             *chk    = BN_CTX_get(ctx), // storage to run checks with              *gcd    = BN_CTX_get(ctx), // GCD(p - 1, q - 1)               *lambda = BN_CTX_get(ctx); // LCM(p - 1, q - 1)    BN_sub(p1, rsa->p, BN_value_one()); // p - 1    BN_sub(q1, rsa->q, BN_value_one()); // q - 1    BN_gcd(gcd, p1, q1, ctx);           // gcd(p - 1, q - 1)    BN_lcm(lambda, p1, q1, gcd, ctx);   // lambda(n)    BN_gcd(chk, lambda, rsa->e, ctx); // check if e is coprime to lambda(n)    if(!BN_is_one(chk))        sane = 0;    // check if public exponent e is less than n - 1    BN_sub(chk, rsa->e, rsa->n); // subtract n from e to avoid checking BN_is_zero    if(!chk->neg)        sane = 0;    BN_mod_inverse(rsa->d, rsa->e, lambda, ctx);    // d    BN_mod(rsa->dmp1, rsa->d, p1, ctx);             // d mod (p - 1)    BN_mod(rsa->dmq1, rsa->d, q1, ctx);             // d mod (q - 1)    BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx); // q ^ -1 mod p    BN_CTX_end(ctx);    BN_CTX_free(ctx);    // this is excessive but you're better off safe than (very) sorry    // in theory this should never be true unless I made a mistake ;)    if((RSA_check_key(rsa) != 1) && sane) {        fprintf(stderr, "WARNING: Key looked okay, but OpenSSL says otherwise!/n");        sane = 0;    }    return sane;}

int DH_check_pub_key(const DH *dh, const BIGNUM *pub_key, int *ret){    int ok = 0;    BIGNUM *tmp = NULL;    BN_CTX *ctx = NULL;    *ret = 0;    ctx = BN_CTX_new();    if (ctx == NULL)        goto err;    BN_CTX_start(ctx);    tmp = BN_CTX_get(ctx);    if (tmp == NULL || !BN_set_word(tmp, 1))        goto err;    if (BN_cmp(pub_key, tmp) <= 0)        *ret |= DH_CHECK_PUBKEY_TOO_SMALL;    if (BN_copy(tmp, dh->p) == NULL || !BN_sub_word(tmp, 1))        goto err;    if (BN_cmp(pub_key, tmp) >= 0)        *ret |= DH_CHECK_PUBKEY_TOO_LARGE;    if (dh->q != NULL) {        /* Check pub_key^q == 1 mod p */        if (!BN_mod_exp(tmp, pub_key, dh->q, dh->p, ctx))            goto err;        if (!BN_is_one(tmp))            *ret |= DH_CHECK_PUBKEY_INVALID;    }    ok = 1; err:    if (ctx != NULL) {        BN_CTX_end(ctx);        BN_CTX_free(ctx);    }    return (ok);}

int DH_check(const DH *dh, int *ret) {  /* Check that p is a safe prime and if g is 2, 3 or 5, check that it is a   * suitable generator where:   *   for 2, p mod 24 == 11   *   for 3, p mod 12 == 5   *   for 5, p mod 10 == 3 or 7   * should hold.   */  int ok = 0, r;  BN_CTX *ctx = NULL;  BN_ULONG l;  BIGNUM *t1 = NULL, *t2 = NULL;  *ret = 0;  ctx = BN_CTX_new();  if (ctx == NULL) {    goto err;  }  BN_CTX_start(ctx);  t1 = BN_CTX_get(ctx);  if (t1 == NULL) {    goto err;  }  t2 = BN_CTX_get(ctx);  if (t2 == NULL) {    goto err;  }  if (dh->q) {    if (BN_cmp(dh->g, BN_value_one()) <= 0) {      *ret |= DH_CHECK_NOT_SUITABLE_GENERATOR;    } else if (BN_cmp(dh->g, dh->p) >= 0) {      *ret |= DH_CHECK_NOT_SUITABLE_GENERATOR;    } else {      /* Check g^q == 1 mod p */      if (!BN_mod_exp(t1, dh->g, dh->q, dh->p, ctx)) {        goto err;      }      if (!BN_is_one(t1)) {        *ret |= DH_CHECK_NOT_SUITABLE_GENERATOR;      }    }    r = BN_is_prime_ex(dh->q, BN_prime_checks, ctx, NULL);    if (r < 0) {      goto err;    }    if (!r) {      *ret |= DH_CHECK_Q_NOT_PRIME;    }    /* Check p == 1 mod q  i.e. q divides p - 1 */    if (!BN_div(t1, t2, dh->p, dh->q, ctx)) {      goto err;    }    if (!BN_is_one(t2)) {      *ret |= DH_CHECK_INVALID_Q_VALUE;    }    if (dh->j && BN_cmp(dh->j, t1)) {      *ret |= DH_CHECK_INVALID_J_VALUE;    }  } else if (BN_is_word(dh->g, DH_GENERATOR_2)) {    l = BN_mod_word(dh->p, 24);    if (l == (BN_ULONG)-1) {      goto err;    }    if (l != 11) {      *ret |= DH_CHECK_NOT_SUITABLE_GENERATOR;    }  } else if (BN_is_word(dh->g, DH_GENERATOR_5)) {    l = BN_mod_word(dh->p, 10);    if (l == (BN_ULONG)-1) {      goto err;    }    if (l != 3 && l != 7) {      *ret |= DH_CHECK_NOT_SUITABLE_GENERATOR;    }  } else {    *ret |= DH_CHECK_UNABLE_TO_CHECK_GENERATOR;  }  r = BN_is_prime_ex(dh->p, BN_prime_checks, ctx, NULL);  if (r < 0) {    goto err;  }  if (!r) {    *ret |= DH_CHECK_P_NOT_PRIME;  } else if (!dh->q) {    if (!BN_rshift1(t1, dh->p)) {      goto err;    }    r = BN_is_prime_ex(t1, BN_prime_checks, ctx, NULL);    if (r < 0) {      goto err;    }    if (!r) {      *ret |= DH_CHECK_P_NOT_SAFE_PRIME;    }  }  ok = 1;err://.........这里部分代码省略.........

static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb)	{	BIGNUM *r0=NULL,*r1=NULL,*r2=NULL,*r3=NULL,*tmp;	BIGNUM local_r0,local_d,local_p;	BIGNUM *pr0,*d,*p;	int bitsp,bitsq,ok= -1,n=0;	BN_CTX *ctx=NULL;	ctx=BN_CTX_new();	if (ctx == NULL) goto err;	BN_CTX_start(ctx);	r0 = BN_CTX_get(ctx);	r1 = BN_CTX_get(ctx);	r2 = BN_CTX_get(ctx);	r3 = BN_CTX_get(ctx);	if (r3 == NULL) goto err;	bitsp=(bits+1)/2;	bitsq=bits-bitsp;	/* We need the RSA components non-NULL */	if(!rsa->n && ((rsa->n=BN_new()) == NULL)) goto err;	if(!rsa->d && ((rsa->d=BN_new()) == NULL)) goto err;	if(!rsa->e && ((rsa->e=BN_new()) == NULL)) goto err;	if(!rsa->p && ((rsa->p=BN_new()) == NULL)) goto err;	if(!rsa->q && ((rsa->q=BN_new()) == NULL)) goto err;	if(!rsa->dmp1 && ((rsa->dmp1=BN_new()) == NULL)) goto err;	if(!rsa->dmq1 && ((rsa->dmq1=BN_new()) == NULL)) goto err;	if(!rsa->iqmp && ((rsa->iqmp=BN_new()) == NULL)) goto err;	BN_copy(rsa->e, e_value);	/* generate p and q */	for (;;)		{		if(!BN_generate_prime_ex(rsa->p, bitsp, 0, NULL, NULL, cb))			goto err;		if (!BN_sub(r2,rsa->p,BN_value_one())) goto err;		if (!BN_gcd(r1,r2,rsa->e,ctx)) goto err;		if (BN_is_one(r1)) break;		if(!BN_GENCB_call(cb, 2, n++))			goto err;		}	if(!BN_GENCB_call(cb, 3, 0))		goto err;	for (;;)		{		/* When generating ridiculously small keys, we can get stuck		 * continually regenerating the same prime values. Check for		 * this and bail if it happens 3 times. */		unsigned int degenerate = 0;		do			{			if(!BN_generate_prime_ex(rsa->q, bitsq, 0, NULL, NULL, cb))				goto err;			} while((BN_cmp(rsa->p, rsa->q) == 0) && (++degenerate < 3));		if(degenerate == 3)			{			ok = 0; /* we set our own err */			RSAerr(RSA_F_RSA_BUILTIN_KEYGEN,RSA_R_KEY_SIZE_TOO_SMALL);			goto err;			}		if (!BN_sub(r2,rsa->q,BN_value_one())) goto err;		if (!BN_gcd(r1,r2,rsa->e,ctx)) goto err;		if (BN_is_one(r1))			break;		if(!BN_GENCB_call(cb, 2, n++))			goto err;		}	if(!BN_GENCB_call(cb, 3, 1))		goto err;	if (BN_cmp(rsa->p,rsa->q) < 0)		{		tmp=rsa->p;		rsa->p=rsa->q;		rsa->q=tmp;		}	/* calculate n */	if (!BN_mul(rsa->n,rsa->p,rsa->q,ctx)) goto err;	/* calculate d */	if (!BN_sub(r1,rsa->p,BN_value_one())) goto err;	/* p-1 */	if (!BN_sub(r2,rsa->q,BN_value_one())) goto err;	/* q-1 */	if (!BN_mul(r0,r1,r2,ctx)) goto err;	/* (p-1)(q-1) */	if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME))		{		  pr0 = &local_r0;		  BN_with_flags(pr0, r0, BN_FLG_CONSTTIME);		}	else	  pr0 = r0;	if (!BN_mod_inverse(rsa->d,rsa->e,pr0,ctx)) goto err;	/* d */	/* set up d for correct BN_FLG_CONSTTIME flag */	if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME))		{		d = &local_d;		BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);		}//.........这里部分代码省略.........

static int generate_key(DH *dh){    int ok = 0;    int generate_new_key = 0;    unsigned l;    BN_CTX *ctx;    BN_MONT_CTX *mont = NULL;    BIGNUM *pub_key = NULL, *priv_key = NULL;    ctx = BN_CTX_new();    if (ctx == NULL)        goto err;    if (dh->priv_key == NULL) {        priv_key = BN_new();        if (priv_key == NULL)            goto err;        generate_new_key = 1;    } else        priv_key = dh->priv_key;    if (dh->pub_key == NULL) {        pub_key = BN_new();        if (pub_key == NULL)            goto err;    } else        pub_key = dh->pub_key;    if (dh->flags & DH_FLAG_CACHE_MONT_P) {        mont = BN_MONT_CTX_set_locked(&dh->method_mont_p,                                      CRYPTO_LOCK_DH, dh->p, ctx);        if (!mont)            goto err;    }    if (generate_new_key) {        if (dh->q) {            do {                if (!BN_rand_range(priv_key, dh->q))                    goto err;            }            while (BN_is_zero(priv_key) || BN_is_one(priv_key));        } else {            /* secret exponent length */            l = dh->length ? dh->length : BN_num_bits(dh->p) - 1;            if (!BN_rand(priv_key, l, 0, 0))                goto err;        }    }    {        BIGNUM local_prk;        BIGNUM *prk;        if ((dh->flags & DH_FLAG_NO_EXP_CONSTTIME) == 0) {            BN_init(&local_prk);            prk = &local_prk;            BN_with_flags(prk, priv_key, BN_FLG_CONSTTIME);        } else            prk = priv_key;        if (!dh->meth->bn_mod_exp(dh, pub_key, dh->g, prk, dh->p, ctx, mont))            goto err;    }    dh->pub_key = pub_key;    dh->priv_key = priv_key;    ok = 1; err:    if (ok != 1)        DHerr(DH_F_GENERATE_KEY, ERR_R_BN_LIB);    if ((pub_key != NULL) && (dh->pub_key == NULL))        BN_free(pub_key);    if ((priv_key != NULL) && (dh->priv_key == NULL))        BN_free(priv_key);    BN_CTX_free(ctx);    return (ok);}

int rsa_default_multi_prime_keygen(RSA *rsa, int bits, int num_primes,                                   BIGNUM *e_value, BN_GENCB *cb) {  BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *r3 = NULL, *tmp;  BIGNUM local_r0, local_d, local_p;  BIGNUM *pr0, *d, *p;  int prime_bits, ok = -1, n = 0, i, j;  BN_CTX *ctx = NULL;  STACK_OF(RSA_additional_prime) *additional_primes = NULL;  if (num_primes < 2) {    ok = 0; /* we set our own err */    OPENSSL_PUT_ERROR(RSA, RSA_R_MUST_HAVE_AT_LEAST_TWO_PRIMES);    goto err;  }  ctx = BN_CTX_new();  if (ctx == NULL) {    goto err;  }  BN_CTX_start(ctx);  r0 = BN_CTX_get(ctx);  r1 = BN_CTX_get(ctx);  r2 = BN_CTX_get(ctx);  r3 = BN_CTX_get(ctx);  if (r0 == NULL || r1 == NULL || r2 == NULL || r3 == NULL) {    goto err;  }  if (num_primes > 2) {    additional_primes = sk_RSA_additional_prime_new_null();    if (additional_primes == NULL) {      goto err;    }  }  for (i = 2; i < num_primes; i++) {    RSA_additional_prime *ap = OPENSSL_malloc(sizeof(RSA_additional_prime));    if (ap == NULL) {      goto err;    }    memset(ap, 0, sizeof(RSA_additional_prime));    ap->prime = BN_new();    ap->exp = BN_new();    ap->coeff = BN_new();    ap->r = BN_new();    if (ap->prime == NULL ||        ap->exp == NULL ||        ap->coeff == NULL ||        ap->r == NULL ||        !sk_RSA_additional_prime_push(additional_primes, ap)) {      RSA_additional_prime_free(ap);      goto err;    }  }  /* We need the RSA components non-NULL */  if (!rsa->n && ((rsa->n = BN_new()) == NULL)) {    goto err;  }  if (!rsa->d && ((rsa->d = BN_new()) == NULL)) {    goto err;  }  if (!rsa->e && ((rsa->e = BN_new()) == NULL)) {    goto err;  }  if (!rsa->p && ((rsa->p = BN_new()) == NULL)) {    goto err;  }  if (!rsa->q && ((rsa->q = BN_new()) == NULL)) {    goto err;  }  if (!rsa->dmp1 && ((rsa->dmp1 = BN_new()) == NULL)) {    goto err;  }  if (!rsa->dmq1 && ((rsa->dmq1 = BN_new()) == NULL)) {    goto err;  }  if (!rsa->iqmp && ((rsa->iqmp = BN_new()) == NULL)) {    goto err;  }  if (!BN_copy(rsa->e, e_value)) {    goto err;  }  /* generate p and q */  prime_bits = (bits + (num_primes - 1)) / num_primes;  for (;;) {    if (!BN_generate_prime_ex(rsa->p, prime_bits, 0, NULL, NULL, cb) ||        !BN_sub(r2, rsa->p, BN_value_one()) ||        !BN_gcd(r1, r2, rsa->e, ctx)) {      goto err;    }    if (BN_is_one(r1)) {      break;    }    if (!BN_GENCB_call(cb, 2, n++)) {      goto err;    }  }//.........这里部分代码省略.........

//.........这里部分代码省略.........	 */	while (!BN_is_zero(B))		{		BIGNUM *tmp;				/*		 *      0 < B < A,		 * (*) -sign*X*a  ==  B   (mod |n|),		 *      sign*Y*a  ==  A   (mod |n|)		 */		/* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,	 	 * BN_div_no_branch will be called eventually.	 	 */		pA = &local_A;		BN_with_flags(pA, A, BN_FLG_CONSTTIME);					/* (D, M) := (A/B, A%B) ... */				if (!BN_div(D,M,pA,B,ctx)) goto err;				/* Now		 *      A = D*B + M;		 * thus we have		 * (**)  sign*Y*a  ==  D*B + M   (mod |n|).		 */				tmp=A; /* keep the BIGNUM object, the value does not matter */				/* (A, B) := (B, A mod B) ... */		A=B;		B=M;		/* ... so we have  0 <= B < A  again */				/* Since the former  M  is now  B  and the former  B  is now  A,		 * (**) translates into		 *       sign*Y*a  ==  D*A + B    (mod |n|),		 * i.e.		 *       sign*Y*a - D*A  ==  B    (mod |n|).		 * Similarly, (*) translates into		 *      -sign*X*a  ==  A          (mod |n|).		 *		 * Thus,		 *   sign*Y*a + D*sign*X*a  ==  B  (mod |n|),		 * i.e.		 *        sign*(Y + D*X)*a  ==  B  (mod |n|).		 *		 * So if we set  (X, Y, sign) := (Y + D*X, X, -sign),  we arrive back at		 *      -sign*X*a  ==  B   (mod |n|),		 *       sign*Y*a  ==  A   (mod |n|).		 * Note that  X  and  Y  stay non-negative all the time.		 */					if (!BN_mul(tmp,D,X,ctx)) goto err;		if (!BN_add(tmp,tmp,Y)) goto err;		M=Y; /* keep the BIGNUM object, the value does not matter */		Y=X;		X=tmp;		sign = -sign;		}			/*	 * The while loop (Euclid's algorithm) ends when	 *      A == gcd(a,n);	 * we have	 *       sign*Y*a  ==  A  (mod |n|),	 * where  Y  is non-negative.	 */	if (sign < 0)		{		if (!BN_sub(Y,n,Y)) goto err;		}	/* Now  Y*a  ==  A  (mod |n|).  */	if (BN_is_one(A))		{		/* Y*a == 1  (mod |n|) */		if (!Y->neg && BN_ucmp(Y,n) < 0)			{			if (!BN_copy(R,Y)) goto err;			}		else			{			if (!BN_nnmod(R,Y,n,ctx)) goto err;			}		}	else		{		BNerr(BN_F_BN_MOD_INVERSE_NO_BRANCH,BN_R_NO_INVERSE);		goto err;		}	ret=R;err:	if ((ret == NULL) && (in == NULL)) BN_free(R);	BN_CTX_end(ctx);	bn_check_top(ret);	return(ret);	}

//.........这里部分代码省略.........			/* Now			 *      A = D*B + M;			 * thus we have			 * (**)  sign*Y*a  ==  D*B + M   (mod |n|).			 */						tmp=A; /* keep the BIGNUM object, the value does not matter */						/* (A, B) := (B, A mod B) ... */			A=B;			B=M;			/* ... so we have  0 <= B < A  again */						/* Since the former  M  is now  B  and the former  B  is now  A,			 * (**) translates into			 *       sign*Y*a  ==  D*A + B    (mod |n|),			 * i.e.			 *       sign*Y*a - D*A  ==  B    (mod |n|).			 * Similarly, (*) translates into			 *      -sign*X*a  ==  A          (mod |n|).			 *			 * Thus,			 *   sign*Y*a + D*sign*X*a  ==  B  (mod |n|),			 * i.e.			 *        sign*(Y + D*X)*a  ==  B  (mod |n|).			 *			 * So if we set  (X, Y, sign) := (Y + D*X, X, -sign),  we arrive back at			 *      -sign*X*a  ==  B   (mod |n|),			 *       sign*Y*a  ==  A   (mod |n|).			 * Note that  X  and  Y  stay non-negative all the time.			 */						/* most of the time D is very small, so we can optimize tmp := D*X+Y */			if (BN_is_one(D))				{				if (!BN_add(tmp,X,Y)) goto err;				}			else				{				if (BN_is_word(D,2))					{					if (!BN_lshift1(tmp,X)) goto err;					}				else if (BN_is_word(D,4))					{					if (!BN_lshift(tmp,X,2)) goto err;					}				else if (D->top == 1)					{					if (!BN_copy(tmp,X)) goto err;					if (!BN_mul_word(tmp,D->d[0])) goto err;					}				else					{					if (!BN_mul(tmp,D,X,ctx)) goto err;					}				if (!BN_add(tmp,tmp,Y)) goto err;				}						M=Y; /* keep the BIGNUM object, the value does not matter */			Y=X;			X=tmp;			sign = -sign;			}		}		

//.........这里部分代码省略.........			/* 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;}