bn_exp.c

mediastreamer2是开源的网络传输媒体流的库

				}
		
		/* 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);
	bn_check_top(rr);
	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_correct_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_correct_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 (!BN_is_odd(m))
		{
		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)
		{
		BN_zero(rr);
		ret = 1;
		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);
	bn_check_top(rr);
	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;
	int start=1;
	BIGNUM *d;
	/* Table of variables obtained from 'ctx' */
	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);
	d = BN_CTX_get(ctx);
	val[0] = BN_CTX_get(ctx);
	if(!d || !val[0]) goto err;

	if (!BN_nnmod(val[0],a,m,ctx)) goto err;		/* 1 */
	if (BN_is_zero(val[0]))
		{
		BN_zero(r);
		ret = 1;
		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++)
			{
			if(((val[i] = BN_CTX_get(ctx)) == NULL) ||
					!BN_mod_mul(val[i],val[i-1],d,m,ctx))
				goto err;
			}
		}

	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);
	bn_check_top(r);
	return(ret);
	}