• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Computer Engineering & Science

Previous Articles     Next Articles

Algebraic fault attack on elliptic curve
scalar multiplication algorithms
 

XU Sheng-wei1,CHEN Cheng1,2,WANG Rong-rong1,2   

  1. (1.Beijing Electronic Science & Technology Institute,Beijing 100070;
    2.College of Communication Engineering,Xidian University,Xi’an 710071,China)
     
  • Received:2016-05-23 Revised:2016-09-09 Online:2017-11-25 Published:2017-11-25

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