`MontyForm` variable-time arithmetic for constants

[daxpedda]

Elliptic-curve algorithms often contain arithmetic with constants. MontyForm could provide functions that optimize these operations.

I propose to introduce *_vartime methods that are only variable-time over rhs: MontyForm. They have to be constant-time for lhs.

Related: #839.

[fjarri]

Probably Word could be used instead of u8? I doubt the logic would change.

[daxpedda]

I'm not super-familiar with the library, but for the public API I think Limb would be better to allow for easy cross-platform conversions.

[tarcieri]

This seems like #585 but for *MontyForm.

See #650 as an example. It's easy enough to support all of the primitive unsigned integer types.

Edit: I see *MontyForm support was requested before too: #585 (comment)

[daxpedda]

I reduced the issue to only cover the variable-time methods with MontyForm. Small integers are covered by #585.

[tarcieri]

@daxpedda so specifically you want const fn-friendly vartime functions that use e.g. a Limb/Word as the rhs operand?

Which ones specifically? add/sub/mul?

[daxpedda]

No doesn't have to be const fn, just fn is fine.
Limb/Word but also MontyForm for rhs, as long as they are faster then the existing methods.
I would need Add, Sub and Mul.

The important part is that they are variable-time for rhs only, they have to be constant-time for lhs.

EDIT: I just realized that after changing it the OP isn't very clear about this indeed. Trying to clarify it now.

[tarcieri]

So you just want variable-time methods where rhs is expected to be a constant and therefore they would behave in constant time in such cases?

[daxpedda]

Yes!

[andrewwhitehead]

I don't think there's a lot that can be done to optimize for rhs while staying constant-time for lhs, any conditional reductions would depend on both values. OTOH we could add optimizations for small constants.

A single-step Montgomery reduction allows reduction from N+1 limbs in O(n) time instead of O(n^2). This would require adding another constant C = 2**(N + W) mod p to Montgomery parameters, where W is the bit width of a limb (this could have a small performance impact for FixedMontyForm). It would allow easier conversion from small (Limb-sized) constants to Montgomery form, which would then be used with the normal addition, subtraction, and multiplication operations.

To compute c*R mod p we multiply (lo, hi): (Limb, Uint) = c*C and perform the single-step reduction. This is a 1*N multiplication and a 1*N reduction which can be performed in one pass (or two if/when vectorized operations would be faster). This can be improved upon for very small constants such as two = R.double(), but only by a constant factor.

I think the other option would be to support a small Barrett-style reduction of a Uint•Limb product. For conversion into Montgomery form the product would be (lo, hi) = (Z, c) = 2**N * c while multiplication by a Montgomery form would reduce (lo, hi) = M*c. I think addition would mean reducing (lo, hi) = (M, c) = M + 2**N * c. This seems like it would require additional bit shifts compared to the single-step Montgomery reduction, although the precomputed constant added to the parameters would be smaller.