/* wvalue will be an odd number < 2^window */		if (!BN_mod_mul_montgomery(r,r,&(val[wvalue>>1]),mont,ctx))			goto err;		/* move the 'window' down further */		wstart-=wend+1;		wvalue=0;		start=0;		if (wstart < 0) break;		}	if (!BN_from_montgomery(rr,r,mont,ctx)) goto err;	ret=1;err:	if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);	BN_CTX_end(ctx);	for (i=0; i<ts; i++)		BN_clear_free(&(val[i]));	return(ret);	}/* BN_mod_exp_mont_consttime() stores the precomputed powers in a specific layout * so that accessing any of these table values shows the same access pattern as far * as cache lines are concerned.  The following functions are used to transfer a BIGNUM * from/to that table. */static int MOD_EXP_CTIME_COPY_TO_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx, int width)	{	size_t i, j;	if (bn_wexpand(b, top) == NULL)		return 0;	while (b->top < top)		{		b->d[b->top++] = 0;		}		for (i = 0, j=idx; i < top * sizeof b->d[0]; i++, j+=width)		{		buf[j] = ((unsigned char*)b->d)[i];		}	bn_fix_top(b);	return 1;	}static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx, int width)	{	size_t i, j;	if (bn_wexpand(b, top) == NULL)		return 0;	for (i=0, j=idx; i < top * sizeof b->d[0]; i++, j+=width)		{		((unsigned char*)b->d)[i] = buf[j];		}	b->top = top;	bn_fix_top(b);	return 1;	}	/* Given a pointer value, compute the next address that is a cache line multiple. */#define MOD_EXP_CTIME_ALIGN(x_) \	((unsigned char*)(x_) + (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - (((BN_ULONG)(x_)) & (MOD_EXP_CTIME_MIN_CACHE_LINE_MASK))))/* This variant of BN_mod_exp_mont() uses fixed windows and the special * precomputation memory layout to limit data-dependency to a minimum * to protect secret exponents (cf. the hyper-threading timing attacks * pointed out by Colin Percival, * http://www.daemonology.net/hyperthreading-considered-harmful/) */int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,		    const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)	{	int i,bits,ret=0,idx,window,wvalue;	int top; 	BIGNUM *r;	const BIGNUM *aa;	BN_MONT_CTX *mont=NULL;	int numPowers;	unsigned char *powerbufFree=NULL;	int powerbufLen = 0;	unsigned char *powerbuf=NULL;	BIGNUM *computeTemp=NULL, *am=NULL;	bn_check_top(a);	bn_check_top(p);	bn_check_top(m);	top = m->top;	if (!(m->d[0] & 1))		{		BNerr(BN_F_BN_MOD_EXP_MONT_CONSTTIME,BN_R_CALLED_WITH_EVEN_MODULUS);		return(0);		}	bits=BN_num_bits(p);	if (bits == 0)		{		ret = BN_one(rr);		return ret;		} 	/* Initialize BIGNUM context and allocate intermediate result */	BN_CTX_start(ctx);	r = BN_CTX_get(ctx);	if (r == NULL) goto err;	/* Allocate a montgomery context if it was not supplied by the caller.	 * 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;		}	/* Get the window size to use with size of p. */	window = BN_window_bits_for_ctime_exponent_size(bits);	/* Allocate a buffer large enough to hold all of the pre-computed	 * powers of a.	 */	numPowers = 1 << window;	powerbufLen = sizeof(m->d[0])*top*numPowers;	if ((powerbufFree=(unsigned char*)OPENSSL_malloc(powerbufLen+MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH)) == NULL)		goto err;			powerbuf = MOD_EXP_CTIME_ALIGN(powerbufFree);	memset(powerbuf, 0, powerbufLen); 	/* Initialize the intermediate result. Do this early to save double conversion,	 * once each for a^0 and intermediate result.	 */ 	if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;	if (!MOD_EXP_CTIME_COPY_TO_PREBUF(r, top, powerbuf, 0, numPowers)) goto err;	/* Initialize computeTemp as a^1 with montgomery precalcs */	computeTemp = BN_CTX_get(ctx);	am = BN_CTX_get(ctx);	if (computeTemp==NULL || am==NULL) goto err;	if (a->neg || BN_ucmp(a,m) >= 0)		{		if (!BN_mod(am,a,m,ctx))			goto err;		aa= am;		}	else		aa=a;	if (!BN_to_montgomery(am,aa,mont,ctx)) goto err;	if (!BN_copy(computeTemp, am)) goto err;	if (!MOD_EXP_CTIME_COPY_TO_PREBUF(am, top, powerbuf, 1, numPowers)) goto err;	/* If the window size is greater than 1, then calculate	 * val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1)	 * (even powers could instead be computed as (a^(i/2))^2	 * to use the slight performance advantage of sqr over mul).	 */	if (window > 1)		{		for (i=2; i<numPowers; i++)			{			/* Calculate a^i = a^(i-1) * a */			if (!BN_mod_mul_montgomery(computeTemp,am,computeTemp,mont,ctx))				goto err;			if (!MOD_EXP_CTIME_COPY_TO_PREBUF(computeTemp, top, powerbuf, i, numPowers)) goto err;			}		} 	/* Adjust the number of bits up to a multiple of the window size. 	 * If the exponent length is not a multiple of the window size, then 	 * this pads the most significant bits with zeros to normalize the 	 * scanning loop to there's no special cases. 	 * 	 * * NOTE: Making the window size a power of two less than the native	 * * word size ensures that the padded bits won't go past the last 	 * * word in the internal BIGNUM structure. Going past the end will 	 * * still produce the correct result, but causes a different branch 	 * * to be taken in the BN_is_bit_set function. 	 */ 	bits = ((bits+window-1)/window)*window; 	idx=bits-1;	/* The top bit of the window */ 	/* Scan the exponent one window at a time starting from the most 	 * significant bits. 	 */ 	while (idx >= 0)  		{ 		wvalue=0; /* The 'value' of the window */ 		 		/* Scan the window, squaring the result as we go */ 		for (i=0; i<window; i++,idx--) 			{			if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))	goto err;			wvalue = (wvalue<<1)+BN_is_bit_set(p,idx);  			} 				/* Fetch the appropriate pre-computed value from the pre-buf */		if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(computeTemp, top, powerbuf, wvalue, numPowers)) goto err; 		/* Multiply the result into the intermediate result */ 		if (!BN_mod_mul_montgomery(r,r,computeTemp,mont,ctx)) goto err;  		} 	/* Convert the final result from montgomery to standard format */	if (!BN_from_montgomery(rr,r,mont,ctx)) goto err;	ret=1;err:	if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);	if (powerbuf!=NULL)		{		OPENSSL_cleanse(powerbuf,powerbufLen);		OPENSSL_free(powerbufFree);		} 	if (am!=NULL) BN_clear(am); 	if (computeTemp!=NULL) BN_clear(computeTemp);	BN_CTX_end(ctx);	return(ret);	}int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,                         const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)	{	BN_MONT_CTX *mont = NULL;	int b, bits, ret=0;	int r_is_one;	BN_ULONG w, next_w;	BIGNUM *d, *r, *t;	BIGNUM *swap_tmp;#define BN_MOD_MUL_WORD(r, w, m) \		(BN_mul_word(r, (w)) && \		(/* BN_ucmp(r, (m)) < 0 ? 1 :*/  \			(BN_mod(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1))))		/* BN_MOD_MUL_WORD is only used with 'w' large,		 * so the BN_ucmp test is probably more overhead		 * than always using BN_mod (which uses BN_copy if		 * a similar test returns true). */		/* We can use BN_mod and do not need BN_nnmod because our		 * accumulator is never negative (the result of BN_mod does		 * not depend on the sign of the modulus).		 */#define BN_TO_MONTGOMERY_WORD(r, w, mont) \		(BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx))	if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0)		{		/* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */		BNerr(BN_F_BN_MOD_EXP_MONT_WORD,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);		return -1;		}	bn_check_top(p);	bn_check_top(m);	if (m->top == 0 || !(m->d[0] & 1))		{		BNerr(BN_F_BN_MOD_EXP_MONT_WORD,BN_R_CALLED_WITH_EVEN_MODULUS);		return(0);		}	if (m->top == 1)		a %= m->d[0]; /* make sure that 'a' is reduced */	bits = BN_num_bits(p);	if (bits == 0)		{		ret = BN_one(rr);		return ret;		}	if (a == 0)		{		ret = BN_zero(rr);		return ret;		}	BN_CTX_start(ctx);	d = BN_CTX_get(ctx);	r = BN_CTX_get(ctx);	t = BN_CTX_get(ctx);	if (d == NULL || r == NULL || t == NULL) goto err;	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;		}	r_is_one = 1; /* except for Montgomery factor */	/* bits-1 >= 0 */	/* The result is accumulated in the product r*w. */	w = a; /* bit 'bits-1' of 'p' is always set */	for (b = bits-2; b >= 0; b--)		{		/* First, square r*w. */		next_w = w*w;		if ((next_w/w) != w) /* overflow */			{			if (r_is_one)				{				if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err;				r_is_one = 0;				}			else				{				if (!BN_MOD_MUL_WORD(r, w, m)) goto err;				}			next_w = 1;			}		w = next_w;		if (!r_is_one)			{			if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) goto err;			}		/* Second, multiply r*w by 'a' if exponent bit is set. */		if (BN_is_bit_set(p, b))			{			next_w = w*a;			if ((next_w/a) != w) /* overflow */				{				if (r_is_one)					{					if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err;					r_is_one = 0;					}				else					{					if (!BN_MOD_MUL_WORD(r, w, m)) goto err;					}				next_w = a;				}			w = next_w;			}		}	/* Finally, set r:=r*w. */	if (w != 1)		{		if (r_is_one)			{			if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err;			r_is_one = 0;			}		else			{			if (!BN_MOD_MUL_WORD(r, w, m)) goto err;			}		}	if (r_is_one) /* can happen only if a == 1*/		{		if (!BN_one(rr)) goto err;		}	else		{		if (!BN_from_montgomery(rr, r, mont, ctx)) goto err;		}	ret = 1;err:	if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);	BN_CTX_end(ctx);	return(ret);	}/* The old fallback, simple version :-) */int BN_mod_exp_simple(BIGNUM *r,	const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,	BN_CTX *ctx)	{	int i,j,bits,ret=0,wstart,wend,window,wvalue,ts=0;	int start=1;	BIGNUM *d;	BIGNUM val[TABLE_SIZE];	if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0)		{		/* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */		BNerr(BN_F_BN_MOD_EXP_SIMPLE,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);		return -1;		}	bits=BN_num_bits(p);	if (bits == 0)		{		ret = BN_one(r);		return ret;		}	BN_CTX_start(ctx);	if ((d = BN_CTX_get(ctx)) == NULL) goto err;	BN_init(&(val[0]));	ts=1;	if (!BN_nnmod(&(val[0]),a,m,ctx)) goto err;		/* 1 */	if (BN_is_zero(&(val[0])))		{		ret = BN_zero(r);		goto err;		}	window = BN_window_bits_for_exponent_size(bits);	if (window > 1)		{		if (!BN_mod_mul(d,&(val[0]),&(val[0]),m,ctx))			goto err;				/* 2 */		j=1<<(window-1);		for (i=1; i<j; i++)			{			BN_init(&(val[i]));			if (!BN_mod_mul(&(val[i]),&(val[i-1]),d,m,ctx))				goto err;			}		ts=i;		}	start=1;	/* This is used to avoid multiplication etc			 * when there is only the value '1' in the			 * buffer. */	wvalue=0;	/* The 'value' of the window */	wstart=bits-1;	/* The top bit of the window */	wend=0;		/* The bottom bit of the window */	if (!BN_one(r)) goto err;	for (;;)		{		if (BN_is_bit_set(p,wstart) == 0)			{			if (!start)				if (!BN_mod_mul(r,r,r,m,ctx))				goto err;			if (wstart == 0) break;			wstart--;			continue;			}		/* We now have wstart on a 'set' bit, we now need to work out		 * how bit a window to do.  To do this we need to scan		 * forward until the last set bit before the end of the		 * window */		j=wstart;		wvalue=1;		wend=0;		for (i=1; i<window; i++)			{			if (wstart-i < 0) break;			if (BN_is_bit_set(p,wstart-i))				{				wvalue<<=(i-wend);				wvalue|=1;				wend=i;				}			}		/* wend is the size of the current window */		j=wend+1;		/* add the 'bytes above' */		if (!start)			for (i=0; i<j; i++)				{				if (!BN_mod_mul(r,r,r,m,ctx))					goto err;				}				/* wvalue will be an odd number < 2^window */		if (!BN_mod_mul(r,r,&(val[wvalue>>1]),m,ctx))			goto err;		/* move the 'window' down further */		wstart-=wend+1;		wvalue=0;		start=0;		if (wstart < 0) break;		}	ret=1;err:	BN_CTX_end(ctx);	for (i=0; i<ts; i++)		BN_clear_free(&(val[i]));	return(ret);	}