双线性对在密码学中的应用（下）

趣链科技阅读 17053 2020-11-30 17:14

如果关心近年的密码学成果，可以发现双线性对作为一个基础的密码学工具频频出现。双线性对是一种二元映射，它作为密码学算法的构造工具，在各区块链平台中广泛应用，比如零知识证明、聚合签名等技术方案大多基于双线性对构造得来。

本次分为上、下两个篇章讲解双线性对在密码学中的应用。

上篇回顾《双线性对在密码学中的应用（上）》

本文为下篇进阶篇，会从双线性对的性质开始着手，然后分析三方一轮密钥交换和SM9数字签名算法两个例子的原理，最后介绍一些双线性对的优秀代码实现。

双线性对的性质介绍

▲ 性质介绍

在本科阶段的线性代数课程中，读者可能已经学习过线性映射（linear mapping）的概念，但是对双线性映射（bilinear mapping）的概念可能会感到陌生。

我们说一个函数f是线性的是指函数f满足可加性和齐次性，也就是：

可加性：f(a)+f(b)=f(a+b)

齐次性：f(ka)=kf(a)

比如中学就接触的正比例函数就是一个线性映射。

例如对f(x)=3x，有f(1)=3，f(-2)=-6，则：

可加性：f(1)+f(-2)=f(-1)=-3

齐次性：f(-2)=-6=-2f(1)

理解了线性，那么双线性就好理解很多。

和线性函数不同的点在于满足双线性的函数有两个输入，而且对这两个输入分别满足线性。换言之，如果固定其中一个输入使之成为一元函数，则这个一元函数满足线性。

而双线性对就是指群上元素满足双线性映射的三个群，它们的关系满足双线性，下面是定义：

G₁、G₂和G₃是三个n阶循环群，一个双线性对（双线性映射）?是一个从G₁×G₂→G₃的双线性映射，满足：

1.双线性性: ?(ag₁，bg₂) = ab?(g₁, g₂), 其中g₁∈ G₁, g₂ ∈ G₂

2.非退化性: 存在g₁，g₂，使得?(g₁，g₂) 不为G₃中的单位元

3.可计算性: 存在有效的多项式时间算法计算双线性对的值

上述定义简单来说就是，一个映射e，能将G₁和G₂中的两个元素映射为G₃中的一个元素，并且该映射满足双线性。这里的定义虽然严谨，但不便于读者接受，我们通过类比来加深理解，例如读者熟悉的向量内积就满足双线性。我们来回顾一下向量内积的特点，内积运算从两个向量α和β得到数r：

α · β → r

所谓双线性映射，是从两个元素到一个元素的映射，并且这个映射对每一个输入的元素都保持线性。

比方说：我们固定β，则r和α是有线性的关系的：如果用kα代替α，那么结果就是kr；固定α也有同样的结论，因此内积的运算是有双线性的。

我们研究的椭圆曲线上的双线性对也正是有类似的双线性，并且根据双线性，我们有下面的推论：

设g₁, g₂分别是群G₁和G₂的元素，?是G₁×G₂→G₃的双线性映射，那么有：

?(ag₁, bg₂) = ab ?(g₁ , g₂) = ?(abg₁ , g₂) = ?(g₁ , abg₂)

?(ag₁, bg₂) + ?(cg₁, dg₂) = (ab+cd) ?(g₁, g₂)

注意这里G₃的群运算用加法表示了，如果用乘法表示则看起来会不同，但是本质一样，写成加法还是乘法只是符号的问题。

本文约定都按照加法形式处理（这里的加法并不暗示群一定是交换群），但通常习惯将G₃写成乘法群的形式，如下：

双线性对在密码学中的应用（下）

综上我们可以看到双线性使得变量前面的系数可以灵活转化，这是正是双线性对独特的性质。利用这些性质，双线性对在密码学中可用来构造很多其他数学工具所不能构造的协议或方案。

▲ SM9密钥协商算法解析

首先我们来理解双线性对在SM9算法中起到的作用。

下面的介绍中的签名算法是简化后的版本，能够体现算法原理，但是并非SM9标准算法本身，签名算法的完整流程可以参看参考文献中的GM/T0044标准。

因为使用到双线性配对，这里涉及到三个椭圆曲线群，我们记为G₁、G₂和G₃，e是从G₁×G₂到G₃的双线性映射，G₁和G₂的生成元分别为P₁、P₂。并且设e(P₁, P₂)=P₃ ∈ G₃。

在签名和验签之前，还需要经历生成主密钥、生成用户密钥两个步骤，主密钥只需要生成一次并由密钥生成中心保管，而用户密钥生成则需要为每个用户生成一次。

双线性对在密码学中的应用（下）

可以看到相对于ECDSA算法，SM9的密钥生成相对要复杂一些。这里的巧妙之处在于将H(ID)+ks的逆元隐藏在用户私钥中，稍后这一逆元也会影响到签名和验签。

双线性对在密码学中的应用（下）

签名和验签算法的巧妙之处在于计算hash时拼接了re(P₁,Ps)，从而将rPs隐藏在hash结果中，验签算法正是通过S和公钥计算rPs的过程——如果签名中的h和S是正确的，那么按照验签流程应该能够计算出同样的rPs，然后同样计算H(M||rPs)，如果该值和h一致，那么签名被认为是合法的。

而验签算法中计算rPs的过程正是利用了双线性映射。验签的第三步骤中通过e(P₁,Ps)约减掉了之前提到的H(ID)+ks，从而得到结果。

这个具体过程可以看下面的式子，这个式子也恰好是SM9签名算法正确性的简单证明：

双线性对在密码学中的应用（下）

▲ 三方一轮密钥协商算法解析

该算法的关键在于三方独立计算出的a?(bG, cG)、b?(aG , cG) 和c?(aG, bG)要相同，否则就无法协商出一致的密钥。

但是根据双线性对能够将每个参数的系数提出来的这个性质，我们有：

a?(bG, cG) = abc?(G , G)

b?(aG , cG) = abc?(G , G)

c?(aG, bG) = abc?(G , G)

因此三方计算出的密钥k是相同的，上面三个式子也恰好是该算法正确性的简单证明。

双线性对的实现

本文的最后，我们来了解一些双线性对已有的代码应用实现。

自Weil提出双线性对概念时构造出Weil对以来，后续的密码学家提出很多新的双线性对的构造，例如Tata对、Ate对、Rate对、最优对等。

虽然双线性对有诸多优点，但是其计算开销往往较大。

例如基于配对的BLS签名，虽然可以方便的实现签名聚合，但是其验签时间相对于传统的ECDSA签名上升了两个数量级。因而不断研究各种配对函数主要也是为了降低配对函数计算的复杂度，从而使双线性对这个工具更有实用性。

另外需要强调的是，并非基于任何椭圆曲线都可以构造配对函数，对于能有效实现双线性对的椭圆曲线，称为pairing-friendly curves。

BN曲线曾是配对友好曲线的代表，在go语言代码包golang.org/x/crypto/bn256中提供了基于BN256曲线的双线性对实现，并且该代码包中提供了使用BN256完成一轮三方密钥协商的测试示例。

下图是该代码包的介绍性注释：

双线性对在密码学中的应用（下）

不幸的是，2016年的研究（https://moderncrypto.org/mail-archive/curves/2016/000740.html)指出BN曲线配对在NFS数域筛算法的攻击下达不到宣称的安全等级（在新攻击方法下估计强度大约减少1/4）。

此发现的影响范围非常广，至少波及zcash等项目使用的zkSNARK实现、Apache Milagro项目、以太坊、任何使用相关曲线的BBS签名和BLS签名等，可能影响到intel的SGX和EPID安全性。

鉴于此，该代码仓库不再做维护。

但是也不必沮丧，回顾《双线性对在密码学中的应用（上）》那句话，进攻和防守只是同一件事的不同方面，这一发现只会促进安全性的又一次进步。

首先对于BN曲线，仍然可以通过提高参数长度来弥补漏洞。建议将曲线大小提高1/3从而到达相同的安全等级。另外，除去BN曲线，仍然有其他可用于配对的曲线可以选择。IEFT审议的草案pairing-friendly-curve的第七个版本（https://tools.ietf.org/pdf/draft-irtf-cfrg-pairing-friendly-curves-07.pdf）已经完全考虑到相关攻击的影响，因此该草案中推荐的曲线目前是安全的。

对于128位安全级别，草案推荐嵌入度为12的381位特征的BLS曲线和462位特征的BN曲线，对于256位的安全级别，推荐嵌入度为48且具有581位特征的BLS曲线。

从代码实现的角度来看，PBC（https://crypto.stanford.edu/pbc/）库和Miracl（https://miracl.com/）库是两个较优的选择。