网络与信息安全学报 ›› 2017, Vol. 3 ›› Issue (10): 25-34.doi: 10.11959/j.issn.2096-109x.2017.00206

• 学术论文 • 上一篇    下一篇

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

王宝楠1,陈宇航1,尹宝1,胡风1,张焕国2,王潮1   

  1. 1 上海大学通信与信息工程学院特种光纤与光接入网省部共建教育部重点实验室,上海 200072
    2 武汉大学空天信息安全与可信计算教育部重点实验室,湖北 武汉 430072
  • 修回日期:2017-09-27 出版日期:2017-10-01 发布日期:2017-11-13
  • 作者简介:王宝楠(1989-),女,江苏淮安人,上海大学博士生,主要研究方向为信息安全、量子计算密码、社会网络。|陈宇航(1991-),男,浙江杭州人,上海大学硕士生,主要研究方向为量子计算与量子攻击密码分析。|尹宝(1991-),男,河南信阳人,上海大学硕士生,主要研究方向为量子计算与量子攻击密码分析。|胡风(1991-),男,浙江温州人,上海大学博士生,主要研究方向为信息安全、量子计算密码、社会网络。|张焕国(1945-),男,河北元氏人,武汉大学教授、博士生导师,主要研究方向为信息安全、密码学和可信计算。|王潮(1971-),男,江苏镇江人,博士,上海大学教授,主要研究方向为无线传感器网络、网络信息安全与椭圆曲线密码学、量子计算与量子攻击密码分析。
  • 基金资助:
    国家自然科学基金重点资助项目(61332019);国家自然科学基金资助项目(61572304);国家自然科学基金资助项目(61272096);国家自然科学基金资助项目(60970006)

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

Bao-nan WANG1,Yu-hang CHEN1,Bao YIN1,Feng HU1,Huan-guo ZHANG2,Chao WANG1   

  1. 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
  • Revised:2017-09-27 Online:2017-10-01 Published:2017-11-13
  • Supported by:
    The Key Program of National Natural Science Foundation of China(61332019);The National Natural Science Foundation of China(61572304);The National Natural Science Foundation of China(61272096);The National Natural Science Foundation of China(60970006)

摘要:

提出了针对RSA的小Qubit量子攻击算法设计,量子攻击的第一量子寄存器所需的Qubit数目由原先至少2L降低到L1,总体空间复杂度记为(L1,L),其中2L1≥r,r为分解所得周期。由于第一寄存器量子比特数的减少,降低了算法复杂度和成功率,且改进原算法中模幂计算,提升运算速率。改进攻击算法的量子电路的时间复杂度为T=O(2L2)。在时间复杂度和空间复杂度上都有明显的进步。改进算法的成功率降低了,但实际成功求解时间,即每次分解时间/成功率,依然低于 Shor 算法目前的主要改进算法。完成了仿真模拟实验,分别用11、10、9 Qubit成功分解119的量子电路。

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

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

中图分类号: 

No Suggested Reading articles found!