Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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);
else
    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?

share|improve this question
    
This sort of question tends to be viewed as off-topic since it is about a users implementation. –  figlesquidge Feb 26 at 10:53
1  
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. –  user12230 Feb 26 at 11:02
    
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. –  user12230 Feb 26 at 15:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.