硬核 | 双线性对在密码学中的应用(上)_绝地求生那个空投的网址是多少

观察 | 建行区块链债券发行取消,数字金融创新风险仍需警惕

导 读

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

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

本文为上篇入门篇,会从观点先容生长历程现实应用三个方面睁开说明,下篇为进阶篇,将从原理层面深入剖析。

双线性对的研究历程

▲ 1946年作为一个数学工具被提出(Weil对)

1946年双线性对首先被法国数学家Weil提出并成为代数几何领域主要的观点和研究工具。

在最初的时刻,双线性对的观点并非为了密码学的研究,甚至Weil在提出双线性对时现代密码学还未成为系统的科学(3年后C.E.香农揭晓著名论文《保密系统的通讯理论》奠基现代密码学理论基础,而公钥密码学的生长更在30年之后)。

▲ 1996年Menezes、Okamoto和Vanstone提出行使双线性对将ECDLP问题规约到DLP问题的MOV攻击

在19年火热的影戏《罗小黑战记》中,主人公拥有控制自己“领域”的能力。影戏中的“领域”指自己专有的一个空间,在此空间中可以主宰一切。

不严谨的说,双线性映射的功效也有几分相似——虽然攻击椭圆曲线系统在离散数域解决起来很难,然则若是被映射到特定的扩域从而规约为一样平常的离散对数问题,解决起来就相对容易。

但与攻击椭圆曲线系统的目的恰恰相反,MOV(一种攻击手段,详细说明见文末)最终促进了椭圆曲线密码学的生长。

这固然也是密码学家去研究攻击方式的本意——究竟攻和防从来都是对立统一的两个方面而已。

MOV攻击并非能作用于所有的椭圆曲线,而是只能对参数知足一定条件的曲线举行攻击。这促使人们在选择椭圆曲线参数时加倍郑重,加倍注重抗MOV攻击。

今天我们再选用椭圆曲线参数时都市思量避开MOV攻击的条件从而使所选的参数更平安。

例如国标《SM2椭圆曲线公钥密码算法》就充实重视了受到MOV攻击的可能性,不仅在第一部门《总则》中用附录A的部门篇幅先容验证曲线参抗MOV攻击的方式,而且也在第五部门《参数界说》中给出了平安曲线的推荐参数。

▲2000年双线性对最先在密码学领域获得重视,功效有基于身份的密码体制(IBE)、三方一轮密钥协商、BLS署名算法等

基于身份的密码体制是公钥密码学的一个研究偏向,其特点是直接用标识用户身份的字符串作为公钥。人人熟悉的国密SM9算法就属于该类算法,这是现在国产密码算法中唯一一个基于双线性对的密码算法

三方一轮密钥协商是一种可以在一轮交互内完成三方的密钥协商的密钥协商协议,效率高于DH密钥协商。

传统的DH密钥协商可以完成两两之间的密钥协商。虽然能够通过两两之间多轮协商完成三方之间的密钥协商,然则增加了通讯复杂度。

基于双线性对能够在三方之间通过一轮通讯完成密钥协商,大大降低了通讯复杂度。

BLS署名是Boneh、Lynn和Shacham三人基于双线性映射组织的短署名方案,其特征之一就是能用于组织聚合署名。

除了上述的代表功效,双线性对在隐私珍爱方面、可证实执行可信盘算等方面也有大量功效,例如可信盘算组(The Trusted Computing Group ,TCG)在可信平台模块规范中推荐的椭圆曲线直接匿名证实协议(ECDAA),适用于通用问题的零知识证实(zk-SNARK),intel的可信盘算环境SGX以及增强隐私ID(EPID)等。

双线性对的应用

虽然双线性对有大量的应用案例,然则限于篇幅,本文挑选了三方一轮密钥交流SM9数字署名算法作为例子。

本部门先将算法历程剥离开来,还没有太多去剖析算法的原理,这是由于在不领会双线性对的前提下明白这些算法是有难题的。

我们建议读者先简朴阅读本部门领会算法能实现的功效,然后在阅读下篇的双线性对的性子先容后再回来品味算法的优美。

▲三方一轮密钥交流

密钥交流(key exchange)又叫密钥协商(key agreement),是一种能够让参与者在公共信道上通过交流某些信息来公共确立一个共享密钥的密码协议。

最常见的是两方DH密钥交流,椭圆曲线群上的DH(ECDH)依据的椭圆曲线群是循环群这个性子。

如下图:

1.用户A天生随机数a,盘算aG,并将aG发送给对方

2.用户B天生随机数b,盘算bG,并将bG发送给对方

3.A和B行使手中信息划分盘算出abG作为协商密钥,缘故原由是abG = baG

通过上述的DH算法可以轻松地完成两方的密钥协商,然则较难知足需要三方密钥协商的场景。

行使双线性对可以仅做一轮通讯完成密钥协商。

如下图所示:

1.A选择随机数a,盘算aG,将效果发送给B和C

2.B选择随机数b,盘算bG,将效果发送给A和C

3.C选择随机数c,盘算cG,将效果发送给A和B

4.A盘算a𝑒(bG, cG)

5.B盘算b𝑒(aG, cG)

6.C盘算c𝑒(aG, bG)

A、B、C划分盘算出的效果就是协商出的密钥。这个协议是双线性配对在密码学研究中的第一次正面应用。

SM9数字署名算法

SM9标识密码算法包罗数字署名算法密钥协商算法加解密算法三部门,我们主要来关注数字署名算法

差别于传统署名算法的由用户随机选择私钥然后盘算获得公钥的方式,SM9能够实现用户指定公钥,密钥天生中央通过公钥盘算私钥。

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

署名算法包罗参数天生、密钥天生、署名和验签等几个步骤。和一样平常署名验签差别的地方在于,密钥天生分为主密钥天生和用户密钥天生两部门,主私钥由密钥天生中央(KGC)保管。


可以看到不论是在三方一轮密钥协商中,照样在SM9署名验签中,𝑒都扮演了主要的角色。当不知道𝑒是指什么的情况下要明白上面两个算法是不现实的,而这个映射𝑒也正是本文的焦点:双线性映射

𝑒的盘算是一个盘算复杂度较高的操作,我们不计划先容关于𝑒的原理和细节,读者只需要领会𝑒的一些属性就足够明白上面两个例子的头脑。

由于篇幅缘故原由,双线性映射的性子将在下篇先容。在下篇的最先我们就会先辅助读者明白什么是双线性,然后紧接着再回首上面的两个算法,先容并剖析它们的头脑和原理。

更多精彩敬请期待下篇

本文有任何问题迎接与我们一起探讨

名词解释

▲ MOV攻击

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

▲ DLP

离散对数问题。例如在整数模11乘法群中容易盘算5×5×5×5=9 mod 11,那么求几个5相乘的效果是9这个问题就是一个离散对数问题。当模数为很大的质数时,这个问题是难题的。

▲ ECDLP

椭圆曲线离散对数问题。例如已知P、Q是两个椭圆曲线点,而且4个P相加获得Q,那么已知P和Q求解几个P相加获得Q的问题就是椭圆曲线离散对数问题。当选择的曲线知足一定要求时,该问题是难题的。

参考文献与推荐阅读

[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

作者简介

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

揭秘Gitcoin:以太坊生态的“军火库”

人已赞赏
币圈资讯

科普 | NFT生长简史_新项目内测首码空投网

2020-11-25 19:58:56

币圈资讯

考察 | 建行区块链债券刊行作废,数字金融创新风险仍需小心_vvbtc交易所糖果空投网

2020-11-25 19:59:45

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