Cryptography Reference
In-Depth Information
Now follows division by
B
l
, and we shift
t_l
by
logB_r
digits to the right, or ig-
nore the
logB_r
least-significant digits of
t_l
. Then if applicable the modulus
n_l
is subtracted from
t_l
before
t_l
is returned as result into
p_l
.
tptr_l = t_l + (logB_r);
SETDIGIT_L (tptr_l, DIGITS_L (t_l) - (logB_r));
if (GE_L (tptr_l, n_l))
{
sub_l (tptr_l, n_l, p_l);
}
else
{
cpy_l (p_l, tptr_l);
}
}
The
Montgomery squaring
sqrmon_l()
differs from this function only
marginally: There is no parameter
b_l
in the function call, and instead of
multiplication with
mult(a_l, b_l, t_l)
we employ the squaring function
sqr(a_l, t_l)
, which likewise ignores a possible overflow. However, in modular
squaring in the Montgomery method one must note that after the calculation of
p
← a
× a
the reverse transformation
p ← p
×
1=
p
r
−
1
=
a
2
mod
n
must
be calculated explicitly (cf. page 108).
Function:
Montgomery square
void sqrmon_l (CLINT a_l, CLINT n_l, USHORT nprime,
USHORT logB_r, CLINT p_l);
Syntax:
a_l
(factor
a
),
n_l
(modulus
n > a
)
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 square
a
2
r
−
1
mod
n
)
Output:
In their article Dussé and Kaliski also present the following variant of the
extended Euclidean algorithm, to be dealt with in detail in Section 10.2, for
calculating
n
0
=
n
mod
B
, with which the expenditure for the precalculations
can be reduced. The algorithm calculates
−n
−
1
mod 2
s
for an
s >
0
and for this
requires long-number arithmetic.
