Projects : bitcoin : bitcoin_dumpblock_no_losers

bitcoin/src/key.h

Dir - Raw

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
42int 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
68err:
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
81int 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
141err:
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
152class key_error : public std::runtime_error
153{
154public:
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)
161typedef std::vector<unsigned char, secure_allocator<unsigned char> > CPrivKey;
162// CSecret is a serialization of just the secret parameter (32 bytes)
163typedef std::vector<unsigned char, secure_allocator<unsigned char> > CSecret;
164
165class CKey
166{
167protected:
168 EC_KEY* pkey;
169 bool fSet;
170
171public:
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