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

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

作　　者：王宝楠 陈宇航[1] 尹宝[1] 胡风[1] 张焕国[2] 王潮[1] 

机构地区：[1]上海大学通信与信息工程学院特种光纤与光接入网省部共建教育部重点实验室,上海200072 [2]武汉大学空天信息安全与可信计算教育部重点实验室,湖北武汉430072

出　　处：《网络与信息安全学报》2017年第10期25-34,共10页Chinese Journal of Network and Information Security

基　　金：国家自然科学基金重点资助项目(No.61332019);国家自然科学基金资助项目(No.61572304;No.61272096;No.60970006)~~

摘　　要：提出了针对RSA的小Qubit量子攻击算法设计,量子攻击的第一量子寄存器所需的Qubit数目由原先至少2L降低到L1,总体空间复杂度记为(L1,L),其中2L1≥r,r为分解所得周期。由于第一寄存器量子比特数的减少,降低了算法复杂度和成功率,且改进原算法中模幂计算,提升运算速率。改进攻击算法的量子电路的时间复杂度为T=O(2L2)。在时间复杂度和空间复杂度上都有明显的进步。改进算法的成功率降低了,但实际成功求解时间,即每次分解时间/成功率,依然低于Shor算法目前的主要改进算法。完成了仿真模拟实验,分别用11、10、9 Qubit成功分解119的量子电路。The small Qubit quantum algorithm attack to RSA was proposed, the need Qubit of the first quantum register from 2 L to L1, it can be reduced to 2 Qubit, the overall space complexity denoted（L1,L）, where 2 L1≥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（2 L2）. 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.

关 键 词：Shor算法 RSA算法 量子电路 小比特 攻击 

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