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

Given the importance of modulus arithmetic to public-key cryptography, it's
been the subject of quite a bit of research. Every computational cycle that can
be squeezed out of a modulus operation is going to go a long way in speeding
up public-key cryptography operations. There are a couple of widely imple-
mented ways to speed up cryptography operations: the Barrett reduction and the
Montgomery reduction. They work somewhat similarly; they trade a relatively
time-consuming up-front computation for faster modulus operations. If you're
going to be computing a lot of moduli against a single value — which public-key
cryptography does — you can save a signifi cant amount of computing time by
calculating and storing the common result.
I don't cover these reductions in detail here. The divide operation shown
earlier computes moduli fast enough for demonstration purposes, although
you can actually observe a noticeable pause whenever a private-key operation
occurs. If you're interested, the Barrett reduction is described in detail in the
journal “Advances in Cryptology '86” ( http://www.springerlink.com/content/
c4f3rqbt5dxxyad4/ ), and the Montgomery reduction in “Math Computation
vol. 44” ( http://www.jstor.org/pss/2007970 ).
Encryption and Decryption with RSA
You now have enough supporting infrastructure to implement RSA encryption
and decryption. How the exponents d and e or the corresponding modulus n
are computed has not yet been discussed, but after you've correctly determined
them, you just need to pass them into the encrypt or decrypt routine. How
you specify the message m is important; for now, just take the internal binary
representation of the entire message to be encrypted as m . After you have done
this, you can implement encryption as shown in Listing 3-17.
Listing 3-17: “rsa.c” rsa_compute
/**
* Compute c = m^e mod n.
*/
void rsa_compute( huge *m, huge *e, huge *n, huge *c )
{
huge counter;
huge one;
copy_huge( c, m );
set_huge( &counter, 1 );
set_huge( &one, 1 );
while ( compare( &counter, e ) < 0 )
{
multiply( c, m );
add( &counter, &one );
}