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