抗SPA攻击的椭圆曲线NAF标量乘实现算法

王敏，吴震

(成都信息工程学院 网络工程学院，四川 成都 610000)

1 引言

1985年，Miller和Kibitz首次将椭圆曲线应用于密码系统后，椭圆曲线密码系统(elliptic curve cryptography, ECC)[1]已受到越来越多的关注。ECC具有安全性高、计算量小、处理速度快、存储空间占用小、带宽要求低的特点。与RSA公钥体制相比，ECC非常适合于资源有限的嵌入式移动环境，如Smartcard上的密码芯片。

由于NAF标量乘法[2,3]运算效率高，所以当前椭圆曲线标量乘的实现大多采用此算法，但NAF标量乘法最易受到边信道攻击(SCA, side channel attack)。SCA是在1996年由P. Kocher提出的一种利用加密过程中的计算时间或能量消耗来分析秘密消息的攻击方法，基本上分为2类，简单能量分析(SPA, simple power analysis)和差分能量分析(DPA, differential power analysis)。所谓简单能量分析是指分析一个设备上一次密码操作所消耗的能量。因为对不同的操作有不同能量消耗，这样对应不同的能量消耗，攻击者可以判断以什么样的顺序进行了什么样的操作。当将多种监听数据与概率的分析工具结合在一起时，攻击的成功率更高，即为差分能量分析。

为了既能发挥NAF标量乘法运算效率高的优点，又能很好地抵抗SPA攻击，本文提出一种新的标量乘实现算法——平衡能量NAF标量乘法。平衡能量NAF标量乘法不仅很好地继承了NAF标量乘法运算效率高的优点，并且通过对功耗信息的实际分析验证，平衡能量NAF标量乘法还能够有效地抵抗SPA攻击。

2 椭圆曲线NAF标量乘法

标量乘kP是椭圆曲线密码算法的核心，并且标量乘的运算效率直接关系到整个椭圆曲线密码算法的实现效率。标量乘的实现算法很多，主要有二进制标量乘法、NAF标量乘法等。其中，NAF标量乘法对密钥k进行了NAF编码，使得密钥k的汉明重量减少，使得运算效率相对于二进制标量乘法有了很大的提高，因此在椭圆曲线标量乘中得到了广泛的应用。

2.1 二元非相邻形式

二元非相邻形式(NAF, non-adjacent form)是对标量乘kP中密钥k进行转换，表示为类似于二进制数序列的形式，但是序列中每个位置除了1和0以外，也会有-1，并且在k的表示序列中不会有相邻的非零元素出现，即且，亦即

计算一个正整数k的二元NAF算法如算法1所示。

算法1 二元NAF算法

输入：k

输出：NAF(k)

二元NAF具有以下性质。

1) NAF(k)在k的所有带符号表示序列中非零位个数最少。

2) NAF(k)的长度最多比k的二进制表示形式的长度大1。

3) k具有唯一的NAF。

4) 所有长度为m的NAF中非零元素的平均个数约为m/3。

2.2 二元NAF范例

设k=0x12345，根据算法1所示二元NAF算法可算出k的二元NAF编码如表1所示。

表1 k=0x12345对应二元NAF编码

由表1可知k=0x12345进行NAF编码后k=(1,0,1,0,0,0,1,0,-1,0,1,0,0,1,0,0,1)NAF。

2.3 NAF标量乘法

NAF标量乘法是首先按照算法1将密钥k进行NAF编码，然后再进行标量乘运算，标量乘算法如算法2所示。

算法2 NAF标量乘算法

输入：k，P

输出：kP

2.4 NAF标量乘法效率分析

设密钥k的二进制表示序列长度为l1，二元NAF表示序列长度为l2，一次倍点的运算时间为t1，由于点加和点减运算时间相差无几，所以设一次点加或点减的运算时间均为t2。

一般情况下，k的二进制序列中1的个数约为l1/2，则一次二进制标量乘算法的运算时间T1约为l1次倍点运算与l1/2次点加运算所消耗时间的总和。

又由二元NAF的性质可知l2≤l1+1，将l2≤l1+1与式(1)代入式(2)后得

由式(4)可知NAF标量法相对于二进制标量乘法在效率上有很大提高。

3 针对NAF标量乘法的SPA攻击

针对NAF标量乘法的SPA攻击，是通过采集密码芯片在进行NAF标量乘运算过程的功耗波形，利用密钥与运算间的相关性从功耗波形中对密钥进行分析提取。由算法2可知整个NAF标量乘运算主要包括2QQ←、QQP←+和QQP←-这3种运算，且当ik取值不同所进行的运算类型也不同，如表2所示。

表2 ki取值与运算类型对应关系

由于密钥k较长，为便于分析说明，对密钥进行简化，只取密钥k的低8bit为0xF1，其余比特均为0，即k=0xF1，对密钥k进行NAF编码后为k′= (1000 -10001)NAF，从功耗分析平台采集一次密码芯片标量乘运算的功耗波形如图1所示。

图1 一次NAF标量乘法功耗波形

由图1可知，一次NAF标量乘运算主要包括预处理和乘法运算2部分，预处理中进行一些乘法运算前的操作，乘法运算部分为与密钥k′有关的部分，由于k′长度为9，最高比特81k′=且只做赋值操作，因此与k′有关的功耗波形部分为乘法运算部分的前8bit，将其放大后如图2所示。

图2 与k’相关运算功耗波形

图3 k’=0时相关运算功耗波形

当ki′=1时，进行Q←2Q与Q←Q+P运算，即一次倍点运算和一次点加运算，如图4所示。

当ki′=-1时，进行Q←2Q与Q←Q+P运算，即一次倍点运算和一次点减运算，如图5所示。

图4 k’=1时相关运算功耗波形

图5 k’=-1时相关运算功耗波形

由以上分析可知，当密钥ki′=0时只进行一次倍点运算，当ki′非0时除了一次倍点运算还需要进行一次点加或点减运算，在功耗波形中，0与非0很容易分辨出，1和-1的区别在于当ki′=1时进行了一次点加运算，当ki′=-1时进行一次点减运算，点加与点减的功耗波形从图4与图5中可看出明显的区别，基于以上分析对图2所示功耗波形进行SPA攻击，结果如图6所示。

图6 对图2所示波形进行SPA攻击

根据图6所示分析结果k′=(1000-1000)NAF，又k′最高一位k8′=1，所以k′的SPA攻击结果为k′=(1000-10001)NAF，然后根据NAF编码原理，对k进行分析，得出k=0xF1，与真实密钥相同，因此SPA攻击结果正确。

4 平衡能量NAF标量乘法

NAF标量乘法相对于二进制标量乘法虽然在运算效率上有很大提高，但是从对NAF标量乘法的SPA攻击中可知NAF标量乘法不能很好地抵抗SPA攻击，对于信息的安全构成很大的威胁。

4.1 平衡能量NAF标量乘法的提出

为了使得NAF标量乘法在运算效率上表现出很好特性的同时，又能抵抗SPA攻击，增强私钥运算的安全性，在此需对NAF标量乘的实现算法以及对NAF标量乘的SPA攻击原理进行分析。对于NAF标量乘的SPA攻击点主要在于ik′在不同值的时候进行不同操作，且这些不同的操作在功耗曲线中表现出不同的特性，于是根据密钥ik′与功耗波形间的相关性对ik′进行分析。为了掩盖这种相关性，本文提出一种新的既不损失NAF标量乘法运算效率，又能很好地抵抗SPA攻击的NAF标量乘实现算法——平衡能量NAF标量乘法。

4.2 平衡能量NAF标量乘法实现原理

为了消除ki′与功耗曲线间的相关性，由以上对NAF标量乘的SPA攻击分析可知在功耗中表现的区别在于点加运算（Q←Q+P）与点减运算（Q←Q-P）在功耗波形中表现出不同的特性。根据有限域运算法则可知Q-P=Q+(-P)，于是对NAF标量乘实现算法进行修改，在每次标量乘运算之前做一次求-P的预处理，将时进行的运算Q←Q-P改为Q←Q+(-P)，使得无论当ki′=1或者ki′=-1时都进行点加运算，进而使得时的功耗波形相同，隐藏密钥ki′在非零时与运算的相关性，以至于攻击者无法从功耗波形中分辨出1和-1，提高标量乘法抵抗SPA攻击的能力。

平衡能量NAF标量乘算法如算法3所示。

算法3 平衡能量NAF标量乘算法

输入：k，P

输出：kP

4.3 平衡能量NAF标量乘法抗SPA攻击分析

为了验证平衡能量NAF标量乘法抵抗SPA攻击的作用，同样取密钥k=0xF1，对k进行NAF编码后，采集在密码芯片中运行一次平衡能量NAF标量乘运算的功耗波形，并对与k′相关的功耗波形部分进行截取放大后，如图7所示。

图7 与k′相关的平衡能量NAF标量乘运算功耗波形

根据SPA攻击原理对图7所示功耗波形进行SPA攻击，攻击结果如图8所示。

由图8所示可知，密钥k′的攻击结果为k′=(100010001)NAF，对k′进行NAF译码后k=0x 111，攻击结果与真实密钥k=0xF1不同，SPA攻击失败，由此可知平衡能量NAF标量乘法能够很好地抵抗SPA攻击。

图8 对图7进行SPA分析攻击

4.4 效率损失分析

平衡能量NAF标量乘法相对于NAF标量乘法只是将点减运算（Q←Q-P）替换为点加运算（Q←Q+(-P)），且在标量乘运算前多进行一次求-P的操作，由于点加与点减的运算量相差无几，且一次求-P的运算量也很小，可以忽略不计，因此平衡能量NAF标量乘法相对于NAF标量乘法没有效率的损失，保留了NAF标量乘法运算效率高的特点。

根据以上分析，平衡能量NAF标量乘法不仅继承了NAF标量乘法运算效率高的特点，而且能够很好地抵抗SPA攻击。

5 结束语

密码算法虽然需要考虑运算效率的问题，尽可能地减少加解密时间，但是更重要的是要确保密码算法的安全性。NAF标量乘法相对于二进制标量乘法虽然有了运算效率的提高，但是通过对NAF标量乘法的SPA攻击分析可知，利用SPA攻击方法很容易就可获取密钥k，对信息的安全构成很大的威胁。平衡能量NAF标量乘法很好地解决了NAF标量乘法安全性弱的问题。平衡能量NAF标量乘法不仅继承了NAF标量乘法运算效率高的优点，并且通过实测波形验证，平衡能量NAF标量乘法能够很好地抵抗SPA攻击。

[1] KOBLITZ N. Elliptic curve cryptosystems[J]. Mathematics of Computation, 1987, 48(177): 203-209.

[2] ZHAO Q J, LI X P, DAI Z B, etal. Research for parallel computation on NAF scalar multiplication[J]. Application of Electronic Technique,2010.160-164.

[3] LIU D, DAI Y Q. A new algorithm of elliptic curve multi-scalar multiplication[J]. Chinese Journal of Computers, 2008.1131-1137.

[4] WANG M, WU Z. Simple power analysis attack on random pseudo operations[J]]. Journal on Communications, 2012,33(5):138-142.

[5] WU Z, CHEN Y, CHEN J, etal. Exponential information’s extraction from power traces of modulo exponentiation implemented on FPGA[J].Journal on Communications, 2010,31(2):17-21.