Overview of BN library -- SSLeay 0.9.0b -- January 1999

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
        {
        BN_ULONG *d;    /* Pointer to an array of 'BN_BITS2' bit chunks. */
        int top;        /* Index of last used d +1. */
        /* The next are internal book keeping for bn_expand. */
        int max;        /* Size of the d array. */
        int neg;        /* one if the number is negative */
        } BIGNUM;

The big number is stored in a malloced array of BN_ULONGs. 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 index of the most significant BN_ULONG in use, 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 has the value 0, the d field can be NULL and top is then 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_NUM BIGNUMs. BN_CTX_NUM is the maximum number of temporary BIGNUMs any publicly exported function will use.

#define BN_CTX_NUM      12
typedef struct bignum_ctx
        {
        int tos;                     /* top of stack */
        BIGNUM *bn[BN_CTX_NUM+1];    /* the variables */
        } BN_CTX;

BIGNUMs are sometimes put into Montgomery form for speed for multiplication. A context structure for that and related operations is defined below:

typedef struct bn_mont_ctx_st
        {
        int ri;         /* number of bits in R */
        BIGNUM *RR;     /* used to convert to montgomery form */
        BIGNUM *N;      /* The modulus */
        BIGNUM *Ni;     /* The inverse of N */
        BN_ULONG n0;    /* word form of inverse, normally only one of
                         * Ni or n0 is defined */
        } BN_MONT_CTX;

In addition there is a structure used for blinding computations, defined as follows:

typedef struct bn_blinding_st
        {
        int init;
        BIGNUM *A;
        BIGNUM *Ai;
        BIGNUM *mod; /* just a reference */
        } BN_BLINDING;

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. You can access it by calling BN_value_one().