橢圓曲線和超橢圓曲線上標(biāo)量乘的快速計算.pdf

1、橢圓曲線密碼體制(ECC)是建立在橢圓曲線離散對數(shù)問題基礎(chǔ)上的。在實現(xiàn)ECC中的加解密計算時，標(biāo)量乘（點乘）是其中一個基本的運算。所謂標(biāo)量乘就是將橢圓曲線上的一個有理點連續(xù)相加若干次，其中相加的次數(shù)是一個整數(shù)，稱之為標(biāo)量。
　　 將整數(shù)標(biāo)量表示為特殊的形式可以降低標(biāo)量的海明重量（非零比特的個數(shù)），從而加快標(biāo)量乘的計算，比如非鄰接表示(Non-Adjacent Form，NAF)和滑動窗口表示(wNAF)的方法。這些傳統(tǒng)的標(biāo)量乘算

2、法主要是基于標(biāo)量的二進(jìn)制表示的。使用兩個或者多個基來表示整數(shù)標(biāo)量，可以進(jìn)一步降低標(biāo)量的海明重量，比如Doche等人提出的雙基鏈法就是以2和3為基來表示標(biāo)量。之后還出現(xiàn)了幾個雙基鏈的擴(kuò)展算法，比如多基鏈、擴(kuò)展的雙基鏈、基于樹的雙基鏈等。這類基于雙基鏈的整數(shù)表示，都是通過貪心算法編碼獲得的，很難精確計算出它們的平均海明重量。于是，這些使用雙基鏈或多基鏈的標(biāo)量乘算法中參數(shù)的設(shè)置是通過經(jīng)驗或者仿真實驗來進(jìn)行的，而這些算法的平均時間復(fù)雜性也很難精

3、確分析。此外，編碼算法本身的運行速度有時會變慢。
　　 Longa和Miri提出的多基NAF、窗口多基NAF和擴(kuò)展窗口多基NAF，是另一種雙基、多基表示。本文討論了擴(kuò)展的窗口多基表示，對其分析得到了它的精確平均海明重量，進(jìn)而計算出使用它的標(biāo)量乘算法的平均時間復(fù)雜性。說明了多基NAF和窗口多基NAF都是擴(kuò)展窗口多基NAF的特殊情況。正是因為可以對擴(kuò)展的窗口多基NAF進(jìn)行精確的形式化分析，該算法中的參數(shù)可以根據(jù)不同情況方便的選取，使

4、該標(biāo)量乘算法達(dá)到最快。分析結(jié)果表明，在大素數(shù)域上進(jìn)行標(biāo)量乘計算時，擴(kuò)展窗口多基NAF算法跟類雙基鏈法相比更快，并且其編碼算法如傳統(tǒng)的NAF算法一樣簡單和快速。
　　 Smart等人曾多次研究了在特征為3的域上如何快速計算標(biāo)量乘。，本文在特征為3的域上，分別改進(jìn)了投影、雅可比和LD坐標(biāo)系上的點運算公式。特別是三倍點和倍點-點加運算公式的加快，使得擴(kuò)展窗口多基NAF算法在這種情況下可以大大提高標(biāo)量乘的計算速度。新設(shè)計的快速點運算公式

5、與Smart的相比，速度提高了4％-15％。在不需要額外存儲空間的情況下，使用改進(jìn)后的點運算公式的擴(kuò)展窗口多基NAF算法比Smart等人的“三倍點-點加”算法快了22.5％。如果有足夠的存儲空間，新算法比Smart等人的快了37.1％。
　　 在特征為2的域上計算標(biāo)量乘時，Bernstein等人曾提出使用二元Edwards曲線來加快計算速度。在二元域上，一條普通的橢圓曲線有多個有理等價的二元Edwards曲線。那么在將普通曲線轉(zhuǎn)

6、換為二元Edwards曲線時，可以挑選參數(shù)是稀疏整數(shù)（非零比特數(shù)目很少）的二元Edwards曲線來加快標(biāo)量乘的計算。本文通過代數(shù)變換，提出了更快的算法來將一般曲線變換為等價的二元Edwards曲線。在某些已有的數(shù)論、密碼學(xué)函數(shù)庫的實現(xiàn)中，域上的求逆、求元素的跡等運算與乘法相比的比率比較大，這時新算法的時間復(fù)雜性明顯較低。比如使用NTL5.4.2或者M(jìn)agma進(jìn)行仿真實驗時，新算法的速度可以提高23.3％-16.6％。
　　 超橢

7、圓曲線上的標(biāo)量乘與橢圓曲線上的非常相似，但是其上的除子運算公式要復(fù)雜很多。蒙特卡洛梯度算法是一個經(jīng)典的標(biāo)量乘算法，使用它可以有效抵抗簡單邊帶信道攻擊。本文在特征為2的域上，通過改進(jìn)超橢圓曲線上的除子加法運算公式，來加速超橢圓曲線上的蒙特卡洛梯度算法。在特征為2的域上，新的運算公式的運行速度在投影坐標(biāo)系和Lange提出的兩種新坐標(biāo)系上比之前的公式均有所提高。特別是在類型Ⅱ的曲線上，新公式比之前的公式快了4％-8.3％。
　　 雙核

8、及多核處理器的廣泛應(yīng)用，促使人們研究如何并行實現(xiàn)橢圓曲線密碼體制中的運算。Mishra曾首次考慮將流水線方法和點運算公式原子化的方法相結(jié)合，設(shè)計適用于雙核環(huán)境下且可以抵抗邊帶信道攻擊的標(biāo)量乘計算方案，但是他只考慮了雅可比坐標(biāo)系。本文進(jìn)一步將Edwards曲線、反向Edwards曲線和扭曲Edwards曲線上的點運算公式原子化，設(shè)計出新的標(biāo)量乘計算方案。如果使用傳統(tǒng)的NAF算法計算標(biāo)量乘，新方案比Mishra的快了12.5％。如果使用窗口