| [ Team LiB ] |
|
7.4 Manipulating Big Numbers7.4.1 ProblemYou 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. 7.4.2 SolutionUse 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. 7.4.3 DiscussionMost 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. 7.4.3.1 Initialization and cleanupThe 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); 7.4.3.2 Assigning to BIGNUM objectsNaturally, 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. There's a similar function for assigning the value 1: 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:
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) 7.4.3.3 Getting BIGNUM objects with random valuesBefore 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:
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:
7.4.3.4 Outputting BIGNUM objectsIf 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);
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;
}
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( ). 7.4.3.5 Common tests on BIGNUM objectsThe 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 280. 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). 7.4.3.6 Math operations on BIGNUM objectsYes, we saved the best for last. Table 7-2 lists the math operations supported by OpenSSL's BIGNUM library.
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. 7.4.4 See Also |
| [ Team LiB ] |
|
a and r