/* acquired/ssleay/crypto/bn/bn_lib.c Summary/Purpose: XXXstring scanning and parsing */ /* $Log$ rights#1 License text in librock_LIDESC_HC=5dbcfd16d6433625e2d81575c94b6bd0a1e8825e */ #ifdef librock_MANUAL_bignum librock_CHISEL subject /math/int/ /* librock_BN_new - XXXXXXXXlibmib */ /**/ #include intxxx librock_BN_new( const char *XXXXlibmib; ); /* This is Eric A. Young's Big Number library from SSLeay 0.6.6, with names modified to have the librock_ prefix. (The prefix keeps the namespace clean. It is not to provide the appearance of different authorship.) Some changes to meet librock coding guidelines are also in place. This documentation is modified from SSLeay bn.doc The routines described here are software written by Eric Young (eay@mincom.oz.au) #include when using this library. This big number library was written for use in implementing the RSA and DH public key encryption algorithms. As such, features such as negative numbers have not been extensively tested but they should work as expected. */ /* The functions that follow have been grouped according to function. Most arithmetic functions return a result in the first argument, sometimes this first argument can also be an input parameter, sometimes it cannot. These restrictions are documented. */ /*
*/ /*

Creation/Destruction routines.

*/ /*
*/librock_BIGNUM *librock_BN_new(); /*
Return a new librock_BIGNUM object. The number initially has a value of 0. If there is an error, NULL is returned. This library uses dynamic memory allocation for storing its data structures so there is no limit on the size of the numbers manipulated. IMPORTANT: Since any operation may require resizing the result argument, there is always the requirement to check return codes from functions just in case a memory allocation error has occurred. The basic object in this library is a librock_BIGNUM. It is used to hold a single large integer. This type should be considered opaque and fields should not be modified or accessed directly. Showing the structure members here is to give an idea of the internal implementation. */ typedef struct librock_bignum_st { int top; /* Index of last used d. */ librock_BN_ULONG *d; /* Pointer to an array of 'librock_BITS2' bit chunks. */ int max; /* Size of the d array. */ int neg; } librock_BIGNUM; /* The big number is stored in @d, a malloced array of librock_BN_ULONG's. A librock_BN_ULONG can be either 16, 32 or 64 bits in size, depending on what integer types are defined by #include 'max' is the size of the 'd' array that has been 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 librock_BIGNUM is '0', the 'd' field can be NULL and top == 0. */ /*
*/void librock_BN_free(librock_BIGNUM *a); /*
Free()s a librock_BIGNUM. */ /*
*/void librock_BN_clear(librock_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 librock_BN_clear_free(librock_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. */ /*
*/librock_BIGNUM *librock_bn_expand(librock_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 librock_BIGNUM routines. If there is an error, NULL is returned. if not, 'b' is returned. */ /*
*/librock_BIGNUM *librock_BN_copy(librock_BIGNUM *to, librock_BIGNUM *from); /*
The 'from' is copied into 'to'. NULL is returned if there is an error, otherwise 'to' is returned. */ /*
*/librock_BIGNUM *librock_BN_dup(librock_BIGNUM *a); /*
A new librock_BIGNUM is created and returned containing the value of 'a'. NULL is returned on error. */ /*

Pre-allocated temporary space.

*/ /* Various routines in this library require the use of 'temporary' librock_BIGNUM variables during their execution. Due to the use of dynamic memory allocation to create librock_BIGNUMs being rather expensive when used in conjunction with repeated subroutine calls, the librock_librock_BN_CTX structure is used. This structure contains librock_librock_BN_CTX BIGNUMs. librock_librock_BN_CTX is the maximum number of temporary BIGNUMs any publicly exported function will use. */ #define librock_librock_BN_CTX 12 typedef struct librock_bignum_ctx { int tos; /* top of stack */ librock_BIGNUM *bn[librock_librock_BN_CTX]; /* The variables */ } librock_librock_BN_CTX; /*
*/librock_BN_CTX *librock_BN_CTX_new(void); /*
*/ /* Returns a new librock_BN_CTX. NULL on error. */ /*
*/void librock_BN_CTX_free(librock_BN_CTX *c); /*
Free a librock_BN_CTX structure. The BIGNUMs in 'c' are librock_BN_clear_free()ed. */ /*

Pre-defined constants.

*/ extern librock_BIGNUM *librock_BN_value_one; /* There is one variable defined by this library, a librock_BIGNUM which contains the number 1. This variable is useful for use in comparisons and assignment. */ /*

Get Size functions.

*/ /*
*/int librock_BN_num_bits(librock_BIGNUM *a); /*
*/ /* This function returns the size of 'a' in bits. */ /*
*/int librock_BN_num_bytes(librock_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 :-). */ /*

Comparison and Test Functions.

*/ /*
*/int librock_BN_is_zero(librock_BIGNUM *a) /*
*/ /* Return 1 if 'a' is zero, else 0. */ /*
*/int librock_BN_is_one(a) /*
*/ /* Return 1 is 'a' is one, else 0. */ /*
*/int librock_BN_is_word(a,w) /*
*/ /* Return 1 if 'a' == w, else 0. 'w' is a librock_BN_ULONG. */ /*
*/int librock_BN_cmp(librock_BIGNUM *a, librock_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 librock_BN_ucmp(librock_BIGNUM *a, librock_BIGNUM *b); /*
*/ /* This function is the same as librock_BN_cmp except that the comparison ignores the sign of the numbers. */ /*

Arithmetic Functions

*/ /*For all of these functions, 0 is returned if there is an error and 1 is returned for success. The return value should always be checked. eg. if (!librock_BN_add(r,a,b)) goto err; Unless explicitly mentioned, the 'return' value can be one of the 'parameters' to the function. */ /*
*/int librock_BN_add(librock_BIGNUM *r, librock_BIGNUM *a, librock_BIGNUM *b); /*
*/ /* Add 'a' and 'b' and return the result in 'r'. This is r=a+b. */ /*
*/int librock_BN_sub(librock_BIGNUM *r, librock_BIGNUM *a, librock_BIGNUM *b); /*
*/ /* Subtract 'a' from 'b' and put the result in 'r'. This is r=a-b. */ /*
*/int librock_BN_lshift(librock_BIGNUM *r, librock_BIGNUM *a, int n); /*
*/ /* Shift 'a' left by 'n' bits. This is r=a*(2^n). */ /*
*/int librock_BN_lshift1(librock_BIGNUM *r, librock_BIGNUM *a); /*
*/ /* Shift 'a' left by 1 bit. This form is more efficient than librock_BN_lshift(r,a,1). This is r=a*2. */ /*
*/int librock_BN_rshift(librock_BIGNUM *r, librock_BIGNUM *a, int n); /*
*/ /* Shift 'a' right by 'n' bits. This is r=int(a/(2^n)). */ /*
*/int librock_BN_rshift1(librock_BIGNUM *r, librock_BIGNUM *a); /*
*/ /* Shift 'a' right by 1 bit. This form is more efficient than librock_BN_rshift(r,a,1). This is r=int(a/2). */ /*
*/int librock_BN_mul(librock_BIGNUM *r, librock_BIGNUM *a, librock_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 librock_BIGNUM. This is r=a*b. */ /*
*/int librock_BN_sqr(librock_BIGNUM *r, librock_BIGNUM *a, librock_BN_CTX *ctx); /*
*/ /* Multiply a by a and return the result in 'r'. 'r' must not be 'a'. This function is alot faster than librock_BN_mul(r,a,a). This is r=a*a. */ /*
*/int librock_BN_div(librock_BIGNUM *dv, librock_BIGNUM *rem, librock_BIGNUM *m, librock_BIGNUM *d, librock_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 librock_BIGNUM variables. This is dv=int(m/d), rem=m%d. */ /*
*/int librock_BN_mod(librock_BIGNUM *rem, librock_BIGNUM *m, librock_BIGNUM *d, librock_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 librock_BN_div(NULL,rem,m,d,ctx); This is rem=m%d. */ /*
*/int librock_BN_mod_mul(librock_BIGNUM *r, librock_BIGNUM *a, librock_BIGNUM *b, librock_BIGNUM *m,librock_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 librock_BN_mod_exp(librock_BIGNUM *r, librock_BIGNUM *a, librock_BIGNUM *p, librock_BIGNUM *m,librock_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 librock_BN_reciprocal(librock_BIGNUM *r, librock_BIGNUM *m, librock_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 librock_BN_mod_mul_reciprocal(). This is r=(1/m)<<(librock_BN_num_bits(m)+1). */ /*
*/int librock_BN_mod_mul_reciprocal(librock_BIGNUM *r, librock_BIGNUM *x, librock_BIGNUM *y, librock_BIGNUM *m, /*
*/ /* librock_BIGNUM *i, int nb, librock_BN_CTX *ctx); This function is used to perform an efficient librock_BN_mod_mul() operation. If one is going to repeatedly perform librock_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 librock_BN_reciprocal(). Normal usage is as follows. bn=librock_BN_reciprocal(i,m); */ for (...) { librock_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 librock_BN_mod_exp() and librock_BN_is_prime(). */ /*

Assignment Operations

*/ /*
*/int librock_BN_one(librock_BIGNUM *a) /*
*/ /* Set 'a' to hold the value one. This is a=1. */ /*
*/int librock_BN_zero(librock_BIGNUM *a) /*
*/ /* Set 'a' to hold the value zero. This is a=0. */ /*
*/int librock_BN_set_word(librock_BIGNUM *a, unsigned long w); /*
*/ /* Set 'a' to hold the value of 'w'. 'w' is an unsigned long. This is a=w. */ /*
*/unsigned long librock_BN_get_word(librock_BIGNUM *a); /*
*/ /* Returns 'a' in an unsigned long. Not remarkably, often 'a' will be biger than a word, in which case 0xffffffffL is returned. */ /*

Word Operations

*/ /*These functions are much more efficient that the normal librock_BIGNUM arithmetic operations. */ /*
*/librock_BN_ULONG librock_BN_mod_word(librock_BIGNUM *a, unsigned long w); /*
*/ /* Return the remainder of 'a' divided by 'w'. This is return(a%w). */ /*
*/int librock_BN_add_word(librock_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 librock_BN_is_bit_set(librock_BIGNUM *a, int n); /*
*/ /* This function return 1 if bit 'n' is set in 'a' else 0. */ /*
*/int librock_BN_set_bit(librock_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<
*/int librock_BN_clear_bit(librock_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<
*/int librock_BN_mask_bits(librock_BIGNUM *a, int n); /*
*/ /* Truncate 'a' to n bits long. This is a&= ~((~0)<

Format conversion routines.

*/ /*
*/librock_BIGNUM *librock_BN_bin2bn(unsigned char *s, int len,librock_BIGNUM *ret); /*
*/ /* This function converts 'len' bytes in 's' into a librock_BIGNUM which is put in 'ret'. If ret is NULL, a new librock_BIGNUM is created. Either this new librock_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 librock_BIGNUM its self. The better solution would be to save the numbers in ASN.1 format since this is a defined standard for storing big numbers. Look at the functions ASN1_INTEGER *librock_BN_to_ASN1_INTEGER(librock_BIGNUM *bn, ASN1_INTEGER *ai); librock_BIGNUM *ASN1_INTEGER_to_BN(ASN1_INTEGER *ai,librock_BIGNUM *bn); int i2d_ASN1_INTEGER(ASN1_INTEGER *a,unsigned char **pp); ASN1_INTEGER *d2i_ASN1_INTEGER(ASN1_INTEGER **a,unsigned char **pp, long length; */ /*
*/int librock_BN_bn2bin(librock_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'. librock_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 :-). As for librock_BN_bin2bn(), look at the ASN.1 integer encoding funtions for SSLeay. They use librock_BN_bin2bn() and librock_BN_bn2bin() internally. */ /*
*/char *librock_BN_bn2ascii(librock_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. Caller must 'free()' the returned data. */ /*
*/int librock_BN_ascii2bn(librock_BIGNUM **bn, char *a); /*
*/ /* The inverse of librock_BN_bn2ascii. The function returns the number of characters from 'a' were processed in generating a the librock_BIGNUM. error is inticated by 0 being returned. The number is a hex digit string, optionally with a leading '-'. If *bn is null, a librock_BIGNUM is created and returned via that variable. /*
*/int librock_BN_print_fp(FILE *fp, librock_BIGNUM *a); /*
*/ /* 'a' is printed to file pointer 'fp'. It is in the same format that is output from librock_BN_bn2ascii(). 0 is returned on error, 1 if things are ok. */ /*
*/int librock_BN_print(BIO *bp, librock_BIGNUM *a); /*
*/ /* Same as librock_BN_print except that the output is done to the SSLeay libraries BIO routines. librock_BN_print_fp() actually calls this function. */ /*

Miscellaneous Routines.

*/ /*
*/int librock_BN_rand(librock_BIGNUM *rnd, int bits, int top, int bottom); /*
*/ /* This function returns in 'rnd' a random librock_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. */ /*
*/librock_BIGNUM *librock_BN_mod_inverse(librock_BIGNUM *a, librock_BIGNUM *n,librock_BN_CTX *ctx); /*
*/ /* This function create a new librock_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 librock_BN_gcd(librock_BIGNUM *r,librock_BIGNUM *a,librock_BIGNUM *b,librock_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 librock_BN_is_prime(librock_BIGNUM *p,int nchecks,void (*callback)(),librock_BN_CTX *ctx); /*
*/ /* This function is used to check if a librock_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 'librock_BN_prime_checks' by default. */ /*
*/librock_BIGNUM *librock_BN_generate_prime( int bits, int strong, librock_BIGNUM *a, librock_BIGNUM *rems, void (*callback)()); /*
*/ /* This function is used to generate prime numbers. It returns a new librock_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 librock_BN_is_prime(). callback(1,round++). Each successful 'round' in librock_BN_is_prime(). callback(2,round). For each successful librock_BN_is_prime() test. */ /*
*/ Typical use is */ XXXX typical use /* XXXX what it calls. */ /* Copyright (C) 1995-1997 Eric Young (eay@mincom.oz.au) Licensed under BSD-ish license, NO WARRANTY. Copies must retain this block. License text in librock_LIDESC_HC=5dbcfd16d6433625e2d81575c94b6bd0a1e8825e */ #endif /* MANUAL */ #ifndef librock_ISOLATED /**************************************************************/ #define librock_IMPLEMENT_bn_lib #include /* sprintf */ #include #include /* memset */ #include "bn.h" #include /**************************************************************/ #endif #ifndef librock_NOIMPL_LIDESC_bn_lib /* License description features are documented at http://www.mibsoftware.com/librock/ */ /* librock_ACQUIRED: #FIXME: YYYY-MM-DD# #FIXME: download-url# #FIXME: homepage# */ #ifdef librock_IMPL_LIDESC /**************************************************************/ #include /* librock_LIDESC_HC=5dbcfd16d6433625e2d81575c94b6bd0a1e8825e */ char *librock_LIDESC_bn_lib[] = { "\n" __FILE__ librock_LIDESC_ssleay "\n", 0 }; /**************************************************************/ #endif #endif #ifndef librock_WRAP /* Function wrapping and tracing features are documented at http://www.mibsoftware.com/librock/ */ /**************************************************************/ #define Free free #define Malloc malloc #define Realloc realloc #define BNerr(a,b) /**************************************************************/ #endif /* crypto/bn/bn_lib.c */ /* Copyright (C) 1995-1997 Eric Young (eay@mincom.oz.au) * All rights reserved. * * This package is an SSL implementation written * by Eric Young (eay@mincom.oz.au). * The implementation was written so as to conform with Netscapes SSL. * * This library is free for commercial and non-commercial use as long as * the following conditions are aheared to. The following conditions * apply to all code found in this distribution, be it the RC4, RSA, * lhash, DES, etc., code; not just the SSL code. The SSL documentation * included with this distribution is covered by the same copyright terms * except that the holder is Tim Hudson (tjh@mincom.oz.au). * * Copyright remains Eric Young's, and as such any Copyright notices in * the code are not to be removed. * If this package is used in a product, Eric Young should be given attribution * as the author of the parts of the library 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 cryptographic software written by * Eric Young (eay@mincom.oz.au)" * The word 'cryptographic' can be left out if the rouines from the library * being used are not cryptographic related :-). * 4. If you include any Windows specific code (or a derivative thereof) from * the apps directory (application code) you must include an acknowledgement: * "This product includes software written by Tim Hudson (tjh@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.] */ #if 0 #include #include "cryptlib.h" #include "bn.h" #endif char *BN_version="Big Number part of SSLeay 0.6.6 14-Jan-1997"; static BN_ULONG data_one=1L; static BIGNUM const_one={&data_one,1,1,0}; BIGNUM *BN_value_one= &const_one; char *BN_options() { static int init=0; static char data[16]; if (!init) { init++; #ifdef librock_BN_LLONG sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULLONG)*8, (int)sizeof(BN_ULONG)*8); #else sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULONG)*8, (int)sizeof(BN_ULONG)*8); #endif } return(data); } int BN_num_bits_word(l) 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, }; #ifdef SIXTY_FOUR_BIT if (l & 0xffffffff00000000) { if (l & 0xffff000000000000) { if (l & 0xff00000000000000) { return(bits[l>>56]+56); } else return(bits[l>>48]+48); } else { if (l & 0x0000ff0000000000) { return(bits[l>>40]+40); } else return(bits[l>>32]+32); } } else #endif { #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) if (l & 0xffff0000L) { if (l & 0xff000000L) return(bits[l>>24L]+24); else return(bits[l>>16L]+16); } else #endif { #if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) if (l & 0xff00L) return(bits[l>>8]+8); else #endif return(bits[l ] ); } } } int BN_num_bits(a) BIGNUM *a; { BN_ULONG l; int i; if (a->top == 0) return(0); l=a->d[a->top-1]; i=(a->top-1)*BN_BITS2; if (l == 0) { #ifdef librock_INC_BIGNUM_H return -1; /* error */ #else #ifndef WIN16 fprintf(stderr,"BAD TOP VALUE\n"); #endif abort(); #endif } return(i+BN_num_bits_word(l)); } void BN_clear_free(a) BIGNUM *a; { if (a == 0) return; if (a->d != 0) { memset(a->d,0,a->max*sizeof(a->d[0])); Free(a->d); } memset(a,0,sizeof(BIGNUM)); Free(a); } void BN_free(a) BIGNUM *a; { if (a == NULL) return; if (a->d != NULL) Free(a->d); Free(a); } BIGNUM *BN_new() { BIGNUM *ret; BN_ULONG *p; ret=(BIGNUM *)Malloc(sizeof(BIGNUM)); if (ret == NULL) goto err; ret->top=0; ret->neg=0; ret->max=(BN_DEFAULT_BITS/BN_BITS2); p=(BN_ULONG *)Malloc(sizeof(BN_ULONG)*(ret->max+1)); if (p == NULL) goto err; ret->d=p; memset(p,0,(ret->max+1)*sizeof(p[0])); return(ret); err: BNerr(BN_F_BN_NEW,ERR_R_MALLOC_FAILURE); return(NULL); } BN_CTX *BN_CTX_new() { BN_CTX *ret; BIGNUM *n; int i,j; ret=(BN_CTX *)Malloc(sizeof(BN_CTX)); if (ret == NULL) goto err2; for (i=0; ibn[i]=n; } ret->tos=0; return(ret); err: for (j=0; jbn[j]); Free(ret); err2: BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE); return(NULL); } void BN_CTX_free(c) BN_CTX *c; { int i; for (i=0; ibn[i]); Free(c); } BIGNUM *bn_expand2(b, bits) BIGNUM *b; int bits; { BN_ULONG *p; register int n; while (bits > b->max*BN_BITS2) { n=((bits+BN_BITS2-1)/BN_BITS2)*2; p=b->d=(BN_ULONG *)Realloc(b->d,sizeof(BN_ULONG)*(n+1)); if (p == NULL) { BNerr(BN_F_BN_EXPAND2,ERR_R_MALLOC_FAILURE); return(NULL); } memset(&(p[b->max]),0,((n+1)-b->max)*sizeof(BN_ULONG)); 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; { if (bn_expand(a,b->top*BN_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));*/ a->top=b->top; a->neg=b->neg; return(a); } void BN_clear(a) BIGNUM *a; { memset(a->d,0,a->max*sizeof(a->d[0])); a->top=0; a->neg=0; } unsigned long BN_get_word(a) BIGNUM *a; { int i,n; unsigned long ret=0; n=BN_num_bytes(a); if (n > sizeof(unsigned long)) return(0xFFFFFFFF); for (i=a->top-1; i>=0; i--) { ret<<=BN_BITS4; /* stops the compiler complaining */ ret<<=BN_BITS4; ret|=a->d[i]; } return(ret); } int BN_set_word(a,w) BIGNUM *a; unsigned long w; { int i,n; if (bn_expand(a,sizeof(unsigned long)*8) == NULL) return(0); n=sizeof(unsigned long)/BN_BYTES; a->neg=0; a->top=0; a->d[0]=(BN_ULONG)w&BN_MASK2; if (a->d[0] != 0) a->top=1; for (i=1; i>=BN_BITS2 so compilers don't complain * on builds where sizeof(long) == BN_TYPES */ w>>=BN_BITS4; w>>=BN_BITS4; a->d[i]=(BN_ULONG)w&BN_MASK2; if (a->d[i] != 0) a->top=i+1; } return(1); } /* ignore negative */ BIGNUM *BN_bin2bn(s, len, ret) unsigned char *s; int len; 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+2)*8) == NULL) return(NULL); i=((n-1)/BN_BYTES)+1; m=((n-1)%(BN_BYTES)); ret->top=i; while (n-- > 0) { l=(l<<8)| *(s++); if (m-- == 0) { ret->d[--i]=l; l=0; m=BN_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); } /* 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/BN_BYTES]; *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff; } return(n); } 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(t1 > t2?1:-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); } int BN_set_bit(a, n) BIGNUM *a; int n; { int i,j; i=n/BN_BITS2; j=n%BN_BITS2; if (a->top <= i) return(0); a->d[i]|=(1L<top <= i) return(0); a->d[i]&=(~(1L<top <= i) return(0); return((a->d[i]&(1L<= a->top) return(0); if (b == 0) a->top=w; else { a->top=w+1; a->d[w]&= ~(BN_MASK2<= 0) && (a->d[w] == 0)) { a->top--; w--; } } return(1); }