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

Listing 3-12: “huge.c” left_shift
void left_shift( huge *h1 )
{
int i;
int old_carry, carry = 0;
i = h1->size;
do
{
i--;
old_carry = carry;
carry = ( h1->rep[ i ] & 0x80 ) == 0x80;
h1->rep[ i ] = ( h1->rep[ i ] << 1 ) | old_carry;
// Again, if C exposed the overflow bit...
}
while ( i );
if ( carry )
{
expand( h1 );
}
}
Because each char can overfl ow into the next-leftmost char , it's necessary to
manually keep track of the carry bit and expand the result if it overfl ows, just
as you did for addition.
This double-and-add approach to multiplication is important when dealing
with binary arithmetic. In fact, you've seen it once before, in Chapter 2, when
you implemented AES multiplication in terms of the dot and xtime opera-
tions. It comes up later when I redefi ne multiplication yet again in the context
of elliptic curves. However, this is not the most effi cient means of performing
binary multiplication. Karatsuba's algorithm, originally published by Anatolii
Karatsuba in the “Proceedings of the USSR Academy of Sciences” in 1962, is
actually much faster, albeit much more complicated to implement — I won't
cover it here, but you can consult a topic on advanced algorithms if you're
curious. However, this routine runs well enough on modern hardware, so
just leave it as is.
Implementing Large-Number Division
Finally, what about division? Division is, of course, the inverse of multiplica-
tion, so it makes sense that you ought to be able to reverse the multiplication
process and perform a division. Consider the multiplication of 13 by 5, in
binary: