背景介紹

技術(shù)博客已經(jīng)好久沒更新了。倒不是因?yàn)闆]得寫，是因?yàn)閷?shí)在是太忙了，而且研究也到了一個(gè)瓶頸期，需要大量閱讀文獻(xiàn)。

本來打算很長一段時(shí)間都不更新博客了，甚至打算等我畢業(yè)工作后再更新一些有價(jià)值的博客，但是最近在CSDN私信上和知乎上經(jīng)常收到求救帖子，希望我能寫一個(gè)jPBC使用方法的博客。甚至實(shí)驗(yàn)室的碩士生們也在各種咨詢我相關(guān)的問題。于是，我打算一勞永逸，寫一篇有關(guān)jPBC使用的博客。希望這個(gè)博客出來后，能解決絕大多數(shù)人的問題吧…
本篇博客期望解決的問題：

• 如何使用jPBC庫進(jìn)行雙線性群初始化，包括：
  
  • 質(zhì)數(shù)階雙線性群（Prime-Order Bilinear Groups）；
  • 合數(shù)階雙線性群（Composite-Order Bilinear Groups）；
• 如何使用jPBC庫執(zhí)行雙線性群運(yùn)算，包括：
  
  • 指數(shù)群Z的加法和乘法；
  • 雙線性群G的乘法和指數(shù)冪；
  • 目標(biāo)群GT的乘法和指數(shù)冪
  • 雙線性群G映射到目標(biāo)群GT的對（Pairing）運(yùn)算；
• 使用jPBC庫的一些注意事項(xiàng)。

本篇博客不會涉及到的問題：

• 如何配置jPBC庫到Eclipse中；這方面的內(nèi)容請參考我的另一篇博客：jPBC 2.0.0配置與測試（補(bǔ)充版）；
• 有關(guān)雙線性對的數(shù)學(xué)知識；這方面我在第二章會稍微介紹一下，但是不會詳談，因?yàn)閮?nèi)容太多了。
• 對偶雙線性群向量空間群（Dual Pairing Vector Space，DPVS）；這個(gè)群在理論上被用于替代合數(shù)階雙線性群。其可以在保證同等安全性的條件下，使雙線性對運(yùn)算時(shí)間較短，而代價(jià)是存儲開銷會變大。這個(gè)工具在2012年得到了廣泛的應(yīng)用。但是這兩年普遍認(rèn)為這個(gè)工具的進(jìn)一步應(yīng)用場景有限，而且表示并不直觀，還不如和合數(shù)階雙線性群好用。jPBC 2.0.0實(shí)際上提供了DPVS的實(shí)現(xiàn)，也是正確的。有興趣的朋友們可以自己研究一下，我在這里就不詳述了。
• 如何使用jPBC 2.0.0的多線性對（Multilinear Maps）函數(shù)庫；這方面我自己一直沒找時(shí)間測試一下多線性對函數(shù)庫，實(shí)際上近期我也不太想測試這個(gè)庫，主要有兩方面的原因。
  
  • 現(xiàn)在所構(gòu)造出來的多線性對并非密碼學(xué)中的理想多線性對（Ideal Multilinear Maps），而是候選多線性對（Candidate Multilinear Maps），后者在使用上有很多的限制。
  • jPBC 2.0.0實(shí)現(xiàn)的多線性對是[CLT-14]的方案，但這個(gè)方案已經(jīng)被證明是不安全的了。

雙線性群簡介

這里我直接引用自己的二篇水文來介紹（都是湊數(shù)用的…）選擇密文安全的身份及廣播加密方案，密碼學(xué)報(bào)，Experimental performance comparisons between (H) IBE schemes over composite-order and prime-order bilinear groups，IBCAST 2014。

質(zhì)數(shù)階雙線性群（Prime-Order Bilinear Groups）

質(zhì)數(shù)雙線性群可以由五元組(p,G1,G2,GT,e)來描述。五元組中p是一個(gè)與給定安全常數(shù)λ相關(guān)的大質(zhì)數(shù)，G1,G2,GT均是階為p的乘法循環(huán)群，e為雙線性映射e:G1×G2→GT，它滿足以下3個(gè)條件：

• 雙線性（Bilinearity）：對于任意的g∈G1，h∈G2，a,b∈Zp，有e(ga,hb)=e(g,h)ab；
• 非退化性（Non-degeneracy）：至少存在元素g1∈G1,g2∈G2，滿足e(g1,g2)≠1；
• 可計(jì)算性（Efficiency）：對于任意的u∈G1,v∈G2，存在一個(gè)與給定安全常數(shù)λ相關(guān)的多項(xiàng)式時(shí)間算法，可以高效地計(jì)算e(u,v)；

現(xiàn)在的密碼學(xué)相關(guān)論文中，習(xí)慣將G1,G2設(shè)置為乘法循環(huán)群。但是，基于橢圓曲線的雙線性群構(gòu)造中，G1,G2是加法群。所以在大約2005年以前的論文中，雙線性群一般寫成加法群形式。jPBC中將G1,G2表示稱為了乘法循環(huán)群，因此在實(shí)現(xiàn)寫成加法群形式的方案時(shí)，要注意將加法群改成乘法群的寫法再進(jìn)行實(shí)現(xiàn)。如何修改呢？很簡單，把加法群中的加法運(yùn)算寫成乘法運(yùn)算、把加法群中的乘法運(yùn)算寫成冪指數(shù)運(yùn)算即可。

合數(shù)階雙線性群（Composite-Order Bilinear Groups）

合數(shù)階雙線性群和質(zhì)數(shù)階雙線性群很類似，區(qū)別是G1,G2,GT的階數(shù)是一個(gè)合數(shù)N，其中N是一些大質(zhì)數(shù)的乘積，如N=p1p2?pn。同樣，e為雙線性映射e:G1×G2→GT，它滿足雙線性性、非退化性以及可計(jì)算性。

與質(zhì)數(shù)階雙線性群不同，合數(shù)階雙線性群中，GN有階數(shù)分別為p1,p2,?,pn的子群Gp1,?,Gpn。這些子群進(jìn)一步滿足正交特性。

對于所有的hi∈Gpi和hj∈Gpj，如果i≠j，那么e(hi,hj)=1
簡單地說就是，子群之間進(jìn)行雙線性運(yùn)算的結(jié)果必為1。

一些說明

首先，由于雙線性群現(xiàn)在的構(gòu)造是基于橢圓曲線的，而橢圓曲線上的元素是由坐標(biāo)(x,y)表示的，所以如果我們將G1,G2的結(jié)果輸出到Java的控制臺，我們得到的是一個(gè)坐標(biāo)。不過，GT是一個(gè)普通的Z群，所以其元素的表示是一個(gè)數(shù)。

其次，在密碼學(xué)中，如果G1=G2，我們稱這個(gè)雙線性群是對稱雙線性群（Symmetric Bilinear Group），否則稱之為非對稱雙線性群（Asymmetric Bilinear Group）。

是否為對稱雙線性群由選取的橢圓曲線種類決定。一般認(rèn)為，非對稱雙線性群要比對稱雙線性群更安全。特別地，現(xiàn)在已經(jīng)證明一些特定的對稱雙線性群是不安全的了。

現(xiàn)在jPBC可以使用的曲線為如下幾類：

• Type A
• Type A1
• Type D
• Type E
• Type F
• Type G

現(xiàn)在密碼學(xué)實(shí)現(xiàn)基本只使用Type A和Type A1的。前者為對稱質(zhì)數(shù)階雙線性群，后者為合數(shù)階對稱雙線性群。本博客也只在這兩類曲線上實(shí)驗(yàn)。其他類曲線的實(shí)現(xiàn)類似。由于是對稱雙線性群，本博客中G1,G2統(tǒng)一寫為G。

雙線性群初始化

在jPBC中，雙線性群的使用都是通過叫做Pairing的對象來實(shí)現(xiàn)的。雙線性群的初始化在jPBC中就是對Pairing對象的初始化。雙線性群有兩種初始化的方法。第一種是通過代碼動(dòng)態(tài)產(chǎn)生一個(gè)雙線性群，第二種是從文件中讀取參數(shù)而產(chǎn)生群。

通過代碼動(dòng)態(tài)產(chǎn)生

動(dòng)態(tài)產(chǎn)生的方法非常簡單，大概有如下步驟：指定橢圓曲線的種類、產(chǎn)生橢圓曲線參數(shù)、初始化Pairing。Type A曲線需要兩個(gè)參數(shù)：rBit是Zp中階數(shù)p的比特長度；qBit是G中階數(shù)的比特長度。代碼為：

TypeACurveGenerator pg = new TypeACurveGenerator(rBit, qBit); PairingParameters typeAParams = pg.generate(); Pairing pairing = PairingFactory.getPairing(typeAParams);

Type A1曲線需要二個(gè)參數(shù)：numPrime是階數(shù)N中有幾個(gè)質(zhì)數(shù)因子；qBit是每個(gè)質(zhì)數(shù)因子的比特長度。注意，Type A1涉及到的階數(shù)很大，其參數(shù)產(chǎn)生的時(shí)間也比較長。代碼為：

TypeA1CurveGenerator pg = new TypeA1CurveGenerator(numPrime, qBit); PairingParameters typeA1Params = pg.generate(); Pairing pairing = PairingFactory.getPairing(typeA1Params);

通過文件讀取產(chǎn)生

我們也可以選擇事先產(chǎn)生好參數(shù)，存放在文件中。以后再初始化的時(shí)候，直接從文件中讀取參數(shù)，就可以非?？焖俚某跏蓟p線性群。

PairingParameters支持toString()函數(shù)。實(shí)際上，我們可以直接將PairingParametersd的toString()存放在文件中。讀取的時(shí)候，通過讀取文件就可以直接初始化雙線性群了。

Type A曲線從文件中讀取參數(shù)初始化的代碼為：

TypeACurveGenerator pg = new TypeACurveGenerator(rBit, qBit); PairingParameters typeAParams = pg.generate(); //將參數(shù)寫入文件a.properties中，我用了Princeton大學(xué)封裝的文件輸出庫 Out out = new Out("a.properties"); out.println(typeAParams); //從文件a.properties中讀取參數(shù)初始化雙線性群 Pairing pairing = PairingFactory.getPairing("a.properties");

Type A1曲線從文件中讀取參數(shù)初始化的代碼為：

TypeA1CurveGenerator pg = new TypeA1CurveGenerator(numPrimes, qBit); PairingParameters typeA1Params = pg.generate(); //將參數(shù)寫入文件a1.properties中，同樣使用了Princeton大學(xué)封裝的文件輸出庫 Out out = new Out("a1.properties"); out.println(typeA1Params); //從文件a1.properties中讀取參數(shù)初始化雙線性群 Pairing pairing = PairingFactory.getPairing("a1.properties");

產(chǎn)生雙線性群中的隨機(jī)數(shù)

Type A中產(chǎn)生隨機(jī)數(shù)的方法很簡單，代碼為：

//隨機(jī)產(chǎn)生一個(gè)Z_p群的元素 Element Z_p = pairing.getZr().newRandomElement().getImmutable(); //隨機(jī)產(chǎn)生一個(gè)G_1群的元素 Element G_1 = pairing.getG1().newRandomElement().getImmutable(); //隨機(jī)產(chǎn)生一個(gè)G_2群的元素 Element G_2 = pairing.getG2().newRandomElement().getImmutable(); //隨機(jī)產(chǎn)生一個(gè)G_T群的元素 Element G_T = pairing.getGT().newRandomElement().getImmutable();

Type A1中產(chǎn)生隨機(jī)數(shù)的方法稍微有點(diǎn)麻煩。對于ZN和GT方法和Type A一樣。代碼為：

//隨機(jī)產(chǎn)生一個(gè)Z_N群的元素 Element Z_N = pairing.getZr().newRandomElement().getImmutable(); //隨機(jī)產(chǎn)生一個(gè)G_T群的元素 Element G_T = pairing.getGT().newRandomElement().getImmutable();

但是對于G就不同了。因?yàn)?span id="ze8trgl8bvbq" class="MathJax_Preview">G有子群Gpi，Type A1產(chǎn)生隨機(jī)數(shù)時(shí)需要指定生成元，橢圓曲線的參數(shù)，產(chǎn)生哪個(gè)子群的元素，以及Type A1一共有多少個(gè)子群。

假定我們產(chǎn)生的Type A1共有n個(gè)子群，這n個(gè)子群的階分別為p1,?,pn，產(chǎn)生隨機(jī)數(shù)的代碼如下：

TypeA1CurveGenerator pg = new TypeA1CurveGenerator(numPrimes, qBit); PairingParameters typeA1Params = pg.generate(); Pairing pairing = PairingFactory.getPairing(typeA1Params);//設(shè)定并存儲一個(gè)生成元。由于橢圓曲線是加法群，所以G群中任意一個(gè)元素都可以作為生成元 Element generator = pairing.getG1().newRandomElement().getImmutable(); //隨機(jī)產(chǎn)生一個(gè)G_p_1中的元素 Element G_p_1 = ElementUtils.getGenerator(pairing, generator, typeA1Params, 0, numPrimes).getImmutable(); //隨機(jī)產(chǎn)生一個(gè)G_p_2中的元素 Element G_p_2 = ElementUtils.getGenerator(pairing, generator, typeA1Params, 1, numPrimes).getImmutable(); // ...... //隨機(jī)產(chǎn)生一個(gè)G_p_n中的元素 Element G_p_n = ElementUtils.getGenerator(pairing, generator, typeA1Params, 1, numPrimes).getImmutable();

將指定的元素哈希到雙線性群中

由于雙線性群最初是用在基于身份的加密（Identity-Based Encryption）系統(tǒng)中，我們經(jīng)常會需要將一個(gè)特定的String或者byte[]哈希到雙線性群中。

jPBC支持將byte[]哈希到雙線性群的Z,G,GT中。但是，jPBC說明文檔中沒有提到的是，byte[]數(shù)組長度不能太長，如果過長會拋出異常。因此，我建議首先將byte[]用一個(gè)SHA256或者其他通用哈希函數(shù)哈希到固定長度，再用jPBC提供的函數(shù)哈希到雙線性群上。在這里我略去SHA256步驟，直接給出哈希到Z,G,GT群的代碼：

//將byte[] byteArray_Z_p哈希到Z_p群 Element hash_Z_p = pairing.getZr().newElement().setFromHash(byteArray_Z_p, 0, byteArray_Z_p.length); //將byte[] byteArray_G_1哈希到G_1群 Element hash_G_1 = pairing.getG1().newElement().setFromHash(byteArray_G_1, 0, byteArray_G_1.length); //將byte[] byteArray_G_2哈希到G_2群 Element hash_G_2 = pairing.getG2().newElement().setFromHash(byteArray_G_2, 0, byteArray_G_2.length); //將byte[] byteArray_G_T哈希到G_T群 Element hash_G_T = pairing.getGT().newElement().setFromHash(byteArray_G_T, 0, byteArray_G_T.length);

注意，對于Type A1來說，這個(gè)代碼無法指定哈希到指定子群Gpi中。解決方法是將byte[]先哈希到Z群，然后利用G,GT的生成元計(jì)算冪指數(shù)，從而達(dá)到哈希到G,GT上的效果。

雙線性群的運(yùn)算

雙線性群之間有如下運(yùn)算：
- G相關(guān)運(yùn)算：GZ, G×G；
- GT相關(guān)運(yùn)算：GZT, GT×GT；
- Z相關(guān)運(yùn)算：Z+Z, Z×Z；
- Pairing運(yùn)算

做運(yùn)算的時(shí)候要注意一下幾點(diǎn)：

Java的運(yùn)算結(jié)果都是產(chǎn)生一個(gè)新的Element來存儲，所以我們需要把運(yùn)算結(jié)果賦值給一個(gè)新的Element；

Java在進(jìn)行相關(guān)運(yùn)算時(shí)，參與運(yùn)算的Element值可能會改變。所以，如果需要在運(yùn)算過程中保留參與運(yùn)算的Element值，在存儲的時(shí)候一定要調(diào)用getImmutable()，具體方法見代碼中的初始化相關(guān)參數(shù)部分。

其實(shí)為了保險(xiǎn)起見，防止Element在運(yùn)算的過程中修改了Element原本的數(shù)值，可以使用Element.duplicate()方法。這個(gè)方法將返回一個(gè)與Element數(shù)值完全一樣的Element，但是是個(gè)新的Element對象。舉例來說，如果做G1×G1的運(yùn)算，可以寫成：

Element G_1_m_G_1 = G_1.duplicate().mul(G_1_p.duplicate());

G和G其實(shí)也是可以進(jìn)行冪指數(shù)運(yùn)算的，即GG，調(diào)用的函數(shù)為Element e1.pow(Element e2)。特別注意，我們再寫G群的Z次方運(yùn)算時(shí)，用的函數(shù)為powZn()，而不是pow()，這個(gè)調(diào)用錯(cuò)誤很容易使得程序的運(yùn)算結(jié)果不正確。

代碼如下：

//初始化相關(guān)參數(shù) Element G_1 = pairing.getG1().newRandomElement().getImmutable(); Element G_2 = pairing.getG2().newRandomElement().getImmutable(); Element Z = pairing.getZr().newRandomElement().getImmutable(); Element G_T = pairing.getGT().newRandomElement().getImmutable();Element G_1_p = pairing.getG1().newRandomElement().getImmutable(); Element G_2_p = pairing.getG2().newRandomElement().getImmutable(); Element Z_p = pairing.getZr().newRandomElement().getImmutable(); Element G_T_p = pairing.getGT().newRandomElement().getImmutable();//G_1的相關(guān)運(yùn)算 //G_1 multiply G_1 Element G_1_m_G_1 = G_1.mul(G_1_p); //G_1 power Z Element G_1_e_Z = G_1.powZn(Z);//G_2的相關(guān)運(yùn)算 //G_2 multiply G_2 Element G_2_m_G_2 = G_2.mul(G_2_p); //G_2 power Z Element G_2_e_Z = G_2.powZn(Z);//G_T的相關(guān)運(yùn)算 //G_T multiply G_T Element G_T_m_G_T = G_T.mul(G_T_p); //G_T power Z Element G_T_e_Z = G_T.powZn(Z);//Z的相關(guān)運(yùn)算 //Z add Z Element Z_a_Z = Z.add(Z_p); //Z multiply Z Element Z_m_Z = Z.mul(Z_p);//Pairing運(yùn)算 Element G_p_G = pairing.pairing(G_1, G_2);

總結(jié)

以上是生活随笔為你收集整理的Java密码学原型算法实现——第三部分：双线性对的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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