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

• 作者: 尹宝 张焕国 王宝楠 王潮 胡风 陈宇航
• 来源期刊: 网络与信息安全学报
• 学科: 工学
• 关键词: Shor算法 RSA算法 量子电路 小比特 攻击
• 年，卷（期）: 2017,（10）
• 所属期刊栏目: 学术论文
• 页码范围: 25-34
• 页数: 10页
• 分类号: TP309
• 字数: 7401字
• 语种: 中文
• DOI: 10.11959/j.issn.2096-109x.2017.00206

摘要

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