引言

相比RSA等算法，ECC的計(jì)算量和密鑰長(zhǎng)度已經(jīng)有了很大的降低，但是它的數(shù)學(xué)結(jié)構(gòu)仍較復(fù)雜，對(duì)于一些計(jì)算能力和存儲(chǔ)資源受限的應(yīng)用場(chǎng)景如無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）來(lái)說(shuō)，算法所需的計(jì)算時(shí)間和計(jì)算量會(huì)極大地縮短網(wǎng)絡(luò)的生命周期［1］。在ECC密碼體制中，標(biāo)量乘（Q=kP）是算法安全性的關(guān)鍵，其運(yùn)算速度從整體上決定了算法的執(zhí)行效率［2］。因此，對(duì)標(biāo)量乘法進(jìn)行輕量化改進(jìn)，將顯著減少ECC密碼方案的資源消耗。

目前，對(duì)標(biāo)量乘的優(yōu)化主要集中在兩方面，一是對(duì)算法本身進(jìn)行設(shè)計(jì)，以減少點(diǎn)加和倍點(diǎn)的運(yùn)算次數(shù)，如Montgomery算法［3］及其改進(jìn)算法［4-5］，基于非相鄰形式（Non-Adjacent Form，NAF）標(biāo)量乘快速算法［6］及其改進(jìn)方案［7-8］。二是對(duì)底層域運(yùn)算進(jìn)行改進(jìn)，如文獻(xiàn)［9］通過(guò)對(duì)多項(xiàng)式乘法和模約減等域運(yùn)算進(jìn)行合理優(yōu)化設(shè)計(jì)，使得基于二進(jìn)制域Koblitz曲線的標(biāo)量乘算法比素?cái)?shù)域上計(jì)算速度更快、效率更高；文獻(xiàn)［10］針對(duì)ATmega128微控制器的特點(diǎn)，對(duì)有限域上平方和乘法運(yùn)算進(jìn)行了優(yōu)化；文獻(xiàn)［11］提出使用最優(yōu)素?cái)?shù)域（OPF）作為底層代數(shù)結(jié)構(gòu)；文獻(xiàn)［12］提出了一種適用于MICAz電機(jī)特點(diǎn)的標(biāo)量乘計(jì)算方案；文獻(xiàn)［13］利用優(yōu)化的掩碼操作數(shù)技術(shù)進(jìn)行模塊加法和減法，以減少掩碼計(jì)算的次數(shù)和延遲；文獻(xiàn)［14］提出了一種基于乘法器編碼的多項(xiàng)式乘法方法。

結(jié)合以上思想，本文以傳感器節(jié)點(diǎn)中常用的8 bit ATmega128芯片為目標(biāo)平臺(tái)，通過(guò)對(duì)二進(jìn)制域上ECC標(biāo)量乘法底層的域運(yùn)算進(jìn)行研究，針對(duì)乘法運(yùn)算，提出一種聯(lián)合區(qū)塊相乘的思想，并進(jìn)一步設(shè)計(jì)出3級(jí)Karatsuba乘法算法；針對(duì)減法運(yùn)算，通過(guò)將減法運(yùn)算與模運(yùn)算相結(jié)合，提出一種模快速約減算法；針對(duì)模平方運(yùn)算，通過(guò)預(yù)處理的方式建立查找表，并結(jié)合模運(yùn)算同時(shí)處理，提出一種快速模平方算法；針對(duì)逆運(yùn)算，結(jié)合擴(kuò)展Euclideam算法，提出一種求模逆算法；最后，基于Montgomery算法設(shè)計(jì)了二進(jìn)制域上的標(biāo)量乘快速實(shí)現(xiàn)方案。理論和實(shí)驗(yàn)分析表明，本文方案減少了計(jì)算過(guò)程的基本運(yùn)算和內(nèi)存讀寫(xiě)次數(shù)，提高了標(biāo)量乘法的計(jì)算效率。

本文詳細(xì)內(nèi)容請(qǐng)下載：

http://m.jysgc.com/resource/share/2000006102

作者信息：

吳昆1，胡現(xiàn)剛2，張學(xué)超3，汪曉睿1

(1.91977部隊(duì),北京100071;

2.南部戰(zhàn)區(qū)海軍參謀部，廣東湛江524000;

3.中央軍委政法委，北京100000)