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

计算机工程与科学

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

李杨1,2，王劲林1，曾学文1，叶晓舟1

（1.中国科学院声学研究所国家网络新媒体工程技术研究中心,北京 100190;

2.中国科学院大学,北京 100049）

收稿日期:2015-10-10 修回日期:2015-12-23 出版日期:2017-01-25 发布日期:2017-01-25
基金资助:
中国科学院战略性先导科技专项课题（XDA06010302）；中国科学院声学研究所知识创新工程项目（Y154191601）

A segmented Montgomery scalar multiplication algorithm

with resistance to simple power analysis SPA attacks

LI Yang 1,2,WANG Jinlin1,ZENG Xuewen1,YE Xiaozhou1

（1.National Network New Media Engineering Research Center,Institute of Acoustics,Chinese Academy of Sciences,Beijing 100190;

2.University of Chinese Academy of Sciences,Beijing 100049,China）

Received:2015-10-10 Revised:2015-12-23 Online:2017-01-25 Published:2017-01-25

摘要/Abstract

摘要：

基于Akishita 在Montgomery形式椭圆曲线上计算双标量乘kP+lQ的思想，提出了一种计算三标量乘kP+lQ+tR的新算法，使运算量减少了约23%。在上述算法基础上提出一种椭圆曲线上分段计算标量乘bP的方法，通过预计算少量点,将计算bP转化为计算kP+lQ或kP+lQ+tR，并使用边信道原子化的方法使其可以抵抗简单能量分析（SPA）攻击。最后使用Magma在二进制域上对分段算法仿真，结果显示二分段算法计算速度最快，三分段算法其次，在效率上均比原始Montgomery算法提升很大。

关键词: 椭圆曲线, 标量乘, Montgomery算法, 分段, SPA

Abstract:

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.

Key words: elliptic curve, scalar multiplication, Montgomery algorithm, segmentation, SPA

李杨1,2，王劲林1，曾学文1，叶晓舟1. 抵抗SPA攻击的分段Montgomery标量乘算法[J]. 计算机工程与科学.

LI Yang 1,2,WANG Jinlin1,ZENG Xuewen1,YE Xiaozhou1.

A segmented Montgomery scalar multiplication algorithm

with resistance to simple power analysis SPA attacks

[J]. Computer Engineering & Science.

参考文献［16］

［1］	Koblitz N.Elliptic curve cryptosystems［J］.Mathematics of Computation,1987,48(48):203209.
［2］	Miller V S.Use of elliptic curves in cryptography［J］.Lecture Notes in Computer Science,1986,218(1):417426.
［3］	Hankerson D. Guide to elliptic curve cryptography ［M］.Zhang Huanguo, translation. Beijing: Publishing House of Electronics Industry,2005.(in Chinese)
［4］	Montgomery P.Speeding the pollard and elliptic curve methods of factorization［J］.Mathematics of Computation,1987,48(48):243264.
［5］	López J,Dahab R.Fast multiplication on elliptic curves over GF(2m) without precomputation［C］∥Proc of International Workshop Cryptographic Hardware and Embedded Systems,1999:316327.
［6］	Akishita T.Fast simultaneous scalar multiplication on elliptic curve with Montgomery form［C］∥Proc of International Workshop on Selected Areas in Cryptograph,2001:97103.
［7］	Chen Jun. A fair exchange protocol based on elliptic curve［J］.Journal of Shandong University of Science and Technology (Natural Science),2014,33(6):103106.(in Chinese)
［8］	Zhang Jianzhong, Ma Weifang. Blind proxy blind signature scheme on elliptic curve［J］.Computer Engineering,2010,36(11):126127.(in Chinese)
［9］	Zhou Keyuan. Digital signature scheme based on elliptic curve and factoring［J］.Computer Science,2014,41(S1):366368.(in Chinese)
［10］	Okeya K, Sakurai K. Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the ycoordinate on a Montgomeryform elliptic curve［C］∥Proc of the 3rd International Worshop on Cryptographic Hardware and Embeded Systems(CHES 2001),2001,2162:126141.
［11］	Okeya K,Sakurai K.Elliptic curves with the Montgomeryform and their cryptographic applications［C］∥
	Proc of the 3rd International Worshop on Practice and Theory in Public Key Cryptographic(PKC 2000),2000:238257.
［12］	Doche C,Sutantyo D.Faster repeated doublings on binary elliptic curves［C］
	∥
	Proc of International Worshop on Selected Areas in Cryptographic(SAC 2013),2013:456470.
［13］	ChevalierMames B,Ciet M,Joye M.Lowcost solutions for preventing simple sidechannel analysis:Sidechannel atomicity［J］.IEEE Transactions on Computers,2004,53(6):760768.
［14］	Cho S M,Seo S C,Kim T H,et al.Extended elliptic curve Montgomery ladder algorithm over binary fields with resistance to simple power analysis［J］.Information Sciences,2013,245(10):304312.
［15］	Bernstein D,Lange T.Analysis and optimization of ellipticcurve singlescalar multiplication［J］.Contemporary Mathematics,2008,461(461):120.
［16］	Chinese Commercial Cryptography Administration Office. Public key cryptographic algorithm SM2 based on elliptic curves［EB/OL］.［20120321］. http://www.oscca.gov.cn/News/201204/News_1229.htm.(in Chinese)
［17］	Li M,Miri A,Zhu D.Fast algorithm for converting ordinary elliptic curves into binary Edward form［J］.International Journal of Digital Content Technology & Its Applic,2012,6(1):405412.
	附中文参考文献：
［3］	Hankerson D.椭圆曲线密码学导论［M］.张焕国，译.北京：电子工业出版社，2005.
［7］	陈俊.基于椭圆曲线的公平交换协议［J］.山东科技大学学报(自然科学版),2014,33(6):103106.
［8］	张建中,马伟芳.椭圆曲线上的盲代理盲签名方案［J］.计算机工程,2010,36(11):126127.
［9］	周克元.基于椭圆曲线和因子分解双难题的数字签名方案［J］.计算机科学,2014,41(S1):366368.
［16］	国家密码管理局.SM2椭圆曲线公钥密码算法［EB/OL］.［20101217］.http://www.oscca.gov.cn/News/201012/News_1197.htm.

[1]	陈侨安1，李峰1，曹越1，龙明盛1,2. 基于运行数据分析的Spark任务参数优化[J]. J4, 20160101, 38(01): 11-19.
[2]	赵振宇, 杨天豪, 蒋汶乘, 张书政. 基于机器学习的多压多温多参标准单元延迟快速计算方法[J]. 计算机工程与科学, 2023, 45(08): 1331-1338.
[3]	熊国杰, 张津铭, 贺光辉. 一种面向Chiplet互连的高效传输协议设计与实现[J]. 计算机工程与科学, 2023, 45(08): 1339-1346.
[4]	孙彩霞, 隋兵才, 邓全, 郑重, 倪晓强, 王永文. 应用级兼容RISC-V的混合指令集处理器[J]. 计算机工程与科学, 2023, 45(08): 1347-1353.
[5]	马思远, 焦佳辉, 任晟岐, 宋伟. 基于注意力机制的城市多元空气质量数据缺失值填充[J]. 计算机工程与科学, 2023, 45(08): 1354-1364.
[6]	史明川, 龙巧洲, 邹鸿基, 李暾. 基于Surrogate模型的断言覆盖技术研究[J]. 计算机工程与科学, 2023, 45(08): 1365-1375.
[7]	高文才, 陈小文. 一种基于混合加固的容软错误NoC路由器[J]. 计算机工程与科学, 2023, 45(08): 1376-1382.
[8]	王星苏, 熊文, 张瑞. 海量地铁乘客轨迹相似性连接方法：以深圳地铁为例[J]. 计算机工程与科学, 2023, 45(08): 1383-1392.
[9]	夏戈明, 虞朝栋, 陈健. 边缘计算中的信任问题：挑战与评论[J]. 计算机工程与科学, 2023, 45(08): 1393-1404.
[10]	尹春勇, 冯梦雪. 基于注意力机制的半监督日志异常检测方法[J]. 计算机工程与科学, 2023, 45(08): 1405-1415.
[11]	余子丞, 凌捷. 基于Transformer和多特征融合的DGA域名检测方法[J]. 计算机工程与科学, 2023, 45(08): 1416-1423.
[12]	侯占伟, 李鑫, 王辉, 申自浩, 刘琨, 刘沛骞. 面向路网的空间众包隐私保护任务分配算法[J]. 计算机工程与科学, 2023, 45(08): 1424-1432.
[13]	印杰, 黄肖宇, 刘家银, 牛博威, 谢文伟, . 基于预训练语言模型的安卓恶意软件检测方法[J]. 计算机工程与科学, 2023, 45(08): 1433-1442.
[14]	谷文俊, 张晟恺, 邱晓梦, 李亚康, 宋伟. 基于双模态的小角散射图像结构表征技术研究[J]. 计算机工程与科学, 2023, 45(08): 1443-1452.
[15]	唐剑, 车文刚, 高盛祥. 融入注意力机制的多尺度卷积图像去雾方法[J]. 计算机工程与科学, 2023, 45(08): 1453-1462.