密码学是区块链的基础,区块链中大量采用了密码学算法,包括对称加密、非对称加密、单向散列算法、数字签名等技术。

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

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

https://github.com/openssl/openssl/issues/11992)。

01

对称加密与非对称加密

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

alt text

图1. 对称密码加密

alt text

图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直接发送的消息的散列值进行对比。如果两者一致,则签名验证成功,否则验证失败。

alt text

图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 椭圆曲线方程

alt text

图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相连,相交于无穷远点。

alt text

图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的过程

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

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

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

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

签名验证

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

计算u1 = hs-1

计算u2 = rs-1

计算点Q=u1G+u2*P

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

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

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

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

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

把步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的源代码,它没有对2nG, n∈0, 256这样的点进行预缓存。如私钥二进制为:1000 1100,它对于的公钥就是27G + 23G + 22G,而2G,22G,23G...2256G都是已知的,所以只需要椭圆曲线上3个点的+运算,不需要每次重新计算。除此之外,有部分核心功能需要用汇编编写,优化后性能有3-4倍的提高,如下表。

alt text

表1. 性能优化前后对比

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

alt text

图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