橢圓曲線標(biāo)量乘法快速實(shí)現(xiàn)研究.pdf

1、自1985年Koblitz和Miller分別獨(dú)立提出橢圓曲線密碼體制(Elliptic Curve Cryptology，ECC)后，由于ECC本身計(jì)算速度快，存儲空間小，帶寬要求低，特別適用于Smart卡和無線應(yīng)用環(huán)境等優(yōu)點(diǎn)，很快得到了廣大研究者的關(guān)注。標(biāo)量乘法是ECC實(shí)現(xiàn)過程中最基本、最耗時(shí)的運(yùn)算，研究標(biāo)量乘法有兩個切入點(diǎn)：一是研究標(biāo)量K的有效表示；二是尋求底層域快速運(yùn)算算法，在前人工作的基礎(chǔ)上，本文主要對以下幾點(diǎn)進(jìn)行了詳細(xì)研究。

2、 (1)從底層域快速算法出發(fā)，結(jié)合抵抗邊際信道攻擊的方法，對傳統(tǒng)標(biāo)量乘法Fixed-base comb算法進(jìn)行改進(jìn)，給出了一個安全、快速的：Fixed-base comb算法。根據(jù)其特點(diǎn)，利用犧牲乘法操作以降低求逆操作的方法，分別用2<'k>p、2P+Q的快速算法對Fixed-base comb算法的預(yù)計(jì)算階段和賦值階段進(jìn)行改進(jìn)，顯著地提高了計(jì)算效率：在素?cái)?shù)域上預(yù)計(jì)算階段提高70％～80％，而賦值階段提高38％～43％，同時(shí)，改進(jìn)

3、算法通過對K的預(yù)處理，使得算法能夠抵抗邊際信道攻擊。 (2)利用底層域2<'k>P、3<'k>P、2P±Q、3P±Q快速算法給出了新的基于雙基數(shù)鏈的標(biāo)量乘法快速算法。借助于雙基數(shù)表示的稀疏性質(zhì)和底層域快速算法的優(yōu)勢，新算法大大減少了底層運(yùn)算中求逆操作的次數(shù)，有效提高了算法的執(zhí)行效率。實(shí)驗(yàn)證明，相同雙基數(shù)表示下，該算法優(yōu)于Dimitrov給出的基于雙基數(shù)鏈的算法：素?cái)?shù)域上，密鑰長度160bit時(shí)算法效率提高19％-22％，192b

4、it提高22％-25％，224bit提高26％-30％，256bit提高35％左右。 (3)定義了雙基數(shù)系統(tǒng)的一個子集，給出了近似規(guī)范雙基數(shù)子集表示法的貪婪算法，并在此基礎(chǔ)上構(gòu)造了新的標(biāo)量乘算法。同帶符號雙基數(shù)系統(tǒng)一樣，該子集能表示所有整數(shù)，而其固有的2．整數(shù)遞增的特質(zhì)，使得它相比其它求雙基數(shù)表示的算法大大節(jié)省了時(shí)間。同時(shí)，雙基數(shù)子系統(tǒng)將預(yù)計(jì)算空間從n<'2>降低到3n-2，節(jié)省了大量預(yù)計(jì)算量和存儲空間。由于搜索空間的降低，整數(shù)