Cryptography Reference
In-Depth Information
This works; you've drastically reduced the number of multiplications needed
to compute an exponentiation. However, you still haven't addressed the primary
problem of memory consumption. Remember that you allocated 56 kilobytes of
memory to compute an interim result — just throw it away when you compute
the modulus at the end of the operation. Is this really necessary? As it turns out,
it's not. Because the modulus operator is distributive — that is, ( abc ) % n
[ a
% n * b % n * c % n ] % n , you can actually compute the modulus at each step.
Although this results in more computations, the memory savings are drastic.
Remember that multiplications take as many addition operations as there are
bits in the representation as well, so reducing the size of the numbers being
multiplied actually speeds things up considerably.
Listing 3-19, then, is the fi nal RSA computation (m e ) % n , with appropriate
speed-ups.
Listing 3-19: “huge.c” mod_pow
/**
* Compute c = m^e mod n.
*
* Note that this same routine is used for encryption and
* decryption; the only difference is in the exponent passed in.
* This is the “exponentiate” algorithm, with the addition of a
* modulo computation at each stage.
*/
void mod_pow( huge *h1, huge *exp, huge *n, huge *h2 )
{
unsigned int i = exp->size;
unsigned char mask;
huge tmp1, tmp2;
set_huge( &tmp1, 0 );
set_huge( &tmp2, 0 );
copy_huge( &tmp1, h1 );
set_huge( h2, 1 );
do
{
i--;
for ( mask = 0x01; mask; mask <<= 1 )
{
if ( exp->rep[ i ] & mask )
{
multiply( h2, &tmp1 );
divide( h2, n, NULL );
}
// square tmp1
copy_huge( &tmp2, &tmp1 );
 
Search WWH ::




Custom Search