橢圓曲線密碼中的有限域算術(shù)運(yùn)算研究.pdf

1、橢圓曲線密碼算法(Elliptie Curve Cryptography，ECC)作為公鑰密碼學(xué)中的一個(gè)研究重點(diǎn)，在性能、安全方面都被證明有很大的優(yōu)勢(shì)。ECC的有效實(shí)現(xiàn)依賴于橢圓曲線群上的點(diǎn)乘和點(diǎn)加運(yùn)算的效率，而這兩種運(yùn)算則直接取決于定義曲線的有限域算術(shù)運(yùn)算的快速實(shí)現(xiàn)。有限域包括三種：素域GF(p)，二元擴(kuò)域GF-(2m)，一般擴(kuò)域GF(pm)(p>2)。目前對(duì)有限域算術(shù)運(yùn)算的實(shí)現(xiàn)方法主要是根據(jù)定義設(shè)計(jì)的，存在著算法效率不高，資源消耗較

2、多等問題。本文針對(duì)上述問題，對(duì)ECC所使用的有限域GF(2m)和G(pm)的算術(shù)運(yùn)算實(shí)現(xiàn)進(jìn)行了深入的研究，并且提出了有效的解決方案。本文的研究?jī)?nèi)容主要包括以下四個(gè)方面：
　　 首先，對(duì)GF(pm)的乘法快速實(shí)現(xiàn)進(jìn)行了研究。重點(diǎn)研究了基于中國剩余定理(Chinese Remainder Theorem，CRT)對(duì)模乘的優(yōu)化實(shí)現(xiàn)。利用二項(xiàng)式剩余算術(shù)(Binomial Residue，BR)較為簡(jiǎn)單的特點(diǎn)，提出了GF(pm)元素一種新

3、的表示方法，即BR表示，給出了對(duì)應(yīng)的BR-Montgomery乘法；針對(duì)最優(yōu)擴(kuò)域(Optimal ExtensionFields，OEF)所使用的不可約二項(xiàng)式存在數(shù)量較少的問題，利用BR表示構(gòu)造了一類不可約多項(xiàng)式，并對(duì)其存在的數(shù)量和分布進(jìn)行了預(yù)測(cè)，隨后研究了模乘的快速實(shí)現(xiàn)；使用快速傅利葉變換(Fast Fourier Transform，F(xiàn)FT)進(jìn)一步提升了BR-Montgomery乘法的實(shí)現(xiàn)速度，并使用相應(yīng)的技巧優(yōu)化了NTRU(Num

4、ber Theory Research Unit)密碼算法的實(shí)現(xiàn)。
　　 其次，研究了BR表示下GF(pm)的求逆運(yùn)算。提出了一種廣義歐幾里德算法的變形，進(jìn)一步完善基于BR表示的算術(shù)運(yùn)算系統(tǒng)；通過對(duì)不可約二項(xiàng)式進(jìn)行變換，提出了一種新的快速模乘算法，并研究了在BR表示下基于Frobenius映射的求逆算法。
　　 再次，研究了GF(2m)的并行乘法器設(shè)計(jì)。重點(diǎn)研究了基于Karatsuba-Offman算法的乘法器：提出了一

5、種Karatsuba算法的變形，在增加少量電路門的前提下，減小了整個(gè)乘法器的時(shí)延；結(jié)合移位多項(xiàng)式基(Shifted Polynomial Basis，SPB)與Karatsuba算法，構(gòu)造了兩類針對(duì)特殊三項(xiàng)式的并行乘法器，與已有的乘法器相比，空間和時(shí)間復(fù)雜度的綜合指標(biāo)要優(yōu)于已有的結(jié)果。
　　 最后，提出了三種基于Fermat小定理的GF(2m)的求逆算法：基于四次方的Itoh-Tsujii(IT)算法以及Takagi-Yoshi

6、ki-Takagi(TYT)算法的兩種改進(jìn)算法。其中，前一種算法使用快速四次方運(yùn)算代替平方運(yùn)算，減少了求逆算法的時(shí)延；后兩種算法則在不同環(huán)境下比原TYT算法使用更少的操作。
　　 本文創(chuàng)新性的工作描述如下：
　　 1.基于二項(xiàng)式剩余算術(shù)，提出了GF(pm)元素的BR表示；據(jù)此構(gòu)造了BR-Montgomery乘法，其計(jì)算復(fù)雜度為亞平方數(shù)量級(jí)，最低可達(dá)到O(m1.5)；針對(duì)BR表示提出了一種廣義歐幾里德的算法變型，可在該表示

7、下直接進(jìn)行求逆。
　　 2.利用BR表示構(gòu)造了一類不可約多項(xiàng)式，提出了一種模乘的快速實(shí)現(xiàn)算法；這種多項(xiàng)式與OEF通常使用的不可約二項(xiàng)式相比，存在數(shù)量更多、分布更廣，并且模乘效率在某些情況下更高，有效的擴(kuò)展了OEF的應(yīng)用范圍。
　　 3.在對(duì)Karatsuba算法進(jìn)行擴(kuò)展的基礎(chǔ)上，提出了一種基于不可約三項(xiàng)式的Karatsuba算法變型，主要目的在于減少Karatsuba并行乘法器的時(shí)延。該乘法器可達(dá)到與Mastrovito

8、并行乘法器相同的時(shí)延，且空間復(fù)雜度更低。此外，提出了兩類關(guān)于特殊三項(xiàng)式的Karatsuba乘法器，這兩種乘法器在達(dá)到目前現(xiàn)有并行乘法器最少時(shí)延的前提下，空間復(fù)雜度僅為同類乘法器的66％和62％，其空間和時(shí)間復(fù)雜度綜合指標(biāo)達(dá)到了最優(yōu)。
　　 4.提出了一種快速四次方運(yùn)算，并據(jù)此改進(jìn)了IT算法，減少了IT算法的時(shí)延。
　　 5.推廣和改進(jìn)了TYT求逆算法：提出了一種多項(xiàng)式基下的TYT算法，證明了該算法實(shí)際效率至少相當(dāng)于原TY