diff options
Diffstat (limited to 'doc/bn.doc')
| -rw-r--r-- | doc/bn.doc | 379 |
1 files changed, 379 insertions, 0 deletions
diff --git a/doc/bn.doc b/doc/bn.doc new file mode 100644 index 0000000000..2358c20f45 --- /dev/null +++ b/doc/bn.doc @@ -0,0 +1,379 @@ +The Big Number library. + +#include "bn.h" 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. +This library uses dynamic memory allocation for storing its data structures +and so there are no limit on the size of the numbers manipulated by these +routines but 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 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. +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 can +be 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 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 BIGNUM is '0', the 'd' field can be NULL and top == 0. + +Various routines in this library require the use of 'temporary' BIGNUM +variables during their execution. Due to the use of dynamic memory +allocation to create BIGNUMs being rather expensive when used in +conjunction with repeated subroutine calls, the BN_CTX structure is +used. This structure contains BN_CTX BIGNUMs. BN_CTX +is the maximum number of temporary BIGNUMs any publicly exported +function will use. + +#define BN_CTX 12 +typedef 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. 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. + +extern BIGNUM *BN_value_one; +There is one variable defined by this library, a BIGNUM which contains the +number 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 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 (!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 Operations + +int 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. + +unsigned long BN_get_word(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 bignum arithmetic +operations. + +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. + 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 *BN_to_ASN1_INTEGER(BIGNUM *bn, ASN1_INTEGER *ai); + BIGNUM *ASN1_INTEGER_to_BN(ASN1_INTEGER *ai,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 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 :-). + As for BN_bin2bn(), look at the ASN.1 integer encoding funtions + for SSLeay. They use BN_bin2bn() and BN_bn2bin() internally. + +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. + +int BN_ascii2bn(BIGNUM **bn, char *a); + The inverse of BN_bn2ascii. The function returns the number of + characters from 'a' were processed in generating a the bignum. + error is inticated by 0 being returned. The number is a + hex digit string, optionally with a leading '-'. If *bn + is null, a BIGNUM is created and returned via that variable. + +int BN_print_fp(FILE *fp, BIGNUM *a); + 'a' is printed to file pointer 'fp'. It is in the same format + that is output from BN_bn2ascii(). 0 is returned on error, + 1 if things are ok. + +int BN_print(BIO *bp, BIGNUM *a); + Same as BN_print except that the output is done to the SSLeay libraries + BIO routines. BN_print_fp() actually calls this function. + +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. If ctx is NULL, it does not matter, a local version + will be malloced. This parameter is present to save some mallocing + inside the function but probably could be removed. + 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. + |