kokke / kokke/tiny-ECDH-c

Point double coordinate Y wrong

Open
#33 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
C
Stars
296
Forks
70
PR merge metrics
No merged PRs in 30d

Description

I was working on my own implementation of Galois Field & Elliptic Curve arithmetic and I used your work as an algorithm reference (in addition to using the NIST documentation), and I found an algorithmic error in your point double algorithm (function **static void gf2point_double(uint8_t* x, uint8_t* y)**). The algo produces correct coordinate X, but incorrect coordinate Y. It's a careless error, that went away once I carefully rewrote three last math operations with a NIST algorithm open.

I used K233 curve for testing.

I edited your "generate key" function so it doesn't reject small numbers as a private key (just a goto to the valid private key branch of code), and I set my test private key to 2, so the output would be 2G (twice the base point of the curve). I found the expected value of 2G online at [http://point-at-infinity.org/ecc/nisttv](http://point-at-infinity.org/ecc/nisttv), and I also verified this result with Wolfram Mathematica, where I calculated 2G for K233. The reference matches Wolfram Mathematica result (not only for 2G, but also beyond it). Your algorithm produced correct X value for 2G, but an incorrect Y value for 2G. I rewrote the three last operations (after the resulting X coordinate was computed correctly), and my result agreed with both online reference value and Wolfram Mathematica. You messed up some input/output parameters in those last operations and overwrote one of the parameters that shouldn't have been overwritten. It took me under 10 minutes to fix it (I just rewrote the last 3 operations from scratch referencing the spec doc).

Here is the NIST reference document (that you also cite in your implementation), page 31 has the formula: [https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186.pdf](NIST SP 800-186 PDF).

```
static void gf2point_double(gf2elem_t x, gf2elem_t y)
{
/* iff P = O (zero or infinity): 2 * P = P */
if (bitvec_is_zero(x))
{
bitvec_set_zero(y);
}
else
{
gf2elem_t l;

gf2field_inv(l, x);
gf2field_mul(l, l, y);
gf2field_add(l, l, x);
gf2field_mul(y, x, x);
gf2field_mul(x, l, l);
#if (coeff_a == 1)
gf2field_inc(l);
#endif
gf2field_add(x, x, l); //WRONG
gf2field_mul(l, l, x); //WRONG
gf2field_add(y, y, l); //WRONG
}
}
```

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with the gf2point_double function and compare its final three operations with the NIST SP 800-186 formula on page 31. Reproduce the K233 test using private key 2, then verify that the computed 2G coordinates match the cited reference and Mathematica result, including Y.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
cryptography
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
55/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.