Cryptography Reference
In-Depth Information
where the coefficients
a
1
,
a
2
,
a
3
,
a
4
,
a
6
∈
K
and such that the curve is nonsingular.
The set of points
(
x
,
y
)
∈
K
×
K
that satisfy the curve equation, along with the
point
.
The full Weierstrass equation can be simplified depending on the characteristics
of the underlying field,
K
. For prime fields, and when char
O
at infinity, is denoted by
E
(
K
)
(
K
)
=
2
,
3, (
9.1
) can be
simplified to
y
2
x
3
E
:
=
+
ax
+
b
(9.2)
where
a
,
b
∈
K
. In a binary field, i.e., when char
(
K
)
=
2, and assuming that
a
1
=
0
and that
E
is nonsupersingular, (
9.1
) can be simplified to
y
2
x
3
ax
2
E
:
+
xy
=
+
+
b
(9.3)
where
a
K
.
The points on an elliptic curve, together with the point
,
b
∈
at infinity, form an
abelian group under the operation of point addition, which has an intuitive geometric
interpretation that can be used to derive explicit formulas. When char
O
(
)
=
,
K
2
3 and
=−
=
(
x
3
,
y
3
)
=
+
P
Q
, we can find
R
P
Q
as follows:
⎧
⎨
y
2
−
y
1
x
1
,
if
P
=
Q
x
2
−
λ
=
3
x
1
+
a
⎩
,
if
P
=
Q
2
y
1
2
x
3
=
λ
−
2
x
1
,
y
3
=
λ(
x
1
−
x
3
)
−
y
1
.
(9.4)
Each point operation on an affine elliptic curve requires a field inversion, which
is significantly more expensive in general than a field multiplication. To address
this problem, various projective coordinates were introduced, e.g., [99], and are
often employed to reduce the number of field inversions at the cost of more field
multiplications and storage space. Different projective coordinates have different
costs in terms of field operations. Moreover, it has been shown that adding points
represented in different projective coordinates can be more efficient than adding of
points in the same coordinate system [98].
The security of ECC is based mainly on the hardness of the elliptic curve discrete
logarithm problem (ECDLP), which can be defined as finding the scalar
k
given
P
E
. Since all the known solutions for this problem in general elliptic curves
have an exponential complexity, parameters should be of appropriate size to make the
instance intractable. Moreover, the ECDLP is easier, i.e., there exist sub-exponential
solutions, for some special elliptic curves. As such, these curves should be avoided
in ECDLP-based cryptography.
,
kP
∈