基于Hessian曲線的一種新的點加運算以及在點乘中的應用.pdf

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

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

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

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

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

6、文中,我們介紹一種基于Hessian曲線的新的點加算法,它是在射影坐標F,將兩個同z坐標的點相加,有以下結果,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).這種點加運算的計算量為8M,小于混合坐標的計算量10M.利用我們所提出的新的點加算法使得在加法鏈算法下,點乘運算的

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

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

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