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

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

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

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

01

对称加密与非对称加密

1.1 对称加密

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

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

图 1. 对称密码加密

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

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

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

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

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

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

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

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

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

表 1. 性能优化前后对比

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

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

图 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

让信任计算赋能各行各业

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

Ultrain 团队核心管理人员

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

扫二维码下载 UltrainOne APP:

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


以下为 Ultrain 各社交媒体账号

欢迎大家加入:

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

微信用户可关注公众平台:ultrainchain

并可添加管理员微信(ultra-in)

或扫码申请加入超脑链 Ultrain 中文社区

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

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

微博用户可关注:@Ultrain 超脑信任计算

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

Facebook 用户可访问主页:Ultraincommunity

Link:http://fb.me/Ultraincommunity

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

Twitter 用户可关注:@UltrainB

Link:https://twitter.com/UltrainB

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

Telegram 用户可加入电报群:

Link:https://t.me/UltrainOfficial

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

-END-

来源链接:mp.weixin.qq.com