雙線性對在密碼學中的應用(上)

導 讀

如果關心近年的密碼學成果,可以發現雙線性對作為一個基礎的密碼學工具頻頻出現。

雙線性對是一種二元對映,它作為密碼學演算法的構造工具,在各區塊鏈平臺中廣泛應用,比如零知識證明、聚合簽名等技術方案大多基於雙線性對構造得來。

本次將分為上、下兩個篇章講解雙線性對在密碼學中的應用。

本文為上篇入門篇,會從概念介紹、發展歷程、實際應用三個方面展開說明,下篇為進階篇,將從原理層面深入剖析。

雙線性對的研究歷程

▲ 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

作者簡介

喬沛楊

來自趣鏈科技基礎平臺部

區塊鏈密碼學研究小組

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读