key.py raw
1 # Copyright (c) 2019-2020 Pieter Wuille
2 # Distributed under the MIT software license, see the accompanying
3 # file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 """Test-only secp256k1 elliptic curve protocols implementation
5
6 WARNING: This code is slow, uses bad randomness, does not properly protect
7 keys, and is trivially vulnerable to side channel attacks. Do not use for
8 anything but tests."""
9 import csv
10 import hashlib
11 import hmac
12 import os
13 import random
14 import unittest
15
16 from test_framework.crypto import secp256k1
17 from test_framework.util import assert_equal, assert_not_equal, random_bitflip
18
19 # Point with no known discrete log.
20 H_POINT = "50929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0"
21
22 # Order of the secp256k1 curve
23 ORDER = secp256k1.GE.ORDER
24
25 def TaggedHash(tag, data):
26 ss = hashlib.sha256(tag.encode('utf-8')).digest()
27 ss += ss
28 ss += data
29 return hashlib.sha256(ss).digest()
30
31
32 class ECPubKey:
33 """A secp256k1 public key"""
34
35 def __init__(self):
36 """Construct an uninitialized public key"""
37 self.p = None
38
39 def set(self, data):
40 """Construct a public key from a serialization in compressed or uncompressed format"""
41 self.p = secp256k1.GE.from_bytes(data)
42 self.compressed = len(data) == 33
43
44 @property
45 def is_compressed(self):
46 return self.compressed
47
48 @property
49 def is_valid(self):
50 return self.p is not None
51
52 def get_bytes(self):
53 assert self.is_valid
54 if self.compressed:
55 return self.p.to_bytes_compressed()
56 else:
57 return self.p.to_bytes_uncompressed()
58
59 def verify_ecdsa(self, sig, msg, low_s=True):
60 """Verify a strictly DER-encoded ECDSA signature against this pubkey.
61
62 See https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm for the
63 ECDSA verifier algorithm"""
64 assert self.is_valid
65
66 # Extract r and s from the DER formatted signature. Return false for
67 # any DER encoding errors.
68 if (sig[1] + 2 != len(sig)):
69 return False
70 if (len(sig) < 4):
71 return False
72 if (sig[0] != 0x30):
73 return False
74 if (sig[2] != 0x02):
75 return False
76 rlen = sig[3]
77 if (len(sig) < 6 + rlen):
78 return False
79 if rlen < 1 or rlen > 33:
80 return False
81 if sig[4] >= 0x80:
82 return False
83 if (rlen > 1 and (sig[4] == 0) and not (sig[5] & 0x80)):
84 return False
85 r = int.from_bytes(sig[4:4+rlen], 'big')
86 if (sig[4+rlen] != 0x02):
87 return False
88 slen = sig[5+rlen]
89 if slen < 1 or slen > 33:
90 return False
91 if (len(sig) != 6 + rlen + slen):
92 return False
93 if sig[6+rlen] >= 0x80:
94 return False
95 if (slen > 1 and (sig[6+rlen] == 0) and not (sig[7+rlen] & 0x80)):
96 return False
97 s = int.from_bytes(sig[6+rlen:6+rlen+slen], 'big')
98
99 # Verify that r and s are within the group order
100 if r < 1 or s < 1 or r >= ORDER or s >= ORDER:
101 return False
102 if low_s and s >= secp256k1.GE.ORDER_HALF:
103 return False
104 z = int.from_bytes(msg, 'big')
105
106 # Run verifier algorithm on r, s
107 w = pow(s, -1, ORDER)
108 R = secp256k1.GE.mul((z * w, secp256k1.G), (r * w, self.p))
109 if R.infinity or (int(R.x) % ORDER) != r:
110 return False
111 return True
112
113 def generate_privkey():
114 """Generate a valid random 32-byte private key."""
115 return random.randrange(1, ORDER).to_bytes(32, 'big')
116
117 def rfc6979_nonce(key):
118 """Compute signing nonce using RFC6979."""
119 v = bytes([1] * 32)
120 k = bytes([0] * 32)
121 k = hmac.new(k, v + b"\x00" + key, 'sha256').digest()
122 v = hmac.new(k, v, 'sha256').digest()
123 k = hmac.new(k, v + b"\x01" + key, 'sha256').digest()
124 v = hmac.new(k, v, 'sha256').digest()
125 return hmac.new(k, v, 'sha256').digest()
126
127 class ECKey:
128 """A secp256k1 private key"""
129
130 def __init__(self):
131 self.valid = False
132
133 def set(self, secret, compressed):
134 """Construct a private key object with given 32-byte secret and compressed flag."""
135 assert_equal(len(secret), 32)
136 secret = int.from_bytes(secret, 'big')
137 self.valid = (secret > 0 and secret < ORDER)
138 if self.valid:
139 self.secret = secret
140 self.compressed = compressed
141
142 def generate(self, compressed=True):
143 """Generate a random private key (compressed or uncompressed)."""
144 self.set(generate_privkey(), compressed)
145
146 def get_bytes(self):
147 """Retrieve the 32-byte representation of this key."""
148 assert self.valid
149 return self.secret.to_bytes(32, 'big')
150
151 @property
152 def is_valid(self):
153 return self.valid
154
155 @property
156 def is_compressed(self):
157 return self.compressed
158
159 def get_pubkey(self):
160 """Compute an ECPubKey object for this secret key."""
161 assert self.valid
162 ret = ECPubKey()
163 ret.p = self.secret * secp256k1.G
164 ret.compressed = self.compressed
165 return ret
166
167 def sign_ecdsa(self, msg, low_s=True, rfc6979=False):
168 """Construct a DER-encoded ECDSA signature with this key.
169
170 See https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm for the
171 ECDSA signer algorithm."""
172 assert self.valid
173 z = int.from_bytes(msg, 'big')
174 # Note: no RFC6979 by default, but a simple random nonce (some tests rely on distinct transactions for the same operation)
175 if rfc6979:
176 k = int.from_bytes(rfc6979_nonce(self.secret.to_bytes(32, 'big') + msg), 'big')
177 else:
178 k = random.randrange(1, ORDER)
179 R = k * secp256k1.G
180 r = int(R.x) % ORDER
181 s = (pow(k, -1, ORDER) * (z + self.secret * r)) % ORDER
182 if low_s and s > secp256k1.GE.ORDER_HALF:
183 s = ORDER - s
184 # Represent in DER format. The byte representations of r and s have
185 # length rounded up (255 bits becomes 32 bytes and 256 bits becomes 33
186 # bytes).
187 rb = r.to_bytes((r.bit_length() + 8) // 8, 'big')
188 sb = s.to_bytes((s.bit_length() + 8) // 8, 'big')
189 return b'\x30' + bytes([4 + len(rb) + len(sb), 2, len(rb)]) + rb + bytes([2, len(sb)]) + sb
190
191 def compute_xonly_pubkey(key):
192 """Compute an x-only (32 byte) public key from a (32 byte) private key.
193
194 This also returns whether the resulting public key was negated.
195 """
196
197 assert_equal(len(key), 32)
198 x = int.from_bytes(key, 'big')
199 if x == 0 or x >= ORDER:
200 return (None, None)
201 P = x * secp256k1.G
202 return (P.to_bytes_xonly(), not P.y.is_even())
203
204 def tweak_add_privkey(key, tweak):
205 """Tweak a private key (after negating it if needed)."""
206
207 assert_equal(len(key), 32)
208 assert_equal(len(tweak), 32)
209
210 x = int.from_bytes(key, 'big')
211 if x == 0 or x >= ORDER:
212 return None
213 if not (x * secp256k1.G).y.is_even():
214 x = ORDER - x
215 t = int.from_bytes(tweak, 'big')
216 if t >= ORDER:
217 return None
218 x = (x + t) % ORDER
219 if x == 0:
220 return None
221 return x.to_bytes(32, 'big')
222
223 def tweak_add_pubkey(key, tweak):
224 """Tweak a public key and return whether the result had to be negated."""
225
226 assert_equal(len(key), 32)
227 assert_equal(len(tweak), 32)
228
229 P = secp256k1.GE.from_bytes_xonly(key)
230 if P is None:
231 return None
232 t = int.from_bytes(tweak, 'big')
233 if t >= ORDER:
234 return None
235 Q = t * secp256k1.G + P
236 if Q.infinity:
237 return None
238 return (Q.to_bytes_xonly(), not Q.y.is_even())
239
240 def verify_schnorr(key, sig, msg):
241 """Verify a Schnorr signature (see BIP 340).
242
243 - key is a 32-byte xonly pubkey (computed using compute_xonly_pubkey).
244 - sig is a 64-byte Schnorr signature
245 - msg is a variable-length message
246 """
247 assert_equal(len(key), 32)
248 assert_equal(len(sig), 64)
249
250 P = secp256k1.GE.from_bytes_xonly(key)
251 if P is None:
252 return False
253 r = int.from_bytes(sig[0:32], 'big')
254 if r >= secp256k1.FE.SIZE:
255 return False
256 s = int.from_bytes(sig[32:64], 'big')
257 if s >= ORDER:
258 return False
259 e = int.from_bytes(TaggedHash("BIP0340/challenge", sig[0:32] + key + msg), 'big') % ORDER
260 R = secp256k1.GE.mul((s, secp256k1.G), (-e, P))
261 if R.infinity or not R.y.is_even():
262 return False
263 if r != R.x:
264 return False
265 return True
266
267 def sign_schnorr(key, msg, aux=None, flip_p=False, flip_r=False):
268 """Create a Schnorr signature (see BIP 340)."""
269
270 if aux is None:
271 aux = bytes(32)
272
273 assert_equal(len(key), 32)
274 assert_equal(len(aux), 32)
275
276 sec = int.from_bytes(key, 'big')
277 if sec == 0 or sec >= ORDER:
278 return None
279 P = sec * secp256k1.G
280 if P.y.is_even() == flip_p:
281 sec = ORDER - sec
282 t = (sec ^ int.from_bytes(TaggedHash("BIP0340/aux", aux), 'big')).to_bytes(32, 'big')
283 kp = int.from_bytes(TaggedHash("BIP0340/nonce", t + P.to_bytes_xonly() + msg), 'big') % ORDER
284 assert_not_equal(kp, 0)
285 R = kp * secp256k1.G
286 k = kp if R.y.is_even() != flip_r else ORDER - kp
287 e = int.from_bytes(TaggedHash("BIP0340/challenge", R.to_bytes_xonly() + P.to_bytes_xonly() + msg), 'big') % ORDER
288 return R.to_bytes_xonly() + ((k + e * sec) % ORDER).to_bytes(32, 'big')
289
290
291 class TestFrameworkKey(unittest.TestCase):
292 def test_ecdsa_and_schnorr(self):
293 """Test the Python ECDSA and Schnorr implementations."""
294 byte_arrays = [generate_privkey() for _ in range(3)] + [v.to_bytes(32, 'big') for v in [0, ORDER - 1, ORDER, 2**256 - 1]]
295 keys = {}
296 for privkey_bytes in byte_arrays: # build array of key/pubkey pairs
297 privkey = ECKey()
298 privkey.set(privkey_bytes, compressed=True)
299 if privkey.is_valid:
300 keys[privkey] = privkey.get_pubkey()
301 for msg in byte_arrays: # test every combination of message, signing key, verification key
302 for sign_privkey, _ in keys.items():
303 sig_ecdsa = sign_privkey.sign_ecdsa(msg)
304 sig_schnorr = sign_schnorr(sign_privkey.get_bytes(), msg)
305 for verify_privkey, verify_pubkey in keys.items():
306 verify_xonly_pubkey = verify_pubkey.get_bytes()[1:]
307 if verify_privkey == sign_privkey:
308 self.assertTrue(verify_pubkey.verify_ecdsa(sig_ecdsa, msg))
309 self.assertTrue(verify_schnorr(verify_xonly_pubkey, sig_schnorr, msg))
310 sig_ecdsa = random_bitflip(sig_ecdsa) # damaging signature should break things
311 sig_schnorr = random_bitflip(sig_schnorr)
312 self.assertFalse(verify_pubkey.verify_ecdsa(sig_ecdsa, msg))
313 self.assertFalse(verify_schnorr(verify_xonly_pubkey, sig_schnorr, msg))
314
315 def test_schnorr_testvectors(self):
316 """Implement the BIP340 test vectors (read from bip340_test_vectors.csv)."""
317 num_tests = 0
318 vectors_file = os.path.join(os.path.dirname(os.path.realpath(__file__)), 'bip340_test_vectors.csv')
319 with open(vectors_file, newline='') as csvfile:
320 reader = csv.reader(csvfile)
321 next(reader)
322 for row in reader:
323 (i_str, seckey_hex, pubkey_hex, aux_rand_hex, msg_hex, sig_hex, result_str, comment) = row
324 i = int(i_str)
325 pubkey = bytes.fromhex(pubkey_hex)
326 msg = bytes.fromhex(msg_hex)
327 sig = bytes.fromhex(sig_hex)
328 result = result_str == 'TRUE'
329 if seckey_hex != '':
330 seckey = bytes.fromhex(seckey_hex)
331 pubkey_actual = compute_xonly_pubkey(seckey)[0]
332 self.assertEqual(pubkey.hex(), pubkey_actual.hex(), "BIP340 test vector %i (%s): pubkey mismatch" % (i, comment))
333 aux_rand = bytes.fromhex(aux_rand_hex)
334 try:
335 sig_actual = sign_schnorr(seckey, msg, aux_rand)
336 self.assertEqual(sig.hex(), sig_actual.hex(), "BIP340 test vector %i (%s): sig mismatch" % (i, comment))
337 except RuntimeError as e:
338 self.fail("BIP340 test vector %i (%s): signing raised exception %s" % (i, comment, e))
339 result_actual = verify_schnorr(pubkey, sig, msg)
340 if result:
341 self.assertEqual(result, result_actual, "BIP340 test vector %i (%s): verification failed" % (i, comment))
342 else:
343 self.assertEqual(result, result_actual, "BIP340 test vector %i (%s): verification succeeded unexpectedly" % (i, comment))
344 num_tests += 1
345 self.assertTrue(num_tests >= 15) # expect at least 15 test vectors
346