《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計(jì)應(yīng)用 > 橢圓曲線標(biāo)量乘高效方案設(shè)計(jì)
橢圓曲線標(biāo)量乘高效方案設(shè)計(jì)
網(wǎng)絡(luò)安全與數(shù)據(jù)治理
吳昆1，胡現(xiàn)剛2，張學(xué)超3，汪曉睿1
1.91977部隊(duì);2.南部戰(zhàn)區(qū)海軍參謀部;3.中央軍委政法委
摘要： 對于一些資源受限的應(yīng)用場景而言，橢圓曲線密碼算法的計(jì)算量還是比較大，這嚴(yán)重影響了網(wǎng)絡(luò)的生命周期，需要對算法進(jìn)行輕量化改進(jìn)以減少資源消耗。標(biāo)量乘運(yùn)算是影響橢圓曲線密碼算法執(zhí)行效率的關(guān)鍵，針對無線傳感器節(jié)點(diǎn)的內(nèi)存和處理特點(diǎn)，首先對其底層的域運(yùn)算進(jìn)行改進(jìn)，提出了二進(jìn)制域上的3-Karatsuba聯(lián)合區(qū)塊乘法算法、快速模約減算法、模平方及模逆算法，減少了域運(yùn)算過程的基本運(yùn)算和內(nèi)存讀寫次數(shù)，最后基于Montgomery算法設(shè)計(jì)了GF(2m)上的標(biāo)量乘快速實(shí)現(xiàn)方案。在8 bit AVR 微處理器上實(shí)驗(yàn)表明，完成一次GF(2163)域上的ECC點(diǎn)乘運(yùn)算共需要5 160 991個(gè)時(shí)鐘周期，時(shí)間消耗大約為0.70 s，改進(jìn)后的方案在運(yùn)算效率方面有一定優(yōu)化。
中圖分類號：TP309.7文獻(xiàn)標(biāo)識碼：ADOI:10.19358/j.issn.2097-1788.2024.08.005
引用格式：吳昆，胡現(xiàn)剛，張學(xué)超，等.橢圓曲線標(biāo)量乘高效方案設(shè)計(jì)［J］.網(wǎng)絡(luò)安全與數(shù)據(jù)治理，2024，43（8）：28-34.
Energy-efficient scheme of elliptic curve cryptography scalar multiplication
Wu Kun1，Hu Xian′gang2，Zhang Xuechao3，Wang Xiaorui1
1.Unit 91977 of People′s Liberation Army of China; 2.Naval Staff Department of the Southern Theater Command;3.Political and Legal Affairs Commission of the Central Military Commission
Abstract： Due to the limited resources of the wireless sensor network, the elliptic curve cryptographic algorithm requires a large amount of computation, which seriously affects the life cycle of the network. It is necessary to make lightweight improvements to the algorithm to reduce resource consumption. Scalar multiplication is the key to the execution efficiency of elliptic curve cryptographic algorithms. By analyzing the storage and processing characteristics of wireless sensor nodes, we improve the underlying domain operations firstly, and propose the 3-Karatsuba block-combined multiplication algorithm, fast modular reduction algorithm, modular square and modular inverse algorithm on binary domain, which can reduce the times of basic operations and memory read and write. Finally, we design a fast implementation scheme of scalar multiplication on GF(2m) based on the Montgomery algorithm. The results of experiments on 8 bit AVR microprocessor demonstrate that, completing an ECC point multiplication operation on the GF (2163) domain requires a total of 5 160 991 clock cycles, with a time consumption of approximately 0.70 seconds, our contribution can improve ECC scalar multiplication significantly.
Key words : elliptic curve cryptography (ECC); scalar multiplication; binary field operations; modular operation

引言

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

目前，對標(biāo)量乘的優(yōu)化主要集中在兩方面，一是對算法本身進(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］。二是對底層域運(yùn)算進(jìn)行改進(jìn)，如文獻(xiàn)［9］通過對多項(xiàng)式乘法和模約減等域運(yùn)算進(jìn)行合理優(yōu)化設(shè)計(jì)，使得基于二進(jìn)制域Koblitz曲線的標(biāo)量乘算法比素?cái)?shù)域上計(jì)算速度更快、效率更高；文獻(xiàn)［10］針對ATmega128微控制器的特點(diǎn)，對有限域上平方和乘法運(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)，通過對二進(jìn)制域上ECC標(biāo)量乘法底層的域運(yùn)算進(jìn)行研究，針對乘法運(yùn)算，提出一種聯(lián)合區(qū)塊相乘的思想，并進(jìn)一步設(shè)計(jì)出3級Karatsuba乘法算法；針對減法運(yùn)算，通過將減法運(yùn)算與模運(yùn)算相結(jié)合，提出一種?？焖偌s減算法；針對模平方運(yùn)算，通過預(yù)處理的方式建立查找表，并結(jié)合模運(yùn)算同時(shí)處理，提出一種快速模平方算法；針對逆運(yùn)算，結(jié)合擴(kuò)展Euclideam算法，提出一種求模逆算法；最后，基于Montgomery算法設(shè)計(jì)了二進(jìn)制域上的標(biāo)量乘快速實(shí)現(xiàn)方案。理論和實(shí)驗(yàn)分析表明，本文方案減少了計(jì)算過程的基本運(yùn)算和內(nèi)存讀寫次數(shù)，提高了標(biāo)量乘法的計(jì)算效率。


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

http://theprogrammingfactory.com/resource/share/2000006102


作者信息：

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

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

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

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


Magazine.Subscription.jpg

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。