1
$\begingroup$

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)
```
$\endgroup$

1 Answer 1

0
$\begingroup$

Do you mean Algorithm 3.77 on p. 129?

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – bsdevlin
    Apr 8, 2019 at 22:37
  • $\begingroup$ 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. $\endgroup$
    – bsdevlin
    Apr 8, 2019 at 23:00
  • $\begingroup$ Yep, important to keep the coordinate field and the scalar ring straight! $\endgroup$ Apr 9, 2019 at 1:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.