Secure Key Exchange over an Insecure Medium with Public Key Cryptography - Implementing SSL/TLS Using Cryptography and PKI - page 93

native computations on numbers with 32 or fewer bits. Even a 64-bit architecture
isn't going to be able to deal with this natively. And even if you could fi nd a
2,048-bit architecture, the interim results are on the order of millions of bits! To
make this possible on any hardware, modern or futuristic, you need an arbitrary
precision math module, and you need to rely on several tricks to both speed up
things and minimize memory footprint.

Performing Arbitrary Precision Binary Math to
Implement Public-Key Cryptography

Developing an arbitrary precision binary math module — one that can effi -
ciently represent and process numbers on the order of 2,048 bits — is not
diffi cult, although it's somewhat tedious at times. It's important that the numeric
representation be constrained only by available memory and, in theory, virtual
memory — that is, disk space (to oversimplify a bit). The number must be able
to grow without bounds and represent, exactly, any size number. In theory,
this is straightforward; any integer can be represented by an array of C char s,
which are eight bits each. The least-signifi cant-bit (LSB) of the next-to-last char
represents 2 8 , with the most-signifi cant-bit (MSB) of the last being 2 7 . As the inte-
ger being represented overfl ows its available space, more space is automatically
allocated for it.

NOTE

For a more detailed understanding of LSB and MSB, see Appendix A.

As such, defi ne a new type, called huge , shown in Listing 3-1.

Listing 3-1: “huge.h” huge structure

typedef struct
{
unsigned int size;
unsigned char *rep;
}
huge;

Each huge is simply an arbitrarily-sized array of char s. As it's manipu-
lated — added to, subtracted from, multiplied or divided by — its size will be
dynamically adjusted to fi t its contents so that the size member always indicates
the current length of rep .

Implementing Large-Number Addition

Addition and subtraction are perhaps more complex than you might expect.
After all, adding and subtracting numbers is fundamentally what computers