7.4. Manipulating Big Numbers

Problem

You need to do integer-based arithmetic on numbers that are too large to represent in 32 (or 64) bits. For example, you may need to implement a public key algorithm that isn't supported by the library you're using.

Solution

Use a preexisting library for arbitrary-precision integer math, such as the BIGNUM library that comes with OpenSSL (discussed here) or the GNU Multi-Precision (gmp) library.

Discussion

Most of the world tends to use a small set of public key primitives, and the popular libraries reflect that fact. There are a lot of interesting things you can do with public key cryptography that are in the academic literature but not in real libraries, such as a wide variety of different digital signature techniques.

If you need such a primitive and there aren't good free libraries that implement it, you may need to strike off on your own, which will generally require doing math with very large numbers.

In general, arbitrary-precision libraries work by keeping an array of words that represents the value of a number, then implementing operations on that representation in software. Math on very large numbers tends to be slow, and software implementation of such math tends to be even slower. While there are tricks that occasionally come in handy (such as using a fast Fourier transform for multiplication instead of longhand multiplication when the numbers are large enough to merit it), such libraries still tend to be slow, even though the most speed-critical parts are often implemented in hand-optimized assembly. For this reason, it's a good idea to stick with a preexisting library for arbitrary-precision arithmetic if you have general-purpose needs.

In this recipe, we'll cover the OpenSSL BIGNUM library, which supports arbitrary precision math, albeit with a very quirky interface.

Initialization and cleanup

The BIGNUM library generally lives in libcrypto , which comes with OpenSSL. Its API is defined in openssl/bn.h. This library exports the BIGNUM type. BIGNUM objects always need to be initialized before use, even if they're statically declared. For example, here's how to initialize a statically allocated BIGNUM object:

BIGNUM bn;
   
void BN_init(&bn);

If you're dynamically allocating a BIGNUM object, OpenSSL provides a function that allocates and initializes in one fell swoop:

BIGNUM *bn = BN_new(  );

You should not use malloc( ) to allocate a BIGNUM object because you are likely to confuse the library (it may believe that your object is unallocated).

If you would like to deallocate a BIGNUM object that was allocated using BN_new( ), pass it to BN_free( ) .

In addition, for security purposes, you may wish to zero out the memory used by a BIGNUM object before you deallocate it. If so, pass it to BN_clear( ) , which explicitly overwrites all memory in use by a BIGNUM context. You can also zero and free in one operation by passing the object to BIGNUM_clear_free( ) .

void BN_free(BIGNUM *bn);
void BN_clear(BIGNUM *bn);
void BN_clear_free(BIGNUM *bn);

Some operations may require you to allocate BN_CTX objects. These objects are scratch space for temporary values. You should always create BN_CTX objects dynamically by calling BN_CTX_new( ) , which will return a dynamically allocated and initialized BN_CTX object. When you're done with a BN_CTX object, destroy it by passing it to BN_CTX_free( ) .

BN_CTX *BN_CTX_new(void);
int BN_CTX_free(BN_CTX *c);

Assigning to BIGNUM objects

Naturally, we'll want to assign numerical values to BIGNUM objects. The easiest way to do this is to copy another number. OpenSSL provides a way to allocate a new BIGNUM object and copy a second BIGNUM object all at once:

BIGNUM *BN_dup(BIGNUM *bn_to_copy);

In addition, if you already have an allocated context, you can just call BN_copy( ) , which has the following signature:

BIGNUM *BN_copy(BIGNUM *destination_bn, BIGNUM *src_bn);

This function returns destination_bn on success.

You can assign the value 0 to a BIGNUM object with the following function:

int BN_zero(BIGNUM *bn);

You can also use BN_clear( ) , which will write over the old value first.

int BN_one(BIGNUM *bn);

You can also assign any nonnegative value that fits in an unsigned long using the function BN_set_word( ) :

int BN_set_word(BIGNUM *bn, unsigned long value);

The previous three functions return 1 on success.

If you need to assign a positive number that is too large to represent as an unsigned long, you can represent it in binary as a sequence of bytes and have OpenSSL convert the binary buffer to a BIGNUM object. Note that the bytes must be in order from most significant to least significant. That is, you can't just point OpenSSL at memory containing a 64-bit long long (_ _int64 on Windows) on a little-endian machine, because the bytes will be backwards. Once your buffer is in the right format, you can use the function BN_bin2bn( ) , which has the following signature:

BIGNUM *BN_bin2bn(unsigned char *buf, int len, BIGNUM *c);

This function has the following arguments:

buf: Buffer containing the binary representation to be converted.
len: Length of the buffer in bits. It does not need to be a multiple of eight. Extra bits in the buffer will be ignored.
c: BIGNUM object to be loaded with the value from the binary representation. This may be specified as NULL, in which case a new BIGNUM object will be dynamically allocated. The new BIGNUM object will be returned if one is allocated; otherwise, the specified BIGNUM object will be returned.

None of the previously mentioned techniques allows us to represent a negative number. The simplest technique is to get the corresponding positive integer, then use the following macro that takes a pointer to a BIGNUM object and negates it (i.e., multiplies by -1):

#define BN_negate(x) ((x)->neg = (!((x)->neg)) & 1)

Getting BIGNUM objects with random values

Before you can get BIGNUM objects with random values, you need to have seeded the OpenSSL random number generator. (With newer versions of OpenSSL, the generator will be seeded for you on most platforms; see Recipe 11.9).

One common thing to want to do is generate a random prime number. The API for this is somewhat complex:

BIGNUM *BN_generate_prime(BIGNUM *ret, int num, int safe, BIGNUM *add, BIGNUM *rem, 
                          void (*callback)(int, int, void *), void *cb_arg);

This function has the following arguments:

ret: An allocated BIGNUM object, which will also be returned on success. If it is specified as NULL, a new BIGNUM object will be dynamically allocated and returned instead. The prime number that is generated will be stored in this object.
num: Number of bits that should be in the generated prime number.
safe

Note that, depending on your hardware, it can take several seconds to generate a prime number, even if you have sufficient entropy available. The callback functionality allows you to monitor the progress of prime generation. Unfortunately, there's no way to determine how much time finding a prime will actually take, so it's not feasible to use this callback to implement a progress meter. We do not discuss the callback mechanism any further in this book. However, callbacks are discussed in the book Network Security with OpenSSL by John Viega, Matt Messier, and Pravir Chandra (O'Reilly & Associates) as well as in the online OpenSSL documentation.

It's much simpler to get a BIGNUM object with a random value:

int BN_rand_range(BIGNUM *result, BIGNUM *range);

This function requires you to pass in a pointer to an initialized BIGNUM object that receives the random value. The possible values for the random number are zero through one less than the specified range.

Additionally, you can ask for a random number with a specific number of bits:

int BN_rand(BIGNUM *result, int bits, int top, int bottom);

This function has the following arguments:

result: The generated random number will be stored in this BIGNUM object.
bits: Number of bits that the generated random number should contain.
top: If the value of this argument is 0, the most significant bit in the generated random number will be set. If it is -1, the most significant bit can be anything. If it is 1, the 2 most significant bits will be set. This is useful when you want to make sure that the product of 2 numbers of a particular bit length will always have exactly twice as many bits.
bottom

Outputting BIGNUM objects

If you wish to represent your BIGNUM object as a binary number, you can use BN_bn2bin( ) , which will store the binary representation of the BIGNUM object in the buffer pointed to by the outbuf argument:

int BN_bn2bin(BIGNUM *bn, unsigned char *outbuf);

Unfortunately, you first need to know in advance how big the output buffer needs to be. You can learn this by calling BN_num_bytes( ) , which has the following signature:

int BN_num_bytes(BIGNUM *bn);

Warning

BN_bn2bin( ) will not output the sign of a number. You can manually query the sign of the number by using the following macro:

#define BN_is_negative(x) ((x)->neg)

The following is a wrapper that converts a BIGNUM object to binary, allocating its result via malloc( ) and properly setting the most significant bit to 1 if the result is negative. Note that you have to pass in a pointer to an unsigned integer. That integer gets filled with the size of the returned buffer in bytes.

#include <stdlib.h>
#include <openssl/bn.h>
   
#define BN_is_negative(x) ((x)->neg)
   
unsigned char *BN_to_binary(BIGNUM *b, unsigned int *outsz) {
  unsigned char *ret;
  
  *outsz = BN_num_bytes(b);
  if (BN_is_negative(b)) {

    (*outsz)++;
    if (!(ret = (unsigned char *)malloc(*outsz))) return 0;
    BN_bn2bin(b, ret + 1);
    ret[0] = 0x80;
  } else {
    if (!(ret = (unsigned char *)malloc(*outsz))) return 0;
    BN_bn2bin(b, ret);
  }
  return ret;
}

Warning

Remember that the binary format used by a BIGNUM object is big-endian, so if you wish to take the binary output and put it in an integer on a little-endian architecture (such as an Intel x86 machine), you must byte-swap each word.

If you wish to print BIGNUM objects, you can print to a FILE pointer using BN_print_fp( ). It will only print in hexadecimal format, but it does get negative numbers right:

int BN_print_fp(FILE *f, BIGNUM *bn);

Note that you have to supply your own newline if required.

You can also convert a BIGNUM object into a hexadecimal or a base-10 string using one of the following two functions:

char *BN_bn2hex(BIGNUM *bn);
char *BN_bn2dec(BIGNUM *bn);

You can then do what you like with the string, but note that when it comes time to deallocate the string, you must call OPENSSL_free( ).

Common tests on BIGNUM objects

The function BN_cmp( ) compares two BIGNUM objects, returning 0 if they're equal, 1 if the first one is larger, or -1 if the second one is larger:

int BN_cmp(BIGNUM *a, BIGNUM *b);

The function BN_ucmp( ) is the same as BN_cmp( ), except that it compares the absolute values of the two numbers:

int BN_ucmp(BIGNUM *a, BIGNUM *b);

The following functions are actually macros that test the value of a single BIGNUM object, and return 1 or 0 depending on whether the respective condition is true or false:

BN_is_zero(BIGNUM *bn);
BN_is_one(BIGNUM *bn);
BN_is_odd(BIGNUM *bn);

In addition, you might wish to test a number to see if it is prime. The API for that one is a bit complex:

int BN_is_prime(BIGNUM *bn, int numchecks, void (*callback)(int, int, void *), 
                BN_CTX *ctx, void *cb_arg);
int BN_is_prime_fasttest(BIGNUM *bn, int numchecks, 
                         void (*callback)(int, int, void *), BN_CTX *ctx,
                         void *cb_arg);

These functions do not guarantee that the number is prime. OpenSSL uses the Rabin-Miller primality test, which is an iterative, probabilistic algorithm, where the probability that the algorithm is right increases dramatically with every iteration. The checks argument specifies how many iterations to use. We strongly recommend using the built-in constant BN_prime_checks, which makes probability of the result being wrong negligible. When using that value, the odds of the result being wrong are 1 in 2⁸⁰.

This function requires you to pass in a pointer to an initialized BN_CTX object, which it uses as scratch space.

Prime number testing isn't that cheap. BN_is_prime_fasttest( ) explicitly tries factoring by a bunch of small primes, which speeds things up when the value you're checking might not be prime (which is the case when you're generating a random prime).

Because testing the primality of a number can be quite expensive, OpenSSL provides a way to monitor status by using the callback and cb_arg arguments. In addition, because the primality-testing algorithm consists of performing a fixed number of iterations, this callback can be useful for implementing a status meter of some sort.

If you define the callback, it is called after each iteration. The first argument is always 1, the second is always the iteration number (starting with 0), and the third is the value of cb_arg (this can be used to identify the calling thread if multiple threads are sharing the same callback).

Math operations on BIGNUM objects

Yes, we saved the best for last. Table 7-2 lists the math operations supported by OpenSSL's BIGNUM library.

Table 7-2. Math operations supported by OpenSSL's BIGNUM library

Function	Description	Limitations	Comments
int BN_add(BIGNUM r, BIGNUM a, BIGNUM *b);	r = a+b
int BN_sub(BIGNUM r, BIGNUM a, BIGNUM *b);	r = a-b	r≠a and r≠b	Values may be the same, but the objects may not be.
int BN_mul(BIGNUM r, BIGNUM a, BIGNUM b, BN_CTX ctx);	r = a×b		Use BN_lshift or BN_lshift1 instead to multiply by a known power of 2 (it's faster).
int BN_lshift1(BIGNUM r, BIGNUM a);	r = a×2		Fastest way to multiply by 2.
int BN_lshift(BIGNUM r, BIGNUM a, int n);	r = a×2ⁿ		Fastest way to multiply by a power of 2 where n>1.
int BN_rshift1(BIGNUM r, BIGNUM a);	r = a÷2		Fastest way to divide by 2.
int BN_rshift(BIGNUM r, BIGNUM a, int n);	r=a÷2ⁿ		Fastest way to divide by a power of 2 where n>1.
int BN_sqr(BIGNUM r, BIGNUM a, BN_CTX *ctx);	r = a×a		Faster than BN_mul.
int BN_exp(BIGNUM r, BIGNUM a, BIGNUM p, BN_ CTX ctx);	r = a^p	r≠a, r≠p	Values may be the same, but the objects may not be.
int BN_div(BIGNUM d, BIGNUM r, BIGNUM a, BIGNUM b, BN_ CTX *ctx);	d = a÷b r = a mod b	d≠a, d≠b, r≠a, r≠b	Values may be the same, but the objects may not be; either d or r may be NULL.
int BN_mod(BIGNUM r, BIGNUM a, BIGNUM b, BN_CTX ctx);	r = a mod b	r≠a, r≠b	Values may be the same, but the objects may not be.
int BN_nnmod(BIGNUM r, BIGNUM a, BIGNUM b, BN_CTX ctx);	r = \|a mod b\|	r≠a, r≠b	Values may be the same, but the objects may not be.
int BN_mod_add(BIGNUM r, BIGNUM a, BIGNUM b, BIGNUM m, BN_CTX *ctx);	r = \|a+b mod m\|	r≠a, r≠b, r≠m	Values may be the same, but the objects may not be.
int BN_mod_sub(BIGNUM r, BIGNUM a, BIGNUM b, BIGNUM m, BN_CTX *ctx);	r = \|a-b mod m\|	r≠a, r≠b, r≠m	Values may be the same, but the objects may not be.
int BN_mod_mul(BIGNUM r, BIGNUM a, BIGNUM b, BIGNUM m, BN_CTX *ctx);	r = \|a×b mod m\|	r≠a, r≠b, r≠m	Values may be the same, but the objects may not be.
int BN_mod_sqr(BIGNUM r, BIGNUM a, BIGNUM b, BIGNUM m, BN_CTX *ctx);	r = \|a×a mod m\|	r≠a, r≠m	Values may be the same, but the objects may not be. Faster than `BN_mod_mul`.
int BN_mod_exp(BIGNUM r, BIGNUM a, BIGNUM p, BIGNUM m, BN_CTX *ctx);	r = \|a^p mod m\|	r≠a, r≠p, r≠m	Values may be the same, but the objects may not be.
BIGNUM BN_mod_ inverse(BIGNUM r, BIGNUM a, BIGNUM m, BN_CTX *ctx);			Returns NULL on error, such as when no modular inverse exists.
int BN_gcd(BIGNUM r, BIGNUM a, BIGNUM b, BN_CTX ctx);	r = GCD(a,b)		Greatest common divisor.
int BN_add_word(BIGNUM *a, BN_ULONG w);	a = a+w
int BN_sub_word(BIGNUM *a, BN_ULONG w);	a = a-w
int BN_mul_word(BIGNUM a, BN_ULONG a);	a = a×w
BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w);	a = a÷w		Returns the remainder.
BN_ULONG BN_mod_word(BIGNUM *a, BN_ULONG w);	return a mod w

All of the above functions that return an int return 1 on success or 0 on failure. BN_div_word( ) and BN_mod_word( ) return their result. Note that the type BN_ULONG is simply a typedef for unsigned long.