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