Cryptography Reference
In-Depth Information
situation is not so different from other cryptographic schemes as it might appear at
first sight. For example, we do not have any formal guarantee about the hardness of
the integer factorization problem either, which is a necessary condition for the secu-
rity of RSA. Although the IFP was already mentioned by Gauss, it was not really
until the introduction of RSA in the 1970s that the problem became widely studied
with the help of modern computers. Elliptic curve cryptography is a few years more
recent but this difference will become less and less significant with time.
11.3.3 Reduction Attacks Against the ECDLP
We have mentioned that generic algorithms, such as the rho method, are the fastest
to solve the ECDLP on subgroups of prime order of elliptic curve groups, but this is
true only if the curve is carefully chosen and meets several requirements which we
are going to briefly discuss. In the early years of elliptic curve cryptography, when
Schoof's algorithm and its variants were not yet fully developed, it was common to
choose, for cryptographic use or at least for demonstration purposes, special types of
elliptic curves whose structure allowed a quick computation of the group order. This
was the case with some curves which were known to be supersingular and hence to
have exactly
p
+
1 points in case they are defined over a prime field
F
p
. For example,
we have the following family of supersingular curves:
∈ F
p
. Then the
Proposition 11.3
Let p be a prime such that p
≡
3
(
mod 4
)
and a
F
p
given by the equation y
2
x
3
elliptic curve E over
=
+
ax is supersingular.
Proof
Since
p
≡
3
(
mod 4
)
we have that
−
1 is not a square in
F
p
by Euler's
∈ F
p
, either
x
or
criterion 2.12. This implies that, for each
x
−
x
, but not both, is a
x
3
square. If we set
f
(
x
)
=
+
ax
we see that, for each
x
∈ F
p
,
f
(
−
x
)
=−
f
(
x
)
∈ F
p
such that
f
(
)
=
(
)
(
−
)
and hence for each
x
x
0 we have that either
f
x
or
f
x
F
p
. Thus for each such
x
we have that exactly one of
x
,
−
is a square in
x
is the
x
-coordinate of two points in
E
(
F
p
)
, the corresponding
y
-coordinates being the two
∈ F
p
square roots of whichever of
f
(
x
)
or
−
f
(
x
)
is a square. If
x
is such that
f
(
x
)
=
0, then we also have the points
(
x
,
0
)
and
(
−
x
,
0
)
, so we see that the
p
−
1
F
p
are the
x
-coordinates of exactly
p
elements of
−
1 points on the curve. In addition
we have the point
(
0
,
0
)
and the point at infinity, so
|
E
(
F
p
)
|=
p
+
1 and the curve
is supersingular.
Example 11.21
We show how to find a subgroup of (large) prime order of
E
(
F
p
)
,
where
E
is the supersingular elliptic curve with equation
y
2
x
3
=
+
x
for a suitable
prime
p
such that
p
≡
3
(
mod 4
)
. If we choose
p
of the form
p
=
4
n
−
1, with
n
prime, then the condition
p
≡
3
(
mod 4
)
is satisfied and, moreover,
|
E
(
F
p
)
|=
2
2
n
, so that the order of the group has a prime factor that is just 2 bits shorter
than the order itself. Since
x
3
p
+
1
=
x
2
x
and
x
2
+
x
=
(
+
1
)
+
1 is an irreducible polynomial
