適合WSN的等價替換標量乘法ECC加密算法研究

胡海峰　王瑞堯

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

關鍵詞：無線傳感網(wǎng)絡（WSN）;橢圓曲線算法（ECC）;等價替換;標量乘法

中圖分類號：TP392? ? ? ? ? 文獻標識碼：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 引言

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

2 等價替換標量乘法的研究

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

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

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

（2）因為np=0，所以，（n-1）p=-1p;（n-2）p=-2p;（n-3）p=-3p;……;1p=（1-n）p。當k在區(qū)間取值時，用dp代替kp，d=k-n，此情況下，，只需把縱坐標加一個負號即可。而|d|要遠小于k，因此，可以節(jié)省大量計算時間。

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

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

（1）

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