dbaryshkov@gmail.com writes:
GOST curves will require different "fixups" for fast (mul X mod p) operations. Move these operations to ecc_modulo structure and call them via function pointer.
Can you explain what methods you intend to use? I had a quick look at the prime definitions in the next patch,
+ else if (!strcmp (curve, "gc256b")) + { + ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, + "ffffffffffffffffffffffffffffffff" + "fffffffffffffffffffffffffffffd97",
Should work fine with the current functions.
+ else if (!strcmp (curve, "gc256c")) + { + ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, + "80000000000000000000000000000000" + "00000000000000000000000000000c99",
Could use special tricks. Structure is similar to the q for curve25519.
+ else if (!strcmp (curve, "gc256d")) + { + ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, + "9b9f605f5a858107ab1ec85e6b41c8aa" + "cf846e86789051d37998f7b9022d759b",
This has no visible structure. One could maybe use some variant of the 3/2 division in https://gmplib.org/~tege/division-paper.pdf to find a good enough quotient, and divide without any bignum adjustment step. The result should then be a non-canonical remainder, in the range 0 <= r < 2^256. Everything needs to be side-channel silent.
Another option is to premultiply, and do computations mod k p for some smallish k. With k = 0x1a51f176161f1d734 (same as the 3/2 reciprocal, I think),
k p = ffffffffffffffffd8e5627c0706fb8dc4f73162b7fca65ab59cdb66ec652b2787ac757f10ec107c
with friendly structure (but one word larger). I think this trick is known as Svoboda division. But for the main operations, it is likely more efficient to use plain unstructured redc, precomputing p^{-1} mod B (where B is word size, 2^32 or 2^64 depending on architecture).
Regards, /Niels