ECDSA和公钥

ECC算法是一种基于有限域椭圆曲线的数学算法。有关ECC算法基本原理的介绍，请参阅ECC加密算法介绍（http://www.8btc.com/eccmath)本文主要研究比特币系统中公钥密码体制和签名算法的实现细节。

1、 什么是pubkey和privkey

公钥加密（又称非对称（key）加密）是指存在一对与密钥相关的数学算法。用一个密钥加密后获得的信息只能用另一个密钥解密。如果其中一个公钥不损害另一个公钥的秘密性质，则公钥称为公钥，未发布的密钥为私钥。

公钥的主要作用：加密；签名验证。私钥的主要功能是：签名；解密。

特点：

公钥可以用私钥计算，否则就不能。

公钥加密：公钥加密的内容可以用私钥解密-只有私钥持有者才能解密。

私钥签名：私钥签名的内容可以通过公钥进行验证。公钥的可验证签名可以看作是私钥持有者的签名。

以上特性由数学算法保证。公钥密码体制有多种实现方案，如RSA、ElGamal、Duffy-Herman密钥交换协议中的公钥加密算法、椭圆曲线加密算法（ECC）。

RSA方案主要用于网上银行系统。比特币系统采用ECC方案，在核心实现中不使用加密，只使用签名算法来保证交易的真实性和所有权的认证。

2、 ECC简介

ECC方案通常包括三个方面：数字签名方案、加密和密钥传输方案以及密钥协商方案。本文仅讨论比特币系统中使用的数字签名方案。

（1） 有限域：

（最近，一些关于量子攻击的讨论涉及到这个概念。有一定或没有数学基础的人可以跳过这一部分。）

场的特点是集合F中的所有元素在定义后被加和乘，结果仍然包含在F中（加法和乘法闭合）。无限域中元素的数目是无限的，如有理数域和实数域。如果f是一个0到9的整数集，那么5和6都属于f，但是传统的加法定义5+6=11，11不属于f。因此，有限域需要定义加法和乘法，这样它们就接近于加法和乘法。

当且仅当元素个数q为素数或素数的n次方时，必有一个有限域。此外，对于满足此条件的每个q值，都存在一个有限域。有Q元素的有限域表示为FQ。在ECC格式中，只使用两种有限域：一种称为素数有限域Fp，其中q=P，P为质数；另一种称为基于特征值2的有限域F2^m，其中q=2^m，mgt；1。比特币系统使用第一种。FP是一组整数。在有限域Fp中定义了a+B≡R（modp）乘法：ab≡s（modp）的加法运算

（2） 基于有限域FP的椭圆曲线域e（FP）：

椭圆曲线：y^2∠x^3+ax+B（mod p）当：A，B∈FP和4A^3+27b^2≠0（mod p），x，y∈FP时，曲线上点的集合p=（x，y）构成基于有限域FP的椭圆曲线域e（FP），元素个数表示为ාe（FP）。

Q： 这跟比特币有什么关系？A： 公钥是曲线上q=（x，y）点的二进制输出格式。公开密钥可以压缩，因为可以根据X从曲线函数计算y。

（3） 椭圆曲线域e（FP）的描述参数如下

E:y^2≡x^3+ax+b（模式p）

为了描述一个特定的椭圆曲线域，需要定义六个参数：T=（P，a，B，G，N，H）

p： 表示有限域fpa，B的素数：椭圆方程的参数G：椭圆曲线上的一个基点G=（XG，YG）n：G在Fp中指定的序数，一个素数。h： 辅助因子，控制选定点的密度。h=#E（Fp）/n

比特币系统选择的secp256k1中，参数为p=ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

a=0，b=7

G=04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483AD77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

n=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF E BAAEDCE6 AF48A03BBFD25E8C D0364141 h=01

Q： n和比特币有什么关系？A： 比特币系统规定，私钥的**值范围不能超过n。

（4） 公钥和私钥：

从[1，n-1]中随机选择一个数字d，并计算q=dg。其中D是私钥，Q是公钥。

这个公式看起来很简单，但是我们怎么能保证D不能从Q来计算呢？有限域中的加法和乘法有特殊的规则。在基于FP的椭圆曲线点集域中，加法运算如下：

添加不同的点：（x1，Y1）∈e（FP），（X2，Y2）∈e（FP），x1≠X2（x1，Y1）+（X2，Y2）=（X3，Y3），其中X3∠λ^2−x1−X2（mod p），Y3∠λ（x1−X3）−Y1（mod p），而λ∠Y2−Y1）/（X2−x1）（mod p）

同点叠加：（x1，Y1）∈e（FP），Y1≠0。（x1，Y1）+（x1，Y1）=（X3，Y3），其中X3≡λ^2−2×1（mod p），Y3≡λ（x1−X3）−Y1（mod p），和λ∠λ（3×1^2+a）/2y1（mod p）

DG是一种标量乘法，可以转换成加法运算。如果有爱好者想从公钥中反推私钥，可以根据这些公式进行尝试（作者已经放弃了这一努力）。

3、 椭圆曲线数字签名算法（ECDSA）

用户密钥对：（D，q）；（D为私钥，q为公钥）待签名信息：m；签名（m）=（R，s）

签字流程：

1根据ECC算法，随机生成一个密钥对（k，R），R=（XR，yr）2，设R=XR，mod n，如果R=0，返回步骤1，3，计算H=hash（m）4，根据数据类转换规则将H转换为大端整数e5，s=k^-1（e+RD）mod n。如果s=0，返回步骤16。输出s=（R，s）是签名。

验证过程：

1计算H=hash（m）2，根据数据类转换规则，将H转换成big-endian的整数e。3计算U1=es^1模n，U2=RS^-1 mod n 4。计算r=（XR，yr）=u1g+u2q。如果r=0，则签名无效。5使v=XR mod n 6。如果v==R，则签名有效。如果V≠R，则签名无效。