适合WSN的等价替换标量乘法ECC加密算法研究

胡海峰　王瑞尧

摘   要：针对传感器网络所处环境恶劣、携带能源较少的特点，论文提出了一种基于等价替换标量乘法的椭圆曲线加密算法。该算法是在素场上对标量乘法进行基于点的阶的等价替换，减少标量乘法运算量的新方法。通过分析，在给定区间内，新方法比传统标量乘法的计算量大大减少，计算速度大大增加，并给出了阶为奇数或偶数时，计算量减少的加速度。该方法由于加密运算数据量少、加密速度快、加密时消耗能量低，适合用于无线传感网络中。

关键词：无线传感网络（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 引言

在信息化社會，数据安全是应用的前提。因此，在无线传感网络中需要对数据采集、处理、传输等过程加以保护，否则会造成信息泄漏、信息伪造，进而导致决策错误[1]，解决这些问题的最好方法就是对数据进行加密。而传感器网络一般部署在恶劣环境中，所携带能源较少，仅具有有限的环境感应能力、计算能力和无线通信能力。因此，传统的加密技术无法直接应用在传感器网络中，这就要求必须设计出能够满足传感器网络应用的耗能较低的加密算法。

2 等价替换标量乘法的研究

在椭圆曲线E上有一点p，如果存在最小的正整数n，使得np=0成立，则称n是点p的阶[2]。椭圆曲线加密算法采用随机从[1，n-1]中选取一个数 k和椭圆上一点p。kp的计算称为数乘或标量乘法，它决定着椭圆曲线密码体质的运算速度和实现效率[3]。

在计算kp的过程中，，即进行k-1次加法运算。如果在加法运算时，能以2n倍增时，运算的次数将会大大减少。如进行32k计算时，需要进行31次加法运算，其复杂度为O（k）。如果通过p+p=2p，2p+2p=4p，……16p+16p=32p，只需进行5次加法运算，其复杂度为O（log2k）。如果能够找到一个数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在区间取值时，用dp代替kp，d=k-n，此情况下，，只需把纵坐标加一个负号即可。而|d|要远小于k，因此，可以节省大量计算时间。

（3）k在区间取值时，dp也可以代替kp，d=k。

因此，按照上述三条内容，在区间[1， n-1]内的等价表示点dp 可以替换主要标量乘法运算中的点kp（其中k>d），在一般情况下，通过公式（1）获取dp的值。

（1）

为了更好地说明等价替换标乘方法，使用一个具体的例子进行描述。选择质数z=23。在实际情况下，z的取值要比23大得多。如果考虑e23（1，1）定义的椭圆E： y2=x3+x+1，设p（3，0）为基点，那么#E（GF（p））=28，GF（p）是一个循环群。因此，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的值即可，因此计算量将会大大减少。