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

1、1985年Miller和Koblitz分別獨(dú)立提出橢圓曲線密碼體制(ECC，Elliptic CurveCryptosystem)，由于ECC本身計(jì)算速度快，存儲(chǔ)空間小，帶寬要求低，特別適用于Smart卡和無(wú)線應(yīng)用環(huán)境等優(yōu)點(diǎn)，很快得到了廣大研究者的關(guān)注。標(biāo)量乘法是ECC中最基本、最耗時(shí)的運(yùn)算，就是已知域內(nèi)整數(shù)k和橢圓曲線上一點(diǎn)P，求橢圓曲線上另一點(diǎn)kP的運(yùn)算，其效率決定著整個(gè)橢圓曲線密碼體制的性能。 計(jì)算標(biāo)量乘法kP的過(guò)程有兩個(gè)

2、層次：一為上層運(yùn)算，即橢圓曲線上的點(diǎn)加與倍點(diǎn)運(yùn)算構(gòu)成的有限阿貝爾群上的運(yùn)算，另一個(gè)層次是底層域運(yùn)算，即在有限域中為實(shí)現(xiàn)上層運(yùn)算而做的算術(shù)運(yùn)算。這些運(yùn)算包括有限域上大整數(shù)的求逆、乘法、平方和加法。相應(yīng)地，標(biāo)量乘法的研究思路也分為兩條：上層運(yùn)算又細(xì)分為兩個(gè)角度：即尋求標(biāo)量k的有效表示形式和標(biāo)量乘法算法的并行化。底層域上主要是尋求實(shí)現(xiàn)點(diǎn)加、倍點(diǎn)的快速計(jì)算。在前人工作的基礎(chǔ)上，本文主要對(duì)以下幾點(diǎn)進(jìn)行了詳細(xì)研究。 (1)通過(guò)將直接計(jì)算dP

3、+Q的快速算法應(yīng)用于Comb算法，對(duì)素?cái)?shù)域上Comb標(biāo)量乘算法的賦值階段進(jìn)行改進(jìn)，其中計(jì)算2P+Q只需要11次乘法和7次平方。由于使用了高效的2P+Q運(yùn)算，使Comb算法效率得到了提高。對(duì)改進(jìn)算法進(jìn)行分析，當(dāng)密鑰長(zhǎng)度ι為160、192和224以及窗口寬度w為4和8時(shí)，在賦值階段，改進(jìn)算法效率比Comb算法大約提高79％。 (2)在二進(jìn)制域上，通過(guò)將折半運(yùn)算應(yīng)用于Comb算法，提出了一種新的Comb標(biāo)量乘算法，它可以提高域F2m上

4、的橢圓曲線標(biāo)量乘法的效率。在預(yù)計(jì)算階段和賦值階段，新算法分別用高效的折半運(yùn)算取代倍點(diǎn)運(yùn)算。對(duì)新算法運(yùn)行時(shí)間進(jìn)行分析，并與傳統(tǒng)的Comb算法進(jìn)行比較，當(dāng)窗口寬度w=4時(shí)，預(yù)計(jì)算階段效率提高68％～74％，賦值階段效率提高19％～24％，總運(yùn)行效率提高了58％～63％。 (3)通過(guò)將交錯(cuò)技術(shù)與Koblitz曲線上的窗口TNAF標(biāo)量乘相結(jié)合，給出一種新的標(biāo)量乘算法，該算法不對(duì)標(biāo)量乘進(jìn)行預(yù)計(jì)算，只是在賦值階段施加交錯(cuò)。由于Frobeni