针对椭圆曲线点乘算法的代数故障攻击  

Algebraic fault attack on elliptic curve scalar multiplication algorithms

作　　者：许盛伟[1] 陈诚[1,2] 王荣荣[1,2] 

机构地区：[1]北京电子科技学院,北京100070 [2]西安电子科技大学通信工程学院,陕西西安710071

出　　处：《计算机工程与科学》2017年第11期2037-2042,共6页Computer Engineering & Science

摘　　要：首先通过分析固定梳(comb)点乘算法和窗口非相邻型(NAF)点乘算法,提出了一种代数故障攻击算法,可以恢复椭圆曲线密码算法的全部私钥。代数故障攻击算法在执行过程中不会被检测出来,遇到全零块也不会使攻击失效。然后通过软件仿真分别实现了对两种点乘算法的攻击,攻击的参考椭圆曲线为商用密码SM2算法提供的素数域曲线。攻击comb点乘算法需要13min,攻击窗口NAF点乘算法需要18min,并且都恢复了256比特长的私钥。而差分故障攻击方法不能攻击comb点乘算法,也容易遭受"故障检测"和"零块失效"的威胁,使得攻击失败。实验结果表明,代数故障攻击可以对有预计算的点乘算法实现高效攻击,健壮性强。Firstly, by analyzing the comb scalar multiplication and window non-adjacent form （NAF） scalar multiplication algorithms, we put forward an algebraic fault attack algorithm, which can recover all the private keys of elliptic curve cryptographic algorithms. The algebra fault attack algorithm cannot be detected in the execution process or fails when it meets all zero blocks. Then using the prime field curve of the commercial cryptography SM2 algorithm as the elliptic curve reference, the two scalar mul- tiplication algorithms are attacked respectively in software simulation. It takes 13 minutes to attack the comb scalar multiplication algorithm and 18 minutes to the window NAF scalar multiplication algorithm, with 256-bits long private key recovered. In comparison, differential fault attack methods cannot attack the comb scalar multiplication algorithm, and they are vulnerable to ＂fault detection＂ and ＂zero block failure＂ simultaneously, so they fail. Experimental results show that the algebraic fault attack can be ef- ficient to the scalar multiplications with precomputation, and the attacks are robust.

关 键 词：椭圆曲线密码 comb点乘算法 窗口NAF点乘算法 代数故障攻击 零块失效 故障检测 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]