view release on metacpan or  search on metacpan

matrixssl-1-8-6-open/src/crypto/peersec/mpi.c  view on Meta::CPAN

 */
	if (X->sign == MP_NEG) {
		mp_int tmpG, tmpX;
		int32 err;

/*
		first compute 1/G mod P
 */
		if ((err = mp_init(pool, &tmpG)) != MP_OKAY) {
			return err;
		}
		if ((err = mp_invmod(pool, G, P, &tmpG)) != MP_OKAY) {
			mp_clear(&tmpG);
			return err;
		}

/*
		now get |X|
 */
		if ((err = mp_init(pool, &tmpX)) != MP_OKAY) {
			mp_clear(&tmpG);
			return err;
		}
		if ((err = mp_abs(X, &tmpX)) != MP_OKAY) {
			mp_clear(&tmpG);
			mp_clear(&tmpX);
			return err;
		}

/*
		and now compute (1/G)**|X| instead of G**X [X < 0]
 */
		err = mp_exptmod(pool, &tmpG, &tmpX, P, Y);
		mp_clear(&tmpG);
		mp_clear(&tmpX);
		return err;
	}

/*
	if the modulus is odd or dr != 0 use the fast method
 */
	if (mp_isodd (P) == 1) {
		return mp_exptmod_fast (pool, G, X, P, Y, 0);
	} else {
/*
		no exptmod for evens
 */
		return MP_VAL;
	}
}

/******************************************************************************/
/*
	Call only from mp_exptmod to make sure this fast version qualifies
*/
static int32 mp_exptmod_fast(psPool_t *pool, mp_int * G, mp_int * X,
				mp_int * P, mp_int * Y, int32 redmode)
{
	mp_int		M[TAB_SIZE], res;
	mp_digit	buf, mp;
	int32		err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize;


/*
	use a pointer to the reduction algorithm.  This allows us to use
	one of many reduction algorithms without modding the guts of
	the code with if statements everywhere.
 */
	int32	(*redux)(mp_int*,mp_int*,mp_digit);

/*
	find window size
 */
	x = mp_count_bits (X);
	if (x <= 7) {
		winsize = 2;
	} else if (x <= 36) {
		winsize = 3;
	} else if (x <= 140) {
		winsize = 4;
	} else if (x <= 450) {
		winsize = 5;
	} else if (x <= 1303) {
		winsize = 6;
	} else if (x <= 3529) {
		winsize = 7;
	} else {
		winsize = 8;
	}

#ifdef MP_LOW_MEM
	if (winsize > 5) {
		winsize = 5;
	}
#endif

/*
	init M array
	init first cell
 */
	if ((err = mp_init(pool, &M[1])) != MP_OKAY) {
		return err;
	}

/*
	now init the second half of the array
 */
	for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
		if ((err = mp_init(pool, &M[x])) != MP_OKAY) {
			for (y = 1<<(winsize-1); y < x; y++) {
				mp_clear(&M[y]);
			}
			mp_clear(&M[1]);
			return err;
		}
	}


/*
	now setup montgomery
 */

matrixssl-1-8-6-open/src/crypto/peersec/mpi.c  view on Meta::CPAN

 */
	if ((err = mp_init(pool, &res)) != MP_OKAY) {
		goto LBL_M;
	}

/*
	create M table. The first half of the table is not computed
	though accept for M[0] and M[1]
*/

/*
	now we need R mod m
 */
	if ((err = mp_montgomery_calc_normalization(&res, P)) != MP_OKAY) {
		goto LBL_RES;
	}

/*
	now set M[1] to G * R mod m
 */
	if ((err = mp_mulmod(pool, G, &res, P, &M[1])) != MP_OKAY) {
		goto LBL_RES;
	}

/*
	compute the value at M[1<<(winsize-1)] by squaring
	M[1] (winsize-1) times
*/
	if ((err = mp_copy(&M[1], &M[1 << (winsize - 1)])) != MP_OKAY) {
		goto LBL_RES;
	}

	for (x = 0; x < (winsize - 1); x++) {
		if ((err = mp_sqr(pool, &M[1 << (winsize - 1)],
				&M[1 << (winsize - 1)])) != MP_OKAY) {
			goto LBL_RES;
		}
		if ((err = redux(&M[1 << (winsize - 1)], P, mp)) != MP_OKAY) {
			goto LBL_RES;
		}
	}

/*
	create upper table
 */
	for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) {
		if ((err = mp_mul(pool, &M[x - 1], &M[1], &M[x])) != MP_OKAY) {
			goto LBL_RES;
		}
		if ((err = redux(&M[x], P, mp)) != MP_OKAY) {
			goto LBL_RES;
		}
	}

/*
	set initial mode and bit cnt
 */
	mode   = 0;
	bitcnt = 1;
	buf    = 0;
	digidx = X->used - 1;
	bitcpy = 0;
	bitbuf = 0;

	for (;;) {
/*
		grab next digit as required
 */
		if (--bitcnt == 0) {
			/* if digidx == -1 we are out of digits so break */
			if (digidx == -1) {
				break;
			}
			/* read next digit and reset bitcnt */
			buf    = X->dp[digidx--];
			bitcnt = (int)DIGIT_BIT;
		}

		/* grab the next msb from the exponent */
		y     = (mp_digit)(buf >> (DIGIT_BIT - 1)) & 1;
		buf <<= (mp_digit)1;

/*
		if the bit is zero and mode == 0 then we ignore it
		These represent the leading zero bits before the first 1 bit
		in the exponent.  Technically this opt is not required but it
		does lower the # of trivial squaring/reductions used
*/
		if (mode == 0 && y == 0) {
			continue;
		}

/*
		if the bit is zero and mode == 1 then we square
 */
		if (mode == 1 && y == 0) {
			if ((err = mp_sqr (pool, &res, &res)) != MP_OKAY) {
				goto LBL_RES;
			}
			if ((err = redux (&res, P, mp)) != MP_OKAY) {
				goto LBL_RES;
			}
			continue;
		}

/*
		else we add it to the window
 */
		bitbuf |= (y << (winsize - ++bitcpy));
		mode    = 2;

		if (bitcpy == winsize) {
/*
			ok window is filled so square as required and multiply
			square first
 */
			for (x = 0; x < winsize; x++) {
				if ((err = mp_sqr(pool, &res, &res)) != MP_OKAY) {
					goto LBL_RES;
				}
				if ((err = redux(&res, P, mp)) != MP_OKAY) {
					goto LBL_RES;
				}
			}

			/* then multiply */
			if ((err = mp_mul(pool, &res, &M[bitbuf], &res)) != MP_OKAY) {
				goto LBL_RES;
			}
			if ((err = redux(&res, P, mp)) != MP_OKAY) {
				goto LBL_RES;
			}

/*
			empty window and reset