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

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

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

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

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

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

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

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

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

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

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

11、(基數(shù)≥2)的最優(yōu)帶符號數(shù)編碼GNAF(Generalized Nonadjacent Form)算法的實(shí)時性效率，證明此算法平均需要向右“掃描”E(d)=l+ 個數(shù)位即可確定當(dāng)前位置的編碼值，標(biāo)準(zhǔn)差σ(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)從左到右的編碼計(jì)算，其Hamming重量為 ，接近rNAF編碼算法的值。 4．改進(jìn)有限域GF(q)上的平方根算法。有限域GF(q)上計(jì)算平方根的算法，其中q=p<'m>，素?cái)?shù)p是有限域的特征，被應(yīng)用在二次域篩法，橢圓曲線素性檢測，以及橢圓曲線的點(diǎn)壓縮等算法中。Barreto在CRYPTO’2002上提出了適合

13、于一類有限域GF(p<'m>)的平方根算法，利用Frobenius映射和正規(guī)基表示，將算法的時間復(fù)雜性從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)，計(jì)

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

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