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

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

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

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

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

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

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

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

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