bn16.c

包含哈希,对称以及非对称的经典算法 包含经典事例

	if (!s || !t) {
		dest->size = 0;
		return 0;
	}

	if (a == b)
		return bnSquare_16(dest, a);

	bnSizeCheck(dest, s+t);

	if (dest == a) {
		LBNALLOC(srcbuf, s);
		if (!srcbuf)
			return -1;
		lbnCopy_16(srcbuf, (BNWORD16 *)a->ptr, s);
		lbnMul_16((BNWORD16 *)dest->ptr, srcbuf, s,
		                                 (BNWORD16 *)b->ptr, t);
		LBNFREE(srcbuf, s);
	} else if (dest == b) {
		LBNALLOC(srcbuf, t);
		if (!srcbuf)
			return -1;
		lbnCopy_16(srcbuf, (BNWORD16 *)b->ptr, t);
		lbnMul_16((BNWORD16 *)dest->ptr, (BNWORD16 *)a->ptr, s,
		                                 srcbuf, t);
		LBNFREE(srcbuf, t);
	} else {
		lbnMul_16((BNWORD16 *)dest->ptr, (BNWORD16 *)a->ptr, s,
		                                 (BNWORD16 *)b->ptr, t);
	}
	dest->size = lbnNorm_16((BNWORD16 *)dest->ptr, s+t);
	MALLOCDB;
	return 0;
}

int
bnMulQ_16(struct BigNum *dest, struct BigNum const *a, unsigned b)
{
	unsigned s;

	s = lbnNorm_16((BNWORD16 *)a->ptr, a->size);
	if (!s || !b) {
		dest->size = 0;
		return 0;
	}
	if (b == 1)
		return bnCopy_16(dest, a);
	bnSizeCheck(dest, s+1);
	lbnMulN1_16((BNWORD16 *)dest->ptr, (BNWORD16 *)a->ptr, s, b);
	dest->size = lbnNorm_16((BNWORD16 *)dest->ptr, s+1);
	MALLOCDB;
	return 0;
}

int
bnDivMod_16(struct BigNum *q, struct BigNum *r, struct BigNum const *n,
            struct BigNum const *d)
{
	unsigned dsize, nsize;
	BNWORD16 qhigh;

	dsize = lbnNorm_16((BNWORD16 *)d->ptr, d->size);
	nsize = lbnNorm_16((BNWORD16 *)n->ptr, n->size);

	if (nsize < dsize) {
		q->size = 0;	/* No quotient */
		r->size = nsize;
		return 0;	/* Success */
	}

	bnSizeCheck(q, nsize-dsize);

	if (r != n) {	/* You are allowed to reduce in place */
		bnSizeCheck(r, nsize);
		lbnCopy_16((BNWORD16 *)r->ptr, (BNWORD16 *)n->ptr, nsize);
	}
		
	qhigh = lbnDiv_16((BNWORD16 *)q->ptr, (BNWORD16 *)r->ptr, nsize,
	                  (BNWORD16 *)d->ptr, dsize);
	nsize -= dsize;
	if (qhigh) {
		bnSizeCheck(q, nsize+1);
		*((BNWORD16 *)q->ptr BIGLITTLE(-nsize-1,+nsize)) = qhigh;
		q->size = nsize+1;
	} else {
		q->size = lbnNorm_16((BNWORD16 *)q->ptr, nsize);
	}
	r->size = lbnNorm_16((BNWORD16 *)r->ptr, dsize);
	MALLOCDB;
	return 0;
}

int
bnMod_16(struct BigNum *dest, struct BigNum const *src, struct BigNum const *d)
{
	unsigned dsize, nsize;

	nsize = lbnNorm_16((BNWORD16 *)src->ptr, src->size);
	dsize = lbnNorm_16((BNWORD16 *)d->ptr, d->size);


	if (dest != src) {
		bnSizeCheck(dest, nsize);
		lbnCopy_16((BNWORD16 *)dest->ptr, (BNWORD16 *)src->ptr, nsize);
	}

	if (nsize < dsize) {
		dest->size = nsize;	/* No quotient */
		return 0;
	}

	(void)lbnDiv_16((BNWORD16 *)dest->ptr BIGLITTLE(-dsize,+dsize),
	                (BNWORD16 *)dest->ptr, nsize,
	                (BNWORD16 *)d->ptr, dsize);
	dest->size = lbnNorm_16((BNWORD16 *)dest->ptr, dsize);
	MALLOCDB;
	return 0;
}

unsigned
bnModQ_16(struct BigNum const *src, unsigned d)
{
	unsigned s;

	s = lbnNorm_16((BNWORD16 *)src->ptr, src->size);
	if (!s)
		return 0;
	
	return lbnModQ_16((BNWORD16 *)src->ptr, s, d);
}

int
bnExpMod_16(struct BigNum *dest, struct BigNum const *n,
	struct BigNum const *exp, struct BigNum const *mod)
{
	unsigned nsize, esize, msize;

	nsize = lbnNorm_16((BNWORD16 *)n->ptr, n->size);
	esize = lbnNorm_16((BNWORD16 *)exp->ptr, exp->size);
	msize = lbnNorm_16((BNWORD16 *)mod->ptr, mod->size);

	if (!msize || (((BNWORD16 *)mod->ptr)[BIGLITTLE(-1,0)] & 1) == 0)
		return -1;	/* Illegal modulus! */

	bnSizeCheck(dest, msize);

	/* Special-case base of 2 */
	if (nsize == 1 && ((BNWORD16 *)n->ptr)[BIGLITTLE(-1,0)] == 2) {
		if (lbnTwoExpMod_16((BNWORD16 *)dest->ptr,
				    (BNWORD16 *)exp->ptr, esize,
				    (BNWORD16 *)mod->ptr, msize) < 0)
			return -1;
	} else {
		if (lbnExpMod_16((BNWORD16 *)dest->ptr,
		                 (BNWORD16 *)n->ptr, nsize,
				 (BNWORD16 *)exp->ptr, esize,
				 (BNWORD16 *)mod->ptr, msize) < 0)
		return -1;
	}

	dest->size = lbnNorm_16((BNWORD16 *)dest->ptr, msize);
	MALLOCDB;
	return 0;
}

int
bnDoubleExpMod_16(struct BigNum *dest,
	struct BigNum const *n1, struct BigNum const *e1,
	struct BigNum const *n2, struct BigNum const *e2,
	struct BigNum const *mod)
{
	unsigned n1size, e1size, n2size, e2size, msize;

	n1size = lbnNorm_16((BNWORD16 *)n1->ptr, n1->size);
	e1size = lbnNorm_16((BNWORD16 *)e1->ptr, e1->size);
	n2size = lbnNorm_16((BNWORD16 *)n2->ptr, n2->size);
	e2size = lbnNorm_16((BNWORD16 *)e2->ptr, e2->size);
	msize = lbnNorm_16((BNWORD16 *)mod->ptr, mod->size);

	if (!msize || (((BNWORD16 *)mod->ptr)[BIGLITTLE(-1,0)] & 1) == 0)
		return -1;	/* Illegal modulus! */

	bnSizeCheck(dest, msize);

	if (lbnDoubleExpMod_16((BNWORD16 *)dest->ptr,
		(BNWORD16 *)n1->ptr, n1size, (BNWORD16 *)e1->ptr, e1size,
		(BNWORD16 *)n2->ptr, n1size, (BNWORD16 *)e2->ptr, e2size,
		(BNWORD16 *)mod->ptr, msize) < 0)
		return -1;

	dest->size = lbnNorm_16((BNWORD16 *)dest->ptr, msize);
	MALLOCDB;
	return 0;
}

int
bnTwoExpMod_16(struct BigNum *n, struct BigNum const *exp,
	struct BigNum const *mod)
{
	unsigned esize, msize;

	esize = lbnNorm_16((BNWORD16 *)exp->ptr, exp->size);
	msize = lbnNorm_16((BNWORD16 *)mod->ptr, mod->size);

	if (!msize || (((BNWORD16 *)mod->ptr)[BIGLITTLE(-1,0)] & 1) == 0)
		return -1;	/* Illegal modulus! */

	bnSizeCheck(n, msize);

	if (lbnTwoExpMod_16((BNWORD16 *)n->ptr, (BNWORD16 *)exp->ptr, esize,
	                    (BNWORD16 *)mod->ptr, msize) < 0)
		return -1;

	n->size = lbnNorm_16((BNWORD16 *)n->ptr, msize);
	MALLOCDB;
	return 0;
}

int
bnGcd_16(struct BigNum *dest, struct BigNum const *a, struct BigNum const *b)
{
	BNWORD16 *tmp;
	unsigned asize, bsize;
	int i;

	/* Kind of silly, but we might as well permit it... */
	if (a == b)
		return dest == a ? 0 : bnCopy(dest, a);

	/* Ensure a is not the same as "dest" */
	if (a == dest) {
		a = b;
		b = dest;
	}

	asize = lbnNorm_16((BNWORD16 *)a->ptr, a->size);
	bsize = lbnNorm_16((BNWORD16 *)b->ptr, b->size);

	bnSizeCheck(dest, bsize+1);

	/* Copy a to tmp */
	LBNALLOC(tmp, asize+1);
	if (!tmp)
		return -1;
	lbnCopy_16(tmp, (BNWORD16 *)a->ptr, asize);

	/* Copy b to dest,if necessary */
	if (dest != b)
		lbnCopy_16((BNWORD16 *)dest->ptr,
			   (BNWORD16 *)b->ptr, bsize);
	if (bsize > asize || (bsize == asize &&
	        lbnCmp_16((BNWORD16 *)b->ptr, (BNWORD16 *)a->ptr, asize) > 0))
	{
		i = lbnGcd_16((BNWORD16 *)dest->ptr, bsize, tmp, asize);
		if (i >= 0) {
			dest->size = (unsigned)i;
		} else {
			lbnCopy_16((BNWORD16 *)dest->ptr, tmp,
				   (unsigned)-i);
			dest->size = (unsigned)-i;
		}
	} else {
		i = lbnGcd_16(tmp, asize, (BNWORD16 *)dest->ptr, bsize);
		if (i <= 0) {
			dest->size = (unsigned)-i;
		} else {
			lbnCopy_16((BNWORD16 *)dest->ptr, tmp,
				   (unsigned)i);
			dest->size = (unsigned)i;
		}
	}
	LBNFREE(tmp, asize+1);
	MALLOCDB;
	return 0;
}

int
bnInv_16(struct BigNum *dest, struct BigNum const *src,
         struct BigNum const *mod)
{
	unsigned s, m;
	int i;

	s = lbnNorm_16((BNWORD16 *)src->ptr, src->size);
	m = lbnNorm_16((BNWORD16 *)mod->ptr, mod->size);

	/* lbnInv_16 requires that the input be less than the modulus */
	if (m < s ||
	    (m==s && lbnCmp_16((BNWORD16 *)src->ptr, (BNWORD16 *)mod->ptr, s)))
	{
		bnSizeCheck(dest, s + (m==s));
		if (dest != src)
			lbnCopy_16((BNWORD16 *)dest->ptr,
			           (BNWORD16 *)src->ptr, s);
		/* Pre-reduce modulo the modulus */
		(void)lbnDiv_16((BNWORD16 *)dest->ptr BIGLITTLE(-m,+m),
			        (BNWORD16 *)dest->ptr, s,
		                (BNWORD16 *)mod->ptr, m);
		s = lbnNorm_16((BNWORD16 *)dest->ptr, m);
		MALLOCDB;
	} else {
		bnSizeCheck(dest, m+1);
		if (dest != src)
			lbnCopy_16((BNWORD16 *)dest->ptr,
			           (BNWORD16 *)src->ptr, s);
	}

	i = lbnInv_16((BNWORD16 *)dest->ptr, s, (BNWORD16 *)mod->ptr, m);
	if (i == 0)
		dest->size = lbnNorm_16((BNWORD16 *)dest->ptr, m);

	MALLOCDB;
	return i;
}

/*
 * Shift a bignum left the appropriate number of bits,
 * multiplying by 2^amt.
 */
int 
bnLShift_16(struct BigNum *dest, unsigned amt)
{
	unsigned s = dest->size;
	BNWORD16 carry;

	if (amt % 16) {
		carry = lbnLshift_16(dest->ptr, s, amt % 16);
		if (carry) {
			s++;
			bnSizeCheck(dest, s);
			((BNWORD16 *)dest->ptr)[BIGLITTLE(-s,s-1)] = carry;
		}
	}

	amt /= 16;
	if (amt) {
		bnSizeCheck(dest, s+amt);
		memmove((BNWORD16 *)dest->ptr BIGLITTLE(-s-amt, +amt),
		        (BNWORD16 *)dest->ptr BIG(-s),
			s * sizeof(BNWORD16));
		lbnZero_16((BNWORD16 *)dest->ptr, amt);
		s += amt;
	}
	dest->size = s;
	MALLOCDB;
	return 0;
}

/*
 * Shift a bignum right the appropriate number of bits,
 * dividing by 2^amt.
 */
void bnRShift_16(struct BigNum *dest, unsigned amt)
{
	unsigned s = dest->size;

	if (amt >= 16) {
		memmove(
		        (BNWORD16 *)dest->ptr BIG(-s+amt/16),
			(BNWORD16 *)dest->ptr BIGLITTLE(-s, +amt/16),
			s-amt/16 * sizeof(BNWORD16));
		s -= amt/16;
		amt %= 16;
	}

	if (amt)
		(void)lbnRshift_16(dest->ptr, s, amt);

	dest->size = lbnNorm_16(dest->ptr, s);
	MALLOCDB;
}

/*
 * Shift a bignum right until it is odd, and return the number of
 * bits shifted.  n = d * 2^s.  Replaces n with d and returns s.
 * Returns 0 when given 0.  (Another valid answer is infinity.)
 */
unsigned
bnMakeOdd_16(struct BigNum *n)
{
	unsigned size;
	unsigned s;	/* shift amount */
	BNWORD16 *p;
	BNWORD16 t;

	p = (BNWORD16 *)n->ptr;
	size = lbnNorm_16(p, n->size);
	if (!size)
		return 0;

	t = BIGLITTLE(p[-1],p[0]);
	s = 0;

	/* See how many words we have to shift */
	if (!t) {
		/* Shift by words */
		do {
			
			s++;
			BIGLITTLE(--p,p++);
		} while ((t = BIGLITTLE(p[-1],p[0])) == 0);
		size -= s;
		s *= 16;
		memmove((BNWORD16 *)n->ptr BIG(-size), p BIG(-size),
			size * sizeof(BNWORD16));
		p = (BNWORD16 *)n->ptr;
		MALLOCDB;
	}

	assert(t);

	/* Now count the bits */
	while ((t & 1) == 0) {
		t >>= 1;
		s++;
	}

	/* Shift the bits */
	if (s & (16-1)) {
		lbnRshift_16(p, size, s & (16-1));
		/* Renormalize */
		if (BIGLITTLE(*(p-size),*(p+(size-1))) == 0)
			--size;
	}
	n->size = size;

	MALLOCDB;
	return s;
}