橢圓曲線上快速標(biāo)量乘算法的研究.pdf

1、橢圓曲線密碼制(ECC)是1985提出的新公鑰體制，由于在保證相同安全強度下其所需的密鑰長度比RSA短，而特別適用于無線系統(tǒng)或存儲受限的設(shè)備。在許多安全標(biāo)準(zhǔn)中，如IPsec、WAPI、WPKI等，都已經(jīng)將其采用，在不遠的將來ECC會成為應(yīng)用標(biāo)準(zhǔn)中的首選算法。 在ECC的快速實現(xiàn)中，關(guān)鍵的運算是標(biāo)量乘法kP的計算，其中k為一個大整數(shù)而P為橢圓曲線上的一個點。因此標(biāo)量乘法的快速算法研究成為了許多密碼學(xué)家關(guān)心的問題。本文主要做了以下幾

2、方面的工作： (1)在標(biāo)量重編碼方面，采用回溯法設(shè)計出一種重編碼算法。該算法只須對標(biāo)量序列進行一次變換、至多四個中間變量及只需基于比特位比較賦值操作，效率更高、利于硬件實現(xiàn)標(biāo)量乘法，并證明了所得結(jié)果具有正則序列的性質(zhì)。將算法應(yīng)用到計算數(shù)字簽名中常用的gP+hQ時，得到g、h的具有最小聯(lián)合重量序列。 (2)在雙基數(shù)標(biāo)量乘算法方面，本文做了兩個工作： 第一引用一個新的數(shù)域系統(tǒng)一雙基數(shù)系統(tǒng)，減少標(biāo)量乘法中的上層運算。在

3、底層域上直接推導(dǎo)出直接計算3kp快速算法。最后結(jié)合直接計算2kp、2P±Q、3P±Q及3kP快速算法，給出基于雙基數(shù)的快速標(biāo)量乘新算法，該算法的效率優(yōu)于Dimitrov 算法及傳統(tǒng)標(biāo)量乘算法。 第二在改進二元域橢圓曲線上基于雙基數(shù)標(biāo)量乘法時，新設(shè)計的以1／2和3為基的雙基數(shù)編碼可結(jié)合直接計算3kP和折半運算?；谠撾p基數(shù)編碼的標(biāo)量乘算法只涉及到點加運算、折半運算、三倍點和直接計算3kP，底層域運算復(fù)雜性得到降低，在NIST推薦的

4、橢圓曲線上比Dimitrov算法效率提高70％以上，比Wong方法提高10％以上。 (3)在定點標(biāo)量乘算法的設(shè)計方面，本文主要做了三個工作： 第一給出一種標(biāo)量的串長加法鏈算法來提高橢圓曲線標(biāo)量乘法的效率。該標(biāo)量乘算法結(jié)合底層域直接計算2Q+P，2nR+S算法，使用大小窗口法將串長算法和滑動窗口算法結(jié)合，加法鏈長度、存儲空間和預(yù)計算都減少，其效率比二元法提高53％，比NAF法提高47.5％，比串長算法提高46.2％，比Wi

5、ndow法提高42.2％。 第二對傳統(tǒng)滑動窗口算法進行改進，首先利用預(yù)處理棧存儲非零窗口值與非零窗口權(quán)的指數(shù)，然后結(jié)合底層域直接計算2kR+S算法和預(yù)計算表提出了新的標(biāo)量乘算法。該算法以犧牲適量的存儲空間換取賦值階段效率的提高，并分析出在混合坐標(biāo)下，當(dāng)w=4時新算法比仿射坐標(biāo)下傳統(tǒng)滑動窗口算法效率提高約40.6％左右。第三利用NAF編碼，預(yù)計算表法和Yen-Laih法分別在三個階段對Lim-Lee算法進行優(yōu)化。該定點標(biāo)量乘算法在

6、賦值階段動態(tài)掃描矩陣寬度為w的非全零列窗口，結(jié)合2kP底層域快速算法和擴充過的預(yù)計算表來提高計算效率。當(dāng)位長是160時，新算法效率比Lim-Lee算法提高22.7％，192時提高23％，224時提高23.3％。 (4)研究Koblitz曲線上的快速標(biāo)量乘法，從整數(shù)k的TNAF出發(fā)，給出了基于Frobenius映射的兩種上層運算：Comb算法和窗口算法。算法對一定長度的序列預(yù)先計算其對應(yīng)的橢圓曲線上點保存，累加賦值階段充分使用該預(yù)