# Question on using endomorphism on secp256k1 and negative results

I have read section 3.5 (algorithm 3.7) in "Guide to Elliptic Curve Cryptography", and have been trying to implement endomorphism on secpt256k1 to speed up calculating $$kP$$ by changing it into 2 point multiplication operations over half-size bit widths of k with a final point add. I tried to implement this in Python first to make sure I had the equations correct.

I can follow algorithm 3.7 to calculate $$k_1$$ and $$k_2$$, but for some values of k input I will get a negative $$k_2$$.

Does this mean when I evaluate $$kP = k_1P + k_2φ(P)$$, where $$φ(P) : (x, y) →(βx, y)$$ , I have to either convert $$k_2$$ to positive by doing $$k_2' = n - k_2$$ where $$n$$ is the curve order (this would not make sense as now $$k_2$$ would be the same bit size of $$k$$), or do I calculate $$k_2φ(P)$$ and then find the inverse of this point (just negate the Y coordinate) before adding it to $$k_1P$$?

This is my code I wrote (I am also not sure if all these operations should be mod n or not).

I do a final check to see if the values match what they should in the textbook ($$k = k_1 +k_2λ$$ mod n).

But I also have the problem of regardless of $$k_2$$ being negative (and so I would do the final inversion), the result I calculate from $$kP$$ does not match the result when I don't use endomorphism (I am using the double-add algorithm for the two point multiplications, not point or NAF, if this makes a difference). I was wondering if anyone knows why?

def decompose_mult(k):
curve_n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
lam = 37718080363155996902926221483475020450927657555482586988616620542887997980018
beta = 55594575648329892869085402983802832744385952214688224221778511981742606582254
a1 = 64502973549206556628585045361533709077
a2 = 367917413016453100223835821029139468248
b2 = 64502973549206556628585045361533709077
b1_neg = 303414439467246543595250775667605759171

c1 = (b2*k) // curve_n
c2 = (b1_neg*k) // curve_n

c1_a1 = (c1*a1) % curve_n
c2_a2 = (c2*a2) % curve_n

c1_b1 = (c1*b1_neg) % curve_n
c2_b2 = (c2*b2) % curve_n

k1 = (k - (c1_a1) - (c2_a2))
k2 = c1_b1 - c2_b2

print ("k1 ", k1, " bits ", k1.bit_length())
print ("k2 ", k2, " bits ", k2.bit_length())

k_test = (k1 + k2*lam) % curve_n
if (k_test == k):
print("Values matched")
else:
print("Values MISMATCHED")
print ("k_test ", k_test)
print ("k ", k)
$$$$
`

The algorithm has an explicit case for whether $$k_{j,i} > 0$$ or not, in the loop in step 8.2. Obviously a conditional like this is bad news for fast constant-time arithmetic if taken naively. But as you noted, you can simply do a conditional subtraction in the coordinate field to negate the point, and then do the point addition unconditionally.
• I was trying to use the double-add algorithm for point multiplication rather than the one in 3.77 you linked, mainly because this is going to run on an FPGA and I already have the code finished, I just wanted to try adding on the "endomorphism" speedup. As far as I understand I should still be able to use the basic double-add algorithm, what I'm doing is checking if $k_2$ is negative, and if it is I invert the result of $abs(k_2)φ(P)$ before adding it to $k_1P$. But I don't seem to get the right answer. Does my approach sound OK? Apr 8, 2019 at 22:37
• I figured out my problem, I was taking mod n instead of mod p here: $φ(P):(x,y)→(βx$ mod p $,y)$ after fixing this it is working. Apr 8, 2019 at 23:00