公鑰密碼體制中的若干算法研究.pdf

1、公鑰密碼體制在數(shù)字簽名、身份認證、電子支付等協(xié)議中具有不可替代的作用，而這些協(xié)議是保障電子商務安全的關(guān)鍵技術(shù)。公鑰密碼體制建立在數(shù)論和代數(shù)中的一些數(shù)學難題的基礎上，包含各種代數(shù)結(jié)構(gòu)(群，環(huán)，域)中的大整數(shù)或多項式的復雜運算，因此運算效率比較低、密鑰存儲空間大，這一直是制約公鑰密碼體制發(fā)展的重要因素。另外，一類利用密碼系統(tǒng)的運行過程中泄漏的計算時間、出現(xiàn)的差錯和電量消耗曲線等敏感信息進行攻擊的方式，即邊帶信道攻擊，能夠直接獲得秘密密鑰等關(guān)

2、鍵信息，或者可以結(jié)合其它密碼分析方法，大大降低密碼分析的代價，這給公鑰密碼體制的實現(xiàn)算法提出新的安全挑戰(zhàn)。于是，近幾年來，將公鑰密碼體制的有效性(計算效率高、存儲空間小)與抵御邊帶信道攻擊的安全性相結(jié)合來設計新的算法，成為密碼學領域的一個研究熱點。 本文的研究工作是圍繞著公鑰密碼體制的若干有效算法和抵御新型邊帶信道攻擊的安全算法而展開的，具體問題包括： (1) 公鑰密碼體制的有效算法。目前最主要的公鑰密碼體制，例如

3、RSA密碼，EIGamal系列密碼，橢圓曲線密碼，和基于雙線性配對的密碼協(xié)議，分別是建立在模n整數(shù)環(huán)，模p素域，有限域GF(q)上的橢圓曲線，以及雙線性配對(Weil和Tate配對)等代數(shù)結(jié)構(gòu)上。因此，提高這些代數(shù)結(jié)構(gòu)上的關(guān)鍵算法的計算效率，其意義尤為重要，而且算法的有效性不僅包括時間復雜性，還體現(xiàn)在可并行性、存儲空間占用、實時性等諸多方面。我們對公鑰密碼體制中的以下四個算法問題進行研究：大整數(shù)的Montgomery快速模乘算法，非稀疏

4、帶符號編碼的窗口算法，從左到右的基數(shù)r的帶符號編碼算法，有限域GF(q)上的平方根算法。 (2) 抵御邊帶信道攻擊的算法。P.Kocher提出的時間攻擊，D.Boneh提出的差錯攻擊，和P.Kocher提出的功耗攻擊是三類主要的邊帶信道攻擊方法。功耗攻擊是其中最強大的一種邊帶信到攻擊，尤其是近年來，一些研究者提出的針對橢圓曲線密碼的新型功耗攻擊方法，包括RPA攻擊(Refined Power Attack)，零值攻擊(Zer

5、o-value Point Attack)，和倍點攻擊(Doubling Attack)，對橢圓曲線密碼體制形成了新的威脅。我們的研究工作是，提出有效的抵御RPA攻擊、零值攻擊和倍點攻擊等新型功耗攻擊的算法。 本文主要的研究內(nèi)容和創(chuàng)新點包括： 1．Z<,n>環(huán)、GF(p)有限域上的改進Montgomery模乘算法。Montgomery算法是實現(xiàn)大整數(shù)模乘運算的最有效算法之一，是RSA密碼體制和橢圓曲線密碼運算中的基本運算

6、。我們利用Karatsuba-Ofman算法的思想，改進了Montgomery模乘的CIOS(Coarsely Integrated Operand Scanning)實現(xiàn)算法：一方面，改進后的CIOS算法在時間效率上有較大提高，將原來CIOS算法的2s<'2>+S次w位整數(shù)乘法減少到 s<'2>+ s次，減少的乘法次數(shù)比率接近25％；而且，改進后的算法具有更好的并行性，能夠?qū)崿F(xiàn)兩個w位乘法器的并行計算結(jié)構(gòu)，適合于設計高速的大整數(shù)模

7、乘密碼芯片。 2．非稀疏帶符號編碼的窗口算法的分析和注記。利用最優(yōu)帶符號編碼和滑動窗口實現(xiàn)橢圓曲線的點乘運算，是橢圓曲線密碼實現(xiàn)的有效算法。K.Koyama和T.Tsumoka在CRYPTO’1992上提出了第一個基于非稀疏帶符號編碼的窗口算法，稱為Koyama-Tsuruoka編碼。目前為止，E.De Win在ANTS’1998會議上，K.Okeya在CRYPTO’2004上，均認為Koyama-Tsuruoka編碼的窗口算法

8、的預計算次數(shù)的上界是2<'w-1>-1。關(guān)于Koyama-Tsumoka編碼的預計算窗口個數(shù)的計算，仍然是一個未解決的公開問題。我們的主要工作：首先，提出并且證明了關(guān)于Koyama-Tsuruoka編碼以及其它非稀疏最優(yōu)帶符號編碼的長度分布的性質(zhì)定理，證明了Koyama-Tsuruoka編碼的長度的下界為K+1/3，因此Koyama和T.Tsumoka提出的編碼長度K+1/4是錯誤的，這在算法性能的分析中有重要應用。然后，提出了一種新的

9、非稀疏最優(yōu)帶符號編碼的窗口算法，當選取橢圓曲線密碼體制最常用的窗口長度4,5,6,7時，新算法的連續(xù)零串的平均長度在1.5～1.625之間，優(yōu)于Koyama-Tsuruoka編碼的1.5值。最后，我們證明了非稀疏最優(yōu)帶符號編碼的預計算次數(shù)的上界為 ·2<'w-1>-1+(-1)<'w>/3，從而解決了Koyama-Tsuruoka編碼的窗口算法的預計算窗口個數(shù)的問題。 3．從左到右的基數(shù)，r的帶符號編碼算法。在基于雙線性配對的密

10、碼體制中，基數(shù)，r的帶符號編碼算法被用于特征為，r的超奇異橢圓曲線的有效計算。一個令人關(guān)注的問題是設計從左到右的帶符號編碼算法，R.M.Avanzi在SAC’2004，Katsuyuki Okeya在CRYPTO’2004，J.A.Muir在CT-RSA'2005，分別獨立地提出了從左到右的二進制的W-NAF編碼的等價算法。我們的工作是設計和分析基數(shù)r的從左到右的帶符號編碼算法。我們通過建立Markov鏈模型，分析了一種從左到右的高基

11、(基數(shù)≥2)的最優(yōu)帶符號數(shù)編碼GNAF(Generalized Nonadjacent Form)算法的實時性效率，證明此算法平均需要向右“掃描”E(d)=l+ 個數(shù)位即可確定當前位置的編碼值，標準差σ(d)= ，且滿足Pr[d>k]= ，k是正整數(shù)。T.Takagi等研究者在ISC’2004上提出的從右到左的rNAF(Radix-r Nonadjacent Form)編碼算法，是目前具有最小Hamming重量的基數(shù)r的帶符

12、號編碼形式。我們首先證明不存在從左到右的rNAF編碼算法，然后提出了一種新的從左到右的基數(shù)r的帶符號編碼算法，能夠?qū)崿F(xiàn)從左到右的編碼計算，其Hamming重量為 ，接近rNAF編碼算法的值。 4．改進有限域GF(q)上的平方根算法。有限域GF(q)上計算平方根的算法，其中q=p<'m>，素數(shù)p是有限域的特征，被應用在二次域篩法，橢圓曲線素性檢測，以及橢圓曲線的點壓縮等算法中。Barreto在CRYPTO’2002上提出了適合

13、于一類有限域GF(p<'m>)的平方根算法，利用Frobenius映射和正規(guī)基表示，將算法的時間復雜性從O(m<'3>log<'3>P)降低為O(m<'2>log<'2>p(10gm+logp))，其中p=3(mod 4)或p=5(mod 8)，且m是奇數(shù)。2004年，S.MUller在Designs，Codes and Cryptography上提出了一種廣義的Atkin平方根算法，在有限域GF(q)中，其中q=9(mod 16)，計

14、算域元素a∈GF(g)的平方根僅需要兩次GF(q)中的求冪運算。我們的主要工作：首先，改進了S.Mailer的廣義的Atkin平方根算法，改進后的算法平均需要1.5次GF(q)中的求冪運算，與S.Mtiller的算法相比，減少了25％的運算時間；然后，在一類有限域GF(p<'m>)中，當特征p滿足p=9(mod 16)，而且m是奇數(shù)時，利用Frobenius映射和正規(guī)基表示，將改進的廣義Atkin算法的時間復雜性從O(m<'3>log<

15、'3>p)降低為O(m<'2>log<'3>p(10gm+logp))，從而擴展了Barreto在CRYPTO，2002上的研究結(jié)果。 5．抵御RPA攻擊、ZPA攻擊和倍點攻擊等新型功耗攻擊的算法。首先，我們用Mamiya的隨機初始化點的思想，改進了Hitchcock的SPA抵御算法，得到的算法能夠抵御SPA，DPA和新型功耗攻擊(RPA，ZPA，Doubling攻擊)，在增加一個存儲點的代價下，需要的點運算個數(shù)比Mam