第一寄存器小Qubit量子计算攻击RSA研究

doi:10.11959/j.issn.2096-109x.2017.00206

Abstract

Abstract:

The small Qubit quantum algorithm attack to RSA was proposed,the need Qubit of the first quantum register from 2L to L1,it can be reduced to 2 Qubit,the overall space complexity denoted (L1,L),where 2L1≥r,r is the period of decomposed.Because of the reduce of the first quantum register,it reduces the algorithm’s complexity and success rates,and use the binary look-up table method to compute the modular exponentiation,it enhances the computing speed.The improved algorithm’s quantum circuit complexity is T=O(2L2).It have a significant improvement on the time complexity and space complexity.Although the success rate is reduced,the overall success solution time is still lower than the Shor algorithm and the current major improvements Shor algorithm.Completed a simulation experiment.Respectively use the 11、10、9 Qubit decomposing the quantum circuit 119.The new algorithm explore the reality of using a universal quantum computer device to decipher the public key cryptography.

Key words: Shor algorithm, RSA algorithm, quantum circuits, small qubits, attack

CLC Number:

TP309

Bao-nan WANG,Yu-hang CHEN,Bao YIN,Feng HU,Huan-guo ZHANG,Chao WANG. Research of the small Qubit quantum computing attack to the RSA public key cryptography[J]. Chinese Journal of Network and Information Security, 2017, 3(10): 25-34.

Figures/Tables 11

攻击方法	时间复杂度	第一个寄存器的比特	第二个寄存器的比特	成功率	成功解决时间
Shor算法	$O (L^{3})$	2L	L	$\frac{ϕ (r)}{3 r} \frac{3}{4}$	$\frac{O (L^{3})}{\frac{ϕ (r)}{4 r}}$
改进的Shor算法	$O (L^{2})$	L1	L	$p = {\begin{cases} 0, 2^{L} < r \\ \frac{1}{ϕ (N)} \frac{ϕ (r)}{3 r} \frac{3}{4}, 2^{L} \geq r \end{cases}$	$\frac{O (N) O (L^{2})}{\frac{ϕ (r)}{4 r}}$

攻击方法	时间复杂度	第一个寄存器的比特	第二个寄存器的比特	成功率	成功解决时间
改进的Shor算法	$O (L^{2})$	L1	L	$p = {\begin{cases} 0, 2^{L} < r \\ \frac{1}{ϕ (N)} \frac{ϕ (r)}{3 r} \frac{3}{4}, 2^{L} \geq r \end{cases}$	$\frac{O (N) O (L^{2})}{\frac{ϕ (r)}{4 r}}$
整数分解算法	$O (L^{3})$	4	L	$\frac{3 ϕ (r)}{π^{2} r}$	$\frac{O (L^{3})}{\frac{ϕ (r)}{4 r}}$
高概率的整数分解算法	$O (L^{3})$	第一寄存器	第二寄存器	第三寄存器	$\frac{3 ϕ (r)}{π^{2} r} < p < \frac{4 ϕ (r)}{π^{2} r}$	$\frac{O (L^{3})}{\frac{4 ϕ (r)}{π^{2} r}}$
高概率的整数分解算法	$O (L^{3})$	L	L	L	$\frac{3 ϕ (r)}{π^{2} r} < p < \frac{4 ϕ (r)}{π^{2} r}$	$\frac{O (L^{3})}{\frac{4 ϕ (r)}{π^{2} r}}$
Michael的改进Shor算法	$O (L^{3})$	L_max≤L		L_max≤L	$\frac{x}{4^{2 L_{\max}}}$	$\frac{O (L^{3})}{\frac{x}{4^{2 L_{\max}}}}$
Parker的改进Shor算法	$O (L^{3})$	1		L	$\frac{3 (p - 1) (q - 1)}{N π^{2} r}$	$\frac{O (L^{3})}{\frac{3 (p - 1) (q - 1)}{N π^{2} r}}$

References 19

[1]	GIBNEY E . Physics:quantum computer quest:after a 30-years struggle to harness quantum weirdness for computing,physicists finally have their goal reach[J]. Nature News Feature, 2014: 24-26.
[2]	MARIANTONI M , WANG H , YAMAMOTO T et al . Implementing the quantum von neumann architecture with superconducting circuits[J]. Science, 2011,334(6052): 61-5.
[3]	ERIK L , BAREDNS R. , CHEN Y ,et al. Computing prime factors with a josephson phase Qubit quantum processor[J]. Nature Physical, 2012,8: 719-723
[4]	王潮, 王云江, 胡风 . 量子计算机的商业化进展及对信息安全的挑战[J]. 网络与信息安全学报, 2016,2(3): 17-27.
	WANG C , WANG Y J , HU F . Shaping the future of commercial quantum computer and the challenge for information security[J]. Chinese Journal of Network and Information Security, 2016,2(3): 17-27.
[5]	VARTIAINEN J J , NISKANEN A O , NAKAHARA M ,et al. Implementing Shor's algorithm on Josephson charge Qubits[J]. Physical Review A, 2004,70(1).
[6]	GLENDINNING I ?MER B . Parallelization of the QC-Lib quantum computer simulator library[J]. Lecture Notes in Computer Science, 2003,(3019): 461-468.
[7]	DE-RAEDT K , MICHIELSEN K , DE-RAEDT H ,ET AL. Massively parallel quantum computer simulator[J]. Computerphysicscommunications, 2007,176: 121-136.
[8]	GARCíA-MATA I , FRAHM K M , SHEPELYANSKY D L . Effects of imperfections for Shor’s factorization algorithm[J]. Physical Review A, 2007,(75).
[9]	YANG C , DANIEL L , BROWNE E , YANG T ,et al. Demonstration of a compiled version of Shor’s quantum factoring algorithm using photonic Qubits[J]. Physical Review Letter, 2007,(99).
[10]	THOMPSON M G , POLITI A , MATTHEWS J C F ,et al. Integrated waveguide circuits for optical quantum computing[J]. Institution of Engineering and Technology, 2011,5: 94-102
[11]	付向群, 鲍皖苏 . 具有高概率的量子计算算法研究[D]. 郑州:解放军信息工程大学, 2011
	FU X Q , BAO W S . Research on the quantum algorithm with high probability[D]. Zhengzhou:PLA Information Engineering University, 2011
[12]	NAGAICH S , GOSWAMI Y C . Shor’s algorithm for quantum numbers using MATLAB simulator[C]// The fifth International Conference on Advanced Computing ＆ Communication Technologies. 2015: 165-168.
[13]	DAVID S W , CHARIES D H , LLOYD C L ,et al. Simulatiobs of shor’s algorithm using matrix product states[J]. 2015.
[14]	董付国, 厉玉蓉, 杜萍 . 方幂模快速计算的二进制分组查表法[J]. 计算机工程与应用, 2009,45(22): 71-73.
	DONG F G , LI Y R , DU P . Fast calculation of modular exponentiation binary group look-up table method[J]. Computer Engineering and Applications, 2009,45(22): 71-73.
[15]	佐川弘幸, 吉田宣章, 著. 宋鹤山译. 量子信息论[M]. 大连: 大连理工大学出版社, 2007.
	SONG H S . Quantum information theory[M]. Dalian: Dalian University of Technology PressPress, 2007.
[16]	CHOI B S , METER R V . On the effect of quantum interaction distance on quantum addition circuits[J]..2010. ACM Journal on Emerging Technologies in Computing Systems, 2010.
[17]	PARKER S , PLENIO M B . Efficient factorization with a single pure Qubit and log N mixed qubits[J]. Physical Review Letter, 2000,(85): 3048-3052
[18]	MICHAEL R.G , ZHOU Z Y . Factoring 51 and 85 with 8 Qubits[R]. Scientific Reports, 2013.
[19]	孙国栋, 苏盛辉, 徐茂智 . 求根问题的量子计算算法[J]. 北京工业大学学报, 2015,(41): 366-371.
	SUN G D , SU S H , XU M Z . Quantum computing algorithms of find roots problems[J]. Journal of Beijing University of Technology, 2015,(41): 366-371.

Metrics

Recommended 0

No Suggested Reading articles found!

实验次数	分解数	需要的量子比特		随机数x	周期	总运行时间/s	分解周期时间/s	是否成功
实验次数	分解数	第一个量子寄存器	第二个量子寄存器	随机数x	周期	总运行时间/s	分解周期时间/s	是否成功
10	119	4	7	7	16	1 821	1 442	失败
10	119	4	7	11	16	1 670	1 350	失败
10	119	4	7	13	4	395	153	成功
10	119	4	7	53	16	1 790	1 413	失败
10	119	4	7	83	8	614	381	成功
10	119	4	7	97	16	1 881	1 451	成功
10	119	4	7	113	16	1 886	1 458	成功

实验次数	分解数	需要的量子比特		随机数x	周期	总运行时间/s	分解周期时间/s	是否成功
实验次数	分解数	第一个量子寄存器	第二个量子寄存器	随机数x	周期	总运行时间/s	分解周期时间/s	是否成功
5	119	5	7	13	未知	未知	未知	失败
10	119	4	7	13	4	395	153	成功
10	119	3	7	13	4	253	24	成功
10	119	2	7	13	4	250	7	成功
10	119	1	7	13	2	235	0.6	失败

实验次数	分解数	需要的量子比特		随机数x	周期	总运行时间/s	分解周期时间/s	是否成功
实验次数	分解数	第一个量子寄存器	第二个量子寄存器	随机数x	周期	总运行时间/s	分解周期时间/s	是否成功
5	119	5	7	83	未知	未知	未知	失败
10	119	4	7	83	8	614	381	成功
10	119	3	7	83	8	324	114	成功
10	119	2	7	83	4	252	13	失败
10	119	1	7	83	2	231	0.65	失败

实验次数	分解数	需要的量子比特		随机数x	周期	总运行时间/s	分解周期时间/s	是否成功
实验次数	分解数	第一个量子寄存器	第二个量子寄存器	随机数x	周期	总运行时间/s	分解周期时间/s	是否成功
5	119	5	7	97	未知	未知	未知	失败
10	119	4	7	97	16	1 881	1 451	成功
10	119	3	7	97	8	325	98	失败
10	119	2	7	97	4	248	11	失败
10	119	1	7	97	2	240	0.67	失败

第一个量子寄存器的数量	13	29	41	43	47	83	97	113	总成功数目
第一个量子寄存器的数量					周期				总成功数目
L=4	4	16	16	8	16	8	16	16	8次
L=4	成功	成功	成功	成功	成功	成功	成功	成功	8次
L=3	4	8	8	8	8	8	8	8	3次
L=3	成功	失败	失败	成功	失败	成功	失败	失败	3次
L=2	4	4	4	4	4	8	4	4	1次
L=2	成功	失败	失败	失败	失败	失败	失败	失败	1次

Research of the small Qubit quantum computing attack to the RSA public key cryptography

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 19

Related Articles 15

Metrics

Recommended 0

操作	时间复杂度	空间复杂度
模幂	O(L ³)	O (L )
量子傅里叶变换	O(L ²)	O (L+2)

[1]	Xianyi CHEN, Jun GU, Kai YAN, Dong JIANG, Linfeng XU, Zhangjie FU. Double adversarial attack against license plate recognition system [J]. Chinese Journal of Network and Information Security, 2023, 9(3): 16-27.
[2]	Genlin XIE, Guozhen CHENG, Yawen WANG, Qingfeng WANG. Software diversity evaluating method based on gadget feature analysis [J]. Chinese Journal of Network and Information Security, 2023, 9(3): 161-173.
[3]	Jinyin CHEN, Rongchang LI, Guohan HUANG, Tao LIU, Haibin ZHENG, Yao CHENG. Survey on vertical federated learning: algorithm, privacy and security [J]. Chinese Journal of Network and Information Security, 2023, 9(2): 1-20.
[4]	Benwei HE, Yunfei GUO, Yawen WANG, Qingfeng WANG, Hongchao HU. Software diversification method based on binary rewriting [J]. Chinese Journal of Network and Information Security, 2023, 9(2): 94-103.
[5]	Beiyuan YU, Shanyao REN, Jianwei LIU. Overview of blockchain assets theft attacks and defense technology [J]. Chinese Journal of Network and Information Security, 2023, 9(1): 1-17.
[6]	Yuning CHI, Yunfei GUO, Yawen WANG, Hongchao HU. Software diversity evaluation method based on the properties of ROP/JOP gadgets [J]. Chinese Journal of Network and Information Security, 2022, 8(6): 135-145.
[7]	Fukang XING, Zheng ZHANG, Ran SUI, Sheng QU, Xinsheng JI. Qualitative modeling and analysis of attack surface for process multi-variant execution software system [J]. Chinese Journal of Network and Information Security, 2022, 8(5): 121-128.
[8]	Wenfu LIU, Jianmin PANG, Xin ZHOU, Nan LI, Feng YUE. Research on network risk assessment based on attack graph of expected benefits-rate [J]. Chinese Journal of Network and Information Security, 2022, 8(4): 87-97.
[9]	Bao ZHANG, Youliang TIAN, Sheng GAO. Global randomized consensus algorithm resist collusion attack based on game theory [J]. Chinese Journal of Network and Information Security, 2022, 8(4): 98-109.
[10]	Fan GAO, Jian WANG, Jiqiang LIU. Research on link detection technology based on dynamic browser fingerprint [J]. Chinese Journal of Network and Information Security, 2022, 8(4): 144-156.
[11]	Shijie TANG, Fang YUAN, Jun LI, Yong DING, Huiyong WANG. Review on security risks of key components in industrial control system [J]. Chinese Journal of Network and Information Security, 2022, 8(3): 1-17.
[12]	Jinyin CHEN, Changan WU, Haibin ZHENG. Novel defense based on softmax activation transformation [J]. Chinese Journal of Network and Information Security, 2022, 8(2): 48-63.
[13]	Zhen GAO, Dongbin ZHANG, Xiao TIAN. Defense scheme for the world state based attack in Ethereum [J]. Chinese Journal of Network and Information Security, 2022, 8(2): 64-72.
[14]	Xiaohu LIU, Hengwei ZHANG, Junqiang MA, Yuchen ZHANG, Jinglei TAN. Research review of network defense decision-making methods based on attack and defense game [J]. Chinese Journal of Network and Information Security, 2022, 8(1): 1-14.
[15]	Jianming FU, Chang LIU, Mengfei XIE, Chenke LUO. Survey of software anomaly detection based on deception [J]. Chinese Journal of Network and Information Security, 2022, 8(1): 15-29.