Cryptography Reference
In-Depth Information
⎧
⎨
k
=
0
s
−
1
a
kr
+
i
m
−
sr
≤
i
<
r
A
i
=
sr
,
k
=
0
s
⎩
a
kr
+
i
0
≤
i
<
m
−
=
r
is the minimum number of the
coordinates of
A
represented by a parity bit. Note that if
m
where
r
is the number of parity bits and
s
sr
, each parity bit
covers
s
coordinates of
A
. Otherwise (which is the common case in ECC), some
parity bits cover
s
bits and the rest cover
s
=
+
1 bits.
Predicting the parity of the final multiplication product
C
is done in two steps.
First, the parity prediction is performed for the first network shown in Fig.
10.2
,
which includes the
x
modules. The following lemma addresses the parity prediction
in the
x
modules.
Lemma 10.4
Assuming A
(
i
−
1
)
and A
(
i
−
1
)
are the input of the x module and its
parity, respectively, the parity of the x module's output A
(
i
)
can be obtained as
follows [83]:
a
(
i
−
1
)
m
)
+
A
(
i
−
1
)
(
1
(
F
j
+
1
j
=
m
−
sr
A
(
i
)
j
−
j
−
1
)
mod
r
=
sr
,
a
(
i
−
1
)
m
F
j
+
A
(
i
−
1
)
0
≤
j
<
r
,
j
=
m
−
−
1
(
j
−
1
)
mod
r
F
j
is the j th parity bit of F
where
(
z
)
.
The formulation above can be used in each
x
module to predict the parity. The
second network of the bit-parallel PB multiplier shown in Fig.
10.2
is based on (
10.7
)
and consists of AND operations with the coordinates of
B
and the final sum using
XOR gates. The parity prediction formulation for this network is
m
−
1
A
(
i
)
j
C
j
=
b
i
,
0
≤
j
<
r
.
i
=
0
The parity based approach used in [343] to design fault detection circuits for the
PB multipliers was extended in [355] using multiple-bit parity codes. The multipliers
considered in [355] include the LSB-first bit-serial PB multiplier (shown in Fig.
10.1
a
using white blocks) and the traditional bit-parallel PB multiplier (shown in Fig.
10.2
).
Assuming
A
=
m
−
1
i
a
i
x
i
2
m
,the
multiple-bit parity of
A
is defined by dividing
A
into
k
parts. Assuming
m
is divisible
by
k
(for simplicity), the
j
th part of
A
is defined as
is a field element of
GF
(
)
and
a
i
∈
GF
(
2
)
=
0
l
−
1
x
jk
a
jk
+
i
x
i
A
j
=
,
i
=
0
