Efficient Algorithm On Koblitz Curves With Resistance To Side Channel Attacks

Koblitz curves belong to a special class of binary curves on which the scalar multiplication can be computed very efficiently by the method of width w radix-r NAF expansion (TNAF_W). But the scalar multiplication using TNAF_W is vulnerable to Side Channel Attacks. Side-channel attacks are easy-to-implement whilst powerful attacks against cryptographic implementations, and their targets range from primitives, protocols,modules, and devices to even systems. These attacks pose a serious threat to the security of cryptographic modules. In consequence, cryptographic implementations have to be evaluated for their resistivity against such attacks and the incorporation of different countermeasures has to be considered. Indeed, side channel attacks become a new serious to implementation of public-key cryptosystems. Therefore, in recent years, to design efficient algorithms with better computational efficiency and lower memory space against side channel attacks has become an active research topic in the cryptographic field.In this paper, we try to investigate one new countermeasure algorithm against side channel attacks more efficient than existed. First,this paper surveys the methods and techniques employed in these attacks, the destructive effects of such attacks, the countermeasures against such attacks and evaluation of their feasibility and applicability. Further ,we propose one new efficient algorithm against Side Channel Attacks. Its basic idea is to insert dummy operations in the scalar multiplication using TNAF_W so as to resist Side Channel Attacks including Refined Power Attack (RPA) and Zero Value Attack (ZPA), with the use of Randomized Linearly-transformed coordinates (RLC). This algorithm further optimizes computational cost and pre-computation table. Compared with SPA- resistant TNAF_W(STNAF_W) algorithm, its number of pre-computation point is reduced about 50% and its computation time is reduced about 18%～28%.