基于奇系数梳状算法的ECC抗功耗攻击算法

殷 守 军

(北京联合大学 工科综合实验教学示范中心，北京 100101)

0 引 言

功耗攻击给密码芯片的安全带来了极大的威胁，但由于密码芯片自身资源限制，造成其在采取防御功耗攻击措施后，将降低密码芯片运算效率，致使产生效率与安全的矛盾，如何解决这一矛盾则成为密码芯片抗功耗攻击研究的热点问题[1-2]。功耗攻击是Paul Kocher在1998年首先提出的密码分析方法，主要工作原理是密码芯片运行时，不同操作产生的功耗不同，通过采集这些泄露的功耗信息，并分析功耗之间的差异即可获取相关密钥信息。而且功耗分析具有易于实现、成功率高等诸多良好攻击特性，因而相较于传统数学攻击方法而言，功耗分析对密码芯片所带来的安全威胁更严重[3-4]。一般来说，功耗攻击因攻击手段不同主要分为：简单功耗攻击技术(Simple Power Attack, SPA)和差分功耗攻击技术(Differential Power Attack, DPA)。其中，由于密码芯片中的主流算法大都是采用椭圆曲线密码(Elliptic Curve Cryptogram, ECC)算法，使得出现了一些列针对ECC的功耗攻击，包括零值寄存器攻击(Zero-value Power Attack, ZPA)与零值点攻击(Refined Power Attack, RPA)[5]。

国内外学者关于密码芯片的抗功耗攻击方面做了大量研究工作[6-7]。Mamiya等[8]给出了一种基于窗口随机化初始点的ECC抗功耗攻击方案(Window-Based Random Initial Point, WBRIP)，基本思想是通过将标量的二进制编码进行窗口化，在一个窗口内实现掩盖所执行的点加运算与倍点运算次数的目的，致使攻击者无法从中间值猜测运算过程中所执行的具体操作及相关步骤，尽管WBRIP可以抵抗多种功耗攻击，但是其运算效率需进一步提高。张涛等[9]给出了一种固定窗口宽度为w的非邻接表示形式的ECC抗功耗攻击算法(Fractional Width-wNon Adjacent From, FWNAF)，主要思想是利用二进制的非邻接表示形式来优化编码，减少在抵抗功耗攻击过程中所需添加伪操作的次数，从而实现运算效率的提升。文献[10]中给出一种高效的窗口随机化初始点ECC抗功耗攻击算法(Efficient-Based Random Initial Point, EBRIP)，主要思想是将标量的二进制编码表示成窗口宽度是w的非邻接表示形式，并将其分成整数部分与分数部分实现抵抗SPA。接着再将基点分成固定部分与可变部分可实现抵抗DPA、ZPA与RPA，并且也可提升运算效率。奇系数Comb算法是ECC标量乘法运算的一种快速计算方法，为保证算法能够抵抗功耗攻击并进一步有效提升运算效率，本文通过在奇系数Comb标量乘算法中结合添加伪操作与基点掩码技术，给出了一种密码芯片上基于奇系数Comb算法的ECC抗功耗攻击算法，同BR、WBRIP及FWNAF算法相比，所给抗功耗攻击算法不仅有相同的抗功耗攻击安全性，而且具有更高的运算效率。

1 奇系数Comb标量乘算法

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

ECC标量乘的运算为

其中:k为标量，采用二进制编码表示;n是二进制编码的长度,则有标量k的表示形式如下：

，ki∈{0,1}

(1)

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

…+lt-12t-1

(2)

式中:li表示标量k的奇系数Comb算法编码系数，且有li≠0;t表示li的编码长度，且有t=

n/s

，s表示li的二进制编码长度,n表示k的二进制编码长度。下面对li进行二进制编码可得：

(3)

(4)

则ECC标量乘法的运算形式可转换为如下形式：

(5)

式中，Pi为预计算点，且有各预计算点

Pi=(u(s-1)2(s-1)t+…+ui2it+…+u12t+1)·P

ui∈{0,1}

然后根据已预计算出的各预计算点生成预计算表。

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

算法1ECC的奇系数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，重复执行：①Q=2Q；②Q=Q+liP；

(8) 返回输出值Q：①k为偶数，返回Q=Q-P;②k为奇数，返回Q=Q-2P。

2 新算法设计

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

文中采用了基点掩码技术，即通过在标量乘运算中引入随机点将基点随机化，同时再结合预计算的方法可实现多标量乘法运算中各分基点的随机化，以此即可掩盖每个小标量乘法运算同功耗之间的相关性，这样就致使攻击者无法利用统计分析的方法，通过多次猜测来获取有效的密钥信息。所以，基于奇系数Comb编码标量乘运算Q=kP在引入随机点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的二进制长度；

(3)R=random()；

(5) 计算奇系数Comb编码长度t=

m/s

；

(6) 计算奇系数Comb编码系数li；

(7) 令Q=R；

(8) 对于i从t-1到0，重复执行：①Q=2Q；②Q=Q+liP；

(9) 返回输出值Q：①k为偶数，返回Q=Q-P-R;②k为奇数，返回Q=Q-2P-R。

3 性能分析

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

n/s

，n为奇数化标量的二进制长度。表1给出了算法2和BR算法(二进制)、WBRIP算法以及FWNAF算法的运算效率比较。其中，w表示窗口宽度，且有w=4。此外，w0和w1分别为FWNAF抗功耗攻击算法中窗口w的整数部分和碎片部分，且有，w1=w-(w0-1)[14]。

表1 算法2和BR、WBRIP以及FWNAF的运算效率比较

w0=

w

由表1可知，算法2需要的存储空间要比WBRIP和FWNAF小。但是，WBRIP比算法2要多执行了(2s-1-2)次点加操作和(2s-1+s-2)次倍点操作，而FWNAF算法比算法2多执行了(w0-1)次倍点操作，执行的点加操作次数基本相似。由此可以看出，算法2不仅能够保持同样抗功耗攻击能力，同时还能够在降低存储空间的情况下提升运算效率。当前ECC中512 bit的密钥一般被认为是安全的，即n=512。令s=4，w=4，则t=128，w0=4，w1=1。在仿射坐标系下[15]，A=23M，D=24M，M表示模乘运算,则有BR、WBRIP、FWNAF的总运算量分别为24 064M、16 025M、15 766M，而算法2的总运算量为15 671M。因此，算法2比BR的运算效率提升了34.88%，比WBRIP提升了2.21%，与FWNAF的总运算量基本相似。尽管算法2所需的预计算量要比WBRIP算法和FWNAF算法大得多，但是预计算表能够预先存储到密码芯片中。然而，仅仅对于主循环运算来说，算法2比WBRIP算法与FWNAF算法的运算效率均提升了60.04%左右。由此可知，算法2可以同时兼顾到安全和效率两个方面，可以较好地用于各种资源受限的应用环境中。

4 结 语

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

参考文献(References)：

[1] 郭 彬, 孙忠廷, 王 勇, 等. 抗能量分析攻击的阶乘展开式标量乘算法[J]. 科技通报, 2016, 32(6): 149-155.

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

[3] Pang S C, Tong S Y, Cong F Z,etal. 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), Berlin: Springer-Verlag, 2010: 361-364.

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

[5] 梁 芳, 沈济南. 基于奇系数Comb的椭圆曲线密码抗功耗攻击方案[J]. 计算机应用与软件统, 2016, 33(3): 288-290.

[6] 闫 娜. 基于带符号整数拆分形式的抗功耗攻击方案[J]. 中国电子科学研究院学报, 2017, 12(4): 438-442.

[7] 赵树林, 王正义, 陈 璐, 等. 基于带符号阶乘展开式的抗功耗方案算法[J]. 计算机与数字工程, 2014, 42(6): 924-926.

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

[9] 张 涛, 范明钰, 王光卫, 等. Smartcard上椭圆曲线密码算法的能量攻击和防御[J]. 计算机工程, 2007, 33(14): 125-127.

[10] 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.

[11] 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.

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

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

[14] 尹 恒, 蒋朝惠, 付 威. 抗边信道攻击的高效多基标量乘算法[J]. 计算机应用, 2014, 34(11): 3287-3290.

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