Cryptography Reference
In-Depth Information
Definition 11.8
[9] define the prime field robust code
(
n
,
k
)
with
r
=
n
−
k
redundant
x
2
bits as
C
={
(
x
,
w
)
|
x
∈
GF
(
p
),
w
=
(
mod
p
)
∈
GF
(
p
)
}
where
r
=
k
.
In the nonredundant case, a point
P
on an elliptic curve
E
is represented as
P
(assuming projective coordinates). However, with the new robust code
definition we have, each point will be represented as
P
=
(
X
,
Y
,
Z
)
=
(
X
,
X
w
,
Y
,
Y
w
,
Z
,
Z
w
)
,
where the subscript
w
is used to show the checksum portions.
The following theorem establishes the security level provided by the nonlinear
code described in Definition 11.8 for any elliptic curve
E
. The detailed proof of this
theorem can be found in [9].
Theorem 11.5
[9] For the nonlinear code C of Definition 11.8, th
e e
rror masking
probability is upper-bounded by max
2
√
p
2
k
)
−
1
.
(
,
−
+
)
·
(
+
−
4
p
1
p
1
Example 11.5
Consider the NIST recommended prime field curve P-192. For this
2
64
. In this case, according to
Ha
sse
's theorem, the number of valid points on this curve will be at least
2
k
curve,
(
−
p
+
1
)
=
18446744073709551618
≈
(
p
+
1
−
2
√
p
2
192
. As a result, the minimum error detection capability proposed by our
scheme in this case will be 1
)
≈
2
64
2
192
2
−
128
.
−
/
=
11.8.3 Proposed Point Addition/Doubling Construction
In this section, we provide the secure implementation of the unified point addi-
tion/doubling operation for Edwards curves. This implementation utilizes the error
detection technique described in Sect.
11.8.2
. The main idea of the nonlinear error
detection is to create two computation paths that are nonlinear to each other. As
the first step to achieving this, the coordinates of the input points in an operation
(point addition or doubling) are encoded using the nonlinear code described in Def-
inition
11.8
. One of the nonlinear paths is the original nonredundant data path. The
second path, which is called the “predictor” block, runs in parallel to the nonre-
dundant path, and essentially predicts the checksum of the results of the original
computation. At this point, it is important to note that we do not simply replicate the
original hardware to implement the predictor. For each data path, the total operation
count is expressed in terms of multiplications, divisions and additions and subtrac-
tions, where
M
stands for multiplication,
D
stands for division, and
A
stands for
addition or subtraction.
For Edwards curves that are using projective coordinates, the unified point
addition operation computes the point
P
3
=
(
X
3
,
Y
3
,
Z
3
)
using the input points
. The explicit formula that implements
the point addition is shown in (
11.11
). In the following, we show how the predictor
block works. It mainly computes the expected
X
3
w
,
Y
3
w
,
Z
3
w
using the inputs and
their checksums. More specifically, the expected checksums should be
P
1
=
(
X
1
,
Y
1
,
Z
1
)
and
P
2
=
(
X
2
,
Y
2
,
Z
2
)
