Cryptography Reference
In-Depth Information
F
p
[
]
−
F
p
)we
in
x
(because of Euler's criterion which tells us that
1 is not a square in
F
p
which means that
see that the cubic polynomial defining
E
has only one zero in
there is only one point of order 2 (namely, the point
(
0
,
0
)
) and hence that the group
Z
4
×Z
n
. Since 4 and
n
are relatively prime, this group is cyclic
and the orders of its points are divisors of 4
n
. Thus these orders are either divisors
of 4 or multiples of the prime
n
by a divisor of 4. The points whose order is a divisor
of 4 form a subgroup isomorphic to
E
(
F
p
)
is isomorphic to
Z
4
and hence there are only four of them (more
specifically, there is a point of order 1, namely
,
and two points of order 4). Thus if
p
is large and we randomly choose an element
of
E
O
, a point of order 2, namely
(
0
,
0
)
, there is an overwhelming probability (equal to
n
−
n
) that the order of the
resulting point is a multiple of
n
. If the order of this point is
cn
(where
c
(
F
p
)
is
the
cofactor
of
n
) then, using Proposition 2.5, we obtain the point of order
n
we are
looking for by multiplying the point of order
cn
by
c
. Note that the same reasoning
applies to the curve of equation
y
2
∈{
1
,
2
,
4
}
x
3
=
+
ax
where
a
is any quadratic residue in
F
p
.
Example 11.22
Let us use Maple to construct a subgroup of large prime order of
an elliptic curve group. Suppose that we want to find a subgroup of order a 256-bit
prime with the idea of making the ECDLP in this group hard. Following the preceding
discussion, we first choose a prime
p
of the form
p
1, where
n
is a 256-bit
prime. To do this we can use the following Maple procedure that, on input a positive
integer
m
, finds the smallest (probable) prime
p
of the form
p
=
4
n
−
=
4
n
−
1, where
n
is
also (probable) prime and
m
<
n
.
> specialprime := proc(m)
local n, p;
n:=m;
p:=1;
while not isprime(p) do
n := nextprime(n);
p := 4*n-1
end do;
p
end proc:
Now, suppose we want
n
to be a 256-bit prime. Then we choose
m
a 256-bit
integer (randomly or otherwise) and apply the preceding procedure to find
p
.For
example, let us take
m
2
255
and proceed as follows:
=
> p := specialprime(2ˆ255);
231584178474632390847141970017375815706539969331281128078915168015826259517507
> isprime(p);
true
> n := (p+1)/4;
57896044618658097711785492504343953926634992332820282019728792003956564879377
> isprime(n);
true
> ilog2(n)+1;
256
