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

導  讀

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

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

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

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

雙線性對的研究歷程

▲ 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計算ae(bG, cG)
5.B計算be(aG, cG)
6.C計算ce(aG, bG)

A、B、C分別計算出的結果就是協商出的金鑰。這個協議是雙線性配對在密碼學研究中的第一次正面應用。

SM9數字簽名演算法

SM9標識密碼演算法包括數字簽名演算法、金鑰協商演算法、加解密演算法三部分,我們主要來關注數字簽名演算法。

不同於傳統簽名演算法的由使用者隨機選擇私鑰然後計算得到公鑰的方式,SM9能夠實現使用者指定公鑰,金鑰生成中心透過公鑰計算私鑰。

這樣可以將一些有意義的字串,例如身份證號碼、郵箱地址等作為使用者公鑰,從而能在公鑰中直接反應出使用者資訊,這也是標識密碼(IBC)的含義。

簽名演算法包括引數生成、金鑰生成、簽名和驗籤等幾個步驟。和一般簽名驗籤不同的地方在於,金鑰生成分為主金鑰生成和使用者金鑰生成兩部分,主私鑰由金鑰生成中心(KGC)保管。

可以看到不論是在三方一輪金鑰協商中,還是在SM9簽名驗籤中,e都扮演了重要的角色。當不知道e是指什麼的情況下要理解上面兩個演算法是不現實的,而這個對映e也正是本文的核心:雙線性對映。

e的計算是一個計算複雜度較高的操作,我們不打算介紹關於e的原理和細節,讀者只需要瞭解e的一些屬性就足夠理解上面兩個例子的思想。

因為篇幅原因,雙線性對映的性質將在下篇介紹。在下篇的開始我們就會先幫助讀者理解什麼是雙線性,然後緊接著再回顧上面的兩個演算法,介紹並分析它們的思想和原理。

雙線性對的性質介紹

▲ 性質介紹

在本科階段的線性代數課程中,讀者可能已經學習過線性對映(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)

理解了線性,那麼雙線性就好理解很多。

和線性函式不同的點在於滿足雙線性的函式有兩個輸入,而且對這兩個輸入分別滿足線性。換言之,如果固定其中一個輸入使之成為一元函式,則這個一元函式滿足線性。

而雙線性對就是指群上元素滿足雙線性對映的三個群,它們的關係滿足雙線性,下面是定義:

綜上我們可以看到雙線性使得變數前面的係數可以靈活轉化,這是正是雙線性對獨特的性質。利用這些性質,雙線性對在密碼學中可用來構造很多其他數學工具所不能構造的協議或方案。

▲ SM9金鑰協商演算法解析

首先我們來理解雙線性對在SM9演算法中起到的作用。

下面的介紹中的簽名演算法是簡化後的版本,能夠體現演算法原理,但是並非SM9標準演算法本身,簽名演算法的完整流程可以參看參考文獻中的GM/T0044標準。

可以看到相對於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簽名演算法正確性的簡單證明:

▲ 三方一輪金鑰協商演算法解析

該演算法的關鍵在於三方獨立計算出的ae(bG, cG)、be(aG , cG) 和ce(aG, bG)要相同,否則就無法協商出一致的金鑰。

但是根據雙線性對能夠將每個引數的係數提出來的這個性質,我們有:

ae(bG, cG) = abce(G , G)
be(aG , cG) = abce(G , G)
ce(aG, bG) = abce(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. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读