密码芯片上高效的ECC抗功耗攻击方案

汤 震

(黄淮学院，河南驻马店 463000)

0 引 言

功耗攻击技术给密码芯片的安全带来了极大的威胁，但由于密码芯片自身资源限制，造成其了在采用防御功耗攻击的方法后，将会降低密码芯片运算效率，这就产生了效率与安全的矛盾，如何解决这一矛盾则成为密码芯片研究的热点问题。功耗攻击是Paul Kocher在1998年首先提出的密码分析方法，主要工作原理是密码芯片运行时，不同操作产生的功耗不同，通过采集这些泄露的功耗信息，并分析功耗之间的差异即可获取相关密钥信息。而且功耗分析具有易于实现、成功率高等诸多良好攻击特性，因而相较于传统数学攻击方法而言，功耗分析对密码芯片所带来的安全威胁更严重[1-2]。一般来说，功耗分析因攻击手段不同主要分为两类：简单功耗攻击技术(Simple Power Attack, SPA)和差分功耗攻击技术(Differential Power Attack, DPA)。其中，密码芯片中的主流算法大都是采用椭圆曲线密码(Elliptic Curve Cryptogram, ECC)算法，这主要是因为ECC算法与传统非对称密码算法相比而言，在安全性相同的情况下ECC算法有诸如密钥长度更短，存储空间更小等一系列优势，这使得ECC算法更能够适合用在资源受限的系统[1]。然而，当前出现了许多针对ECC的功耗攻击，包括零值寄存器攻击(Zero-value Power Attack, ZPA)与零值点攻击(Refined Power Attack, RPA)[3-4]。国内外学者关于密码芯片的抗功耗攻击方面做了大量研究工作。Mamiya H等人[5]给出了一种基于窗口随机化初始点的ECC抗功耗攻击方案(Window-Based Random Initial Point, WBRIP)，基本思想是通过将标量的二进制编码进行窗口化，在一个窗口内实现掩盖所执行的点加运算与倍点运算次数的目的，致使攻击者无法从中间值猜测运算过程中所执行的具体操作及相关步骤，尽管WBRIP可以抵抗多种功耗攻击，但是其运算效率需进一步提高。张涛等人[6]给出了一种固定窗口宽度为w的非邻接表示形式的ECC抗功耗攻击算法(Fractional Width-w Non Adjacent From, FWNAF)，主要思想是利用二进制的非邻接表示形式来优化编码，减少在抵抗功耗攻击过程中所需添加伪操作的次数，从而实现运算效率的提升。文献[7]给出一种高效的窗口随机化初始点ECC抗功耗攻击算法(Efficient-Based Random Initial Point, EBRIP)，主要思想是将标量的二进制编码表示成窗口宽度是w的非邻接表示形式，并将其分成整数部分与分数部分可实现抵抗SPA，接着再将基点分成固定部分与可变部分可实现抵抗DPA、ZPA与RPA，并且也可提升运算效率。奇系数Comb算法是ECC标量乘法运算的一种快速计算方法，为保证算法能够抵抗功耗攻击并进一步有效提升运算效率，文中通过在奇系数Comb标量乘算法中结合添加伪操作与基点掩码技术，给出了一种密码芯片上基于奇系数Comb算法的ECC抗功耗攻击算法(Resisting Power Attacks algorithm of ECC based on Odd-only Comb Method, RPAOCM )，同BR、WBRIP及FWNAF算法相比，所给抗功耗攻击算法不仅有相同的抗功耗攻击安全性，而且具有更高的运算效率[2-5]。

1 奇系数Comb标量乘算法

ECC标量乘快速算法主要有两类，一类是通过提高底层域运算来实现，另一类是对标量进行重新编码来实现。其中，奇系数Comb标量乘算法属于第二类快速算法，同时也是常用的ECC标量乘快速算法，与其它同类快速算法(诸如双基数系统快速算法[8]、阶乘展开式快速算法[9]和整数拆分表示形式快速算法[10]等)相比，具有所需存储空间较小、运算效率更高等优点。

下面给出ECC的奇系数Comb标量乘快速算法实施过程：

(1)

通过利用奇系数Comb算法对ECC的正奇数标量进行重新编码，则标量k的奇系数Comb形式编码如式(2)所示：

(2)

其中，li表示标量k的奇系数Comb算法编码系数，且有li≠0。t表示li的编码长度，且有t=「n/s⎤，s表示li的二进制编码长度，n表示k的二进制编码长度。下面对li进行二进制编码可得如下式(3)：

(3)

(4)

则ECC标量乘法的运算形式可转换为如下形式，如式(5)所示：

Q=k·P

(5)

其中，Pi为预计算点，且有各预计算点Pi=(u(s-1)2(s-1)t+…+ui2it+…+u12t+1)·P，ui∈{0,1}。然后根据已预计算出的各预计算点生成预计算表[6-8]。

需要把已知标量k奇数化，且令奇数化后的标量为l。即如果k为正奇数，则l=k+1；但如果k是正偶数，则l=k+2。由于对k进行了奇数化，所以需在返回Q值时增加后处理操作：若k为奇数，则要增加一次Q=Q-2P操作；若k为偶数，则要增加一次Q=Q-P操作。所以ECC标量重新编码之后，则奇系数Comb标量乘运算的具体过程如下面算法1所示[11]：

算法1 ECC的奇系数Comb标量乘快速算法

输入：k,s,P；

输出：Q=kP。

步骤1 对标量k进行奇数化变换成l；

步骤2 令m表示l的二进制长度；

步骤3 生成预计算表Pi；

步骤4 计算奇系数Comb编码长度t=「m/s⎤；

步骤5 计算奇系数Comb编码系数li；

步骤6 令Q=O；

步骤7 对于i从t-1到0，重复执行：

步骤7.1Q=2Q；

步骤7.2Q=Q+liP；

步骤8 返回输出值Q：

步骤8.1 若k为偶数，则返回Q=Q-P;

步骤8.2 若k为奇数，则返回Q=Q-2P。

2 新算法设计

在所给的算法1中，由于标量的奇系数编码系数li都不为0，因而在步骤6中总是执行同样的操作步骤和顺序。也即是，每当执行一次倍点运算后就接着也执行一次点加运算，所获得的能耗图谱基本没有出现显著的功耗曲线差异，这样也就使攻击者不能根据功耗的差异来猜测相关的密钥信息。并且无论所给标量是奇数还是偶数，在步骤8中都会执行一次点加运算，因此所给标量的奇偶性也不会被泄露。因而所给算法1能够防御SPA。然而，因为已知的基点P致使运算中间值和输入之间具有一定的相关性，这就使得攻击者能够利用运算过程的中间值来推测出相关的密钥信息，因而算法1不能防御DPA。与此同时，所给的基点中可能存在有可以被攻击者利用的特殊点，从而使得算法1不能抵抗ZPA与RPA[9-10]。

文中采用了基点掩码技术，即通过在标量乘运算中引入随机点将基点随机化，同时再结合预计算的方法可实现多标量乘法运算中各分基点的随机化，以此即可掩盖每个小标量乘法运算同功耗之间的相关性，这样就致使攻击者无法利用统计分析的方法，通过多次猜测来获取有效的密钥信息。所以，基于奇系数Comb编码标量乘运算Q=kP在引入随机点R之后可转化成如下形式，如式(6)所示：

Q=k·P+R

(6)

其中，因为引入了随机点R，使得在返回Q时，需增加后处理操作来进行恢复：若k为奇数，则增加操作Q=Q-2P-R；若k为偶数，则增加操作Q=Q-P-R。所给基于奇系数Comb的标量乘抗功耗攻击算法具体过程如下面算法2所示：

算法2 基于奇系数Comb的标量乘抗功耗攻击算法

输入：k,P；

输出：Q=kP。

步骤1 对标量k进行奇数化变换成l；

步骤2 令m为奇数化标量l的二进制长度；

步骤3R=random()；

步骤5 计算奇系数Comb编码长度t=「m/s⎤；

步骤6 计算奇系数Comb编码系数li；

步骤7 令Q=R；

步骤8 对于i从t-1到0，重复执行：

步骤8.1Q=2Q；

步骤8.2Q=Q+liP；

步骤9 返回输出值Q：

步骤9.1 若k为偶数，则返回Q=Q-P-R;

步骤9.2 若k为奇数，则返回Q=Q-2P-R。

3 仿真及性能分析

3.1 安全性分析

在算法2中，因为不存在系数为0的系数，使得其没有功耗差异的操作，所以其能耗图谱是相同的，这也说明其本身具备抵抗SPA的能力。同时，由于引入了随机点R，使得预计算表中分基点Pi和功耗之间的相关性被掩藏，进而也可隐藏可被利用的某些特殊点，因而所给算法2能防御DPA、ZPA与RPA。最后，所给算法2执行了两次后处理操作，这主要是实现两个方面的目的：一方面是用于掩盖原标量自身的奇偶性，有效提升了算法的安全性；另一方面是可减去引入的随机点，从而恢复真实的返回值。其中，文中采用了文献[12]所给的功耗仿真平台对算法1和算法2进行功耗仿真分析，如图1和图2所示(以实施DPA攻击为例)[11]。

下面图1中给出了对算法1实施DPA攻击所获得的功耗曲线图。由图1可以看出，对算法1实施DPA攻击后，其功耗轨迹曲线出现明显的起伏，这就使得攻击者有可能推测出相关的密钥信息。虽然算法1具有相同的能力图谱可以抵抗SPA，但如果攻击者对算法1实施DPA攻击，然后对已获得的大量功耗轨迹曲线进行统计分析，攻击者将能够推测出相关的密钥信息。所以，仿真结果表明算法1是无法抵抗DPA攻击的，因而需要对其进行改进。

图1 对算法1实施DPA攻击的功耗曲线

下面图2中给出了对所给算法2实施DPA攻击所获得的功耗曲线图。由图2可以看出，算法2的功耗轨迹曲线总体来说比较平滑，并无明显的波形起伏，因而攻击者无法根据所获得的大量功耗轨迹曲线进行统计分析，来得到与之相关的密钥信息。因此，仿真结果表明所给算法2能够有效地抵抗DPA攻击。

图2 对所给算法2实施DPA攻击的功耗曲线

3.2 效率分析

在所给算法2中，步骤1、2和3所需运算量与其它步骤的运算量相比可忽略不计。步骤4的预计算需要计算2(s-1)tP,…,2tP和Pi-R，其中前者所需运算量是(s-1)tD，后者所需运算量是(2s-1)A，因此生成预计算表Pi′需要的运算量是(2s-1)A+(s-1)tD。步骤5和6所需运算量与其它步骤的运算量也可忽略不计。步骤8中主循环运算的运算量是tA+tD。步骤9中后处理运算的运算量是2A或2A+D。所以，算法2需要的总运算量是(2s+t+1)A+(st+1)D。其中，A为点加运算，D为倍点运算，t为奇系数编码长度，s为奇系数Comb算法编码系数的二进制长度，而且t=「n/s⎤，n为奇数化标量的二进制长度。下表1给出了所给算法2和BR算法(二进制)、WBRIP算法以及FWNAF算法的运算效率比较[12]。其中，w表示窗口宽度，且有w=4。此外，w0和w1分别为FWNAF抗功耗攻击算法中窗口w的整数部分和碎片部分，且有w0=「w⎤，w1=w-(w0-1)[13]。

表1 所给算法2和BR、WBRIP以及FWNAF抗功耗攻击算法的运算效率比较

由表1可知，所给算法2需要的存储空间要比WBRIP和FWNAF的小。但是，WBRIP比所给算法2要多执行了(2s-1-2)次点加操作和(2s-1+s-2)次倍点操作，而FWNAF算法比所给算法2多执行了(w0-1)次倍点操作，执行的点加操作次数基本相似。由此可以看出，所给算法2不仅能够保持同样抗功耗攻击能力，同时还能够在降低存储空间的情况下提升运算效率。当前ECC中512bit的密钥一般被认为是安全的，即n=512。令s=4，w=4，则t=128，w0=4，w1=1。

此外，在文献[14]给出的仿射坐标系下，A=23M，D=24M，M表示模乘运算。则BR抗功耗攻击算法的总运算量为24064M，WBRIP抗功耗攻击算法的总运算量为16025M，FWNAF抗功耗攻击算法的总运算量为15766M，而算法2的总运算量为15671M。因此，所给算法2比BR算法的运算效率提升了34.88%，比WBRIP算法提升了2.21%，而与FWNAF算法的总运算量基本相似。尽管所给算法2所需的预计算量要比WBRIP算法和FWNAF算法大的多，但是预计算表能够预先存储到密码芯片中。然而，仅仅对于主循环运算来说，所给算法2比WBRIP算法与FWNAF算法的运算效率均提升了60.04%左右。由此可知，所给算法2可以同时兼顾到安全和效率两个方面，可以较好地用于各种资源受限的应用环境中[13-14]。

4 结 语

ECC是密码安全芯片中主流的密码算法，广泛应用于各类安全环境中，而其中基于奇系数Comb的标量乘算法则是ECC中的一种快速标量乘算法，但是因为近年来出现的功耗分析技术致使密码安全芯片遭遇了非常大的安全风险和挑战。因而文中结合奇系数Comb快速标量乘算法与基点掩码技术，从而给出了一种改进的ECC抗功耗攻击算法。该算法与BR、WBRIP以及FWNAF抗功耗攻击算法相比，不仅同样能够有效抵抗多种功耗攻击，同时具有更高的运算效率。由此可知，所给RPAOCM算法能较好地解决密码芯片等类似系统因资源受限而存在效率和安全两方面矛盾的问题，能够较好地用于各类自身资源受限的应用系统中。

[1] Pang S C, Tong S Y, Cong F Z, et al. A efficient elliptic curve scalar multiplication algorithm against side channel attacks [C]//Proceedings of the 2010 International Conference on Computer, Mechatronics, Control and Electronic Engineering (CMCE2010), Springer-Verlag, Berlin, 2010: 361-364.

[2] 王正义，赵俊阁.ECC抗功率分析攻击的等功耗编码算法[J].计算机工程，2012，38(10)：111-113．

[3] Akishita T, Takagi T. Zero-value point attacks on elliptic curve cryptosystems [EB/OL]. http://www.Informatik. tudarmstadt.de/ftp/pub/TI/TR/TI-03-01.zvp.ps.

[4] Gobin L. A refined power analysis attack on elliptic curve cryptosystems [C]//Public Key Cryptography 2003, LNCS 2567, Springer-Verlag, 2003.

[5] Mamiya H, Miyaji A, Morimoto H. Efficient countermeasures against RPA, DPA, and SPA [C]//Cryptographic Hardware and Embedded Systems(CHES’04), LNCS 3156, Springer-Verlag, 2004: 343-356.

[6] 张涛. Smartcard上椭圆曲线密码算法的能量攻击和防御[J]．计算机工程，2007，33(14)：125-127．

[7] Zhang Tao, Fan Mingyu, Zheng Xiaoyu. Secure and efficient elliptic curve cryptography resists side-channel attacks [J]. Journal of Systems Engineering and Electronics, 2009, 20(3): 660-665.

[8] Dimitrov V S, Jullien G A, Miller W C. Theory and applications for a double-base number system [J]. IEEE Transactions on Computers, 1999, 48(10): 1098-1106.

[9] 赖忠喜，张占军，陶东娅．椭圆曲线中直接计算7P的方法及其应用[J]．计算机应用，2013，33(7)：1870-1874.

[10] 石润华，葛丽娜，钟诚．椭圆曲线密码体制上一种快速kP算法[J]．计算机工程与科学，2004，26(4)：55-58．

[11] Feng M, Zhu B B. Efficient comb elliptic curve multiplication methods resistant to power analysis [EB/OL]. http://eprint.iacr. org/2005/222.ps.gz.

[12] 王晨旭，赵占峰，喻明艳，等．Picclol相关性功耗分析攻击技术研究[J]．哈尔滨工业大学学报，2013，45(9)：17-22．

[13] 姚剑波，张涛．基于素数域上复合运算的快速标量乘算法[J]．计算机应用研究，2012，29(12)：4639-4643．

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