密码学系列 - 双线性对

双线性对是一种二元映射，它作为密码学算法的构造工具，在各区块链平台中广泛应用，比如零知识证明、聚合签名等技术方案大多基于双线性对构造得来。线性映射一个函数f是线性的是指函数f满足可加性和齐次性，也就是：可加性：f(a)+f(b)=f(a+b)齐次性：f(ka)=kf(a)双线性映射和线性函数不同的点在于满足双线性的函数有两个输入，而且对这两个输入分别满足线性。一个映射e，能将G₁和G₂中的两个元素

搬砖魁首

18262人浏览 · 2021-02-02 10:55:30

搬砖魁首 · 2021-02-02 10:55:30 发布

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

线性映射

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

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

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

双线性映射

和线性函数不同的点在于满足双线性的函数有两个输入，而且对这两个输入分别满足线性。

一个映射e，能将G₁和G₂中的两个元素映射为G₃中的一个元素，并且该映射满足双线性。

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

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

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

双线性使得变量前面的系数可以灵活转化

基于双线性对的密码算法

三方一轮密钥协商

三方一轮密钥协商是一种可以在一轮交互内完成三方的密钥协商的密钥协商协议，效率高于DH密钥协商。传统的DH密钥协商可以完成两两之间的密钥协商。虽然能够通过两两之间多轮协商完成三方之间的密钥协商，但是增加了通信复杂度。

国密SM9算法

基于身份的密码体制（IBE）是公钥密码学的一个研究方向，其特点是直接用标识用户身份的字符串作为公钥。大家熟悉的国密SM9算法就属于该类算法，这是目前国产密码算法中唯一一个基于双线性对的密码算法。

SM9标识密码算法包括数字签名算法、密钥协商算法、加解密算法三部分。不同于传统签名算法的由用户随机选择私钥然后计算得到公钥的方式，SM9能够实现用户指定公钥，密钥生成中心通过公钥计算私钥。

这样可以将一些有意义的字符串，例如身份证号码、邮箱地址等作为用户公钥，从而能在公钥中直接反应出用户信息，这也是标识密码（IBC）的含义。这样可以将一些有意义的字符串，例如身份证号码、邮箱地址等作为用户公钥，从而能在公钥中直接反应出用户信息，这也是标识密码（IBC）的含义。

和一般签名验签不同的地方在于，密钥生成分为主密钥生成和用户密钥生成两部分，主私钥由密钥生成中心（KGC）保管。

在这里插入图片描述

BLS签名算法

BLS签名是Boneh、Lynn和Shacham三人基于双线性映射构造的短签名方案，其特性之一就是能用于构造聚合签名。

可以有效缩减PBFT类共识在区块头中存放的签名体积, 聚合签名只占 32 字节, 可以在区块中放更多笔的交易。

MOV攻击

又称MOV规约攻击，是Menezes、Okamoto和Vanstone三人的论文中提出的针对特殊椭圆曲线离散对数问题（ECDLP）的一种有效解法。通过双线性配对，将椭圆曲线上的离散对数问题规约成为某个乘法群上的离散对数问题，能够在亚指数步骤中计算ECDLP。

MOV攻击并非能作用于全部的椭圆曲线，而是只能对参数满足一定条件的曲线进行攻击。这促使人们在选择椭圆曲线参数时更加谨慎，更加注重抗MOV攻击。

例如国标《SM2椭圆曲线公钥密码算法》就充分重视了受到MOV攻击的可能性，不仅在第一部分《总则》中用附录A的部分篇幅介绍验证曲线参抗MOV攻击的方法，而且也在第五部分《参数定义》中给出了安全曲线的推荐参数。

缺点: 计算开销较大

配对函数并不那么高效, 验签时间相对于传统的ECDSA签名上升了两个数量级。

BLS 签名验证的复杂度要比 ECDSA 高上一个数量级。在验证区块中 1000 笔交易的聚合签名时，仍需要进行 1000 次配对计算，这可能比使用 ECDSA 时（对 1000 个单独签名进行验证）还要慢。唯一的好处在于，可以在区块中放更多笔的交易，毕竟聚合签名只占 32 字节。