Cryptography Reference
In-Depth Information
11.8 Secure ECC Based on Nonlinear Codes
Elliptic Curve Cryptosystems (ECCs) have also been a target of active fault attacks.
In [44], Biehl et al. showed that using fault injection, ECC point multiplication can
be forced to be computed over a less secure elliptic curve. As a result, it becomes
relatively easy to solve the discrete log problem on which the ECC is based. They
also proposed implementing bit faults during random moments of a multiplication
operation and showed that it is possible to reveal the secret key
d
in a bit-by-bit
fashion. In [90], the authors relaxed the assumptions of Biehl et al. in terms of the
location and precision of the injected faults. Even with this new attacker model,
their attack essentially recovers the (partial) secret in the ECC discrete log problem.
Similarly, in [54], Blomer et al. proposed the so-called “Sign Change Fault” attacks on
the ECC-based systems. Using this attack, they recover the secret scalar in polynomial
time. In this section, we will discuss how nonlinear robust codes can be used to protect
ECC operations.
11.8.1 Elliptic Curve Cryptography Overview
This section briefly describes the elliptic curve discrete logarithm problem (ECDLP)
and ECC formulations over finite fields of prime characteristics. A point
P
of order
#
n
, selected over an elliptic curve
E
defined over a finite field GF(
p
), can be used to
generate a cyclic subgroup
.
The ECDLP is the underlying number theoretical problem used by ECC, and it
is defined as determining the value
k
P
= {∞
,
P
,
2
P
,
3
P
,...,(
#
n
−
1
)
P
}
of
E
(
GF
(
p
))
∈[
1
,
#
n
−
1
]
, given a point
P
∈
E
(
GF
(
p
))
of order #
n
, and a point
Q
. In a cryptosystem, the private key is
obtained by selecting an integer
k
randomly from the interval
=
kP
∈
P
[
1
,
#
n
−
1
]
. Then the
corresponding public key is the result of scalar point multiplication
Q
=
kP
, which
is computed by a series of point additions and doublings.
ECC can be built upon two curves: (1) Weierstrass and (2) Edwards. In this
chapter, we focus on Edwards curves. However, note that the technique we propose
is a generic one that can be applied to all elliptic curve structures (Weierstrass and
Edwards) and all coordinate systems (projective and affine).
11.8.1.1 Edwards Formulation for Elliptic Curves
An elliptic curve
E
defined over a prime field
GF
(
p
)
(with
p
>
3) can be written
in the Edwards normal form as
x
2
y
2
c
2
dx
2
y
2
E
(
GF
(
p
))
:
+
=
(
1
+
),
(11.9)
