橢圓曲線上標量乘快速算法研究.pdf

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

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

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