技术科普 | 国密算法在Ultrain区块链中的运用

为了实现密码学技术的自主可控，中国也定义了自己的国密标准，2020年央行颁布的《金融分布式账本技术安全规范》中，明确要求国内的区块链技术必须支持国密算法。Ultrain区块链现已完成对国密算法的支持，符合央行安全规范的全部要求。

本文首先介绍了对称加密、非对称加密和数字签名的基本概念，然后重点讲述了非对称加密算法中的椭圆曲线密码技术，最后阐述了国密算法在Ultrain区块链中的运用。针对openssl国密算法签名验签性能低下的问题，Ultrain对算法实现进行了优化，实现了3~4倍的性能提升，相关的优化代码已经提交到openssl Github

（https://github.com/openssl/openssl/issues/11992）。

01

对称加密与非对称加密

1.1 对称加密

对称加密(symmetric cryptography)是指在加密和解密时使用相同密钥的方式。对称密钥有很多别名，如公共密钥密码，传统密码，私钥密码，共享密钥密码等。图1和图2分别是对称密码加密，解密过程，加密和解密使用相同的密钥，所以称为对称加密。

图1. 对称密码加密

图2. 对称密码解密

1.2 非对称加密

非对称加密(asymmetric cryptography)在加密和解密时使用不同密钥，非对称加密也称为公钥加密(public-key cryptography)。它们通常是一对密钥: 公钥(public key)和私钥(private key), 公钥加密后的密文，私钥可以解密；私钥加密后的密文，公钥可以解密。公钥是由私钥推导出来的，且公钥是公开的。非对称加密解决了对称加密过程中，加密密钥的分发问题。一般公钥用于加密，私钥用于解密。当私钥用于加密时，本质就是数字签名(digital signature)，即用公钥解密可以验证信息确实为私钥加密结果。公钥密码目前主要有如下几种：

• RSA(Ron Rivest, Adi Shamir和Leonard Adleman的姓氏的首字母组成)，该算法利用大质因数分解的困难度。

• EIGamal，由Taher EIGamal设计，与RSA不同，它是利用mod N下求离散对数的困难度。

• Rabin，由M.O.Rabin设计的公钥算法。Rabin方式求平方根的困难度

• 椭圆曲线密码(Elliptic Curve Cryptography, ECC)，

今天我们重点讲解的密码学算法，它是通过将椭圆曲线上的特定点进行特殊的乘法运算来实现的，它利用了这种乘法算法的逆运算非常困难这一特性。

公钥密钥算法较对称加密算法运算慢，所以，数据加密用对称加密算法，而公钥密码算法更多的应用于数字签名场景。

1.3 数字签名

某天Alice向Bob发送邮件：“hi，Bob，给我打1000000元，账号是6214 6576 8789 8987 账号名Alice”。在现实生活中，Bob可能会打电话给Alice，确认下邮件是否是伪造；还要确认内容有没有被篡改，防止收款账号和金额被恶意修改；当然还有一种场景，Bob把钱打给了Alice，最后Alice却否认发过这封邮件。

能够防止上述伪造，篡改和否认等威胁的技术就是前面提过的数字签名。通常消息比较长，我们只对消息的散列值进行签名，所以Alice发送邮件的流程如下：

1. Alice用单向散列函数计算邮件内容的散列值；

2. Alice用私钥对散列值进行加密，得到的密文就是Alice对这条散列值的签名，由于只有Alice才持有自己的私钥，所以除了Alice本人，其他人无法生成相同的密文，签出的签名Alice也无法抵赖；

3. Alice将消息和签名发送给Bob；

4. Bob用Alice的公钥对收到的签名进行解密的到散列值；

5. Bob将4中的得到的散列值与Alice直接发送的消息的散列值进行对比。如果两者一致，则签名验证成功，否则验证失败。

图3. 数字签名和签名验证

02

椭圆曲线加密算法详解

上面我们了解了对称加密和非对称加密的基本概念，本节我们主要讲用于数字签名的非对称加密算法中的椭圆曲线技术。

2.1 基本概念

2.1.1 阿贝尔群

在数学中，群是一种代数结构，有一个集合以及一个二元运算+所组成，满足以下条件：

1. 封闭性。集合内两数进行二元运算，结果仍在集合中。

2. 结合性。a+b+c = a+(b+c)

3. 单位元。存在单位元0，使得a+0=0+a=a

4. 逆元。每个元素都存在相反数，对任意a，必存在b使得a+b=0

5. 交换律。a+b+c = a+c+b

2.1.2 椭圆曲线方程

图4. 椭圆曲线[1]

在密码学中，定义在素数域GFp的椭圆曲线方程为：

E: y2 = x3 + ax + b 其中, a,b∈GFp且(4a3 + 27b2) mod p != 0

除了p，a，b定义了曲线之外，通常还需要x, y, n来确定一条椭圆曲线。所以，描述一条有限域上的椭圆曲线，有六个变量：T = (p, a, b, x, y, n).

p - 素数域内点的个数，p越大越安全，但是伴随着计算量的增大

a, b - 曲线系数

x, y - G点的x, y轴坐标

n - 为素数，且是G点的阶。椭圆曲线上一点P，存在着最小的正整数，使得nP=0∞(原点或无穷远点，以下无穷远点用0表示)，则称n为P的阶；若n不存在，我们说P是无限阶。在素数域上，椭圆曲线所有点的阶都存在。

2.1.3 椭圆曲线上点运算

素数域椭圆曲线上的点也是阿贝尔群。单位元是无穷远点0。椭圆曲线上点P的逆元是其x轴对称的点。

P和Q分别为素数域GFp上椭圆曲线两点，它们的连线与椭圆曲线交于第三点R(见图5中情况1)，有P + Q + R = 0无穷远点。有几种特殊情况，分别是下图中的2，3，4。第2种情况，直线与Q相切，可以看成Q和Q两点相连，与椭圆曲线相交于P点，即Q + Q + P = 0；第三种P，Q两点与y轴平行，因为两条平行线相交于无穷远点，所以有P + Q + 0 = 0;第四种情况，P和P相连，相交于无穷远点。

图5. 椭圆曲线运算[1]

根据以上我们有如下结论：

Q + Q + P = 0即Q + Q = -P, (Q + Q) + (Q + Q) = (-P) + (-P),即以P的对称点-P做切线，以此类推，我们可以快速得到2n*Q点, n∈[0, +∞)。在椭圆曲线用于加密中，私钥就是一个大整数，公钥就是椭圆曲线上的点G与私钥的乘积。我们通过私钥的二进制表示快速计算出公钥。

2.2 算法运用

椭圆曲线主要用于数字签名，以下是实现数字签名和签名验证的数学计算过程。

2.2.1 数字签名和签名验证

数字签名主要需要消息m的散列值(摘要)h，私钥kA，生成最终的结果{r,s}；签名验证主要用到公钥P，消息摘要h。以下是签名生成和验签的计算过程。

• 生成签名,即计算r和s的过程

1. 私钥为大数kA,公钥为私钥与G点相乘的点，P = kAG

2. 生成随机数小k，计算与基点的乘积K=kG，K点的x轴坐标Kx对椭圆曲线阶n的模Kx(mod n)为r，即r = Kx (mod n)

3. 计算k基于曲线阶的乘法逆元k-1(mod n)

4. r已经在第2步中生成，s=k-1(h+kAr)(mod n)

• 签名验证

1. 计算s基于椭圆曲线阶n的逆元s-1

2. 计算u1 = hs-1

3. 计算u2 = rs-1

4. 计算点Q=u1G+u2*P

5. 取点Q的x轴坐标Qx,若Qx等于r，即签名过程中K点的x轴坐标Kx，则验证通过。

• 证明为什么在验证签名过程中有这个特性？

1. 根据签名计算可知，s=k-1(h+kAr)(mod n)，两边乘k有sk=(h+kAr)(mod n)。

2. 点Q=u1G+u2*P，又P=KAG,有Q=u1G+u2KAG

3. 把u1和u2代入，Q=hs-1G+rs-1KAG=(h+rkA)s-1G

4. 把步1公式代入步骤3中，Q=sk*s-1G = kG,所以，假如{r,s}, h正确，点K和点P有相同的x轴坐标

2.2.2 椭圆曲线与RSA技术对比优势

之前我们讲过非对称密码RSA，国密推荐使用椭圆曲线加密，因为椭圆曲线比RSA有一定优势：

• 更安全。椭圆曲线基于离散对数困难度，计算复杂度是指数级的，求解难度大。而RSA算法是大质因数分解困难度，计算复杂度是亚指数级的。

• 更短的密钥。同等安全程度要求下，椭圆曲线算法比其他公钥算法需要的密钥长度小很多。128bit椭圆曲线算法拥有1024bit RSA算法相同的安全程度。

2.3 常用几种椭圆曲线

• secp256k1. 在比特币和以太坊网络中，用的是secp256k1，p是256位的素数，k代表Koblitz。a=0，b=7。曲线方程即y2=x3+7。Koblitz椭圆曲线具有一些特殊属性，可以更有效地实现组操作。

• secp256r1. secp256k1的姊妹曲线。p也是256位的素数，但值和secp256k1曲线是不一样的，r代表随机。"随机"选择的参数更安全，然而，有些人怀疑随机系数可能已经被选择来提供后门。因此，比特币网络并没有选择它，而是选择了更高效的secp256k1。

• SM2曲线。SM2是基于前人对ECC研究的基础上，中国推荐的标准曲线。GB/T 35276-2017定义了SM2算法的具体实现。

03

国密算法在Ultrain中的应用

Ultrain区块链对国密算法对支持，除了SM2椭圆曲线外，还应用了SM3, SM4。

• SM3 散列算法，生成256bit的散列值，主要用于替换SHA256算法。

• SM4 对称加密算法，Ultrain钱包公私钥加密用SM4取代了aes128。

3.1 国密算法实现详解

上面我们讲解了椭圆曲线的原理，SM2曲线也是建立在其之上，但是也有自己的特点：

3.1.1 SM2中h值的计算

在secp256k1中，h就是消息的散列值，而在SM2中，计算h值更复杂，需要分两步计算：

1. 通过sm3算法计算出Z值:
Z=SM3(ENTL||ID||a||b||xG||yG||xA||yA)
ID: 用户身份标志的字符串
ENTL: 两个字节表示的ID的比特长度
a, b: 曲线参数
xG, yG：G点坐标x，y轴
xA，yA：公钥坐标x，y轴

2. 使用Z和待签名的消息，通过sm3算出杂凑值h，h=SM3(Z||M)

3.2 国密算法优化

3.2.1 openssl SM2曲线性能问题

我们基于openssl开发SM2的实现，但是使用过程中发现签名和验证速度很慢，在Macbook Pro上，每10秒签名22496次，每10秒验签24374次。定位到EC_POINT_mul速度慢。查看openssl的源代码，它没有对2n*G, n∈[0, 256](私钥是256bit长)这样的点进行预缓存。如私钥二进制为：1000 1100，它对于的公钥就是27*G + 23*G + 22*G,而2*G，22*G，23*G...2256*G都是已知的，所以只需要椭圆曲线上3个点的+运算，不需要每次重新计算。除此之外，有部分核心功能需要用汇编编写，优化后性能有3-4倍的提高，如下表。

表1. 性能优化前后对比

相应的优化代码我们已经提交到openssl Github。

图6. 优化代码提交到openssl Github

3.2.2 SM2签名和消息无法recover公钥

在secp256k1我们可以根据签名{r,s}和消息恢复公钥，但是SM2却不能通过签名和消息恢复公钥，因为在SM2的h值计算过程中，我们用到了公钥的坐标，所以必须知道公钥了，和只有签名和消息recover公钥相矛盾。因为SM2无法通过签名和消息recover公钥，所以在对交易验证的过程，我们都是取出公钥然后验证。但是，在我们的系统里，一个账号可以拥有几个公钥，所以需要遍历账号的公钥验证交易，导致多公钥账号的交易执行性能会低些。幸运的是，我们统计系统中所有的账号，99%只有一对公私钥，所以理论上不会对系统整体性能造成影响。

04

结论

本文首先介绍了对称加密和非对称加密的基本概念，然后详细介绍了非对称加密技术中的椭圆曲线加密技术，最后阐述了Ultrain区块链对国密算法的支持，椭圆曲线加密部分的理解对数学基础要求比较高。区块链的去中心化信任建立密码学之上，密码学技术又建立在数学之上，所以说，In Math We Trust。

参考文献：

[1]. https://encyclopedia.thefreedictionary.com/elliptic+curve