幾類代數(shù)曲線上的快速標(biāo)量乘算法研究.pdf

1、在現(xiàn)代密碼體制中,橢圓曲線密碼體制(ECC)是一種應(yīng)用非常廣泛的密碼體制。為了滿足電子認(rèn)證服務(wù)系統(tǒng)等應(yīng)用要求,國家密碼管理局第21號公告就發(fā)布了SM2橢圓曲線公鑰密碼算法和SM2橢圓曲線公鑰算法推薦曲線參數(shù),在第7號公告中也規(guī)定了無線局域網(wǎng)產(chǎn)品須采用橢圓曲線數(shù)字簽名算法(ECDSA),并且國外的一些公司,如Motorola,Sony,Cisco等,也都開發(fā)出基于ECC的密碼產(chǎn)品,并且以IC芯片或者軟件的形式出現(xiàn)。橢圓曲線密碼體制本身具有

2、存儲空間小、傳輸帶寬要求低、處理器的速度要求低等特點,這些特點對于資源受限的移動用戶終端、IC卡等有著重要的意義。而作為ECC關(guān)鍵運算的標(biāo)量乘計算,其運算速度決定了整個密碼體制實現(xiàn)的效率。因此,如何快速地計算標(biāo)量乘,成為了密碼學(xué)相關(guān)領(lǐng)域科研人員關(guān)注的熱點問題。如何提高標(biāo)量乘算法的計算效率,可以從兩個方面入手:(1)尋求對標(biāo)量k的有效表示;(2)加快底層的域運算。
　　 本論文主要研究了兩類代數(shù)曲線上的快速標(biāo)量乘算法。一類是Edw

3、ards曲線,該類曲線上的有理點群運算具有法則簡單、計算加點和二倍點有相同的公式表示等特點。相關(guān)文獻(xiàn)對Edwards曲線上的群運算作了詳細(xì)的分析,指出其運算效率高于Hessian曲線、Jacobiquartics曲線等其他形式的代數(shù)曲線。
　　 (1)首先介紹了已有的一種Edwards曲線上的快速標(biāo)量乘算法。然后通過對標(biāo)量七進(jìn)行四進(jìn)制表示,引入3倍點的計算公式,提出了一種新的快速標(biāo)量乘算法。同時比較了原算法和改進(jìn)算法的計算量,并

4、分析了原算法和改進(jìn)算法的安全性。結(jié)果表明:不論n的大小(假設(shè)標(biāo)量用三進(jìn)制表示時有n位),及D和M的大小關(guān)系如何,改進(jìn)算法的計算量始終是少于原算法的,并且相比于原算法,改進(jìn)算法節(jié)省了約20％的存儲空間。
　　 (2)利用相關(guān)文獻(xiàn)提出的計算2nP,3nP的快速算法,通過將標(biāo)量k進(jìn)行2,3進(jìn)制的混合表示,提出了一種快速標(biāo)量乘的算法,該算法能有效地減少標(biāo)量乘算法的計算量。本文研究的另一類代數(shù)曲線是超橢圓曲線Cq∶v2=up+qu+b。超

5、橢圓曲線密碼體制(HECC)的安全性是以超橢圓曲線上的Jacobian商群上的離散對數(shù)問題為基礎(chǔ)的,其結(jié)構(gòu)和運算比有理點群要復(fù)雜。但是相比于其他的密碼體制,超橢圓密碼體制也有其自身的優(yōu)勢,比如更強(qiáng)的單比特安全性,豐富的可用于密碼體制的超橢圓曲線。本文重點研究了超橢圓曲線Cq上的快速除子標(biāo)量乘算法。相關(guān)文獻(xiàn)提出了計算pιD的快速算法,其中p是一個素數(shù),D為Cq上的一個除子,ι為任意正整數(shù)。一般的雙基鏈算法都是將標(biāo)量k分解為2,3進(jìn)制的,而