[openssl-dev] Partially- vs. full- reduced inputs to ecp_nistz256_neg

[Andy Polyakov]

>>> No, it subtraction subroutine uses *borrow* to determine if modulus is
>>> to be added. I.e. (a >= b) ? (a - b) : (P - (b - a)). If both a and b
>>> are less than P, then result is less than P.
>>
>> Consider the case where a > P and a >= b and b is very small (e.g. 1).
>> For example, a == P + 2 and b == 1, so a >= b, and a - b == P + 2 - 1
>> == P + 1.
> 
> But assertion was "if *both* a and b are less than P". I can also tell
> that multiplication result is fully reduced.

And it's not only that multiplication (and squaring) result is fully
reduced, it, multiplication (ans squaring) subroutine can actually
manage partially reduced input. On related note one can point out that
result of addition (and mul_by_[2|3]) is partially reduced. But it's
multiplication's ability to handle it that ties things up. One should
also remember that it always ends with multiplication when result is
converted from Montgomery representation. As well as that it starts with
multiplication when input is converted to Montgomery representation...