Cryptography Reference
In-Depth Information
k := order/orderfactors[i][1];
while not found do
P := PseudoRandomEllipticPoint(E);
found := evalb(EllipticMult(k, P, E) <> 0)
end do;
k := order/(orderfactors[i][1])ˆorderfactors[i][2];
l := [op(l), EllipticMult(k, P, E)]
end do;
G:=0;
foritondo
G := EllipticAdd(G, l[i], E)
end do;
G
end proc:
Example 11.14
We construct an elliptic curve over
p
256 is the 256-
bit prime over which the NIST curve P-256, used in Example 11.10, is defined. This
prime is the following:
F
p
, where
p
=
> p256 := 2ˆ256-2ˆ224+2ˆ192+2ˆ96-1:
The elliptic curve that we will use is:
> ec256 := EllipticCurve(7, 11, p256):
The order of this curve can be computed by means of the implementation of the
SEA algorithm in [143] and it turns out to be:
> o256:=115792089210356248762697446949407573529756567700756856116485097055070429878012:
The order is easy to factor and we obtain:
> ifactor(o256);
(2)ˆ2 (72361432789) (264147774106088250771567413659195695032988900394667)
(2260717937) (669913)
As we have remarked, if the order is squarefree then the group is cyclic but in this
case we have a squared factor 2. By the structure theorem of finite abelian groups this
group has either a factor (isomorphic to)
Z
2
× Z
2
. The first possibility
occurs precisely when there is a unique element of order 2 (the only element of order
2in
Z
4
or a factor
Z
2
× Z
2
) three elements of
order 2. So, in order to see whether the group of the curve
ec256
is cyclic, it suffices
to check how many points of order 2 it has. As we have seen, the points of order 2
correspond to the roots in
Z
4
is 2) and the second occurs when there are (as in
F
p
of the cubic polynomial
x
3
+
ax
+
b
defining the curve
and we can compute these roots with Maple as follows:
> Roots(xˆ3+7*x+11) mod p256;
[[111237276231358922482507679868246738551900716794723608870821124038139942305782, 1]]
We see that there is a single root—the 1 on the right indicates the multiplicity—
and hence a single element of order 2, so that the group is indeed cyclic. Thus we
can use the previous function to compute a generator as follows:
> g256 := EllipticGroupGenerator(ec256, o256);
[69385755060832967159269382451180048774019250174739376235116761742455836744302,
14320494373671200908641310158175006546673336442776538268872712821746618358626]
