Andy Polyakov <ap...@openssl.org> wrote:
>> Note in particular that, IIUC, ecp_nistz256_neg will never get an
>> unreduced input when applied to the the based point multiples, because
>> those are already fully reduced. But, when it is used in
>> ecp_nistz256_windowed_mul, it isn't clear whether or how the input Y
>> coordinate is fully reduced mod P before passed to ecp_nistz256_neg.
>
> Is it correctly understood that concern is that input to
> ecp_nistz256_windowed_mul, which in turn can be *user* input, would be
> not fully reduced?

Let's assume, for the purpose of this discussion, that the coordinates
of the user input point `p` is already reduced, or that we will reject
it or reduce it.

Given that input point, we calculate multiples 1*p, 2*p, ... 16*p
using ecp_nistz256_point_double and ecp_nistz256_point_add. Let's look
at how ecp_nistz256_point_double and ecp_nistz256_point_add calculates
the Y coordinate:

double:
    ...
    ecp_nistz256_mul_mont(S, S, M);
    ecp_nistz256_sub(res_y, S, res_y);

add:
    ...
    ecp_nistz256_mul_mont(res_y, R, res_y);
    ecp_nistz256_sub(res_y, res_y, S2);
    memcpy(r->Y, res_y, sizeof(res_y));

Now, I was told by one of the authors of the original code that all
the ecp_nistz256_* field operations return a result in the range [0,
2**256), not [0, P). This can be seen in the reduction code, e.g. in
ecp_nistz256_sub. It uses the result of "sbb \$0, $t4" to determine if
the result is larger than 2**256 - 1. If the result is larger than
2**256 - 1 then it subtracts P. Otherwise, it returns the result. But,
in the case where it doesn't subtract P, the result might be in the
range [P, 2**256); i.e. not fully reduced.

NOTE: I may not be understanding it correctly! It's a very real
possibility. But, my understanding seems to match what I was told,
which is that the results of all the field operations are not fully
reduced.

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

Reply via email to