橢圓曲線上標(biāo)量乘快速算法研究.pdf

1、橢圓曲線密碼體制(ECC)是迄今為止單比特具有最高安全強(qiáng)度的密碼系統(tǒng)。與其他公鑰密碼系統(tǒng)相比,橢圓曲線密碼體制具有安全性高、計(jì)算負(fù)載小、密鑰尺寸短、占用帶寬少等眾多優(yōu)點(diǎn),深入研究基于橢圓曲線離散對(duì)數(shù)問題的公鑰密碼體制具有很大的現(xiàn)實(shí)意義。標(biāo)量乘法是橢圓曲線密碼體制實(shí)現(xiàn)過程中最基本、最耗時(shí)的運(yùn)算,也是橢圓曲線密碼體制快速實(shí)現(xiàn)最關(guān)鍵的運(yùn)算,提高標(biāo)量乘法的運(yùn)算速度對(duì)橢圓曲線密碼體制的推廣意義重大。研究標(biāo)量乘法有兩個(gè)切入點(diǎn):一是研究標(biāo)量k的有效表

2、示:二是尋求底層域快速運(yùn)算算法。本文將研究重點(diǎn)放在標(biāo)量k的有效表示上。
　　 本文主要針對(duì)雙標(biāo)量乘快速算法和k的多基編碼標(biāo)量乘算法兩個(gè)方面進(jìn)行了研究:首先介紹了橢圓曲線上原有的單標(biāo)量乘算法如二元法、NAF法、窗口法等,對(duì)Shamir快速雙標(biāo)量乘算法和交錯(cuò)NAF方法的優(yōu)缺點(diǎn)進(jìn)行了詳細(xì)分析,結(jié)合二者優(yōu)點(diǎn)給出了Shamir快速算法的一種改進(jìn)方案。改進(jìn)方案與Shamir快速算法相比,在沒有明顯增加運(yùn)算量的前提下,至少減少點(diǎn)存儲(chǔ)量50％以

3、上,是一種適合于內(nèi)存受限的手持設(shè)備的方案。其次,介紹了雙基和多基編碼標(biāo)量乘算法的發(fā)展和研究現(xiàn)狀,并對(duì)與之相關(guān)的底層域快速算法kP+Q的研究進(jìn)展做了說明。之后分析了Ciet等人的雙基編碼標(biāo)量乘算法和一種多基編碼標(biāo)量乘算法的運(yùn)算效率,給出了一種改進(jìn)的基于多基的標(biāo)量乘算法,對(duì)此三種算法效率進(jìn)行定量分析,分析結(jié)果表明,改進(jìn)方案較原有多基標(biāo)量乘,每次點(diǎn)乘能減少兩個(gè)逆運(yùn)算,從而達(dá)到降低運(yùn)算量的目的。當(dāng)I／M=60時(shí),改進(jìn)方案比原有的多基標(biāo)量乘算法提