抗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是椭圆曲线密码算法的核心，并且标量乘的运算效率直接关系到整个椭圆曲线密码算法的实现效率。……