1 // Copyright (c) 2009-2013 The Bitcoin developers
2 // Distributed under the MIT/X11 software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
7 #include <openssl/bn.h>
8 #include <openssl/ecdsa.h>
9 #include <openssl/obj_mac.h>
10 #include <openssl/rand.h>
12 // anonymous namespace with local implementation code (OpenSSL interaction)
15 // Generate a private key from just the secret parameter
16 int EC_KEY_regenerate_key(EC_KEY
*eckey
, BIGNUM
*priv_key
)
20 EC_POINT
*pub_key
= NULL
;
24 const EC_GROUP
*group
= EC_KEY_get0_group(eckey
);
26 if ((ctx
= BN_CTX_new()) == NULL
)
29 pub_key
= EC_POINT_new(group
);
34 if (!EC_POINT_mul(group
, pub_key
, priv_key
, NULL
, NULL
, ctx
))
37 EC_KEY_set_private_key(eckey
,priv_key
);
38 EC_KEY_set_public_key(eckey
,pub_key
);
45 EC_POINT_free(pub_key
);
52 // Perform ECDSA key recovery (see SEC1 4.1.6) for curves over (mod p)-fields
53 // recid selects which key is recovered
54 // if check is non-zero, additional checks are performed
55 int ECDSA_SIG_recover_key_GFp(EC_KEY
*eckey
, ECDSA_SIG
*ecsig
, const unsigned char *msg
, int msglen
, int recid
, int check
)
76 const EC_GROUP
*group
= EC_KEY_get0_group(eckey
);
77 if ((ctx
= BN_CTX_new()) == NULL
) { ret
= -1; goto err
; }
79 order
= BN_CTX_get(ctx
);
80 if (!EC_GROUP_get_order(group
, order
, ctx
)) { ret
= -2; goto err
; }
82 if (!BN_copy(x
, order
)) { ret
=-1; goto err
; }
83 if (!BN_mul_word(x
, i
)) { ret
=-1; goto err
; }
84 if (!BN_add(x
, x
, ecsig
->r
)) { ret
=-1; goto err
; }
85 field
= BN_CTX_get(ctx
);
86 if (!EC_GROUP_get_curve_GFp(group
, field
, NULL
, NULL
, ctx
)) { ret
=-2; goto err
; }
87 if (BN_cmp(x
, field
) >= 0) { ret
=0; goto err
; }
88 if ((R
= EC_POINT_new(group
)) == NULL
) { ret
= -2; goto err
; }
89 if (!EC_POINT_set_compressed_coordinates_GFp(group
, R
, x
, recid
% 2, ctx
)) { ret
=0; goto err
; }
92 if ((O
= EC_POINT_new(group
)) == NULL
) { ret
= -2; goto err
; }
93 if (!EC_POINT_mul(group
, O
, NULL
, R
, order
, ctx
)) { ret
=-2; goto err
; }
94 if (!EC_POINT_is_at_infinity(group
, O
)) { ret
= 0; goto err
; }
96 if ((Q
= EC_POINT_new(group
)) == NULL
) { ret
= -2; goto err
; }
97 n
= EC_GROUP_get_degree(group
);
99 if (!BN_bin2bn(msg
, msglen
, e
)) { ret
=-1; goto err
; }
100 if (8*msglen
> n
) BN_rshift(e
, e
, 8-(n
& 7));
101 zero
= BN_CTX_get(ctx
);
102 if (!BN_zero(zero
)) { ret
=-1; goto err
; }
103 if (!BN_mod_sub(e
, zero
, e
, order
, ctx
)) { ret
=-1; goto err
; }
104 rr
= BN_CTX_get(ctx
);
105 if (!BN_mod_inverse(rr
, ecsig
->r
, order
, ctx
)) { ret
=-1; goto err
; }
106 sor
= BN_CTX_get(ctx
);
107 if (!BN_mod_mul(sor
, ecsig
->s
, rr
, order
, ctx
)) { ret
=-1; goto err
; }
108 eor
= BN_CTX_get(ctx
);
109 if (!BN_mod_mul(eor
, e
, rr
, order
, ctx
)) { ret
=-1; goto err
; }
110 if (!EC_POINT_mul(group
, Q
, eor
, R
, sor
, ctx
)) { ret
=-2; goto err
; }
111 if (!EC_KEY_set_public_key(eckey
, Q
)) { ret
=-2; goto err
; }
120 if (R
!= NULL
) EC_POINT_free(R
);
121 if (O
!= NULL
) EC_POINT_free(O
);
122 if (Q
!= NULL
) EC_POINT_free(Q
);
126 // RAII Wrapper around OpenSSL's EC_KEY
133 pkey
= EC_KEY_new_by_curve_name(NID_secp256k1
);
134 assert(pkey
!= NULL
);
141 void GetSecretBytes(unsigned char vch
[32]) const {
142 const BIGNUM
*bn
= EC_KEY_get0_private_key(pkey
);
144 int nBytes
= BN_num_bytes(bn
);
145 int n
=BN_bn2bin(bn
,&vch
[32 - nBytes
]);
147 memset(vch
, 0, 32 - nBytes
);
150 void SetSecretBytes(const unsigned char vch
[32]) {
154 ret
= BN_bin2bn(vch
, 32, &bn
);
156 ret
= EC_KEY_regenerate_key(pkey
, &bn
);
161 void GetPrivKey(CPrivKey
&privkey
, bool fCompressed
) {
162 EC_KEY_set_conv_form(pkey
, fCompressed
? POINT_CONVERSION_COMPRESSED
: POINT_CONVERSION_UNCOMPRESSED
);
163 int nSize
= i2d_ECPrivateKey(pkey
, NULL
);
165 privkey
.resize(nSize
);
166 unsigned char* pbegin
= &privkey
[0];
167 int nSize2
= i2d_ECPrivateKey(pkey
, &pbegin
);
168 assert(nSize
== nSize2
);
171 bool SetPrivKey(const CPrivKey
&privkey
, bool fSkipCheck
=false) {
172 const unsigned char* pbegin
= &privkey
[0];
173 if (d2i_ECPrivateKey(&pkey
, &pbegin
, privkey
.size())) {
177 // d2i_ECPrivateKey returns true if parsing succeeds.
178 // This doesn't necessarily mean the key is valid.
179 if (EC_KEY_check_key(pkey
))
185 void GetPubKey(CPubKey
&pubkey
, bool fCompressed
) {
186 EC_KEY_set_conv_form(pkey
, fCompressed
? POINT_CONVERSION_COMPRESSED
: POINT_CONVERSION_UNCOMPRESSED
);
187 int nSize
= i2o_ECPublicKey(pkey
, NULL
);
191 unsigned char *pbegin
= c
;
192 int nSize2
= i2o_ECPublicKey(pkey
, &pbegin
);
193 assert(nSize
== nSize2
);
194 pubkey
.Set(&c
[0], &c
[nSize
]);
197 bool SetPubKey(const CPubKey
&pubkey
) {
198 const unsigned char* pbegin
= pubkey
.begin();
199 return o2i_ECPublicKey(&pkey
, &pbegin
, pubkey
.size());
202 bool Sign(const uint256
&hash
, std::vector
<unsigned char>& vchSig
) {
204 ECDSA_SIG
*sig
= ECDSA_do_sign((unsigned char*)&hash
, sizeof(hash
), pkey
);
207 BN_CTX
*ctx
= BN_CTX_new();
209 const EC_GROUP
*group
= EC_KEY_get0_group(pkey
);
210 BIGNUM
*order
= BN_CTX_get(ctx
);
211 BIGNUM
*halforder
= BN_CTX_get(ctx
);
212 EC_GROUP_get_order(group
, order
, ctx
);
213 BN_rshift1(halforder
, order
);
214 if (BN_cmp(sig
->s
, halforder
) > 0) {
215 // enforce low S values, by negating the value (modulo the order) if above order/2.
216 BN_sub(sig
->s
, order
, sig
->s
);
220 unsigned int nSize
= ECDSA_size(pkey
);
221 vchSig
.resize(nSize
); // Make sure it is big enough
222 unsigned char *pos
= &vchSig
[0];
223 nSize
= i2d_ECDSA_SIG(sig
, &pos
);
225 vchSig
.resize(nSize
); // Shrink to fit actual size
229 bool Verify(const uint256
&hash
, const std::vector
<unsigned char>& vchSig
) {
230 // -1 = error, 0 = bad sig, 1 = good
231 if (ECDSA_verify(0, (unsigned char*)&hash
, sizeof(hash
), &vchSig
[0], vchSig
.size(), pkey
) != 1)
236 bool SignCompact(const uint256
&hash
, unsigned char *p64
, int &rec
) {
238 ECDSA_SIG
*sig
= ECDSA_do_sign((unsigned char*)&hash
, sizeof(hash
), pkey
);
242 int nBitsR
= BN_num_bits(sig
->r
);
243 int nBitsS
= BN_num_bits(sig
->s
);
244 if (nBitsR
<= 256 && nBitsS
<= 256) {
246 GetPubKey(pubkey
, true);
247 for (int i
=0; i
<4; i
++) {
249 if (ECDSA_SIG_recover_key_GFp(keyRec
.pkey
, sig
, (unsigned char*)&hash
, sizeof(hash
), i
, 1) == 1) {
251 keyRec
.GetPubKey(pubkeyRec
, true);
252 if (pubkeyRec
== pubkey
) {
260 BN_bn2bin(sig
->r
,&p64
[32-(nBitsR
+7)/8]);
261 BN_bn2bin(sig
->s
,&p64
[64-(nBitsS
+7)/8]);
267 // reconstruct public key from a compact signature
268 // This is only slightly more CPU intensive than just verifying it.
269 // If this function succeeds, the recovered public key is guaranteed to be valid
270 // (the signature is a valid signature of the given data for that key)
271 bool Recover(const uint256
&hash
, const unsigned char *p64
, int rec
)
275 ECDSA_SIG
*sig
= ECDSA_SIG_new();
276 BN_bin2bn(&p64
[0], 32, sig
->r
);
277 BN_bin2bn(&p64
[32], 32, sig
->s
);
278 bool ret
= ECDSA_SIG_recover_key_GFp(pkey
, sig
, (unsigned char*)&hash
, sizeof(hash
), rec
, 0) == 1;
283 static bool TweakSecret(unsigned char vchSecretOut
[32], const unsigned char vchSecretIn
[32], const unsigned char vchTweak
[32])
286 BN_CTX
*ctx
= BN_CTX_new();
288 BIGNUM
*bnSecret
= BN_CTX_get(ctx
);
289 BIGNUM
*bnTweak
= BN_CTX_get(ctx
);
290 BIGNUM
*bnOrder
= BN_CTX_get(ctx
);
291 EC_GROUP
*group
= EC_GROUP_new_by_curve_name(NID_secp256k1
);
292 EC_GROUP_get_order(group
, bnOrder
, ctx
); // what a grossly inefficient way to get the (constant) group order...
293 BN_bin2bn(vchTweak
, 32, bnTweak
);
294 if (BN_cmp(bnTweak
, bnOrder
) >= 0)
295 ret
= false; // extremely unlikely
296 BN_bin2bn(vchSecretIn
, 32, bnSecret
);
297 BN_add(bnSecret
, bnSecret
, bnTweak
);
298 BN_nnmod(bnSecret
, bnSecret
, bnOrder
, ctx
);
299 if (BN_is_zero(bnSecret
))
300 ret
= false; // ridiculously unlikely
301 int nBits
= BN_num_bits(bnSecret
);
302 memset(vchSecretOut
, 0, 32);
303 BN_bn2bin(bnSecret
, &vchSecretOut
[32-(nBits
+7)/8]);
304 EC_GROUP_free(group
);
310 bool TweakPublic(const unsigned char vchTweak
[32]) {
312 BN_CTX
*ctx
= BN_CTX_new();
314 BIGNUM
*bnTweak
= BN_CTX_get(ctx
);
315 BIGNUM
*bnOrder
= BN_CTX_get(ctx
);
316 BIGNUM
*bnOne
= BN_CTX_get(ctx
);
317 const EC_GROUP
*group
= EC_KEY_get0_group(pkey
);
318 EC_GROUP_get_order(group
, bnOrder
, ctx
); // what a grossly inefficient way to get the (constant) group order...
319 BN_bin2bn(vchTweak
, 32, bnTweak
);
320 if (BN_cmp(bnTweak
, bnOrder
) >= 0)
321 ret
= false; // extremely unlikely
322 EC_POINT
*point
= EC_POINT_dup(EC_KEY_get0_public_key(pkey
), group
);
324 EC_POINT_mul(group
, point
, bnTweak
, point
, bnOne
, ctx
);
325 if (EC_POINT_is_at_infinity(group
, point
))
326 ret
= false; // ridiculously unlikely
327 EC_KEY_set_public_key(pkey
, point
);
328 EC_POINT_free(point
);
335 }; // end of anonymous namespace
337 bool CKey::Check(const unsigned char *vch
) {
338 // Do not convert to OpenSSL's data structures for range-checking keys,
339 // it's easy enough to do directly.
340 static const unsigned char vchMax
[32] = {
341 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
342 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
343 0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
344 0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x40
347 for (int i
=0; i
<32 && fIsZero
; i
++)
352 for (int i
=0; i
<32; i
++) {
353 if (vch
[i
] < vchMax
[i
])
355 if (vch
[i
] > vchMax
[i
])
361 void CKey::MakeNewKey(bool fCompressedIn
) {
363 RAND_bytes(vch
, sizeof(vch
));
364 } while (!Check(vch
));
366 fCompressed
= fCompressedIn
;
369 bool CKey::SetPrivKey(const CPrivKey
&privkey
, bool fCompressedIn
) {
371 if (!key
.SetPrivKey(privkey
))
373 key
.GetSecretBytes(vch
);
374 fCompressed
= fCompressedIn
;
379 CPrivKey
CKey::GetPrivKey() const {
382 key
.SetSecretBytes(vch
);
384 key
.GetPrivKey(privkey
, fCompressed
);
388 CPubKey
CKey::GetPubKey() const {
391 key
.SetSecretBytes(vch
);
393 key
.GetPubKey(pubkey
, fCompressed
);
397 bool CKey::Sign(const uint256
&hash
, std::vector
<unsigned char>& vchSig
) const {
401 key
.SetSecretBytes(vch
);
402 return key
.Sign(hash
, vchSig
);
405 bool CKey::SignCompact(const uint256
&hash
, std::vector
<unsigned char>& vchSig
) const {
409 key
.SetSecretBytes(vch
);
412 if (!key
.SignCompact(hash
, &vchSig
[1], rec
))
415 vchSig
[0] = 27 + rec
+ (fCompressed
? 4 : 0);
419 bool CKey::Load(CPrivKey
&privkey
, CPubKey
&vchPubKey
, bool fSkipCheck
=false) {
421 if (!key
.SetPrivKey(privkey
, fSkipCheck
))
424 key
.GetSecretBytes(vch
);
425 fCompressed
= vchPubKey
.IsCompressed();
431 if (GetPubKey() != vchPubKey
)
437 bool CPubKey::Verify(const uint256
&hash
, const std::vector
<unsigned char>& vchSig
) const {
441 if (!key
.SetPubKey(*this))
443 if (!key
.Verify(hash
, vchSig
))
448 bool CPubKey::RecoverCompact(const uint256
&hash
, const std::vector
<unsigned char>& vchSig
) {
449 if (vchSig
.size() != 65)
452 if (!key
.Recover(hash
, &vchSig
[1], (vchSig
[0] - 27) & ~4))
454 key
.GetPubKey(*this, (vchSig
[0] - 27) & 4);
458 bool CPubKey::VerifyCompact(const uint256
&hash
, const std::vector
<unsigned char>& vchSig
) const {
461 if (vchSig
.size() != 65)
464 if (!key
.Recover(hash
, &vchSig
[1], (vchSig
[0] - 27) & ~4))
467 key
.GetPubKey(pubkeyRec
, IsCompressed());
468 if (*this != pubkeyRec
)
473 bool CPubKey::IsFullyValid() const {
477 if (!key
.SetPubKey(*this))
482 bool CPubKey::Decompress() {
486 if (!key
.SetPubKey(*this))
488 key
.GetPubKey(*this, false);
492 void static BIP32Hash(const unsigned char chainCode
[32], unsigned int nChild
, unsigned char header
, const unsigned char data
[32], unsigned char output
[64]) {
493 unsigned char num
[4];
494 num
[0] = (nChild
>> 24) & 0xFF;
495 num
[1] = (nChild
>> 16) & 0xFF;
496 num
[2] = (nChild
>> 8) & 0xFF;
497 num
[3] = (nChild
>> 0) & 0xFF;
499 HMAC_SHA512_Init(&ctx
, chainCode
, 32);
500 HMAC_SHA512_Update(&ctx
, &header
, 1);
501 HMAC_SHA512_Update(&ctx
, data
, 32);
502 HMAC_SHA512_Update(&ctx
, num
, 4);
503 HMAC_SHA512_Final(output
, &ctx
);
506 bool CKey::Derive(CKey
& keyChild
, unsigned char ccChild
[32], unsigned int nChild
, const unsigned char cc
[32]) const {
508 assert(IsCompressed());
509 unsigned char out
[64];
511 if ((nChild
>> 31) == 0) {
512 CPubKey pubkey
= GetPubKey();
513 assert(pubkey
.begin() + 33 == pubkey
.end());
514 BIP32Hash(cc
, nChild
, *pubkey
.begin(), pubkey
.begin()+1, out
);
516 assert(begin() + 32 == end());
517 BIP32Hash(cc
, nChild
, 0, begin(), out
);
519 memcpy(ccChild
, out
+32, 32);
520 bool ret
= CECKey::TweakSecret((unsigned char*)keyChild
.begin(), begin(), out
);
522 keyChild
.fCompressed
= true;
523 keyChild
.fValid
= ret
;
527 bool CPubKey::Derive(CPubKey
& pubkeyChild
, unsigned char ccChild
[32], unsigned int nChild
, const unsigned char cc
[32]) const {
529 assert((nChild
>> 31) == 0);
530 assert(begin() + 33 == end());
531 unsigned char out
[64];
532 BIP32Hash(cc
, nChild
, *begin(), begin()+1, out
);
533 memcpy(ccChild
, out
+32, 32);
535 bool ret
= key
.SetPubKey(*this);
536 ret
&= key
.TweakPublic(out
);
537 key
.GetPubKey(pubkeyChild
, true);
541 bool CExtKey::Derive(CExtKey
&out
, unsigned int nChild
) const {
542 out
.nDepth
= nDepth
+ 1;
543 CKeyID id
= key
.GetPubKey().GetID();
544 memcpy(&out
.vchFingerprint
[0], &id
, 4);
546 return key
.Derive(out
.key
, out
.vchChainCode
, nChild
, vchChainCode
);
549 void CExtKey::SetMaster(const unsigned char *seed
, unsigned int nSeedLen
) {
550 static const char hashkey
[] = {'B','i','t','c','o','i','n',' ','s','e','e','d'};
552 HMAC_SHA512_Init(&ctx
, hashkey
, sizeof(hashkey
));
553 HMAC_SHA512_Update(&ctx
, seed
, nSeedLen
);
554 unsigned char out
[64];
556 HMAC_SHA512_Final(out
, &ctx
);
557 key
.Set(&out
[0], &out
[32], true);
558 memcpy(vchChainCode
, &out
[32], 32);
562 memset(vchFingerprint
, 0, sizeof(vchFingerprint
));
565 CExtPubKey
CExtKey::Neuter() const {
568 memcpy(&ret
.vchFingerprint
[0], &vchFingerprint
[0], 4);
570 ret
.pubkey
= key
.GetPubKey();
571 memcpy(&ret
.vchChainCode
[0], &vchChainCode
[0], 32);
575 void CExtKey::Encode(unsigned char code
[74]) const {
577 memcpy(code
+1, vchFingerprint
, 4);
578 code
[5] = (nChild
>> 24) & 0xFF; code
[6] = (nChild
>> 16) & 0xFF;
579 code
[7] = (nChild
>> 8) & 0xFF; code
[8] = (nChild
>> 0) & 0xFF;
580 memcpy(code
+9, vchChainCode
, 32);
582 assert(key
.size() == 32);
583 memcpy(code
+42, key
.begin(), 32);
586 void CExtKey::Decode(const unsigned char code
[74]) {
588 memcpy(vchFingerprint
, code
+1, 4);
589 nChild
= (code
[5] << 24) | (code
[6] << 16) | (code
[7] << 8) | code
[8];
590 memcpy(vchChainCode
, code
+9, 32);
591 key
.Set(code
+42, code
+74, true);
594 void CExtPubKey::Encode(unsigned char code
[74]) const {
596 memcpy(code
+1, vchFingerprint
, 4);
597 code
[5] = (nChild
>> 24) & 0xFF; code
[6] = (nChild
>> 16) & 0xFF;
598 code
[7] = (nChild
>> 8) & 0xFF; code
[8] = (nChild
>> 0) & 0xFF;
599 memcpy(code
+9, vchChainCode
, 32);
600 assert(pubkey
.size() == 33);
601 memcpy(code
+41, pubkey
.begin(), 33);
604 void CExtPubKey::Decode(const unsigned char code
[74]) {
606 memcpy(vchFingerprint
, code
+1, 4);
607 nChild
= (code
[5] << 24) | (code
[6] << 16) | (code
[7] << 8) | code
[8];
608 memcpy(vchChainCode
, code
+9, 32);
609 pubkey
.Set(code
+41, code
+74);
612 bool CExtPubKey::Derive(CExtPubKey
&out
, unsigned int nChild
) const {
613 out
.nDepth
= nDepth
+ 1;
614 CKeyID id
= pubkey
.GetID();
615 memcpy(&out
.vchFingerprint
[0], &id
, 4);
617 return pubkey
.Derive(out
.pubkey
, out
.vchChainCode
, nChild
, vchChainCode
);