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]$

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

1 Answer 1

1
$\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.

$\endgroup$

Your Answer

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

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