Cryptography Reference
In-Depth Information
Another countermeasure to the sign change attack has been proposed in [54], and
extends a countermeasure presented in [372] for RSA. The idea is to employ another
curve
E
t
defined over a smaller field
F
t
for some prime
t
. Moreover, a base point
P
t
is chosen to have a large order within
E
t
. A combined curve
E
pt
and a new base
point
P
pt
can be constructed using the Chinese remainder theorem, and then the
scalar multiplication is performed once on each of
E
pt
and
E
t
. If the results do not
match modulo
t
, they are rejected.
A similar countermeasure has been proposed in [19]. Most notably, in this coun-
termeasure, the integer
t
, the curve
E
t
and the point
P
t
are selected randomly and
t
is not necessarily prime. However, it has been shown in [196] that this setup allows
a nonnegligible proportion of faults to pass through, and that a nonrandom setup like
the one proposed in [54] is significantly more secure.
A countermeasure based on coherency checking is described [124]. This counter-
measure extends the coherency-based countermeasure presented in [162] for RSA
signature algorithms. As illustrated in Algorithm 9.4, this countermeasure is based on
the right-to-left double-and-add-always scalar multiplication algorithm. It includes
within it point validation of resulting points, and since it is a double-and-add-always
algorithm, it is inherently resistant to simple power and timing analysis attacks.
It is worth mentioning, however, that only single-fault attacks are considered in this
algorithm. By tracing the iterations in this algorithm, we notice that in a
n
error-free
ru
n,
Q
1
is expected to have the value
kP
, while
Q
0
will have the value
kP
, where
k
2
n
k
. Since
Q
2
has the value 2
n
P
, it follows that
Q
0
+
Q
2
.As
shown in [124], a sign change fault in any of the intermediate values can be detected
by checking this invariant. This countermeasure incurs significantly less overhead
than the ones based on combined curves.
=
−
1
−
Q
1
+
P
=
Algorithm 9.4:
Right-to-left double-and-add-always scalar multiplication algo-
rithm with point validation and coherency checking
Input
:
P
∈
E
(
K
)
,
k
=
(
k
n
−
1
,
k
n
−
2
,...,
k
0
)
Output
:
kP
1
Q
0
←
O
,
Q
1
←
O
,
Q
2
←
P
2
for
i
←
0
to
n
−
1
do
3
Q
k
i
←
Q
k
i
+
Q
2
Q
2
←
2
Q
2
4
5
end
6
if
Q
0
∈
E
(
K
)
and
Q
1
∈
E
(
K
)
and
Q
2
=
Q
0
+
Q
1
+
P
then
7
return
Q
1
8
else
9
return
O
10
end
