Cryptography Reference
In-Depth Information
...
m
Module
Module
Module
m
m
m
AND
AND
AND
AND
1
1
1
1
...
XOR
XOR
XOR
Fig. 10.2
Traditional bit-parallel polynomial basis multiplier
2
m
Algorithm 10.1
: Bit-serial Montgomery multiplication over
GF
(
)
[235]
Input
:
A
,
B
,
F
(
x
)
Output
:
C
=
A
·
B
·
x
−
m
mod
F
(
x
)
T
←
0;
1
for
i
=
0
to
m
−
1
do
2
T
←
T
+
b
i
A
;
3
T
←
T
+
t
0
F
(
x
)
;
4
T
/
T
←
x
;
5
end
6
return
T
7
Let T
(
i
)
and T
(
i
−
1
)
be the value of T at the i th and
Lemma 10.3
(
i
−
1
)
th iterations
T
(
i
)
T
(
i
−
1
)
of the Montgomery multiplication algorithm, respectively. Also, let
and
T
(
i
)
can be obtained as [177]
be their corresponding parity bits. Now,
t
(
i
−
1
)
0
T
(
i
)
=
T
(
i
−
1
)
+
b
i
·
A
+
+
b
0
·
a
0
,
A and t
(
i
−
1
)
0
are the parity bit of A and the LSB of T
(
i
−
1
)
, respectively.
where
The fault detection circuit for the bit-serial Montgomery multiplication algorithm
can be constructed from Lemma 10.3 directly.
10.2.2 Multiple-Bit Parity-Based Approaches
Another approach to fault detection in bit-parallel PB multiplication was proposed
in [83]. This approach is based on using multiple interlacing parity bits. Using this
method, the parity bits for the operand
A
can be defined as follows:
