论文部分内容阅读
摘要： 为提高智能电网ECC公钥算法中椭圆曲线标量乘的快速性和安全性，提出一种新算法——四进制快速标量乘算法，在Jacobi坐标上计算4P和4kP，在Jacobi-Affine坐标上计算点加，实现标量乘运算的快速性；在此基础上，提出一种改进算法——四进制分段并行标量乘算法，通过采用分段并行算法，隐藏真实能量消耗，以提高新算法的安全性。研究表明：与NAF标量乘算法相比，四进制分段标量乘算法效率提高了57.9%，并能有效抵御SPA攻击，可根据设备的存储能力获得不同的运算效率。新算法及其改进算法对改善椭圆曲线密码体制的性能具有一定理论意义与工程应用价值。
关键词： 椭圆曲线密码；四进制；标量乘；边信道攻击，信息安全
【中图分类号】TP309.7【文献标识码】B【文章编号】2236-1879（2017）21-0002-02
0 引言
智能电网信息安全是智能电网建设中的关键环节，国内学者在互联电力信息安全与安全管理、电力信息系统网络安全态势评估以及智能电网数据安全存储等方面做了大量的研究[1-4]。椭圆曲线密码体制（elliptic curve cryptography， ECC） 具有安全性高、密钥长度短、计算量小、计算速度快、[]占用存储空间少、带宽要求低等特点，而且ECC公钥算法不存在知识产权问题，因而被广泛应用于智能电网信息安全建设[5-8]。标量乘运算是ECC中最主要的运算算法，即椭圆曲线非相邻形式（NAF）采用二进制编码，在单个坐标系上运算点加和点乘，具有耗时低效和不能抵御边信道（SCA）的缺陷。快速、安全实现椭圆曲线密码体制对保证智能电网信息安全至关重要，因此如何提高标量乘的效率和抵御边信道攻击是提高椭圆曲线密码算法性能的关键。
本文针对椭圆曲线标量乘的快速实现和安全性，在NAF标量乘算法的基础上，提出一种新算法——四进制快速标量乘算法，在Jacobi坐标上计算4P 和4kP ，在Jacobi-Affine坐标上计算点加，实现标量乘运算的快速性；在此基础上，提出两种改进算法——四进制分段并行标量乘算法通过采用分段并行算法，隐藏真实能量消耗，以提高新算法的安全性。
1 椭圆曲线标量乘运算
1.1 椭圆曲线定义。
定义1 设q元有限域K=Fq，其中q=pn，E是定义在K=Fq上的Weierstrass 等式为
y2+a1 xy+a3y=x3+a2x2+a4x+a6 （1）
其中a1，a2，a3，a4，a6∈K。当K的特征值不等于2、3时的Weierstrass 等式为y2=x3+a4x+a6，其判别式为△=-16（4a3+27b2）。
1.2 不同坐标系下点加和倍点计算量比较。
椭圆曲线上的点在不同坐标下具有不同的表示形式，不同坐标下的点加和倍点的运算量也不同。表1列出不同坐标下点加和倍点所需的域操作次数。其中，A表示仿射坐标，P表示映射坐标，J表示Jacobi坐标，C表示Chudnovsky坐标，I表示有限域求逆运算，M表示有限域乘法运算，S表示有限域乘方运算。
1.3 椭圆曲线NAF标量乘算法。
整数k的一个带符号的二进制表示（kl-1，…，k0），如果其中没有两个连续的ki是非零的，则说它是非相邻的形式。这样的表示称为NAF表示。整数k的一个带符号的二进制表示可以很容易的转化为NAF表示。转换的基础是，在二进制表示中，用（1，0，0，0，-1）替换（0，0，0，1），而这种替换并不改变k的值，因为有等式
2i+2i-1+…+2j=2i+1-2i（2）
这里i>j。这个过程从最低位的比特开始向高位，按需要重复进行。
通过实例阐述上述过程：
（1， 1， 1， 1 0， 0， 1， 1， 0， 1， 1， 1）
↓
（1， 1， 1， 1， 0， 0， 1， 1， 1， 0， 0，-1）
↓
（1， 1， 1， 1， 0， 1， 0， 0，-1， 0， 0，-1）
↓
（1， 0， 0， 0，-1， 0， 1， 0， 0，-1， 0， 0，-1）
任意整数k的NAF表示都是唯一的，且在k的所有带符号序列中零位个数最多。可以证明，一个l比特整数的二进制表示中含有2l/3个零。
设P是一个阶为n的椭圆曲线的点。计算整数k的NAF形式，其中0kn-1，算法1可以计算出椭圆曲线上点P的乘积kP。
算法1 NAF标量乘算法
在算法1中，计算kP需要l次乘法和l/3次加（减）法，由坐标系最优组合，算法1的运算量为l（2M+8S）+l/3（8M+3S）。
2 算法安全性分析
2.1 对SPA安全性分析。
因为加密过程中不同的操作有不同能量消耗，所以攻击者可以判断以什么样的顺序进行了什么样的操作，这是SPA能成功的基础。表4列出了文中主要标量乘算法对SPA的安全性。
2.2 对DPA的安全性分析。
DPA与SPA不同，它不仅与不同的操作有关，而且还与运算过程中出现的中间值有关，因此攻击能力更强。DPA能够成功攻击密码系统的前提是：加密电路的功率信号与密码系统的密钥及敏感数据存在相关性。其攻击过程描述如下：
1）输入P输出Q=KP，得到功耗曲线L′j；
2）假设Ki=0，其余位为任意值，再执行一次算法，得到功率曲线L′j；
3）构造差分功耗曲线Sj=Lj-Lj。
由于运算是从k的最高位开始扫描的，两次输入相同，k和K′前n-i-1位相同，则中间值也相同；当扫描到第i位时，如果Ki=K′i，则Dj=0（i=j），反之差分功耗曲线出现明显尖峰，同理可以猜测其余位。
算法1、4和5并不能抵御DPA而其原因为：当攻击者通过DPA分析h时，由表5可知，|Ki+li|=0，1，4时的计算量均为零，则对应的中间值相同，因此攻击无法猜测其对应的hn，自然无法得到正确的四进制序列。
3 结论
为提高智能电网ECC公钥算法中椭圆曲线标量乘的快速性和安全性，针对采用二进制编码的标量乘算法的不足，提出了基于四进制的快速安全标量乘算法，并证明了新算法的优越性，得出以下结论：
（1）四进制分段标量乘算法在不预存储点4mP（0mn/2）坐标的情况下，比传统NAF标量乘算法效率提高了33.1%；如果预存儲点4mP（0mn/2）坐标的情况下，效率提则高了57.9%。相比于文献算法也有10%以上的提升。
（2）算法4由于只需预存储2P和-2P的坐标，且具有较高的效率，故更适合存储空间十分有限的设备，如智能卡；算法5具有一定的弹特性，可以根据设备的存储能力获得不同的运算效率，故适用范围更广。
（3）改进型算法能完全抵御SPA攻击；而对DPA同样具有较好的抗性，在安全性能上也有较大的提升。
参考文献
[1]李文武， 游文霞， 王先培. 电力系统信息安全研究综述[J]. 电力系统保护与控制， 2011， 39（10）： 140-147.
[2]刘念，张建华.互动用电力式下的信息安全风险与安全需求分析[J].电力系统自动化，2011，35（2）： 79-83.
[3]镐俊杰， 王丹， 杨东海. 电力信息系统网络安全态势在线评估框架与算法研究[J]. 电力系统保护与控制， 2013， 41（9）： 116-120.
关键词： 椭圆曲线密码；四进制；标量乘；边信道攻击，信息安全
【中图分类号】TP309.7【文献标识码】B【文章编号】2236-1879（2017）21-0002-02
0 引言
智能电网信息安全是智能电网建设中的关键环节，国内学者在互联电力信息安全与安全管理、电力信息系统网络安全态势评估以及智能电网数据安全存储等方面做了大量的研究[1-4]。椭圆曲线密码体制（elliptic curve cryptography， ECC） 具有安全性高、密钥长度短、计算量小、计算速度快、[]占用存储空间少、带宽要求低等特点，而且ECC公钥算法不存在知识产权问题，因而被广泛应用于智能电网信息安全建设[5-8]。标量乘运算是ECC中最主要的运算算法，即椭圆曲线非相邻形式（NAF）采用二进制编码，在单个坐标系上运算点加和点乘，具有耗时低效和不能抵御边信道（SCA）的缺陷。快速、安全实现椭圆曲线密码体制对保证智能电网信息安全至关重要，因此如何提高标量乘的效率和抵御边信道攻击是提高椭圆曲线密码算法性能的关键。
本文针对椭圆曲线标量乘的快速实现和安全性，在NAF标量乘算法的基础上，提出一种新算法——四进制快速标量乘算法，在Jacobi坐标上计算4P 和4kP ，在Jacobi-Affine坐标上计算点加，实现标量乘运算的快速性；在此基础上，提出两种改进算法——四进制分段并行标量乘算法通过采用分段并行算法，隐藏真实能量消耗，以提高新算法的安全性。
1 椭圆曲线标量乘运算
1.1 椭圆曲线定义。
定义1 设q元有限域K=Fq，其中q=pn，E是定义在K=Fq上的Weierstrass 等式为
y2+a1 xy+a3y=x3+a2x2+a4x+a6 （1）
其中a1，a2，a3，a4，a6∈K。当K的特征值不等于2、3时的Weierstrass 等式为y2=x3+a4x+a6，其判别式为△=-16（4a3+27b2）。
1.2 不同坐标系下点加和倍点计算量比较。
椭圆曲线上的点在不同坐标下具有不同的表示形式，不同坐标下的点加和倍点的运算量也不同。表1列出不同坐标下点加和倍点所需的域操作次数。其中，A表示仿射坐标，P表示映射坐标，J表示Jacobi坐标，C表示Chudnovsky坐标，I表示有限域求逆运算，M表示有限域乘法运算，S表示有限域乘方运算。
1.3 椭圆曲线NAF标量乘算法。
整数k的一个带符号的二进制表示（kl-1，…，k0），如果其中没有两个连续的ki是非零的，则说它是非相邻的形式。这样的表示称为NAF表示。整数k的一个带符号的二进制表示可以很容易的转化为NAF表示。转换的基础是，在二进制表示中，用（1，0，0，0，-1）替换（0，0，0，1），而这种替换并不改变k的值，因为有等式
2i+2i-1+…+2j=2i+1-2i（2）
这里i>j。这个过程从最低位的比特开始向高位，按需要重复进行。
通过实例阐述上述过程：
（1， 1， 1， 1 0， 0， 1， 1， 0， 1， 1， 1）
↓
（1， 1， 1， 1， 0， 0， 1， 1， 1， 0， 0，-1）
↓
（1， 1， 1， 1， 0， 1， 0， 0，-1， 0， 0，-1）
↓
（1， 0， 0， 0，-1， 0， 1， 0， 0，-1， 0， 0，-1）
任意整数k的NAF表示都是唯一的，且在k的所有带符号序列中零位个数最多。可以证明，一个l比特整数的二进制表示中含有2l/3个零。
设P是一个阶为n的椭圆曲线的点。计算整数k的NAF形式，其中0kn-1，算法1可以计算出椭圆曲线上点P的乘积kP。
算法1 NAF标量乘算法
在算法1中，计算kP需要l次乘法和l/3次加（减）法，由坐标系最优组合，算法1的运算量为l（2M+8S）+l/3（8M+3S）。
2 算法安全性分析
2.1 对SPA安全性分析。
因为加密过程中不同的操作有不同能量消耗，所以攻击者可以判断以什么样的顺序进行了什么样的操作，这是SPA能成功的基础。表4列出了文中主要标量乘算法对SPA的安全性。
2.2 对DPA的安全性分析。
DPA与SPA不同，它不仅与不同的操作有关，而且还与运算过程中出现的中间值有关，因此攻击能力更强。DPA能够成功攻击密码系统的前提是：加密电路的功率信号与密码系统的密钥及敏感数据存在相关性。其攻击过程描述如下：
1）输入P输出Q=KP，得到功耗曲线L′j；
2）假设Ki=0，其余位为任意值，再执行一次算法，得到功率曲线L′j；
3）构造差分功耗曲线Sj=Lj-Lj。
由于运算是从k的最高位开始扫描的，两次输入相同，k和K′前n-i-1位相同，则中间值也相同；当扫描到第i位时，如果Ki=K′i，则Dj=0（i=j），反之差分功耗曲线出现明显尖峰，同理可以猜测其余位。
算法1、4和5并不能抵御DPA而其原因为：当攻击者通过DPA分析h时，由表5可知，|Ki+li|=0，1，4时的计算量均为零，则对应的中间值相同，因此攻击无法猜测其对应的hn，自然无法得到正确的四进制序列。
3 结论
为提高智能电网ECC公钥算法中椭圆曲线标量乘的快速性和安全性，针对采用二进制编码的标量乘算法的不足，提出了基于四进制的快速安全标量乘算法，并证明了新算法的优越性，得出以下结论：
（1）四进制分段标量乘算法在不预存储点4mP（0mn/2）坐标的情况下，比传统NAF标量乘算法效率提高了33.1%；如果预存儲点4mP（0mn/2）坐标的情况下，效率提则高了57.9%。相比于文献算法也有10%以上的提升。
（2）算法4由于只需预存储2P和-2P的坐标，且具有较高的效率，故更适合存储空间十分有限的设备，如智能卡；算法5具有一定的弹特性，可以根据设备的存储能力获得不同的运算效率，故适用范围更广。
（3）改进型算法能完全抵御SPA攻击；而对DPA同样具有较好的抗性，在安全性能上也有较大的提升。
参考文献
[1]李文武， 游文霞， 王先培. 电力系统信息安全研究综述[J]. 电力系统保护与控制， 2011， 39（10）： 140-147.
[2]刘念，张建华.互动用电力式下的信息安全风险与安全需求分析[J].电力系统自动化，2011，35（2）： 79-83.
[3]镐俊杰， 王丹， 杨东海. 电力信息系统网络安全态势在线评估框架与算法研究[J]. 电力系统保护与控制， 2013， 41（9）： 116-120.