bigd.c

RSA operation library.

	bdFree(&ww);

	return 0;
}

int bdSquare(T w, T x)
	/* Computes w = x^2, w#x */
{
	size_t dig_size;

	assert(w && x);

	dig_size = max(x->ndigits, 1);
	/* Make sure w is big enough for product */
	bd_resize(w, 2 * dig_size);

	/* Finally, do the business */
	mpSquare(w->digits, x->digits, dig_size);

	/* Make sure we've set the right size for w */
	w->ndigits = mpSizeof(w->digits, 2 * dig_size);	

	return 0;
}

int bdSquareEx(T w, T x)
	/* Compute w = x^2 (safe) */
{
	T ww;

	assert(w && x);
	/* Use temp */
	ww = bdNew();
	bdSetEqual(ww, w);

	bdSquare(ww, x);

	bdSetEqual(w, ww);
	bdFree(&ww);

	return 0;
}

int bdSqrt(BIGD s, BIGD x)
	/* Computes integer square root s = floor(sqrt(x)) */
{
	size_t dig_size;
	int r;

	assert(s && x);
	dig_size = x->ndigits;
	bd_resize(s, dig_size);
	r = mpSqrt(s->digits, x->digits, dig_size);
	s->ndigits = mpSizeof(s->digits, dig_size);

	return r;
}

int bdShortDiv(T q, T r, T u, bdigit_t d)
	/* Computes quotient q = u / d and remainder r = u mod d */
{
	DIGIT_T rem;
	size_t dig_size;

	assert(q && r && u);
	dig_size = u->ndigits;
	bd_resize(q, dig_size);

	rem = mpShortDiv(q->digits, u->digits, d, dig_size);
	bdSetShort(r, rem);

	q->ndigits = mpSizeof(q->digits, dig_size);

	return 0;
}

int bdDivide(T q, T r, T u, T v)
	/* Computes quotient q = u / v and remainder r = u mod v 
	   trashes q and r first
	*/
{
	size_t dig_size;

	assert(q && r && u && v);
	dig_size = u->ndigits;
	bd_resize(q, dig_size);
	bd_resize(r, dig_size);

	/* Do the business */
	mpDivide(q->digits, r->digits, u->digits, dig_size, v->digits, v->ndigits);

	/* Set final sizes */
	q->ndigits = mpSizeof(q->digits, dig_size);
	r->ndigits = mpSizeof(r->digits, dig_size);

	return 0;
}

int bdDivideEx(T q, T r, T u, T v)
	/* Computes quotient q = u / v and remainder r = u mod v (safe) */
{
	size_t dig_size;
	BIGD qq, rr;

	assert(q && r && u && v);
	/* Use temps because mpDivide trashes q and r */
	qq = bdNew();
	rr = bdNew();

	dig_size = u->ndigits;
	bd_resize(qq, dig_size);
	bd_resize(rr, dig_size);

	/* Do the business */
	mpDivide(qq->digits, rr->digits, u->digits, dig_size, v->digits, v->ndigits);

	/* Copy temps */
	qq->ndigits = dig_size;
	rr->ndigits = dig_size;
	bdSetEqual(q, qq);
	bdSetEqual(r, rr);

	/* Set final sizes */
	q->ndigits = mpSizeof(q->digits, dig_size);
	r->ndigits = mpSizeof(r->digits, dig_size);

	/* Free temps */
	bdFree(&qq);
	bdFree(&rr);

	return 0;
}

bdigit_t bdShortMod(T r, T u, bdigit_t d)
	/* Returns r = u mod d */
{
	DIGIT_T rr;

	assert(r && u);
	rr = mpShortMod(u->digits, d, u->ndigits);
	bdSetShort(r, rr);

	return rr;
}

int bdModulo(T r, T u, T v)
	/* Computes r = u mod v, r#u */
{
	size_t nr;

	assert(r && u && v);

	/* NB r is only vdigits long at most */
	nr = v->ndigits;
	bd_resize(r, nr);

	/* Do the business */
	mpModulo(r->digits, u->digits, u->ndigits, v->digits, v->ndigits);

	/* Set final size */
	r->ndigits = mpSizeof(r->digits, nr);

	return 0;
}

int bdModuloEx(T r, T u, T v)
	/* Computes r = u mod v (safe) */
{
	T rr;

	assert(r && u && v);
	/* Use temp */
	rr = bdNew();
	bdSetEqual(rr, r);

	bdModulo(rr, u, v);

	bdSetEqual(r, rr);
	bdFree(&rr);

	return 0;
}

int bdSetBit(T a, size_t ibit, int value)
/* Set bit ibit (0..nbits-1) with value 1 or 0 
   -- increases size if a too small but does not shrink */
{
	size_t idigit, bit_to_set;
	DIGIT_T mask;
	DIGIT_T *p;

	assert(a);
	/* Which digit? (0-based) */
	idigit = ibit / BITS_PER_DIGIT;
	/* Check size */
	/* [EDIT v2.1:] change a->maxdigits to a->ndigits */
	if (idigit >= a->ndigits)
	{
		bd_resize(a, idigit+1);
		a->ndigits = idigit+1;
	}

	/* use a ptr */
	p = a->digits;

	/* Set mask */
	bit_to_set = ibit % BITS_PER_DIGIT;
	mask = 0x01 << bit_to_set;

	if (value)
		p[idigit] |= mask;
	else
		p[idigit] &= (~mask);

	/* Set the right size */
	a->ndigits = mpSizeof(a->digits, a->ndigits);

	return 0;
}

int bdGetBit(T a, size_t ibit)
	/* Returns value 1 or 0 of bit n (0..nbits-1) */
{
	size_t idigit, bit_to_get;
	DIGIT_T mask;
	DIGIT_T *p;

	assert(a);
	/* Which digit? (0-based) */
	idigit = ibit / BITS_PER_DIGIT;
	/* Check size */
	if (idigit >= a->maxdigits)
		return 0;

	/* use a ptr */
	p = a->digits;

	/* Set mask */
	bit_to_get = ibit % BITS_PER_DIGIT;
	mask = 0x01 << bit_to_get;

	/* [EDIT v2.0.1:] return ((p[idigit] &= mask) ? 1 : 0);*/
	return ((p[idigit] & mask) ? 1 : 0);
}

void bdShiftLeft(T a, T b, size_t s)
	/* Computes a = b << s */
{ 
	/* Increases the size of a if necessary. */
	/* [v2.1.0] modified to allow any size of shift */

	size_t dig_size = b->ndigits;
	
	assert(a && b);

	if (s >= BITS_PER_DIGIT)
		dig_size += (s / BITS_PER_DIGIT);
	
	/* Assume overflow */
	dig_size++;
	/* Make sure both big enough */
	bd_resize(a, dig_size);
	bd_resize(b, dig_size);

	/* Set the final size */
	mpShiftLeft(a->digits, b->digits, s, dig_size);

	a->ndigits = mpSizeof(a->digits, dig_size);

}

void bdShiftRight(T a, T b, size_t n)
	/* Computes a = b >> n */
{ 
	/* Throws away shifted bits */
	/* [v2.1.0] modified to allow any size of shift */

	size_t dig_size = b->ndigits;
	
	assert(a && b);

	bd_resize(a, dig_size);
	mpShiftRight(a->digits, b->digits, n, dig_size);

	/* Set the final size */
	a->ndigits = mpSizeof(a->digits, dig_size);

}

void bdXorBits(T a, T b, T c)
	/* Computes bitwise operation a = b XOR c */
{ 
	size_t n;

	assert(a && b && c);
	/* Make sure all variables are the same size */
	n = max(b->ndigits, c->ndigits);

	bd_resize(a, n);
	bd_resize(b, n);
	bd_resize(c, n);

	/* Do the business */
	mpXorBits(a->digits, b->digits, c->digits, n);

	/* Set the final size */
	a->ndigits = mpSizeof(a->digits, n);

}

void bdOrBits(T a, T b, T c)
	/* Computes bitwise operation a = b OR c */
{ 
	size_t n;

	assert(a && b && c);
	/* Make sure all variables are the same size */
	n = max(b->ndigits, c->ndigits);

	bd_resize(a, n);
	bd_resize(b, n);
	bd_resize(c, n);

	/* Do the business */
	mpOrBits(a->digits, b->digits, c->digits, n);

	/* Set the final size */
	a->ndigits = mpSizeof(a->digits, n);

}

void bdAndBits(T a, T b, T c)
	/* Computes bitwise operation a = b AND c */
{ 
	size_t n;

	assert(a && b && c);
	/* Make sure all variables are the same size */
	n = max(b->ndigits, c->ndigits);

	bd_resize(a, n);
	bd_resize(b, n);
	bd_resize(c, n);

	/* Do the business */
	mpAndBits(a->digits, b->digits, c->digits, n);

	/* Set the final size */
	a->ndigits = mpSizeof(a->digits, n);

}

void bdModPowerOf2(BIGD a, size_t L)
	/* Computes a = a mod 2^L */
{
	size_t n;

	assert(a);
	n = a->ndigits;

	/* Do the business */
	mpModPowerOf2(a->digits, n, L);

	/* Set the final size */
	a->ndigits = mpSizeof(a->digits, n);
}

int bdModExp(T y, T x, T e, T m)
{
	/* Compute y = x^e mod m 
	   x,e < m */

	size_t n;
	int status;

	assert(y && x && e && m);
	/* Make sure all variables are the same size */
	n = max(e->ndigits, m->ndigits);
	n = max(x->ndigits, n);

	bd_resize(y, n);
	bd_resize(x, n);
	bd_resize(e, n);
	bd_resize(m, n);

	/* Finally, do the business */
	status = mpModExp(y->digits, x->digits, e->digits, m->digits, n);

	y->ndigits = mpSizeof(y->digits, n);

	return status;
}

int bdModMult(T a, T x, T y, T m)
	/* Compute a = (x * y) mod m */
{
	size_t n;
	int status;

	assert(a && x && y && m);
	/* Make sure all variables are the same size */
	n = max(y->ndigits, m->ndigits);
	n = max(x->ndigits, n);

	bd_resize(a, n);
	bd_resize(y, n);
	bd_resize(x, n);
	bd_resize(m, n);

	/* Do the business */
	status = mpModMult(a->digits, x->digits, y->digits, m->digits, n);

	a->ndigits = mpSizeof(a->digits, n);

	return status;
}


int bdModInv(T x, T a, T m)
	/* Compute x = a^-1 mod m */
{
	size_t n;
	int status;

	assert(x && a && m);
	/* Make sure all variables are the same size */
	n = max(a->ndigits, m->ndigits);

	bd_resize(x, n);
	bd_resize(a, n);
	bd_resize(m, n);

	/* Do the business */
	status = mpModInv(x->digits, a->digits, m->digits, n);

	x->ndigits = mpSizeof(x->digits, n);

	return status;
}

int bdGcd(T g, T x, T y)
	/* Compute g = gcd(x, y) */
{
	size_t n;
	int status;

	assert(g && x && y);
	n = max(x->ndigits, y->ndigits);

	bd_resize(g, n);
	bd_resize(y, n);
	bd_resize(x, n);

	/* Do the business */
	status = mpGcd(g->digits, x->digits, y->digits, n);

	g->ndigits = mpSizeof(g->digits, n);

	return status;
}

int bdIsPrime(T b, size_t ntests)
/* Returns true if passes ntests x Miller-Rabin tests */
{
	assert(b);
	return (mpIsPrime(b->digits, b->ndigits, ntests));
}

int bdRabinMiller(T b, size_t ntests)
/* Returns true if passes ntests x Miller-Rabin tests without trial division */
{
	assert(b);
	return (mpRabinMiller(b->digits, b->ndigits, ntests));
}

/* [Version 2.1: bdRandDigit moved to bdRand.c] */

size_t bdSetRandTest(T a, size_t ndigits)
/* Make a random bigd a of up to ndigits digits 
   -- NB just for testing 
   Return # digits actually set */ 
{
	size_t i, n, bits;
	DIGIT_T mask;

	assert(a);
	/* Pick a random size */
	n = (size_t)spSimpleRand(1, ndigits);
	
	/* Check allocated memory */
	bd_resize(a, n);
	
	/* Now fill with random digits */
	for (i = 0; i < n; i++)
		a->digits[i] = spSimpleRand(0, MAX_DIGIT);

	a->ndigits = n;

	/*	Zero out a random number of bits in leading digit 
		about half the time */
	bits = (size_t)spSimpleRand(0, 2*BITS_PER_DIGIT);
	if (bits != 0 && bits < BITS_PER_DIGIT)
	{
		mask = HIBITMASK;
		for (i = 1; i < bits; i++)
		{
			mask |= (mask >> 1);
		}
		mask = ~mask;
		a->digits[n-1] &= mask;
	}
	return n;
}


int bdRandomSeeded(T a, size_t nbits, const unsigned char *seed, 
	size_t seedlen, BD_RANDFUNC RandFunc)
/* Create a random mp digit at most nbits long
   -- high bit may or may not be set
   -- Uses whatever RNG function the user specifies */
{
	size_t i, hibit, ndigits, nbytes;
	DIGIT_T chop;

	assert(a);
	/* Make sure big enough */
	ndigits = (nbits + BITS_PER_DIGIT - 1) / BITS_PER_DIGIT;
	bd_resize(a, ndigits);
	nbytes = ndigits * sizeof(DIGIT_T);

	/* Generate random bytes using callback function */
	RandFunc((unsigned char *)a->digits, nbytes, seed, seedlen);

	/* Clear unwanted high bits */
	hibit = (nbits-1) % BITS_PER_DIGIT;
	for (chop = 0x01, i = 0; i < hibit; i++)
		chop = (chop << 1) | chop;

	a->digits[ndigits-1] &= chop;

	a->ndigits = ndigits;

	return 0;
}


int bdGeneratePrime(T b, size_t nbits, size_t ntests, 
	const unsigned char *seed, size_t seedlen, BD_RANDFUNC RandFunc)
{
	size_t i, hibit, ndigits, nbytes;
	DIGIT_T mask, chop;
	DIGIT_T *p;
	int done;
	int iloop, maxloops, j, maxodd;

	assert(b);
	/* Make sure big enough */
	ndigits = (nbits + BITS_PER_DIGIT - 1) / BITS_PER_DIGIT;
	bd_resize(b, ndigits);
	nbytes = ndigits * sizeof(DIGIT_T);

	/* use a ptr */
	p = b->digits;

	maxloops = 5;
	maxodd = 100 * nbits;
	done = 0;
	for (iloop = 0; !done && iloop < maxloops; iloop++)
	{
		/* Generate random digits using callback function */
		RandFunc((unsigned char *)p, nbytes, seed, seedlen);

		/* Set high and low bits */
		hibit = (nbits-1) % BITS_PER_DIGIT;
		mask = 0x01 << hibit;
		for (chop = 0x01, i = 0; i < hibit; i++)
			chop = (chop << 1) | chop;

		p[ndigits-1] |= mask;
		p[ndigits-1] &= chop;
		p[0] |= 0x01;

		/* Try each odd number until success or too many tries */
		for (j = 0; !done && j < maxodd; j++, mpShortAdd(p, p, 2, ndigits))
		{
			if (!(p[ndigits-1] & mask))
				break;	/* Catch overflow */

			if (debug) mpPrintNL(p, ndigits);

			if (mpIsPrime(p, ndigits, ntests))
			{
				done = 1;
				break;
			}
		}
	}

	if (debug) mpPrintNL(p, ndigits);

	b->ndigits = ndigits;

	return (done ? 0 : 1);
}

/* Version Info - added in ver 2.0.2 */
int bdVersion(void)
{
	return mpVersion();
}