1
$\begingroup$

I am new in Elliptic curve, so I started with implementing (single scalar multiplication) I have done it the simple way, and then I moved to Double & Add algorithm later with NAF form.

When I moved to the NAF form. Two versions of algorithm gave me two different results. And I'm not sure what did I miss.

I'm using ECC defined as: $y^2=x^3 - 2x +2$ over the finite field $GF(23)$

I'm trying to compute $7P$ where $P=[5,5]$, with simple double and add the result is $7P=[5,18]$ but with NAF $7P=[5,-5]$

I believe the reason is I compute $7P$ in double & add with NAF as $7P = 8P - P = O - [5,5] = [5,-5]$ so I'm not sure if I miss some important condition when working in NAF form.

Computed points:

1P:     [5, 5]
2P:     [15, 14]
3P:     [16, 15]
4P:     [11, 0]
5P:     [16, 8]
6P:     [15, 9]
7P:     [5, 18]
8P:     O
9P:     [5, 5]
10P:    [15, 14]
11P:    [16, 15]
12P:    [11, 0]
13P:    [16, 8]
14P:    [15, 9]
15P:    [5, 18]
16P:    O

double & add $7P = 1P + 2P + 4P = [5,18]$

double & add with NAF $7P = 8P - P = O - [5,5] = [5,-5]$

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Hint: in $\operatorname{GF}(23)$, what's another common notation for $-5$? $\endgroup$
    – fgrieu ♦
    Feb 2 at 11:36
  • 1
    $\begingroup$ Thanks a lot, I totally missed this. I feel bad for missing this one. $\endgroup$
    – Tibor
    Feb 2 at 11:40

1 Answer 1

Reset to default
0
$\begingroup$

It work's as expected, just forgot that the coordinate negation over a finite field GF(p) must use modular arithmetic. So -5 mod23 is 18.

Improve this answer
$\endgroup$

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.