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

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

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

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

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

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