橢圓曲線密碼體制中標(biāo)量乘法的快速算法研究.pdf

1、自從Koblitz和Miller分別獨立提出橢圓曲線密碼體制（ECC）之后，這種公鑰密碼的潛力越來越被人們所認(rèn)同。與另一著名的公鑰密碼RSA相比，ECC密鑰短，安全性高，速度快，存儲空間占用少和帶寬要求低，它的這些特點使得業(yè)內(nèi)人士普遍認(rèn)為ECC將成為下一代最通用的公鑰加密算法標(biāo)準(zhǔn)。在ECC的快速實現(xiàn)中，最關(guān)鍵的就是標(biāo)量乘法kP的計算，其在計算上非常復(fù)雜，因此，對標(biāo)量乘法的快速算法研究已成為密碼學(xué)界共同關(guān)心的問題。 本文首先闡述了

2、ECC的研究背景、現(xiàn)狀和基本概念，通過橢圓曲線離散對數(shù)問題（ECDLP），引入了標(biāo)量乘法的定義，并對標(biāo)量乘法的常用算法進(jìn)行了分析比較，給出其優(yōu)缺點。 然后利用轉(zhuǎn)化求逆為乘法的原理，改進(jìn)了仿射坐標(biāo)下3P+Q的算法，此算法比Ciet的算法節(jié)省了1次求逆；提出了仿射坐標(biāo)下直接計算3kP（k>1）的算法，該算法比連續(xù)k次計算3P更有效。結(jié)合l-NAFw的編碼方法，把3kP、3P+Q的新算法運(yùn)用于標(biāo)量乘法的改進(jìn)，效率明顯高于NAF等傳統(tǒng)方

3、法。當(dāng)然，3kP的算法結(jié)合2kP的算法還可使DBNS算法的效率進(jìn)一步提高。預(yù)計算的效率同樣影響著標(biāo)量乘法的效率，本文對固定基comb算法做了詳細(xì)研究，利用直接計算2kP和2P+Q的算法對固定基comb算法作了有效改進(jìn)，改進(jìn)的算法在預(yù)計算和主循環(huán)階段效率都有不同程度的提高。同時還對窗口法的預(yù)計算提出了改進(jìn)方案，設(shè)計了同時計算2P、3P和5P的算法，該算法只需要1次求逆，提高了預(yù)計算的效率。 最后研究了Koblitz曲線，分析了Ko