Issues with implementing scalar multiplication using projective coordinates for elliptic curves

Rui

4/4/24, 5:13 PM

I am trying to implement scalar multiplication for elliptic curves using projective coordinates and the short Weierstrass equation. Specifically, I am using the Montgomery ladder algorithm with addition and doubling functions that take and return projective points.

However, I am encountering issues as the result I get from the algorithm is incorrect. I have tested my addition and doubling functions and they seem to be working fine, so I am not sure what the issue could be.

Here is the short Weierstrass equation that I am using: $$Y^2 Z = X^3 + aXZ^2 + bZ^3$$

Can anyone provide insight into what I might be missing in my implementation? Any help would be greatly appreciated. Thank you.

Edit: I'm using the addition formulas from this paper, and for the scalar multiplication I'm using this algorithm

  R0 ← 0
  R1 ← P
  for i from m downto 0 do
      if di = 0 then
          R1 ← point_add(R0, R1)
          R0 ← point_double(R0)
      else
          R0 ← point_add(R0, R1)
          R1 ← point_double(R1)
  return R0

0 + 5

elliptic-curves

fgrieu

4/4/24, 5:26 PM

We've seen similar questions where the method and result was actually OK, but checking it against a reference result was wrong. Recall that when working in $\mathbb F_q$, a point on the curve has $q-1$ equally valid distinct projective coordinates!

Rui

4/4/24, 8:14 PM

@fgrieu I think this is not the case. When comparing against a reference result I also tried to convert both to affine coordinates and the results are different

fgrieu

4/5/24, 5:18 AM

Suggestion: [edit](https://crypto.stackexchange.com/posts/105963/edit) the question to add some indication of the addition and doubling formulas you are using, perhaps among [these](https://www.hyperelliptic.org/EFD/g1p/auto-shortw-projective.html), and conversion with affine; and explain your scalar multiplication algorithm (which would be the likely culprit if addition, doubling and conversion functions are working fine).

Rui

4/6/24, 1:09 AM

@fgrieu Thank you for the suggestion. I have updated the question accordingly.

fgrieu

4/6/24, 6:00 AM

This is increasingly looking like a programming problem (which is off-topic), without the code on top of that. One remark: the pseudocode for the Montgomery ladder assumes $d$ has $m+1$ bits, which is slightly unusual. Suggestion: test for incremental values of $d$ starting from $0$, to determine where things go wrong.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Issues with implementing scalar multiplication using projective coordinates for elliptic curves

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.