Cryptography Reference
In-Depth Information
After various checks the position of the leading 1 of the exponent
e
is determined.
Here the variable
k
is used to mask the individual binary digits of
e
.Then
k
is
shifted one more place to the right, corresponding to setting
i ← n −
2
in step 1
of the algorithm.
while ((e & k) == 0)
{
k >>= 1;
}
k >>= 1;
For the remaining digits of
e
we run through steps 2 and 3. The mask
k
serves as
loop counter, which we shift to the right one digit each time. We then multiply by
the base reduced modulo
m_l
.
while (k != 0)
{
msqr_l (tmp_l, tmp_l, m_l);
if (e & k)
{
mmul_l (tmp_l, tmpbas_l, tmp_l, m_l);
}
k >>= 1;
}
cpy_l (p_l, tmp_l);
return err;
}
The binary algorithm for exponentiation offers particular advantages
when it is used with small bases. If the base is of type
USHORT
, then all of the
multiplications
p ← pa
mod
m
in step 3 of the binary algorithm are of the type
CLINT * USHORT
modulo
CLINT
, which makes possible a substantial increase in
speed in comparison to other algorithms that in this case would also require the
multiplication of two
CLINT
types. The squarings, to be sure, use
CLINT
objects, but
here we are able to use the advantageous squaring function.
Thus in the following we shall implement the exponentiation function
wmexp_l()
, the dual to
umexp_l()
, which accepts a base of type
USHORT
.The
masking out of bits of the exponent is a good preparatory exercise in view of the
following “large” functions for exponentiation. The way of proceeding consists
essentially in testing one after the other each digit
e
i
of the exponent against a
variable
b
initialized to
1
in the highest-valued bit, and then shifting to the right
and repeating the test until
b
is equal to
0
.
