The Big Number library.#include "bn.h" when using this library.This big number library was written for use in implementing the RSA and DHpublic key encryption algorithms.  As such, features such as negativenumbers have not been extensively tested but they should work as expected.This library uses dynamic memory allocation for storing its data structuresand so there are no limit on the size of the numbers manipulated by theseroutines but there is always the requirement to check return codes fromfunctions just in case a memory allocation error has occurred.The basic object in this library is a BIGNUM.  It is used to hold a singlelarge integer.  This type should be considered opaque and fields should notbe modified or accessed directly.typedef struct bignum_st	{	int top;	/* Index of last used d. */	BN_ULONG *d;	/* Pointer to an array of 'BITS2' bit chunks. */	int max;	/* Size of the d array. */	int neg;	} BIGNUM;The big number is stored in a malloced array of BN_ULONG's.  A BN_ULONG canbe either 16, 32 or 64 bits in size, depending on the 'number of  bits'specified in bn.h. The 'd' field is this array.  'max' is the size of the 'd' array that hasbeen allocated.  'top' is the 'last' entry being used, so for a value of 4,bn.d[0]=4 and bn.top=1.  'neg' is 1 if the number is negative.When a BIGNUM is '0', the 'd' field can be NULL and top == 0.Various routines in this library require the use of 'temporary' BIGNUMvariables during their execution.  Due to the use of dynamic memoryallocation to create BIGNUMs being rather expensive when used inconjunction with repeated subroutine calls, the BN_CTX structure isused.  This structure contains BN_CTX BIGNUMs.  BN_CTXis the maximum number of temporary BIGNUMs any publicly exported function will use.#define BN_CTX	10typedef struct bignum_ctx	{	int tos;			/* top of stack */	BIGNUM *bn[BN_CTX];	/* The variables */	} BN_CTX;The functions that follow have been grouped according to function.  Mostarithmetic functions return a result in the first argument, sometimes thisfirst argument can also be an input parameter, sometimes it cannot.  Theserestrictions are documented.extern BIGNUM *BN_value_one;There is one variable defined by this library, a BIGNUM which contains thenumber 1.  This variable is useful for use in comparisons and assignment.Get Size functions.int BN_num_bits(BIGNUM *a);	This function returns the size of 'a' in bits.	int BN_num_bytes(BIGNUM *a);	This function (macro) returns the size of 'a' in bytes.	For conversion of BIGNUMs to byte streams, this is the number of	bytes the output string will occupy.  If the output byte	format specifies that the 'top' bit indicates if the number is	signed, so an extra '0' byte is required if the top bit on a	positive number is being written, it is upto the application to	make this adjustment.  Like I said at the start, I don't	really support negative numbers :-).Creation/Destruction routines.BIGNUM *BN_new();	Return a new BIGNUM object.  The number initially has a value of 0.  If	there is an error, NULL is returned.	void	BN_free(BIGNUM *a);	Free()s a BIGNUM.	void	BN_clear(BIGNUM *a);	Sets 'a' to a value of 0 and also zeros all unused allocated	memory.  This function is used to clear a variable of 'sensitive'	data that was held in it.	void	BN_clear_free(BIGNUM *a);	This function zeros the memory used by 'a' and then free()'s it.	This function should be used to BN_free() BIGNUMS that have held	sensitive numeric values like RSA private key values.  Both this	function and BN_clear tend to only be used by RSA and DH routines.BN_CTX *BN_CTX_new(void);	Returns a new BN_CTX.  NULL on error.	void	BN_CTX_free(BN_CTX *c);	Free a BN_CTX structure.  The BIGNUMs in 'c' are BN_clear_free()ed.	BIGNUM *bn_expand(BIGNUM *b, int bits);	This is an internal function that should not normally be used.  It	ensures that 'b' has enough room for a 'bits' bit number.  It is	mostly used by the various BIGNUM routines.  If there is an error,	NULL is returned. if not, 'b' is returned.	BIGNUM *BN_copy(BIGNUM *to, BIGNUM *from);	The 'from' is copied into 'to'.  NULL is returned if there is an	error, otherwise 'to' is returned.BIGNUM *BN_dup(BIGNUM *a);	A new BIGNUM is created and returned containing the value of 'a'.	NULL is returned on error.Comparison and Test Functions.int BN_is_zero(BIGNUM *a)	Return 1 if 'a' is zero, else 0.int BN_is_one(a)	Return 1 is 'a' is one, else 0.int BN_is_word(a,w)	Return 1 if 'a' == w, else 0.  'w' is a BN_ULONG.int BN_cmp(BIGNUM *a, BIGNUM *b);	Return -1 if 'a' is less than 'b', 0 if 'a' and 'b' are the same	and 1 is 'a' is greater than 'b'.  This is a signed comparison.	int BN_ucmp(BIGNUM *a, BIGNUM *b);	This function is the same as BN_cmp except that the comparison	ignores the sign of the numbers.	Arithmetic FunctionsFor all of these functions, 0 is returned if there is an error and 1 isreturned for success.  The return value should always be checked.  eg.if (!BN_add(r,a,b)) goto err;Unless explicitly mentioned, the 'return' value can be one of the'parameters' to the function.int BN_add(BIGNUM *r, BIGNUM *a, BIGNUM *b);	Add 'a' and 'b' and return the result in 'r'.  This is r=a+b.	int BN_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b);	Subtract 'a' from 'b' and put the result in 'r'. This is r=a-b.	int BN_lshift(BIGNUM *r, BIGNUM *a, int n);	Shift 'a' left by 'n' bits.  This is r=a*(2^n).	int BN_lshift1(BIGNUM *r, BIGNUM *a);	Shift 'a' left by 1 bit.  This form is more efficient than	BN_lshift(r,a,1).  This is r=a*2.	int BN_rshift(BIGNUM *r, BIGNUM *a, int n);	Shift 'a' right by 'n' bits.  This is r=int(a/(2^n)).	int BN_rshift1(BIGNUM *r, BIGNUM *a);	Shift 'a' right by 1 bit.  This form is more efficient than	BN_rshift(r,a,1).  This is r=int(a/2).	int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b);	Multiply a by b and return the result in 'r'. 'r' must not be	either 'a' or 'b'.  It has to be a different BIGNUM.	This is r=a*b.int BN_sqr(BIGNUM *r, BIGNUM *a, BN_CTX *ctx);	Multiply a by a and return the result in 'r'. 'r' must not be	'a'.  This function is alot faster than BN_mul(r,a,a).  This is r=a*a.int BN_div(BIGNUM *dv, BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx);	Divide 'm' by 'd' and return the result in 'dv' and the remainder	in 'rem'.  Either of 'dv' or 'rem' can be NULL in which case that	value is not returned.  'ctx' needs to be passed as a source of	temporary BIGNUM variables.	This is dv=int(m/d), rem=m%d.	int BN_mod(BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx);	Find the remainder of 'm' divided by 'd' and return it in 'rem'.	'ctx' holds the temporary BIGNUMs required by this function.	This function is more efficient than BN_div(NULL,rem,m,d,ctx);	This is rem=m%d.int BN_mod_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m,BN_CTX *ctx);	Multiply 'a' by 'b' and return the remainder when divided by 'm'.	'ctx' holds the temporary BIGNUMs required by this function.	This is r=(a*b)%m.int BN_mod_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,BN_CTX *ctx);	Raise 'a' to the 'p' power and return the remainder when divided by	'm'.  'ctx' holds the temporary BIGNUMs required by this function.	This is r=(a^p)%m.int BN_reciprocal(BIGNUM *r, BIGNUM *m, BN_CTX *ctx);	Return the reciprocal of 'm'.  'ctx' holds the temporary variables	required.  This function returns -1 on error, otherwise it returns	the number of bits 'r' is shifted left to make 'r' into an integer.	This number of bits shifted is required in BN_mod_mul_reciprocal().	This is r=(1/m)<<(BN_num_bits(m)+1).	int BN_mod_mul_reciprocal(BIGNUM *r, BIGNUM *x, BIGNUM *y, BIGNUM *m, 	BIGNUM *i, int nb, BN_CTX *ctx);	This function is used to perform an efficient BN_mod_mul()	operation.  If one is going to repeatedly perform BN_mod_mul() with	the same modulus is worth calculating the reciprocal of the modulus	and then using this function.  This operation uses the fact that	a/b == a*r where r is the reciprocal of b.  On modern computers	multiplication is very fast and big number division is very slow.	'x' is multiplied by 'y' and then divided by 'm' and the remainder	is returned.  'i' is the reciprocal of 'm' and 'nb' is the number	of bits as returned from BN_reciprocal().  Normal usage is as follows.	bn=BN_reciprocal(i,m);	for (...)		{ BN_mod_mul_reciprocal(r,x,y,m,i,bn,ctx); }	This is r=(x*y)%m.  Internally it is approximately	r=(x*y)-m*(x*y/m) or r=(x*y)-m*((x*y*i) >> bn)	This function is used in BN_mod_exp() and BN_is_prime().Assignment Operationsint BN_one(BIGNUM *a)	Set 'a' to hold the value one.	This is a=1.	int BN_zero(BIGNUM *a)	Set 'a' to hold the value zero.	This is a=0.	int BN_set_word(BIGNUM *a, unsigned long w);	Set 'a' to hold the value of 'w'.  'w' is an unsigned long.	This is a=w.Word OperationsThese functions are much more efficient that the normal bignum arithmeticoperations.BN_ULONG BN_mod_word(BIGNUM *a, unsigned long w);	Return the remainder of 'a' divided by 'w'.	This is return(a%w).	int BN_add_word(BIGNUM *a, unsigned long w);	Add 'w' to 'a'.  This function does not take the sign of 'a' into	account.  This is a+=w;	Bit operations.int BN_is_bit_set(BIGNUM *a, int n);	This function return 1 if bit 'n' is set in 'a' else 0.int BN_set_bit(BIGNUM *a, int n);	This function sets bit 'n' to 1 in 'a'.  Return 0 if less than	'n' bits in 'a', else 1.  This is a&= ~(1<<n);int BN_clear_bit(BIGNUM *a, int n);	This function sets bit 'n' to zero in 'a'.  Return 0 if less	than 'n' bits in 'a' else 1.  This is a&= ~(1<<n);int BN_mask_bits(BIGNUM *a, int n);	Truncate 'a' to n bits long.  This is a&= ~((~0)<<n)Format conversion routines.BIGNUM *BN_bin2bn(unsigned char *s, int len,BIGNUM *ret);	This function converts 'len' bytes in 's' into a BIGNUM which	is put in 'ret'.  If ret is NULL, a new BIGNUM is created.	Either this new BIGNUM or ret is returned.  The number is	assumed to be in bigendian form in 's'.  By this I mean that	to 'ret' is created as follows for 'len' == 5.	ret = s[0]*2^32 + s[1]*2^24 + s[2]*2^16 + s[3]*2^8 + s[4];	This function cannot be used to convert negative numbers.  It	is always assumed the number is positive.  The application	needs to diddle the 'neg' field of th BIGNUM its self.int BN_bn2bin(BIGNUM *a, unsigned char *to);	This function converts 'a' to a byte string which is put into	'to'.  The representation is big-endian in that the most	significant byte of 'a' is put into to[0].  This function	returns the number of bytes used to hold 'a'.  BN_num_bytes(a)	would return the same value and can be used to determine how	large 'to' needs to be.  If the number is negative, this	information is lost.  Since this library was written to	manipulate large positive integers, the inability to save and	restore them is not considered to be a problem by me :-).	char *BN_bn2ascii(BIGNUM *a);	This function returns a malloc()ed string that contains the	ascii hexadecimal encoding of 'a'.  The number is in bigendian	format with a '-' in front if the number is negative.	Currently there is no BN_ascii2bn() function, perhaps there	should be....	void BN_print(FILE *fp, BIGNUM *a);	'a' is printed to file pointer 'fp'.  It is in the same format	that is output from BN_bn2ascii().Miscellaneous Routines.int BN_rand(BIGNUM *rnd, int bits, int top, int bottom);	This function returns in 'rnd' a random BIGNUM that is bits	long.  If bottom is 1, the number returned is odd.  If top is set,	the top 2 bits of the number are set.  This is useful because if	this is set, 2 'n; bit numbers multiplied together will return a 2n	bit number.  If top was not set, they could produce a 2n-1 bit	number.BIGNUM *BN_mod_inverse(BIGNUM *a, BIGNUM *n,BN_CTX *ctx);	This function create a new BIGNUM and returns it.  This number	is the inverse mod 'n' of 'a'.  By this it is meant that the	returned value 'r' satisfies (a*r)%n == 1.  This function is	used in the generation of RSA keys.  'ctx', as per usual,	is used to hold temporary variables that are required by the	function.  NULL is returned on error.int BN_gcd(BIGNUM *r,BIGNUM *a,BIGNUM *b,BN_CTX *ctx);	'r' has the greatest common divisor of 'a' and 'b'.  'ctx' is	used for temporary variables and 0 is returned on error.int BN_is_prime(BIGNUM *p,int nchecks,void (*callback)(),BN_CTX *ctx);	This function is used to check if a BIGNUM ('p') is prime.	It performs this test by using the Miller-Rabin randomised	primality test.  This is a probalistic test that requires a	number of rounds to ensure the number is prime to a high	degree of probability.  Since this can take quite some time, a	callback function can be passed and it will be called each	time 'p' passes a round of the prime testing.  'callback' will	be called as follows, callback(1,n) where n is the number of	the round, just passed.  As per usual 'ctx' contains temporary	variables used.  0 is returned on error.	'ncheck' is the number of Miller-Rabin tests to run.  It is	suggested to use the value 'BN_prime_checks' by default.BIGNUM *BN_generate_prime(int bits,int strong,BIGNUM *a,BIGNUM *rems,void (*callback)());	This function is used to generate prime numbers.  It returns a	new BIGNUM that has a high probability of being a prime.	'bits' is the number of bits that	are to be in the prime.  If 'strong' is true, the returned prime	will also be a strong prime ((p-1)/2 is also prime).	While searching for the prime ('p'), we	can add the requirement that the prime fill the following	condition p%a == rem.  This can be used to help search for	primes with specific features, which is required when looking	for primes suitable for use with certain 'g' values in the	Diffie-Hellman key exchange algorithm.  If 'a' is NULL,	this condition is not checked.  If rem is NULL, rem is assumed	to be 1.  Since this search for a prime	can take quite some time, if callback is not NULL, it is called	in the following situations.	We have a suspected prime (from a quick sieve),	callback(0,sus_prime++).  Each item to be passed to BN_is_prime().	callback(1,round++).  Each successful 'round' in BN_is_prime().	callback(2,round). For each successful BN_is_prime() test.