（原理部分请参考：《比特币系统采用的公钥密码学方案和ECDSA签名算法介绍——第一部分：原理》）
依赖库：openssl-1.01h ，参考文档：http://openssl.sourcearchive.com/
为降低代码复杂度，本文借助了openssl库来实现大整数（BIGNUM）的运算、伪随机数的生成、HASH算法、密钥生成以及数字签名。
比特币系统中的整数字节顺序：（首先要搞清楚字节次序，看bitcoin-qt源码时会有一定帮助）
- 大整数（超过64位的）使用big endian编码，如HASH值。
- 64位及以下的变长整数使用little endian编码，如Varint, Compact Integer等。
- 64位及以下的常规整数使用系统内定的编码。如int64_t, itn32_t等。
一、 哈希函数:
目前bitcoin-qt中的使用的HASH函数主要是Hash256和Hash160。(代码中预留了Hash512，但未使用)
Hash256是对原始数据进行两次SHA256操作，生成一个256位(bit)的HASH结果。应用场合：block_header, 交易(Transactions)，base58check校验等。
Hash160是对原始数据先进性一次SHA256操作，再对生成的hash值进行RIPEMD160操作，生成一个160位(bit)的HASH结果。应用场合：bitcoin地址。
示例代码：
#define HASH256_SIZE (32)
#define HASH160_SIZE (20)
size_t Hash256(const unsigned char * begin, size_t size, unsigned char to[])
{
unsigned char hash[HASH256_SIZE];
if(NULL == begin || size == 0) return 0;
SHA256(begin, size, (unsigned char *)&hash[0]);
SHA256(&hash[0], sizeof hash, (unsigned char *)&to[0]);
return HASH256_SIZE;
}
size_t Hash160(const unsigned char * begin, size_t size, unsigned char to[])
{
unsigned char hash[HASH256_SIZE];
if(NULL == begin || size == 0) return 0;
SHA256(begin, size, (unsigned char *)&hash[0]);
RIPEMD160(&hash[0], sizeof hash, &to[0]);
return HASH160_SIZE;
}
二、 Base58编码
编码特点：输出结果为不容易混淆的字母和数字，便于鼠标操作（用鼠标双击即可选取完整的文本）。
应用场合：Bitcoin的地址、私钥导出。
编码步骤：
将原始数据看作一个大整数 E
(1) r = E mod 58
(2) 将r附加到输出缓冲区，
(3) E = E / 58， 若E ≠ 0，则返回（1）
(4) 检查原始数据是否有前导的’0’，如有，则将base58编码的0添加到输出缓冲区中
(5) 字符串反转（转换成big endian的格式）
示例代码：
static const char* pszBase58 = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
size_t Base58Encode(const unsigned char *begin, size_t size, char *to)
{
size_t cb = 0;
BN_CTX * ctx = NULL;
unsigned char c;
unsigned char *pzero = (unsigned char *)begin;
unsigned char *pend = (unsigned char *)(begin + size);
char *p = to;
// bool fSign = 0;
BIGNUM bn, dv, rem, bn58, bn0;
if((NULL == begin) || (size == 0)) return 0; // invalid parameter
cb = size * 138 /100+1; // the size of output will less than (138/100 * sizeof(src))
//** output buffer should be allocated enough memory
if(NULL == to) return cb;
BN_init(&bn58); BN_init(&bn0);
BN_set_word(&bn58, 58);
BN_zero(&bn0);
BN_init(&bn); BN_init(&dv); BN_init(&rem);
BN_bin2bn(begin, size, &bn);
ctx = BN_CTX_new();
if(NULL==ctx) return 0;
// 前面的都是初始化工作，下面是正式的算法
while(BN_cmp(&bn, &bn0) > 0)
{
if(!BN_div(&dv, &rem, &bn, &bn58, ctx)) break;
bn = dv;
c = BN_get_word(&rem);
*(p++) = pszBase58[c];
}
// 添加前导的0
while(*(pzero++)==0)
{
*(p++) = pszBase58[0];
if(pzero > pend) break;
}
*p = '';
cb = p - to;
ReverseBytes((unsigned char *)to, cb); // output as a big endian integer
BN_CTX_free(ctx);
return cb;
}
解码步骤：
static const int8_t b58digits[] = {
-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
-1, 0, 1, 2, 3, 4, 5, 6, 7, 8,-1,-1,-1,-1,-1,-1,
-1, 9,10,11,12,13,14,15, 16,-1,17,18,19,20,21,-1,
22,23,24,25,26,27,28,29, 30,31,32,-1,-1,-1,-1,-1,
-1,33,34,35,36,37,38,39, 40,41,42,43,-1,44,45,46,
47,48,49,50,51,52,53,54, 55,56,57,-1,-1,-1,-1,-1,
};
size_t Base58Decode(const char *begin, size_t size, unsigned char *to)
{
unsigned char c;
unsigned char *p = (unsigned char *)begin;
unsigned char *pend = p + size;
size_t cb;
BIGNUM bn, bnchar;
BIGNUM bn58, bn0;
BN_CTX *ctx = BN_CTX_new();
if(NULL == ctx) return 0;
BN_init(&bn58);
BN_init(&bn0);
BN_init(&bn); BN_init(&bnchar);
BN_set_word(&bn58, 58);
BN_zero(&bn0);
while(p < pend)
{
c = *p;
if(c & 0x80) goto label_errexit;
if(-1 == b58digits[c]) goto label_errexit;
BN_set_word(&bnchar, b58digits[c]);
if(!BN_mul(&bn, &bn, &bn58, ctx)) goto label_errexit;
BN_add(&bn, &bn, &bnchar);
p++;
}
cb = BN_num_bytes(&bn);
if(NULL == to) return cb;
BN_bn2bin(&bn, to);
BN_CTX_free(ctx);
return cb;
label_errexit:
if(NULL != ctx) BN_CTX_free(ctx);
return 0;
}
三、 私钥生成
比特币系统中的私钥是一个256位（bits）的随机整数。
取值范围在[1,n-1]之间，其中，
n (order) = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
生成步骤：
1、初始化伪随机数种子
2、生成一个256位的随机数
3、验证随机数范围是否在[1,n-1]，如超出范围，则返回2
示例代码：
BOOL ECKey_Check(const unsigned char vch[32]);
uint32_t ECKey_GeneratePrivKey(EC_KEY * pkey, unsigned char vch[32])
{
RandAndSeed(); // 初始化随机数种子，具体实现请参考附件中的源文件，或bitcoin-qt的源码
do
{
RAND_bytes(vch, 32); // 利用openssl库生成一个256位的随机数
}while(!ECKey_Check(vch)); // 检查取值范围是否合法
if(pkey != NULL) return ECKey_GenKeypair(pkey, vch); // 生成密钥对
return 32; // 私钥的字节数
}
BOOL ECKey_Check(const unsigned char vch[32])
{
static const unsigned char order[32] = {
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x40
};
BIGNUM bn; // 私钥
BIGNUM bnOrder; // G在Fp下的序号order
BIGNUM bn0; // 0
BN_init(&bn);
BN_init(&bnOrder);
BN_init(&bn0);
BN_zero(&bn0);
BN_bin2bn(vch, 32, &bn); //将二进制序列转化为一个大整数
BN_bin2bn(order, 32, &bnOrder);
//** 0 < [私钥] < order
if(BN_is_zero(&bn)) return 0; // 私钥不能为0
if(BN_cmp(&bn, &bnOrder) > 0) return 0; //私钥必须小于order
return 1;
}
四、公钥的生成
公钥的计算公式：Q = dG
Q: 公钥
d: 私钥
G: 椭圆曲线基点
//** 初始化EC_KEY，告知openssl库将使用secp256k1椭圆曲线。
EC_KEY * ECKey_new()
{
return EC_KEY_new_by_curve_name(NID_secp256k1);
}
uint32_t ECKey_GenKeypair(EC_KEY * pkey, unsigned char vch[HASH256_SIZE])
{
//** pkey = ECKey_new();
const uint32_t key_size = HASH256_SIZE;
const EC_GROUP * group;
BIGNUM bn;
BIGNUM * privkey = &bn;
BN_CTX * ctx = NULL;
EC_POINT * pubkey = NULL;
if(NULL == pkey) return 0;
BN_init(&bn); // BIGNUM使用前最好先初始化，否则windows + mingw环境下有时会出错
group = EC_KEY_get0_group(pkey); // group结构体中存储了G值和运算规则
pubkey = EC_POINT_new(group); // 给pubkey分配内存，pubkey为曲线上的一个点
ctx = BN_CTX_new();
if(NULL == pubkey || NULL == ctx) goto label_errexit;
if(BN_bin2bn(vch, key_size, &bn)) // 将私钥（二进制形式）转化为一个大整数
{
if(EC_POINT_mul(group, pubkey, privkey, NULL, NULL, ctx)) // pubkey =privkey*G
{
// 将密钥存储于EC_KEY结构体中，便于导出为所需的格式
EC_KEY_set_private_key(pkey, privkey);
EC_KEY_set_public_key(pkey, pubkey);
}
BN_clear_free(&bn);
}
EC_POINT_free(pubkey);
BN_CTX_free(ctx);
return key_size;
label_errexit:
if(NULL!=pubkey) EC_POINT_free(pubkey);
if(NULL != ctx) BN_CTX_free(ctx);
return 0;
}
公钥提取：
uint32_t ECKey_GetPubkey(EC_KEY * pkey, unsigned char * pubkey, BOOL fCompressed)
{
unsigned char * p_pubkey = pubkey;
uint32_t cb;
EC_KEY_set_conv_form(pkey, fCompressed?POINT_CONVERSION_COMPRESSED:POINT_CONVERSION_UNCOMPRESSED); // 公钥采用压缩还是非压缩格式输出
cb = i2o_ECPublicKey(pkey, NULL);
if(0==cb || cb>65) return 0;
if(NULL == pubkey) return cb;
// 此处不要直接用pubkey，openssl库会自动修改传递进去的指针
cb = i2o_ECPublicKey(pkey, &p_pubkey);
return cb;
}
五、 比特币地址的生成和私钥的导出
比特币地址的生成：
步骤：
1、H0 = Hash160(公钥)
2、在H0前添加版本号: 0×00, –> extH0
3、生成校验值H1 = Hash256(extH0)
4、将H1的前四个字节 复制到extH0之后, ext_pubkey ={0×0, H0, <first 4 bytes of H1>};
5、对ext_pubkey进行base58编码，输出的结果即为比特币地址
//**************************************************
//** Base58check编码生成比特币地址
uint32_t PubkeyToAddr(const unsigned char * pubkey, size_t size, char *to)
{
struct
{
unsigned char version;
unsigned char vch[20];
unsigned char checksum[4];
}ext_pubkey;
unsigned char hash[32]={0};
printf("ext_pubkey size: %d\n", sizeof(ext_pubkey));
ext_pubkey.version = 0x00;
Hash160(pubkey, size, &ext_pubkey.vch[0]);
Hash256(&ext_pubkey.version, 1+20, hash);
memcpy(ext_pubkey.checksum, hash, 4);
return Base58Encode((unsigned char *)&ext_pubkey.version, sizeof(ext_pubkey), to);
}
私钥导出格式：
步骤：
1、将私钥转化为256位的二进制格式V
2、在V前添加版本号: 0×80, （如果使用压缩标志，则在V后再添加一个0×01），–>extV
3、生成校验值H1 = Hash256(extV)
4、将H1的前四个字节 复制到extV之后, ext_privkey ={0×80, V, (0×01), <first 4 bytes of H1>};
5、对ext_privkey进行base58编码，输出的结果即为比特币地址
uint32_t PrivkeyToWIF(const unsigned char vch[HASH256_SIZE], char *to, BOOL fCompressed)
{
struct
{
unsigned char version;
unsigned char vch[HASH256_SIZE];
unsigned char checksum[5];
}ext_privkey;
unsigned char hash[HASH256_SIZE];
uint32_t offset = fCompressed?1:0;
ext_privkey.version = 0x80;
memcpy(ext_privkey.vch, vch, 32);
if(offset) ext_privkey.checksum[0] = 0x01;
Hash256(&ext_privkey.version, 1 + HASH256_SIZE +offset, hash);
memcpy(&ext_privkey.checksum[offset], hash, 4 );
return Base58Encode(&ext_privkey.version, 1 + HASH256_SIZE + offset + 4, to);
}
六、签名和验证
签名步骤：
1、H = Hash256(M)
2、调用openssl的ECDSA_do_sign函数，生成签名sig = (r,s)。
3、检查s值是否大于order/2，如果大于，则利用 s + (-s) = order, -s = order –s, 这一性质将签名改写为(r, -s)的形式。这两种形式的签名是等效的，但如果s > order/2，由于验证方的实现方式不可预知，验证方有可能将其视为一个更大的正整数而不是-s,这会导致签名验证失败。
size_t ECKey_Sign(EC_KEY *pkey, const unsigned char hash[HASH256_SIZE], unsigned char **to)
{
//** if (*to) == NULL, the caller should use OPENSSL_free(*to) to free the memory
size_t cb = 0;
ECDSA_SIG *sig = NULL;
BN_CTX * ctx = NULL;
BIGNUM order; // The order of G
BIGNUM halforder; // get sign/unsign mark
unsigned char *output = NULL;
const EC_GROUP * group = EC_KEY_get0_group(pkey); // secp256k1: G
if(NULL == group) return 0;
sig = ECDSA_do_sign((unsigned char *)&hash[0], HASH256_SIZE, pkey);
if(NULL == sig) return 0;
//** sig = (r,s) = (r,-s)
//** s must less than order/2, otherwise, some app may parse '-s' as a large unsigned positive integer
ctx = BN_CTX_new();
if(NULL == ctx) goto label_exit;
//** allocate memory for bignum
BN_init(&order);
BN_init(&halforder);
// get the order of G
EC_GROUP_get_order(group, &order, ctx); // secp256k1: n
BN_rshift1(&halforder, &order);
if(BN_cmp(sig->s, &halforder)>0)
{
// if s > order/2, then output -s. (-s = (order - s))
BN_sub(sig->s, &order, sig->s);
}
BN_CTX_free(ctx);
output = *to;
cb = ECDSA_size(pkey);
if(NULL == output)
{
output = (unsigned char *)OPENSSL_malloc(cb);
if(NULL == output) goto label_exit;
}
if(NULL == *to) *to = output;
//** i2d_ECDSA_SIG DER encode content of ECDSA_SIG object
//** (note: this function modifies *pp (*pp += length of the DER encoded signature)).
//** do not pass the address of 'to' directly
cb = i2d_ECDSA_SIG(sig, &output);
label_exit:
ECDSA_SIG_free(sig);
return cb;
}
验证签名：
BOOL ECKey_Verify(EC_KEY *pkey, const unsigned char hash[HASH256_SIZE], const unsigned char *sig, size_t size)
{
if(ECDSA_verify(0, (unsigned char *)&hash[0], HASH256_SIZE, sig, size, pkey) != 1) // -1 = error, 0 = bad sig, 1 = good
return FALSE;
return TRUE;
}
附件：
1. “sample.h”
3. VS6下需要下载gnu兼容的<stdint.h>
