Add some missing secp256k1 routines

[Rexicon226]

I'm using s2n-bignum for field operations over secp256k1, and I need the ability to multiply scalars mod n. The closest function that exists now is bignum_mod_n256k1_4, but that doesn't give me the necessary API to reduce from bignum_mul_4_8.

I'm hoping for either a tomont API, so that I am able to use bignum_montmul, or an API for reducing the result of the non-montgomery multiplication into 4 limbs.

• There is also no montinv_p256k1 API to mirror the montinv_p256 one.
• No p256k1_montjadd.

Thank you!

[jargh]

Good point! The secp256k1 field doesn't seem to offer a compelling performance reason to go for either Montgomery or non-Montgomery, so a lot of field operations provide both to be more agnostic. As you point out though, this is not done consistently and there is no easy way of converting.

• It definitely makes sense to add something like a general group-order modulus function bignum_mod_n256k1 for generic length of input, by analogy with the same thing for NIST curves. I hope that would fix the first problem.
• Would you be OK working in a non-Montgomery representation, or possibly converting in and out, in which case secp256k1_jadd etc would work for point operations? But of course we could consistently add mont forms with more work.
• The lack of either bignum_inv_p256k1 or bignum_montinv_p256k1 is indeed a big failing relative to the other curves. At some performance cost, you could work around it via the generic bignum_modinv, but we should definitely provide one or both of these.

Although I'm quite keen on this curve myself, it's not high on our primary customer interests so I can't promise this will happen quickly, but I'll try to tackle at least the easier targets in the next few weeks.

[Rexicon226]

Thank you for the quick response!

For the record, I have been able to replicate all of the missing behaviour without too much difficulty.
I do tomont with:

bignum_montmul( 4, r->limbs, t, rr, n );

(where rr is R in the montgomery domain, i.e. R^2 mod n).

Inversion, as you suggest, I just do with modinv before I convert into mont domain. Fortunately my usecase is focused on correctness rather than performance, but it would be a welcome improvement to have the correct version. The less constants I need to define that may be wrong, the better.

For the jadd, I just implemented it using a generic sw form jacobian add formula. It's fine to move out of the montgomery domain for the jacobian adds, but as you note, it would be better if we just had the right API.

No worries about the timeline, as I've worked around all of the hurdles. But I would nevertheless appreciate this improvement!

[jargh]

Meanwhile Claude has been busy - I have only looked superficially but it looks somewhat plausible: #358. So maybe my not having time is no longer an excuse :-)

I will probably set Claude going on something inverse-related next, which would be more challenging but should also be feasible.

[jargh]

Oh, it failed the CT test but that's just because the check is too stupid not because there's a problem (worries the conditional branches are secret-dependent). I'll fix it.