資源描述:
《GF (2m )上橢圓曲線標(biāo)量乘快速算法研究》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、ComputerScienceandApplication計(jì)算機(jī)科學(xué)與應(yīng)用,2014,4,76-84PublishedOnlineApril2014inHans.http://www.hanspub.org/journal/csahttp://dx.doi.org/10.12677/csa.2014.44013ResearchonFastAlgorithmsforScalarMultiplicationofEllipticCurveoverGF(2m)LiSun,MengZhouSchoolofMathematicsandSystemSc
2、ience,LMIB,BeihangUniversity,BeijingEmail:sunlibuaa@126.com,zm1613@sina.comthththReceived:Mar.6,2014;revised:Apr.4,2014;accepted:Apr.18,2014Copyright?2014byauthorsandHansPublishersInc.ThisworkislicensedundertheCreativeCommonsAttributionInternationalLicense(CCBY).http://cr
3、eativecommons.org/licenses/by/4.0/AbstractEllipticcurvecryptographyfindsnumerousapplicationsbecauseofitsexcellentanduniqueproperties.ThispaperfocusedonthescalarmultiplicationofEllipticcurve.Weproposedthere-kmcursionformulatocompute3PoverGF(2)basedontheideaoftradinginversi
4、onsformul-tiplications,whichreducedtheinversiontoonlyonce.Atthesametime,thispaperalsogaveanac-celeratedalgorithmforcomputing3PQ+,whichsavedtwoinversionscomparedtocomputingitdirectly.Theresultsuggeststhattheproposedalgorithmsaremoreefficientthanthenormalal-gorithmswhenther
5、atiosaremorethan7.4and5.9respectively.KeywordsEllipticCurve,ScalarMultiplication,AcceleratedAlgorithm,InversionGF(2m)上橢圓曲線標(biāo)量乘快速算法研究孫俐,周夢(mèng)北京航空航天大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院LMIB,北京Email:sunlibuaa@126.com,zm1613@sina.com收稿日期:2014年3月6日;修回日期:2014年4月4日;錄用日期:2014年4月18日76mGF(2)上橢圓曲線標(biāo)量乘快速算法研究摘要橢圓曲線
6、密碼自提出以來(lái)便因其優(yōu)良的性質(zhì)而得到了廣泛的應(yīng)用。本文針對(duì)橢圓曲線上關(guān)鍵的標(biāo)量乘運(yùn)mk算,根據(jù)將耗時(shí)較多的求逆轉(zhuǎn)換為乘法的思想,推導(dǎo)出了GF(2)上計(jì)算3P的遞推公式,將求逆次數(shù)減少到一次。同時(shí)提出了計(jì)算3PQ+的加速算法,比直接計(jì)算節(jié)省了2次求逆。分析表明,在逆乘率分別大于7.4和5.9時(shí),改進(jìn)算法的效率優(yōu)于逐次計(jì)算。關(guān)鍵詞橢圓曲線,標(biāo)量乘,加速算法,求逆1.引言1985年,橢圓曲線密碼(ECC)由Miller[1]和Koblitz[2]等人分別獨(dú)立提出。該密碼體制一經(jīng)提出便得到眾多密碼學(xué)研究專(zhuān)家的關(guān)注。ECC基于有限域中的離散對(duì)數(shù)難解
7、問(wèn)題(DL),這使得在同樣的安全性能下,ECC需要的密鑰長(zhǎng)度比RSA要短很多。隨著橢圓曲線密碼的發(fā)展,快速實(shí)現(xiàn)成為學(xué)著們研究的重點(diǎn)。橢圓曲線的運(yùn)算分為上層算法和底層算法,其中,上層加速算法是針對(duì)橢圓曲線上點(diǎn)的運(yùn)算,即群的計(jì)算;底層算法是針對(duì)底層有限域上為實(shí)現(xiàn)點(diǎn)之間的運(yùn)算而做的乘法、求逆、平方等運(yùn)算。很明顯,為了達(dá)到更好的計(jì)算效率,需要結(jié)合上層域以及底層域計(jì)算展開(kāi)改進(jìn)。這也是橢圓曲線加速算法的一個(gè)研究趨勢(shì)。在橢圓曲線密碼體制中,核心運(yùn)算就是橢圓曲線的標(biāo)量乘kP的運(yùn)算,它是橢圓曲線密碼體制快速實(shí)現(xiàn)的關(guān)鍵。在標(biāo)量乘運(yùn)算中求逆的耗時(shí)是乘法的8倍[
8、3],用適量的乘法代替求逆可以明顯的提高計(jì)算的m效率。利用此思想,Guajardo等人[4]提出了GF(2)上直接計(jì)算4P、8P、16P的算法。Sakai等人[5]k在Guajardo的基礎(chǔ)上