Cryptography Reference
In-Depth Information
Exercise 11.19
Write a Maple function that checks whether a given point of an
elliptic curve cyclic group is a generator and use it to check that points obtained
with the
EllipticGroupGenerator
function, as in the previous example, are
indeed generators.
We next give a Maple function that computes the order of a point on an elliptic
curve given the group order. The input parameters are the point, the elliptic curve,
the order of the group and, optionally, the sorted set of divisors of the group order,
which may be passed to the procedure through the keyword parameter
orddivs
.
If no value is passed to this parameter then Maple computes the divisors by default.
The output is the order of the point in the elliptic curve group.
> EllipticPointOrder := proc(P::{list(integer), identical(0)}, E::(list(integer)),
ord::posint, {orddivs := sort(convert(numtheory:-divisors(ord), list))})
local d;
option remember;
if 'not'(IsEllipticPoint(P, E)) then
error "the point is not on the curve"
end if;
for d in orddivs while EllipticMult(d, P, E) <> 0 do
NULL
end do;
d
end proc:
Example 11.15
Using a modified version of the function
EllipticCurve
Points
, one sees that the points of the curve
ec256
in Example 11.14 whose
x
-coordinate is
≤
10 are the elements of the following list:
> ep256l10 :=
[[2, 65580740334265363388806975267261614797714391452302187355066257759605956091865],
[2, 50211348876090885373890471682145958732371751962988126840467373549261141762086],
[10, 77239952575121080653999719600085583238841187993596466080490007326994794653185],
[10, 38552136635235168108697727349321990291244955421693848115043623981872303200766]]
These points appear in pairs, where one point is followed by its opposite, which
has the same
x
-coordinate. Thus the order of the first point above is equal to the
order of the second and, similarly, the order of the third is the same as the order of
the fourth. We may compute the order of the first and third points as follows:
> map(x -> EllipticPointOrder(x, ec256, o256), subsop(2 = NULL, 4 = NULL, ep256l10));
[57896044605178124381348723474703786764878283850378428058242548527535214939006,
115792089210356248762697446949407573529756567700756856116485097055070429878012]
We see that the order of the first point in the list above is just one-half of the group
order, while the order of the third point is equal to the group order, meaning that this
point is a generator of the group.
Example 11.16
To illustrate the simple computations on elliptic curves that can be
carried out with the previous functions, we give an example in which knowledge of
the order of a single point of an elliptic curve allows us to determine the order of
the group of rational points. This technique, combined with the baby-step giant-step
method to compute the order of a point, leads to a subexponential algorithm—the
