>> 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.
> 
> Let me state thing in a different way, and see if this is what you
> meant: Every function will have as a prerequisite that its inputs are
> fully reduced and will have a postcondition that its output is fully
> reduced.

Assertion is that every function but addition and mul_by_[23] *has* (not
"will have", but "has") such postcondition that their outputs are fully
reduced as long as inputs are. Not to mention that multiplication (and
squaring) *can* (or should we say "is likely to") produce fully reduced
output even if inputs are not fully reduced.

> We know that ecp_nistz256_add doesn't fully reduce its output
> even if the input is fully reduced, and we know that
> ecp_nistz256_mul_by_[23] are implemented in terms of ecp_nistz256_add
> (or equivalent logic, in the case of some of the ASM stuff).
> Accordingly, the plan of action is:
> 
> * Fix ecp_nistz256_mul_by_2 and ecp_nistz256_mul_by_3 to fully reduce
> their outputs.
> 
> * Fix ecp_nistz256_add to fully reduce its output.

As for specifically addition see below. As for fixing mul_by_[23] and
the fact that they use addition. There are two ways. a) Modify addition
so that it *preserves* property of being fully reduced and leave
mul_by_[23] as is. b) Let addition as is and add additional step to
mul_by_[23]. The choice of approach can be platform-specific. For
example on x86_64 a) is simpler and appears more efficient. But on some
platforms b) could be better option.

> * Ensure in ecp_nistz256_points_mul that all the input coordinates are
> fully reduced.

I didn't mean to add any additional steps, but simply see that inputs
should be fully reduced. Simply put question is if output from
conversion to Montgomery representation is fully reduced. And then as
all involved subroutines would *preserve* the property, everything
remains fully reduced throughout the complete course.

> After all of this, we won't have to worry about the handling of
> partially-reduced values anywhere.
> 
> Is that correct? In particular, you said "we only have to watch out
> for mul_by_[23]" but you didn't mention ecp_nistz256_add, which *is*
> used directly in ecp_nistz256_point_double, according to the reference
> C implementation.

Rationale behind not explicitly mentioning addition is following
sequence from ecp_nistz256_point_double:

    ecp_nistz256_add(M, in_x, Zsqr);
    ecp_nistz256_mul_mont(M, M, Zsqr);
    ecp_nistz256_mul_by_3(M, M);
    ecp_nistz256_sqr_mont(res_x, M);

It doesn't matter if addition returns partially reduced result, as long
as mul_by_3 ties it up.

-- 
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev

Reply via email to