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

/* * BN_generate_dsa_nonce generates a random number 0 <= out < range. Unlike * BN_rand_range, it also includes the contents of |priv| and |message| in * the generation so that an RNG failure isn't fatal as long as |priv| * remains secret. This is intended for use in DSA and ECDSA where an RNG * weakness leads directly to private key exposure unless this function is * used. */int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range,                          const BIGNUM *priv, const unsigned char *message,                          size_t message_len, BN_CTX *ctx){    SHA512_CTX sha;    /*     * We use 512 bits of random data per iteration to ensure that we have at     * least |range| bits of randomness.     */    unsigned char random_bytes[64];    unsigned char digest[SHA512_DIGEST_LENGTH];    unsigned done, todo;    /* We generate |range|+8 bytes of random output. */    const unsigned num_k_bytes = BN_num_bytes(range) + 8;    unsigned char private_bytes[96];    unsigned char *k_bytes;    int ret = 0;    k_bytes = OPENSSL_malloc(num_k_bytes);    if (!k_bytes)        goto err;    /* We copy |priv| into a local buffer to avoid exposing its length. */    todo = sizeof(priv->d[0]) * priv->top;    if (todo > sizeof(private_bytes)) {        /*         * No reasonable DSA or ECDSA key should have a private key this         * large and we don't handle this case in order to avoid leaking the         * length of the private key.         */        BNerr(BN_F_BN_GENERATE_DSA_NONCE, BN_R_PRIVATE_KEY_TOO_LARGE);        goto err;    }    memcpy(private_bytes, priv->d, todo);    memset(private_bytes + todo, 0, sizeof(private_bytes) - todo);    for (done = 0; done < num_k_bytes;) {        if (RAND_bytes(random_bytes, sizeof(random_bytes)) != 1)            goto err;        SHA512_Init(&sha);        SHA512_Update(&sha, &done, sizeof(done));        SHA512_Update(&sha, private_bytes, sizeof(private_bytes));        SHA512_Update(&sha, message, message_len);        SHA512_Update(&sha, random_bytes, sizeof(random_bytes));        SHA512_Final(digest, &sha);        todo = num_k_bytes - done;        if (todo > SHA512_DIGEST_LENGTH)            todo = SHA512_DIGEST_LENGTH;        memcpy(k_bytes + done, digest, todo);        done += todo;    }    if (!BN_bin2bn(k_bytes, num_k_bytes, out))        goto err;    if (BN_mod(out, out, range, ctx) != 1)        goto err;    ret = 1; err:    OPENSSL_free(k_bytes);    return ret;}

int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,	const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb)	{	BIGNUM *t;	int found=0;	int i,j,c1=0;	BN_CTX *ctx;	int checks = BN_prime_checks_for_size(bits);	if (bits < 2)		{		/* There are no prime numbers this small. */		BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);		return 0;		}	else if (bits == 2 && safe)		{		/* The smallest safe prime (7) is three bits. */		BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);		return 0;		}	ctx=BN_CTX_new();	if (ctx == NULL) goto err;	BN_CTX_start(ctx);	t = BN_CTX_get(ctx);	if(!t) goto err;loop: 	/* make a random number and set the top and bottom bits */	if (add == NULL)		{		if (!probable_prime(ret,bits)) goto err;		}	else		{		if (safe)			{			if (!probable_prime_dh_safe(ret,bits,add,rem,ctx))				 goto err;			}		else			{			if (!bn_probable_prime_dh(ret,bits,add,rem,ctx))				goto err;			}		}	/* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */	if(!BN_GENCB_call(cb, 0, c1++))		/* aborted */		goto err;	if (!safe)		{		i=BN_is_prime_fasttest_ex(ret,checks,ctx,0,cb);		if (i == -1) goto err;		if (i == 0) goto loop;		}	else		{		/* for "safe prime" generation,		 * check that (p-1)/2 is prime.		 * Since a prime is odd, We just		 * need to divide by 2 */		if (!BN_rshift1(t,ret)) goto err;		for (i=0; i<checks; i++)			{			j=BN_is_prime_fasttest_ex(ret,1,ctx,0,cb);			if (j == -1) goto err;			if (j == 0) goto loop;			j=BN_is_prime_fasttest_ex(t,1,ctx,0,cb);			if (j == -1) goto err;			if (j == 0) goto loop;			if(!BN_GENCB_call(cb, 2, c1-1))				goto err;			/* We have a safe prime test pass */			}		}	/* we have a prime :-) */	found = 1;err:	if (ctx != NULL)		{		BN_CTX_end(ctx);		BN_CTX_free(ctx);		}	bn_check_top(ret);	return found;	}

int BN_mod_exp2_mont(BIGNUM *rr, BIGNUM *a1, BIGNUM *p1, BIGNUM *a2,	     BIGNUM *p2, BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)	{	int i,j,k,bits,bits1,bits2,ret=0,wstart,wend,window,xvalue,yvalue;	int start=1,ts=0,x,y;	BIGNUM *d,*aa1,*aa2,*r;	BIGNUM val[EXP2_TABLE_SIZE][EXP2_TABLE_SIZE];	BN_MONT_CTX *mont=NULL;	bn_check_top(a1);	bn_check_top(p1);	bn_check_top(a2);	bn_check_top(p2);	bn_check_top(m);	if (!(m->d[0] & 1))		{		BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);		return(0);		}	bits1=BN_num_bits(p1);	bits2=BN_num_bits(p2);	if ((bits1 == 0) && (bits2 == 0))		{		BN_one(rr);		return(1);		}	BN_CTX_start(ctx);	d = BN_CTX_get(ctx);	r = BN_CTX_get(ctx);	if (d == NULL || r == NULL) goto err;	bits=(bits1 > bits2)?bits1:bits2;	/* If this is not done, things will break in the montgomery	 * part */	if (in_mont != NULL)		mont=in_mont;	else		{		if ((mont=BN_MONT_CTX_new()) == NULL) goto err;		if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;		}	BN_init(&(val[0][0]));	BN_init(&(val[1][1]));	BN_init(&(val[0][1]));	BN_init(&(val[1][0]));	ts=1;	if (BN_ucmp(a1,m) >= 0)		{		BN_mod(&(val[1][0]),a1,m,ctx);		aa1= &(val[1][0]);		}	else		aa1=a1;	if (BN_ucmp(a2,m) >= 0)		{		BN_mod(&(val[0][1]),a2,m,ctx);		aa2= &(val[0][1]);		}	else		aa2=a2;	if (!BN_to_montgomery(&(val[1][0]),aa1,mont,ctx)) goto err;	if (!BN_to_montgomery(&(val[0][1]),aa2,mont,ctx)) goto err;	if (!BN_mod_mul_montgomery(&(val[1][1]),		&(val[1][0]),&(val[0][1]),mont,ctx))		goto err;#if 0	if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */		window=1;	else if (bits > 250)		window=5;	/* max size of window */	else if (bits >= 120)		window=4;	else		window=3;#else	window=EXP2_TABLE_BITS;#endif	k=1<<window;	for (x=0; x<k; x++)		{		if (x >= 2)			{			BN_init(&(val[x][0]));			BN_init(&(val[x][1]));			if (!BN_mod_mul_montgomery(&(val[x][0]),				&(val[1][0]),&(val[x-1][0]),mont,ctx)) goto err;			if (!BN_mod_mul_montgomery(&(val[x][1]),				&(val[1][0]),&(val[x-1][1]),mont,ctx)) goto err;			}		for (y=2; y<k; y++)			{			BN_init(&(val[x][y]));			if (!BN_mod_mul_montgomery(&(val[x][y]),//.........这里部分代码省略.........

int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d,           BN_CTX *ctx){    int i, nm, nd;    int ret = 0;    BIGNUM *D;    bn_check_top(m);    bn_check_top(d);    if (BN_is_zero(d)) {        BNerr(BN_F_BN_DIV, BN_R_DIV_BY_ZERO);        return (0);    }    if (BN_ucmp(m, d) < 0) {        if (rem != NULL) {            if (BN_copy(rem, m) == NULL)                return (0);        }        if (dv != NULL)            BN_zero(dv);        return (1);    }    BN_CTX_start(ctx);    D = BN_CTX_get(ctx);    if (dv == NULL)        dv = BN_CTX_get(ctx);    if (rem == NULL)        rem = BN_CTX_get(ctx);    if (D == NULL || dv == NULL || rem == NULL)        goto end;    nd = BN_num_bits(d);    nm = BN_num_bits(m);    if (BN_copy(D, d) == NULL)        goto end;    if (BN_copy(rem, m) == NULL)        goto end;    /*     * The next 2 are needed so we can do a dv->d[0]|=1 later since     * BN_lshift1 will only work once there is a value :-)     */    BN_zero(dv);    if (bn_wexpand(dv, 1) == NULL)        goto end;    dv->top = 1;    if (!BN_lshift(D, D, nm - nd))        goto end;    for (i = nm - nd; i >= 0; i--) {        if (!BN_lshift1(dv, dv))            goto end;        if (BN_ucmp(rem, D) >= 0) {            dv->d[0] |= 1;            if (!BN_usub(rem, rem, D))                goto end;        }/* CAN IMPROVE (and have now :=) */        if (!BN_rshift1(D, D))            goto end;    }    rem->neg = BN_is_zero(rem) ? 0 : m->neg;    dv->neg = m->neg ^ d->neg;    ret = 1; end:    BN_CTX_end(ctx);    return (ret);}

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

/* BN_div computes  dv := num / divisor,  rounding towards * zero, and sets up rm  such that  dv*divisor + rm = num  holds. * Thus: *     dv->neg == num->neg ^ divisor->neg  (unless the result is zero) *     rm->neg == num->neg                 (unless the remainder is zero) * If 'dv' or 'rm' is NULL, the respective value is not returned. */int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,	   BN_CTX *ctx)	{	int norm_shift,i,loop;	BIGNUM *tmp,wnum,*snum,*sdiv,*res;	BN_ULONG *resp,*wnump;	BN_ULONG d0,d1;	int num_n,div_n;	int no_branch=0;	/* Invalid zero-padding would have particularly bad consequences	 * so don't just rely on bn_check_top() here	 * (bn_check_top() works only for BN_DEBUG builds) */	if ((num->top > 0 && num->d[num->top - 1] == 0) ||		(divisor->top > 0 && divisor->d[divisor->top - 1] == 0))		{		BNerr(BN_F_BN_DIV,BN_R_NOT_INITIALIZED);		return 0;		}	bn_check_top(num);	bn_check_top(divisor);	if ((BN_get_flags(num, BN_FLG_CONSTTIME) != 0) || (BN_get_flags(divisor, BN_FLG_CONSTTIME) != 0))		{		no_branch=1;		}	bn_check_top(dv);	bn_check_top(rm);	/* bn_check_top(num); */ /* 'num' has been checked already */	/* bn_check_top(divisor); */ /* 'divisor' has been checked already */	if (BN_is_zero(divisor))		{		BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO);		return(0);		}	if (!no_branch && BN_ucmp(num,divisor) < 0)		{		if (rm != NULL)			{ if (BN_copy(rm,num) == NULL) return(0); }		if (dv != NULL) BN_zero(dv);		return(1);		}	BN_CTX_start(ctx);	tmp=BN_CTX_get(ctx);	snum=BN_CTX_get(ctx);	sdiv=BN_CTX_get(ctx);	if (dv == NULL)		res=BN_CTX_get(ctx);	else	res=dv;	if (sdiv == NULL || res == NULL || tmp == NULL || snum == NULL)		goto err;	/* First we normalise the numbers */	norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2);	if (!(BN_lshift(sdiv,divisor,norm_shift))) goto err;	sdiv->neg=0;	norm_shift+=BN_BITS2;	if (!(BN_lshift(snum,num,norm_shift))) goto err;	snum->neg=0;	if (no_branch)		{		/* Since we don't know whether snum is larger than sdiv,		 * we pad snum with enough zeroes without changing its		 * value. 		 */		if (snum->top <= sdiv->top+1) 			{			if (bn_wexpand(snum, sdiv->top + 2) == NULL) goto err;			for (i = snum->top; i < sdiv->top + 2; i++) snum->d[i] = 0;			snum->top = sdiv->top + 2;			}		else			{			if (bn_wexpand(snum, snum->top + 1) == NULL) goto err;			snum->d[snum->top] = 0;			snum->top ++;			}		}	div_n=sdiv->top;	num_n=snum->top;	loop=num_n-div_n;	/* Lets setup a 'window' into snum	 * This is the part that corresponds to the current	 * 'area' being divided */	wnum.neg   = 0;	wnum.d     = &(snum->d[loop]);//.........这里部分代码省略.........

/* * Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'. * This is an array  r[]  of values that are either zero or odd with an * absolute value less than  2^w  satisfying *     scalar = /sum_j r[j]*2^j * where at most one of any  w+1  consecutive digits is non-zero * with the exception that the most significant digit may be only * w-1 zeros away from that next non-zero digit. */signed char *bn_compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len){    int window_val;    signed char *r = NULL;    int sign = 1;    int bit, next_bit, mask;    size_t len = 0, j;    if (BN_is_zero(scalar)) {        r = OPENSSL_malloc(1);        if (r == NULL) {            BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);            goto err;        }        r[0] = 0;        *ret_len = 1;        return r;    }    if (w <= 0 || w > 7) {      /* 'signed char' can represent integers with                                 * absolute values less than 2^7 */        BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);        goto err;    }    bit = 1 << w;               /* at most 128 */    next_bit = bit << 1;        /* at most 256 */    mask = next_bit - 1;        /* at most 255 */    if (BN_is_negative(scalar)) {        sign = -1;    }    if (scalar->d == NULL || scalar->top == 0) {        BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);        goto err;    }    len = BN_num_bits(scalar);    r = OPENSSL_malloc(len + 1); /*                                  * Modified wNAF may be one digit longer than binary representation                                  * (*ret_len will be set to the actual length, i.e. at most                                  * BN_num_bits(scalar) + 1)                                  */    if (r == NULL) {        BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);        goto err;    }    window_val = scalar->d[0] & mask;    j = 0;    while ((window_val != 0) || (j + w + 1 < len)) { /* if j+w+1 >= len,                                                      * window_val will not                                                      * increase */        int digit = 0;        /* 0 <= window_val <= 2^(w+1) */        if (window_val & 1) {            /* 0 < window_val < 2^(w+1) */            if (window_val & bit) {                digit = window_val - next_bit; /* -2^w < digit < 0 */#if 1                           /* modified wNAF */                if (j + w + 1 >= len) {                    /*                     * Special case for generating modified wNAFs:                     * no new bits will be added into window_val,                     * so using a positive digit here will decrease                     * the total length of the representation                     */                    digit = window_val & (mask >> 1); /* 0 < digit < 2^w */                }#endif            } else {

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

/* random number r:  0 <= r < range */static int bn_rand_range(int pseudo, BIGNUM *r, const BIGNUM *range)	{	/* Although the handling of pseudo to chose between BN_rand and	 * BN_pseudo_rand could more cleanly be done via a function pointer, doing	 * so crashes the ADS1.2 compiler used by BREW; see bug 329079 :-( */	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			{#ifdef LIBOPEAY_ASYNCHRONOUS_KEYGENERATION			if (pseudo)			    {			    if (!BN_pseudo_rand(r, n + 1, -1, 0)) return 0;			    }			else#endif			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 */#ifdef LIBOPEAY_ASYNCHRONOUS_KEYGENERATION			if (pseudo)			    {				if (!BN_pseudo_rand(r, n, -1, 0)) return 0;			    }			else#endif			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;	}

/* Must 'OPENSSL_free' the returned data */char *BN_bn2dec(const BIGNUM *a)	{	int i=0,num, ok = 0;	char *buf=NULL;	char *p;	BIGNUM *t=NULL;	BN_ULONG *bn_data=NULL,*lp;	/* get an upper bound for the length of the decimal integer	 * num <= (BN_num_bits(a) + 1) * log(2)	 *     <= 3 * BN_num_bits(a) * 0.1001 + log(2) + 1     (rounding error)	 *     <= BN_num_bits(a)/10 + BN_num_bits/1000 + 1 + 1 	 */	i=BN_num_bits(a)*3;	num=(i/10+i/1000+1)+1;	bn_data=(BN_ULONG *)OPENSSL_malloc((num/BN_DEC_NUM+1)*sizeof(BN_ULONG));	buf=(char *)OPENSSL_malloc(num+3);	if ((buf == NULL) || (bn_data == NULL))		{		BNerr(BN_F_BN_BN2DEC,ERR_R_MALLOC_FAILURE);		goto err;		}	if ((t=BN_dup(a)) == NULL) goto err;#define BUF_REMAIN (num+3 - (size_t)(p - buf))	p=buf;	lp=bn_data;	if (BN_is_zero(t))		{		*(p++)='0';		*(p++)='/0';		}	else		{		if (BN_is_negative(t))			*p++ = '-';		i=0;		while (!BN_is_zero(t))			{			*lp=BN_div_word(t,BN_DEC_CONV);			lp++;			}		lp--;		/* We now have a series of blocks, BN_DEC_NUM chars		 * in length, where the last one needs truncation.		 * The blocks need to be reversed in order. */		BIO_snprintf(p,BUF_REMAIN,BN_DEC_FMT1,*lp);		while (*p) p++;		while (lp != bn_data)			{			lp--;			BIO_snprintf(p,BUF_REMAIN,BN_DEC_FMT2,*lp);			while (*p) p++;			}		}	ok = 1;err:	if (bn_data != NULL) OPENSSL_free(bn_data);	if (t != NULL) BN_free(t);	if (!ok && buf)		{		OPENSSL_free(buf);		buf = NULL;		}	return(buf);	}

/* unsigned subtraction of b from a, a must be larger than b. */int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b){    int max, min, dif;    register BN_ULONG t1, t2, *rp;    register const BN_ULONG *ap, *bp;    int i, carry;    bn_check_top(a);    bn_check_top(b);    max = a->top;    min = b->top;    dif = max - min;    if (dif < 0) {              /* hmm... should not be happening */        BNerr(BN_F_BN_USUB, BN_R_ARG2_LT_ARG3);        return (0);    }    if (bn_wexpand(r, max) == NULL)        return (0);    ap = a->d;    bp = b->d;    rp = r->d;#if 1    carry = 0;    for (i = min; i != 0; i--) {        t1 = *(ap++);        t2 = *(bp++);        if (carry) {            carry = (t1 <= t2);            t1 = (t1 - t2 - 1) & BN_MASK2;        } else {            carry = (t1 < t2);            t1 = (t1 - t2) & BN_MASK2;        }        *(rp++) = t1 & BN_MASK2;    }#else    carry = bn_sub_words(rp, ap, bp, min);    ap += min;    bp += min;    rp += min;#endif    if (carry) {                /* subtracted */        if (!dif)            /* error: a < b */            return 0;        while (dif) {            dif--;            t1 = *(ap++);            t2 = (t1 - 1) & BN_MASK2;            *(rp++) = t2;            if (t1)                break;        }    }    memcpy(rp, ap, sizeof(*rp) * dif);    r->top = max;    r->neg = 0;    bn_correct_top(r);    return (1);}

int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m,	BN_RECP_CTX *recp, BN_CTX *ctx)	{	int i,j,ret=0;	BIGNUM *a,*b,*d,*r;	BN_CTX_start(ctx);	a=BN_CTX_get(ctx);	b=BN_CTX_get(ctx);	if (dv != NULL)		d=dv;	else		d=BN_CTX_get(ctx);	if (rem != NULL)		r=rem;	else		r=BN_CTX_get(ctx);	if (a == NULL || b == NULL || d == NULL || r == NULL) goto err;	if (BN_ucmp(m,&(recp->N)) < 0)		{		if (!BN_zero(d)) return 0;		if (!BN_copy(r,m)) return 0;		BN_CTX_end(ctx);		return(1);		}	/* We want the remainder	 * Given input of ABCDEF / ab	 * we need multiply ABCDEF by 3 digests of the reciprocal of ab	 *	 */	/* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */	i=BN_num_bits(m);	j=recp->num_bits<<1;	if (j>i) i=j;	/* Nr := round(2^i / N) */	if (i != recp->shift)		recp->shift=BN_reciprocal(&(recp->Nr),&(recp->N),			i,ctx); /* BN_reciprocal returns i, or -1 for an error */	if (recp->shift == -1) goto err;	/* d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))|	 *    = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))|	 *   <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|	 *    = |m/N|	 */	if (!BN_rshift(a,m,recp->num_bits)) goto err;	if (!BN_mul(b,a,&(recp->Nr),ctx)) goto err;	if (!BN_rshift(d,b,i-recp->num_bits)) goto err;	d->neg=0;	if (!BN_mul(b,&(recp->N),d,ctx)) goto err;	if (!BN_usub(r,m,b)) goto err;	r->neg=0;#if 1	j=0;	while (BN_ucmp(r,&(recp->N)) >= 0)		{		if (j++ > 2)			{			BNerr(BN_F_BN_MOD_MUL_RECIPROCAL,BN_R_BAD_RECIPROCAL);			goto err;			}		if (!BN_usub(r,r,&(recp->N))) goto err;		if (!BN_add_word(d,1)) goto err;		}#endif	r->neg=BN_is_zero(r)?0:m->neg;	d->neg=m->neg^recp->N.neg;	ret=1;err:	BN_CTX_end(ctx);	return(ret);	}

/* 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);#ifdef OPENSSL_FIPS	/* FIPS 186-3 is picky about how random numbers for keys etc are	 * generated. So we just use the second case which is equivalent to	 * "Generation by Testing Candidates" mentioned in B.1.2 et al.	 */	else if (!FIPS_mode() && !BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3))#else	else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3))#endif		{		/* 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;	}

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

int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,	   BN_CTX *ctx)	{	int norm_shift,i,j,loop;	BIGNUM *tmp,wnum,*snum,*sdiv,*res;	BN_ULONG *resp,*wnump;	BN_ULONG d0,d1;	int num_n,div_n;	bn_check_top(num);	bn_check_top(divisor);	if (BN_is_zero(divisor))		{		BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO);		return(0);		}	if (BN_ucmp(num,divisor) < 0)		{		if (rm != NULL)			{ if (BN_copy(rm,num) == NULL) return(0); }		if (dv != NULL) BN_zero(dv);		return(1);		}	BN_CTX_start(ctx);	tmp=BN_CTX_get(ctx);	snum=BN_CTX_get(ctx);	sdiv=BN_CTX_get(ctx);	if (dv == NULL)		res=BN_CTX_get(ctx);	else	res=dv;	if (sdiv==NULL || res == NULL) goto err;	tmp->neg=0;	/* First we normalise the numbers */	norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2);	if (!(BN_lshift(sdiv,divisor,norm_shift))) goto err;	sdiv->neg=0;	norm_shift+=BN_BITS2;	if (!(BN_lshift(snum,num,norm_shift))) goto err;	snum->neg=0;	div_n=sdiv->top;	num_n=snum->top;	loop=num_n-div_n;	/* Lets setup a 'window' into snum	 * This is the part that corresponds to the current	 * 'area' being divided */	BN_init(&wnum);	wnum.d=	 &(snum->d[loop]);	wnum.top= div_n;	wnum.dmax= snum->dmax+1; /* a bit of a lie */	/* Get the top 2 words of sdiv */	/* i=sdiv->top; */	d0=sdiv->d[div_n-1];	d1=(div_n == 1)?0:sdiv->d[div_n-2];	/* pointer to the 'top' of snum */	wnump= &(snum->d[num_n-1]);	/* Setup to 'res' */	res->neg= (num->neg^divisor->neg);	if (!bn_wexpand(res,(loop+1))) goto err;	res->top=loop;	resp= &(res->d[loop-1]);	/* space for temp */	if (!bn_wexpand(tmp,(div_n+1))) goto err;	if (BN_ucmp(&wnum,sdiv) >= 0)		{		if (!BN_usub(&wnum,&wnum,sdiv)) goto err;		*resp=1;		res->d[res->top-1]=1;		}	else		res->top--;	resp--;	for (i=0; i<loop-1; i++)		{		BN_ULONG q,l0;#if defined(BN_DIV3W) && !defined(NO_ASM)		BN_ULONG bn_div_3_words(BN_ULONG*,BN_ULONG,BN_ULONG);		q=bn_div_3_words(wnump,d1,d0);#else		BN_ULONG n0,n1,rem=0;		n0=wnump[0];		n1=wnump[-1];		if (n0 == d0)			q=BN_MASK2;		else 			/* n0 < d0 */			{#ifdef BN_LLONG			BN_ULLONG t2;//.........这里部分代码省略.........

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

/* solves ax == 1 (mod n) */BIGNUM *BN_mod_inverse(BIGNUM *in, BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)	{	BIGNUM *A,*B,*X,*Y,*M,*D,*R=NULL;	BIGNUM *T,*ret=NULL;	int sign;	bn_check_top(a);	bn_check_top(n);	BN_CTX_start(ctx);	A = BN_CTX_get(ctx);	B = BN_CTX_get(ctx);	X = BN_CTX_get(ctx);	D = BN_CTX_get(ctx);	M = BN_CTX_get(ctx);	Y = BN_CTX_get(ctx);	if (Y == NULL) goto err;	if (in == NULL)		R=BN_new();	else		R=in;	if (R == NULL) goto err;	if (!BN_zero(X)) goto err;	if (!BN_one(Y)) goto err;	if (BN_copy(A,a) == NULL) goto err;	if (BN_copy(B,n) == NULL) goto err;	sign=1;	while (!BN_is_zero(B))		{		if (!BN_div(D,M,A,B,ctx)) goto err;		T=A;		A=B;		B=M;		/* T has a struct, M does not */		if (!BN_mul(T,D,X,ctx)) goto err;		if (!BN_add(T,T,Y)) goto err;		M=Y;		Y=X;		X=T;		sign= -sign;		}	if (sign < 0)		{		if (!BN_sub(Y,n,Y)) goto err;		}	if (BN_is_one(A))		{ if (!BN_mod(R,Y,n,ctx)) goto err; }	else		{		BNerr(BN_F_BN_MOD_INVERSE,BN_R_NO_INVERSE);		goto err;		}	ret=R;err:	if ((ret == NULL) && (in == NULL)) BN_free(R);	BN_CTX_end(ctx);	return(ret);	}

static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom)	{	unsigned char *buf=NULL;	int ret=0,bit,bytes,mask;	if (bits == 0)		{		BN_zero(rnd);		return 1;		}	bytes=(bits+7)/8;	bit=(bits-1)%8;	mask=0xff<<(bit+1);	buf=(unsigned char *)OPENSSL_malloc(bytes);	if (buf == NULL)		{		BNerr(BN_F_BNRAND,ERR_R_MALLOC_FAILURE);		goto err;		}	/* make a random number and set the top and bottom bits */	if (pseudorand)		{		if (RAND_pseudo_bytes(buf, bytes) == -1)			goto err;		}	else		{		if (RAND_bytes(buf, bytes) <= 0)			goto err;		}#if 1	if (pseudorand == 2)		{		/* generate patterns that are more likely to trigger BN		   library bugs */		int i;		unsigned char c;		for (i = 0; i < bytes; i++)			{			RAND_pseudo_bytes(&c, 1);			if (c >= 128 && i > 0)				buf[i] = buf[i-1];			else if (c < 42)				buf[i] = 0;			else if (c < 84)				buf[i] = 255;			}		}#endif	if (top != -1)		{		if (top)			{			if (bit == 0)				{				buf[0]=1;				buf[1]|=0x80;				}			else				{				buf[0]|=(3<<(bit-1));				}			}		else			{			buf[0]|=(1<<bit);			}		}	buf[0] &= ~mask;	if (bottom) /* set bottom bit if requested */		buf[bytes-1]|=1;	if (!BN_bin2bn(buf,bytes,rnd)) goto err;	ret=1;err:	if (buf != NULL)		{		OPENSSL_cleanse(buf,bytes);		OPENSSL_free(buf);		}	bn_check_top(rnd);	return(ret);	}

/* unsigned subtraction of b from a, a must be larger than b. */int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)	{	int max,min,dif;	register BN_ULONG t1,t2,*ap,*bp,*rp;	int i,carry;#if defined(IRIX_CC_BUG) && !defined(LINT)	int dummy;#endif	bn_check_top(a);	bn_check_top(b);	max = a->top;	min = b->top;	dif = max - min;	if (dif < 0)	/* hmm... should not be happening */		{		BNerr(BN_F_BN_USUB,BN_R_ARG2_LT_ARG3);		return(0);		}	if (bn_wexpand(r,max) == NULL) return(0);	ap=a->d;	bp=b->d;	rp=r->d;#if 1	carry=0;	for (i = min; i != 0; i--)		{		t1= *(ap++);		t2= *(bp++);		if (carry)			{			carry=(t1 <= t2);			t1=(t1-t2-1)&BN_MASK2;			}		else			{			carry=(t1 < t2);			t1=(t1-t2)&BN_MASK2;			}#if defined(IRIX_CC_BUG) && !defined(LINT)		dummy=t1;#endif		*(rp++)=t1&BN_MASK2;		}#else	carry=bn_sub_words(rp,ap,bp,min);	ap+=min;	bp+=min;	rp+=min;#endif	if (carry) /* subtracted */		{		if (!dif)			/* error: a < b */			return 0;		while (dif)			{			dif--;			t1 = *(ap++);			t2 = (t1-1)&BN_MASK2;			*(rp++) = t2;			if (t1)				break;			}		}#if 0	TINYCLR_SSL_MEMCPY(rp,ap,sizeof(*rp)*(max-i));#else	if (rp != ap)		{		for (;;)			{			if (!dif--) break;			rp[0]=ap[0];			if (!dif--) break;			rp[1]=ap[1];			if (!dif--) break;			rp[2]=ap[2];			if (!dif--) break;			rp[3]=ap[3];			rp+=4;			ap+=4;			}		}#endif	r->top=max;	r->neg=0;	bn_correct_top(r);	return(1);	}

BN_BLINDING *BN_BLINDING_create_param(BN_BLINDING *b,                                      const BIGNUM *e, BIGNUM *m, BN_CTX *ctx,                                      int (*bn_mod_exp) (BIGNUM *r,                                                         const BIGNUM *a,                                                         const BIGNUM *p,                                                         const BIGNUM *m,                                                         BN_CTX *ctx,                                                         BN_MONT_CTX *m_ctx),                                      BN_MONT_CTX *m_ctx){    int retry_counter = 32;    BN_BLINDING *ret = NULL;    if (b == NULL)        ret = BN_BLINDING_new(NULL, NULL, m);    else        ret = b;    if (ret == NULL)        goto err;    if (ret->A == NULL && (ret->A = BN_new()) == NULL)        goto err;    if (ret->Ai == NULL && (ret->Ai = BN_new()) == NULL)        goto err;    if (e != NULL) {        if (ret->e != NULL)            BN_free(ret->e);        ret->e = BN_dup(e);    }    if (ret->e == NULL)        goto err;    if (bn_mod_exp != NULL)        ret->bn_mod_exp = bn_mod_exp;    if (m_ctx != NULL)        ret->m_ctx = m_ctx;    do {        if (!BN_rand_range(ret->A, ret->mod))            goto err;        if (BN_mod_inverse(ret->Ai, ret->A, ret->mod, ctx) == NULL) {            /*             * this should almost never happen for good RSA keys             */            unsigned long error = ERR_peek_last_error();            if (ERR_GET_REASON(error) == BN_R_NO_INVERSE) {                if (retry_counter-- == 0) {                    BNerr(BN_F_BN_BLINDING_CREATE_PARAM,                          BN_R_TOO_MANY_ITERATIONS);                    goto err;                }                ERR_clear_error();            } else                goto err;        } else            break;    } while (1);    if (ret->bn_mod_exp != NULL && ret->m_ctx != NULL) {        if (!ret->bn_mod_exp            (ret->A, ret->A, ret->e, ret->mod, ctx, ret->m_ctx))            goto err;    } else {        if (!BN_mod_exp(ret->A, ret->A, ret->e, ret->mod, ctx))            goto err;    }    return ret; err:    if (b == NULL && ret != NULL) {        BN_BLINDING_free(ret);        ret = NULL;    }    return ret;}

static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom){    unsigned char *buf = NULL;    int ret = 0, bit, bytes, mask;    time_t tim;    if (bits == 0) {        if (top != BN_RAND_TOP_ANY || bottom != BN_RAND_BOTTOM_ANY)            goto toosmall;        BN_zero(rnd);        return 1;    }    if (bits < 0 || (bits == 1 && top > 0))        goto toosmall;    bytes = (bits + 7) / 8;    bit = (bits - 1) % 8;    mask = 0xff << (bit + 1);    buf = OPENSSL_malloc(bytes);    if (buf == NULL) {        BNerr(BN_F_BNRAND, ERR_R_MALLOC_FAILURE);        goto err;    }    /* make a random number and set the top and bottom bits */    time(&tim);    RAND_add(&tim, sizeof(tim), 0.0);    if (RAND_bytes(buf, bytes) <= 0)        goto err;    if (pseudorand == 2) {        /*         * generate patterns that are more likely to trigger BN library bugs         */        int i;        unsigned char c;        for (i = 0; i < bytes; i++) {            if (RAND_bytes(&c, 1) <= 0)                goto err;            if (c >= 128 && i > 0)                buf[i] = buf[i - 1];            else if (c < 42)                buf[i] = 0;            else if (c < 84)                buf[i] = 255;        }    }    if (top >= 0) {        if (top) {            if (bit == 0) {                buf[0] = 1;                buf[1] |= 0x80;            } else {                buf[0] |= (3 << (bit - 1));            }        } else {            buf[0] |= (1 << bit);        }    }    buf[0] &= ~mask;    if (bottom)                 /* set bottom bit if requested */        buf[bytes - 1] |= 1;    if (!BN_bin2bn(buf, bytes, rnd))        goto err;    ret = 1; err:    OPENSSL_clear_free(buf, bytes);    bn_check_top(rnd);    return (ret);toosmall:    BNerr(BN_F_BNRAND, BN_R_BITS_TOO_SMALL);    return 0;}

int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m,                BN_RECP_CTX *recp, BN_CTX *ctx){    int i, j, ret = 0;    BIGNUM *a, *b, *d, *r;    BN_CTX_start(ctx);    d = (dv != NULL) ? dv : BN_CTX_get(ctx);    r = (rem != NULL) ? rem : BN_CTX_get(ctx);    a = BN_CTX_get(ctx);    b = BN_CTX_get(ctx);    if (b == NULL)        goto err;    if (BN_ucmp(m, &(recp->N)) < 0) {        BN_zero(d);        if (!BN_copy(r, m)) {            BN_CTX_end(ctx);            return 0;        }        BN_CTX_end(ctx);        return 1;    }    /*     * We want the remainder Given input of ABCDEF / ab we need multiply     * ABCDEF by 3 digests of the reciprocal of ab     */    /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */    i = BN_num_bits(m);    j = recp->num_bits << 1;    if (j > i)        i = j;    /* Nr := round(2^i / N) */    if (i != recp->shift)        recp->shift = BN_reciprocal(&(recp->Nr), &(recp->N), i, ctx);    /* BN_reciprocal could have returned -1 for an error */    if (recp->shift == -1)        goto err;    /*-     * d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))|     *    = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))|     *   <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|     *    = |m/N|     */    if (!BN_rshift(a, m, recp->num_bits))        goto err;    if (!BN_mul(b, a, &(recp->Nr), ctx))        goto err;    if (!BN_rshift(d, b, i - recp->num_bits))        goto err;    d->neg = 0;    if (!BN_mul(b, &(recp->N), d, ctx))        goto err;    if (!BN_usub(r, m, b))        goto err;    r->neg = 0;    j = 0;    while (BN_ucmp(r, &(recp->N)) >= 0) {        if (j++ > 2) {            BNerr(BN_F_BN_DIV_RECP, BN_R_BAD_RECIPROCAL);            goto err;        }        if (!BN_usub(r, r, &(recp->N)))            goto err;        if (!BN_add_word(d, 1))            goto err;    }    r->neg = BN_is_zero(r) ? 0 : m->neg;    d->neg = m->neg ^ recp->N.neg;    ret = 1; err:    BN_CTX_end(ctx);    bn_check_top(dv);    bn_check_top(rem);    return ret;}

int BN_div_recp(BIGNUM *dv, BIGNUM *rem, BIGNUM *m, BN_RECP_CTX *recp,	     BN_CTX *ctx)	{	int i,j,ret=0;	BIGNUM *a,*b,*d,*r;	BN_CTX_start(ctx);	a=BN_CTX_get(ctx);	b=BN_CTX_get(ctx);	if (dv != NULL)		d=dv;	else		d=BN_CTX_get(ctx);	if (rem != NULL)		r=rem;	else		r=BN_CTX_get(ctx);	if (a == NULL || b == NULL || d == NULL || r == NULL) goto err;	if (BN_ucmp(m,&(recp->N)) < 0)		{		BN_zero(d);		BN_copy(r,m);		BN_CTX_end(ctx);		return(1);		}	/* We want the remainder	 * Given input of ABCDEF / ab	 * we need multiply ABCDEF by 3 digests of the reciprocal of ab	 *	 */	i=BN_num_bits(m);	j=recp->num_bits<<1;	if (j>i) i=j;	j>>=1;	if (i != recp->shift)		recp->shift=BN_reciprocal(&(recp->Nr),&(recp->N),			i,ctx);	if (!BN_rshift(a,m,j)) goto err;	if (!BN_mul(b,a,&(recp->Nr),ctx)) goto err;	if (!BN_rshift(d,b,i-j)) goto err;	d->neg=0;	if (!BN_mul(b,&(recp->N),d,ctx)) goto err;	if (!BN_usub(r,m,b)) goto err;	r->neg=0;#if 1	j=0;	while (BN_ucmp(r,&(recp->N)) >= 0)		{		if (j++ > 2)			{			BNerr(BN_F_BN_MOD_MUL_RECIPROCAL,BN_R_BAD_RECIPROCAL);			goto err;			}		if (!BN_usub(r,r,&(recp->N))) goto err;		if (!BN_add_word(d,1)) goto err;		}#endif	r->neg=BN_is_zero(r)?0:m->neg;	d->neg=m->neg^recp->N.neg;	ret=1;err:	BN_CTX_end(ctx);	return(ret);	}