橢圓曲線標量乘法快速實現研究.pdf

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

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

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

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