Cryptography Reference
In-Depth Information
foritoldo
if bits[i] = 1 then
S := EllipticAdd(S, R, E)
end if;
R := EllipticAdd(R, R, E)
end do;
S
end proc:
Remark 11.3 The scalar multiplication operation is the one that dominates the exe-
cution time of elliptic curve cryptographic schemes. The previous function performs
multiplication in a straightforward way, without exploiting any special structure of
the curve or doing any precomputation. A survey of efficient algorithms that exploit
some of these aspects or make use of projective coordinates is presented in [97,
Chap. 3].
Example 11.13 We use the previous function to compute all the generators of the
group of the elliptic curve ec327 := EllipticCurve(3,2,7) , which is
cyclic of order 9 as we saw in Example 11.11. If we exclude the point at infin-
ity, the remaining points have order either 3 or 9 (the divisors of 9 different from 1)
and the generators are precisely the points of order 9, i.e., those points P such that
3 P
= O
. They may be computed as follows:
> select(x -> evalb(EllipticMult(3, x, ec327) <> 0), ep327);
[[0, 3], [0, 4], [2, 3], [2, 4], [4, 1], [4, 6]]
There are six generators in this case because
φ(
9
) =
6.
Exercise 11.18 Write a 'left to right' version of the Maple function implementing
the multiplication operation, namely, the elliptic curve analogue of the function
ExpMod in Sect. 2.7 .
Next we give a function to pseudo-randomly choose a generator of a cyclic elliptic
curve group over a prime field. This function is simply a transcription to the elliptic
curve setting of our earlier function findgenerator , which was used in Chap. 2
to find a generator of the multiplicative group
Z p . The inputs are an elliptic curve,
its order and, optionally, the factors of the order in the format provided by Maple's
function ifactors . If the factors are not supplied then they are computed inside the
function. The output is a generator of the group. We remark that elliptic curve groups
of prime order are often selected for cryptographic use. In that case this function is not
needed, because to choose a generator pseudo-randomly it suffices to choose a point
= O
in the curve using the previous function PseudoRandomEllipticPoint .
> EllipticGroupGenerator := proc(E::list(integer), order::posint,
{orderfactors := ifactors(order)[2]})
local n, l, i, found, k, P, G;
n := nops(orderfactors);
RandomTools:-MersenneTwister:-SetState();
l:=[];
foritondo
found := false;
 
Search WWH ::




Custom Search