抵抗SPA攻击的分段Montgomery标量乘算法  

A segmented Montgomery scalar multiplication algorithm with resistance to simple power analysis SPA attacks

作　　者：李杨[1,2] 王劲林[1] 曾学文[1] 叶晓舟[1] LI Yang WANG Jin-lin ZENG Xue-wen YE Xiao-zhou(National Network New Media Engineering Research Center, Institute of Acoustics, Chinese Academy of Sciences, Beijing 100190 University of Chinese Academy of Sciences, Beijing 100049 ,China)

机构地区：[1]中国科学院声学研究所国家网络新媒体工程技术研究中心,北京100190 [2]中国科学院大学,北京100049

出　　处：《计算机工程与科学》2017年第1期92-102,共11页Computer Engineering & Science

基　　金：中国科学院战略性先导科技专项课题(XDA06010302);中国科学院声学研究所知识创新工程项目(Y154191601)

摘　　要：基于Akishita在Montgomery形式椭圆曲线上计算双标量乘kP+lQ的思想,提出了一种计算三标量乘kP+lQ+tR的新算法,使运算量减少了约23%。在上述算法基础上提出一种椭圆曲线上分段计算标量乘bP的方法,通过预计算少量点,将计算bP转化为计算kP+lQ或kP+lQ+tR,并使用边信道原子化的方法使其可以抵抗简单能量分析(SPA)攻击。最后使用Magma在二进制域上对分段算法仿真,结果显示二分段算法计算速度最快,三分段算法其次,在效率上均比原始Montgomery算法提升很大。Based on the Akishita＇s idea of computing scalar multiplication kP ＋lQ on elliptic curve with Montgomery form, we propose a new algorithm to reduce the computation for scalar multiplication kP＋lQ＋tR by 23%. We then propose a subsection method on the basis of the above two algorithms to enhance the efficiency of computing scalar multiplication bP on elliptic curve by converting bP to kP＋lQ or kP＋lQ ＋tR, which combines the concept of side-channel atomicity to resist SPA attacks. Simulations on Magma demonstrate that the two-segmentation algorithm is the fastest and the three-segmentation algorithm is the second, and they can both greatly improve the efficiency in comparison with the original Montgomery algorithm.

关 键 词：椭圆曲线 标量乘 MONTGOMERY算法 分段 SPA 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]