橢圓曲線密碼中的有限域算術運算研究.pdf

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

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

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

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

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

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

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

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