基于特殊加法链的快速安全椭圆曲线标量乘算法

为了抵抗椭圆曲线密码的边信道攻击,提出了一种新型快速安全的标量乘算法.该算法是一种基于仅有点加运算的特殊加法链,可自然地抵抗边信道攻击.此外,提出在一种新型点加运算公式中引进特殊结构的加法链,可以大大提高标量乘算法的运算效率.对于长度为160比特的整数,其特殊加法链长度为260时,仅仅需要1 719次乘法运算.特殊加法链长度为280～260时,运行标量乘算法比倍点-点加算法效率上提高26%～31%,比NAF算法快16%～22%,比4-NAF算法快7%～13%,比目前最好的方法双基链算法还要快1%～8%.

Fast and secure elliptic curve scalar multiplication algorithm based on special addition chains

To resist the side channel attacks of elliptic curve cryptography,a new fast and secure point multiplication algorithm is proposed.The algorithm is based on a particular kind of addition chains involving only additions,providing a natural protection against side channel attacks.Moreover,the new addition formulae that take into account the specific structure of those chains making point multiplication very efficient are proposed.The point multiplication algorithm only needs 1 719 multiplications for the SAC260 of 160-bit integers.For chains of length from 280 to 260,the proposed method outperforms all the previous methods with a gain of 26% to 31% over double-and add,16% to 22% over NAF,7% to 13% over 4-NAF and 1% to 8% over the present best algorithm-double-base chain.