引用格式：吳昆，胡現(xiàn)剛，張學(xué)超，等.橢圓曲線標(biāo)量乘高效方案設(shè)計［J］.網(wǎng)絡(luò)安全與數(shù)據(jù)治理，2024，43（8）：28-34.
引言
相比RSA等算法，ECC的計算量和密鑰長度已經(jīng)有了很大的降低，但是它的數(shù)學(xué)結(jié)構(gòu)仍較復(fù)雜，對于一些計算能力和存儲資源受限的應(yīng)用場景如無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）來說，算法所需的計算時間和計算量會極大地縮短網(wǎng)絡(luò)的生命周期［1］。在ECC密碼體制中，標(biāo)量乘（Q=kP）是算法安全性的關(guān)鍵，其運算速度從整體上決定了算法的執(zhí)行效率［2］。因此，對標(biāo)量乘法進(jìn)行輕量化改進(jìn)，將顯著減少ECC密碼方案的資源消耗。
目前，對標(biāo)量乘的優(yōu)化主要集中在兩方面，一是對算法本身進(jìn)行設(shè)計，以減少點加和倍點的運算次數(shù)，如Montgomery算法［3］及其改進(jìn)算法［4-5］，基于非相鄰形式（Non-Adjacent Form，NAF）標(biāo)量乘快速算法［6］及其改進(jìn)方案［7-8］。二是對底層域運算進(jìn)行改進(jìn)，如文獻(xiàn)［9］通過對多項式乘法和模約減等域運算進(jìn)行合理優(yōu)化設(shè)計，使得基于二進(jìn)制域Koblitz曲線的標(biāo)量乘算法比素數(shù)域上計算速度更快、效率更高；文獻(xiàn)［10］針對ATmega128微控制器的特點，對有限域上平方和乘法運算進(jìn)行了優(yōu)化；文獻(xiàn)［11］提出使用最優(yōu)素數(shù)域（OPF）作為底層代數(shù)結(jié)構(gòu)；文獻(xiàn)［12］提出了一種適用于MICAz電機特點的標(biāo)量乘計算方案；文獻(xiàn)［13］利用優(yōu)化的掩碼操作數(shù)技術(shù)進(jìn)行模塊加法和減法，以減少掩碼計算的次數(shù)和延遲；文獻(xiàn)［14］提出了一種基于乘法器編碼的多項式乘法方法。
結(jié)合以上思想，本文以傳感器節(jié)點中常用的8 bit ATmega128芯片為目標(biāo)平臺，通過對二進(jìn)制域上ECC標(biāo)量乘法底層的域運算進(jìn)行研究，針對乘法運算，提出一種聯(lián)合區(qū)塊相乘的思想，并進(jìn)一步設(shè)計出3級Karatsuba乘法算法；針對減法運算，通過將減法運算與模運算相結(jié)合，提出一種模快速約減算法；針對模平方運算，通過預(yù)處理的方式建立查找表，并結(jié)合模運算同時處理，提出一種快速模平方算法；針對逆運算，結(jié)合擴展Euclideam算法，提出一種求模逆算法；最后，基于Montgomery算法設(shè)計了二進(jìn)制域上的標(biāo)量乘快速實現(xiàn)方案。理論和實驗分析表明，本文方案減少了計算過程的基本運算和內(nèi)存讀寫次數(shù)，提高了標(biāo)量乘法的計算效率。
本文詳細(xì)內(nèi)容請下載：
http://ihrv.cn/resource/share/2000006102
作者信息：
吳昆1，胡現(xiàn)剛2，張學(xué)超3，汪曉睿1
(1.91977部隊,北京100071;
2.南部戰(zhàn)區(qū)海軍參謀部，廣東湛江524000;
3.中央軍委政法委，北京100000)
