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

Abstract:

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.

Key words: elliptic curve cryptography, comb scalar multiplication, window NAF scalar multiplication, algebraic fault attack, zero block failure, fault detection