手艺 | 双线性对在密码学中的应用(下)_星空首码对接团队长

科普 | ETH2.0将启动的PoS(权益证明)有哪些优势?

导 读

若是体贴近年的密码学功效,可以发现双线性对作为一个基础的密码学工具一再泛起。双线性对是一种二元映射,它作为密码学算法的组织工具,在各区块链平台中广泛应用,好比零知识证实、聚合署名等手艺方案大多基于双线性对组织得来。

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

上篇回首

本文为下篇进阶篇,会从双线性对的性子最先着手,然后剖析三方一轮密钥交流和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/)库是两个较优的选择。

总 结

经由十余年的研究,双线性对的性子、实现方式等研究领域已经有了很大希望。

本文简要先容了双线性对在密码学中的应用,包罗双线性对的研究历程、双线性对的观点和性子以及双线性对的应用,主要包罗三方一轮密钥协商、SM9标识密码。

在学界对双线性对多年的研究之后,多线性映射作为一个自然而然的推广也获得越来越多的关注,是相关领域下一个值得期待的研究热门,我们会在以后的先容中分享,人人敬请期待!

参考文献与推荐阅读

[1] cl署名

https://www.iacr.org/archive/crypto2004/31520055/cl04.pdf

[2] 配对友好的曲线(RFC草案)

https://tools.ietf.org/pdf/draft-irtf-cfrg-pairing-friendly-curves-07.pdf

[3] 三方一轮密钥交流

https://xueshu.baidu.com/usercenter/paper/show?paperid=5521a92e88e750ae92df7b1cd8287452&site=xueshu_se

[4] 一个关于双线性对的综述

http://jos.org.cn/ch/reader/create_pdf.aspx?file_no=3651&journal_id=jos

[5] 基于BN曲线的双线性对实现

https://cryptojedi.org/papers/dclxvi-20100714.pdf

[6] SM9标识密码算法GMT0044

http://www.gmbz.org.cn/main/viewfile/20180110024900801385.html

作者简介

乔沛杨,来自趣链科技基础平台部 区块链密码学研究小组

.

比特币托管市场观察:潜在市场超1400亿美元,中国为何没有“灰度”?

人已赞赏
币圈资讯

数字钱币登上《人民日报海外版》,海内外专家看好这几点_空投网站

2020-11-30 20:00:17

币圈资讯

科普 | ETH2.0将启动的PoS(权益证实)有哪些优势?_mi链空投官网版下载

2020-11-30 20:00:43

0 条回复 A文章作者 M管理员
    没有人发言,快说说你的看法吧!
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索