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

/* * 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');}

static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,	const BIGNUM *rem, BN_CTX *ctx)	{	int i,ret=0;	BIGNUM *t1,*qadd,*q;	bits--;	BN_CTX_start(ctx);	t1 = BN_CTX_get(ctx);	q = BN_CTX_get(ctx);	qadd = BN_CTX_get(ctx);	if (qadd == NULL) goto err;	if (!BN_rshift1(qadd,padd)) goto err;			if (!BN_rand(q,bits,0,1)) goto err;	/* we need ((rnd-rem) % add) == 0 */	if (!BN_mod(t1,q,qadd,ctx)) goto err;	if (!BN_sub(q,q,t1)) goto err;	if (rem == NULL)		{ if (!BN_add_word(q,1)) goto err; }	else		{		if (!BN_rshift1(t1,rem)) goto err;		if (!BN_add(q,q,t1)) goto err;		}	/* we now have a random number 'rand' to test. */	if (!BN_lshift1(p,q)) goto err;	if (!BN_add_word(p,1)) goto err;loop:	for (i=1; i<NUMPRIMES; i++)		{		/* check that p and q are prime */		/* check that for p and q		 * gcd(p-1,primes) == 1 (except for 2) */		if ((BN_mod_word(p,(BN_ULONG)primes[i]) == 0) ||			(BN_mod_word(q,(BN_ULONG)primes[i]) == 0))			{			if (!BN_add(p,p,padd)) goto err;			if (!BN_add(q,q,qadd)) goto err;			goto loop;			}		}	ret=1;err:	BN_CTX_end(ctx);	bn_check_top(p);	return(ret);	}

/* * 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');}

int DH_check(const DH *dh, int *ret){    int ok = 0;    BN_CTX *ctx = NULL;    BN_ULONG l;    BIGNUM *q = NULL;    *ret = 0;    ctx = BN_CTX_new();    if (ctx == NULL)        goto err;    q = BN_new();    if (q == NULL)        goto err;    if (BN_is_word(dh->g, DH_GENERATOR_2)) {        l = BN_mod_word(dh->p, 24);        if (l != 11)            *ret |= DH_NOT_SUITABLE_GENERATOR;    }# if 0    else if (BN_is_word(dh->g, DH_GENERATOR_3)) {        l = BN_mod_word(dh->p, 12);        if (l != 5)            *ret |= DH_NOT_SUITABLE_GENERATOR;    }# endif    else if (BN_is_word(dh->g, DH_GENERATOR_5)) {        l = BN_mod_word(dh->p, 10);        if ((l != 3) && (l != 7))            *ret |= DH_NOT_SUITABLE_GENERATOR;    } else        *ret |= DH_UNABLE_TO_CHECK_GENERATOR;    if (!BN_is_prime_ex(dh->p, BN_prime_checks, ctx, NULL))        *ret |= DH_CHECK_P_NOT_PRIME;    else {        if (!BN_rshift1(q, dh->p))            goto err;        if (!BN_is_prime_ex(q, BN_prime_checks, ctx, NULL))            *ret |= DH_CHECK_P_NOT_SAFE_PRIME;    }    ok = 1; err:    if (ctx != NULL)        BN_CTX_free(ctx);    if (q != NULL)        BN_free(q);    return (ok);}

static intprobable_prime(BIGNUM *rnd, int bits){	int i;	prime_t mods[NUMPRIMES];	BN_ULONG delta, maxdelta;again:	if (!BN_rand(rnd, bits, 1, 1))		return (0);	/* we now have a random number 'rand' to test. */	for (i = 1; i < NUMPRIMES; i++)		mods[i] = (prime_t)BN_mod_word(rnd, (BN_ULONG)primes[i]);	maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];	delta = 0;loop:	for (i = 1; i < NUMPRIMES; i++) {		/* check that rnd is not a prime and also		 * that gcd(rnd-1,primes) == 1 (except for 2) */		if (((mods[i] + delta) % primes[i]) <= 1) {			delta += 2;			if (delta > maxdelta)				goto again;			goto loop;		}	}	if (!BN_add_word(rnd, delta))		return (0);	bn_check_top(rnd);	return (1);}

static int probable_prime(BIGNUM *rnd, int bits)	{	int i;	BN_ULONG mods[NUMPRIMES];	BN_ULONG delta,d;again:	if (!BN_rand(rnd,bits,1,1)) return(0);	/* we now have a random number 'rand' to test. */	for (i=1; i<NUMPRIMES; i++)		mods[i]=BN_mod_word(rnd,(BN_ULONG)primes[i]);	delta=0;	loop: for (i=1; i<NUMPRIMES; i++)		{		/* check that rnd is not a prime and also		 * that gcd(rnd-1,primes) == 1 (except for 2) */		if (((mods[i]+delta)%primes[i]) <= 1)			{			d=delta;			delta+=2;			/* perhaps need to check for overflow of			 * delta (but delta can be up to 2^32)			 * 21-May-98 eay - added overflow check */			if (delta < d) goto again;			goto loop;			}		}	if (!BN_add_word(rnd,delta)) return(0);	return(1);	}

int bn_probable_prime_dh_retry(BIGNUM *rnd, int bits, BN_CTX *ctx){    int i;    int ret = 0; loop:    if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD))        goto err;    /* we now have a random number 'rand' to test. */    for (i = 1; 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_check_top(rnd);    return (ret);}

static int base58encode(char *input, char *base58encode) {    BIGNUM *bnfromhex = BN_new();    BN_hex2bn(&bnfromhex, input);    char *codeString = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";    char buildString[35];    int lengthofstring = 0;    int startat = 34;    while(BN_is_zero(bnfromhex) != 1) {      int rem = BN_mod_word(bnfromhex, 58);      buildString[startat] = codeString[rem];      BN_div_word(bnfromhex, 58);      lengthofstring++;      startat--;    }    startat ++;        int j = 0;    int i;    for (i = startat; i < lengthofstring; i++) {      base58encode[j] = buildString[i];      j++;    }    BN_free(bnfromhex);    return NOERROR;}

static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add,                             const BIGNUM *rem, BN_CTX *ctx) {  int i, ret = 0;  BIGNUM *t1;  BN_CTX_start(ctx);  if ((t1 = BN_CTX_get(ctx)) == NULL) {    goto err;  }  if (!BN_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) {    goto err;  }  /* we need ((rnd-rem) % add) == 0 */  if (!BN_mod(t1, rnd, add, ctx)) {    goto err;  }  if (!BN_sub(rnd, rnd, t1)) {    goto err;  }  if (rem == NULL) {    if (!BN_add_word(rnd, 1)) {      goto err;    }  } else {    if (!BN_add(rnd, rnd, rem)) {      goto err;    }  }  /* we now have a random number 'rand' to test. */loop:  for (i = 1; 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) {      if (!BN_add(rnd, rnd, add)) {        goto err;      }      goto loop;    }  }  ret = 1;err:  BN_CTX_end(ctx);  return ret;}

int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx,                            int do_trial_division, BN_GENCB *cb) {  if (BN_cmp(a, BN_value_one()) <= 0) {    return 0;  }  /* first look for small factors */  if (!BN_is_odd(a)) {    /* a is even => a is prime if and only if a == 2 */    return BN_is_word(a, 2);  }  /* Enhanced Miller-Rabin does not work for three. */  if (BN_is_word(a, 3)) {    return 1;  }  if (do_trial_division) {    for (int i = 1; i < NUMPRIMES; i++) {      BN_ULONG mod = BN_mod_word(a, primes[i]);      if (mod == (BN_ULONG)-1) {        return -1;      }      if (mod == 0) {        return BN_is_word(a, primes[i]);      }    }    if (!BN_GENCB_call(cb, 1, -1)) {      return -1;    }  }  int ret = -1;  BN_CTX *ctx_allocated = NULL;  if (ctx == NULL) {    ctx_allocated = BN_CTX_new();    if (ctx_allocated == NULL) {      return -1;    }    ctx = ctx_allocated;  }  enum bn_primality_result_t result;  if (!BN_enhanced_miller_rabin_primality_test(&result, a, checks, ctx, cb)) {    goto err;  }  ret = (result == bn_probably_prime);err:  BN_CTX_free(ctx_allocated);  return ret;}

int CPK_MAP_str2index(const X509_ALGOR *algor, const char *str, int *index){	int ret = 0;	const EVP_MD *md;	unsigned char dgst[EVP_MAX_MD_SIZE];	unsigned int dgstlen;	BIGNUM *bn = NULL;	int i, num_index, num_subset;		OPENSSL_assert(algor);	OPENSSL_assert(algor->algorithm);	OPENSSL_assert(str);	OPENSSL_assert(strlen(str) > 0);		if (!CPK_MAP_is_valid(algor)) {		CPKerr(CPK_F_CPK_MAP_STR2INDEX, CPK_R_INVALID_MAP_ALGOR);		goto err;	}	if (!index) {		ret = CPK_MAP_num_index(algor);		goto err;	}	if (!(md = EVP_get_digestbyobj(algor->algorithm))) {		CPKerr(CPK_F_CPK_MAP_STR2INDEX, ERR_R_EVP_LIB);		goto err;	}	if (!EVP_Digest(str, strlen(str), dgst, &dgstlen, md, NULL)) {		CPKerr(CPK_F_CPK_MAP_STR2INDEX, ERR_R_EVP_LIB);		return 0;	}	if (!(bn = BN_new())) {		CPKerr(CPK_F_CPK_MAP_STR2INDEX, ERR_R_BN_LIB);		goto err;	}	if (!BN_bin2bn(dgst, dgstlen, bn)) {		CPKerr(CPK_F_CPK_MAP_STR2INDEX, ERR_R_BN_LIB);		goto err;	}	num_index = CPK_MAP_num_index(algor);	num_subset = CPK_MAP_num_subset(algor);		for (i = 0; i < num_index; i++) {		int r = BN_mod_word(bn, num_subset);		index[i] = num_subset * i + r;	}	ret = num_index;err:		if (bn) BN_free(bn);	return ret;}

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

/* See FIPS 186-4 C.3.1 Miller Rabin Probabilistic Primality Test. */int BN_is_prime_fasttest_ex(const BIGNUM *w, int checks, BN_CTX *ctx_passed,                            int do_trial_division, BN_GENCB *cb){    int i, status, ret = -1;    BN_CTX *ctx = NULL;    /* w must be bigger than 1 */    if (BN_cmp(w, BN_value_one()) <= 0)        return 0;    /* w must be odd */    if (BN_is_odd(w)) {        /* Take care of the really small prime 3 */        if (BN_is_word(w, 3))            return 1;    } else {        /* 2 is the only even prime */        return BN_is_word(w, 2);    }    /* first look for small factors */    if (do_trial_division) {        for (i = 1; i < NUMPRIMES; i++) {            BN_ULONG mod = BN_mod_word(w, primes[i]);            if (mod == (BN_ULONG)-1)                return -1;            if (mod == 0)                return BN_is_word(w, primes[i]);        }        if (!BN_GENCB_call(cb, 1, -1))            return -1;    }    if (ctx_passed != NULL)        ctx = ctx_passed;    else if ((ctx = BN_CTX_new()) == NULL)        goto err;    ret = bn_miller_rabin_is_prime(w, checks, ctx, cb, 0, &status);    if (!ret)        goto err;    ret = (status == BN_PRIMETEST_PROBABLY_PRIME);err:    if (ctx_passed == NULL)        BN_CTX_free(ctx);    return ret;}

static intprobable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem,    BN_CTX *ctx){	int i, ret = 0;	BIGNUM *t1;	BN_CTX_start(ctx);	if ((t1 = BN_CTX_get(ctx)) == NULL)		goto err;	if (!BN_rand(rnd, bits, 0, 1))		goto err;	/* we need ((rnd-rem) % add) == 0 */	if (!BN_mod(t1, rnd, add, ctx))		goto err;	if (!BN_sub(rnd, rnd, t1))		goto err;	if (rem == NULL) {		if (!BN_add_word(rnd, 1))			goto err;	} else {		if (!BN_add(rnd, rnd, rem))			goto err;	}	/* we now have a random number 'rand' to test. */loop:	for (i = 1; i < NUMPRIMES; i++) {		/* check that rnd is a prime */		if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {			if (!BN_add(rnd, rnd, add))				goto err;			goto loop;		}	}	ret = 1;err:	BN_CTX_end(ctx);	bn_check_top(rnd);	return (ret);}

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

/** * public static native boolean BN_mod_word(int, int) */static BN_ULONG NativeBN_BN_mod_word(JNIEnv* env, jclass cls, BIGNUM *a, BN_ULONG w) {    if (!oneValidHandle(env, a)) return FALSE;    return BN_mod_word(a, w);}

static int probable_prime(BIGNUM *rnd, int bits)	{	int i;	prime_t mods[NUMPRIMES];	BN_ULONG delta;	BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES-1];	char is_single_word = bits <= BN_BITS2;again:	if (!BN_rand(rnd,bits,1,1)) return(0);	/* we now have a random number 'rnd' to test. */	for (i=1; i<NUMPRIMES; i++)		mods[i]=(prime_t)BN_mod_word(rnd,(BN_ULONG)primes[i]);	/* If bits is so small that it fits into a single word then we	 * additionally don't want to exceed that many bits. */	if (is_single_word)		{		BN_ULONG size_limit = (((BN_ULONG) 1) << bits) - BN_get_word(rnd) - 1;		if (size_limit < maxdelta)			maxdelta = size_limit;		}	delta=0;loop:	if (is_single_word)		{		BN_ULONG rnd_word = BN_get_word(rnd);		/* In the case that the candidate prime is a single word then		 * we check that:		 *   1) It's greater than primes[i] because we shouldn't reject		 *      3 as being a prime number because it's a multiple of		 *      three.		 *   2) That it's not a multiple of a known prime. We don't		 *      check that rnd-1 is also coprime to all the known		 *      primes because there aren't many small primes where		 *      that's true. */		for (i=1; i<NUMPRIMES && primes[i]<rnd_word; i++)			{			if ((mods[i]+delta)%primes[i] == 0)				{				delta+=2;				if (delta > maxdelta) goto again;				goto loop;				}			}		}	else		{		for (i=1; i<NUMPRIMES; i++)			{			/* check that rnd is not a prime and also			 * that gcd(rnd-1,primes) == 1 (except for 2) */			if (((mods[i]+delta)%primes[i]) <= 1)				{				delta+=2;				if (delta > maxdelta) goto again;				goto loop;				}			}		}	if (!BN_add_word(rnd,delta)) return(0);	if (BN_num_bits(rnd) != bits)		goto again;	bn_check_top(rnd);	return(1);	}

static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods){    int i;    BN_ULONG delta;    BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];    char is_single_word = bits <= BN_BITS2; again:    if (!BN_priv_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD))        return 0;    /* we now have a random number 'rnd' to test. */    for (i = 1; i < NUMPRIMES; i++) {        BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);        if (mod == (BN_ULONG)-1)            return 0;        mods[i] = (prime_t) mod;    }    /*     * If bits is so small that it fits into a single word then we     * additionally don't want to exceed that many bits.     */    if (is_single_word) {        BN_ULONG size_limit;        if (bits == BN_BITS2) {            /*             * Shifting by this much has undefined behaviour so we do it a             * different way             */            size_limit = ~((BN_ULONG)0) - BN_get_word(rnd);        } else {            size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1;        }        if (size_limit < maxdelta)            maxdelta = size_limit;    }    delta = 0; loop:    if (is_single_word) {        BN_ULONG rnd_word = BN_get_word(rnd);        /*-         * In the case that the candidate prime is a single word then         * we check that:         *   1) It's greater than primes[i] because we shouldn't reject         *      3 as being a prime number because it's a multiple of         *      three.         *   2) That it's not a multiple of a known prime. We don't         *      check that rnd-1 is also coprime to all the known         *      primes because there aren't many small primes where         *      that's true.         */        for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) {            if ((mods[i] + delta) % primes[i] == 0) {                delta += 2;                if (delta > maxdelta)                    goto again;                goto loop;            }        }    } else {        for (i = 1; i < NUMPRIMES; i++) {            /*             * check that rnd is not a prime and also that gcd(rnd-1,primes)             * == 1 (except for 2)             */            if (((mods[i] + delta) % primes[i]) <= 1) {                delta += 2;                if (delta > maxdelta)                    goto again;                goto loop;            }        }    }    if (!BN_add_word(rnd, delta))        return 0;    if (BN_num_bits(rnd) != bits)        goto again;    bn_check_top(rnd);    return 1;}

int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,                            int do_trial_division, BN_GENCB *cb){    int i, j, ret = -1;    int k;    BN_CTX *ctx = NULL;    BIGNUM *A1, *A1_odd, *check; /* taken from ctx */    BN_MONT_CTX *mont = 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))        /* a is even => a is prime if and only if a == 2 */        return BN_is_word(a, 2);    if (do_trial_division) {        for (i = 1; i < NUMPRIMES; i++) {            BN_ULONG mod = BN_mod_word(a, primes[i]);            if (mod == (BN_ULONG)-1)                goto err;            if (mod == 0)                return BN_is_word(a, primes[i]);        }        if (!BN_GENCB_call(cb, 1, -1))            goto err;    }    if (ctx_passed != NULL)        ctx = ctx_passed;    else if ((ctx = BN_CTX_new()) == NULL)        goto err;    BN_CTX_start(ctx);    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_priv_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 (!BN_GENCB_call(cb, 1, i))            goto err;    }    ret = 1; err:    if (ctx != NULL) {        BN_CTX_end(ctx);        if (ctx_passed == NULL)            BN_CTX_free(ctx);    }    BN_MONT_CTX_free(mont);    return ret;}

unsigned BN::operator%(unsigned mod) const{	BN result(*this);	return (unsigned)BN_mod_word(PTR(result.dp), mod);}

static int probable_prime(BIGNUM *rnd, int bits) {  int i;  uint16_t mods[NUMPRIMES];  BN_ULONG delta;  BN_ULONG maxdelta = BN_MASK2 - primes[NUMPRIMES - 1];  char is_single_word = bits <= BN_BITS2;again:  if (!BN_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD)) {    return 0;  }  // we now have a random number 'rnd' to test.  for (i = 1; i < NUMPRIMES; i++) {    BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);    if (mod == (BN_ULONG)-1) {      return 0;    }    mods[i] = (uint16_t)mod;  }  // If bits is so small that it fits into a single word then we  // additionally don't want to exceed that many bits.  if (is_single_word) {    BN_ULONG size_limit;    if (bits == BN_BITS2) {      // Avoid undefined behavior.      size_limit = ~((BN_ULONG)0) - BN_get_word(rnd);    } else {      size_limit = (((BN_ULONG)1) << bits) - BN_get_word(rnd) - 1;    }    if (size_limit < maxdelta) {      maxdelta = size_limit;    }  }  delta = 0;loop:  if (is_single_word) {    BN_ULONG rnd_word = BN_get_word(rnd);    // In the case that the candidate prime is a single word then    // we check that:    //   1) It's greater than primes[i] because we shouldn't reject    //      3 as being a prime number because it's a multiple of    //      three.    //   2) That it's not a multiple of a known prime. We don't    //      check that rnd-1 is also coprime to all the known    //      primes because there aren't many small primes where    //      that's true.    for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) {      if ((mods[i] + delta) % primes[i] == 0) {        delta += 2;        if (delta > maxdelta) {          goto again;        }        goto loop;      }    }  } else {    for (i = 1; i < NUMPRIMES; i++) {      // check that rnd is not a prime and also      // that gcd(rnd-1,primes) == 1 (except for 2)      if (((mods[i] + delta) % primes[i]) <= 1) {        delta += 2;        if (delta > maxdelta) {          goto again;        }        goto loop;      }    }  }  if (!BN_add_word(rnd, delta)) {    return 0;  }  if (BN_num_bits(rnd) != (unsigned)bits) {    goto again;  }  return 1;}

static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,                                  const BIGNUM *rem, BN_CTX *ctx) {  int i, ret = 0;  BIGNUM *t1, *qadd, *q;  bits--;  BN_CTX_start(ctx);  t1 = BN_CTX_get(ctx);  q = BN_CTX_get(ctx);  qadd = BN_CTX_get(ctx);  if (qadd == NULL) {    goto err;  }  if (!BN_rshift1(qadd, padd)) {    goto err;  }  if (!BN_rand(q, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD)) {    goto err;  }  /* we need ((rnd-rem) % add) == 0 */  if (!BN_mod(t1, q, qadd, ctx)) {    goto err;  }  if (!BN_sub(q, q, t1)) {    goto err;  }  if (rem == NULL) {    if (!BN_add_word(q, 1)) {      goto err;    }  } else {    if (!BN_rshift1(t1, rem)) {      goto err;    }    if (!BN_add(q, q, t1)) {      goto err;    }  }  /* we now have a random number 'rand' to test. */  if (!BN_lshift1(p, q)) {    goto err;  }  if (!BN_add_word(p, 1)) {    goto err;  }loop:  for (i = 1; i < NUMPRIMES; i++) {    /* check that p and q are prime */    /* check that for p and q     * gcd(p-1,primes) == 1 (except for 2) */    BN_ULONG pmod = BN_mod_word(p, (BN_ULONG)primes[i]);    BN_ULONG qmod = BN_mod_word(q, (BN_ULONG)primes[i]);    if (pmod == (BN_ULONG)-1 || qmod == (BN_ULONG)-1) {      goto err;    }    if (pmod == 0 || qmod == 0) {      if (!BN_add(p, p, padd)) {        goto err;      }      if (!BN_add(q, q, qadd)) {        goto err;      }      goto loop;    }  }  ret = 1;err:  BN_CTX_end(ctx);  return ret;}

extern "C" BN_ULONG Java_java_math_NativeBN_BN_1mod_1word(JNIEnv* env, jclass, jlong a, BN_ULONG w) {  if (!oneValidHandle(env, a)) return 0;  int result = BN_mod_word(toBigNum(a), w);  throwExceptionIfNecessary(env);  return result;}

int DH_check(const DH *dh, int *ret){    int ok = 0;    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_NOT_SUITABLE_GENERATOR;        else if (BN_cmp(dh->g, dh->p) >= 0)            *ret |= DH_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_NOT_SUITABLE_GENERATOR;        }        if (!BN_is_prime_ex(dh->q, BN_prime_checks, ctx, NULL))            *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 != 11)            *ret |= DH_NOT_SUITABLE_GENERATOR;    }#if 0    else if (BN_is_word(dh->g, DH_GENERATOR_3)) {        l = BN_mod_word(dh->p, 12);        if (l != 5)            *ret |= DH_NOT_SUITABLE_GENERATOR;    }#endif    else if (BN_is_word(dh->g, DH_GENERATOR_5)) {        l = BN_mod_word(dh->p, 10);        if ((l != 3) && (l != 7))            *ret |= DH_NOT_SUITABLE_GENERATOR;    } else        *ret |= DH_UNABLE_TO_CHECK_GENERATOR;    if (!BN_is_prime_ex(dh->p, BN_prime_checks, ctx, NULL))        *ret |= DH_CHECK_P_NOT_PRIME;    else if (!dh->q) {        if (!BN_rshift1(t1, dh->p))            goto err;        if (!BN_is_prime_ex(t1, BN_prime_checks, ctx, NULL))            *ret |= DH_CHECK_P_NOT_SAFE_PRIME;    }    ok = 1; err:    if (ctx != NULL) {        BN_CTX_end(ctx);        BN_CTX_free(ctx);    }    return (ok);}

BN& BN::operator%=(unsigned mod){	BN_ULONG result = BN_mod_word(BNP, mod);	BN_set_word(BNP, result);	return *this;}

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

int VN_BN_jacobi( const BIGNUM *za, const BIGNUM *zn, int *jacobi, BN_CTX *ctx ){	int ret = 0, e = 0, s = 0, mod = -1, amod = -1;	BIGNUM zero, three, za1, zn1;	BN_init( &zero );	BN_init( &three );	BN_init( &za1 );	BN_init( &zn1 );	BN_set_word( &zero, 0 );	BN_set_word( &three, 3 );	BN_copy( &za1, za );	BN_copy( &zn1, zn );	for( *jacobi = 1; 0 == ret; )	{		if( ! BN_is_odd( &zn1 ) ) { ret = -1; break; }		if( BN_cmp( &zn1, &three ) < 0 ) { ret = -1; break; }		if( ( BN_cmp( &za1, &zn1 ) > 0 ) || ( BN_cmp( &za1, &zero ) < 0 ) ) { ret = -1; break; }		if( BN_is_zero( &za1 ) ) break;         // step1		if( BN_is_one( &za1 ) ) break;          // step2		for( e = 0; ; e++ )                     // step3		{			if( BN_is_odd( &za1 ) ) break;			BN_rshift1( &za1, &za1 );		}		if( 0 == ( e % 2 ) )                    // step4		{			s = 1;		} else {			mod = BN_mod_word( &zn1, 8 );			if( 1 == mod || 7 == mod ) s = 1;			if( 3 == mod || 5 == mod ) s = -1;		}		amod = BN_mod_word( &za1, 4 );          // step5		mod =  BN_mod_word( &zn1, 4 );		if( 3 == mod && 3 == amod ) s = - s;		BN_mod( &zn1, &zn1, &za1, ctx );        // step6		*jacobi = ( *jacobi ) * s;              // step7		if( BN_is_one( &za1 ) ) break;		BN_swap( &za1, &zn1 );	}	BN_free( &zero );	BN_free( &three );	BN_free( &za1 );	BN_free( &zn1 );	return ret;}