基于伪四维投射坐标的多基链标量乘法

doi:10.11959/j.issn.1000-436x.2018078

通信学报 ›› 2018, Vol. 39 ›› Issue (5): 74-84.doi: 10.11959/j.issn.1000-436x.2018078

基于伪四维投射坐标的多基链标量乘法

徐明^1,²(),史量¹

¹ 上海海事大学信息工程学院，上海 201306
² 同济大学电子与信息工程学院，上海 201804

修回日期:2018-03-26 出版日期:2018-05-01 发布日期:2018-06-01
作者简介:徐明（1977-），男，安徽马鞍山人，博士，上海海事大学副教授，主要研究方向为无线通信网络、网络空间安全等。|史量（1992-），男，重庆人，上海海事大学硕士生，主要研究方向为椭圆曲线密码学、网络空间安全等。
基金资助:
国家自然科学基金资助项目(61202370);中国博士后科学基金资助项目(2014M561512)

Pseudo 4D projective coordinate-based multi-base scalar multiplication

Ming XU^1,²(),Liang SHI¹

¹ College of Information Engineering,Shanghai Maritime University,Shanghai 201306,China
² College of Electronics and Information Engineering,Tongji University,Shanghai 201804,China

Revised:2018-03-26 Online:2018-05-01 Published:2018-06-01
Supported by:
The National Natural Science Foundation of China(61202370);The China Postdoctoral Science Foundation Projects(2014M561512)

摘要/Abstract

摘要：

针对椭圆曲线密码系统的标量乘运算开销较大和易受能量分析攻击的问题，提出基于伪四维投射坐标的快速群运算和基于伪四维投射坐标的多基链标量乘法，对椭圆曲线密码系统的群运算层和标量乘运算层进行优化，旨在提高椭圆曲线密码系统的整体性能并抵御常见的能量分析攻击。实验表明，与现有算法相比，所提算法离散群运算的倍点运算开销降低 5.71%，三倍点运算开销降低 3.17%，五倍点运算开销降低 8.74%。此外，在密钥长度为160位的情况下，所提算法连续群运算的三倍点运算开销降低36.32%，五倍点运算开销降低17.42%，系统整体开销降低8.70%。能量波形分析表明，所提算法可以有效抵御SPA攻击和DPA攻击。

关键词: 椭圆曲线密码系统, 坐标变换, 多基链标量乘法, 能量分析攻击

Abstract:

In order to address the problem of elliptic curve cryptosystem (ECC) for the expensive cost in scalar multiplication and the vulnerability to the power analysis attacks,a pseudo 4D projective coordinate-based multi-base scalar multiplication was proposed to optimize group operation layer and scalar multiplication operation layer,which aimed at increasing the performance of ECC and resisting common power analysis attacks.Experimental results show that compared with the state-of-the-art algorithms,the proposed algorithm decreases 5.71% of point doubling cost,3.17% of point tripling cost,and 8.74% of point quintupling cost under discrete group operations.When the key length is 160 bit,the proposed algorithm decreases 36.32% of point tripling cost,17.42% of point quintupling cost,and 8.70% of the system cost under continuous group operations.The analyzing of power consumption wave shows that the proposed algorithm can resist SPA and DPA attack.

Key words: elliptic curve cryptosystem, coordinate transformation, multi-base scalar multiplication, power analysis attack

中图分类号:

TP393

徐明,史量. 基于伪四维投射坐标的多基链标量乘法[J]. 通信学报, 2018, 39(5): 74-84.

Ming XU,Liang SHI. Pseudo 4D projective coordinate-based multi-base scalar multiplication[J]. Journal on Communications, 2018, 39(5): 74-84.

图/表 10

图1

图2

图3

表1

表2

图4

表3

图5

图6

图7

参考文献 25

[1]	RIVEST R , SHAMIR A , ADLEMAN L . A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1983,26(1): 96-99.
[2]	KOBLITZ N . Elliptic curve cryptosystems[J]. Mathematics of Computation, 1987,48(48): 203-209.
[3]	MILLER V . Use of elliptic curves in cryptography[J]. Lecture Notes in Computer Science, 1985,218(1): 417-426.
[4]	SAQIB N , . Key exchange protocol for WSN resilient against man in the middle attack[C]// IEEE International Conference on Advances in Computer Applications. 2017: 265-269.
[5]	YEH H L , CHEN T H , SHIH W K . Robust smart card secured authentication scheme on SIP using elliptic curve cryptography[J]. Computer Standards ＆Interfaces, 2014,36(2): 397-402.
[6]	SHENTU Q C , YU J P . A blind-mixing scheme for bitcoin based on an elliptic curve cryptography blind digital signature algorithm[J]. Computer Science, 2015: 1-17.
[7]	GUERON S , KRASNOV V . Fast prime field elliptic-curve cryptography with 256-bit primes[J]. Journal of Cryptographic Engineering, 2015,5(2): 141-151.
[8]	IZU T , TAKAGI T . Exceptional procedure attack on elliptic curve cryptosystems[C]// International Workshop on Public Key Cryptography-pkc. 2003: 224-239.
[9]	MATHER L , OSWALD E . Pinpointing side-channel information leaks in Web applications[J]. Journal of Cryptographic Engineering, 2012,2(3): 161-177.
[10]	KOCHER P , . Timing attacks on implementations of Diffie-Hellman,RSA,DSS,and other system[C]// International Cryptology Conference on Advances in Cryptology. 1996: 104-113.
[11]	MESSERGES T . Using second-order power analysis to attack DPA resistant software[J]. Springer Berlin Heidelberg, 2000,1965: 238-251.
[12]	王敏, 吴震 . 抗 SPA 攻击的椭圆曲线 NAF 标量乘实现算法[J]. 通信学报, 2012,33(S1): 228-232.
	WANG M , WU Z . Algorithm of NAF scalar multiplication on ECC against SPA[J]. Journal on Communications, 2012,33(S1): 228-232.
[13]	MAMIYA H , MIYAJI A , MORIMOTO H . Efficient countermeasures against RPA,DPA,and SPA[J]. Springer Berlin Heidelberg, 2014,3156: 343-356.
[14]	MISHRA P , DIMITROV V . Efficient quintuple formulas for elliptic curves and efficient scalar multiplication using multibase number representation[C]// International Conference on Information Security. 2007: 390-406.
[15]	DANGER J , GUILLEY S , HOOGVORST P ,et al. Improving the big mac attack on elliptic curve cryptography[J]. Springer Berlin Heidelberg, 2016: 374-386.
[16]	LI L , LI S . High-performance pipelined architecture of elliptic curve scalar multiplication over GF(2m)[J]. IEEE Transactions on Very Large Scale Integration Systems, 2016,24(4): 1223-1232.
[17]	DUBEUF J , HELY D , BEROULLE V . ECDSA passive attacks,leakage sources,and common design mistakes[J]. ACM Transactions on Design Automation of Electronic Systems, 2016,21(2): 1-24.
[18]	LIU Z , HUANG X , HU Z ,et al. On emerging family of elliptic curves to secure Internet of Things:ECC comes of age[J]. IEEE Transactions on Dependable ＆ Secure Computing, 2017,14(3): 237-248.
[19]	MELONI N , HASAN M . Efficient double bases for scalar multiplication[J]. IEEE Transactions on Computers, 2015,64(8): 2204-2212.
[20]	CHO S , GWAL S , CHANG H K ,et al. Faster elliptic curve arithmetic for triple-base chain by reordering sequences of field operations[J]. Multimedia Tools ＆Applications, 2016: 1-13.
[21]	PUROHIT G , RAWAT A . Elliptic curve point multiplication using MBNR and point halving[J]. International Journal of Advanced Networking ＆ Applications, 2012: 1329-1337.
[22]	PAAR C , PELZL J . Understanding cryptography[J]. Springer Berlin Heidelberg, 2010: 519-551.
[23]	HASAN AE , REYHANIMASOLEH A . New regular radix-8 scheme for elliptic curve scalar multiplication without pre-computation[J]. IEEE Transactions on Computers, 2013,64(2): 438-451.
[24]	BERNSTEIN D , CHUENGSATIANSUP C , LANGE T . Double-base scalar multiplication revisited[R]. IACR Cryptology ePrint Archive, 2017: 1-38.
[25]	O’FLYNN C , CHEN Z . ChipWhisperer:an open-source platform for hardware embedded security research[C]// International Workshop on Constructive Side-Channel Analysis and Secure Design. 2014: 243-260.

密钥位数/bit	c₁	c₂	c₃	最短链长/个
160	0.223	0.321	0.254	30.621
192	0.238	0.363	0.432	54.682
256	0.415	0.502	0.347	62.644
384	0.323	0.452	0.328	91.097

算法	倍点	三倍点	五倍点
文献[14]	4M+6S	10M+6S	15M+10S
文献[15]	6M+2S	N/A	N/A
文献[17]	4M+4S	N/A	N/A
文献[19]	1M+8S	5M+10S	N/A
文献[20]	4M+6S	10M+6S	12M+13S
文献[21]	1I+2M+S	1I+7M+4S	1I+13M+5S
本文	3M+5S	7M+7S	11M+12S

算法	群运算方法	标量乘方法	总开销/次
文献[14]	雅可比	D＆A方法	1 950.60
文献[13]	雅可比	蒙哥马利阶梯	1 682.40
文献[17]	雅可比	多基链(2、3、5为基)	1 567.78
文献[16]	雅可比	双基链(2、3为基)	1 524.42
文献[15]	投射	蒙哥马利阶梯	1 396.20
文献[18]	仿射	多基链(1/2、3、5为基)	1 343.72
本文	伪四维	多基链(2、3、5为基)	1 236.16

基于伪四维投射坐标的多基链标量乘法

Pseudo 4D projective coordinate-based multi-base scalar multiplication

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 25

相关文章 8

Metrics

推荐阅读 0

[1]	杜之波,吴震,王敏,饶金涛. 基于SM3的动态令牌的能量分析攻击方法[J]. 通信学报, 2017, 38(3): 65-72.
[2]	吴震,王敏,饶金涛,杜之波,王胜,张凌浩. 针对基于SM3的HMAC的互信息能量分析攻击[J]. 通信学报, 2016, 37(Z1): 57-62.
[3]	杜之波,孙元华,王燚. 针对AES密码算法的多点联合能量分析攻击[J]. 通信学报, 2016, 37(Z1): 78-84.
[4]	杜之波,吴震,王敏,饶金涛. 针对基于SM3的HMAC的能量分析攻击方法[J]. 通信学报, 2016, 37(5): 38-43.
[5]	杜之波,吴震,王敏,饶金涛. 针对SM4轮输出的改进型选择明文功耗分析攻击[J]. 通信学报, 2015, 36(10): 85-91.
[6]	王敏,杜之波,吴震,饶金涛. 针对SMS4轮输出的选择明文能量分析攻击[J]. 通信学报, 2015, 36(1): 142-148.
[7]	甘刚，王敏，杜之波，吴震. 基于Montgomery算法安全漏洞的SPA攻击算法[J]. 通信学报, 2013, 34(Z1): 20-161.
[8]	甘刚,王敏,杜之波,吴震. 基于Montgomery算法安全漏洞的SPA攻击算法[J]. 通信学报, 2013, 34(Z1): 156-161.