Cryptography Reference
In-Depth Information
proportional to the large prime cofactor
n
). Thus, for a randomly chosen elliptic curve
over
F
q
k
is in fact much harder than the original ECDLP problem.
However, there are some special classes of curves for which the embedding degree
is low and the MOV reduction gives a subexponential-time algorithm. Some of these
curves are given in the following example:
F
q
the DLP over
Example 11.23
Let
E
be a supersingular elliptic curve over
F
p
where
p
>
3is
prime. Then
|
E
(
F
p
)
|=
p
+
1 and, since we are assuming that the prime
n
divides
p
2
|
(
F
p
)
|
|
+
|
−
=
E
, we have that
n
p
1
1, so that the embedding degree is
k
2. Thus
the ECDLP in
P
, where
P
is a point of prime order
n
, can be reduced to a DLP
F
p
2
, for which there are subexponential algorithms. This is the reason why the
ECDLP considered in Example 11.22 above is not hard.
on
Some of the most important classes of elliptic curves with small embedding
degree are:
•
Supersingular curves.
•
|
(
F
q
)
|=
−
Elliptic curves of trace 2, i.e., such that
E
q
1.
6 and hence they should not be used in
cryptographic algorithms that rely on the hardness of the ECDLP unless the underly-
ing finite field is large enough for the DLP in
All these curves have embedding degree
≤
F
q
k
to be hard. This fact discouraged the
cryptographic use of supersingular elliptic curves for a while, at least until construc-
tive applications of these curves were discovered with the arrival of IB cryptography.
To ensure that an elliptic curve defined over
F
q
is resistant to the MOV and FR
reductions it suffices to check that the order
n
of the base point
P
relative to which
the ECDLP is computed does not divide
q
k
−
1 for the small values of
k
for which
F
q
k
is considered feasible. In [97] it is estimated that if
n
2
160
then
the DLP in
>
it suffices to check this condition for all
k
∈[
1
,
20
]
(so that the embedding degree
is
20) and in the more recent recommendation in [173], the embedding degree is
required to be
>
≥
100.
Example 11.24
Let us consider again the NIST elliptic curve P-256 introduced in
Example 11.10. The prime modulus and the order of the curve are the following:
> p256 := 2ˆ256-2ˆ224+2ˆ192+2ˆ96-1:
oP256 := 11579208921035624876269744694940757352999695522413576034242225906106851\
2044369:
The order is prime, and hence any point on the curve distinct from the point at
infinity is a generator and has order
oP256
. Let us check that the embedding degree
of the curve is not
≤
100:
> member(0, Power
∼
(p256, [$1 .. 100]) mod oP256 -
∼
1);
false
Thus this curve is resistant to the MOV and FR reductions and seems, from this
point of view, adequate for cryptographic use.
