I am experimenting with the GLV method but cannot manage to get the right results according to the literature.

I managed to find lambda, beta, split $K$ into $k_1$ and $k_2$ etc. for the curve I'm interested in.

According to the literature:

$$kP = k_1P + k_2\phi(P)$$

However, to get the right results, it seems to be needed to test if $k_1$ and $k_2$ are of the same sign, in which case a point addition should be applied. In the case of $k_1$ and $k_2$ being of different sings, one possibly needs to apply a subtraction.

Relevant part of code applying this method as is such:

BigInteger[] ba=splitK(k);
Point QP=new Point(beta.multiply(Q.x).mod(FIELD),Q.y);
Point A=wNAFMultiply(Q, ba[0],(byte)4);
Point B=wNAFMultiply(QP,ba[1],(byte)4);
if (ba[0].signum()==ba[1].signum()) // Where is this explained ????
    return add(A,B);
    return subtract(A,B);

It also follows that algo. 3.77 of the book “Guide to elliptic curve cryptography” probably does not work.

Screenshot of algo. 3.77

Am I missing something obvious?

  • $\begingroup$ This sort of question tends to be viewed as off-topic since it is about a users implementation. $\endgroup$ – Cryptographeur Feb 26 '14 at 10:53
  • 1
    $\begingroup$ My apologies if the code seems like a user implementation, but the question is relevant: are the books missing information/incorrect or am I doing something wrong ? The original paper from GLV also does not mention the need to subtract both terms in the case that k1 and k2 are of different signs. $\endgroup$ – user12230 Feb 26 '14 at 11:02
  • $\begingroup$ I think I may have a hint of an answer. Point multiplication generally assumes a positive integer. However, after splitting k into k1 and k2, one may actually end up with negative k1 and/or k2. Therefore care is needed not to resort to point multiplication with negative 'ks'. I think greater attention to this issue should be devoted in various texts as the understanding of how the GLV method is specified depends on the assumptions one make about the underlying point multiplication. $\endgroup$ – user12230 Feb 26 '14 at 15:40
  • $\begingroup$ There isn't really a notion of sign in the scalar ring, since scalars that differ by a multiple of the point (or group) order $n$ have the same action on the point, so they really live in $\mathbb Z/n\mathbb Z$ rather than in $\mathbb Z$. $\endgroup$ – Squeamish Ossifrage Feb 28 '19 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.