橢圓曲線和超橢圓曲線上標量乘的快速計算.pdf

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

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

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

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

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

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

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

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