Cryptography Reference
In-Depth Information
have cryptographically weak twists. It is also important to ensure that the output
points lie on the original curve. Another countermeasure, which has been reported
in [122] and extends the approach presented in [162] for RSA, uses the invariant in
the Montgomery algorithm (Algorithm 9.3), i.e.,
Q
[
1
]−
Q
[
0
]=
P
, to validate the
variables before results are returned.
9.3.2 Targeting the System Parameters
It is also possible to target the parameters of the system, e.g., the field representation,
or the parameters of the curve equation. This will generally lead to the computation
being performed on a weaker curve or a weaker curve-field combination.
9.3.2.1 Faulty Field Representation
Faults can be injected into the field parameters, either in storage or in transit. This
attack, introduced in [90], exploits this fact. Let
E
be a curve defined over a prime
field
F
p
of characteristics other than 2 and 3. Assume that a bit error is injected
into
p
to give the almost similar value
p
and that all field operations will then be
performed modulo
p
instead. In particular, the values of
P
,
Q
,
a
and
b
will be
represented modulo
p
as
P
,
Q
,
a
and
b
, respectively.
Since
Q
satisfies the equation of
E
, it follows that
y
2
Q
−
x
3
Q
−
b
≡
a
≡
y
2
x
3
mod
p
).
b
≡
−
−
a
(
y
2
Q
−
x
3
Q
−
Hence,
p
|
and
p
can be revealed
through factoring
D
as the product of factors that has the shortest Hamming distance
from
p
. Using these factors, the value of
k
can be computed by solving a set of small
DLPs and then Chinese remaindering.
Moreover,
p
can be found more efficiently when
p
is a (generalized) Mersenne
prime.
Generalized Mersenne primes
areprimesoftheform
a
−
(
y
2
x
3
D
where
D
=
−
−
a
)
B
2
ω
0
2
ω
i
p
=
+
1
±
i
=
where
B
is typically small [381]. These primes are commonly used to enable highly
efficient field reduction and to significantly reduce storage requirements for
p
.For
example, when
B
≤
4, as is the case for all NIST prime curves [141],
p
can be
written as
3
2
ω
0
1
σ
i
2
ω
i
=
+
+
σ
4
p
(9.5)
i
=
