Cryptography Reference
In-Depth Information
Proposition 5.6 shows that we can lift E , P ,and Q to an elliptic curve E
over Z with points P and Q . If we can find k with Q = k P ,then Q = k P .
However, it is usually the case that P and Q are independent, so no k ex-
ists. Silverman's idea was to start with several (up to 9) points of the form
a i P + b i Q and lift them to a curve over Q . This is possible: Choose a lift
to Z for each of the points. Write down an arbitrary cubic curve containing
lifts of the points. The fact that a point lies on the curve gives a linear equa-
tion in the coecients of the cubic equation. Use linear algebra to solve for
these coecients. This curve can then be converted to Weierstrass form (see
Section 2.5.2). Since most curves over Q tend to have at most 2 independent
points, the hope was that there would be relations among the lifted points.
These could then be reduced mod p to obtain relations between P and Q ,thus
solving the discrete log problem. Unfortunately, the curves obtained tend to
have many independent points and no relations. Certain modifications that
should induce the curve to have fewer independent points do not seem to
work. For an analysis of the algorithm and why it probably is not successful,
see [55].
Exercises
5.1 Suppose G is a subgroup of order N of the points on an elliptic curve over
a field. Show that the following algorithm finds k such that kP = Q :
(a) Fix an integer m ≥ N .
(b) Compute and store a list of the x -coordinates of iP for 0 ≤ i ≤ m/ 2.
(c) Compute the points Q − jmP for j =0 , 1 , 2 , ··· ,m− 1untilthe
x -coordinate of one of them matches an element from the stored
list.
(d) Decide whether Q − jmP = iP or = −iP .
(e) If ±iP = Q − jmP ,wehave Q = kP with k ≡±i + jm (mod N ).
This requires a little less computation and half as much storage as the
baby step, giant step algorithm in the text. It is essentially the same as
the method used in Section 4.3.4 to find the order of E ( F q ).
5.2 Let G be the additive group Z n . Explain why the discrete logarithm
problem for G means solving ka ≡ b (mod n )for k and describe how
this can be solved quickly. This shows that the diculty of a discrete
logarithm problem depends on the group.
5.3 Let E be the elliptic curve y 2 = x 3 +3over F 7 .
(a) Show that 4(1 , 2) = (4 , 5) on E .
Search WWH ::




Custom Search