Cryptography Reference
In-Depth Information
t
(
l
)
≡
ab
mod
n
follows (6.20), and lastly we have (6.21) on account of
l
−
1
t
(
l
)
=
t
(0)
+
n
m
i
B
i
<
2
nB
l
i
=0
(note here that
t
(0)
=
ab<n
2
<nB
l
).
The expenditure for the reduction is now determined essentially by
multiplication of numbers of order of magnitude the size of the modulus. This
variant of Montgomery multiplication can be elegantly implemented in code that
forms the core of the multiplication routine
mul_l()
(cf. page 36).
Function:
Montgomery product
void mulmon_l (CLINT a_l, CLINT b_l, CLINT n_l,
USHORT nprime, USHORT logB_r,
CLINT p_l);
Syntax:
a_l, b_l
(factors
a
and
b
)
n_l
(modulus
n>a,b
)
nprime
(
n
mod
B
)
logB_r
(logarithm of
r
to base
B
=2
16
;
it must hold that
B
logB_r
−
1
Input:
n<B
logB_r
)
≤
p_l
(Montgomery product
a × b
=
a · b · r
−
1
mod
n
)
Output:
void
mulmon_l (CLINT a_l, CLINT b_l, CLINT n_l, USHORT nprime,
USHORT logB_r, CLINT p_l)
{
CLINTD t_l;
clint *tptr_l, *nptr_l, *tiptr_l, *lasttnptr, *lastnptr;
ULONG carry;
USHORT mi;
int i;
mult (a_l, b_l, t_l);
lasttnptr = t_l + DIGITS_L (n_l);
lastnptr = MSDPTR_L (n_l);
The earlier use of
mult()
makes possible the multiplication of
a_l
and
b_l
without
the possibility of overflow (see page 72); for the Montgomery squaring we simply
insert
sqr()
. The result has sufficient space in
t_l
.Then
t_l
is given leading zeros
to bring it to double the number of digits of
n_l
if
t_l
is smaller than this.
