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

[Andy Polyakov]

>> I think you are assuming that ret is in the range [0, 2P), so that if
>> you subtract P, the result would be in the range [0, P). That is the
>> case in normal Montgomery multiplication, where the inputs are in the
>> range [0, P). But, my understanding is that if the inputs are in the
>> range [P, 2**256), e.g. they are the result of ecp_nistz256_add, then
>> that assumption doesn't necessarily hold.
> 
> Looks like you are right. I mean it indeed appears to be possible for
> multiplication (and squaring) subroutine to return partially reduced
> result. But *only* if input was partially reduced. I.e. if input is
> fully reduced, the output *shall* be too. And if input is not fully
> reduced, then output *can* be.

It appears to me that with multiplication, squaring, subtraction,
negation, halving *preserving* property of being fully reduced (i.e. if
inputs are fully reduced, then output is too), we only have to watch out
for mul_by_[23], i.e. ensure that their outputs are fully reduced. This
would ensure that output will always be fully reduced.

In this and RT#4621 combined context one can conclude that *as long as*
inputs to ecp_nistz256_point_add are fully reduced, is_equal calls work
correctly, because there are no non-full-reduction-preserving calls
prior them. Would you agree?