雙線性對(duì)的快速計(jì)算研究.pdf

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

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

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

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

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

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