Cryptography Reference
In-Depth Information
Exercise 11.23
Write a Maple program that searches, up to a specified bound, for
the embedding degree of an elliptic curve over
(
F
p
)
|
and use it to show that the embedding degree of the curve P-256 in Example 11.24
with respect to its order is greater than one million.
F
p
with respect to a factor of
|
E
11.3.3.2 Anomalous Elliptic Curves
The elliptic curves of small embedding degree are not the only ones that are vulner-
able to a reduction attack. After the MOV reduction was known, it was suggested
that curves of trace one, namely those curves—called
anomalous curves
—such that
|
q
, could be adequate for cryptographic use. In the case of curves defined
over a prime field
E
(
F
q
)
|=
F
p
, the number of points is
p
and hence prime and, moreover,
p
does not divide
p
k
1 for any value of
k
, so that the group of rational points of the
curve cannot be embedded in the multiplicative group of
−
F
p
k
. Thus these curves are
immune to the MOV and FR reductions. However, there exist even more efficient
reductions for this class of curves, which provide a polynomial-time algorithm to
solve the ECDLP in this case.
These reductions were independently found by Semaev, Satoh-Araki, and Smart,
and they show that there is an efficiently computable isomorphism
ψ
:
(
F
p
)
→ Z
p
E
where
Z
p
is, as usual, the additive group of integers modulo
p
. This reduces the
ECDLP on an anomalous curve over a prime field to the DLP in
Z
p
which, as we
have seen, is easy because it essentially reduces to the application of the Euclidean
algorithm. As a consequence of this fact, anomalous elliptic curves should not be
used for cryptographic purposes. This poses no problem because very few elliptic
curves have this property and, on the other hand, it is easy to determine whether an
elliptic curve over
and checking whether
it is equal to
p
. We refer to [181, 197] for details on anomalous curves and their
ECDLP reductions.
F
p
is anomalous by computing
|
E
(
F
p
)
|
11.3.4 Final Remarks on the ECDLP
The preceding discussion suggests that in order to ensure that the ECDLP is hard, one
should select an elliptic curve of prime order or whose order has a large prime factor
and work in the corresponding (sub)group. Moreover, additional precautions should
be taken such as, in particular, checking that the curve is not anomalous and that the
embedding degree is sufficiently large. Besides these considerations, experience tells
us that it is dangerous to use curves which have a rich structure in order to ease point
counting—such as was the case with supersingular curves—or tomake the arithmetic
computations faster. Even if no special purpose attacks against the DLP are currently
known, the existence of some additional structure moves us further away from the
generic group model where we know that the ECDLP is hard and opens a door for
