/* lib/rsa/bn.c *//* Copyright (C) 1995 Eric Young (eay@mincom.oz.au) * All rights reserved. *  * This file is part of an SSL implementation written * by Eric Young (eay@mincom.oz.au). * The implementation was written so as to conform with Netscapes SSL * specification.  This library and applications are * FREE FOR COMMERCIAL AND NON-COMMERCIAL USE * as long as the following conditions are aheared to. *  * Copyright remains Eric Young's, and as such any Copyright notices in * the code are not to be removed.  If this code is used in a product, * Eric Young should be given attribution as the author of the parts used. * This can be in the form of a textual message at program startup or * in documentation (online or textual) provided with the package. *  * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the copyright *    notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright *    notice, this list of conditions and the following disclaimer in the *    documentation and/or other materials provided with the distribution. * 3. All advertising materials mentioning features or use of this software *    must display the following acknowledgement: *    This product includes software developed by Eric Young (eay@mincom.oz.au) *  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. *  * The licence and distribution terms for any publically available version or * derivative of this code cannot be changed.  i.e. this code cannot simply be * copied and put under another distribution licence * [including the GNU Public Licence.] */#include <stdio.h>#include "bn.h"#ifdef PROTOstatic void bn_SUB(BIGNUM *r, BIGNUM *a, BIGNUM *b);/*static void bn_fix_top(BIGNUM *a);*/static BIGNUM *euclid(BIGNUM *a, BIGNUM *b);#elsestatic void bn_SUB();/*static void bn_fix_top();*/static BIGNUM *euclid();#endifint bn_num_bits(a)BIGNUM *a;	{	int i;	BN_ULONG l;	static char bits[256]={		0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,		5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,		6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,		6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,		7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,		7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,		7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,		7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,		};	l=a->d[a->top-1];	i=(a->top-1)*BITS2;	if (l == 0)		{		fprintf(stderr,"BAD TOP VALUE\n");		abort();		}#ifdef SIXTY_FOUR_BIT	if (l & 0xffffffff00000000)		{		if (l & 0xffff000000000000)			{			if (l & 0xff00000000000000)				{				return(i+bits[l>>56]+56);				}			else	return(i+bits[l>>48]+48);			}		else			{			if (l & 0x0000ff0000000000)				{				return(i+bits[l>>40]+40);				}			else	return(i+bits[l>>32]+32);			}		}	else#endif		{#if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT)		if (l & 0xffff0000L)			{			if (l & 0xff000000L)				return(i+bits[l>>24L]+24);			else	return(i+bits[l>>16L]+16);			}		else#endif			{			if (l & 0xff00L)				return(i+bits[l>>8]+8);			else	return(i+bits[l   ]  );			}		}	}void bn_free(a)BIGNUM *a;	{	if (a == NULL) return;	if (a->d != NULL) free(a->d);	free(a);	}/*static void bn_fix_top(a)BIGNUM *a;	{	int i;	BN_ULONG *l;	l=a->d;	for (i=a->top-1; i>0; i--)		if (l[i]) break;	a->top=i+1;	}*/BIGNUM *bn_new()	{	BIGNUM *ret;	BN_ULONG *p;	ret=(BIGNUM *)malloc(sizeof(BIGNUM));	if (ret == NULL)		return NULL;	ret->top=0;	ret->neg=0;	ret->max=(DEFAULT_BITS/BITS2);	p=(BN_ULONG *)malloc(sizeof(BN_ULONG)*(ret->max+1));	if (p == NULL)		return NULL;	ret->d=p;	memset(p,0,(ret->max+1)*sizeof(p[0]));	return(ret);	}BIGNUM *bn_expand(b, bits)BIGNUM *b;int bits;	{	BN_ULONG *p;	register int n;/*	if (b == NULL)		{ RSAerr(RSA_F_BN_EXPAND,RSA_R_NULL_ARG); return(NULL); }*/	while (bits > b->max*BITS2)		{		n=((bits+BITS2-1)/BITS2)*2;		p=b->d=(BN_ULONG *)realloc(b->d,sizeof(BN_ULONG)*n+1);		if (p == NULL)			return NULL;		memset(&(p[b->max]),0,((n+1)-b->max)*sizeof(p[0]));/*		for (i=b->max; i<(n+1); i++)			p[i]=0;*/		b->max=n;		}	return(b);	}BIGNUM *bn_dup(a)BIGNUM *a;	{	BIGNUM *r;	r=bn_new();	if (r == NULL) return(NULL);	return((BIGNUM *)bn_copy(r,a));	}BIGNUM *bn_copy(a, b)BIGNUM *a;BIGNUM *b;	{/*	int i;*/	if (bn_expand(a,b->top*BITS2) == NULL) return(NULL);	memcpy(a->d,b->d,sizeof(b->d[0])*b->top);	memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));/*	for (i=0; i<b->top; i++)		a->d[i]=b->d[i];	for (;i<a->max; i++)		a->d[i]=0;*/	a->top=b->top;	a->neg=b->neg;	return(a);	}void bn_zero(a)BIGNUM *a;	{	memset(a->d,0,a->max*sizeof(a->d[0]));	a->top=0;	a->neg=0;	}int bn_one(a)BIGNUM *a;	{	if (bn_expand(a,1) == NULL) return(0);	memset(a->d,0,a->max);	a->d[0]=1;	a->top=1;	a->neg=0;	return(1);	}int bn_set_word(a,w)BIGNUM *a;unsigned long w;	{	if (bn_expand(a,sizeof(unsigned long)*8) == NULL) return(0);	memset(a->d,0,a->max);	a->d[0]=w;	a->top=1;	a->neg=0;	return(1);	}/* ignore negative */BIGNUM *bn_bin2bn(len, s, ret)int len;unsigned char *s;BIGNUM *ret;	{	unsigned int i,m;	unsigned int n;	BN_ULONG l;	if (ret == NULL) ret=bn_new();	if (ret == NULL) return(NULL);	l=0;	n=len;	if (n == 0)		{		ret->top=0;		return(ret);		}	if (bn_expand(ret,(int)n*8) == NULL)		return(NULL);	i=((n-1)/BYTES)+1;	m=((n-1)%(BYTES));	ret->top=i;	while (n-- > 0)		{		l=(l<<8)| *(s++);		if (m-- == 0)			{			ret->d[--i]=l;			l=0;			m=BYTES-1;			}		}	/* need to call this due to clear byte at top if avoiding	 * having the top bit set (-ve number) */	bn_fix_top(ret);	return(ret);	}void bn_print(fp, a)FILE *fp;BIGNUM *a;	{	int i,j,v,z=0;	static char *hex="0123456789ABCDEF";	if (a->neg) fputc('-',fp);	if (a->top == 0) fputc('0',fp);	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))				{				fputc(hex[v],fp);				z=1;				}			}		}	}/* ignore negative */int bn_bn2bin(a, to)BIGNUM *a;unsigned char *to;	{	int n,i;	BN_ULONG l;	n=i=bn_num_bytes(a);	while (i-- > 0)		{		l=a->d[i/BYTES];		*(to++)=(unsigned char)(l>>(8*(i%BYTES)))&0xff;		}	return(n);	}/* r can == a or b */int bn_add(r, a, b)BIGNUM *r;BIGNUM *a;BIGNUM *b;	{	register int i;	int max,min;	BN_ULONG *ap,*bp,*rp,carry,t1,t2;	BIGNUM *tmp;	/*  a +  b	a+b	 *  a + -b	a-b	 * -a +  b	b-a	 * -a + -b	-(a+b)	 */	if (a->neg ^ b->neg)		{		if (a->neg)			{ a->neg=0; i=bn_sub(r,b,a); if (a != r) a->neg=1; }		else			{ b->neg=0; i=bn_sub(r,a,b); if (b != r) b->neg=1; }		return(i);		}	if (a->neg) /* both are neg */		{		a->neg=0; b->neg=0; i=bn_add(r,a,b);		if (a != r) a->neg=1;		if (b != r) b->neg=1;		return(i);		}	if (a->top < b->top)		{ tmp=a; a=b; b=tmp; }			max=a->top;	min=b->top;	if (bn_expand(r,(max+1)*BITS2) == NULL) return(0);	r->top=max;	r->neg=0;	ap=a->d;	bp=b->d;	rp=r->d;	carry=0;	for (i=0; i<min; i++)		{		t1= *(ap++);		t2= *(bp++);		if (carry)			{			carry=(t2 >= ((~t1)&MASK2));			t2=(t1+t2+1)&MASK2;			}		else			{			t2=(t1+t2)&MASK2;			carry=(t2 < t1);			}		*(rp++)=t2;		}	if (carry)		{		while (i < max)			{			t1= *(ap++);			t2=(t1+1)&MASK2;			*(rp++)=t2;			carry=(t2 < t1);			i++;			if (!carry) break;			}		if ((i >= max) && carry)			{			*(rp++)=1;			r->top++;			}		}	for (; i<max; i++)		*(rp++)= *(ap++);	memcpy(rp,ap,sizeof(*ap)*(max-i));	return(1);	}int bn_Ucmp(a, b)BIGNUM *a;BIGNUM *b;	{	int i;	BN_ULONG t1,t2,*ap,*bp;	i=a->top-b->top;	if (i != 0) return(i);	ap=a->d;	bp=b->d;	for (i=a->top-1; i>=0; i--)		{		t1=ap[i];		t2=bp[i];		if (t1 > t2) return(1);		if (t1 < t2) return(-1);		}	return(0);	}int bn_cmp(a, b)BIGNUM *a;BIGNUM *b;	{	int i;	int gt,lt;	BN_ULONG t1,t2;	if (a->neg != b->neg)		{		if (a->neg)			return(-1);		else	return(1);		}	if (a->neg == 0)		{ gt=1; lt=-1; }	else	{ gt=-1; lt=1; }	if (a->top > b->top) return(gt);	if (a->top < b->top) return(lt);	for (i=a->top-1; i>=0; i--)		{		t1=a->d[i];		t2=b->d[i];		if (t1 > t2) return(gt);		if (t1 < t2) return(lt);		}	return(0);	}static void bn_SUB(r, a, b)BIGNUM *r;BIGNUM *a;BIGNUM *b;	{	int max,min;	register BN_ULONG t1,t2,*ap,*bp,*rp;	int i,carry;#if defined(IRIX_CC_BUG) && !defined(LINT)	int dummy;#endif	max=a->top;	min=b->top;	ap=a->d;	bp=b->d;	rp=r->d;	carry=0;	for (i=0; i<min; i++)		{		t1= *(ap++);		t2= *(bp++);		if (carry)			{			carry=(t1 <= t2);			t1=(t1-t2-1);			}		else			{			carry=(t1 < t2);			t1=(t1-t2);			}#if defined(IRIX_CC_BUG) && !defined(LINT)		dummy=t1;#endif		*(rp++)=t1&MASK2;		}	if (carry) /* subtracted */		{		while (i < max)			{			i++;			t1= *(ap++);			t2=(t1-1)&MASK2;			*(rp++)=t2;			if (t1 > t2) break;			}		}	memcpy(rp,ap,sizeof(*rp)*(max-i));/*	for (; i<max; i++)		*(rp++)=*(ap++);*/	r->top=max;	bn_fix_top(r);	}int bn_sub(r, a, b)BIGNUM *r;BIGNUM *a;BIGNUM *b;	{	int max,i;	/*  a -  b	a-b	 *  a - -b	a+b	 * -a -  b	-(a+b)	 * -a - -b	b-a	 */	if (a->neg)		{		if (b->neg)			{			a->neg=b->neg=0;			i=bn_sub(r,b,a);			if (a != r) a->neg=1;			if (b != r) b->neg=1;			}		else			{			a->neg=0;			i=bn_add(r,a,b);			r->neg=a->neg=1;			}		return(i);		}	else		{		if (b->neg)			{			b->neg=0;			i=bn_add(r,a,b);			if (r != b) b->neg=1;			return(i);			}		}	max=(a->top > b->top)?a->top:b->top;	if (bn_cmp(a,b) < 0)		{		if (bn_expand(r,max*BITS2) == NULL) return(0);		bn_SUB(r,b,a);		r->neg=1;		}	else		{		if (bn_expand(r,max*BITS2) == NULL) return(0);		bn_SUB(r,a,b);		r->neg=0;		}	return(1);	}int bn_lshift1(r, a)BIGNUM *r;BIGNUM *a;	{	register BN_ULONG *ap,*rp,t,c;	int i;	if (r != a)		{		r->neg=a->neg;		if (bn_expand(r,(a->top+1)*BITS2) == NULL) return(0);		r->top=a->top;		}	else		{		if (bn_expand(r,(a->top+1)*BITS2) == NULL) return(0);		}	ap=a->d;	rp=r->d;	c=0;	for (i=0; i<a->top; i++)		{		t= *(ap++);		*(rp++)=((t<<1)|c)&MASK2;		c=(t & TBIT)?1:0;		}	if (c)		{		*rp=1;		r->top++;		}	return(1);	}int bn_rshift1(r, a)