Projects : bitcoin : bitcoin_dumpblock_no_losers
1 | // Copyright (c) 2009-2010 Satoshi Nakamoto |
2 | // Copyright (c) 2009-2012 The Bitcoin developers |
3 | // Distributed under the MIT/X11 software license, see the accompanying |
4 | // file license.txt or http://www.opensource.org/licenses/mit-license.php. |
5 | #ifndef BITCOIN_KEY_H |
6 | #define BITCOIN_KEY_H |
7 | |
8 | #include <stdexcept> |
9 | #include <vector> |
10 | |
11 | #include <openssl/ec.h> |
12 | #include <openssl/ecdsa.h> |
13 | #include <openssl/obj_mac.h> |
14 | |
15 | #include "serialize.h" |
16 | #include "uint256.h" |
17 | |
18 | // secp160k1 |
19 | // const unsigned int PRIVATE_KEY_SIZE = 192; |
20 | // const unsigned int PUBLIC_KEY_SIZE = 41; |
21 | // const unsigned int SIGNATURE_SIZE = 48; |
22 | // |
23 | // secp192k1 |
24 | // const unsigned int PRIVATE_KEY_SIZE = 222; |
25 | // const unsigned int PUBLIC_KEY_SIZE = 49; |
26 | // const unsigned int SIGNATURE_SIZE = 57; |
27 | // |
28 | // secp224k1 |
29 | // const unsigned int PRIVATE_KEY_SIZE = 250; |
30 | // const unsigned int PUBLIC_KEY_SIZE = 57; |
31 | // const unsigned int SIGNATURE_SIZE = 66; |
32 | // |
33 | // secp256k1: |
34 | // const unsigned int PRIVATE_KEY_SIZE = 279; |
35 | // const unsigned int PUBLIC_KEY_SIZE = 65; |
36 | // const unsigned int SIGNATURE_SIZE = 72; |
37 | // |
38 | // see www.keylength.com |
39 | // script supports up to 75 for single byte push |
40 | |
41 | // Generate a private key from just the secret parameter |
42 | int static inline EC_KEY_regenerate_key(EC_KEY *eckey, BIGNUM *priv_key) |
43 | { |
44 | int ok = 0; |
45 | BN_CTX *ctx = NULL; |
46 | EC_POINT *pub_key = NULL; |
47 | |
48 | if (!eckey) return 0; |
49 | |
50 | const EC_GROUP *group = EC_KEY_get0_group(eckey); |
51 | |
52 | if ((ctx = BN_CTX_new()) == NULL) |
53 | goto err; |
54 | |
55 | pub_key = EC_POINT_new(group); |
56 | |
57 | if (pub_key == NULL) |
58 | goto err; |
59 | |
60 | if (!EC_POINT_mul(group, pub_key, priv_key, NULL, NULL, ctx)) |
61 | goto err; |
62 | |
63 | EC_KEY_set_private_key(eckey,priv_key); |
64 | EC_KEY_set_public_key(eckey,pub_key); |
65 | |
66 | ok = 1; |
67 | |
68 | err: |
69 | |
70 | if (pub_key) |
71 | EC_POINT_free(pub_key); |
72 | if (ctx != NULL) |
73 | BN_CTX_free(ctx); |
74 | |
75 | return(ok); |
76 | } |
77 | |
78 | // Perform ECDSA key recovery (see SEC1 4.1.6) for curves over (mod p)-fields |
79 | // recid selects which key is recovered |
80 | // if check is nonzero, additional checks are performed |
81 | int static inline ECDSA_SIG_recover_key_GFp(EC_KEY *eckey, ECDSA_SIG *ecsig, const unsigned char *msg, int msglen, int recid, int check) |
82 | { |
83 | if (!eckey) return 0; |
84 | |
85 | int ret = 0; |
86 | BN_CTX *ctx = NULL; |
87 | |
88 | BIGNUM *x = NULL; |
89 | BIGNUM *e = NULL; |
90 | BIGNUM *order = NULL; |
91 | BIGNUM *sor = NULL; |
92 | BIGNUM *eor = NULL; |
93 | BIGNUM *field = NULL; |
94 | EC_POINT *R = NULL; |
95 | EC_POINT *O = NULL; |
96 | EC_POINT *Q = NULL; |
97 | BIGNUM *rr = NULL; |
98 | BIGNUM *zero = NULL; |
99 | int n = 0; |
100 | int i = recid / 2; |
101 | |
102 | const EC_GROUP *group = EC_KEY_get0_group(eckey); |
103 | if ((ctx = BN_CTX_new()) == NULL) { ret = -1; goto err; } |
104 | BN_CTX_start(ctx); |
105 | order = BN_CTX_get(ctx); |
106 | if (!EC_GROUP_get_order(group, order, ctx)) { ret = -2; goto err; } |
107 | x = BN_CTX_get(ctx); |
108 | if (!BN_copy(x, order)) { ret=-1; goto err; } |
109 | if (!BN_mul_word(x, i)) { ret=-1; goto err; } |
110 | if (!BN_add(x, x, ecsig->r)) { ret=-1; goto err; } |
111 | field = BN_CTX_get(ctx); |
112 | if (!EC_GROUP_get_curve_GFp(group, field, NULL, NULL, ctx)) { ret=-2; goto err; } |
113 | if (BN_cmp(x, field) >= 0) { ret=0; goto err; } |
114 | if ((R = EC_POINT_new(group)) == NULL) { ret = -2; goto err; } |
115 | if (!EC_POINT_set_compressed_coordinates_GFp(group, R, x, recid % 2, ctx)) { ret=0; goto err; } |
116 | if (check) |
117 | { |
118 | if ((O = EC_POINT_new(group)) == NULL) { ret = -2; goto err; } |
119 | if (!EC_POINT_mul(group, O, NULL, R, order, ctx)) { ret=-2; goto err; } |
120 | if (!EC_POINT_is_at_infinity(group, O)) { ret = 0; goto err; } |
121 | } |
122 | if ((Q = EC_POINT_new(group)) == NULL) { ret = -2; goto err; } |
123 | n = EC_GROUP_get_degree(group); |
124 | e = BN_CTX_get(ctx); |
125 | if (!BN_bin2bn(msg, msglen, e)) { ret=-1; goto err; } |
126 | if (8*msglen > n) BN_rshift(e, e, 8-(n & 7)); |
127 | zero = BN_CTX_get(ctx); |
128 | if (!BN_zero(zero)) { ret=-1; goto err; } |
129 | if (!BN_mod_sub(e, zero, e, order, ctx)) { ret=-1; goto err; } |
130 | rr = BN_CTX_get(ctx); |
131 | if (!BN_mod_inverse(rr, ecsig->r, order, ctx)) { ret=-1; goto err; } |
132 | sor = BN_CTX_get(ctx); |
133 | if (!BN_mod_mul(sor, ecsig->s, rr, order, ctx)) { ret=-1; goto err; } |
134 | eor = BN_CTX_get(ctx); |
135 | if (!BN_mod_mul(eor, e, rr, order, ctx)) { ret=-1; goto err; } |
136 | if (!EC_POINT_mul(group, Q, eor, R, sor, ctx)) { ret=-2; goto err; } |
137 | if (!EC_KEY_set_public_key(eckey, Q)) { ret=-2; goto err; } |
138 | |
139 | ret = 1; |
140 | |
141 | err: |
142 | if (ctx) { |
143 | BN_CTX_end(ctx); |
144 | BN_CTX_free(ctx); |
145 | } |
146 | if (R != NULL) EC_POINT_free(R); |
147 | if (O != NULL) EC_POINT_free(O); |
148 | if (Q != NULL) EC_POINT_free(Q); |
149 | return ret; |
150 | } |
151 | |
152 | class key_error : public std::runtime_error |
153 | { |
154 | public: |
155 | explicit key_error(const std::string& str) : std::runtime_error(str) {} |
156 | }; |
157 | |
158 | |
159 | // secure_allocator is defined in serialize.h |
160 | // CPrivKey is a serialized private key, with all parameters included (279 bytes) |
161 | typedef std::vector<unsigned char, secure_allocator<unsigned char> > CPrivKey; |
162 | // CSecret is a serialization of just the secret parameter (32 bytes) |
163 | typedef std::vector<unsigned char, secure_allocator<unsigned char> > CSecret; |
164 | |
165 | class CKey |
166 | { |
167 | protected: |
168 | EC_KEY* pkey; |
169 | bool fSet; |
170 | |
171 | public: |
172 | CKey() |
173 | { |
174 | pkey = EC_KEY_new_by_curve_name(NID_secp256k1); |
175 | if (pkey == NULL) |
176 | throw key_error("CKey::CKey() : EC_KEY_new_by_curve_name failed"); |
177 | fSet = false; |
178 | } |
179 | |
180 | CKey(const CKey& b) |
181 | { |
182 | pkey = EC_KEY_dup(b.pkey); |
183 | if (pkey == NULL) |
184 | throw key_error("CKey::CKey(const CKey&) : EC_KEY_dup failed"); |
185 | fSet = b.fSet; |
186 | } |
187 | |
188 | CKey& operator=(const CKey& b) |
189 | { |
190 | if (!EC_KEY_copy(pkey, b.pkey)) |
191 | throw key_error("CKey::operator=(const CKey&) : EC_KEY_copy failed"); |
192 | fSet = b.fSet; |
193 | return (*this); |
194 | } |
195 | |
196 | ~CKey() |
197 | { |
198 | EC_KEY_free(pkey); |
199 | } |
200 | |
201 | bool IsNull() const |
202 | { |
203 | return !fSet; |
204 | } |
205 | |
206 | void MakeNewKey() |
207 | { |
208 | if (!EC_KEY_generate_key(pkey)) |
209 | throw key_error("CKey::MakeNewKey() : EC_KEY_generate_key failed"); |
210 | fSet = true; |
211 | } |
212 | |
213 | bool SetPrivKey(const CPrivKey& vchPrivKey) |
214 | { |
215 | const unsigned char* pbegin = &vchPrivKey[0]; |
216 | if (!d2i_ECPrivateKey(&pkey, &pbegin, vchPrivKey.size())) |
217 | return false; |
218 | fSet = true; |
219 | return true; |
220 | } |
221 | |
222 | bool SetSecret(const CSecret& vchSecret) |
223 | { |
224 | EC_KEY_free(pkey); |
225 | pkey = EC_KEY_new_by_curve_name(NID_secp256k1); |
226 | if (pkey == NULL) |
227 | throw key_error("CKey::SetSecret() : EC_KEY_new_by_curve_name failed"); |
228 | if (vchSecret.size() != 32) |
229 | throw key_error("CKey::SetSecret() : secret must be 32 bytes"); |
230 | BIGNUM *bn = BN_bin2bn(&vchSecret[0],32,BN_new()); |
231 | if (bn == NULL) |
232 | throw key_error("CKey::SetSecret() : BN_bin2bn failed"); |
233 | if (!EC_KEY_regenerate_key(pkey,bn)) |
234 | { |
235 | BN_clear_free(bn); |
236 | throw key_error("CKey::SetSecret() : EC_KEY_regenerate_key failed"); |
237 | } |
238 | BN_clear_free(bn); |
239 | fSet = true; |
240 | return true; |
241 | } |
242 | |
243 | CSecret GetSecret() const |
244 | { |
245 | CSecret vchRet; |
246 | vchRet.resize(32); |
247 | const BIGNUM *bn = EC_KEY_get0_private_key(pkey); |
248 | int nBytes = BN_num_bytes(bn); |
249 | if (bn == NULL) |
250 | throw key_error("CKey::GetSecret() : EC_KEY_get0_private_key failed"); |
251 | int n=BN_bn2bin(bn,&vchRet[32 - nBytes]); |
252 | if (n != nBytes) |
253 | throw key_error("CKey::GetSecret(): BN_bn2bin failed"); |
254 | return vchRet; |
255 | } |
256 | |
257 | CPrivKey GetPrivKey() const |
258 | { |
259 | unsigned int nSize = i2d_ECPrivateKey(pkey, NULL); |
260 | if (!nSize) |
261 | throw key_error("CKey::GetPrivKey() : i2d_ECPrivateKey failed"); |
262 | CPrivKey vchPrivKey(nSize, 0); |
263 | unsigned char* pbegin = &vchPrivKey[0]; |
264 | if (i2d_ECPrivateKey(pkey, &pbegin) != nSize) |
265 | throw key_error("CKey::GetPrivKey() : i2d_ECPrivateKey returned unexpected size"); |
266 | return vchPrivKey; |
267 | } |
268 | |
269 | bool SetPubKey(const std::vector<unsigned char>& vchPubKey) |
270 | { |
271 | const unsigned char* pbegin = &vchPubKey[0]; |
272 | if (!o2i_ECPublicKey(&pkey, &pbegin, vchPubKey.size())) |
273 | return false; |
274 | fSet = true; |
275 | return true; |
276 | } |
277 | |
278 | std::vector<unsigned char> GetPubKey() const |
279 | { |
280 | unsigned int nSize = i2o_ECPublicKey(pkey, NULL); |
281 | if (!nSize) |
282 | throw key_error("CKey::GetPubKey() : i2o_ECPublicKey failed"); |
283 | std::vector<unsigned char> vchPubKey(nSize, 0); |
284 | unsigned char* pbegin = &vchPubKey[0]; |
285 | if (i2o_ECPublicKey(pkey, &pbegin) != nSize) |
286 | throw key_error("CKey::GetPubKey() : i2o_ECPublicKey returned unexpected size"); |
287 | return vchPubKey; |
288 | } |
289 | |
290 | bool Sign(uint256 hash, std::vector<unsigned char>& vchSig) |
291 | { |
292 | vchSig.clear(); |
293 | ECDSA_SIG *sig = ECDSA_do_sign((unsigned char *) &hash, sizeof(hash), pkey); |
294 | |
295 | if (sig == NULL) |
296 | { |
297 | printf("ERROR, ECDSA_sign failed in key.h:Sign()\n"); |
298 | return false; |
299 | } |
300 | |
301 | BN_CTX *ctx = BN_CTX_new(); |
302 | BN_CTX_start(ctx); |
303 | const EC_GROUP *group = EC_KEY_get0_group(pkey); |
304 | BIGNUM *order = BN_CTX_get(ctx); |
305 | BIGNUM *halforder = BN_CTX_get(ctx); |
306 | EC_GROUP_get_order(group, order, ctx); |
307 | BN_rshift1(halforder, order); |
308 | |
309 | if (fHighS && (BN_cmp(sig->s, halforder) < 0)) |
310 | { |
311 | // enforce high S values |
312 | BN_sub(sig->s, order, sig->s); |
313 | } |
314 | |
315 | if (fLowS && (BN_cmp(sig->s, halforder) > 0)) |
316 | { |
317 | // enforce low S values |
318 | BN_sub(sig->s, order, sig->s); |
319 | } |
320 | |
321 | BN_CTX_end(ctx); |
322 | BN_CTX_free(ctx); |
323 | unsigned int nSize = ECDSA_size(pkey); |
324 | vchSig.resize(nSize); // Make sure it is big enough |
325 | unsigned char *pos = &vchSig[0]; |
326 | nSize = i2d_ECDSA_SIG(sig, &pos); |
327 | //printf("DEBUG DER R: 0x%s\n", BN_bn2hex(sig->r)); |
328 | //printf("DEBUG DER R: %s\n", BN_bn2dec(sig->r)); |
329 | //printf("DEBUG DER S: 0x%s\n", BN_bn2hex(sig->s)); |
330 | //printf("DEBUG DER S: %s\n", BN_bn2dec(sig->s)); |
331 | ECDSA_SIG_free(sig); |
332 | vchSig.resize(nSize); // Shrink to fit actual size |
333 | return true; |
334 | } |
335 | |
336 | // create a compact signature (65 bytes), which allows reconstructing the used public key |
337 | // The format is one header byte, followed by two times 32 bytes for the serialized r and s values. |
338 | // The header byte: 0x1B = first key with even y, 0x1C = first key with odd y, |
339 | // 0x1D = second key with even y, 0x1E = second key with odd y |
340 | bool SignCompact(uint256 hash, std::vector<unsigned char>& vchSig) |
341 | { |
342 | bool fOk = false; |
343 | ECDSA_SIG *sig = ECDSA_do_sign((unsigned char*)&hash, sizeof(hash), pkey); |
344 | if (sig==NULL) |
345 | return false; |
346 | vchSig.clear(); |
347 | vchSig.resize(65,0); |
348 | int nBitsR = BN_num_bits(sig->r); |
349 | int nBitsS = BN_num_bits(sig->s); |
350 | if (nBitsR <= 256 && nBitsS <= 256) |
351 | { |
352 | int nRecId = -1; |
353 | for (int i=0; i<4; i++) |
354 | { |
355 | CKey keyRec; |
356 | keyRec.fSet = true; |
357 | if (ECDSA_SIG_recover_key_GFp(keyRec.pkey, sig, (unsigned char*)&hash, sizeof(hash), i, 1) == 1) |
358 | if (keyRec.GetPubKey() == this->GetPubKey()) |
359 | { |
360 | nRecId = i; |
361 | break; |
362 | } |
363 | } |
364 | |
365 | if (nRecId == -1) |
366 | throw key_error("CKey::SignCompact() : unable to construct recoverable key"); |
367 | |
368 | vchSig[0] = nRecId+27; |
369 | BN_bn2bin(sig->r,&vchSig[33-(nBitsR+7)/8]); |
370 | BN_bn2bin(sig->s,&vchSig[65-(nBitsS+7)/8]); |
371 | fOk = true; |
372 | } |
373 | ECDSA_SIG_free(sig); |
374 | return fOk; |
375 | } |
376 | |
377 | // reconstruct public key from a compact signature |
378 | // This is only slightly more CPU intensive than just verifying it. |
379 | // If this function succeeds, the recovered public key is guaranteed to be valid |
380 | // (the signature is a valid signature of the given data for that key) |
381 | bool SetCompactSignature(uint256 hash, const std::vector<unsigned char>& vchSig) |
382 | { |
383 | if (vchSig.size() != 65) |
384 | return false; |
385 | if (vchSig[0]<27 || vchSig[0]>=31) |
386 | return false; |
387 | ECDSA_SIG *sig = ECDSA_SIG_new(); |
388 | BN_bin2bn(&vchSig[1],32,sig->r); |
389 | BN_bin2bn(&vchSig[33],32,sig->s); |
390 | |
391 | EC_KEY_free(pkey); |
392 | pkey = EC_KEY_new_by_curve_name(NID_secp256k1); |
393 | if (ECDSA_SIG_recover_key_GFp(pkey, sig, (unsigned char*)&hash, sizeof(hash), vchSig[0] - 27, 0) == 1) |
394 | { |
395 | fSet = true; |
396 | ECDSA_SIG_free(sig); |
397 | return true; |
398 | } |
399 | return false; |
400 | } |
401 | |
402 | bool Verify(uint256 hash, const std::vector<unsigned char>& vchSig) |
403 | { |
404 | // -1 = error, 0 = bad sig, 1 = good |
405 | if (ECDSA_verify(0, (unsigned char*)&hash, sizeof(hash), &vchSig[0], vchSig.size(), pkey) != 1) |
406 | return false; |
407 | return true; |
408 | } |
409 | |
410 | // Verify a compact signature |
411 | bool VerifyCompact(uint256 hash, const std::vector<unsigned char>& vchSig) |
412 | { |
413 | CKey key; |
414 | if (!key.SetCompactSignature(hash, vchSig)) |
415 | return false; |
416 | if (GetPubKey() != key.GetPubKey()) |
417 | return false; |
418 | return true; |
419 | } |
420 | |
421 | bool IsValid() |
422 | { |
423 | if (!fSet) |
424 | return false; |
425 | |
426 | CSecret secret = GetSecret(); |
427 | CKey key2; |
428 | key2.SetSecret(secret); |
429 | return GetPubKey() == key2.GetPubKey(); |
430 | } |
431 | }; |
432 | |
433 | #endif |