Cryptography Reference
In-Depth Information
(a)
(b)
Reg.
XOR
m
m
m
Module
m
Reg.
Reg.
Reg.
AND
m
AND
XOR
1
m
m
m
m
m
Module
FF
Preload
AND
1
m
FF
FF
FF
Module
Parity
AND
XOR
XOR
1
1
1
1
1
Module
Parity
1
1
1
Preload
1
1
Fig. 10.1 a
The LSB-first bit-serial PB multiplier with fault detection,
b
The MSB-first bit-serial
PB multiplier with fault detection
Traditionally, the bit-parallel PB multiplication can be based on the following
formulation:
m
−
1
Ax
i
C
=
A
·
B
mod
F
(
x
)
=
b
i
·
(
)
mod
F
(
x
)
.
(10.6)
i
=
0
Assuming
A
(
i
)
=
A
(
i
−
1
)
mod
F
1, and
A
(
0
)
=
·
(
)
≤
≤
−
x
x
for 1
i
m
A
,(
10.6
)
can be written as
m
−
1
A
(
i
)
.
C
=
b
i
·
(10.7)
i
=
0
The structure of the traditional bit-parallel PB multiplier is shown in Fig.
10.2
,
based on (
10.7
). The main components of this multiplier are the same as the ones
discussed for bit-serial PB multipliers, and consequently the fault detection circuits
for this multiplier can be designed similarly.
A single-bit parity-based approach has been used in [177] for fault detection in
the bit-serial Montgomery multiplier of [235]. Properties 10.1 and 10.2 mentioned
for the single-bit parity code in PB are also applicable in this approach. Assuming
A
,
B
, and
C
2
m
∈
GF
(
)
, the bit-serial Montgomery multiplication algorithm proposed
x
−
m
in [235] computes
C
and is shown in Algorithm 10.1.
The following lemma addresses parity prediction in the bit-serial Montgomery
multiplication algorithm.
=
A
·
B
·
mod
F
(
x
)