比特币非对称加密算法 比特币算法原理详解

一、非对称加密算法 (RSA、DSA、ECC、DH)

非对称加密需要两个密钥：公钥(publickey)和私钥(privatekey)。公钥和私钥是一对，如果用公钥对数据加密，那么只能用对应的私钥解密。如果用私钥对数据加密，只能用对应的公钥进行解密。因为加密和解密用的是不同的密钥，所以称为非对称加密。

非对称加密算法的保密性好，它消除了最终用户交换密钥的需要。但是加解密速度要远远慢于对称加密，在某些极端情况下，甚至能比对称加密慢上1000倍。

算法强度复杂、安全性依赖于算法与密钥但是由于其算法复杂，而使得加密解密速度没有对称加密解密的速度快。对称密码体制中只有一种密钥，并且是非公开的，如果要解密就得让对方知道密钥。所以保证其安全性就是保证密钥的安全，而非对称密钥体制有两种密钥，其中一个是公开的，这样就可以不需要像对称密码那样传输对方的密钥了。这样安全性就大了很多。

RSA、Elgamal、背包算法、Rabin、D-H、ECC(椭圆曲线加密算法)。使用最广泛的是 RSA算法，Elgamal是另一种常用的非对称加密算法。

收信者是唯一能够解开加密信息的人，因此收信者手里的必须是私钥。发信者手里的是公钥，其它人知道公钥没有关系，因为其它人发来的信息对收信者没有意义。

客户端需要将认证标识传送给服务器，此认证标识(可能是一个随机数)其它客户端可以知道，因此需要用私钥加密，客户端保存的是私钥。服务器端保存的是公钥，其它服务器知道公钥没有关系，因为客户端不需要登录其它服务器。

数字签名是为了表明信息没有受到伪造，确实是信息拥有者发出来的，附在信息原文的后面。就像手写的签名一样，具有不可抵赖性和简洁性。

简洁性：对信息原文做哈希运算，得到消息摘要，信息越短加密的耗时越少。

不可抵赖性：信息拥有者要保证签名的唯一性，必须是唯一能够加密消息摘要的人，因此必须用私钥加密(就像字迹他人无法学会一样)，得到签名。如果用公钥，那每个人都可以伪造签名了。

问题起源：对1和3，发信者怎么知道从网上获取的公钥就是真的？没有遭受中间人攻击？

这样就需要第三方机构来保证公钥的合法性，这个第三方机构就是 CA(Certificate Authority)，证书中心。

CA用自己的私钥对信息原文所有者发布的公钥和相关信息进行加密，得出的内容就是数字证书。

信息原文的所有者以后发布信息时，除了带上自己的签名，还带上数字证书，就可以保证信息不被篡改了。信息的接收者先用 CA给的公钥解出信息所有者的公钥，这样可以保证信息所有者的公钥是真正的公钥，然后就能通过该公钥证明数字签名是否真实了。

RSA是目前最有影响力的公钥加密算法，该算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥，即公钥，而两个大素数组合成私钥。公钥是可发布的供任何人使用，私钥则为自己所有，供解密之用。

A要把信息发给 B为例，确定角色：A为加密者，B为解密者。首先由 B随机确定一个 KEY，称之为私钥，将这个 KEY始终保存在机器 B中而不发出来；然后，由这个 KEY计算出另一个 KEY，称之为公钥。这个公钥的特性是几乎不可能通过它自身计算出生成它的私钥。接下来通过网络把这个公钥传给 A，A收到公钥后，利用公钥对信息加密，并把密文通过网络发送到 B，最后 B利用已知的私钥，就能对密文进行解码了。以上就是 RSA算法的工作流程。

由于进行的都是大数计算，使得 RSA最快的情况也比 DES慢上好几倍，无论是软件还是硬件实现。速度一直是 RSA的缺陷。一般来说只用于少量数据加密。RSA的速度是对应同样安全级别的对称密码算法的1/1000左右。

比起 DES和其它对称算法来说，RSA要慢得多。实际上一般使用一种对称算法来加密信息，然后用 RSA来加密比较短的公钥，然后将用 RSA加密的公钥和用对称算法加密的消息发送给接收方。

这样一来对随机数的要求就更高了，尤其对产生对称密码的要求非常高，否则的话可以越过 RSA来直接攻击对称密码。

和其它加密过程一样，对 RSA来说分配公钥的过程是非常重要的。分配公钥的过程必须能够抵挡中间人攻击。假设 A交给 B一个公钥，并使 B相信这是A的公钥，并且 C可以截下 A和 B之间的信息传递，那么 C可以将自己的公钥传给 B，B以为这是 A的公钥。C可以将所有 B传递给 A的消息截下来，将这个消息用自己的密钥解密，读这个消息，然后将这个消息再用 A的公钥加密后传给 A。理论上 A和 B都不会发现 C在偷听它们的消息，今天人们一般用数字认证来防止这样的攻击。

(1)针对 RSA最流行的攻击一般是基于大数因数分解。1999年，RSA-155(512 bits)被成功分解，花了五个月时间（约8000 MIPS年）和224 CPU hours在一台有3.2G中央内存的 Cray C916计算机上完成。

RSA-158表示如下：

2009年12月12日，编号为 RSA-768(768 bits, 232 digits)数也被成功分解。这一事件威胁了现通行的1024-bit密钥的安全性，普遍认为用户应尽快升级到2048-bit或以上。

RSA-768表示如下：

(2)秀尔算法

量子计算里的秀尔算法能使穷举的效率大大的提高。由于 RSA算法是基于大数分解(无法抵抗穷举攻击)，因此在未来量子计算能对 RSA算法构成较大的威胁。一个拥有 N量子位的量子计算机，每次可进行2^N次运算，理论上讲，密钥为1024位长的 RSA算法，用一台512量子比特位的量子计算机在1秒内即可破解。

DSA(Digital Signature Algorithm)是 Schnorr和 ElGamal签名算法的变种，被美国 NIST作为 DSS(DigitalSignature Standard)。 DSA是基于整数有限域离散对数难题的。

简单的说，这是一种更高级的验证方式，用作数字签名。不单单只有公钥、私钥，还有数字签名。私钥加密生成数字签名，公钥验证数据及签名，如果数据和签名不匹配则认为验证失败。数字签名的作用就是校验数据在传输过程中不被修改，数字签名，是单向加密的升级。

椭圆加密算法（ECC）是一种公钥加密算法，最初由 Koblitz和 Miller两人于1985年提出，其数学基础是利用椭圆曲线上的有理点构成 Abel加法群上椭圆离散对数的计算困难性。公钥密码体制根据其所依据的难题一般分为三类：大整数分解问题类、离散对数问题类、椭圆曲线类。有时也把椭圆曲线类归为离散对数类。

ECC的主要优势是在某些情况下它比其他的方法使用更小的密钥(比如 RSA)，提供相当的或更高等级的安全。ECC的另一个优势是可以定义群之间的双线性映射，基于 Weil对或是 Tate对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。不过一个缺点是加密和解密操作的实现比其他机制花费的时间长。

ECC被广泛认为是在给定密钥长度的情况下，最强大的非对称算法，因此在对带宽要求十分紧的连接中会十分有用。

比特币钱包公钥的生成使用了椭圆曲线算法，通过椭圆曲线乘法可以从私钥计算得到公钥，这是不可逆转的过程。

Java中 Chipher、Signature、KeyPairGenerator、KeyAgreement、SecretKey均不支持 ECC算法。

DH，全称为"Diffie-Hellman"，它是一种确保共享 KEY安全穿越不安全网络的方法，也就是常说的密钥一致协议。由公开密钥密码体制的奠基人 Diffie和 Hellman所提出的一种思想。简单的说就是允许两名用户在公开媒体上交换信息以生成"一致"的、可以共享的密钥。也就是由甲方产出一对密钥(公钥、私钥)，乙方依照甲方公钥产生乙方密钥对(公钥、私钥)。

以此为基线，作为数据传输保密基础，同时双方使用同一种对称加密算法构建本地密钥(SecretKey)对数据加密。这样，在互通了本地密钥(SecretKey)算法后，甲乙双方公开自己的公钥，使用对方的公钥和刚才产生的私钥加密数据，同时可以使用对方的公钥和自己的私钥对数据解密。不单单是甲乙双方两方，可以扩展为多方共享数据通讯，这样就完成了网络交互数据的安全通讯。

具体例子可以移步到这篇文章：非对称密码之DH密钥交换算法

参考：

二、高中生如何理解比特币加密算法

加密算法是数字货币的基石，比特币的公钥体系采用椭圆曲线算法来保证交易的安全性。这是因为要攻破椭圆曲线加密就要面对离散对数难题，目前为止还没有找到在多项式时间内解决的办法，在算法所用的空间足够大的情况下，被认为是安全的。本文不涉及高深的数学理论，希望高中生都能看懂。

密码学具有久远的历史，几乎人人都可以构造出加解密的方法，比如说简单地循环移位。古老或简单的方法需要保密加密算法和秘钥。但是从历史上长期的攻防斗争来看，基于加密方式的保密并不可靠，同时，长期以来，秘钥的传递也是一个很大的问题，往往面临秘钥泄漏或遭遇中间人攻击的风险。

上世纪70年代，密码学迎来了突破。Ralph C. Merkle在1974年首先提出非对称加密的思想，两年以后，Whitfield Diffie和Whitfield Diffie两位学者以单向函数和单向暗门函数为基础提出了具体的思路。随后，大量的研究和算法涌现，其中最为著名的就是RSA算法和一系列的椭圆曲线算法。

无论哪一种算法，都是站在前人的肩膀之上，主要以素数为研究对象的数论的发展，群论和有限域理论为基础。内容加密的秘钥不再需要传递，而是通过运算产生，这样，即使在不安全的网络中进行通信也是安全的。密文的破解依赖于秘钥的破解，但秘钥的破解面临难题，对于RSA算法，这个难题是大数因式分解，对于椭圆曲线算法，这个难题是类离散对数求解。两者在目前都没有多项式时间内的解决办法，也就是说，当位数增多时，难度差不多时指数级上升的。

那么加解密如何在公私钥体系中进行的呢？一句话，通过在一个有限域内的运算进行，这是因为加解密都必须是精确的。一个有限域就是一个具有有限个元素的集合。加密就是在把其中一个元素映射到另一个元素，而解密就是再做一次映射。而有限域的构成与素数的性质有关。

前段时间，黎曼猜想（与素数定理关系密切）被热炒的时候，有一位区块链项目的技术总监说椭圆曲线算法与素数无关，不受黎曼猜想证明的影响，就完全是瞎说了。可见区块链项目内鱼龙混杂，确实需要好好洗洗。

比特币及多数区块链项目采用的公钥体系都是椭圆曲线算法，而非RSA。而介绍椭圆曲线算法之前，了解一下离散对数问题对其安全性的理解很有帮助。

先来看一下费马小定理：

原根定义：

设（a, p)=1（a与p互素），满足

的最下正整数 l，叫作a模p的阶，模p阶为（最大值）p-1的整数a叫作模p的原根。

两个定理：

基于此，我们可以看到，{1, 2, 3,… p-1}就是一个有限域，而且定义运算 gi(mod p),落在这个有限域内，同时，当i取0～p-2的不同数时，运算结果不同。这和我们在高中学到的求幂基本上是一样的，只不过加了一层求模运算而已。

另一点需要说明的是，g的指数可以不限于0~p-2,其实可以是所有自然数，但是由于

所以，所有的函数值都是在有限域内，而且是连续循环的。

离散对数定义：

设g为模p的原根，（a,p)= 1，

我们称 i为a（对于模p的原根g）的指数，表示成：

这里ind就是 index的前3个字母。

这个定义是不是和log的定义很像？其实这也就是我们高中学到的对数定义的扩展，只不过现在应用到一个有限域上。

但是，这与实数域上的对数计算不同，实数域是一个连续空间，其上的对数计算有公式和规律可循，但往往很难做到精确。我们的加密体系里需要精确，但是在一个有限域上的运算极为困难，当你知道幂值a和对数底g，求其离散对数值i非常困难。

当选择的素数P足够大时，求i在时间上和运算量上变得不可能。因此我们可以说i是不能被计算出来的，也就是说是安全的，不能被破解的。

比特币的椭圆曲线算法具体而言采用的是 secp256k1算法。网上关于椭圆曲线算法的介绍很多，这里不做详细阐述，大家只要知道其实它是一个三次曲线（不是一个椭圆函数），定义如下：

那么这里有参数a, b；取值不同，椭圆曲线也就不同，当然x, y这里定义在实数域上，在密码体系里是行不通的，真正采用的时候，x, y要定义在一个有限域上，都是自然数，而且小于一个素数P。那么当这个椭圆曲线定义好后，它反应在坐标系中就是一些离散的点，一点也不像曲线。但是，在设定的有限域上，其各种运算是完备的。也就是说，能够通过加密运算找到对应的点，通过解密运算得到加密前的点。

同时，与前面讲到的离散对数问题一样，我们希望在这个椭圆曲线的离散点阵中找到一个有限的子群，其具有我们前面提到的遍历和循环性质。而我们的所有计算将使用这个子群。这样就建立好了我们需要的一个有限域。那么这里就需要子群的阶（一个素数n）和在子群中的基点G（一个坐标，它通过加法运算可以遍历n阶子群）。

根据上面的描述，我们知道椭圆曲线的定义包含一个五元祖（P, a, b, G, n, h)；具体的定义和概念如下：

P:一个大素数，用来定义椭圆曲线的有限域（群）

a, b:椭圆曲线的参数，定义椭圆曲线函数

G:循环子群中的基点，运算的基础

n:循环子群的阶（另一个大素数，< P）

h：子群的相关因子，也即群的阶除以子群的阶的整数部分。

好了，是时候来看一下比特币的椭圆曲线算法是一个怎样的椭圆曲线了。简单地说，就是上述参数取以下值的椭圆曲线：

椭圆曲线定义了加法，其定义是两个点相连，交与图像的第三点的关于x轴的对称点为两个点的和。网上这部分内容已经有很多，这里不就其细节进行阐述。

但细心的同学可能有个疑问，离散对数问题的难题表现在求幂容易，但求其指数非常难，然而，椭圆曲线算法中，没有求幂，只有求乘积。这怎么体现的是离散对数问题呢？

其实，这是一个定义问题，最初椭圆曲线算法定义的时候把这种运算定义为求和，但是，你只要把这种运算定义为求积，整个体系也是没有问题的。而且如果定义为求积，你会发现所有的操作形式上和离散对数问题一致，在有限域的选择的原则上也是一致的。所以，本质上这还是一个离散对数问题。但又不完全是简单的离散对数问题，实际上比一般的离散对数问题要难，因为这里不是简单地求数的离散对数，而是在一个自定义的计算上求类似于离散对数的值。这也是为什么椭圆曲线算法采用比RSA所需要的（一般2048位）少得多的私钥位数（256位）就非常安全了。

三、区块链技术(二) -- 比特币中使用的加密算法ECC

比特币中使用的加密算法ECC的要点如下：

基于椭圆曲线数学理论：

ECC是一种非对称加密算法，其安全性基于椭圆曲线数学问题的复杂性。密钥长度优势：

相较于RSA，ECC使用更短的密钥即可达到与RSA相等或更高的安全级别。特定椭圆曲线secp256k1：

比特币采用secp256k1椭圆曲线进行加密，该曲线关于y轴对称，且满足特定条件，适用于安全加密。加密过程：

涉及椭圆曲线上的加法运算，包括两个点的和以及同一个点的二倍运算。加密过程在有限域内进行，例如模数为质数的域，以避免加密解密后的偏差。同余运算与乘法逆元：

ECC加密算法涉及同余运算和乘法逆元的概念，这些数学概念在有限域内保证了加密过程的有效性。私钥与公钥的关系：

ECC加密算法的核心在于计算私钥与公钥的关系。已知公钥和基点，计算出私钥是非常困难的，这为加密提供了强大的安全性。ECDSA：

用于生成和验证签名，通过将私钥与消息摘要进行运算，生成不可逆的签名。签名的生成和验证过程依赖于随机数的引入，确保即使对相同消息，生成的签名也不同，提高了安全性。验证过程：

涉及从签名中提取出的两个值，利用公开密钥计算得到的值与接收到的值进行比较，若一致则验证成功，否则失败。整个过程确保了消息的真实性和完整性，是区块链技术中确保数据安全和交易可信的重要手段。