基于分拆窗口NAFw标量乘的抗功耗分析方案

邬 迎 高 静

(中原工学院信息商务学院 河南 郑州 450007)

0 引 言

椭圆曲线密码(Elliptic curve cryptography,ECC)构建的高安全性主要基于椭圆曲线离散对数难题，尤其是针对一些特殊椭圆曲线所构建的椭圆曲线密码大都具有亚指数甚至多项式时间算法。在通常情况下，160 bit密钥的ECC算法与1 024 bit密钥的RSA算法具有同级别的安全性[1-2]。ECC具有密钥长度短、基于有限域运算次数远小于传统离散对数、易在计算机软硬件上实现加法运算等优点。同时ECC也有高复杂度、处理速度低的不足，所以国内外研究人员提出了一系列诸如二进制编码算法、2w编码算法、滑动窗口编码算法等多种优化算法[3]。然而，在大多数优化的ECC标量乘中仅考虑提高运算效率的问题，却未施加任何抗边信道攻击的相关措施。边信道攻击(Side channel attack,SCA)[4-5]是近年来针对椭圆曲线密码进行攻击最具威胁的手段之一，其主要工作原理是在密码算法执行过程中通过监听一些诸如算法执行时间、固定步骤能耗等相关信息，然后攻击者从这些通过监听所获取的信息中收集一些与密钥具有相关性的信息，从而获知密码算法内在的工作情况，进而可以猜测出相关密钥信息。其中，功耗分析是边信道攻击中被广泛运用的攻击方法之一。功耗分析[6]主要通过获取密码系统工作中的能耗信息来得到与密钥相关中间值信息，该方式实现简单且成功率高。功耗分析通常包括简单功耗分析(Simple power analysis, SPA)与差分功耗分析(Differential power analysis, DPA)等。

由于增加抗功耗分析措施会降会低标量乘的运算效率，使得椭圆曲线密码存在安全与效率的矛盾。因此，为同时兼顾椭圆曲线密码算法的安全和效率，提出了一种基于分拆窗口NAFw的标量乘抗功耗分析方案(FW-NAFw)。该方案首先采用基于窗口的二元非相邻形式编码方法(NAFw)对标量进行编码，从而实现椭圆曲线密码标量乘算法;通过分析NAFw的各种改进方案，给出一种改进的NAFw;用标量乘算法提高椭圆曲线密码的执行效率，最后在所给改进NAFw标量乘算法的基础上采用分拆窗口方法实施抗功耗分析。

1 NAFw标量乘算法

二元非相邻形式(Non-adjacent form, NAF)[7]是对ECC中的标量k进行重新编码的一种方式，具体指k的NAF编码中的比特位包含0、1、-1三种元素，且不会存在相邻的非零元素。即标量k的NAF编码形式为k=(km-1,…,ki,…,k1,k0)NAF，其中ki∈{-1,0,1}，且有km-1≠0，具体表示形式如下：

(1)

为了进一步提高NAF标量乘算法的效率，国内外研究人员提出了基于窗口的NAFw。由Okeya等[8]提出的NAFw编码方法具有更好的运算效率，如算法1所示。

算法1NAFw

输入：标量k，长度为n比特，窗口宽度w。

输出：k=(km-1,…,ki,…,k1,k0)NAFw。

1. 令i=0；

2. 如果k≠1，则重复执行：

3.u=(kmod2w+1)-2w；

4.kw[i]=u;kw[i+1]=0;…;kw[i+w+1]=0；

6.kw[i]=1;kw[i+1]=0;…;kw[i+w+1]=0；

7. 返回(km-1,…,ki,…,k1,k0)NAFw。

算法2从左到右基于改进NAFw编码标量乘算法

输入：标量k，长度为n比特，窗口宽度w。

输出：Q=kP。

1. 令i=0，Q=O；

2. 预计算uP；

3. 当i>w时，则重复执行：

4.u=k[i-1→i-w]‖1

//k[i→j]表示从k推出的比特串，

//从j位开始到i位结束；

5. 若k[i]=0且i

6.Q=2wQ；

7.Q=Q+uP；

8.i=i-w;

9.u=k[i-1→0]；

10. 若k[i]=0且i

11.Q=2iQ；

12.Q=Q+uP；

13. 返回Q。

2 FW-NAFw抗功耗分析方案

未施加抗功耗分析措施的椭圆曲线标量乘算法都易遭受攻击。目前，抵抗功耗分析的方案主要包括基于固定程序方法、基于随机加法链方法、基于统一公式方法等。其中，基于固定程序方法主要指在执行标量乘时，当标量的二进制位为0和1时执行相同的操作程序，从而致使标量乘的点加操作和倍点操作不可区分，目前已有典型的基于固定程序方法的抗功耗分析方案主要包括Coron冗余方案[9]、Montgomery阶梯方案[10]和Möller方案[11]。基于随机加法链方法主要指尝试利用多种加法链来抵抗SPA与DPA，目前典型的基于随机加法链方法的抗功耗分析方案主要包括随机窗口方案[12]与随机加减链方案[13]。基于统一公式方法主要指通过减少ECC标量乘中点加操作和倍点操作的差异来抵抗功耗分析，该方案尽管能掩盖非零位元素在编码序列中的位置，然而攻击者仍可以利用私钥中的汉明重量信息实施传统攻击[14]。因此，为有效抵抗功耗分析，在算法2的NAFw编码标量乘算法基础上，采用分拆窗口的方法来抵抗功耗分析，从而给出一种兼顾安全和效率的椭圆曲线密码标量乘方案。下面给出基于拆分窗口NAFw的ECC标量乘抗功耗分析算法，如算法3所示。

算法3基于拆分窗口NAFw的抗功耗分析算法

输入：标量k，长度为n比特，窗口宽度w，b∈B的概率p。

输出：Q=kP。

1. 令i=0，Q=O；

2. 预计算uP；

3. 当i≥w时，则重复执行：

4.x=k[i-1→i-w]‖1；

5.y=k[i-1→i-w+1]‖1；

//k[i→j]表示从k推出的比特

//串，从j位开始到i位结束

6. 如果k[i]=0且i

7.x=x-2w；

8.y=y-2w-1；

9. 如果|x|<2w-1，则引入随机数r，且有0≤r≤1；

10. 如果r

11. 如果r≥p，则执行u=y，r=w-1；

12. 如果|x|∈B，则执行u=x，r=w；

13. 如果|x|∉B，则执行u=y，r=w-1；

14.Q=2rQ，Q=Q+uP，i=i-r；

15. 如果k[i]=0，则执行u=u-2i；

16.Q=2rQ，Q=Q+uP；

17. 返回Q。

3 性能分析

通常密码算法的安全性与密钥长度相关，虽然较长的密钥可以大幅提高密码算法的安全性，但同时也降低标量乘法运算的实现效率。表1给出了密钥长度为160 bit时不同窗口宽度下所需的理论计算量。可以看出，增加的运用量导致采用分拆窗口的标量乘运用效率要比采用较小整体窗口的标量乘运算效率更低。当w=4,8时，标量乘法运算不需要额外的计算量，而当w=5,6时，则需要更多的运算量，但w=4时需要的存储空间更大。

表1 密钥长度为160 bit时不同窗口宽度下所需理论计算量

表2 算法3的运算量小于算法2的运算量时所取的γ最小值

当算法3抵抗简单功耗分析时，即算法3执行过程中点加操作的运算量近似于倍点操作的运算量，则在Jacobian坐标系下可计算得到γ=1.66，其中：S≈0.8M，S表示平方运算的运算量，M表示模乘运算的运算量[15]。这说明当w=5,6,9,10,11,12,13时，基于分拆窗口NAFw的抗功耗分析算法的运算效率低于基于整体窗口NAFw的标量乘算法的运算效率；当w=3,7,14,15时，所给基于分拆窗口NAFw的抗功耗分析算法的运算效率高于基于整体窗口NAFw的标量乘算法的运算效率。而在射影坐标系下，可计算得到γ=2.25。这说明当w=3,6,7时，所给基于分拆窗口NAFw的抗功耗分析算法的运算效率高于在v=3时整体窗口NAFw的标量乘算法的运算效率；同样地，当w=13,14,15时，基于分拆窗口NAFw的抗功耗分析算法的运算效率也高于在v=4时整体窗口NAFw的标量乘算法的运算效率。

当算法3抵抗简单功耗分析及差分功耗分析时，在Jacobian坐标系下，可计算得到γ=2.33，此时当w=3,6,7,13,14,15时，算法3的运算效率更高，同时结合随机坐标技术即可实现抵抗简单功耗分析及差分功耗分析。在射影坐标系下，可计算得到γ=3，此时当w=3,6,7,12,13,15时，算法3具有更高的运算效率且可抵抗简单功耗分析以及差分功耗分析。

当算法3抵抗简单功耗分析及二阶差分功耗分析时，在Jacobian坐标下，素数域上椭圆曲线密码标量乘算法的运算量为17M+7S，则可计算得到γ=3.14，此时查表可知当w=3,6,7,12,13,14,15，算法3具有更高的运算效率，且能够抵抗简单功耗分析以及二阶差分功耗分析。在射影坐标系下，二元域上椭圆曲线密码标量乘算法的运算量为15M，则可计算得到γ=3.75，此时查表可知当w=3,6,7，所给基于分拆窗口NAFw抗功耗分析算法的运算效率高于在v=3时整体窗口NAFw的标量乘算法的运算效率；同样地，当w=12,13,14,15时，所给基于分拆窗口NAFw的抗功耗分析算法的运算效率也高于在v=4时整体窗口NAFw的标量乘算法的运算效率，且均可抵抗简单功耗分析和二阶差分功耗分析。

4 结 语

椭圆曲线密码算法是应用最为广泛的密码算法之一，但是功耗分析技术严重威胁椭圆曲线密码算法的安全，施加抗功耗分析措施的同时将会降低椭圆曲线密码算法的运算效率。为同时保证椭圆曲线密码算法的安全和效率，给出了一种基于拆分窗口的NAFw的抗功耗分析方案。本文方案一方面通过改进NAFw算法来提高椭圆曲线密码标量乘算法效率，另一方面采用拆分窗口的方法实现抗功耗分析，且该方案可根据实际情况选取窗口宽度。算法性能分析表明，本文算法可以同时兼顾安全和效率，具有灵活高效、安全性较高、占用空间小等优点，非常适用于智能芯片等存储资源受限的密码设备中，因此具有较好理论研究价值和实际推广应用价值。