An Introduction to Elliptic Curve Cryptography - Introduction to Cryptography with Maple - page 636

| ( F q ) |

points, this may be enough to uniquely determine E . We refer to the discussion

in [197, Chap. 4] for more information on this subject.
The double-and-add algorithmmentioned above is also a crucial tool in the imple-
mentation of elliptic curve-based cryptographic algorithms such as Elgamal, just as
is the case with its multiplicative counterpart when working in the multiplicative
groups of finite fields. We are going to implement it in Maple and we also want to
be able to multiply negative integers by points. For this we have to use the opposite
point which is given by the following Maple function:

> EllipticOppositePoint := proc(P::{list(integer), identical(0)}, E::list(integer))
local p;
p := E[3];
if not IsEllipticPoint(P, E) then
error "the point is not on the curve"
elif P = 0 then
0
else [P[1], -P[2] mod p]
end if;
end proc:

Example 11.12 We use the curve P256 defined in Example 11.10. We generate a
pseudo-random point on the curve and add it to its opposite:

> RandomTools:-MersenneTwister:-SetState():
R := PseudoRandomEllipticPoint(P256):
EllipticAdd(R, EllipticOppositePoint(R, P256), P256);
0

11.2.4.2 Elliptic Curve Scalar Multiplication and the Order of Points

The next function implements the multiplication of a point by an integer—often
called scalar multiplication —using the “double-and-add” algorithm. The required
inputs are an integer k , a point P and an elliptic curve E , and the output is the result
of adding P to itself k times in case k is positive and the result of adding − P to itself

− k times when k is negative.

> EllipticMult := proc(k::integer, P::{list(integer), identical(0)},
E::(list(integer)))
local t, R, S, bits, l, i;
if not IsEllipticPoint(P, E) then
error "the point is not on the curve"
end if;
ifk=0orP=0then
return 0
end if;
ifk>0then
t:=k;
R:=P;
else
t:=-k;
R := EllipticOppositePoint(P, E)
end if;
S:=0;
bits := convert(t, base, 2);
l := nops(bits);