diff options
Diffstat (limited to 'lib/libssl/src/doc/bn.doc')
| -rw-r--r-- | lib/libssl/src/doc/bn.doc | 381 |
1 files changed, 0 insertions, 381 deletions
diff --git a/lib/libssl/src/doc/bn.doc b/lib/libssl/src/doc/bn.doc deleted file mode 100644 index 47be23b6eaf..00000000000 --- a/lib/libssl/src/doc/bn.doc +++ /dev/null @@ -1,381 +0,0 @@ -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'. - 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, - char *cb_arg); - 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,cb_arg) 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)()); -char *cb_arg - 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++,cb_arg). Each item to be passed to BN_is_prime(). - callback(1,round++,cb_arg). Each successful 'round' in BN_is_prime(). - callback(2,round,cb_arg). For each successful BN_is_prime() test. - |