线性代数特征多项式是什么（双线性对在密码学中的应用（下））

导读：近年来，双线性对作为密码学工具频频出现，尤其在各区块链平台中广泛应用。本次分为上、下两篇讲解双线性对在密码学中的应用。上篇回顾了双线性对在密码学中的应用概述，下篇将深入探究双线性对的性质、9数字签名算法、三方一轮密钥协商算法等，并了解双线性对的代码实现。

上篇回顾：双线性对在密码学中的应用

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

一、双线性对的性质介绍

▲ 性质介绍

在本科阶段的线性代数课程中，读者可能已习过线性映射的概念，但对双线性映射的概念可能会感到陌生。双线性映射是一种特殊的映射，满足可加性和齐次性。

例如，对于函数f(x)=3x，当输入两个值x1和x2时，f(x1+x2)=f(x1)+f(x2)，这就是可加性的体现。对于任意的常数k，f(kx)=kf(x)，这就是齐次性的体现。理解了线性映射后，双线性映射的理解就会相对容易。

双线性对是指群上元素满足双线性映射的三个群之间的关系。具体来说，G1、G2和G3是三个n阶循环群，一个双线性对（双线性映射）是从G1G2到G3的双线性映射，满足以下性质：

1. 双线性性：对于任意的g1∈G1，g2∈G2，有(ag1, bg2) = ab(g1, g2)。

2. 非退化性：存在g1，g2，使得(g1, g2)不为G3中的单位元。

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

简单来说，一个映射e能将G1和G2中的两个元素映射为G3中的一个元素，并且该映射满足双线性。这里的定义虽然严谨，但为了方便读者理解，我们可以通过类比来加深理解。例如，向量内积就满足双线性。

▲ 9密钥协商算法解析

9算法是一种基于双线性对的密钥协商算法。在签名和验签之前，需要经历生成主密钥、生成用户密钥两个步骤。主密钥只需要生成一次并由密钥生成中心保管，而用户密钥生成则需要为每个用户生成一次。相对于其他算法，9的密钥生成相对复杂。

其中的巧妙之处在于将H(ID)+ks的逆元隐藏在用户私钥中，这一逆元也会影响到签名和验签。签名和验签算法的巧妙之处在于计算hash时拼接了re(P1,Ps)，从而将rPs隐藏在hash结果中。验签算法正是通过S和公钥计算rPs的过程来验证签名的合法性。

这个具体过程可以通过公式来简单证明9签名算法的正确性。

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

该算法的关键在于三方独立计算出的a(bG, cG)、b(aG, cG) 和c(aG, bG)要相同，否则就无法协商出一致的密钥。但是根据双线性对的性质，我们可以证明三方计算出的密钥k是相同的。

二、双线性对的实现

自Weil提出双线性对概念以来，后续的密码学家提出了许多新的双线性对的构造方法。虽然双线性对有诸多优点，但其计算开销往往较大。例如基于配对的S签名，虽然可以方便的实现签名聚合，但其验签时间相对于传统的ECDSA签名上升了两个数量级。不断研究各种配对函数主要是为了降低配对函数计算的复杂度，从而使双线性对这个工具更有实用性。另外需要强调的是，并非任何椭圆曲线都可以构造配对函数，对于能有效实现双线性对的椭圆曲线，称为pairing-friendly curves。BN曲线曾是配对友好曲线的代表，但在某些攻击下可能无法达到宣称的安全级别。尽管如此，仍有其他可用于配对的曲线可以选择。IEFT审议的草案pairing-friendly-curve中推荐的曲线是安全的。对于代码实现，PBC和Miracl是两个较优的选择。

经过十余年的研究，双线性对的性质、实现方法等研究领域已经有了很大进展。本文简要介绍了双线性对在密码学中的应用，包括其研究历程、概念和性质以及应用。从代码实现的角度来看，双线性对的应用已经有很多优秀的实现可以参考。未来多线性映射作为双线性对的一个推广也将得到更多关注。我们期待在后续的分享中探讨更多相关内容。