公钥密码算法(public-key cryptography)，也被称为非对称密码算法，是一种非常有用的安全算法，是一种利用公钥和私钥两者来实现安全数据的传输，数据加解密的算法。

公钥加密算法的特点是使用两个密钥：一个为公开密钥（公钥），一个为私有密钥（私钥）。其中公钥用于加密数据，私钥用于解密数据，是一种通用的对称（Symmetric）加密算法的变体，缺点就是它相对比较耗费资源。

典型的公钥加密算法有RSA，Diffie-Hellman，ElGamal，DSA，这些算法都是经典的非对称加密算法的典型代表。RSA是最古老和最具有代表性的公钥算法，它根据一个出色的数论结论而闪耀出来，同时它有足够的安全性保障，并且加密速度极快（尤其是在解密方面）。

Diffie-Hellman算法是一种算法，可以在不安全的公开通信网络上实现安全沟通。它是建立在对数域上的，分布式系统特性的公钥通信系统，实现的主要是利用不同实体之间的数字方法来交换一个共享的密钥，以此实现安全传输。

ElGamal算法是基于大数因子分解和其它因数分解的非对称密码系统，通过非常复杂的数学运算，以确定消息通信的安全性。它实现的基本思想是允许接收者使用一个公钥来检验发送者的身份，同时也能加密信息。

DSA（数字签名算法）是一种非对称加密算法，用来生成由接收者认证发送者。它是一种随机生成公钥加密算法，用于数字签名，可以有效检查消息的完整性和真实性，也可以判断传输消息子的真实发送者。

总的来说，公钥密码算法是一种非常有效的安全技术，它不但保证了数据的安全，也保障了消息、文件和身份数据的真实传播性和脱机可验证性等。

一、 公钥(pubkey)、私钥(privkey)是什么

公开密钥加密（public-key cryptography，也称为非对称(密钥)加密），是指存在一对数学算法相关的密钥，使用其中一个密钥加密后所得的信息，只能用另一个密钥才能解密。如果其中一个公开后并不会危害到另外一个的秘密性质，则称公开的密钥为公钥，不公开的密钥为私钥。

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

特性：

• 通过私钥可以计算出公钥，反之则不行。
• 公钥加密：公钥加密的内容可以用私钥来解密——只有私钥持有者才能解密。
• 私钥签名：私钥签名的内容可以用公钥验证。公钥能验证的签名均可视为私钥持有人所签署。

以上特性通过数学算法来保证。公钥密码学的实现方案有很多种， 常见的有RSA、ElGamal、、迪菲－赫尔曼密钥交换协议中的公钥加密算法、椭圆曲线加密算法（ECC）。

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

二、椭圆曲线加密算法(ECC)简介

ECC方案通常包含有三方面内容，数字签名方案、加密和密钥传输方案、以及密钥协商方案。本文只涉及到比特币系统所使用的数字签名方案。

(最近有一些关于量子攻击的讨论中涉及到这一概念，有一定数学基础的和毫无数学基础的可以跳过这一小节）

域(Field)的特性是集合F中的所有元素经过定义后的加法和乘法运算，所得结果仍包含于F（在加法和乘法上封闭）。无限域的元素个数无限，比如有理数域、实数域。 有限域的元素个数有限，这就出现一个问题，假设F为从0至9的整数集合，那么5，6都属于F，但常规的加法定义5+6=11，11不属于F。因而，有限域需要定义加法和乘法，使其满足对加法和乘法的封闭。

目前已发现，当且仅当元素个数q为质数或某个质素的n次幂时，必有一个元素个数为q的有限域存在。另外，对于每一个符合这一条件的q值，都恰有一个有限域。含有q个元素的有限域记作：Fq。 ECC方案中只使用了两类有限域：一种称为质数有限域Fp，其中 q = p, p 为一个质数；另一种称为基于特征值2的有限域F2^m，其中q = 2^m , m > 1。 比特币系统使用的是第一种。 Fp是一个{0,1…,p-1}的整数集合，有限域Fp中定义了 加法：a + b ≡ r (mod p) 乘法：ab ≡ s(mod p).

（二）基于有限域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=(x,y)的二进制输出格式。公钥可以压缩，是因为y可以根据x通过曲线函数计算出来。

（三）椭圆曲线域E（Fp)的描述参数：

E : y^2 ≡ x^3 + ax + b (mod p)

为描述特定的椭圆曲线域，需明确六个参数：T = (p, a, b, G, n, h)

p: 代表有限域Fp的那个质数 a,b：椭圆方程的参数 G: 椭圆曲线上的一个基点G = (xG, yG) n：G在Fp中规定的序号，一个质数。 h：余因数（cofactor），控制选取点的密度。h = #E(Fp) / n。

比特币系统选用的secp256k1中，参数为 p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F = 2^256 − 2^32 − 2^9 − 2^8 − 2^7 − 2^6 − 2^4 − 1

a = 0， b = 7

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

n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 h = 01

问：n和比特币系统有什么关系？ 答：比特币系统规定私钥的取值范围最大不能超过n。

随机从[1,n-1]中选取一个数d, 计算Q = dG。 其中，d就是私钥，而Q即为公钥。

不同的点相加： (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 − 2x1 (mod p), y3≡ λ(x1 − x3) − y1 (mod p), andλ≡(3x1^2+ a)/2y1(mod p).

dG是一个标量乘法，可以转化为加法运算，如果有爱好者想由公钥逆推出私钥，可以根据这些公式来尝试一下（笔者本人已经放弃了这种努力）。

三、 椭圆曲线数字签名算法(ECDSA)：

用户的密钥对:（d, Q）；(d为私钥，Q为公钥) 待签名的信息：M； 签名：Signature(M) = ( r, s)

1、根据ECC算法随机生成一个密钥对(k, R), R=(xR, yR) 2、令 r = xR mod n，如果r = 0，则返回步骤1 3、计算 H = Hash(M) 4、按照数据类型转换规则，将H转化为一个big endian的整数e 5、s = k^-1 (e + rd) mod n，若s = 0, 则返回步骤1 6、输出的S =(r,s)即为签名。

1、 计算 H = Hash(M) 2、按照数据类型转换规则，将H转化为一个big endian的整数e 3、计算 u1 = es^-1 mod n, u2 = rs^-1 mod n 4、计算 R = (xR, yR) = u1G + u2Q, 如果R = 零点，则验证该签名无效 5、令 v = xR mod n 6、若 v == r，则签名有效，若 v ≠ r, 则签名无效。