Cryptography Reference
In-Depth Information
We see that
p
and
n
are primes and that
n
is 256 bits long. The supersingular
elliptic curve we want is the following:
> E258 := EllipticCurve(1, 0, p):
Let us now generate a pseudo-random point on this curve:
> RandomTools:-MersenneTwister:-SetState();
R258 := PseudoRandomEllipticPoint(E258);
[69000281114944882070326462838229975840143886278619026101699998021265922379419,
68315539690844455458172461002363545292895348061065537489772144848548131935309]
We now compute the order of this point or, rather, we compute the quotient of its
order divided by
n
; from the previous discussion we know that, with overwhelming
probability, this quotient will be either 1, 2 or 4:
> EllipticPointOrder(R258, E258, p+1)/n;
4
The result is 4, which means that the order is exactly 4
n
=
p
+
1 and hence the
point
R
258 is a generator of
E
(
F
p
)
. To obtain a point of order
n
we simply multiply
R
258 by 4:
> P258 := EllipticMult(4, R258, E258);
[173111335492990338254801713908264336074248773279792702929290254354011194404717,
168998047512458939398710531199066686924425997870916399851718955296173447826793]
is
n
, a 256-bit prime. Pohlig-
Hellman is of no help since
n
is prime and, on the other hand, the size of
n
makes
it infeasible to solve the ECDLP in this group by means of a collision attack such
as Pollard's rho. We could be tempted to conclude that the ECDLP in this group of
large prime order is hard but, as we explain below,
this is not the case
.
Nowwe know that the order of the subgroup
P
258
Exercise 11.22
Consider the supersingular curve of equation
y
2
x
3
=
−
x
over
F
p
,
where
p
1 is the prime in Example 11.22. Show that its group of rational
points is isomorphic to
=
4
n
−
Z
2
× Z
2
n
) and find a point of
order
n
on the curve. Show that the same is true for the curve over
Z
2
× Z
2
× Z
n
(and also to
F
p
of equation
y
2
x
3
=
+
2
x
and find a point of order
n
on this curve.
11.3.3.1 The MOV and FR Reductions
As we have mentioned, the fastest known algorithms to solve the ECDLP that work
for all elliptic curves are the exponential collision algorithms such as the rho method.
However, there are special classes of curves for which the ECDLP is easier to solve
and one of them includes the supersingular curves such as the one considered in
Example 11.22. The idea is to exploit some additional structure of the elliptic curve
that allows a reduction of the problem to an easier DLP in a different group, such as
the multiplicative group of a finite field where index calculus methods are applicable.
Thus if
P
∈
E
(
F
q
)
is a point of prime order
n
on an elliptic curve
E
defined over
