基于边带信道原子的安全快速椭圆曲线密码点乘算法

Fast and secure elliptic curve scalar multiplication algorithm based on side channel atomicity

简单功耗分析对椭圆曲线点乘算法的安全性具有很大的威胁,在某种程度上可以恢复出密钥。提出一种抵抗简单功耗攻击的快速边带信道原子点乘算法。算法的倍点和点加运算采用形如S-A-N-A-M-N-A(平方-加法-逆运算-加法-乘法-逆运算-加法)的边带信道原子结构,其运算量为:在Jacobian坐标系下倍点运算量为5M+5S+15A,混加运算量为6M+6S+18A;在改进的Jacobian坐标系下,倍点运算量为4M+4S+12A,混加运算量为7M+7S+21A。在效率方面,新的点乘算法比以往的边带信道原子点乘算法的运算速度有较大提高。例如对于采用NAF编码的192bit的点乘算法,当S/M=0.8时,效率提高约7.8%～10%,当S/M=0.6时,提高约18%～20%。

Simple power analysis is the most devastating attack on the security of elliptic curve scalar multiplication and can retrieve the secret key in some degree. A fast and secure side channel atomic elliptic curve scalar multiplication algorithm was put forward using the side channel atomic block S-A-N-A-M-N-A. In Jacobian coordination, the new algorithm used only 5M ＋ 5S ＋ 15A for doubling and 6M ＋ 6S ＋ 18A for mixed addition. In modified Jacobian coordination, the new algorithm used only 4M ＋4S ＋ 12A for doubling and 7M ＋7S ＋21A for mixed addition. Compared with the previous methods, the new method can improve the speed by about 7.8% - 10% if S/M = 0.8 or 18% - 20% if S/M = 0.6 for 192 bit scalar using NAF recoding.