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

68849422, which took up 58,236 bytes to represent. At this point, my computer
fi nally gave up and stopped allocating memory to my process.
First, you need to get the number of multiplications under control. If you
remember when I fi rst discussed huge number multiplication, the naïve imple-
mentation that would have involved adding a number m to itself n times to
compute m n was rejected. Instead, you developed a technique of doubling and
adding. Can you do something similar with exponentiation? In fact, you can.
Instead of doubling and adding, square and multiply . By doing so, you reduce
65,537 operations down to log 2 65,537 17 operations.

Fundamentally, this works the same as double and add; cycle through the
bits in the exponent, starting with the least-signifi cant bit. If the bit position is
1, perform a multiplication. At each stage, square the running exponent, and
that's what you multiply by at the 1 bits. Incidentally, if you look at the binary
representation of 65,537 10000000000000001, you can see why it's so appeal-

ing for public-key operations; it's big enough to be useful, but with just two 1
bits, it's also quick to operate on. You square m 17 times, but only multiply the
fi rst and 17th results.

NOTE Why 65,537? Actually, it's the smallest prime number (which e must
be) that can feasibly be used as a secure RSA public-key exponent. There are
only four other prime numbers smaller than 65,537 that can be represented
in just two 1 bits: 3, 5, 17, and 257, all of which are far too small for the RSA
algorithm. 65,537 is also the largest such number that can be represented in
32 bits. You could, if you were so inclined, take advantage of this and speed
up computations by using native arithmetic operations.

If it's not clear that this should work for exponentiation as well as for multi-
plication, consider x 10 . This, expanded, is
xxxxxxxxxx
(xxxxx)(xxxxx)
(xxxxx) 2
[(xx)(xx)x] 2
[(x x) 2 x] 2
[((x 2 ) 2 )x] 2

Notice how you can successively split the x 's in half, reducing them to squaring
operations each time. It should be clear that you can do this with any number;
you may have a spare x left over, if the exponent is an odd number, but that's OK.
If you look at the binary representation of the decimal number 10 (1010 in
binary) and you work backward through its binary digits, squaring at each
step, you get: