Cryptography Reference
In-Depth Information
hold the same values as in that example namely, the curve and its order, respectively.
Consider the point:
> P2 := [3463541678371912851659120316656876403420014785151586839208,
568842212284238416323372900024177583272538035222864414728]:
IsEllipticPoint
can be used to check that
P2
is indeed a point on the curve.
We compute its order as follows:
> oP2 := EllipticPointOrder(P2, ec192, o192);
3138550867693340381917894711564020156878505115103324566632
If we compare
oP2
to the order of the group we see that the latter is twice the
former. In fact, if one pseudo-randomly chooses points on the curve, most of the
time they will have order equal to one-half the curve order (Exercise: why?). It can
be easily checked that the order of
P
2 is a 191-bit integer and hence it might seem
that computing discrete logarithms in
P
2
should be very hard (see Example 11.20
below) but it is really not so because:
> ifactor(oP2);
(2)ˆ3 (3) (97) (104109613) (109152774691) (6624920655989) (23014823341457) (778094341)
The order of
P2
is a product of small primes and this makes computing discrete
logs in
easy because of Pohlig-Hellman. Let us consider, for example, the point
Q2
obtained by multiplying
P2
by a large integer:
P
2
> Q2 := [2279620476803698355975116795317394432717933822248062522259,
3165999503627392754528245842683201607139518735263854029139]
Using the function
EllipticPohligHellmanRho
to compute log
P
2
Q
2we
obtain:
> EllipticPohligHellmanRho(P2, Q2, ec192, oP2);
55287500897344162193983928157297523873113574138608106493
The following checks that this value is indeed the discrete logarithm for which
we searched:
> evalb(EllipticMult(%, P2, ec192) = Q2);
true
Exercise 11.21
Write an elliptic curve version of the Maple function
BSGS
given
in Sect.
6.5
and use it to compute the discrete logarithm of Example 11.18. Write
also a function which combines this algorithm with the Pohlig-Hellman algorithm
and use it to solve the discrete logarithm of Example 11.19.
In view of the Pohlig-Hellman algorithmwe will henceforth assume, without loss
of generality, that the group
where the ECDLP is considered, has prime order. In
practice, this is achieved by selecting an elliptic curve whose order is either prime or
has a large prime factor and then taking
P
to be a generator of the subgroup of this
prime order. The simplest way to obtain an elliptic curve whose group of rational
points has prime order is to choose curves at random and compute their orders until
P
