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

Quantum Solving Euler’s Totient Function to Crack RSA

作　　者：张兴兰 张丰 ZHANG Xinglan;ZHANG Feng(Faculty of Information Technology,Beijing University of Technology,Beijing 100124,China;Beijing Key Laboratory of Trusted Computing,Beijing 100124,China)

机构地区：[1]北京工业大学信息学部,北京100124 [2]可信计算北京市重点实验室,北京100124

出　　处：《信息网络安全》2023年第7期1-8,共8页Netinfo Security

基　　金：北京市自然科学基金[4212015]。

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

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

分 类 号：TP309[自动化与计算机技术—计算机系统结构]