doc/bn.doc

   1 The Big Number library.
   2
   3 #include "bn.h" when using this library.
   4
   5 This big number library was written for use in implementing the RSA and DH
   6 public key encryption algorithms.  As such, features such as negative
   7 numbers have not been extensively tested but they should work as expected.
   8 This library uses dynamic memory allocation for storing its data structures
   9 and so there are no limit on the size of the numbers manipulated by these
  10 routines but there is always the requirement to check return codes from
  11 functions just in case a memory allocation error has occurred.
  12
  13 The basic object in this library is a BIGNUM.  It is used to hold a single
  14 large integer.  This type should be considered opaque and fields should not
  15 be modified or accessed directly.
  16 typedef struct bignum_st
  17         {
  18         int top;        /* Index of last used d. */
  19         BN_ULONG *d;    /* Pointer to an array of 'BITS2' bit chunks. */
  20         int max;        /* Size of the d array. */
  21         int neg;
  22         } BIGNUM;
  23 The big number is stored in a malloced array of BN_ULONG's.  A BN_ULONG can
  24 be either 16, 32 or 64 bits in size, depending on the 'number of  bits'
  25 specified in bn.h.
  26 The 'd' field is this array.  'max' is the size of the 'd' array that has
  27 been allocated.  'top' is the 'last' entry being used, so for a value of 4,
  28 bn.d[0]=4 and bn.top=1.  'neg' is 1 if the number is negative.
  29 When a BIGNUM is '0', the 'd' field can be NULL and top == 0.
  30
  31 Various routines in this library require the use of 'temporary' BIGNUM
  32 variables during their execution.  Due to the use of dynamic memory
  33 allocation to create BIGNUMs being rather expensive when used in
  34 conjunction with repeated subroutine calls, the BN_CTX structure is
  35 used.  This structure contains BN_CTX BIGNUMs.  BN_CTX
  36 is the maximum number of temporary BIGNUMs any publicly exported
  37 function will use.
  38
  39 #define BN_CTX  12
  40 typedef struct bignum_ctx
  41         {
  42         int tos;                        /* top of stack */
  43         BIGNUM *bn[BN_CTX];     /* The variables */
  44         } BN_CTX;
  45
  46 The functions that follow have been grouped according to function.  Most
  47 arithmetic functions return a result in the first argument, sometimes this
  48 first argument can also be an input parameter, sometimes it cannot.  These
  49 restrictions are documented.
  50
  51 extern BIGNUM *BN_value_one;
  52 There is one variable defined by this library, a BIGNUM which contains the
  53 number 1.  This variable is useful for use in comparisons and assignment.
  54
  55 Get Size functions.
  56
  57 int BN_num_bits(BIGNUM *a);
  58         This function returns the size of 'a' in bits.
  59
  60 int BN_num_bytes(BIGNUM *a);
  61         This function (macro) returns the size of 'a' in bytes.
  62         For conversion of BIGNUMs to byte streams, this is the number of
  63         bytes the output string will occupy.  If the output byte
  64         format specifies that the 'top' bit indicates if the number is
  65         signed, so an extra '0' byte is required if the top bit on a
  66         positive number is being written, it is upto the application to
  67         make this adjustment.  Like I said at the start, I don't
  68         really support negative numbers :-).
  69
  70 Creation/Destruction routines.
  71
  72 BIGNUM *BN_new();
  73         Return a new BIGNUM object.  The number initially has a value of 0.  If
  74         there is an error, NULL is returned.
  75
  76 void    BN_free(BIGNUM *a);
  77         Free()s a BIGNUM.
  78
  79 void    BN_clear(BIGNUM *a);
  80         Sets 'a' to a value of 0 and also zeros all unused allocated
  81         memory.  This function is used to clear a variable of 'sensitive'
  82         data that was held in it.
  83
  84 void    BN_clear_free(BIGNUM *a);
  85         This function zeros the memory used by 'a' and then free()'s it.
  86         This function should be used to BN_free() BIGNUMS that have held
  87         sensitive numeric values like RSA private key values.  Both this
  88         function and BN_clear tend to only be used by RSA and DH routines.
  89
  90 BN_CTX *BN_CTX_new(void);
  91         Returns a new BN_CTX.  NULL on error.
  92
  93 void    BN_CTX_free(BN_CTX *c);
  94         Free a BN_CTX structure.  The BIGNUMs in 'c' are BN_clear_free()ed.
  95
  96 BIGNUM *bn_expand(BIGNUM *b, int bits);
  97         This is an internal function that should not normally be used.  It
  98         ensures that 'b' has enough room for a 'bits' bit number.  It is
  99         mostly used by the various BIGNUM routines.  If there is an error,
 100         NULL is returned. if not, 'b' is returned.
 101
 102 BIGNUM *BN_copy(BIGNUM *to, BIGNUM *from);
 103         The 'from' is copied into 'to'.  NULL is returned if there is an
 104         error, otherwise 'to' is returned.
 105
 106 BIGNUM *BN_dup(BIGNUM *a);
 107         A new BIGNUM is created and returned containing the value of 'a'.
 108         NULL is returned on error.
 109
 110 Comparison and Test Functions.
 111
 112 int BN_is_zero(BIGNUM *a)
 113         Return 1 if 'a' is zero, else 0.
 114
 115 int BN_is_one(a)
 116         Return 1 is 'a' is one, else 0.
 117
 118 int BN_is_word(a,w)
 119         Return 1 if 'a' == w, else 0.  'w' is a BN_ULONG.
 120
 121 int BN_cmp(BIGNUM *a, BIGNUM *b);
 122         Return -1 if 'a' is less than 'b', 0 if 'a' and 'b' are the same
 123         and 1 is 'a' is greater than 'b'.  This is a signed comparison.
 124
 125 int BN_ucmp(BIGNUM *a, BIGNUM *b);
 126         This function is the same as BN_cmp except that the comparison
 127         ignores the sign of the numbers.
 128
 129 Arithmetic Functions
 130 For all of these functions, 0 is returned if there is an error and 1 is
 131 returned for success.  The return value should always be checked.  eg.
 132 if (!BN_add(r,a,b)) goto err;
 133 Unless explicitly mentioned, the 'return' value can be one of the
 134 'parameters' to the function.
 135
 136 int BN_add(BIGNUM *r, BIGNUM *a, BIGNUM *b);
 137         Add 'a' and 'b' and return the result in 'r'.  This is r=a+b.
 138
 139 int BN_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b);
 140         Subtract 'a' from 'b' and put the result in 'r'. This is r=a-b.
 141
 142 int BN_lshift(BIGNUM *r, BIGNUM *a, int n);
 143         Shift 'a' left by 'n' bits.  This is r=a*(2^n).
 144
 145 int BN_lshift1(BIGNUM *r, BIGNUM *a);
 146         Shift 'a' left by 1 bit.  This form is more efficient than
 147         BN_lshift(r,a,1).  This is r=a*2.
 148
 149 int BN_rshift(BIGNUM *r, BIGNUM *a, int n);
 150         Shift 'a' right by 'n' bits.  This is r=int(a/(2^n)).
 151
 152 int BN_rshift1(BIGNUM *r, BIGNUM *a);
 153         Shift 'a' right by 1 bit.  This form is more efficient than
 154         BN_rshift(r,a,1).  This is r=int(a/2).
 155
 156 int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b);
 157         Multiply a by b and return the result in 'r'. 'r' must not be
 158         either 'a' or 'b'.  It has to be a different BIGNUM.
 159         This is r=a*b.
 160
 161 int BN_sqr(BIGNUM *r, BIGNUM *a, BN_CTX *ctx);
 162         Multiply a by a and return the result in 'r'. 'r' must not be
 163         'a'.  This function is alot faster than BN_mul(r,a,a).  This is r=a*a.
 164
 165 int BN_div(BIGNUM *dv, BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx);
 166         Divide 'm' by 'd' and return the result in 'dv' and the remainder
 167         in 'rem'.  Either of 'dv' or 'rem' can be NULL in which case that
 168         value is not returned.  'ctx' needs to be passed as a source of
 169         temporary BIGNUM variables.
 170         This is dv=int(m/d), rem=m%d.
 171
 172 int BN_mod(BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx);
 173         Find the remainder of 'm' divided by 'd' and return it in 'rem'.
 174         'ctx' holds the temporary BIGNUMs required by this function.
 175         This function is more efficient than BN_div(NULL,rem,m,d,ctx);
 176         This is rem=m%d.
 177
 178 int BN_mod_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m,BN_CTX *ctx);
 179         Multiply 'a' by 'b' and return the remainder when divided by 'm'.
 180         'ctx' holds the temporary BIGNUMs required by this function.
 181         This is r=(a*b)%m.
 182
 183 int BN_mod_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,BN_CTX *ctx);
 184         Raise 'a' to the 'p' power and return the remainder when divided by
 185         'm'.  'ctx' holds the temporary BIGNUMs required by this function.
 186         This is r=(a^p)%m.
 187
 188 int BN_reciprocal(BIGNUM *r, BIGNUM *m, BN_CTX *ctx);
 189         Return the reciprocal of 'm'.  'ctx' holds the temporary variables
 190         required.  This function returns -1 on error, otherwise it returns
 191         the number of bits 'r' is shifted left to make 'r' into an integer.
 192         This number of bits shifted is required in BN_mod_mul_reciprocal().
 193         This is r=(1/m)<<(BN_num_bits(m)+1).
 194
 195 int BN_mod_mul_reciprocal(BIGNUM *r, BIGNUM *x, BIGNUM *y, BIGNUM *m,
 196         BIGNUM *i, int nb, BN_CTX *ctx);
 197         This function is used to perform an efficient BN_mod_mul()
 198         operation.  If one is going to repeatedly perform BN_mod_mul() with
 199         the same modulus is worth calculating the reciprocal of the modulus
 200         and then using this function.  This operation uses the fact that
 201         a/b == a*r where r is the reciprocal of b.  On modern computers
 202         multiplication is very fast and big number division is very slow.
 203         'x' is multiplied by 'y' and then divided by 'm' and the remainder
 204         is returned.  'i' is the reciprocal of 'm' and 'nb' is the number
 205         of bits as returned from BN_reciprocal().  Normal usage is as follows.
 206         bn=BN_reciprocal(i,m);
 207         for (...)
 208                 { BN_mod_mul_reciprocal(r,x,y,m,i,bn,ctx); }
 209         This is r=(x*y)%m.  Internally it is approximately
 210         r=(x*y)-m*(x*y/m) or r=(x*y)-m*((x*y*i) >> bn)
 211         This function is used in BN_mod_exp() and BN_is_prime().
 212
 213 Assignment Operations
 214
 215 int BN_one(BIGNUM *a)
 216         Set 'a' to hold the value one.
 217         This is a=1.
 218
 219 int BN_zero(BIGNUM *a)
 220         Set 'a' to hold the value zero.
 221         This is a=0.
 222
 223 int BN_set_word(BIGNUM *a, unsigned long w);
 224         Set 'a' to hold the value of 'w'.  'w' is an unsigned long.
 225         This is a=w.
 226
 227 unsigned long BN_get_word(BIGNUM *a);
 228         Returns 'a' in an unsigned long.  Not remarkably, often 'a' will
 229         be biger than a word, in which case 0xffffffffL is returned.
 230
 231 Word Operations
 232 These functions are much more efficient that the normal bignum arithmetic
 233 operations.
 234
 235 BN_ULONG BN_mod_word(BIGNUM *a, unsigned long w);
 236         Return the remainder of 'a' divided by 'w'.
 237         This is return(a%w).
 238
 239 int BN_add_word(BIGNUM *a, unsigned long w);
 240         Add 'w' to 'a'.  This function does not take the sign of 'a' into
 241         account.  This is a+=w;
 242
 243 Bit operations.
 244
 245 int BN_is_bit_set(BIGNUM *a, int n);
 246         This function return 1 if bit 'n' is set in 'a' else 0.
 247
 248 int BN_set_bit(BIGNUM *a, int n);
 249         This function sets bit 'n' to 1 in 'a'.
 250         This is a&= ~(1<<n);
 251
 252 int BN_clear_bit(BIGNUM *a, int n);
 253         This function sets bit 'n' to zero in 'a'.  Return 0 if less
 254         than 'n' bits in 'a' else 1.  This is a&= ~(1<<n);
 255
 256 int BN_mask_bits(BIGNUM *a, int n);
 257         Truncate 'a' to n bits long.  This is a&= ~((~0)<<n)
 258
 259 Format conversion routines.
 260
 261 BIGNUM *BN_bin2bn(unsigned char *s, int len,BIGNUM *ret);
 262         This function converts 'len' bytes in 's' into a BIGNUM which
 263         is put in 'ret'.  If ret is NULL, a new BIGNUM is created.
 264         Either this new BIGNUM or ret is returned.  The number is
 265         assumed to be in bigendian form in 's'.  By this I mean that
 266         to 'ret' is created as follows for 'len' == 5.
 267         ret = s[0]*2^32 + s[1]*2^24 + s[2]*2^16 + s[3]*2^8 + s[4];
 268         This function cannot be used to convert negative numbers.  It
 269         is always assumed the number is positive.  The application
 270         needs to diddle the 'neg' field of th BIGNUM its self.
 271         The better solution would be to save the numbers in ASN.1 format
 272         since this is a defined standard for storing big numbers.
 273         Look at the functions
 274
 275         ASN1_INTEGER *BN_to_ASN1_INTEGER(BIGNUM *bn, ASN1_INTEGER *ai);
 276         BIGNUM *ASN1_INTEGER_to_BN(ASN1_INTEGER *ai,BIGNUM *bn);
 277         int i2d_ASN1_INTEGER(ASN1_INTEGER *a,unsigned char **pp);
 278         ASN1_INTEGER *d2i_ASN1_INTEGER(ASN1_INTEGER **a,unsigned char **pp,
 279                 long length;
 280
 281 int BN_bn2bin(BIGNUM *a, unsigned char *to);
 282         This function converts 'a' to a byte string which is put into
 283         'to'.  The representation is big-endian in that the most
 284         significant byte of 'a' is put into to[0].  This function
 285         returns the number of bytes used to hold 'a'.  BN_num_bytes(a)
 286         would return the same value and can be used to determine how
 287         large 'to' needs to be.  If the number is negative, this
 288         information is lost.  Since this library was written to
 289         manipulate large positive integers, the inability to save and
 290         restore them is not considered to be a problem by me :-).
 291         As for BN_bin2bn(), look at the ASN.1 integer encoding funtions
 292         for SSLeay.  They use BN_bin2bn() and BN_bn2bin() internally.
 293
 294 char *BN_bn2ascii(BIGNUM *a);
 295         This function returns a malloc()ed string that contains the
 296         ascii hexadecimal encoding of 'a'.  The number is in bigendian
 297         format with a '-' in front if the number is negative.
 298
 299 int BN_ascii2bn(BIGNUM **bn, char *a);
 300         The inverse of BN_bn2ascii.  The function returns the number of
 301         characters from 'a' were processed in generating a the bignum.
 302         error is inticated by 0 being returned.  The number is a
 303         hex digit string, optionally with a leading '-'.  If *bn
 304         is null, a BIGNUM is created and returned via that variable.
 305
 306 int BN_print_fp(FILE *fp, BIGNUM *a);
 307         'a' is printed to file pointer 'fp'.  It is in the same format
 308         that is output from BN_bn2ascii().  0 is returned on error,
 309         1 if things are ok.
 310
 311 int BN_print(BIO *bp, BIGNUM *a);
 312         Same as BN_print except that the output is done to the SSLeay libraries
 313         BIO routines.  BN_print_fp() actually calls this function.
 314
 315 Miscellaneous Routines.
 316
 317 int BN_rand(BIGNUM *rnd, int bits, int top, int bottom);
 318         This function returns in 'rnd' a random BIGNUM that is bits
 319         long.  If bottom is 1, the number returned is odd.  If top is set,
 320         the top 2 bits of the number are set.  This is useful because if
 321         this is set, 2 'n; bit numbers multiplied together will return a 2n
 322         bit number.  If top was not set, they could produce a 2n-1 bit
 323         number.
 324
 325 BIGNUM *BN_mod_inverse(BIGNUM *a, BIGNUM *n,BN_CTX *ctx);
 326         This function create a new BIGNUM and returns it.  This number
 327         is the inverse mod 'n' of 'a'.  By this it is meant that the
 328         returned value 'r' satisfies (a*r)%n == 1.  This function is
 329         used in the generation of RSA keys.  'ctx', as per usual,
 330         is used to hold temporary variables that are required by the
 331         function.  NULL is returned on error.
 332
 333 int BN_gcd(BIGNUM *r,BIGNUM *a,BIGNUM *b,BN_CTX *ctx);
 334         'r' has the greatest common divisor of 'a' and 'b'.  'ctx' is
 335         used for temporary variables and 0 is returned on error.
 336
 337 int BN_is_prime(BIGNUM *p,int nchecks,void (*callback)(),BN_CTX *ctx,
 338         char *cb_arg);
 339         This function is used to check if a BIGNUM ('p') is prime.
 340         It performs this test by using the Miller-Rabin randomised
 341         primality test.  This is a probalistic test that requires a
 342         number of rounds to ensure the number is prime to a high
 343         degree of probability.  Since this can take quite some time, a
 344         callback function can be passed and it will be called each
 345         time 'p' passes a round of the prime testing.  'callback' will
 346         be called as follows, callback(1,n,cb_arg) where n is the number of
 347         the round, just passed.  As per usual 'ctx' contains temporary
 348         variables used.  If ctx is NULL, it does not matter, a local version
 349         will be malloced.  This parameter is present to save some mallocing
 350         inside the function but probably could be removed.
 351         0 is returned on error.
 352         'ncheck' is the number of Miller-Rabin tests to run.  It is
 353         suggested to use the value 'BN_prime_checks' by default.
 354
 355 BIGNUM *BN_generate_prime(
 356 int bits,
 357 int strong,
 358 BIGNUM *a,
 359 BIGNUM *rems,
 360 void (*callback)());
 361 char *cb_arg
 362         This function is used to generate prime numbers.  It returns a
 363         new BIGNUM that has a high probability of being a prime.
 364         'bits' is the number of bits that
 365         are to be in the prime.  If 'strong' is true, the returned prime
 366         will also be a strong prime ((p-1)/2 is also prime).
 367         While searching for the prime ('p'), we
 368         can add the requirement that the prime fill the following
 369         condition p%a == rem.  This can be used to help search for
 370         primes with specific features, which is required when looking
 371         for primes suitable for use with certain 'g' values in the
 372         Diffie-Hellman key exchange algorithm.  If 'a' is NULL,
 373         this condition is not checked.  If rem is NULL, rem is assumed
 374         to be 1.  Since this search for a prime
 375         can take quite some time, if callback is not NULL, it is called
 376         in the following situations.
 377         We have a suspected prime (from a quick sieve),
 378         callback(0,sus_prime++,cb_arg). Each item to be passed to BN_is_prime().
 379         callback(1,round++,cb_arg).  Each successful 'round' in BN_is_prime().
 380         callback(2,round,cb_arg). For each successful BN_is_prime() test.
 381