量子求解欧拉函数破解RSA算法

doi:10.3969/j.issn.1671-1122.2023.07.001

信息网络安全 ›› 2023, Vol. 23 ›› Issue (7): 1-8.doi: 10.3969/j.issn.1671-1122.2023.07.001

量子求解欧拉函数破解RSA算法

张兴兰¹^,², 张丰¹^,²()

1.北京工业大学信息学部，北京 100124
2.可信计算北京市重点实验室，北京 100124

收稿日期:2023-01-16 出版日期:2023-07-10 发布日期:2023-07-14
通讯作者: 张丰 changfeng@emails.bjut.edu.cn
作者简介:张兴兰（1970—），女，山西，教授，博士，主要研究方向为密码学、量子计算、量子机器学习和量子密钥|张丰（1998—），男，江西，硕士研究生，主要研究方向为量子计算、量子机器学习和量子组合优化
基金资助:
北京市自然科学基金(4212015)

Quantum Solving Euler’s Totient Function to Crack RSA

ZHANG Xinglan¹^,², ZHANG Feng¹^,²()

1. Faculty of Information Technology, Beijing University of Technology, Beijing 100124, China
2. Beijing Key Laboratory of Trusted Computing, Beijing 100124, China

Received:2023-01-16 Online:2023-07-10 Published:2023-07-14

摘要/Abstract

摘要：

量子计算根据量子力学原理设计，具有天然的并行计算优势。Shor算法是一个能够快速分解整数，从而有望破解RSA加密技术的算法。然而Shor算法存在着需要构造的模幂电路极其复杂、量子位数会影响后期连分式计算精度的缺点，因此难以在量子计算机上实现。针对上述问题，文章基于数论知识和RSA算法提出一种新的算法，设计相关量子线路去求解待分解整数$~N$的欧拉函数，待量子求解出待分解整数的欧拉函数后，通过构造二元一次方程组可以求出整数$~N$的两质因子。并且结合公钥可以进一步计算出私钥，从而对密文进行破译。文章所提算法在做到通用的基础上，只使用$~2n+2$个量子比特，仅需要求解数的模乘，不用进行连分式计算，从而实现计算量和线路复杂度低的量子算法。

关键词: 量子计算, Shor算法, RSA算法, 欧拉函数

Abstract:

Quantum computing is a novel computing mode based on the principles of quantum mechanics, which has the natural advantages of parallel computing. Shor’s algorithm is an algorithm that can quickly decompose integers and is expected to crack RSA encryption technology. However, Shor’s algorithm is difficult to be implemented on a quantum computer due to the fact that the modular power circuit to be constructed is extremely complex, and the number of qubits affects the accuracy of the subsequent continued fractions. To solve the above problems, this paper proposed a new algorithm based on the knowledge of number theory and RSA algorithm, designed relevant quantum circuits to solve the Euler’s totient function of the integer N to be decomposed. After the Euler’s totient function of the integer N to be decomposed was solved by quantum computing, the two prime factors could be obtained by constructing and solving a system of binary linear equations. Moreover, the private key could be further calculated by combining the public key, so as to crack the ciphertext. On the basis of universality, this algorithm only uses 2n+2 qubits, only needs to solve the modular multiplication of numbers, and does not need to calculate continued fractions.

Key words: quantum computing, Shor’s algorithm, RSA algorithm, Euler’s totient function

中图分类号:

TP309

张兴兰, 张丰. 量子求解欧拉函数破解RSA算法[J]. 信息网络安全, 2023, 23(7): 1-8.

ZHANG Xinglan, ZHANG Feng. Quantum Solving Euler’s Totient Function to Crack RSA[J]. Netinfo Security, 2023, 23(7): 1-8.

图/表 10

图1

图2

图3

图4

图5

表1

图6

图7

图8

图9

参考文献 27

[1]	FEYNMAN R P. Simulating Physics with Computers[J]. International Journal of Theoretical Physics, 1982, 21(6): 467-488. doi: 10.1007/BF02650179 URL
[2]	ARUTE F, ARYA K, BABBUSH R, et al. Quantum Supremacy Using a Programmable Superconducting Processor[J]. Nature, 2019, 574(7779): 505-510. doi: 10.1038/s41586-019-1666-5
[3]	BHATIA V, RAMKUMAR K R. An Efficient Quantum Computing Technique for Cracking RSA Using Shor's Algorithm[C]// IEEE. 5th International Conference on Computing Communication and Automation. New York: IEEE, 2020: 89-94.
[4]	MASLOV D, NAM Y, KIM J. An Outlook for Quantum Computing[J]. Proceedings of the IEEE, 2018, 107(1): 5-10. doi: 10.1109/JPROC.2018.2884353 URL
[5]	NIELSEN M A, CHUANG I L. Quantum Computation and Quantum Information[M]. Cambridge: Cambridge University Press, 2010.
[6]	DEUTSCH D, JOZSA R. Rapid Solution of Problems by Quantum Computation[J]. Proceedings of the Royal Society A, 1992, 439(1907): 553-558.
[7]	SHOR P W. Algorithms for Quantum Computation: Discrete Logarithms and Factoring[C]// IEEE. Proceedings 35th Annual Symposium on Foundations of Computer Science. Piscataway: IEEE, 1994: 124-134.
[8]	GROVER L K. A Fast Quantum Mechanical Algorithm for Database Search[C]// ACM. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. New York: ACM. 1996: 212-219.
[9]	HARROW A W, HASSIDIM A, LLOYD S. Quantum Algorithm for Linear Systems of Equations[EB/OL].(2009-07-5) [2022-12-10]. https://doi.org/10.1103/PhysRevLett.103.150502.
[10]	LI Zhaokai, LIU Xiaomei, XU Nanyang, et al. Experimental Realization of a Quantum Support Vector Machine[EB/OL]. (2014-12-01) [2022-12-10]. https://doi.org/10.1103/PhysRevLett.114.140504.
[11]	LLOYD S, MOHSENI M, REBENTROST P. Quantum Principal Component Analysis[J]. Nature Physics, 2014, 10(9): 631-633. doi: 10.1038/nphys3029
[12]	OHZEKI M. Message-Passing Algorithm of Quantum Annealing with Nonstoquastic Hamiltonian[EB/OL]. (2019-04-17) [2022-12-10]. https://doi.org/10.7566/JPSJ.88.061005.
[13]	ZHANG Guofeng, HAMDULLA A. Adaptive Morphological Contrast Enhancement Based on Quantum Genetic Algorithm for Point Target Detection[J]. Mobile Networks and Applications, 2021, 26(2): 638-648. doi: 10.1007/s11036-019-01410-8
[14]	AMICO M, SALEEM Z H, KUMPH M. Experimental Study of Shor's Factoring Algorithm Using the IBM Q Experience[EB/OL]. (2019-03-02) [2022-12-10]. https://doi.org/10.1103/PhysRevA.100.012305.
[15]	RIVEST R L, SHAMIR A, ADLEMAN L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems[J]. Communications of the ACM, 1978, 21(2): 120-126. doi: 10.1145/359340.359342 URL
[16]	GAMEL O, JAMES D F V. Simplified Factoring Algorithms for Validating Small-Scale Quantum Information Processing Technologies[EB/OL]. (2013-11-14) [2022-12-10]. https://doi.org/10.48550/arXiv.1310.6446.
[17]	GELLER M R, ZHOU Z. Factoring 51 and 85 with 8 Qubits[J]. Scientific reports, 2013, 3(1): 1-5.
[18]	MOUSAVI M, HOUSHMAND M, BOLOKIAN M. The Cost Reduction of Distributed Quantum Factorization Circuits[J]. International Journal of Theoretical Physics, 2021, 60(4): 1292-1298. doi: 10.1007/s10773-021-04756-6
[19]	SKOSANA U, TAME M. Demonstration of Shor’s Factoring Algorithm for N \$\$= \$\$= 21 on IBM Quantum Processors[J]. Scientific Reports, 2021, 11(1): 1-12. doi: 10.1038/s41598-020-79139-8
[20]	CHERVENAK A, VELLANKI V, KURMAS Z. Protecting File Systems: A Survey of Backup Techniques[C]// ACM. Joint NASA and IEEE Mass Storage Conference. New York: ACM. 1998: 17-31.
[21]	WIENER M J. Cryptanalysis of Short RSA Secret Exponents[J]. IEEE Transactions on Information theory, 1990, 36(3): 553-558. doi: 10.1109/18.54902 URL
[22]	BONEH D. Twenty Years of Attacks on the RSA Cryptosystem[J]. Notices of the AMS, 1999, 46(2): 203-213.
[23]	SHAND M, VUILLEMIN J. Fast Implementations of RSA Cryptography[C]// IEEE. Proceedings of IEEE 11th Symposium on Computer Arithmetic. New York: IEEE, 1993: 252-259.
[24]	BEAUREGARD S. Circuit for Shor's Algorithm Using 2n+3 Qubits[J]. Quantum Information & Computation, 2003, 3(2): 175-185.
[25]	DRAPER T G. Addition on a Quantum Computer[EB/OL]. (2000-08-07) [2022-12-10]. https://doi.org/10.48550/arXiv.quant-ph/0008033.
[26]	CROSS A. The IBM Q Experience and Qiskit Open-Source Quantum Computing Software[C]// APS. APS March Meeting Abstracts. Maryland: APS, 2018: 53-58.
[27]	DA S A J, PARK D K. Linear-Depth Quantum Circuits for Multiqubit Controlled Gates[EB/OL]. (2022-09-07) [2022-12-10]. https://doi.org/10.1103/PhysRevA.106.042602.

Qiskit Software	Version
qiskit-terra	0.21.2
qiskit-aer	0.10.4
qiskit-ignis	0.7.1
qiskit-ibmq-provider	0.19.2
qiskit	0.37.2
Python version	3.8.0
Python compiler	Clang 4.0.1 (tags/RELEASE_401/final)
Python build	default, Nov 6 2019 15:49:01
OS	macOS Monterey 12.5.1
CPU	8
Memory (GB)	16

量子求解欧拉函数破解RSA算法

Quantum Solving Euler’s Totient Function to Crack RSA

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 27

相关文章 9

编辑推荐

Metrics

本文评价

[1]	游伟青, 陈小明, 齐健. 一类抗量子计算的公钥密码算法研究[J]. 信息网络安全, 2017, 17(4): 53-60.
[2]	王永建, 张健, 程少豫, 铁小辉. 面向云计算的同态加密改进设计[J]. 信息网络安全, 2017, 17(3): 21-26.
[3]	. 基于格的大数据动态存储完整性验证方案[J]. , 2014, 14(4): 46-.
[4]	吴乐华;孙贤鲁;孟槟;朱晋飞. 基于 Android 手机软件认证的U盘锁系统[J]. , 2014, 14(3): 0-0.
[5]	. 基于 Android 手机软件认证的U盘锁系统[J]. , 2014, 14(3): 68-.
[6]	张焕国;王后珍. 抗量子计算密码体制研究(续前)[J]. , 2011, 11(6): 0-0.
[7]	张焕国;王后珍. 抗量子计算密码体制研究(待续)[J]. , 2011, 11(5): 0-0.
[8]	钟秀玉. 加密算法在身份验证中的应用[J]. , 2010, (5): 0-0.
[9]	管海明. 抗量子计算公钥密码需求分析与技术路线[J]. , 2009, 9(4): 0-0.