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

static intbn_rand_range(int pseudo, BIGNUM *r, BIGNUM *range){    int (*bn_rand)(BIGNUM *, int, int, int) = pseudo ? BN_pseudo_rand : BN_rand;    int n;    if (range->neg || BN_is_zero(range)) return 0;    n = BN_num_bits(range);    if (n == 1) {	if (!BN_zero(r)) return 0;    } else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3)) {	do {	    if (!bn_rand(r, n + 1, -1, 0)) return 0;	    if (BN_cmp(r ,range) >= 0) {		if (!BN_sub(r, r, range)) return 0;		if (BN_cmp(r, range) >= 0)		    if (!BN_sub(r, r, range)) return 0;	    }	} while (BN_cmp(r, range) >= 0);    } else {	do {	    if (!bn_rand(r, n, -1, 0)) return 0;	} while (BN_cmp(r, range) >= 0);    }    return 1;}

int BN_rand_range_ex(BIGNUM *r, BN_ULONG min_inclusive,                     const BIGNUM *max_exclusive, RAND *rng) {  unsigned n;  unsigned count = 100;  if (BN_cmp_word(max_exclusive, min_inclusive) <= 0) {    OPENSSL_PUT_ERROR(BN, BN_R_INVALID_RANGE);    return 0;  }  n = BN_num_bits(max_exclusive); /* n > 0 */  /* BN_is_bit_set(range, n - 1) always holds */  if (n == 1) {    BN_zero(r);    return 1;  }  do {    if (!--count) {      OPENSSL_PUT_ERROR(BN, BN_R_TOO_MANY_ITERATIONS);      return 0;    }    if (!BN_is_bit_set(max_exclusive, n - 2) &&        !BN_is_bit_set(max_exclusive, n - 3)) {      /* range = 100..._2, so 3*range (= 11..._2) is exactly one bit longer       * than range. This is a common scenario when generating a random value       * modulo an RSA public modulus, e.g. for RSA base blinding. */      if (!BN_rand(r, n + 1, -1 /* don't set most significant bits */,                   0 /* don't set least significant bits */, rng)) {        return 0;      }      /* If r < 3*range, use r := r MOD range (which is either r, r - range, or       * r - 2*range). Otherwise, iterate again. Since 3*range = 11..._2, each       * iteration succeeds with probability >= .75. */      if (BN_cmp(r, max_exclusive) >= 0) {        if (!BN_sub(r, r, max_exclusive)) {          return 0;        }        if (BN_cmp(r, max_exclusive) >= 0) {          if (!BN_sub(r, r, max_exclusive)) {            return 0;          }        }      }    } else {      /* range = 11..._2  or  range = 101..._2 */      if (!BN_rand(r, n, -1, 0, rng)) {        return 0;      }    }  } while (BN_cmp_word(r, min_inclusive) < 0 ||           BN_cmp(r, max_exclusive) >= 0);  return 1;}

int BN_rand_range(BIGNUM *r, const BIGNUM *range) {  unsigned n;  unsigned count = 100;  if (range->neg || BN_is_zero(range)) {    OPENSSL_PUT_ERROR(BN, BN_rand_range, BN_R_INVALID_RANGE);    return 0;  }  n = BN_num_bits(range); /* n > 0 */  /* BN_is_bit_set(range, n - 1) always holds */  if (n == 1) {    BN_zero(r);  } else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3)) {    /* range = 100..._2,     * so  3*range (= 11..._2)  is exactly one bit longer than  range */    do {      if (!BN_rand(r, n + 1, -1 /* don't set most significant bits */,                   0 /* don't set least significant bits */)) {        return 0;      }      /* If r < 3*range, use r := r MOD range (which is either r, r - range, or       * r - 2*range). Otherwise, iterate again. Since 3*range = 11..._2, each       * iteration succeeds with probability >= .75. */      if (BN_cmp(r, range) >= 0) {        if (!BN_sub(r, r, range)) {          return 0;        }        if (BN_cmp(r, range) >= 0) {          if (!BN_sub(r, r, range)) {            return 0;          }        }      }      if (!--count) {        OPENSSL_PUT_ERROR(BN, BN_rand_range, BN_R_TOO_MANY_ITERATIONS);        return 0;      }    } while (BN_cmp(r, range) >= 0);  } else {    do {      /* range = 11..._2  or  range = 101..._2 */      if (!BN_rand(r, n, -1, 0)) {        return 0;      }      if (!--count) {        OPENSSL_PUT_ERROR(BN, BN_rand_range, BN_R_TOO_MANY_ITERATIONS);        return 0;      }    } while (BN_cmp(r, range) >= 0);  }  return 1;}

voiddh_gen_key(DH *dh, int need){	int i, bits_set, tries = 0;	if (dh->p == NULL)		fatal("dh_gen_key: dh->p == NULL");	if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p))		fatal("dh_gen_key: group too small: %d (2*need %d)",		    BN_num_bits(dh->p), 2*need);	do {		if (dh->priv_key != NULL)			BN_clear_free(dh->priv_key);		if ((dh->priv_key = BN_new()) == NULL)			fatal("dh_gen_key: BN_new failed");		/* generate a 2*need bits random private exponent */		if (!BN_rand(dh->priv_key, 2*need, 0, 0))			fatal("dh_gen_key: BN_rand failed");		if (DH_generate_key(dh) == 0)			fatal("DH_generate_key");		for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++)			if (BN_is_bit_set(dh->priv_key, i))				bits_set++;		debug2("dh_gen_key: priv key bits set: %d/%d",		    bits_set, BN_num_bits(dh->priv_key));		if (tries++ > 10)			fatal("dh_gen_key: too many bad keys: giving up");	} while (!dh_pub_is_valid(dh, dh->pub_key));}

void compute_y(BIGNUM *bn_y, BIGNUM *bn_a, BIGNUM *bn_r, BIGNUM *bn_n, BN_CTX *bn_ctx){	BIGNUM *bn_i = NULL;	BIGNUM *bn_1 = NULL;	int num_bits = 0;	int i = 0;	BIGNUM **bn_array = NULL;		num_bits = BN_num_bits(bn_r);	bn_array = (BIGNUM **)malloc(sizeof(BIGNUM*) * num_bits);	computeBNArray(bn_array, bn_a, bn_n, bn_ctx, num_bits);		bn_1 = BN_new();	bn_i = BN_new();	BN_one(bn_1);	BN_zero(bn_i);	BN_one(bn_y);		for(i = 0; i < num_bits; i++){		if(BN_is_bit_set(bn_r, i) == 1){			BN_mod_mul(bn_y, bn_y, bn_array[i], bn_n, bn_ctx);		}	}	BN_free(bn_1);	BN_free(bn_i);}

int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) {  int i, bits, ret = 0;  BIGNUM *v, *rr;  if ((p->flags & BN_FLG_CONSTTIME) != 0) {    /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */    OPENSSL_PUT_ERROR(BN, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);    return 0;  }  BN_CTX_start(ctx);  if (r == a || r == p) {    rr = BN_CTX_get(ctx);  } else {    rr = r;  }  v = BN_CTX_get(ctx);  if (rr == NULL || v == NULL) {    goto err;  }  if (BN_copy(v, a) == NULL) {    goto err;  }  bits = BN_num_bits(p);  if (BN_is_odd(p)) {    if (BN_copy(rr, a) == NULL) {      goto err;    }  } else {    if (!BN_one(rr)) {      goto err;    }  }  for (i = 1; i < bits; i++) {    if (!BN_sqr(v, v, ctx)) {      goto err;    }    if (BN_is_bit_set(p, i)) {      if (!BN_mul(rr, rr, v, ctx)) {        goto err;      }    }  }  if (r != rr && !BN_copy(r, rr)) {    goto err;  }  ret = 1;err:  BN_CTX_end(ctx);  return ret;}

/** * public static native void modifyBit(int, int, int) */static jboolean NativeBN_modifyBit(JNIEnv* env, jclass cls, BIGNUM* a, int n, int op) {// LOGD("NativeBN_BN_modifyBit");    if (!oneValidHandle(env, a)) return FALSE;    switch (op) {    case 1: return BN_set_bit(a, n);    case 0: return BN_clear_bit(a, n);    case -1:        if (BN_is_bit_set(a, n)) return BN_clear_bit(a, n);        else return BN_set_bit(a, n);    }    return FALSE;}

/* * call-seq: *    bn.bit_set?(bit) => true | false */static VALUEossl_bn_is_bit_set(VALUE self, VALUE bit){    int b;    BIGNUM *bn;    b = NUM2INT(bit);    GetBN(self, bn);    if (BN_is_bit_set(bn, b)) {	return Qtrue;    }    return Qfalse;}

int BN_bn2solinas(const BIGNUM *bn, BN_SOLINAS *solinas){	int ret = 0;	BIGNUM *tmp = NULL;	int nbits;	int i;	if (!solinas || !bn) {		BNerr(BN_F_BN_BN2SOLINAS, ERR_R_PASSED_NULL_PARAMETER);		return 0;	}	if (!BN_copy(tmp, bn)) {		goto end;	}	if ((nbits = BN_num_bits(bn) - 1) < 1) {		BNerr(BN_F_BN_BN2SOLINAS, BN_R_INVALID_SOLINAS);		goto end;	}	solinas->c = BN_is_bit_set(bn, 1) ? 1 : -1;	if (BN_is_bit_set(bn, nbits - 1)) {		solinas->s = -1;		solinas->a = nbits;	} else {		solinas->s = 1;		solinas->a = nbits - 1;	}	for (i = 1; i < nbits; i++) {	}end:	return ret;}

/* random number r:  0 <= r < range */int	BN_rand_range(BIGNUM *r, BIGNUM *range)	{	int n;	if (range->neg || BN_is_zero(range))		{		BNerr(BN_F_BN_RAND_RANGE, BN_R_INVALID_RANGE);		return 0;		}	n = BN_num_bits(range); /* n > 0 */	if (n == 1)		{		if (!BN_zero(r)) return 0;		}	else if (BN_is_bit_set(range, n - 2))		{		do			{			/* range = 11..._2, so each iteration succeeds with probability >= .75 */			if (!BN_rand(r, n, -1, 0)) return 0;			}		while (BN_cmp(r, range) >= 0);		}	else		{		/* range = 10..._2,		 * so  3*range (= 11..._2)  is exactly one bit longer than  range */		do			{			if (!BN_rand(r, n + 1, -1, 0)) return 0;			/* If  r < 3*range,  use  r := r MOD range			 * (which is either  r, r - range,  or  r - 2*range).			 * Otherwise, iterate once more.			 * Since  3*range = 11..._2, each iteration succeeds with			 * probability >= .75. */			if (BN_cmp(r ,range) >= 0)				{				if (!BN_sub(r, r, range)) return 0;				if (BN_cmp(r, range) >= 0)					if (!BN_sub(r, r, range)) return 0;				}			}		while (BN_cmp(r, range) >= 0);		}	return 1;	}

int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits, BN_CTX *ctx){    int i;    BIGNUM *offset_index;    BIGNUM *offset_count;    int ret = 0;    OPENSSL_assert(bits > prime_multiplier_bits);    BN_CTX_start(ctx);    if ((offset_index = BN_CTX_get(ctx)) == NULL)        goto err;    if ((offset_count = BN_CTX_get(ctx)) == NULL)        goto err;    if (!BN_add_word(offset_count, prime_offset_count))        goto err; loop:    if (!BN_rand(rnd, bits - prime_multiplier_bits,                 BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD))        goto err;    if (BN_is_bit_set(rnd, bits))        goto loop;    if (!BN_rand_range(offset_index, offset_count))        goto err;    if (!BN_mul_word(rnd, prime_multiplier)        || !BN_add_word(rnd, prime_offsets[BN_get_word(offset_index)]))        goto err;    /* we now have a random number 'rand' to test. */    /* skip coprimes */    for (i = first_prime_index; i < NUMPRIMES; i++) {        /* check that rnd is a prime */        BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);        if (mod == (BN_ULONG)-1)            goto err;        if (mod <= 1)            goto loop;    }    ret = 1; err:    BN_CTX_end(ctx);    bn_check_top(rnd);    return ret;}

intdh_pub_is_valid(const DH *dh, const BIGNUM *dh_pub){	int i;	int n = BN_num_bits(dh_pub);	int bits_set = 0;	BIGNUM *tmp;	const BIGNUM *p;	if (BN_is_negative(dh_pub)) {		logit("invalid public DH value: negative");		return 0;	}	if (BN_cmp(dh_pub, BN_value_one()) != 1) {	/* pub_exp <= 1 */		logit("invalid public DH value: <= 1");		return 0;	}	if ((tmp = BN_new()) == NULL) {		error("%s: BN_new failed", __func__);		return 0;	}	DH_get0_pqg(dh, &p, NULL, NULL);	if (!BN_sub(tmp, p, BN_value_one()) ||	    BN_cmp(dh_pub, tmp) != -1) {		/* pub_exp > p-2 */		BN_clear_free(tmp);		logit("invalid public DH value: >= p-1");		return 0;	}	BN_clear_free(tmp);	for (i = 0; i <= n; i++)		if (BN_is_bit_set(dh_pub, i))			bits_set++;	debug2("bits set: %d/%d", bits_set, BN_num_bits(p));	/*	 * if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial	 */	if (bits_set < 4) {		logit("invalid public DH value (%d/%d)",		   bits_set, BN_num_bits(p));		return 0;	}	return 1;}

int dh_pub_is_valid(DH *dh, BIGNUM *dh_pub){	int i;	int n = BN_num_bits(dh_pub);	int bits_set = 0;	if (dh_pub->neg) {		//logit("invalid public DH value: negativ");		return 0;	}	for (i = 0; i <= n; i++)		if (BN_is_bit_set(dh_pub, i))			bits_set++;	//debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p));	/* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */	if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))		return 1;	//logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));	return 0;}

voidprint_ascii(FILE *f, const struct number *n){	BIGNUM *v;	int numbits, i, ch;	v = BN_dup(n->number);	bn_checkp(v);	if (BN_cmp(v, &zero) < 0)		bn_check(BN_sub(v, &zero, v));	numbits = BN_num_bytes(v) * 8;	while (numbits > 0) {		ch = 0;		for (i = 0; i < 8; i++)			ch |= BN_is_bit_set(v, numbits-i-1) << (7 - i);		putc(ch, f);		numbits -= 8;	}	BN_free(v);}

voidfixed_mod_exp (auto_BN & retval,               const auto_BN & base,               const auto_BN & exp,               const auto_BN & modulus,               auto_BN_CTX & ctx){#if defined (MOD_EXP_STATS)   clock_t start_time = clock();#endif   // Number of bits in the exponent   int numbits = BN_num_bits(exp);   // An iterator to search the map   std::map< g_base_mod_pair, g_bn_vec >::iterator m_it;   // The values corresponding to our base   g_bn_vec current_vector;   // Try to find base in map   VHUtil::AutoMutex m(g_mutex);   m_it = g_fme_map.find(g_base_mod_pair(base, modulus));   {      // Make a mutex object to keep the map in one thread at a time      if (m_it != g_fme_map.end() )      {         // Found it         current_vector = m_it->second;         if (current_vector.size() < numbits )         {            // Need more bits in the vector            for (int n=current_vector.size(); n<numbits; n++)            {               // The final table value               auto_BN t_value;               if ( !(BN_mod_mul(t_value, current_vector[n-1], current_vector[n-1],                  modulus, ctx)) )                  throw SSL_ERROR;               current_vector.push_back(t_value);            }         }      }      else      {         // Didn't find it, create the table values and put into a new vector         std::vector< auto_BN > table_values;         // Seed our table with the base^(2^0)         table_values.push_back(base);         for (int i=1; i<numbits; i++)         {            // The final table value            auto_BN t_value;            if ( !(BN_mod_mul(t_value, table_values[i-1], table_values[i-1],               modulus, ctx)) )               throw SSL_ERROR;            table_values.push_back(t_value);         }         current_vector = table_values;         // Add the base and vector to our map         g_fme_map.insert(std::pair< g_base_mod_pair, g_bn_vec >            (g_base_mod_pair(base, modulus), current_vector));      }   }   // Now look up the exponent   // Our running product   auto_BN prod_values;   BN_one(prod_values);   for (int j=0; j<numbits; j++)   {      // Find out which bits are set, then find those      // values in the vector and multiply them together      if (BN_is_bit_set(exp, j) != 0)      {         // The bit is set, so find the value in the vector and multiply         if ( !(BN_mod_mul(prod_values, prod_values, current_vector[j], modulus, ctx)) )            throw SSL_ERROR;      }   }   retval = prod_values;#if defined (MOD_EXP_STATS)   time_spent_in_fme += clock() - start_time;   {      auto_BN alternate_retval;      clock_t start_time = clock();      BN_mod_exp(alternate_retval, base, exp, modulus, ctx);      time_spent_in_BN_mod_exp += clock() - start_time;      VH_zero(BN_cmp(alternate_retval, retval), FIXED_MOD_EXP_SCREWED_UP);   }#endif}

voidtests(void){#ifndef USING_WOLFSSL	struct bitmap *b;	BIGNUM *bn;	size_t len;	int i, j, k, n;	u_char bbuf[1024], bnbuf[1024];	int r;#else	struct bitmap *b;	BIGNUM *bn;#endif	TEST_START("bitmap_new");	b = bitmap_new();	ASSERT_PTR_NE(b, NULL);	bn = BN_new();	ASSERT_PTR_NE(bn, NULL);	TEST_DONE();	TEST_START("bitmap_set_bit / bitmap_test_bit");#ifndef USING_WOLFSSL	for (i = -1; i < NTESTS; i++) {		for (j = -1; j < NTESTS; j++) {			for (k = -1; k < NTESTS; k++) {				bitmap_zero(b);	/* wolfSSL does not have support for BN_clear at this time */				BN_clear(bn);				test_subtest_info("set %d/%d/%d", i, j, k);				/* Set bits */				if (i >= 0) {					ASSERT_INT_EQ(bitmap_set_bit(b, i), 0);					ASSERT_INT_EQ(BN_set_bit(bn, i), 1);				}				if (j >= 0) {					ASSERT_INT_EQ(bitmap_set_bit(b, j), 0);					ASSERT_INT_EQ(BN_set_bit(bn, j), 1);				}				if (k >= 0) {					ASSERT_INT_EQ(bitmap_set_bit(b, k), 0);					ASSERT_INT_EQ(BN_set_bit(bn, k), 1);				}				/* Check perfect match between bitmap and bn */				test_subtest_info("match %d/%d/%d", i, j, k);				for (n = 0; n < NTESTS; n++) {					ASSERT_INT_EQ(BN_is_bit_set(bn, n),					    bitmap_test_bit(b, n));				}				/* Test length calculations */				test_subtest_info("length %d/%d/%d", i, j, k);				ASSERT_INT_EQ(BN_num_bits(bn),				    (int)bitmap_nbits(b));				ASSERT_INT_EQ(BN_num_bytes(bn),				    (int)bitmap_nbytes(b));				/* Test serialisation */				test_subtest_info("serialise %d/%d/%d",				    i, j, k);				len = bitmap_nbytes(b);				memset(bbuf, 0xfc, sizeof(bbuf));				ASSERT_INT_EQ(bitmap_to_string(b, bbuf,				    sizeof(bbuf)), 0);				for (n = len; n < (int)sizeof(bbuf); n++)					ASSERT_U8_EQ(bbuf[n], 0xfc);				r = BN_bn2bin(bn, bnbuf);				ASSERT_INT_GE(r, 0);				ASSERT_INT_EQ(r, (int)len);				ASSERT_MEM_EQ(bbuf, bnbuf, len);				/* Test deserialisation */				test_subtest_info("deserialise %d/%d/%d",				    i, j, k);				bitmap_zero(b);				ASSERT_INT_EQ(bitmap_from_string(b, bnbuf,				    len), 0);				for (n = 0; n < NTESTS; n++) {					ASSERT_INT_EQ(BN_is_bit_set(bn, n),					    bitmap_test_bit(b, n));				}				/* Test clearing bits */				test_subtest_info("clear %d/%d/%d",				    i, j, k);				for (n = 0; n < NTESTS; n++) {					ASSERT_INT_EQ(bitmap_set_bit(b, n), 0);					ASSERT_INT_EQ(BN_set_bit(bn, n), 1);				}				if (i >= 0) {					bitmap_clear_bit(b, i);	/* wolfSSL does not have support for BN_clear_bit at this time */					BN_clear_bit(bn, i);				}				if (j >= 0) {					bitmap_clear_bit(b, j);	/* wolfSSL does not have support for BN_clear_bit at this time */					BN_clear_bit(bn, j);//.........这里部分代码省略.........

int BN_is_prime_fasttest(const BIGNUM *a, int checks,		void (*callback)(int,int,void *),		BN_CTX *ctx_passed, void *cb_arg,		int do_trial_division)	{	int i, j, ret = -1;	int k;	BN_CTX *ctx = NULL;	BIGNUM *A1, *A1_odd, *check; /* taken from ctx */	BN_MONT_CTX *mont = NULL;	const BIGNUM *A = NULL;	if (BN_cmp(a, BN_value_one()) <= 0)		return 0;		if (checks == BN_prime_checks)		checks = BN_prime_checks_for_size(BN_num_bits(a));	/* first look for small factors */	if (!BN_is_odd(a))		return 0;	if (do_trial_division)		{		for (i = 1; i < NUMPRIMES; i++)			if (BN_mod_word(a, primes[i]) == 0) 				return 0;		if (callback != NULL) callback(1, -1, cb_arg);		}	if (ctx_passed != NULL)		ctx = ctx_passed;	else		if ((ctx=BN_CTX_new()) == NULL)			goto err;	BN_CTX_start(ctx);	/* A := abs(a) */	if (a->neg)		{		BIGNUM *t;		if ((t = BN_CTX_get(ctx)) == NULL) goto err;		BN_copy(t, a);		t->neg = 0;		A = t;		}	else		A = a;	A1 = BN_CTX_get(ctx);	A1_odd = BN_CTX_get(ctx);	check = BN_CTX_get(ctx);	if (check == NULL) goto err;	/* compute A1 := A - 1 */	if (!BN_copy(A1, A))		goto err;	if (!BN_sub_word(A1, 1))		goto err;	if (BN_is_zero(A1))		{		ret = 0;		goto err;		}	/* write  A1  as  A1_odd * 2^k */	k = 1;	while (!BN_is_bit_set(A1, k))		k++;	if (!BN_rshift(A1_odd, A1, k))		goto err;	/* Montgomery setup for computations mod A */	mont = BN_MONT_CTX_new();	if (mont == NULL)		goto err;	if (!BN_MONT_CTX_set(mont, A, ctx))		goto err;		for (i = 0; i < checks; i++)		{		if (!BN_pseudo_rand_range(check, A1))			goto err;		if (!BN_add_word(check, 1))			goto err;		/* now 1 <= check < A */		j = witness(check, A, A1, A1_odd, k, ctx, mont);		if (j == -1) goto err;		if (j)			{			ret=0;			goto err;			}		if (callback != NULL) callback(1,i,cb_arg);		}	ret=1;err:	if (ctx != NULL)		{		BN_CTX_end(ctx);		if (ctx_passed == NULL)//.........这里部分代码省略.........

intDH_check_pubkey(const DH *dh, const BIGNUM *pub_key, int *codes){    BIGNUM *bn = NULL, *sum = NULL;    int ret = 0;    *codes = 0;    /**     * Checks that the function performs are:     * - pub_key is not negative     */    if (BN_is_negative(pub_key))	goto out;    /**     * - pub_key > 1    and    pub_key < p - 1,     *    to avoid small subgroups attack.     */    bn = BN_new();    if (bn == NULL)	goto out;    if (!BN_set_word(bn, 1))	goto out;    if (BN_cmp(bn, pub_key) >= 0)	*codes |= DH_CHECK_PUBKEY_TOO_SMALL;    sum = BN_new();    if (sum == NULL)	goto out;    BN_uadd(sum, pub_key, bn);    if (BN_cmp(sum, dh->p) >= 0)	*codes |= DH_CHECK_PUBKEY_TOO_LARGE;    /**     * - if g == 2, pub_key have more then one bit set,     *   if bits set is 1, log_2(pub_key) is trival     */    if (!BN_set_word(bn, 2))	goto out;    if (BN_cmp(bn, dh->g) == 0) {	unsigned i, n = BN_num_bits(pub_key);	unsigned bits = 0;	for (i = 0; i <= n; i++)	    if (BN_is_bit_set(pub_key, i))		bits++;	if (bits < 2) {	    *codes |= DH_CHECK_PUBKEY_TOO_SMALL;	    goto out;	}    }    ret = 1;out:    if (bn)	BN_free(bn);    if (sum)	BN_free(sum);    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 *///.........这里部分代码省略.........

/* random number r:  0 <= r < range */static int bn_rand_range(int pseudo, BIGNUM *r, const BIGNUM *range)	{	int (*bn_rand)(BIGNUM *, int, int, int) = pseudo ? BN_pseudo_rand : BN_rand;	int n;	int count = 100;	if (range->neg || BN_is_zero(range))		{		BNerr(BN_F_BN_RAND_RANGE, BN_R_INVALID_RANGE);		return 0;		}	n = BN_num_bits(range); /* n > 0 */	/* BN_is_bit_set(range, n - 1) always holds */	if (n == 1)		BN_zero(r);	else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3))		{		/* range = 100..._2,		 * so  3*range (= 11..._2)  is exactly one bit longer than  range */		do			{			if (!bn_rand(r, n + 1, -1, 0)) return 0;			/* If  r < 3*range,  use  r := r MOD range			 * (which is either  r, r - range,  or  r - 2*range).			 * Otherwise, iterate once more.			 * Since  3*range = 11..._2, each iteration succeeds with			 * probability >= .75. */			if (BN_cmp(r ,range) >= 0)				{				if (!BN_sub(r, r, range)) return 0;				if (BN_cmp(r, range) >= 0)					if (!BN_sub(r, r, range)) return 0;				}			if (!--count)				{				BNerr(BN_F_BN_RAND_RANGE, BN_R_TOO_MANY_ITERATIONS);				return 0;				}						}		while (BN_cmp(r, range) >= 0);		}	else		{		do			{			/* range = 11..._2  or  range = 101..._2 */			if (!bn_rand(r, n, -1, 0)) return 0;			if (!--count)				{				BNerr(BN_F_BN_RAND_RANGE, BN_R_TOO_MANY_ITERATIONS);				return 0;				}			}		while (BN_cmp(r, range) >= 0);		}	bn_check_top(r);	return 1;	}

ERL_NIF_TERM mod_exp_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]){/* (Base,Exponent,Modulo,bin_hdr) */    BIGNUM *bn_base = NULL, *bn_exponent = NULL, *bn_modulo = NULL, *bn_result = NULL;    BN_CTX *bn_ctx = NULL;    unsigned char* ptr;    int dlen;    unsigned bin_hdr; /* return type: 0=plain binary, 4: mpint */    unsigned extra_byte;    ERL_NIF_TERM ret;    ASSERT(argc == 4);    if (!get_bn_from_bin(env, argv[0], &bn_base))        goto bad_arg;    if (!get_bn_from_bin(env, argv[1], &bn_exponent))        goto bad_arg;    if (!get_bn_from_bin(env, argv[2], &bn_modulo))        goto bad_arg;    if (!enif_get_uint(env, argv[3], &bin_hdr))        goto bad_arg;    if (bin_hdr != 0 && bin_hdr != 4)        goto bad_arg;    if ((bn_result = BN_new()) == NULL)        goto err;    if ((bn_ctx = BN_CTX_new()) == NULL)        goto err;    if (!BN_mod_exp(bn_result, bn_base, bn_exponent, bn_modulo, bn_ctx))        goto err;    dlen = BN_num_bytes(bn_result);    if (dlen < 0 || dlen > INT_MAX / 8)        goto bad_arg;    extra_byte = bin_hdr && BN_is_bit_set(bn_result, dlen * 8 - 1);    if ((ptr = enif_make_new_binary(env, bin_hdr + extra_byte + (unsigned int)dlen, &ret)) == NULL)        goto err;    if (bin_hdr) {        put_uint32(ptr, extra_byte + (unsigned int)dlen);        ptr[4] = 0; /* extra zeroed byte to ensure a positive mpint */        ptr += bin_hdr + extra_byte;    }    BN_bn2bin(bn_result, ptr);    goto done; bad_arg: err:    ret = enif_make_badarg(env); done:    if (bn_base)        BN_free(bn_base);    if (bn_exponent)        BN_free(bn_exponent);    if (bn_modulo)        BN_free(bn_modulo);    if (bn_result)        BN_free(bn_result);    if (bn_ctx)        BN_CTX_free(bn_ctx);    return ret;}

static inttest_BN_bit(void){    BIGNUM *bn;    int ret = 0;    bn = BN_new();    /* test setting and getting of "word" */    if (!BN_set_word(bn, 1))	return 1;    if (!BN_is_bit_set(bn, 0))	ret += 1;    if (!BN_is_bit_set(bn, 0))	ret += 1;    if (!BN_set_word(bn, 2))	return 1;    if (!BN_is_bit_set(bn, 1))	ret += 1;    if (!BN_set_word(bn, 3))	return 1;    if (!BN_is_bit_set(bn, 0))	ret += 1;    if (!BN_is_bit_set(bn, 1))	ret += 1;    if (!BN_set_word(bn, 0x100))	return 1;    if (!BN_is_bit_set(bn, 8))	ret += 1;    if (!BN_set_word(bn, 0x1000))	return 1;    if (!BN_is_bit_set(bn, 12))	ret += 1;    /* test bitsetting */    if (!BN_set_word(bn, 1))	return 1;    if (!BN_set_bit(bn, 1))	return 1;    if (BN_get_word(bn) != 3)	return 1;    if (!BN_clear_bit(bn, 0))	return 1;    if (BN_get_word(bn) != 2)	return 1;    /* test bitsetting past end of current end */    BN_clear(bn);    if (!BN_set_bit(bn, 12))	return 1;    if (BN_get_word(bn) != 0x1000)	return 1;    /* test bit and byte counting functions */    if (BN_num_bits(bn) != 13)	return 1;    if (BN_num_bytes(bn) != 2)	return 1;    BN_free(bn);    return ret;}

BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) /* Returns 'ret' such that *      ret^2 == a (mod p), * using the Tonelli/Shanks algorithm (cf. Henri Cohen, "A Course * in Algebraic Computational Number Theory", algorithm 1.5.1). * 'p' must be prime! */	{	BIGNUM *ret = in;	int err = 1;	int r;	BIGNUM *A, *b, *q, *t, *x, *y;	int e, i, j;		if (!BN_is_odd(p) || BN_abs_is_word(p, 1))		{		if (BN_abs_is_word(p, 2))			{			if (ret == NULL)				ret = BN_new();			if (ret == NULL)				goto end;			if (!BN_set_word(ret, BN_is_bit_set(a, 0)))				{				if (ret != in)					BN_free(ret);				return NULL;				}			bn_check_top(ret);			return ret;			}		BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME);		return(NULL);		}	if (BN_is_zero(a) || BN_is_one(a))		{		if (ret == NULL)			ret = BN_new();		if (ret == NULL)			goto end;		if (!BN_set_word(ret, BN_is_one(a)))			{			if (ret != in)				BN_free(ret);			return NULL;			}		bn_check_top(ret);		return ret;		}	BN_CTX_start(ctx);	A = BN_CTX_get(ctx);	b = BN_CTX_get(ctx);	q = BN_CTX_get(ctx);	t = BN_CTX_get(ctx);	x = BN_CTX_get(ctx);	y = BN_CTX_get(ctx);	if (y == NULL) goto end;		if (ret == NULL)		ret = BN_new();	if (ret == NULL) goto end;	/* A = a mod p */	if (!BN_nnmod(A, a, p, ctx)) goto end;	/* now write  |p| - 1  as  2^e*q  where  q  is odd */	e = 1;	while (!BN_is_bit_set(p, e))		e++;	/* we'll set  q  later (if needed) */	if (e == 1)		{		/* The easy case:  (|p|-1)/2  is odd, so 2 has an inverse		 * modulo  (|p|-1)/2,  and square roots can be computed		 * directly by modular exponentiation.		 * We have		 *     2 * (|p|+1)/4 == 1   (mod (|p|-1)/2),		 * so we can use exponent  (|p|+1)/4,  i.e.  (|p|-3)/4 + 1.		 */		if (!BN_rshift(q, p, 2)) goto end;		q->neg = 0;		if (!BN_add_word(q, 1)) goto end;		if (!BN_mod_exp(ret, A, q, p, ctx)) goto end;		err = 0;		goto vrfy;		}		if (e == 2)		{		/* |p| == 5  (mod 8)		 *		 * In this case  2  is always a non-square since		 * Legendre(2,p) = (-1)^((p^2-1)/8)  for any odd prime.		 * So if  a  really is a square, then  2*a  is a non-square.		 * Thus for		 *      b := (2*a)^((|p|-5)/8),//.........这里部分代码省略.........

static voidbexp(void){	struct number	*a, *p;	struct number	*r;	bool		neg;	u_int		scale;	p = pop_number();	if (p == NULL) {		return;	}	a = pop_number();	if (a == NULL) {		push_number(p);		return;	}	if (p->scale != 0)		warnx("Runtime warning: non-zero scale in exponent");	normalize(p, 0);	neg = false;	if (BN_cmp(p->number, &zero) < 0) {		neg = true;		negate(p);		scale = bmachine.scale;	} else {		/* Posix bc says min(a.scale * b, max(a.scale, scale) */		u_long	b;		u_int	m;		b = BN_get_word(p->number);		m = max(a->scale, bmachine.scale);		scale = a->scale * (u_int)b;		if (scale > m || (a->scale > 0 && (b == BN_MASK2 ||		    b > UINT_MAX)))			scale = m;	}	if (BN_is_zero(p->number)) {		r = new_number();		bn_check(BN_one(r->number));		normalize(r, scale);	} else {		while (!BN_is_bit_set(p->number, 0)) {			bmul_number(a, a, a);			bn_check(BN_rshift1(p->number, p->number));		}		r = dup_number(a);		normalize(r, scale);		bn_check(BN_rshift1(p->number, p->number));		while (!BN_is_zero(p->number)) {			bmul_number(a, a, a);			if (BN_is_bit_set(p->number, 0))				bmul_number(r, r, a);			bn_check(BN_rshift1(p->number, p->number));		}		if (neg) {			BN_CTX	*ctx;			BIGNUM	*one;			one = BN_new();			bn_checkp(one);			bn_check(BN_one(one));			ctx = BN_CTX_new();			bn_checkp(ctx);			scale_number(one, r->scale + scale);			normalize(r, scale);			bn_check(BN_div(r->number, NULL, one, r->number, ctx));			BN_free(one);			BN_CTX_free(ctx);		} else			normalize(r, scale);	}	push_number(r);	free_number(a);	free_number(p);}

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

static voidbexp(void){	struct number	*a, *p;	struct number	*r;	bool		neg;	u_int		rscale;	p = pop_number();	if (p == NULL)		return;	a = pop_number();	if (a == NULL) {		push_number(p);		return;	}	if (p->scale != 0) {		BIGNUM *i, *f;		i = BN_new();		bn_checkp(i);		f = BN_new();		bn_checkp(f);		split_number(p, i, f);		if (!BN_is_zero(f))			warnx("Runtime warning: non-zero fractional part in exponent");		BN_free(i);		BN_free(f);	}	normalize(p, 0);	neg = false;	if (BN_is_negative(p->number)) {		neg = true;		negate(p);		rscale = bmachine.scale;	} else {		/* Posix bc says min(a.scale * b, max(a.scale, scale) */		u_long b;		u_int m;		b = BN_get_word(p->number);		m = max(a->scale, bmachine.scale);		rscale = a->scale * (u_int)b;		if (rscale > m || (a->scale > 0 && (b == ULONG_MAX ||		    b > UINT_MAX)))			rscale = m;	}	if (BN_is_zero(p->number)) {		r = new_number();		bn_check(BN_one(r->number));		normalize(r, rscale);	} else {		u_int ascale, mscale;		ascale = a->scale;		while (!BN_is_bit_set(p->number, 0)) {			ascale *= 2;			bmul_number(a, a, a, ascale);			bn_check(BN_rshift1(p->number, p->number));		}		r = dup_number(a);		bn_check(BN_rshift1(p->number, p->number));		mscale = ascale;		while (!BN_is_zero(p->number)) {			ascale *= 2;			bmul_number(a, a, a, ascale);			if (BN_is_bit_set(p->number, 0)) {				mscale += ascale;				bmul_number(r, r, a, mscale);			}			bn_check(BN_rshift1(p->number, p->number));		}		if (neg) {			BN_CTX *ctx;			BIGNUM *one;			one = BN_new();			bn_checkp(one);			bn_check(BN_one(one));			ctx = BN_CTX_new();			bn_checkp(ctx);			scale_number(one, r->scale + rscale);			if (BN_is_zero(r->number))				warnx("divide by zero");			else				bn_check(BN_div(r->number, NULL, one,				    r->number, ctx));			BN_free(one);			BN_CTX_free(ctx);			r->scale = rscale;		} else			normalize(r, rscale);	}//.........这里部分代码省略.........

/* Returns -2 for errors because both -1 and 0 are valid results. */int BN_kronecker (const BIGNUM * a, const BIGNUM * b, BN_CTX * ctx){    int i;    int ret = -2;                /* avoid 'uninitialized' warning */    int err = 0;    BIGNUM *A, *B, *tmp;    /* In 'tab', only odd-indexed entries are relevant:     * For any odd BIGNUM n,     *     tab[BN_lsw(n) & 7]     * is $(-1)^{(n^2-1)/8}$ (using TeX notation).     * Note that the sign of n does not matter.     */    static const int tab[8] = { 0, 1, 0, -1, 0, -1, 0, 1 };    bn_check_top (a);    bn_check_top (b);    BN_CTX_start (ctx);    A = BN_CTX_get (ctx);    B = BN_CTX_get (ctx);    if (B == NULL)        goto end;    err = !BN_copy (A, a);    if (err)        goto end;    err = !BN_copy (B, b);    if (err)        goto end;    /*     * Kronecker symbol, imlemented according to Henri Cohen,     * "A Course in Computational Algebraic Number Theory"     * (algorithm 1.4.10).     */    /* Cohen's step 1: */    if (BN_is_zero (B))    {        ret = BN_abs_is_word (A, 1);        goto end;    }    /* Cohen's step 2: */    if (!BN_is_odd (A) && !BN_is_odd (B))    {        ret = 0;        goto end;    }    /* now  B  is non-zero */    i = 0;    while (!BN_is_bit_set (B, i))        i++;    err = !BN_rshift (B, B, i);    if (err)        goto end;    if (i & 1)    {        /* i is odd */        /* (thus  B  was even, thus  A  must be odd!)  */        /* set 'ret' to $(-1)^{(A^2-1)/8}$ */        ret = tab[BN_lsw (A) & 7];    }    else    {        /* i is even */        ret = 1;    }    if (B->neg)    {        B->neg = 0;        if (A->neg)            ret = -ret;    }    /* now  B  is positive and odd, so what remains to be done is     * to compute the Jacobi symbol  (A/B)  and multiply it by 'ret' */    while (1)    {        /* Cohen's step 3: */        /*  B  is positive and odd */        if (BN_is_zero (A))        {            ret = BN_is_one (B) ? ret : 0;            goto end;        }//.........这里部分代码省略.........

// generate_prime sets |out| to a prime with length |bits| such that |out|-1 is// relatively prime to |e|. If |p| is non-NULL, |out| will also not be close to// |p|. |sqrt2| must be 
C++ BN_is_negative函数代码示例
C++ BN_init函数代码示例