2014-06-11 17:07

比特币系统采用的公钥密码学方案和ECDSA签名算法介绍——第二部分:代码实现(C语言)

(原理部分请参考:《比特币系统采用的公钥密码学方案和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前添加版本号: 0x00,  --> extH0 3、生成校验值H1 = Hash256(extH0) 4、将H1的前四个字节 复制到extH0之后, ext_pubkey ={0x0, 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前添加版本号: 0x80, (如果使用压缩标志,则在V后再添加一个0x01),-->extV 3、生成校验值H1 = Hash256(extV) 4、将H1的前四个字节 复制到extV之后, ext_privkey ={0x80, V, (0x01), <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"

2."ecc_sample1.c"

3. VS6下需要下载gnu兼容的<stdint.h>

cprogram

2014.6.11

chehw


BTC addr:1ChEiWRkJJMBZVQojqjvW5fTB7hhUng129

本文链接:https://www.8btc.com/article/20121
转载请注明文章出处

评论(17)
登录 账号发表你的看法,还没有账号?立即免费 注册
荼蘼 2018-04-14
怎么附件里的代码找不到了
巴比特资讯 2014-06-23
982558d15c332ed8a2265d208fb29002242510cf910c39529d499764f6230fe1
我是大宇 2014-06-12
回复@羽毛币李志:[呵呵]
我是大宇 2014-06-12
回复@羽毛币李志:
我是大宇 2014-06-11
@吾谓话剧社 您好!来自【微问】的网友向您请教院校信息方面的问题:“南京财经大学2014年在新疆这里招生吗”『分享知识和经验来帮助TA,请点击 http://t.cn/RvaDSmw 』回答还能攒积分换礼品,iPad在向你招手!不愿收到求助信息请点击http://t.cn/8F4Kgad
我是大宇 2014-06-11
很好的代码剖析
昌用 2014-06-11
赞一个!
  • 大猫(bitPaul): 2014-06-11
    书读百遍,其义自见。。。虽然基础不好,但多花点时间,闲下来多看看,总是有收货的。互联网的分享精神真棒!哈哈。。。没准哪天我也是码农了呢?
我是大宇 2014-06-11
[花心]//@bitPaul: [好喜欢]好东西。
我是大宇 2014-06-11
//@bitPaul: [好喜欢]好东西。
我是大宇 2014-06-11
牛//@bitPaul:[好喜欢]好东西。
我是大宇 2014-06-11
[好喜欢]好东西。
我是大宇 2014-06-11
[c得瑟]韩版[ali扑]格子欧根纱中长半身裙a字高腰裙季式长裙http://t.cn/RvXylYW
我是大宇 2014-06-11
又不是你学校....
我是大宇 2014-06-11
转发微博
我是大宇 2014-06-11
《比特币系统采用的公钥密码学方案和ECDSA签名算法介绍——第二部分:代码实现(C语言)》http://t.cn/RvaWcyL 为降低代码复杂度,本文借助了openssl库来实现。一、 哈希函数;二、 Base58编码;三、 私钥生成;四、公钥的生成;五、 地址的生成和私钥的导出;六、签名和验证 @chehw_1 [汗]大神!!
我是大宇 2014-06-11
比特币系统采用的公钥密码学方案和ECDSA签名算法介绍——第二部分:代码实现(C语言): http://t.cn/RvaWcyL (《第三部分:交易细节》稍后再发,正在测试代码ing......)
下载
阅读
分享
评论
17
点赞
上一篇
下一篇