第一寄存器小Qubit量子计算攻击RSA研究 |
| |
作者姓名: | 王宝楠 陈宇航 尹宝 胡风 张焕国 王潮 |
| |
作者单位: | 1. 上海大学通信与信息工程学院特种光纤与光接入网省部共建教育部重点实验室,上海 200072;2. 武汉大学空天信息安全与可信计算教育部重点实验室,湖北 武汉 430072 |
| |
基金项目: | 国家自然科学基金重点资助项目(61332019);国家自然科学基金资助项目(61572304);国家自然科学基金资助项目(61272096);国家自然科学基金资助项目(60970006) |
| |
摘 要: | 提出了针对RSA的小Qubit量子攻击算法设计,量子攻击的第一量子寄存器所需的Qubit数目由原先至少2L降低到L1,总体空间复杂度记为(L1,L),其中2L1≥r,r为分解所得周期。由于第一寄存器量子比特数的减少,降低了算法复杂度和成功率,且改进原算法中模幂计算,提升运算速率。改进攻击算法的量子电路的时间复杂度为T=O(2L2)。在时间复杂度和空间复杂度上都有明显的进步。改进算法的成功率降低了,但实际成功求解时间,即每次分解时间/成功率,依然低于 Shor 算法目前的主要改进算法。完成了仿真模拟实验,分别用11、10、9 Qubit成功分解119的量子电路。
|
关 键 词: | Shor算法 RSA算法 量子电路 小比特 攻击 |
Research of the small Qubit quantum computing attack to the RSA public key cryptography |
| |
Authors: | Bao-nan WANG Yu-hang CHEN Bao YIN Feng HU Huan-guo ZHANG Chao WANG |
| |
Affiliation: | 1. Key Laboratory of Special Fiber Optics and Optical Access Networks,School of Communication and Information Engineering,Shanghai University,Shanghai 200072,China;2. Key Laboratory of Aerospace Information Security and Trusted Computing,Wuhan University,Wuhan 430072,China |
| |
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. |
| |
Keywords: | Shor algorithm RSA algorithm quantum circuits small qubits attack |
|
| 点击此处可从《》浏览原始摘要信息 |
|
点击此处可从《》下载全文 |