1 import sys
2 from reference import *
3 4 5 def is_square(x):
6 return int(pow(x, (p - 1) // 2, p)) == 1
7 8 9 def has_square_y(P):
10 """Determine if P has a square Y coordinate. Used in an earlier draft of BIP340."""
11 assert not is_infinite(P)
12 return is_square(P[1])
13 14 15 def vector0():
16 seckey = bytes_from_int(3)
17 msg = bytes_from_int(0)
18 aux_rand = bytes_from_int(0)
19 sig = schnorr_sign(msg, seckey, aux_rand)
20 pubkey = pubkey_gen(seckey)
21 22 # We should have at least one test vector where the seckey needs to be
23 # negated and one where it doesn't. In this one the seckey doesn't need to
24 # be negated.
25 x = int_from_bytes(seckey)
26 P = point_mul(G, x)
27 assert (y(P) % 2 == 0)
28 29 # For historical reasons (pubkey tiebreaker was squareness and not evenness)
30 # we should have at least one test vector where the the point reconstructed
31 # from the public key has a square and one where it has a non-square Y
32 # coordinate. In this one Y is non-square.
33 pubkey_point = lift_x(pubkey)
34 assert (not has_square_y(pubkey_point))
35 36 # For historical reasons (R tiebreaker was squareness and not evenness)
37 # we should have at least one test vector where the the point reconstructed
38 # from the R.x coordinate has a square and one where it has a non-square Y
39 # coordinate. In this one Y is non-square.
40 R = lift_x(sig[0:32])
41 assert (not has_square_y(R))
42 43 return seckey, pubkey, aux_rand, msg, sig, "TRUE", None
44 45 46 def vector1():
47 seckey = bytes_from_int(0xB7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF)
48 msg = bytes_from_int(0x243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89)
49 aux_rand = bytes_from_int(1)
50 51 sig = schnorr_sign(msg, seckey, aux_rand)
52 53 # The point reconstructed from the R.x coordinate has a square Y coordinate.
54 R = lift_x(sig[0:32])
55 assert (has_square_y(R))
56 57 return seckey, pubkey_gen(seckey), aux_rand, msg, sig, "TRUE", None
58 59 60 def vector2():
61 seckey = bytes_from_int(0xC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B14E5C9)
62 msg = bytes_from_int(0x7E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C)
63 aux_rand = bytes_from_int(0xC87AA53824B4D7AE2EB035A2B5BBBCCC080E76CDC6D1692C4B0B62D798E6D906)
64 sig = schnorr_sign(msg, seckey, aux_rand)
65 66 # The point reconstructed from the public key has a square Y coordinate.
67 pubkey = pubkey_gen(seckey)
68 pubkey_point = lift_x(pubkey)
69 assert (has_square_y(pubkey_point))
70 71 # This signature vector would not verify if the implementer checked the
72 # evenness of the X coordinate of R instead of the Y coordinate.
73 R = lift_x(sig[0:32])
74 assert (R[0] % 2 == 1)
75 76 return seckey, pubkey, aux_rand, msg, sig, "TRUE", None
77 78 79 def vector3():
80 seckey = bytes_from_int(0x0B432B2677937381AEF05BB02A66ECD012773062CF3FA2549E44F58ED2401710)
81 82 # Need to negate this seckey before signing
83 x = int_from_bytes(seckey)
84 P = point_mul(G, x)
85 assert (y(P) % 2 != 0)
86 87 msg = bytes_from_int(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF)
88 aux_rand = bytes_from_int(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF)
89 90 sig = schnorr_sign(msg, seckey, aux_rand)
91 return seckey, pubkey_gen(seckey), aux_rand, msg, sig, "TRUE", "test fails if msg is reduced modulo p or n"
92 93 94 # Signs with a given nonce. This can be INSECURE and is only INTENDED FOR
95 # GENERATING TEST VECTORS. Results in an invalid signature if y(kG) is not
96 # even.
97 def insecure_schnorr_sign_fixed_nonce(msg, seckey0, k):
98 if len(msg) != 32:
99 raise ValueError('The message must be a 32-byte array.')
100 seckey0 = int_from_bytes(seckey0)
101 if not (1 <= seckey0 <= n - 1):
102 raise ValueError('The secret key must be an integer in the range 1..n-1.')
103 P = point_mul(G, seckey0)
104 seckey = seckey0 if has_even_y(P) else n - seckey0
105 R = point_mul(G, k)
106 e = int_from_bytes(tagged_hash("BIP0340/challenge", bytes_from_point(R) + bytes_from_point(P) + msg)) % n
107 return bytes_from_point(R) + bytes_from_int((k + e * seckey) % n)
108 109 110 # Creates a singature with a small x(R) by using k = -1/2
111 def vector4():
112 one_half = n - 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0
113 seckey = bytes_from_int(0x763758E5CBEEDEE4F7D3FC86F531C36578933228998226672F13C4F0EBE855EB)
114 msg = bytes_from_int(0x4DF3C3F68FCC83B27E9D42C90431A72499F17875C81A599B566C9889B9696703)
115 sig = insecure_schnorr_sign_fixed_nonce(msg, seckey, one_half)
116 return None, pubkey_gen(seckey), None, msg, sig, "TRUE", None
117 118 119 default_seckey = bytes_from_int(0xB7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF)
120 default_msg = bytes_from_int(0x243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89)
121 default_aux_rand = bytes_from_int(0xC87AA53824B4D7AE2EB035A2B5BBBCCC080E76CDC6D1692C4B0B62D798E6D906)
122 123 124 # Public key is not on the curve
125 def vector5():
126 # This creates a dummy signature that doesn't have anything to do with the
127 # public key.
128 seckey = default_seckey
129 msg = default_msg
130 sig = schnorr_sign(msg, seckey, default_aux_rand)
131 132 pubkey = bytes_from_int(0xEEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34)
133 assert (lift_x(pubkey) is None)
134 135 return None, pubkey, None, msg, sig, "FALSE", "public key not on the curve"
136 137 138 def vector6():
139 seckey = default_seckey
140 msg = default_msg
141 k = 6
142 sig = insecure_schnorr_sign_fixed_nonce(msg, seckey, k)
143 144 # Y coordinate of R is not even
145 R = point_mul(G, k)
146 assert (not has_even_y(R))
147 148 return None, pubkey_gen(seckey), None, msg, sig, "FALSE", "has_even_y(R) is false"
149 150 151 def vector7():
152 seckey = default_seckey
153 msg = int_from_bytes(default_msg)
154 neg_msg = bytes_from_int(n - msg)
155 sig = schnorr_sign(neg_msg, seckey, default_aux_rand)
156 return None, pubkey_gen(seckey), None, bytes_from_int(msg), sig, "FALSE", "negated message"
157 158 159 def vector8():
160 seckey = default_seckey
161 msg = default_msg
162 sig = schnorr_sign(msg, seckey, default_aux_rand)
163 sig = sig[0:32] + bytes_from_int(n - int_from_bytes(sig[32:64]))
164 return None, pubkey_gen(seckey), None, msg, sig, "FALSE", "negated s value"
165 166 167 def bytes_from_point_inf0(P):
168 if P is None:
169 return bytes_from_int(0)
170 return bytes_from_int(P[0])
171 172 173 def vector9():
174 seckey = default_seckey
175 msg = default_msg
176 177 # Override bytes_from_point in schnorr_sign to allow creating a signature
178 # with k = 0.
179 k = 0
180 bytes_from_point_tmp = bytes_from_point.__code__
181 bytes_from_point.__code__ = bytes_from_point_inf0.__code__
182 sig = insecure_schnorr_sign_fixed_nonce(msg, seckey, k)
183 bytes_from_point.__code__ = bytes_from_point_tmp
184 185 return (None, pubkey_gen(seckey), None, msg, sig, "FALSE",
186 "sG - eP is infinite. Test fails in single verification if has_even_y(inf) is defined as true and x(inf) as 0")
187 188 189 def bytes_from_point_inf1(P):
190 if P == None:
191 return bytes_from_int(1)
192 return bytes_from_int(P[0])
193 194 195 def vector10():
196 seckey = default_seckey
197 msg = default_msg
198 199 # Override bytes_from_point in schnorr_sign to allow creating a signature
200 # with k = 0.
201 k = 0
202 bytes_from_point_tmp = bytes_from_point.__code__
203 bytes_from_point.__code__ = bytes_from_point_inf1.__code__
204 sig = insecure_schnorr_sign_fixed_nonce(msg, seckey, k)
205 bytes_from_point.__code__ = bytes_from_point_tmp
206 207 return (None, pubkey_gen(seckey), None, msg, sig, "FALSE",
208 "sG - eP is infinite. Test fails in single verification if has_even_y(inf) is defined as true and x(inf) as 1")
209 210 211 # It's cryptographically impossible to create a test vector that fails if run
212 # in an implementation which merely misses the check that sig[0:32] is an X
213 # coordinate on the curve. This test vector just increases test coverage.
214 def vector11():
215 seckey = default_seckey
216 msg = default_msg
217 sig = schnorr_sign(msg, seckey, default_aux_rand)
218 219 # Replace R's X coordinate with an X coordinate that's not on the curve
220 x_not_on_curve = bytes_from_int(0x4A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269BC70A74F8220429BA1D)
221 assert (lift_x(x_not_on_curve) is None)
222 sig = x_not_on_curve + sig[32:64]
223 224 return None, pubkey_gen(seckey), None, msg, sig, "FALSE", "sig[0:32] is not an X coordinate on the curve"
225 226 227 # It's cryptographically impossible to create a test vector that fails if run
228 # in an implementation which merely misses the check that sig[0:32] is smaller
229 # than the field size. This test vector just increases test coverage.
230 def vector12():
231 seckey = default_seckey
232 msg = default_msg
233 sig = schnorr_sign(msg, seckey, default_aux_rand)
234 235 # Replace R's X coordinate with an X coordinate that's equal to field size
236 sig = bytes_from_int(p) + sig[32:64]
237 238 return None, pubkey_gen(seckey), None, msg, sig, "FALSE", "sig[0:32] is equal to field size"
239 240 241 # It's cryptographically impossible to create a test vector that fails if run
242 # in an implementation which merely misses the check that sig[32:64] is smaller
243 # than the curve order. This test vector just increases test coverage.
244 def vector13():
245 seckey = default_seckey
246 msg = default_msg
247 sig = schnorr_sign(msg, seckey, default_aux_rand)
248 249 # Replace s with a number that's equal to the curve order
250 sig = sig[0:32] + bytes_from_int(n)
251 252 return None, pubkey_gen(seckey), None, msg, sig, "FALSE", "sig[32:64] is equal to curve order"
253 254 255 # Test out of range pubkey
256 # It's cryptographically impossible to create a test vector that fails if run
257 # in an implementation which accepts out of range pubkeys because we can't find
258 # a secret key for such a public key and therefore can not create a signature.
259 # This test vector just increases test coverage.
260 def vector14():
261 # This creates a dummy signature that doesn't have anything to do with the
262 # public key.
263 seckey = default_seckey
264 msg = default_msg
265 sig = schnorr_sign(msg, seckey, default_aux_rand)
266 pubkey_int = p + 1
267 pubkey = bytes_from_int(pubkey_int)
268 assert (lift_x(pubkey) is None)
269 # If an implementation would reduce a given public key modulo p then the
270 # pubkey would be valid
271 assert (lift_x(bytes_from_int(pubkey_int % p)) is not None)
272 273 return (
274 None, pubkey, None, msg, sig, "FALSE", "public key is not a valid X coordinate because it exceeds the field size")
275 276 277 def varlen_vector(msg_int):
278 seckey = bytes_from_int(int(16 * "0340", 16))
279 pubkey = pubkey_gen(seckey)
280 aux_rand = bytes_from_int(0)
281 msg = msg_int.to_bytes((msg_int.bit_length() + 7) // 8, "big")
282 sig = schnorr_sign(msg, seckey, aux_rand)
283 comment = "message of size %d (added 2022-12)"
284 return seckey, pubkey, aux_rand, msg, sig, "TRUE", comment % len(msg)
285 286 287 vector15 = lambda: varlen_vector(0)
288 vector16 = lambda: varlen_vector(0x11)
289 vector17 = lambda: varlen_vector(0x0102030405060708090A0B0C0D0E0F1011)
290 vector18 = lambda: varlen_vector(int(100 * "99", 16))
291 292 vectors = [
293 vector0(),
294 vector1(),
295 vector2(),
296 vector3(),
297 vector4(),
298 vector5(),
299 vector6(),
300 vector7(),
301 vector8(),
302 vector9(),
303 vector10(),
304 vector11(),
305 vector12(),
306 vector13(),
307 vector14(),
308 vector15(),
309 vector16(),
310 vector17(),
311 vector18(),
312 ]
313 314 315 # Converts the byte strings of a test vector into hex strings
316 def bytes_to_hex(seckey, pubkey, aux_rand, msg, sig, result, comment):
317 return (seckey.hex().upper() if seckey is not None else None, pubkey.hex().upper(),
318 aux_rand.hex().upper() if aux_rand is not None else None, msg.hex().upper(), sig.hex().upper(), result,
319 comment)
320 321 322 vectors = list(
323 map(lambda vector: bytes_to_hex(vector[0], vector[1], vector[2], vector[3], vector[4], vector[5], vector[6]),
324 vectors))
325 326 327 def print_csv(vectors):
328 writer = csv.writer(sys.stdout)
329 writer.writerow(
330 ("index", "secret key", "public key", "aux_rand", "message", "signature", "verification result", "comment"))
331 for (i, v) in enumerate(vectors):
332 writer.writerow((i,) + v)
333 334 335 print_csv(vectors)
336