Brian Smith <br...@briansmith.org> wrote: > When doing math on short Weierstrass curves like P-256, we have to > special case points at infinity. In Jacobian coordinates (X, Y, Z), > points at infinity have Z == 0. However, instead of checking for Z == > 0, p256-x86-64 instead checks for (X, Y) == (0, 0). In other words, it > does, in some sense, the opposite of what I expect it to do. >
I exchanged email with both of the original authors of the code, Shay and Vlad. He that the ecp_nistz256_point_* functions indeed intend to represent the point at infinity as (0, 0) and it is expected (but I did not verify) that those functions should work when the point at infinity is encoded as (0, 0, _). The authors > instead decided to encode the point at infinity as (0, 0), since the > affine point (0, 0) isn't on the P-256 curve. It isn't clear why the > authors chose to do that though, since the point at infinity doesn't > (can't, logically) appear in the table of precomputed multiples of G > anyway. Actually, as the code says, the point at infinity implicitly occurs in the table implicitly. Obviously the accumulator point will be at infinity until at least a one bit is found in the scalar. > But, it seems like the functions that do the computations, like > ecp_nistz256_point_add and ecp_nistz256_point_add_affine, output the > point at infinity as (_, _, 0), not necessarily (0, 0, _). Also, > ecp_nistz256's EC_METHOD uses ec_GFp_simple_is_at_infinity and > ec_GFp_simple_point_set_to_infinity, which represent the point at > infinity with z == 0, not (x, y) == 0. Further ecp_nistz256_get_affine > uses EC_POINT_is_at_infinity, which checks z == 0, not (x, y) == 0. > This inconsistency is confusing, if not wrong. Given this, it seems > like the point-at-infinity checks in the ecp_nistz256_point_add and > ecp_nistz256_point_add_affine code should also be checking that z == 0 > instead of (x, y) == (0, 0). > Instead, when we convert a point from EC_POINT to P256_POINT or P256_POINT_AFFINE, we should translate the (_, _, 0) form into the (0, 0, 0) form. And/or reject points at infinity as inputs to the function. Similarly, when we convert the resultant P256_POINT to an EC_POINT, we chould translate the (0, 0) encoding of the point at infinity to the (0, 0, 0) form or at least the (_, _, 0) form. In particular, consider the case where you have an EC_POINT that isn't at infinity, e.g. (x, y, 1). Then you call EC_POINT_set_to_infinity on it. Then it is (x, y, 0). Then you pass it to EC_POINT_mul/EC_POINTs_mul even though you shouldn't. Maybe the precondition of EC_POINT_mul/EC_POINTs_mul is that none of the input points are at infinity, in which case it doesn't matter. (But if so, maybe these functions should do a point-at-infinity check.) But if it is allowed to pass in the point at infinity, then the ecp_nistz256 code should translate the input point from (_, _, 0) form to (0, 0, _) form before doing the computation. It can use is_zero and copy_conditional and friends to do this. Similarly, after the computation, it should translate the (0, 0, _) form to (_, _, 0) form. In particular, it should do such a translation before the code sets Z_is_one, AFAICT. Note that the nistz256 code might be using the form (0, 0, 0) instead of (0, 0, _) in which case this translation might not be necessary. Regardless, it would be useful to write tests for these cases: 1. Verify that the result is correct when any of the input points are (0, 0, 0) 2. Verify that the result is correct when any of the input points are (_, _, 0). 3. Verify that the result is correct, and in particular that Z_is_one is set correctly on the result, when the final result is at infinity, especially for the cases where neither the input points are at infinity, e.g. when adding (n-1)G to 1G. Note that all of the above cases have interesting sub-cases: the G scalar is NULL, the G scalar is non-NULL and zero-valued, G scalar is a multiple of G, G scalar is larger than G. And same for the P scalars. Cheers, Brian -- https://briansmith.org/
-- openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev