:sigh: I forgot the attachment with my test vectors. Here it is. On Tue, Jun 28, 2016 at 10:43 AM, 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 have built a testing framework for exploring things like this in > *ring*. I will attach the input file for my tests which show that > ecp_nistz256_point_add seems to fail to recognize the point at > infinity correctly. However, it is also possible that I just don't > understand how ecp_nistz256 intends to work. My questions are: > > 1. With respect to additions of the form (a + infinity == a) and > (infinity + b == b), is the code in ecp_nistz256_point_add and > ecp_nistz256_point_add_affine correct? > > 2. if it is correct, could we add more explanation as to why it is correct? > > 3. Given the specifics of the implementation of the ecp_nistz256 > implementation, is it even possible for us to encounter the point at > infinity as one of the parameters to ecp_nistz256_point_add, other > than in the very final addition that adds g_scalar*G + p_scalar*P? See > Section 4.1 of [1]. > > Background: For based point (G) multiplication, the code has a large > table of multiples of G, in affine (not Jacobian) coordinates. The > point at infinity cannot be encoded in affine coordinates. 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. Regardless, if you represent the point at infinity as (0, 0) > then it makes sense to check (x, y) == (0, 0). > > 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). > > Note that this is confusing because `EC_POINT_new` followed by > `EC_POINT_to_infinity` initializes (X, Y, Z) = (0, 0, 0). Thus, the > check of (x, y) == (0, 0) "works" as well as the check z == 0. But, it > doesn't work in real-life cases where the point is infinity is > encountered during calculations, because we'll have (X, Y) != (0, 0) > but Z == 0. > > The assembly language code that does this check is hard to understand > unless one is familiar with SIMD. However, the C reference > implementation that the assembly language code used as a model is easy > to understand. This code can be found in the ecp_nistz256.c file. > > Note the parameters of ecp_nistz256_point_add are P256_POINT, not > P256_POINT_AFFINE, so "representation of the point at infinity as (0, > 0)" doesn't make sense to me. But, that's exactly what it checks. > > In ecp_nistz256_point_add_affine, it makes more sense to me, because > parameter |b| is in fact a |P256_POINT_AFFINE|. However, |a| is not a > |P256_POINT_AFFINE|, so the (x, y) == (0, 0) check doesn't make sense > to me. The x86-64 and x86 assembly language code seems to emulate this > exactly. I didn't test the ARM code, but I'd guess it is similar. > > [1] https://eprint.iacr.org/2014/130.pdf (Section 4.1) > > Here's the specific logic I'm talking about (which is also present in > the asm code): > > ``` > static void ecp_nistz256_point_add(P256_POINT *r, > const P256_POINT *a, const P256_POINT *b) { > [...] > > const BN_ULONG *in1_x = a->X; > const BN_ULONG *in1_y = a->Y; > const BN_ULONG *in1_z = a->Z; > > const BN_ULONG *in2_x = b->X; > const BN_ULONG *in2_y = b->Y; > const BN_ULONG *in2_z = b->Z; > > /* We encode infinity as (0,0), which is not on the curve, > * so it is OK. */ > in1infty = (in1_x[0] | in1_x[1] | in1_x[2] | in1_x[3] | > in1_y[0] | in1_y[1] | in1_y[2] | in1_y[3]); > if (P256_LIMBS == 8) > in1infty |= (in1_x[4] | in1_x[5] | in1_x[6] | in1_x[7] | > in1_y[4] | in1_y[5] | in1_y[6] | in1_y[7]); > > in2infty = (in2_x[0] | in2_x[1] | in2_x[2] | in2_x[3] | > in2_y[0] | in2_y[1] | in2_y[2] | in2_y[3]); > if (P256_LIMBS == 8) > in2infty |= (in2_x[4] | in2_x[5] | in2_x[6] | in2_x[7] | > in2_y[4] | in2_y[5] | in2_y[6] | in2_y[7]); > > [...] > } > > static void ecp_nistz256_point_add_affine(P256_POINT *r, > const P256_POINT *a, > const P256_POINT_AFFINE *b) { > [...] > > const BN_ULONG *in1_x = a->X; > const BN_ULONG *in1_y = a->Y; > const BN_ULONG *in1_z = a->Z; > > const BN_ULONG *in2_x = b->X; > const BN_ULONG *in2_y = b->Y; > > /* > * In affine representation we encode infty as (0,0), which is not on the > * curve, so it is OK > */ > in1infty = (in1_x[0] | in1_x[1] | in1_x[2] | in1_x[3] | > in1_y[0] | in1_y[1] | in1_y[2] | in1_y[3]); > if (P256_LIMBS == 8) > in1infty |= (in1_x[4] | in1_x[5] | in1_x[6] | in1_x[7] | > in1_y[4] | in1_y[5] | in1_y[6] | in1_y[7]); > > in2infty = (in2_x[0] | in2_x[1] | in2_x[2] | in2_x[3] | > in2_y[0] | in2_y[1] | in2_y[2] | in2_y[3]); > if (P256_LIMBS == 8) > in2infty |= (in2_x[4] | in2_x[5] | in2_x[6] | in2_x[7] | > in2_y[4] | in2_y[5] | in2_y[6] | in2_y[7]); > > in1infty = is_zero(in1infty); > in2infty = is_zero(in2infty); > > [...] > } > ``` > > Cheers, > Brian > -- > https://briansmith.org/
-- https://briansmith.org/
# Some test vectors for a + b == r for the P-256 curve that demonstrate the # incorrect point-on-the-curve check. # # All test vectors' elements are in the Montgomery domain. Also, the result |r| # is normalized to Z == to_mont(1). # G + inf == G. The code handles this correctly, but only accidentally because # all three of (X, Y, Z) are zero. Curve = P-256 a = 18905f76a53755c679fb732b7762251075ba95fc5fedb60179e730d418a9143c, 8571ff1825885d85d2e88688dd21f3258b4ab8e4ba19e45cddf25357ce95560a, 00000000fffffffeffffffffffffffffffffffff000000000000000000000001 b = 0000000000000000000000000000000000000000000000000000000000000000, 0000000000000000000000000000000000000000000000000000000000000000, 0000000000000000000000000000000000000000000000000000000000000000 r = 18905f76a53755c679fb732b7762251075ba95fc5fedb60179e730d418a9143c, 8571ff1825885d85d2e88688dd21f3258b4ab8e4ba19e45cddf25357ce95560a, 00000000fffffffeffffffffffffffffffffffff000000000000000000000001 # G + the point (0, 0, Junk), which is not on the curve as affine point (0, 0) # is not on the curve. The code thinks this is at infinity because # (X, Y) == (0, 0), but it's not at infinity, because Z != 0. The value of |r| # here is what the code actually calculates (the value of G). There is no right # answer for this input because b isn't even on the curve. Curve = P-256 a = 18905f76a53755c679fb732b7762251075ba95fc5fedb60179e730d418a9143c, 8571ff1825885d85d2e88688dd21f3258b4ab8e4ba19e45cddf25357ce95560a, 00000000fffffffeffffffffffffffffffffffff000000000000000000000001 b = 0000000000000000000000000000000000000000000000000000000000000000, 0000000000000000000000000000000000000000000000000000000000000000, 6d333da42e30f7011245b6281015ded14e0f100968e758a1b6c3c083afc14ea0 r = 18905f76a53755c679fb732b7762251075ba95fc5fedb60179e730d418a9143c, 8571ff1825885d85d2e88688dd21f3258b4ab8e4ba19e45cddf25357ce95560a, 00000000fffffffeffffffffffffffffffffffff000000000000000000000001 # G + (n*G) == G. Note that n*G results in the point at infinity (Z == 0), but # with (X, Y) != (0, 0). The code calculates the wrong result. Here |r| is what # the code should calculate (the value of G). Curve = P-256 a = 18905f76a53755c679fb732b7762251075ba95fc5fedb60179e730d418a9143c, 8571ff1825885d85d2e88688dd21f3258b4ab8e4ba19e45cddf25357ce95560a, 00000000fffffffeffffffffffffffffffffffff000000000000000000000001 b = 2b11cb945c8cf152ffa4c9c2b1c965b019b35d0b7626919ef0ae6cb9d232f8af, 6d333da42e30f7011245b6281015ded14e0f100968e758a1b6c3c083afc14ea0, 0000000000000000000000000000000000000000000000000000000000000000 r = 18905f76a53755c679fb732b7762251075ba95fc5fedb60179e730d418a9143c, 8571ff1825885d85d2e88688dd21f3258b4ab8e4ba19e45cddf25357ce95560a, 00000000fffffffeffffffffffffffffffffffff000000000000000000000001
-- openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
