導(dǎo) 讀
如果關(guān)心近年的密碼學(xué)成果，可以發(fā)現(xiàn)雙線性對作為一個(gè)基礎(chǔ)的密碼學(xué)工具頻頻出現(xiàn)。
雙線性對是一種二元映射，它作為密碼學(xué)算法的構(gòu)造工具，在各區(qū)塊鏈平臺(tái)中廣泛應(yīng)用，比如零知識證明、聚合簽名等技術(shù)方案大多基于雙線性對構(gòu)造得來。
本次將分為上、下兩個(gè)篇章講解雙線性對在密碼學(xué)中的應(yīng)用。

本文為上篇入門篇，會(huì)從概念介紹、發(fā)展歷程、實(shí)際應(yīng)用三個(gè)方面展開說明，下篇為進(jìn)階篇，將從原理層面深入剖析。

雙線性對的研究歷程

▲ 1946年作為一個(gè)數(shù)學(xué)工具被提出（Weil對）

1946年雙線性對首先被法國數(shù)學(xué)家Weil提出并成為代數(shù)幾何領(lǐng)域重要的概念和研究工具。

在最初的時(shí)候，雙線性對的概念并非為了密碼學(xué)的研究，甚至Weil在提出雙線性對時(shí)現(xiàn)代密碼學(xué)還未成為系統(tǒng)的科學(xué)（3年后C.E.香農(nóng)發(fā)表著名論文《保密系統(tǒng)的通信理論》奠定現(xiàn)代密碼學(xué)理論基礎(chǔ)，而公鑰密碼學(xué)的發(fā)展更在30年之后）。

▲ 1996年Menezes、Okamoto和Vanstone提出利用雙線性對將ECDLP問題規(guī)約到DLP問題的MOV攻擊

在19年火熱的電影《羅小黑戰(zhàn)記》中，主人公擁有控制自己“領(lǐng)域”的能力。電影中的“領(lǐng)域”指自己專有的一個(gè)空間，在此空間中可以主宰一切。

不嚴(yán)謹(jǐn)?shù)恼f，雙線性映射的功能也有幾分相似——雖然攻擊橢圓曲線系統(tǒng)在離散數(shù)域解決起來很難，但是如果被映射到特定的擴(kuò)域從而規(guī)約為一般的離散對數(shù)問題，解決起來就相對容易。

但與攻擊橢圓曲線系統(tǒng)的目的恰恰相反，MOV（一種攻擊手段，詳細(xì)說明見文末）最終促進(jìn)了橢圓曲線密碼學(xué)的發(fā)展。

這當(dāng)然也是密碼學(xué)家去研究攻擊方法的本意——畢竟攻和防從來都是對立統(tǒng)一的兩個(gè)方面而已。

MOV攻擊并非能作用于全部的橢圓曲線，而是只能對參數(shù)滿足一定條件的曲線進(jìn)行攻擊。這促使人們在選擇橢圓曲線參數(shù)時(shí)更加謹(jǐn)慎，更加注重抗MOV攻擊。

今天我們再選用橢圓曲線參數(shù)時(shí)都會(huì)考慮避開MOV攻擊的條件從而使所選的參數(shù)更安全。

例如國標(biāo)《SM2橢圓曲線公鑰密碼算法》就充分重視了受到MOV攻擊的可能性，不僅在第一部分《總則》中用附錄A的部分篇幅介紹驗(yàn)證曲線參抗MOV攻擊的方法，而且也在第五部分《參數(shù)定義》中給出了安全曲線的推薦參數(shù)。

▲2000年雙線性對開始在密碼學(xué)領(lǐng)域得到重視，成果有基于身份的密碼體制（IBE）、三方一輪密鑰協(xié)商、BLS簽名算法等

基于身份的密碼體制是公鑰密碼學(xué)的一個(gè)研究方向，其特點(diǎn)是直接用標(biāo)識用戶身份的字符串作為公鑰。大家熟悉的國密SM9算法就屬于該類算法，這是目前國產(chǎn)密碼算法中唯一一個(gè)基于雙線性對的密碼算法。

三方一輪密鑰協(xié)商是一種可以在一輪交互內(nèi)完成三方的密鑰協(xié)商的密鑰協(xié)商協(xié)議，效率高于DH密鑰協(xié)商。

傳統(tǒng)的DH密鑰協(xié)商可以完成兩兩之間的密鑰協(xié)商。雖然能夠通過兩兩之間多輪協(xié)商完成三方之間的密鑰協(xié)商，但是增加了通信復(fù)雜度。

基于雙線性對能夠在三方之間通過一輪通信完成密鑰協(xié)商，大大降低了通信復(fù)雜度。

BLS簽名是Boneh、Lynn和Shacham三人基于雙線性映射構(gòu)造的短簽名方案，其特性之一就是能用于構(gòu)造聚合簽名。

除了上述的代表成果，雙線性對在隱私保護(hù)方面、可證明執(zhí)行、可信計(jì)算等方面也有大量成果，例如可信計(jì)算組（The Trusted Computing Group ，TCG）在可信平臺(tái)模塊規(guī)范中推薦的橢圓曲線直接匿名證明協(xié)議（ECDAA），適用于通用問題的零知識證明（zk-SNARK），intel的可信計(jì)算環(huán)境SGX以及加強(qiáng)隱私ID（EPID）等。

雙線性對的應(yīng)用

雖然雙線性對有大量的應(yīng)用案例，但是限于篇幅，本文挑選了三方一輪密鑰交換和SM9數(shù)字簽名算法作為例子。

本部分先將算法過程剝離開來，還沒有太多去分析算法的原理，這是因?yàn)樵诓涣私怆p線性對的前提下理解這些算法是有困難的。

我們建議讀者先簡單閱讀本部分了解算法能實(shí)現(xiàn)的功能，然后在閱讀下篇的雙線性對的性質(zhì)介紹后再回來品味算法的優(yōu)美。

▲三方一輪密鑰交換

密鑰交換（key exchange）又叫密鑰協(xié)商（key agreement），是一種能夠讓參與者在公共信道上通過交換某些信息來公共建立一個(gè)共享密鑰的密碼協(xié)議。

最常見的是兩方DH密鑰交換，橢圓曲線群上的DH（ECDH）依據(jù)的橢圓曲線群是循環(huán)群這個(gè)性質(zhì)。

如下圖：

1.用戶A生成隨機(jī)數(shù)a，計(jì)算aG，并將aG發(fā)送給對方

2.用戶B生成隨機(jī)數(shù)b，計(jì)算bG，并將bG發(fā)送給對方

3.A和B利用手中信息分別計(jì)算出abG作為協(xié)商密鑰，原因是abG = baG

通過上述的DH算法可以輕松地完成兩方的密鑰協(xié)商，但是較難滿足需要三方密鑰協(xié)商的場景。

利用雙線性對可以僅做一輪通信完成密鑰協(xié)商。

如下圖所示：

1.A選擇隨機(jī)數(shù)a，計(jì)算aG，將結(jié)果發(fā)送給B和C

2.B選擇隨機(jī)數(shù)b，計(jì)算bG，將結(jié)果發(fā)送給A和C

3.C選擇隨機(jī)數(shù)c，計(jì)算cG，將結(jié)果發(fā)送給A和B

4.A計(jì)算a𝑒(bG, cG)

5.B計(jì)算b𝑒(aG, cG)

6.C計(jì)算c𝑒(aG, bG)

A、B、C分別計(jì)算出的結(jié)果就是協(xié)商出的密鑰。這個(gè)協(xié)議是雙線性配對在密碼學(xué)研究中的第一次正面應(yīng)用。

SM9數(shù)字簽名算法

SM9標(biāo)識密碼算法包括數(shù)字簽名算法、密鑰協(xié)商算法、加解密算法三部分，我們主要來關(guān)注數(shù)字簽名算法。

不同于傳統(tǒng)簽名算法的由用戶隨機(jī)選擇私鑰然后計(jì)算得到公鑰的方式，SM9能夠?qū)崿F(xiàn)用戶指定公鑰，密鑰生成中心通過公鑰計(jì)算私鑰。

這樣可以將一些有意義的字符串，例如身份證號碼、郵箱地址等作為用戶公鑰，從而能在公鑰中直接反應(yīng)出用戶信息，這也是標(biāo)識密碼（IBC）的含義。

簽名算法包括參數(shù)生成、密鑰生成、簽名和驗(yàn)簽等幾個(gè)步驟。和一般簽名驗(yàn)簽不同的地方在于，密鑰生成分為主密鑰生成和用戶密鑰生成兩部分，主私鑰由密鑰生成中心（KGC）保管。

可以看到不論是在三方一輪密鑰協(xié)商中，還是在SM9簽名驗(yàn)簽中，𝑒都扮演了重要的角色。當(dāng)不知道𝑒是指什么的情況下要理解上面兩個(gè)算法是不現(xiàn)實(shí)的，而這個(gè)映射𝑒也正是本文的核心：雙線性映射。

𝑒的計(jì)算是一個(gè)計(jì)算復(fù)雜度較高的操作，我們不打算介紹關(guān)于𝑒的原理和細(xì)節(jié)，讀者只需要了解𝑒的一些屬性就足夠理解上面兩個(gè)例子的思想。

因?yàn)槠?#xff0c;雙線性映射的性質(zhì)將在下篇介紹。在下篇的開始我們就會(huì)先幫助讀者理解什么是雙線性，然后緊接著再回顧上面的兩個(gè)算法，介紹并分析它們的思想和原理。

更多精彩敬請期待下篇

本文有任何問題歡迎與我們一起探討

名詞解釋

▲ MOV攻擊

又稱MOV規(guī)約攻擊，是Menezes、Okamoto和Vanstone三人的論文中提出的針對特殊橢圓曲線離散對數(shù)問題（ECDLP）的一種有效解法。通過雙線性配對，將橢圓曲線上的離散對數(shù)問題規(guī)約成為某個(gè)乘法群上的離散對數(shù)問題，能夠在亞指數(shù)步驟中計(jì)算ECDLP。

▲ DLP

離散對數(shù)問題。例如在整數(shù)模11乘法群中容易計(jì)算5×5×5×5=9 mod 11，那么求幾個(gè)5相乘的結(jié)果是9這個(gè)問題就是一個(gè)離散對數(shù)問題。當(dāng)模數(shù)為很大的質(zhì)數(shù)時(shí)，這個(gè)問題是困難的。

▲ ECDLP

橢圓曲線離散對數(shù)問題。例如已知P、Q是兩個(gè)橢圓曲線點(diǎn)，并且4個(gè)P相加得到Q，那么已知P和Q求解幾個(gè)P相加得到Q的問題就是橢圓曲線離散對數(shù)問題。當(dāng)選擇的曲線滿足一定要求時(shí)，該問題是困難的。

參考文獻(xiàn)與推薦閱讀

[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] 一個(gè)關(guān)于雙線性對的綜述

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

[5] 基于bn曲線的雙線性對實(shí)現(xiàn)

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

[6] SM9標(biāo)識密碼算法GMT0044

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

作者簡介

喬沛楊

來自趣鏈科技基礎(chǔ)平臺(tái)部

區(qū)塊鏈密碼學(xué)研究小組

總結(jié)

以上是生活随笔為你收集整理的双线性对在密码学中的应用（上）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。