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

bit_position = 8 - ( bit_size % 8 ) - 1;
do
{
if ( compare( divisor, dividend ) <= 0 )
{
subtract( dividend, divisor );
if ( quotient )
{
quotient->rep[ ( int ) ( bit_position / 8 ) ] |=
( 0x80 >> ( bit_position % 8 ) );
}
}
if ( bit_size )
{
right_shift( divisor );
}
bit_position++;
}
while ( bit_size-- );
}
One note about the choice to use char s-that is, bytes — instead of int s for the
huge arrays: You could reduce the number of add and subtract operations by a
factor of four if you represent huge s as integer arrays rather than char arrays.
This is actually how OpenSSL, GMP, and Java implement their own arbitrary-
precision math libraries. However, this introduces all sorts of problems later
on when you try to convert from big endian to little endian. You also need to
keep close track of the exact non-padded size of the huge . A three-byte numeral
uses up one int ; however, you'd need to remember that the leading byte of that
int is just padding. RSA implementations in particular are very fi nicky about
result length; if they expect a 128-byte response and you give them 129 bytes,
they error out without even telling you what you did wrong.
Using Modulus Operations to Effi ciently Compute
Discrete Logarithms in a Finite Field
The modulus operation — that is, the remainder left over after a division opera-
tion — is important to modern public-key cryptography and is likely going to
remain important for the foreseeable future. In general, and especially with
respect to the algorithms currently used in SSL/TLS, public-key operations
require that all mathematical operations — addition, subtraction, multiplica-
tion, division — be performed in such a fi nite fi eld. In simple terms, this just
means that each operation is followed by a modulus operation to truncate it
into a fi nite space.