雙線性對的快速計算研究.pdf

1、基于身份的密碼體制是現(xiàn)代密碼學的一個研究熱點，它降低了公鑰密碼系統(tǒng)中可信第三方管理公鑰證書的復雜度。目前許多基于身份的密碼方案都使用了橢圓曲線上的雙線性對。為了使這些方案能夠在工程實踐中應用，對選取的橢圓曲線提出了一些限制：(1)為了保證系統(tǒng)的安全性，要求選取的橢圓曲線具有一個大素數(shù)階的子群并且雙線性對所映射到的有限域擴域應足夠大，一般不能小于960比特；(2)從系統(tǒng)的計算效率考慮，要求雙線性對所映射到的有限域擴域的階應足夠小。為了滿足

2、前述的兩個條件，要求橢圓曲線具有適宜的嵌入次數(shù)。
　　 超奇異橢圓曲線的嵌入次數(shù)≤6，但它們的群結(jié)構(gòu)比較簡單，存在易受攻擊的風險。為了提高系統(tǒng)的安全級別，通常會采用非超奇異橢圓曲線。但具有較小嵌入次數(shù)的非超奇異橢圓曲線很稀少，很難通過隨機選取的方式尋找到，需要設計專門的方法來構(gòu)造。目前在能有效構(gòu)造具有較小嵌入次數(shù)的非超奇異橢圓曲線的方法中，分圓多項式與有理多項式的合成多項式的可約分性起著重要的作用。但可約分的合成多項式的分布很稀

3、疏。
　　 在基于身份的密碼體制中，雙線性對的計算決定著整個系統(tǒng)的效率。通常采用Miller算法來計算雙線性對。在Miller算法中許多運算在有限域的擴域中進行，為了提高計算效率，應盡量減少擴域中的乘法運算和求逆運算的次數(shù)。
　　 論文對分圓多項式與有理多項式的合成多項式的可約分性，雙線性對的快速計算以及多核處理器環(huán)境下雙線性對的并行計算進行了研究，取得以下主要結(jié)果。
　　 (1)給出了分圓多項式與有理多項式的合

4、成多項式可約分的充分必要條件。根據(jù)這個充要條件，提出了一種通過構(gòu)造分圓域的單代數(shù)擴域，然后利用本原元定理來構(gòu)造可約分的分圓多項式與有理多項式的合成多項式的方法。該方法可以構(gòu)造出所有使?jié)M足條件的有理多項式。
　　 (2)分析了雙線性對計算中所利用的循環(huán)控制多項式的性質(zhì)。在這個結(jié)論的基礎上，給出了構(gòu)造適合于雙線性對計算的非超奇異橢圓曲線時，選取適宜的橢網(wǎng)曲線參數(shù)的方法。還給出了利用分圓多項式與有理多項式的合成多項式的不可約分因子來生

5、成適合于雙線性對計算的非超奇異橢圓曲線，并運用Miller算法來計算Atei對時，循環(huán)次數(shù)達到理論下限的充要條件。
　　 (3)通過利用新Miller公式，改進了基于雙重基鏈的Tate對計算方法，大大減少了二倍乘運算和三倍乘運算的計算量。改進的方法與原方法比效率提高了約23％。
　　 (4)提出一種通過構(gòu)造具有一個階為Proth型素數(shù)的子群的橢圓曲線來優(yōu)化雙線性對計算的方法。該方法減少了運用Miller算法計算雙線性對時

6、所需的加法運算的次數(shù)，而同時未降低子群階的漢明重量，保證了系統(tǒng)的安全性。
　　 (5)將從右至左重復加倍和加方法推廣到雙線性對的計算中。在Miller算法中采用從右至左的計算結(jié)構(gòu)，使得在同一輪循環(huán)中加法運算和二倍乘算不相關，從而可以利用處理器的兩個核來并行計算Tate對。
　　 (6)提出對Miller算法中的循環(huán)控制參數(shù)進行分解，從而將Miller公式分解為三個不相關的部分，然后利用多核處理器的三個不同的核來并行計算不