基于0.1π旋转相位Grover算法的ECC电压毛刺攻击算法

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

Abstract

Abstract:

The Grover's a1gorithm was used for fau1t attack against the pub1ic key cryptography.A fixed phase rotation based Grover's a1gorithm was proposed，and the probabi1ity of success achieved 99.23% with 0.1π phase rotation.Combined with the fau1t attack further，ECC（e11iptic curve cryptography）vo1tage burr attack a1gorithm based on Grover a1gorithm with 0.1π phase rotation was proposed.Then a safety Kob1itz curve，K-163，pub1ished successfu11y attacked by NIST on binary domain in simu1ation and the success rate was 100%.The comp1exity of the attack great1y reduces on the exponentia1.It was a new effective way，except the Shor's a1gorithm，to attack pub1ic key cryptography by quantum computing，and it contributed to extend the attack ways to the other pub1ic key cryptography.

Key words: quantum search a1gorithm, Grover's a1gorithm, phase matching, quantum computing, vo1tage burr attack

CLC Number:

TP309.7

Chao WANG,Lin CAO,Hui-hui JIA,Feng HU. ECC fault attack algorithm based on Grover's quantum search algorithm with 0.1π phase rotation[J]. Journal on Communications, 2017, 38(8): 1-8.

Figures/Tables 9

性能指标	Grover算法（α=0.1π）	Younes固定相位算法（α=1.825π）	Younes局部扩散算法（α=0.5π）	经典Grover算法
$P_{\min}$	0.992 3	0.980 7	0.847 6	0.500 0
${(\frac{N}{N})}_{P = P_{\min}}$	0.511 8	0.514 1	0.307 9	0.500 0
$R_{\max}$	159	90	35	24

References 22

[1]	ZHANG F , GUO S Z , ZHAO X J . A framework for the analysis and evaluation of algebraic fault attacks on lightweight block ciphers[J]. IEEE Transactions on Information Forensics and Security, 2016,11(5): 1039-1054.
[2]	ZHAO X J , GUO S , ZHANG F . Algebraic fault analysis on GOST for key recovery and reverse engineering[C]// 2014 Workshop on Fault Diagnosis and Tolerance in Cryptography(FDTC). 2014: 29-39.
[3]	BIHAM E , SHAMIR A . Differential fault analysis of secret key cryptosystem[J]. Springer Berlin Heidelberg, 1997,1294: 513-525.
[4]	BIEHL I , MEYER B , MULLER V . Differential fault attacks on elliptic curve cryptosystems[C]// CRYPTO 2000,LNCS 1880. 2000: 131-146.
[5]	DOMINGUE-VIEDO A , HASAN MA , ANSARI B . Fault-based attack on Montgomery′s ladder ECSM algorithm[J]. Journal of Cryptology, 2011,24(2): 346-374.
[6]	赵彦光, 白国强, 陈弘毅 ,等. ECC专用密码芯片的功耗分析研究[J]. 计算机工程与应用, 2006,42(16): 25-28.
	ZHAO Y G , BAI G Q , CHEN H Y ,et al. Study of power analysis attack to ECC in ASIC chip[J]. Computer Engineering and Applications, 2006,42(16): 25-28.
[7]	张金中, 寇应展, 王韬 ,等. 针对滑动窗口算法的椭圆曲线密码故障分析[J]. 通信学报, 2012,33(1): 71-78
	ZHANG J Z , KOU Y Z , WANG T ,et al. Fault analysis on elliptic curve cryptosystems with sliding window method[J]. Journal on Communications, 2012,33(1): 71-78.
[8]	王潮, 王云江, 胡风 . 量子计算机的商业化进展以及对信息安全的挑战[J]. 网络与信息安全学报, 2016,2(3): 17-27.
	WANG C , WANG Y J , HU F . Shaping the fature of commercial quantum computer and the challenge for information security[J]. Chinese Journal Network and Information Security, 2016,2(3): 17-27.
[9]	陈宇航, 贾徽徽, 姜丽莹 . 基于Grover算法的ECC扫描式攻击[J]. 信息网络安全, 2016(2): 28-32.
	CHEN Y H , JIA H H , JIANG L Y . ECC scanning attack based on Grover algorithm[J]. Net Info Security, 2016(2): 28-32.
[10]	BIHAM E , BIHAM O . Grover's quantum search algorithm for an arbitrary initial amplitude distribution[J]. Physical Review A, 1999,60(4): 2742-2745.
[11]	BIHAM E , BIHAM O . Analysis of generalized Grover quantum search algorithms using recursion equations[J]. Physical Review A, 2001,63(1): 5348-5353.
[12]	GROVER J K . Fixed-point quantum search[J]. Physical Review Letters, 2005,95(15): 1-4.
[13]	YOUNES A . Fixed phase quantum search algorithm[J]. Applied Mathematics ＆ Informationences, 2007,7(1): 93-98.
[14]	DHAWAN S , PERKOWSKI M . Comparison of influence of two data-encoding methods for Grover algorithm on quantum costs[C]// The 41st IEEE International Symposium on Multiple-Valued Logic. 2011: 176-181.
[15]	LONG G L , LI Y S , ZHANG W L . Dominant gate imperfection in Grover's quantum search algorithm[J]. Physical Review A, 2000,61(042305): 1-5.
[16]	LONG G L , LI Y S , XIAO L . Phase matching in quantum searching and the improved Grover algorithm[J]. Nuclear Physics Review, 2004,21(2): 114-116.
[17]	LI P C , LI S Y . Phase matching in Grover's algorithm[J]. Physics Letters A, 2007,366(1-2): 42-46.
[18]	YOUNES A , ROWE J , MILLER J . Quantum search algorithm with more reliable behaviour using partial diffusion[C]// The 7th International Conference on Quantum Communication,Measurement and Computing. 2004.
[19]	GROVER L K . Quantum mechanics helps in searching for a needle in a haystack[J]. Physical Review Letters, 1997,79(2): 325-328.
[20]	GROVER L K , . A fast quantum mechanical algorithm for database search[C]// The 28th Annual ACM Symposium on the Theory of Computing. 1996: 212-219.
[21]	BULGER D , BAEITOMPA W P , WOOD G R . Implementing pure adaptive search with Grover's quantum algorithm[J]. Journal of Optimization Theory and Applications, 2003,116(3): 517-529.
[22]	LONG G L , LI Y S , ZHANG W L . Phase matching in quantum searching[J]. Physics Letters A, 1999,262(1): 27-34.

Metrics

Recommended 0

No Suggested Reading articles found!

功击类型	复杂度
功击类型	m=8	m=16	m=32	m=64
原电压毛刺攻击	O（2¹²）	O（2¹⁹）	O（2³⁴）	O（2⁶⁵）
加入Grover算法	O（5× 2⁸）	O（5× 2¹¹）	O（5× 2¹⁸）	O（5× 2³³）

ECC fault attack algorithm based on Grover's quantum search algorithm with 0.1π phase rotation

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 22

Related Articles 15

Metrics

Recommended 0

[1]	Xiaoni DU, Xiangyu WANG, Lifang LIANG, Kaibin LI. Quantum cryptanalysis of lightweight block cipher Piccolo [J]. Journal on Communications, 2023, 44(6): 175-182.
[2]	Wei LI, Chun LIU, Dawu GU, Wenqian SUN, Jianning GAO, Mengyang QIN. Statistical ineffective fault analysis of the lightweight authenticated cipher algorithm Saturnin-Short [J]. Journal on Communications, 2023, 44(4): 167-175.
[3]	Hua REN, Shaozhang NIU, Ruyong REN, Zhen YUE. Research on meaningful image encryption algorithm based on 2-dimensional compressive sensing [J]. Journal on Communications, 2022, 43(5): 45-57.
[4]	Xiaodong YANG, Tian TIAN, Jiaqi WANG, Meijuan LI, Caifen WANG. Certificateless ciphertext retrieval scheme with multi-user and multi-keyword based on cloud-edge collaboration [J]. Journal on Communications, 2022, 43(5): 144-154.
[5]	Changgen PENG, Ting GAO, Huilan LIU, Hongfa DING. PCA-based membership inference attack for machine learning models [J]. Journal on Communications, 2022, 43(1): 149-160.
[6]	Xiaodong YANG, Wanting XI, Jiaqi WANG, Aijia CHEN, Caifen WANG. Electronic evidence sharing scheme of Internet of vehicles based on signcryption and blockchain [J]. Journal on Communications, 2021, 42(12): 236-246.
[7]	Ruiqi LI, Chunfu JIA, Yafei WANG. Multi-key homomorphic proxy re-encryption scheme based on NTRU and its application [J]. Journal on Communications, 2021, 42(3): 11-22.
[8]	Wei LI, Menglin WANG, Dawu GU, Jiayao LI, Tianpei CAI, Guangwei XU. Ciphertext-only fault analysis of the TWINE lightweight cryptogram algorithm [J]. Journal on Communications, 2021, 42(3): 135-149.
[9]	Shufen NIU,Wenke LIU,Lixia CHEN,Caifen WANG,Xiaoni DU. Electronic medical record data sharing scheme based on searchable encryption via consortium blockchain [J]. Journal on Communications, 2020, 41(8): 204-214.
[10]	Yiliang HAN,Zhong WANG. Code-based generalized signcryption scheme with multi-receiver [J]. Journal on Communications, 2020, 41(1): 53-65.
[11]	Youliang TIAN,Kedi YANG,Zuan WANG,Tao FENG. Algorithm of blockchain data provenance based on ABE [J]. Journal on Communications, 2019, 40(11): 101-111.
[12]	Wei LI,Yixin WU,Dawu GU,Jiayao LI,Shan CAO,Menglin WANG,Tianpei CAI,Xiangwu DING,Zhiqiang LIU. Ciphertext-only fault analysis of the SIMON lightweight cipher [J]. Journal on Communications, 2019, 40(11): 122-137.
[13]	Xiaodong YANG,Yutong LI,Jinli WANG,Tingchun MA,Caifen WANG. Revocable identity-based proxy re-signature scheme in the standard model [J]. Journal on Communications, 2019, 40(5): 153-162.
[14]	Yu SHEN,Wei LI,Dawu GU,Yixin WU,Shan CAO,Ya LIU,Zhiqiang LIU,Zhihong ZHOU. Integral fault analysis of the ARIA cipher [J]. Journal on Communications, 2019, 40(2): 164-173.
[15]	Hongyu YANG,Zaiming WANG. Android collusion attack detection model [J]. Journal on Communications, 2018, 39(6): 27-36.