胡海峰　王瑞堯

摘? ?要：針對傳感器網(wǎng)絡(luò)所處環(huán)境惡劣、攜帶能源較少的特點(diǎn)，論文提出了一種基于等價(jià)替換標(biāo)量乘法的橢圓曲線加密算法。該算法是在素場上對標(biāo)量乘法進(jìn)行基于點(diǎn)的階的等價(jià)替換，減少標(biāo)量乘法運(yùn)算量的新方法。通過分析，在給定區(qū)間內(nèi)，新方法比傳統(tǒng)標(biāo)量乘法的計(jì)算量大大減少，計(jì)算速度大大增加，并給出了階為奇數(shù)或偶數(shù)時(shí)，計(jì)算量減少的加速度。該方法由于加密運(yùn)算數(shù)據(jù)量少、加密速度快、加密時(shí)消耗能量低，適合用于無線傳感網(wǎng)絡(luò)中。

關(guān)鍵詞：無線傳感網(wǎng)絡(luò)（WSN）;橢圓曲線算法（ECC）;等價(jià)替換;標(biāo)量乘法

中圖分類號：TP392? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A

Research on ECC of equivalent substitution scalar multiplication suitable for WSN

Hu Haifeng， Wang Ruiyao

（College of Information Engineering， Pingdingshan University， HenanPingdingshan 467000

Abstract： In the view of the harsh environment and less energy carried by sensor networks， an elliptic curve encryption algorithm based on equivalent substitution scalar multiplication is proposed in this paper. This algorithm is a new method to reduce the computation amount of scalar multiplication by an equivalent representation of points based on point order on the prime field. Through the analysis， the new method greatly reduces the calculation amount and increases the calculation speed compared with the traditional scalar multiplication in the given interval. This method is suitable for wireless sensor networks due to the decrease of data volume and the increase of encryption speed.

Key words： wireless sensor network; elliptic curve cryptography; equivalent substitution; scalar multiplication

1 引言

在信息化社會(huì)，數(shù)據(jù)安全是應(yīng)用的前提。因此，在無線傳感網(wǎng)絡(luò)中需要對數(shù)據(jù)采集、處理、傳輸?shù)冗^程加以保護(hù)，否則會(huì)造成信息泄漏、信息偽造，進(jìn)而導(dǎo)致決策錯(cuò)誤[1]，解決這些問題的最好方法就是對數(shù)據(jù)進(jìn)行加密。而傳感器網(wǎng)絡(luò)一般部署在惡劣環(huán)境中，所攜帶能源較少，僅具有有限的環(huán)境感應(yīng)能力、計(jì)算能力和無線通信能力。因此，傳統(tǒng)的加密技術(shù)無法直接應(yīng)用在傳感器網(wǎng)絡(luò)中，這就要求必須設(shè)計(jì)出能夠滿足傳感器網(wǎng)絡(luò)應(yīng)用的耗能較低的加密算法。

2 等價(jià)替換標(biāo)量乘法的研究

在橢圓曲線E上有一點(diǎn)p，如果存在最小的正整數(shù)n，使得np=0成立，則稱n是點(diǎn)p的階[2]。橢圓曲線加密算法采用隨機(jī)從[1，n-1]中選取一個(gè)數(shù) k和橢圓上一點(diǎn)p。kp的計(jì)算稱為數(shù)乘或標(biāo)量乘法，它決定著橢圓曲線密碼體質(zhì)的運(yùn)算速度和實(shí)現(xiàn)效率[3]。

在計(jì)算kp的過程中，，即進(jìn)行k-1次加法運(yùn)算。如果在加法運(yùn)算時(shí)，能以2n倍增時(shí)，運(yùn)算的次數(shù)將會(huì)大大減少。如進(jìn)行32k計(jì)算時(shí)，需要進(jìn)行31次加法運(yùn)算，其復(fù)雜度為O（k）。如果通過p+p=2p，2p+2p=4p，……16p+16p=32p，只需進(jìn)行5次加法運(yùn)算，其復(fù)雜度為O（log2k）。如果能夠找到一個(gè)數(shù)d來代替k，并且log2k-log2d≥0，那么就可以減少標(biāo)量乘法的運(yùn)算量。

（1）在橢圓曲線上任取一點(diǎn)p，點(diǎn)p的階為n，有np=0。則當(dāng)k>n時(shí)，有，這反映了橢圓曲線上的標(biāo)量乘法運(yùn)算的一種周期性。因此，如果k>n，dp可以代替kp，。

（2）因?yàn)閚p=0，所以，（n-1）p=-1p;（n-2）p=-2p;（n-3）p=-3p;……;1p=（1-n）p。當(dāng)k在區(qū)間取值時(shí)，用dp代替kp，d=k-n，此情況下，，只需把縱坐標(biāo)加一個(gè)負(fù)號即可。而|d|要遠(yuǎn)小于k，因此，可以節(jié)省大量計(jì)算時(shí)間。

（3）k在區(qū)間取值時(shí)，dp也可以代替kp，d=k。

因此，按照上述三條內(nèi)容，在區(qū)間[1， n-1]內(nèi)的等價(jià)表示點(diǎn)dp 可以替換主要標(biāo)量乘法運(yùn)算中的點(diǎn)kp（其中k>d），在一般情況下，通過公式（1）獲取dp的值。

（1）

為了更好地說明等價(jià)替換標(biāo)乘方法，使用一個(gè)具體的例子進(jìn)行描述。選擇質(zhì)數(shù)z=23。在實(shí)際情況下，z的取值要比23大得多。如果考慮e23（1，1）定義的橢圓E： y2=x3+x+1，設(shè)p（3，0）為基點(diǎn)，那么#E（GF（p））=28，GF（p）是一個(gè)循環(huán)群。因此，27P=-P=（3，?10mod23）=（3，13），同理，[15p，16p，…，26p，27p]計(jì)算出的點(diǎn)可分別替換為[-13p，-12p，…，-2p，-p]。在這種情況下，計(jì)算27p時(shí)，需要計(jì)算24p+23p+2p+p=27p。而-p與27p坐標(biāo)相同，且在橢圓曲線上。-p可以通過p的縱坐標(biāo)加負(fù)號獲得，計(jì)算量可以忽略不計(jì)。如果用-p代替27p，只需計(jì)算p的值即可，因此計(jì)算量將會(huì)大大減少。