bn.c

CryptoExtensions1.0 for Java源代码

BIGNUM *r;
BIGNUM *a;
	{
	BN_ULONG *ap,*rp,t,c;
	int i;

	if (bn_is_zero(a))
		{
		bn_zero(r);
		return(1);
		}
	if (a != r)
		{
		if (bn_expand(r,a->top*BITS2) == NULL) return(0);
		r->top=a->top;
		r->neg=a->neg;
		}
	ap=a->d;
	rp=r->d;
	c=0;
	for (i=a->top-1; i>=0; i--)
		{
		t=ap[i];
		rp[i]=((t>>1)&MASK2)|c;
		c=(t&1)?TBIT:0;
		}
	bn_fix_top(r);
	return(1);
	}

int bn_lshift(r, a, n)
BIGNUM *r;
BIGNUM *a;
int n;
	{
	int i,nw,lb,rb;
	BN_ULONG *t,*f;
	BN_ULONG l;

	r->neg=a->neg;
	if (bn_expand(r,(a->top*BITS2)+n) == NULL) return(0);
	nw=n/BITS2;
	lb=n%BITS2;
	rb=BITS2-lb;
	f=a->d;
	t=r->d;
	t[a->top+nw]=0;
	if (lb == 0)
		for (i=a->top-1; i>=0; i--)
			t[nw+i]=f[i];
	else
		for (i=a->top-1; i>=0; i--)
			{
			l=f[i];
			t[nw+i+1]|=(l>>rb)&MASK2;
			t[nw+i]=(l<<lb)&MASK2;
			}
	memset(t,0,nw*sizeof(t[0]));
/*	for (i=0; i<nw; i++)
		t[i]=0;*/
	r->top=a->top+nw+1;
	bn_fix_top(r);
	return(1);
	}

int bn_rshift(r, a, n)
BIGNUM *r;
BIGNUM *a;
int n;
	{
	int i,nw,lb,rb;
	BN_ULONG *t,*f;
	BN_ULONG l;

	r->neg=a->neg;
	nw=n/BITS2;
	rb=n%BITS2;
	lb=BITS2-rb;
	if (nw > a->top)
		{
		bn_zero(r);
		return(1);
		}
	if (bn_expand(r,(a->top-nw+1)*BITS2) == NULL) return(0);
	f=a->d;
	t=r->d;
	if (rb == 0)
		for (i=nw; i<a->top; i++)
			t[i-nw]=f[i];
	else
		{
		l=f[nw];
		for (i=nw; i<a->top; i++)
			{
			t[i-nw] =(l>>rb)&MASK2;
			l=f[i+1];
			t[i-nw]|=(l<<lb)&MASK2;
			}
		}
	r->top=a->top-nw;
	t[r->top]=0;
	bn_fix_top(r);
	return(1);
	}

int bn_clear_bit(a, n)
BIGNUM *a;
int n;
	{
	int i,j;

	i=n/BITS2;
	j=n%BITS2;
	if (a->top <= i) return(0);

	return(a->d[i]&(~(1L<<j)));
	}

int bn_is_bit_set(a, n)
BIGNUM *a;
int n;
	{
	int i,j;

	i=n/BITS2;
	j=n%BITS2;
	if (a->top <= i) return(0);
	return((a->d[i]&(1L<<j))?1:0);
	}

/* rem != m */
int bn_mod(rem, m, d)
BIGNUM *rem;
BIGNUM *m;
BIGNUM *d;
	{
	int i,nm,nd,tos;
	BIGNUM *dv;

	if (bn_Ucmp(m,d) < 0)
		return((bn_copy(rem,m) == NULL)?0:1);
	tos=bn_get_tos();
	dv=bn_get_reg();
	if (dv == NULL) return(0);

	if (!bn_copy(rem,m)) return(0);

	nm=bn_num_bits(rem);
	nd=bn_num_bits(d);
	if (!bn_lshift(dv,d,nm-nd)) return(0);
	for (i=nm-nd; i>=0; i--)
		{
		if (bn_cmp(rem,dv) >= 0)
			{
			if (!bn_sub(rem,rem,dv)) return(0);
			}
		if (!bn_rshift1(dv,dv)) return(0);
		}
	bn_set_tos(tos);
	return(1);
	}

static int mod_init=1;
static int mod_bits,mod_shift;
static BIGNUM *mod_value;
static BIGNUM *mod_shifts[BITS2];
static BN_ULONG *mod_shiftp[BITS2];
static int mod_top[BITS2];

int bn_mod2_init(d, max_bits)
BIGNUM *d;
int max_bits;
	{
	int i;

	if (mod_init)
		{
		mod_init=0;
		for (i=0; i<BITS2; i++)
			{
			mod_shifts[i]=bn_new();
			if (mod_shifts[i] == NULL)
				{ return(0); }
			}
		mod_value=bn_new();
		if (mod_value == NULL)
			{ return(0); }
		}
	if (bn_copy(mod_value,d) == NULL) return(0);
	mod_bits=bn_num_bits(d);
	mod_shift=max_bits-mod_bits;

	if (!bn_lshift(mod_shifts[0],d,mod_shift)) return(0);
	for (i=1; i<BITS2; i++)
		if (!bn_rshift1(mod_shifts[i],mod_shifts[i-1])) return(0);
	for (i=0; i<BITS2; i++)
		{
		mod_shiftp[i]=mod_shifts[i]->d;
		mod_top[i]=mod_shifts[i]->top;
		}
	return(1);
	}

/* don't use :-( */
int bn_mod2(ret, m, d)
BIGNUM *ret;
BIGNUM *m;
BIGNUM *d;
	{
	int i,j,nm,nd,x;
	int w;

	if (bn_copy(ret,m) == NULL) return(0);
	if (bn_cmp(m,mod_value) < 0)
		return(1);
	nm=bn_num_bits(m);
	nd=mod_bits;
	i=nm-nd;

	j=mod_shift-i;	/* take off what we are shifted,
			 * how far do we need to go back */
	w=j/BITS2;	/* number of words to jump back */
	x=j%BITS2;	/* which shift to start on */

	if (w != 0)
		for (i=0; i<BITS2; i++) 
			{
			j=w+(x>i);
			mod_shifts[i]->top-=j;
			mod_shifts[i]->d+=j;
			}
	
	for (i=nm-nd; i>=0; i--)
		{
		if (bn_cmp(ret,mod_shifts[x]) >= 0)
			{
			if (!bn_sub(ret,ret,mod_shifts[x])) return(0);
			}

		mod_shifts[x]->top--;
		mod_shifts[x]->d++;
		x=(x+1)%BITS2;
		}
	for (i=0; i<BITS2; i++)
		{
		mod_shifts[i]->d=mod_shiftp[i];
		mod_shifts[i]->top=mod_top[i];
		}
#ifdef LINT
	d->d[0]=d->d[0];
#endif
	return(1);
	}

int bn_div(dv, rem, m, d)
BIGNUM *dv;
BIGNUM *rem;
BIGNUM *m;
BIGNUM *d;
	{
	int i,nm,nd;
	BIGNUM *D;
	int tos;

	/* Check for divide by zero */
	if (bn_is_zero(d))
		return NULL;

	if (bn_cmp(m,d) < 0)
		{
		if (rem != NULL)
			{ if (bn_copy(rem,m) == NULL) return(0); }
		if (dv != NULL) bn_zero(dv);
		return(1);
		}

	tos=bn_get_tos();
	D=bn_get_reg();
	if (dv == NULL) dv=bn_get_reg();
	if (rem == NULL) rem=bn_get_reg();
	if ((D == NULL) || (dv == NULL) || (rem == NULL))
		return(0);

	nd=bn_num_bits(d);
	nm=bn_num_bits(m);
	if (bn_copy(D,d) == NULL) return(0);
	if (bn_copy(rem,m) == NULL) return(0);

	/* The next 2 are needed so we can do a dv->d[0]|=1 later
	 * since bn_lshift1 will only work once there is a value :-) */
	bn_zero(dv);
	dv->top=1;

	if (!bn_lshift(D,D,nm-nd)) return(0);
	for (i=nm-nd; i>=0; i--)
		{
		if (!bn_lshift1(dv,dv)) return(0);
		if (bn_cmp(rem,D) >= 0)
			{
			dv->d[0]|=1;
			if (!bn_sub(rem,rem,D)) return(0);
			}
/* CAN IMPROVE */
		if (!bn_rshift1(D,D)) return(0);
		}
	dv->neg=m->neg^d->neg;
	bn_set_tos(tos);
	return(1);
	}

BN_ULONG bn_mod_word(a, w)
BIGNUM *a;
unsigned long w;
	{
	BN_ULONG ret;
	int i;

	ret=0;
	for (i=a->top-1; i>=0; i--)
		{
#ifndef RSA_LLONG
		ret=((ret<<BITS4)|((a->d[i]>>BITS4)&MASK2l))%w;
		ret=((ret<<BITS4)|(a->d[i]&MASK2l))%w;
#else
		ret=(((BN_ULLONG)ret<<BITS2)|a->d[i])%w;
#endif
		}
	return(ret);
	}

int bn_add_word(a, w)
BIGNUM *a;
unsigned long w;
	{
	BN_ULONG l;
	int i;

	if (bn_expand(a,a->top*BITS2+1) == NULL) return(0);
	i=0;
	for (;;)
		{
		l=(a->d[i]+w)&MASK2;
		a->d[i]=l;
		if (w > l)
			w=1;
		else
			break;
		i++;
		}
	if (i >= a->top)
		a->top++;
	return(1);
	}


int bn_mul_mod(ret, a, b, m)
BIGNUM *ret;
BIGNUM *a;
BIGNUM *b;
BIGNUM *m;
	{
	BIGNUM *t;
	int tos,r=1;

	tos=bn_get_tos();
	t=bn_get_reg();
	if (t == NULL) return(0);
	if (!bn_mul(t,a,b)) { r=0; goto err; }
	if (!bn_mod(ret,t,m)) { r=0; goto err; }
err:
	bn_set_tos(tos);
	return(r);
	}

#ifndef RECP_MUL_MOD
/* this one works */
int bn_mod_exp(r,a,p,m)
BIGNUM *r,*a,*p,*m;
	{
	int tos,i,bits;
	BIGNUM *v=NULL,*tmp=NULL;

	tos=bn_get_tos();
	if (v == NULL) v=bn_get_reg();
	if (tmp == NULL) tmp=bn_get_reg();
	if ((v == NULL) || (tmp == NULL)) goto err;
	if (bn_copy(v,a) == NULL) goto err;
	bits=bn_num_bits(p);

	if (p->d[0]&1)
		{ if (bn_copy(r,a) == NULL) goto err; }
	else	{ if (bn_one(r) == NULL) goto err; }

	if (!bn_mod2_init(m,m->top*3*BITS2)) goto err;
	for (i=1; i<bits; i++)
		{
		if (!bn_mul(tmp,v,v)) goto err;
		if (!bn_mod2(v,tmp,m)) goto err;
		if (bn_is_bit_set(p,i))
			{
			if (!bn_mul(tmp,r,v)) goto err;
			if (!bn_mod2(r,tmp,m)) goto err;
			}
		}
	bn_set_tos(tos);
	return(1);
err:
	bn_set_tos(tos);
	return(0);
	}

#else
int bn_mod_exp(r, a, p, m)
BIGNUM *r;
BIGNUM *a;
BIGNUM *p;
BIGNUM *m;
	{
	int tos,nb,i,bits;
	BIGNUM *v=NULL,*tmp=NULL;
	BIGNUM *d=NULL;

	tos=bn_get_tos();
	if (v == NULL) v=bn_get_reg();
	if (tmp == NULL) tmp=bn_get_reg();
	if (d == NULL) d=bn_get_reg();
	if ((v == NULL) || (tmp == NULL) || (d == NULL)) goto err;
	if (!bn_mod(v,a,m)) goto err;
	bits=bn_num_bits(p);

	if (p->d[0]&1)
		{ if (!bn_mod(r,a,m)) goto err; }
	else	{ if (!bn_one(r)) goto err; }

	nb=bn_reciprical(d,m);
	if (nb == -1) goto err;
	for (i=1; i<bits; i++)
		{
		if (!bn_modmul_recip(v,v,v,m,d,nb)) goto err;
		if (bn_is_bit_set(p,i))
			{ if (!bn_modmul_recip(r,r,v,m,d,nb)) goto err; }
		}
	bn_set_tos(tos);
	return(1);
err:
	bn_set_tos(tos);
	return(0);
	}
#endif

int bn_modmul_recip(r, x, y, m, i, nb)
BIGNUM *r;
BIGNUM *x;
BIGNUM *y;
BIGNUM *m;
BIGNUM *i;
int nb;
	{
	int tos,j;
	BIGNUM *a,*b,*c,*d;

	tos=bn_get_tos();
	a=bn_get_reg();
	b=bn_get_reg();
	c=bn_get_reg();
	d=bn_get_reg();
	if ((a == NULL) || (b == NULL) || (c == NULL) || (d == NULL))
		goto err;

	if (!bn_mul(a,x,y)) goto err;
	if (!bn_rshift(d,a,nb-1)) goto err;
	if (!bn_mul(b,d,i)) goto err;
	if (!bn_rshift(c,b,nb-1)) goto err;
	if (!bn_mul(b,m,c)) goto err;
	if (!bn_sub(r,a,b)) goto err;
	j=0;
	while (bn_cmp(r,m) >= 0)
		{
		if (j++ > 2)
			goto err;
		if (!bn_sub(r,r,m))
			goto err;
		}

	bn_set_tos(tos);
	return(1);
err:
	bn_set_tos(tos);
	return(0);
	}

int bn_reciprical(r, m)
BIGNUM *r;
BIGNUM *m;
	{
	int nm,tos;
	BIGNUM *t;

	tos=bn_get_tos();
	t=bn_get_reg();
	if (t == NULL) goto err;

	if (!bn_one(t)) goto err;
	nm=bn_num_bits(m);
	if (!bn_lshift(t,t,nm*2)) goto err;

	if (!bn_div(r,NULL,t,m)) goto err;
	bn_set_tos(tos);
	return(nm+1);
err:
	bn_set_tos(tos);
	return(-1);
	}

char *bn_bn2ascii(a)
BIGNUM *a;
	{
	int i,j,v,z=0;
	static char *hex="0123456789ABCDEF";
	static char buf[1024];
	char *p=buf;

	if ((a->top*BYTES*2) > sizeof(buf)+2)
		return("buffer too small in bn_bn2ascii");
	if (a->neg) *(p++)='-';
	if (a->top == 0) *(p++)='0';
	for (i=a->top-1; i >=0; i--)
		{
		for (j=BITS2-4; j >= 0; j-=4)
			{
			/* strip leading zeros */
			v=(a->d[i]>>j)&0x0f;
			if (z || (v != 0))
				{
				*(p++)=hex[v];
				z=1;
				}
			}
		}
	return(buf);
	}

int bn_gcd(r,in_a,in_b)
BIGNUM *r,*in_a,*in_b;
	{
	BIGNUM *a,*b,*t;
	int tos,ret=0;

	tos=bn_get_tos();
	a=bn_get_reg();
	b=bn_get_reg();
	if ((a == NULL) || (b == NULL)) goto err;

	if (!bn_copy(a,in_a)) goto err;
	if (!bn_copy(b,in_b)) goto err;

	if (bn_cmp(a,b) < 0) { t=a; a=b; b=t; }
	t=euclid(a,b);
	if (t == NULL) goto err;

	r=bn_copy(r,t);
	ret=1;
err:
	bn_set_tos(tos);
	return(ret);
	}

static BIGNUM *euclid(a,b)
BIGNUM *a,*b;
	{
	BIGNUM *t;
	int shifts=0;

	for (;;)
		{
		if (bn_is_zero(b))
			break;

		if ((a->d[0]&1))	/* a is odd */
			{
			if (b->d[0]&1)  /* b is odd */
				{
				if (!bn_sub(a,a,b)) goto err;
				if (!bn_rshift1(a,a)) goto err;
				if (bn_cmp(a,b) < 0)
					{ t=a; a=b; b=t; }
				}
			else		/* a odd - b even */
				{
				if (!bn_rshift1(b,b)) goto err;
				if (bn_cmp(a,b) < 0)
					{ t=a; a=b; b=t; }
				}
			}
		else			/* a is even */
			{
			if (b->d[0]&1)	/* b id odd */
				{
				if (!bn_rshift1(a,a)) goto err;
				if (bn_cmp(a,b) < 0)
					{ t=a; a=b; b=t; }
				}
			else		/* a even - b even */
				{
				if (!bn_rshift1(a,a)) goto err;
				if (!bn_rshift1(b,b)) goto err;
				shifts++;
				}
			}
		}
	if (shifts)
		{
		if (!bn_lshift(a,a,shifts)) goto err;
		}
	return(a);
err:
	return(NULL);
	}