From afa13249ed45826c2d7086714026c9bc1ccbf963 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 18 Aug 2020 11:28:17 -0700 Subject: Update test vectors and generation script --- bip-0340/test-vectors.py | 58 ++++++++++++++++++++++++++++++++---------------- 1 file changed, 39 insertions(+), 19 deletions(-) (limited to 'bip-0340/test-vectors.py') diff --git a/bip-0340/test-vectors.py b/bip-0340/test-vectors.py index 9c029ec..e5b8847 100644 --- a/bip-0340/test-vectors.py +++ b/bip-0340/test-vectors.py @@ -1,6 +1,14 @@ import sys from reference import * +def is_square(x): + return int(pow(x, (p - 1) // 2, p)) == 1 + +def has_square_y(P): + """Determine if P has a square Y coordinate. Used in an earlier draft of BIP340.""" + assert not is_infinity(P) + return is_square(P[1]) + def vector0(): seckey = bytes_from_int(3) msg = bytes_from_int(0) @@ -19,9 +27,16 @@ def vector0(): # we should have at least one test vector where the the point reconstructed # from the public key has a square and one where it has a non-square Y # coordinate. In this one Y is non-square. - pubkey_point = lift_x_even_y(pubkey) + pubkey_point = lift_x(pubkey) assert(not has_square_y(pubkey_point)) + # For historical reasons (R tiebreaker was squareness and not evenness) + # we should have at least one test vector where the the point reconstructed + # from the R.x coordinate has a square and one where it has a non-square Y + # coordinate. In this one Y is non-square. + R = lift_x(sig[0:32]) + assert(not has_square_y(R)) + return (seckey, pubkey, aux_rand, msg, sig, "TRUE", None) def vector1(): @@ -30,6 +45,11 @@ def vector1(): aux_rand = bytes_from_int(1) sig = schnorr_sign(msg, seckey, aux_rand) + + # The point reconstructed from the R.x coordinate has a square Y coordinate. + R = lift_x(sig[0:32]) + assert(has_square_y(R)) + return (seckey, pubkey_gen(seckey), aux_rand, msg, sig, "TRUE", None) def vector2(): @@ -40,13 +60,13 @@ def vector2(): # The point reconstructed from the public key has a square Y coordinate. pubkey = pubkey_gen(seckey) - pubkey_point = lift_x_even_y(pubkey) + pubkey_point = lift_x(pubkey) assert(has_square_y(pubkey_point)) # This signature vector would not verify if the implementer checked the - # squareness of the X coordinate of R instead of the Y coordinate. - R = lift_x_square_y(sig[0:32]) - assert(not is_square(R[0])) + # evenness of the X coordinate of R instead of the Y coordinate. + R = lift_x(sig[0:32]) + assert(R[0] % 2 == 1) return (seckey, pubkey, aux_rand, msg, sig, "TRUE", None) @@ -66,7 +86,7 @@ def vector3(): # Signs with a given nonce. This can be INSECURE and is only INTENDED FOR # GENERATING TEST VECTORS. Results in an invalid signature if y(kG) is not -# square. +# even. def insecure_schnorr_sign_fixed_nonce(msg, seckey0, k): if len(msg) != 32: raise ValueError('The message must be a 32-byte array.') @@ -76,12 +96,12 @@ def insecure_schnorr_sign_fixed_nonce(msg, seckey0, k): P = point_mul(G, seckey0) seckey = seckey0 if has_even_y(P) else n - seckey0 R = point_mul(G, k) - e = int_from_bytes(tagged_hash("BIP340/challenge", bytes_from_point(R) + bytes_from_point(P) + msg)) % n + e = int_from_bytes(tagged_hash("BIP0340/challenge", bytes_from_point(R) + bytes_from_point(P) + msg)) % n return bytes_from_point(R) + bytes_from_int((k + e * seckey) % n) -# Creates a singature with a small x(R) by using k = 1/2 +# Creates a singature with a small x(R) by using k = -1/2 def vector4(): - one_half = 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0 + one_half = n - 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0 seckey = bytes_from_int(0x763758E5CBEEDEE4F7D3FC86F531C36578933228998226672F13C4F0EBE855EB) msg = bytes_from_int(0x4DF3C3F68FCC83B27E9D42C90431A72499F17875C81A599B566C9889B9696703) sig = insecure_schnorr_sign_fixed_nonce(msg, seckey, one_half) @@ -100,21 +120,21 @@ def vector5(): sig = schnorr_sign(msg, seckey, default_aux_rand) pubkey = bytes_from_int(0xEEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34) - assert(lift_x_even_y(pubkey) is None) + assert(lift_x(pubkey) is None) return (None, pubkey, None, msg, sig, "FALSE", "public key not on the curve") def vector6(): seckey = default_seckey msg = default_msg - k = 3 + k = 6 sig = insecure_schnorr_sign_fixed_nonce(msg, seckey, k) - # Y coordinate of R is not a square + # Y coordinate of R is not even R = point_mul(G, k) - assert(not has_square_y(R)) + assert(not has_even_y(R)) - return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "has_square_y(R) is false") + return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "has_even_y(R) is false") def vector7(): seckey = default_seckey @@ -147,7 +167,7 @@ def vector9(): sig = insecure_schnorr_sign_fixed_nonce(msg, seckey, k) bytes_from_point.__code__ = bytes_from_point_tmp - return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "sG - eP is infinite. Test fails in single verification if has_square_y(inf) is defined as true and x(inf) as 0") + return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "sG - eP is infinite. Test fails in single verification if has_even_y(inf) is defined as true and x(inf) as 0") def bytes_from_point_inf1(P): if P == None: @@ -166,7 +186,7 @@ def vector10(): sig = insecure_schnorr_sign_fixed_nonce(msg, seckey, k) bytes_from_point.__code__ = bytes_from_point_tmp - return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "sG - eP is infinite. Test fails in single verification if has_square_y(inf) is defined as true and x(inf) as 1") + return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "sG - eP is infinite. Test fails in single verification if has_even_y(inf) is defined as true and x(inf) as 1") # It's cryptographically impossible to create a test vector that fails if run # in an implementation which merely misses the check that sig[0:32] is an X @@ -178,7 +198,7 @@ def vector11(): # Replace R's X coordinate with an X coordinate that's not on the curve x_not_on_curve = bytes_from_int(0x4A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269BC70A74F8220429BA1D) - assert(lift_x_square_y(x_not_on_curve) is None) + assert(lift_x(x_not_on_curve) is None) sig = x_not_on_curve + sig[32:64] return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "sig[0:32] is not an X coordinate on the curve") @@ -222,10 +242,10 @@ def vector14(): sig = schnorr_sign(msg, seckey, default_aux_rand) pubkey_int = p + 1 pubkey = bytes_from_int(pubkey_int) - assert(lift_x_even_y(pubkey) is None) + assert(lift_x(pubkey) is None) # If an implementation would reduce a given public key modulo p then the # pubkey would be valid - assert(lift_x_even_y(bytes_from_int(pubkey_int % p)) is not None) + assert(lift_x(bytes_from_int(pubkey_int % p)) is not None) return (None, pubkey, None, msg, sig, "FALSE", "public key is not a valid X coordinate because it exceeds the field size") -- cgit v1.2.3