基于Montgomery算法安全漏洞的SPA攻击算法

doi:10.3969/j.issn.1000-436x.2013.z1.020

Abstract

Abstract:

The Montgomery algorithm is widely used to reduce the computational complexity of large integer modular exponentiation. The SPA (simple power analysis) attacks against public-key cryptosystems based on Montgomery algo-rithm implementation were presented by exploitation of the inherent security vulnerability which that sensitive informa-tion leakage could be used by side-channel attack. The chosen-message SPA attacks were focused on, which enhance the differences of operating wave-forms between multiplication and squaring correlated to the secret key by using the input of particular messages. In particular, a SPA attack against RSA cryptosystem was showed based on large integer modular exponentiation. The results show that the attack algorithm is correct and effective.

Key words: modular exponentiation, side-channel attack, simple power analysis, Montgomery algorithm

Gang GAN,Min WANG,Zhi-bo DU,Zhen WU. Simple power analysis attack against cryptosystems based on Montgomery algorithm[J]. Journal on Communications, 2013, 34(Z1): 156-161.

Figures/Tables 18

References 14

[1]	KOCHER P , JAFFE J , JUN B . Differential power analysis[A]. Pro-ceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology[C]. 1999.388-397.
[2]	P KOCHER C . Timing attacks on implementations of diffie-hellman, RSA, DSS, and other systems[A]. Advances in Cryptology-CRYPTO' 96, Lecture Notes in Computer Science[C]. 1996.104-113.
[3]	韩军，曾晓洋，汤庭鳌．基于时间随机化的密码芯片防攻击方法[J]．计算机工程， 2007,33(2):6-8. HAN J , ZENG X Y , TANG T A . Modeling timing randomization in cryptographic chip against power analysis attack[J]. Computer Engi-neering, 2007,33(2):6-8.
[4]	成为，谷大武，郭筝等．一种针对RSA-CRT的功耗分析攻击方法[J]．通信技术， 2011,6(44):123-125. CHENG W , GU D W , GUO Z , et al. A power analysis attack against RSA-CRT[J]. Communications Technology, 2011,6(44):123-125.
[5]	吴震，陈运，陈俊等．真实硬件环境下幂剩余功耗轨迹指数信息提取[J]．通信学报， 2010,31(2):17-21. WU Z , CHEN Y , CHEN J , et al. Exponential information's extraction from power traces of modulo exponentiation implemented on FPGA[J]. Journal on Communications, 2010,31(2):17-21.
[6]	ACICMEZ O , SEIFERT J P , KOC C K . Predicting Secret Keys Via Branch Prediction[R]. Topics in Cryptology-CT-RSA, 2007.
[7]	ACIICMEZ O , KOC C K , SEIFERT J P . On the Power of Simple-Branch Prediction Analysis[R]. Cryptology ePrint Archive, 2006.
[8]	李志强，严迎建，段二鹏．差分能量攻击所需样本数量研究[J]．计算机工程， 2013,38(24):128-132. LI Z Q , YAN Y J , DUAN E P . Research on sample amounts needed by dif-ferential power attack[J]. Computer Engineering, 2013,38(24):128-132.
[9]	KADLOOR S , KIYAVASH N , VENKITASUBRAMANIAM P . Miti-gating timing side channel in shared schedulers[J]. arXiv preprint arXiv:1302.6123, 2013.
[10]	BAUER A , JAULMES E , PROUFF E , et al. Horizontal and vertical side-channel attacks against secure RSA implementations[A]. Topics in Cryptology-CT-RSA 2013 Springer Berlin Heidelberg[C]. 2013.1-17.
[11]	PROUFF E , RIVAIN M . Masking against side-channel attacks: a formal security proof[A]. Advances in Cryptology-EUROCRYPT 2013 Springer Berlin Heidelberg[C]. 2013.142-159.
[12]	杜之波，陈运．防范边信道攻击的逆伪操作实现算法[J]．计算机工程， 2010,36(3):131-133. DU Z B , CHEN Y . Implementation algorithm of pseudo modular in-version secure against side channel attack[J]. Computer Engineering, 2010,36(3):131-133.
[13]	BRICKEL E F . A survey of hardware implementations of RSA[A]. Proceedings of the Advances in Cryptology(CRYP TO'89)[C]. Santa Barbara, USA, 1990.368-370.
[14]	MARCELO E K , NAOFUMI T . A hardware algorithm for modular multiplication division based on the extended Euclidean algorithm[A]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences[C]. 2005.3610-3617.

Metrics

Recommended 0

No Suggested Reading articles found!

攻击方法	曲线条数	成功率	其他操作
对任意底数M的SPA	无法定量分析	无法保证100%	无
对选择底数M的SPADPA	幂指数二进制长度＞8 000	100%100%	无虑波处理，对齐操作

Simple power analysis attack against cryptosystems based on Montgomery algorithm

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 18

References 14

Related Articles 9

Metrics

Recommended 0

[1]	Shaohu DING,Jichao XIE,Peng ZHANG,Liming PU,Yunjie GU. Dynamic migration method of key virtual network function based on risk awareness [J]. Journal on Communications, 2020, 41(4): 102-113.
[2]	Shuo ZHAO,Xin-sheng JI,Yu-xing MAO,Guo-zhen CHENG,Hong-chao HU. Research on dynamic migration of virtual machine based on security level [J]. Journal on Communications, 2017, 38(7): 165-174.
[3]	Min WANG,Zhen WU,Jin-tao RAO,Zhi-bo DU. Mutual information power analysis attack in the frequency domain of the crypto chip [J]. Journal on Communications, 2015, 36(Z1): 131-135.
[4]	. Simple power analysis attack against cryptosystemsbased on Montgomery algorithm [J]. Journal on Communications, 2013, 34(Z1): 20-161.
[5]	Min WANG,Zhen WU. Algorithm of NAF scalar multiplication on ECC against SPA [J]. Journal on Communications, 2012, 33(Z1): 228-232.
[6]	Min WANG,Zhen WU. Simple power analysis attack on random pseudo operations [J]. Journal on Communications, 2012, 33(5): 138-142.
[7]	Zhen WU,Yun CHEN,Jun CHEN,Min WANG. Exponential information’s extraction from power traces of modulo exponentiation implemented on FPGA [J]. Journal on Communications, 2010, 31(2): 17-21.
[8]	Hong WANG,Bao LI,Wei YU. Montgomery algorithm on elliptic curves over finite fields of character three [J]. Journal on Communications, 2008, 29(10): 25-29.
[9]	Bao-hua ZHANG,Xin-chun YIN,Hai-ling ZHANG. EDSM:secure and efficient scalar multiplication algorithm on Edwards curves [J]. Journal on Communications, 2008, 29(10): 76-81.