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

首先通过分析固定梳(comb)点乘算法和窗口非相邻型(NAF)点乘算法,提出了一种代数故障攻击算法,可以恢复椭圆曲线密码算法的全部私钥。代数故障攻击算法在执行过程中不会被检测出来,遇到全零块也不会使攻击失效。然后通过软件仿真分别实现了对两种点乘算法的攻击,攻击的参考椭圆曲线为商用密码SM2算法提供的素数域曲线。攻击comb点乘算法需要13min,攻击窗口NAF点乘算法需要18min,并且都恢复了256比特长的私钥。而差分故障攻击方法不能攻击comb点乘算法,也容易遭受"故障检测"和"零块失效"的威胁,使得攻击失败。实验结果表明,代数故障攻击可以对有预计算的点乘算法实现高效攻击,健壮性强。

Algebraic fault attack on elliptic curve scalar multiplication algorithms

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 multiplication 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 efficient to the scalar multiplications with precomputation, and the attacks are robust.