基于Hessian曲線(xiàn)的一種新的點(diǎn)加運(yùn)算以及在點(diǎn)乘中的應(yīng)用.pdf

1、自從Koblitz[1]和Miner[2]分別提出橢圓曲線(xiàn)加密技術(shù)(ECC)之后,它逐漸成為密碼學(xué)一個(gè)重要的研究方向.同其它公鑰密碼技術(shù)相比,例如RSA以及離散對(duì)數(shù),在相同安全強(qiáng)度的條件下,橢圓曲線(xiàn)所要求的密鑰長(zhǎng)度更小.
　　 點(diǎn)乘運(yùn)算([n]P)是橢圓曲線(xiàn)加密技術(shù)的核心研究方向之一,這里n表示一個(gè)整數(shù),P表示橢圓曲線(xiàn)上的一點(diǎn).目前,在改善點(diǎn)乘速度的研究方面,主要有兩個(gè)方向.
　　 一是通過(guò)改進(jìn)整數(shù)n的表示方式,以減少點(diǎn)

2、乘計(jì)算中點(diǎn)加(P+Q)與倍乘([2]P))的次數(shù).目前,在這一方向最有效的算法是窗口算法(wNAF)和分式窗口算法(Frac-wNAF)[11],它們都是基于整數(shù)的二進(jìn)制表示形式,在此基礎(chǔ)上,將二進(jìn)制序列劃分為不同長(zhǎng)度的窗口,以減少它的漢明(Hamming)重量.2007年,Longa[13]提出了基于多基的窗口算法(mbNAF)和多基的分式窗口算法(Frac-wmbNAF),它們是將整數(shù)表示為多基形式.2009年,Longa和Gebo

3、tys[11]將這種方法作了改進(jìn),使得點(diǎn)乘運(yùn)算中點(diǎn)加計(jì)算的次數(shù)進(jìn)一步減少.
　　 二是減少點(diǎn)加計(jì)算和倍乘計(jì)算中的計(jì)算量.根據(jù)文獻(xiàn)[3],目前在基于Hessian方程形式的橢圓曲線(xiàn)點(diǎn)乘運(yùn)算中,射影坐標(biāo)下點(diǎn)加計(jì)算中最小的計(jì)算量為12M,倍乘的最小計(jì)算量為7M+1S,三倍的最小計(jì)算量為8M+6S.射影-仿射混和坐標(biāo)下的最小計(jì)算量為10M.2009年,Hisil.Wong.Carter和Dawson[17]提出了一種擴(kuò)展射影坐標(biāo),改進(jìn)點(diǎn)

4、加的計(jì)算角為6M+6S,倍乘的計(jì)算量為3M+6S,混合坐標(biāo)的點(diǎn)加計(jì)算量為5M+6S.這里S和M分別表示平方和乘法計(jì)算.
　　 根據(jù)窗口算法的特征,在所有窗口的算法中.都需要有預(yù)計(jì)算.也就是計(jì)算集合{[3]P,[5]P,…,[2k+1]P}中的所有點(diǎn),在文獻(xiàn)[10]中,Dahmen等人提出了一種新的辦法,它可以在一次域的求逆的情況下.將集合中所有的預(yù)計(jì)算點(diǎn)轉(zhuǎn)化為仿射坐標(biāo),這樣可以用混合坐標(biāo)的形式完成點(diǎn)乘計(jì)算中所有的點(diǎn)加運(yùn)算,從而提

5、高點(diǎn)乘運(yùn)算的效率.2006年,Meloni[7]介紹了基于Jacobian坐標(biāo)的一種特殊的加法算法.他是利用很小的計(jì)算量計(jì)算兩個(gè)同z坐標(biāo)點(diǎn)的加法.2008年,Longa和Miri[4]利用這種算法提出了一種新的更高效的預(yù)計(jì)算方法,它是在更小的計(jì)算量和更少的存貯空間的情況下,也是利用一次域的逆運(yùn)算,將所有的預(yù)計(jì)算點(diǎn)轉(zhuǎn)化為仿射坐標(biāo).但是以上兩種方法都只能基于Weierstrass方程形式,不能擴(kuò)展到其它形式的橢圓曲線(xiàn)上.
　　 在本

6、文中,我們介紹一種基于Hessian曲線(xiàn)的新的點(diǎn)加算法,它是在射影坐標(biāo)F,將兩個(gè)同z坐標(biāo)的點(diǎn)相加,有以下結(jié)果,X3=(Y2-Y1)(X2Y2-(Y1+Y2)(X1+X2))+Y1(X2Y2-X1Y1),Y3=(X2-X1)(X2Y2-(Y1+Y2)(X1+X2))+X1(X2Y2-X1Y1),Z3=Z(X2Y2-X1Y1).這種點(diǎn)加運(yùn)算的計(jì)算量為8M,小于混合坐標(biāo)的計(jì)算量10M.利用我們所提出的新的點(diǎn)加算法使得在加法鏈算法下,點(diǎn)乘運(yùn)算的

7、計(jì)算量改進(jìn)為(8s-7)M+1S,這里s表示加法鏈的長(zhǎng)度.由于利用加法鏈算法可以使得點(diǎn)乘運(yùn)算中只有點(diǎn)加計(jì)算而沒(méi)有倍乘計(jì)算,依據(jù)簡(jiǎn)單側(cè)信道攻擊(SSCAs)的原理,此方法可以有效的抵御SSCAs攻擊.
　　 利用文獻(xiàn)[4]中的方法,我們可以改進(jìn)Hessian曲線(xiàn)上基于窗口算法的預(yù)計(jì)算.在本文中,我們提出了兩種預(yù)計(jì)算方法.
　　 方法一是結(jié)合我們提出的新的算法,以及形式為diP=2P+…+2P+2P+P的迭代計(jì)算,在計(jì)算量為

8、(8L+4)M+4S的條件下,計(jì)算出所有的預(yù)計(jì)算點(diǎn),這里L(fēng)表示預(yù)計(jì)算的點(diǎn).相比較射影坐標(biāo)條件下的計(jì)算量(12L+1)M+3S,在窗口越大的情況下,算法一的改進(jìn)越多.在利用Frac-wNAF和Frac-wmbNAF,當(dāng)窗口w＞6時(shí),方法一可以減少計(jì)算量大于28M.
　　 方法二是在方法一的基礎(chǔ)上,在一次求逆的情況下,將所有的預(yù)計(jì)算點(diǎn)轉(zhuǎn)化為仿射坐標(biāo),所用的計(jì)算量為1I+(11L+3)M+4S.這樣我們可以利用混合坐標(biāo)運(yùn)算來(lái)完成點(diǎn)乘運(yùn)

9、算中的點(diǎn)加計(jì)算.相比較射影坐標(biāo)的計(jì)算方法,假設(shè)I/M≈30,n=192 bits,方法二減少計(jì)算暈至少為31M.當(dāng)w=4時(shí),辦法二在利用Frac-wNAF時(shí)可以減少47M,在利用Frac-wmbNAF時(shí)可以減少計(jì)算最36M,并且,在任何窗口寬度下,它至少節(jié)省計(jì)算量31M.
　　 本文章節(jié)安排如下,第一章主要介紹橢圓曲線(xiàn)和點(diǎn)乘算法的基本內(nèi)容,Hessian曲線(xiàn)的相關(guān)介紹,Meloni所提出的基于Jacobian坐標(biāo)的特殊的點(diǎn)加算法