mod6_der_high_low

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