Correct secp256k1_gej_add

sipa commented at 1:51 pm on June 22, 2015: contributor

Fixes #257 by computing both double and add, and cmov’ing the correct result.

This is a simple and complete solution, but it has a significant performance impact (18% slowdown for signing). More efficient solutions can come later.

Correct secp256k1_gej_add_ge e6d22fd402

gmaxwell commented at 11:31 pm on June 22, 2015: contributor

Can this come with some a more comprehensive test?

Add tests for adding P+Q with P.x!=Q.x and P.y=-Q.y 9b18bb5b33

sipa commented at 10:43 am on June 23, 2015: contributor

@gmaxwell Added a test that fails due to #257, and the first commit here fixes it.

tests: Add failing unit test for #257 (bad addition formula) 171149d69b

sipa commented at 3:21 pm on June 23, 2015: contributor

@gmaxwell Also added @apoelstra’s test which does not depend on having the endomorphism compiled in.

in src/tests.c: in 171149d69b

1189+     * Q = -int(lam) * P
1190+     * print "    P: %x %x" % P.xy()
1191+     * print "    Q: %x %x" % Q.xy()
1192+     * print "P + Q: %x %x" % (P + Q).xy()
1193+     */
1194+    secp256k1_gej_t aj = SECP256K1_GEJ_CONST(

dcousens commented at 5:05 am on June 24, 2015:

const?

apoelstra commented at 1:05 pm on June 24, 2015:

I tried making these const, but secp256k1_ge_set_gej scales its Jacobian input, blocking it. (IIRC one of the three constants can be const without trouble, but I didn’t to make the code more symmetric.)

On Tue, Jun 23, 2015 at 10:05:53PM -0700, Daniel Cousens wrote:

```
\* C = EllipticCurve ([F (0), F (7)])
```

\* G = C.lift_x(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)

```
\* N = FiniteField(G.order())
```
```
*
```

\* # endomorphism values (lambda is 1^{1/3} in N, beta is 1^{1/3} in F)

```
\* x = polygen(N)
```
```
\* lam  = (1 - x^3).roots()[1][0]
```
```
*
```
```
\* # random "bad pair"
```
```
\* P = C.random_element()
```
```
\* Q = -int(lam) \* P
```
```
\* print "    P: %x %x" % P.xy()
```
```
\* print "    Q: %x %x" % Q.xy()
```
```
\* print "P + Q: %x %x" % (P + Q).xy()
```
```
*/
```
secp256k1_gej_t aj = SECP256K1_GEJ_CONST(

const?

Reply to this email directly or view it on GitHub: https://github.com/bitcoin/secp256k1/pull/260/files#r33117648

Andrew Poelstra Mathematics Department, University of Texas at Austin Email: apoelstra at wpsoftware.net Web: https://www.wpsoftware.net/andrew

“When I came into my land, I did not understand: neither dry rot, nor the burn pile, nor the bark-beetle, nor the dry well, nor the black bear.” – Joanna Newsom

sipa commented at 1:06 pm on June 24, 2015: contributor

Closing; @apoelstra has a better implementation which I’ll turn into a PR soon.

sipa closed this on Jun 24, 2015

Correct secp256k1_gej_add_ge #260