Cryptography Reference
In-Depth Information
too tempting. The central question is whether there are considerably faster meth-
ods for exponentiation available. The answer is, luckily, yes. Otherwise we could
forget about RSA and pretty much all other public-key cryptosystems in use today,
since they all rely on exponentiation. One such method is the
square-and-multiply
algorithm
. We first show a few illustrative examples with small numbers before pre-
senting the actual algorithm.
Example 7.2.
Let's look at how many multiplications are required to compute the
simple exponentiation
x
8
. With the straightforward method:
SQ
−→
MU L
−−−→
MU L
−−−→
MU L
−−−→
MU L
−−−→
MU L
−−−→
MU L
−−−→
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
we need seven multiplications and squarings. Alternatively, we can do something
faster:
SQ
−→
SQ
−→
SQ
−→
x
2
x
4
x
8
x
which requires only three squarings that are roughly as complex as a multiplication.
This fast method works fine but is restricted to exponents that are powers of 2,
i.e., values
e
and
d
of the form 2
i
. Now the question is, whether we can extend the
method to arbitrary exponents? Let us look at another example:
Example 7.3.
This time we have the more general exponent 26, i.e., we want to
compute
x
26
. Again, the naıve method would require 25 multiplications. A faster
way is as follows:
SQ
−→
SQ
−→
SQ
−→
SQ
−→
MU L
−−−→
MU L
−−−→
x
2
x
3
x
6
x
12
x
13
x
26
.
x
This approach takes a total of six operations, two multiplications and four squarings.
Looking at the last example, we see that we can achieve the desired result by
performing two basic operations:
1.
squaring
the current result,
2.
multiplying
the current result by the base element
x
.
In the example above we computed the sequence
SQ
,
MU L
,
SQ
,
SQ
,
MU L
,
SQ
.
However, we do not know the sequence in which the squarings and multiplications
have to be performed for other exponents. One solution is the
square-and-multiply
algorithm. It provides a systematic way for finding the sequence in which we have
to perform squarings and multiplications by
x
for computing
x
H
. Roughly speaking,
the algorithm works as follows:
The algorithm is based on scanning the bit of the exponent from the left (the
most significant bit) to the right (the least significant bit). In every iteration, i.e.,
for every exponent bit, the current result is squared. If and only if the currently
