基于带符号整数拆分形式的抗功耗攻击方案

闫 娜

(永城职业学院 电子信息工程系，河南 永城 476600)

基于带符号整数拆分形式的抗功耗攻击方案

闫 娜

(永城职业学院 电子信息工程系，河南 永城 476600)

为抗功耗攻击椭圆曲线密码算法的运算效率，文中给出一种基于整数拆分形式的抗功耗攻击方案。通过将标量进行带符号的整数拆分形式编码，同时结合预计算和标量分割的方法将标量乘运算转化为一组椭圆曲线上的点加运算，然后采用基点掩码实施抗功耗攻击。算法安全性及性能分析结果表明，所给方案的运算效率与传统的抗功耗攻击方法相比明显提高，能够较好地满足安全芯片等资源受限的应用系统。

椭圆曲线密码；功耗攻击分析；带符号的整数拆分；多标量乘算法；标量分割

0 引 言

1998年，Paul Kocherr率先提出功耗攻击方法[1]，它是一种利用密码芯片在运作时泄露的功率消耗信息而获得密钥有关信息的非常有效的密码破解技术，这种攻击技术具备实现简易，攻击成功率大的优势，同传统的数学攻击技术具备更大的威胁[2-3]。根据攻击者实施攻击采用的攻击方式不同，主要能够分成简单功耗攻击(Simple Power Attack, SPA)与差分功耗攻击(Differential Power Attack, DPA)等。因把椭圆曲线密码算法与其它的传统公钥密码算法进行比较来说，在同样的安全级别条件下具备所需密钥长度更短、存储空间更小等优点，更加适用于密码芯片等资源受限设备，因此存在许多针对椭圆曲线密码的功耗攻击。当前，椭圆曲线功耗攻击的方式主要包括零值寄存器功耗分析攻击(Zero-value Power Attack, ZPA)与零值点功耗分析攻击(Refined Power Attack, RPA)等[4-5]。

通过将标量利用带符号整数拆分(signed integer splitting , SIS)形式进行编码[6]，把大标量乘法运算转化成一组带系数的由固定且已知标量的小标量乘运算的累加和的形式，然后利用标量分割的随机化技术，同时结合预计算表的方法，提出了一种高效安全的基于整数拆分形式的椭圆曲线密码抗功耗分析攻击方案，所给方面不仅能够抵御各种功耗攻击方法，而且可以有效大幅提升椭圆曲线密码抗功耗攻击算法的计算效率，所以能够同时兼顾效率与安全两个方面的需要，因而所给的抗功耗攻击方案能够满足加解密芯片等资源受限制的密码系统中，具有重要的研究意义与实用价值。

1 带符号整数拆分标量乘快速算法

(1)

(2)

算法1 基于SIS的标量乘快速算法

输入：k，P；

输出：Q=kP。

1. 计算(um,um-1,…,u1)；

2. 构造出预计算表Pi；

3. 令Q=O；

4. 对于i从1到n，重复执行：

4.1 若ui=1，则Q=Q+Pi；

4.2 若ui=-1，则Q=Q-Pi；

5. 返回Q。

其中，构造的预计算表Pi=a(i)P是固定的且已知的，详细的构造算法描述如算法2所示：

算法2 预计算表Pi的生成算法

输入：n，P；

输出：预计算表Pi。

1. 令Q=O；

2. 对于i从1到n，重复执行：

2.1S=2Q；

2.2Pi=S+P；

2.3Q=Pi+Q；

3. 返回Pi。

2 SIS标量乘潜在的功耗攻击威胁

(1)算法1的步骤4循环操作中，尽管仅执行点加运算，但是对于整体的循环过程依然有功耗差异，拆分系数ui=±1时，执行了一次点加操作，ui=0时，仅执行空操作。攻击者可根据点加操作执行顺序和次数，能够推测出标量的拆分系数ui，进而可以较为容易地获取全部的密钥信息，所以算法1易遭受SPA攻击。

(2)因为基点P是固定的，它的密钥信息同输入之间存在相关性。攻击者推测拆分系数ui错误时，在进行了多次功耗统计分析后，执行空操作与点加操作之间的功耗差异界限不明显；攻击者推测拆分系数ui正确时，在进行了多次功耗统计分析后，出现了明显的功耗差异界限，因而攻击者能够推测获得拆分系数与类基间的关系，进而能够推断出全部的密钥信息，所以算法1易遭受DPA攻击。

(3)算法1的标量乘法运算中，基点P为固定的，攻击者能够利用算法中的特殊点(零值点或是零值寄存器)来进行攻击，进而获得密钥的有关信息，所以算法1易遭受RPA和ZPA攻击。

3 基于SIS的标量乘抗功耗攻击方案

根据标量的拆分表示形式可知，对于所有的不大于所给标量的整数皆能够由同样个数的类基表示，所以能够利用标量分割技术，不仅可用于抵御功耗攻击，同时通过引入一个随机整数，把大标量乘法运算转换成为一组小标量乘法运算，并通过共用一个较小的预计算表，从而可进一步提升计算效率。标量分割技术[8]是椭圆曲线标量乘运算中用来抵御功耗攻击的一种盲乘数的随机化技术，通过采用加上随机数r的乘数k′=k+r以代替标量k来进行标量乘运算，即转换为多标量乘运算，下面则给出基于标量分割技术的标量乘运算的一般形式，如式(3)所示：

kP=(xk+pr)(uP)+(yk+qr)(vP)

(3)

式中，r是随机整数，x,y,p,q,u,v是标量分割系数。为有效提升标量乘运算的效率，通常会令x,y,p,q,u,v∈{-2,-1,0,1,2}，标量的分割次数能根据所选的快速算法和安全性需求来确定。

因为当基点固定时，预计算表具有反复可利用性的特点，因而把大标量分割为一组小标量，共用同一张较小的预计算表。采用一次分割为例，假定x=u=q=v=1,p=-1,y=0，则标量乘运算kP=(k-r)P+rP。式中通过减去随机数r，掩饰了原始标量信息与功耗之间的相关性，所以能够抵御DPA攻击。但是攻击者仍能采用拆分系数是0和1时执行不同操作所产生的功耗差异来实施SPA攻击，然而采用添加伪操作方法抵御SPA攻击将造成非必要的效率损失。经分析可知，添加伪操作的位与拆分系数是0的位有关，可通过将两个拆分系数相加而得到一个和系数li，减少ui和vi单独是0的位，以此减少须要添加伪操作的数目，最终实现降低效率损失的目的。同时也可以将和系数ki看作是一个窗口，窗口的宽度是标量分割的次数的和[9]，因而基于SIS的标量乘法运算kP能变化为如式(4)所示：

kP=(k-r)P+rP=

l1P1+l2P2+…+ltPt=

(4)

式中，r是所引入的一个随机整数，ui,vi分别是小标量(k-r)和r的拆分系数，t,s分别是小标量(k-r)和r的拆分数列的个数，并且有t≥s，vs+1=vs+2=…=vt=0，所以新构造出的预计算表Pi的长度是t，li是已给标量k在进行一次分割后的两个拆分系数的和系数，而且有li∈{-2，-1，0，1，2}。因为所得窗口宽度是2，因而有e∈{1，2}，并且可得Qe=∑i:li=ePi。

根据式(4)可知，标量乘法运算转换为一个窗口宽度为2的基于SIS标量乘运算，然后结合抵御SPA攻击的伪操作方法，下面给出了同时能够兼顾效率与安全两方面的基于整数拆分形式的椭圆曲线密码抗功耗攻击的方案。下面算法3给出了基于SIS的椭圆曲线密码抗功耗攻击算法的详细描述过程：

算法3 基于SIS的快速标量乘抗功耗攻击算法

输入：k，P；

输出：kP。

1.r=random(),h=k-r；

2. 计算SIS(h)=(ut,ut-1,…,u1)；

3. 计算SIS(r)=(vt,vt-1,…,v1)；

4. 计算和系数li=(lt,lt-1,…,l1)；

5. 构造出预计算表Pi；

6. 令Q=O，E=O；

7. 对于e从2到1，重复执行：

7.1 对于i从1到t，重复执行：

7.1.1 若li=e，则E=E+Pi；

7.1.2 若li=-e，则E=E-Pi；

7.1.3 否则li=0，则T=E+P；

7.2Q=Q+E；

8. 返回Q。

4 仿真及性能分析

4.1 安全性分析

可以通过采用文献[10]给出的功耗仿真实验平台对所给抗功耗攻击方案进行抗功耗攻击实验仿真，如图1所示。实验对象为IC卡智能芯片，其内嵌CPU为32位的ARM处理器，并利用VHDL语言对所给设计方案完成硬件描述；然后选用一个合适的单片机将设计方案综合到FPGA开发板上进行模拟仿真，通过选用相关参数执行指定的加密或解密功能；最后则根据在VSS与地之间所串联的电阻来测量单片机在执行加解密运算指令时的功率消耗波形，并把采样所获得的数据信息存储到示波器中，接着则通过采用通讯软件把得到的数据传输到PC机上，同时应用Matlab等有关数据处理软件实施数据的处理和分析。

图1 功耗数据采集实验平台

首先，对算法1的基于SIS标量乘算法实施功耗仿真，可以得到未施加任何抗功耗攻击措施的功耗轨迹波形图谱，如图2所示。

图2 基于SIS标量乘算法功耗轨迹

算法3中，通过使用标量分割的技术，把标量减去一个随机的整数，从而把密钥信息随机化，使得攻击者不能够获取中间运算结果与已给输入之间的相关性信息，因此所给的方案能抵御DPA攻击。并且由于参与标量乘运算的标量已被随机化，使得攻击者无法找到特殊点加以利用，因而所给算法也能够抵抗ZPA和RPA攻击。在步骤7循环操作中，因为和系数li依然能够是0，因此在步骤7.1.3中添加伪操作，从而使得每次循环运算中皆执行两次点加操作，使其能量图谱不存在功耗差异，从而攻击者无法获得相关信息来进行密钥猜测，因而所给算法能够抵御SPA攻击。对算法3的基于SIS标量乘抗功耗攻击算法进行功耗仿真实验，能够得到施加抗功耗攻击措施之后的功耗轨迹波形图谱，如图3所示。

图3 基于SIS标量乘抗功耗攻击算法功耗轨迹

从图2和图3能够看出，在没有施加抗功耗攻击措施的基于SIS标量乘算法，其功耗轨迹波形的图谱具有明显的可分辨性，执行点加操作和空操作在图谱上具有明显的界限，所以攻击者能够实施功耗攻击。然后，在实施抗功耗攻击的措施之后，算法3的功耗轨迹波形图谱却没有明显地波形起伏，攻击者可对大量功耗轨迹曲线进行统计分析却无法得到相关性的信息，所以攻击者无法对算法3实施功耗分析攻击。

4.2 效率分析

算法3中，步骤1、2、3和4所需运算量能够忽略不计。因为预计算表已知且固定，能够预先存储到应用系统中，不再需要重复进行计算。步骤7中的主循环运算所需的运算量是tA。其中，D是倍点运算，A是点加运算，c是大标量的二进制编码长度，t是进行一次标量分割后的小标量的SIS编码长度，w是窗口宽度，一般令w=4，b=⎣c/w」。通常认为椭圆曲线密码512比特的密钥是安全的，也即c=512。在进行了一次标量分割后，则有小标量的整数拆分形式的最大编码长度是t=323。文献[11]中给出在仿射坐标系下，倍点运算是D=11M，点加运算是A=6M，M是模乘运算。下面的表1则给出了算法3和WBRIP算法、EBRIP算法[12]三种抗功耗攻击方案在执行效率方面的分析比较。

从表1能够看出，算法3与WBRIP算法和EBRIP算法功耗攻击方案相比，效率分别提高了69.72%和10.94%，这将在很大程度上满足芯片等便携式设备的高效性需求，同时也说明在固定基点的标量乘运算中，所给新方案具有更优良的性能。另外，还能够根据安全和效率的需求实施多次标量分割。根据性能分析的结果表明：所给方案能够满足安全和效率两个方面的需要，尤其是能够适用于对于存储空间要求不是很高的密码加密部件等应用系统中。

表1 算法3和WBRIP算法、EBRIP算法抗功耗攻击方案的执行效率比较分析

5 结 语

通过结合基于带符号的整数拆分形式多标量乘快速算法和标量分割随机化技术所给出的椭圆曲线密码抗功耗攻击方案，能够抵抗多种功耗攻击，并且具有更加高效的计算效率。同时因为所给新方案构造生成的预计算表为固定的且已知的，因而能够预先存储到应用系统中，不再需要重新计算，接下来就仅需考虑主循环的加密运算。新方案可以更好地应用在安全芯片等一些资源受限的各类便携式系统中，具有很好的理论研究和实际应用价值。

[1] Kocher P,Jaffe J, Jun B. Introcuction to differential power analysis and related attacks [EB/OL]. http://www.Cryptography.com/dpa/technical,1998.

[2] Kocher P,Jaffe J,Jun B. Differential power analysis [C]. Advanced in Cryptology-CRYPTO’99. Cali- fornia, USA：Springer Verlag，1999：388-397．

[3] 张友桥，周武能，申晔，等．椭圆曲线密码中抗功耗分析攻击的标量乘改进方案[J]．计算机工程与科学，2014，36(4)：644-648．

[4] 姚建波，张涛．抗侧信道攻击的安全有效椭圆加密算法[J]．计算机应用研究，2012，29(12)：4639-4643．

[5] 王正义，赵俊阁．基于带符号双基数系统的抗功耗攻击方案算法[J]．计算机应用，2011，31(11)：2973-2974．

[6] 张亮．改进的基于整数拆分形式标量乘快速算法[J]．中国电子科学研究院学报，2016，11(5)：56-59．

[7] 石润华，钟诚．一种快速的椭圆曲线标量乘方法[J]．计算机工程与应用，2006，(2)：156-158．

[8] 童莲，刘宁，钱江．改进的抗能量分析的椭圆曲线标量乘算法[J]．计算机工程与应用，2011，47(33)：68-70．

[9] 陈厚友，马传贵．椭圆曲线密码中一种多标量乘算法[J]. 软件学报，2011，22(4)：782-788．

[10]罗鹏，冯登国，周永彬．功耗分析攻击中的功耗与数据相关性模型[J]．通信学报，2012，33(z1)：276-281．

[11]王玉玺，张串绒，张柄虹，等．基于素数域上复合运算的快速标量乘算法[J]．计算机应用研究，2013，30(11)：3365-3387．

[12]Mamiya H. Efficient countermeasures against RPA, DPA and SPA [C]. Proc of Cryptographic Hardware and Embedded System. 2004：343-356．

Resisting Power Attacks Scheme Based on Signed Integer Splitting Form

YAN Na

(Department of Electronic Information Engineering, Yongcheng Vocational College, Yongcheng 476600, China)

The contradiction between efficiency and security lies in the scheme of resisting power analysis attack for ellipse curve cryptography due to the limited resource of security chip. Combining with the method of the pre-computation table and scalar division, scalar multiplication was turned into a set of point addition of ellipse curve by coding the scalar with signed integer splitting form. And then a scheme based on Signed Integer Splitting Form was presented by basic point masking algorithm. Security and performance analysis shows that the improved scheme has higher efficiency comparing with other resisting power analysis attacks and could be used in the limited resource system preferably.

Ellipse Curve Cryptography (ECC); power analysis attack; Signed Integer Splitting (SIS); multiple scalar multiplication algorithm; scalar division

10.3969/j.issn.1673-5692.2017.04.020

2017-05-27

2017-07-01

河南省科技发展计划项目(152102210039)

闫 娜(1982—)，女，河南人，硕士，讲师，主要研究方向为计算机应用;

E-mail:xinlinzh2@163.com

TP309

A

1673-5692(2017)04-438-05