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);	}#elseint 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);	}#endifint 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);	}