Inside Bitcoin

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
6WARNING: This code is slow, uses bad randomness, does not properly protect
7keys, and is trivially vulnerable to side channel attacks. Do not use for
8anything but tests."""
9import csv
10import hashlib
11import hmac
12import os
13import random
14import unittest
15
16from test_framework.crypto import secp256k1
17from test_framework.util import assert_equal, assert_not_equal, random_bitflip
18
19# Point with no known discrete log.
20H_POINT = "50929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0"
21
22# Order of the secp256k1 curve
23ORDER = secp256k1.GE.ORDER
24
25def 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
32class 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
113def generate_privkey():
114    """Generate a valid random 32-byte private key."""
115    return random.randrange(1, ORDER).to_bytes(32, 'big')
116
117def 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
127class 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
191def 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
204def 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
223def 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
240def 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)