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

如果我们关注最近的密码学成就，我们会发现双线性配对作为一种基本的密码学工具经常出现。双线性对是一种二元映射。作为密码算法的构造工具，它被广泛应用于各种区块链平台，如零知识证明、聚合签名等。

本文分为两章来说明双线性对在密码学中的应用。

第一部分回顾了双线性对在密码学中的应用（1）

本文是下一个高级部分。从双线性对的性质入手，分析了三方一轮密钥交换和SM9数字签名算法的原理，最后介绍了双线性对的一些优秀代码实现。

双线性对的性质简介

物业简介

在本科线性代数课程中，读者可能已经了解了线性映射的概念，但他们可能不熟悉双线性映射的概念。

当我们说函数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₁₁₁₁₁₁₁₁₁₁₁₁₁₁叻⻕

?（ag₁，bgс）=ab?（g₁，gс）=?（abg₁，gс）=?（g₁，abgс）

?（ag₁，bgс）+?（cg₁，dgс）=（ab+cd）?（g₁，gП）

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

在本文中，我们同意用加法的形式来处理它们（这里的加法并不意味着群必须是交换的），但我们通常用乘法群的形式来写g₃，如下所示：

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

综上所述，双线性使得变量前面的系数可以灵活地变换，这是双线性对的独特性质。利用这些性质，双线性对可以用来构造许多其它密码学工具无法构造的协议或方案。

SM9密钥协商算法分析

首先了解bilism9算法中的角色。

下面介绍的签名算法是一个简化版，可以反映算法的原理，但它本身并不是SM9标准算法。有关签名算法的完整过程，请参考参考文献中的GM/t0044标准。

由于采用双线性对，这里涉及三个椭圆曲线群，分别表示为G₁、GΨ和G₃。E是G₁×GΨ到G₃的双线性映射。G₁和GΨ的发生器分别为p₁和p₁。设e（P₁，PΨ）=P₃∈g₃。

在签名和验证之前，有两个步骤来生成主密钥和生成用户密钥。主密钥只需要生成一次并由密钥生成中心保存，而用户密钥生成则需要为每个用户生成一次。

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

可以看出，与ECDSA算法相比，SM9密钥生成相对复杂。这里的聪明之处在于将H（ID）+KS的逆元素隐藏在用户的私钥中，这也会影响以后的签名和验证。

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

签名和签名验证算法的聪明之处在于re（P₁），这样就可以将RPS隐藏在哈希结果中。签名验证算法是通过s和公钥计算RPS的过程。如果签名中的h和s是正确的，则根据签名验证过程计算相同的RPS，然后计算h（m | RPS）。如果值与H一致，则认为签名是合法的。

在签名验证算法中，利用双线性映射来计算RPS。在签名验证的第三步，用E（P₁，PS）减去H（ID）+KS得到结果。

这个具体过程可以从下面的公式中看出，这也是SM9签名算法正确性的一个简单证明：

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

三方一轮密钥协商算法分析

该算法的关键是三方独立计算的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对、速率对和最优等价。

虽然双线性对有许多优点，但其计算量往往很大。

例如，基于配对的BLS签名可以很容易地实现签名聚合，但其验证时间比传统的ECDSA签名高出两个数量级。因此，不断研究各种配对函数的主要目的是降低配对函数的计算复杂度，使双线性配对更具实用性。

此外，需要强调的是，配对函数不能基于任何椭圆曲线构造。对于能够有效地实现双线性配对的椭圆曲线，称之为对友好曲线。

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

下图显示了代码包的介绍性注释：

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

不幸的是，2016年的研究（https://moderncrypto.org/mail-archive/curves/2016/000740.html)指出在NFS数域过滤算法的攻击中，BN曲线对不能达到声明的安全级别（新的攻击方法估计强度降低了约1/4）。

这一发现的影响非常广泛，至少涉及到zcash等项目使用的zksnark实现、Apache Milagro项目、以太坊、BBS签名和使用相关曲线的BLS签名，可能会影响Intel SGX和EPID的安全性。

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

但没必要灰心丧气。回顾一下双线性对在密码学中的应用（第1部分）中的句子，攻击和防御只是同一事物的不同方面。这一发现只会促进安全性的另一次改进。

首先，对于BN曲线，可以通过增加参数长度来弥补漏洞。建议将曲线尺寸增加1/3，以达到相同的安全水平。此外，除了BN曲线，还有其他曲线可以用来配对。Left（LEFT.N:行情）考虑的第七版配对友好曲线草案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/)图书馆与奇迹（https://miracl.com/)图书馆是两个更好的选择。