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

王宝楠; 陈宇航; 尹宝; 胡风; 张焕国; 王潮

doi:10.11959/j.issn.2096-109x.2017.00206

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-03

- 第一寄存器小Qubit量子计算攻击RSA研究
- Research of the small Qubit quantum computing attack to the RSA public key cryptography
- 网络与信息安全学报 2017年3卷第10期页码：25-34
- 作者机构：
  
  1. 上海大学通信与信息工程学院特种光纤与光接入网省部共建教育部重点实验室，上海 200072
  2. 武汉大学空天信息安全与可信计算教育部重点实验室，湖北武汉 430072
- 作者简介：
  
  [ "王宝楠（1989-），女，江苏淮安人，上海大学博士生，主要研究方向为信息安全、量子计算密码、社会网络。" ]
  [ "陈宇航（1991-），男，浙江杭州人，上海大学硕士生，主要研究方向为量子计算与量子攻击密码分析。" ]
  [ "尹宝（1991-），男，河南信阳人，上海大学硕士生，主要研究方向为量子计算与量子攻击密码分析。" ]
  [ "胡风（1991-），男，浙江温州人，上海大学博士生，主要研究方向为信息安全、量子计算密码、社会网络。" ]
  [ "张焕国（1945-），男，河北元氏人，武汉大学教授、博士生导师，主要研究方向为信息安全、密码学和可信计算。" ]
  [ "王潮（1971-），男，江苏镇江人，博士，上海大学教授，主要研究方向为无线传感器网络、网络信息安全与椭圆曲线密码学、量子计算与量子攻击密码分析。" ]
- 基金信息：
  
  国家自然科学基金重点资助项目;Key Program of National 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)
- DOI：10.11959/j.issn.2096-109x.2017.00206
  中图分类号： TP309
- 网络首发：2017-10，
  
  纸质出版：2017-10-15
- 稿件说明：
移动端阅览
王宝楠, 陈宇航, 尹宝, 等. 第一寄存器小Qubit量子计算攻击RSA研究[J]. 网络与信息安全学报, 2017,3(10):25-34.

Bao-nan WANG, Yu-hang CHEN, Bao YIN, et al. Research of the small Qubit quantum computing attack to the RSA public key cryptography[J]. Chinese Journal of Network and Information Security, 2017, 3(10): 25-34.
王宝楠, 陈宇航, 尹宝, 等. 第一寄存器小Qubit量子计算攻击RSA研究[J]. 网络与信息安全学报, 2017,3(10):25-34. DOI： 10.11959/j.issn.2096-109x.2017.00206.

Bao-nan WANG, Yu-hang CHEN, Bao YIN, et al. Research of the small Qubit quantum computing attack to the RSA public key cryptography[J]. Chinese Journal of Network and Information Security, 2017, 3(10): 25-34. 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的量子电路。

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

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

references

GIBNEY E . Physics:quantum computer quest:after a 30-years struggle to harness quantum weirdness for computing,physicists finally have their goal reach [J ] . Nature News Feature , 2014 : 24 - 26 .

MARIANTONI M , WANG H , YAMAMOTO T et al . Implementing the quantum von neumann architecture with superconducting circuits [J ] . Science , 2011 , 334 ( 6052 ): 61 - 5 .

ERIK L , BAREDNS R. , CHEN Y , et al . Computing prime factors with a josephson phase Qubit quantum processor [J ] . Nature Physical , 2012 , 8 : 719 - 723

王潮 , 王云江 , 胡风 . 量子计算机的商业化进展及对信息安全的挑战 [J ] . 网络与信息安全学报 , 2016 , 2 ( 3 ): 17 - 27 .

WANG C , WANG Y J , HU F . Shaping the future of commercial quantum computer and the challenge for information security [J ] . Chinese Journal of Network and Information Security , 2016 , 2 ( 3 ): 17 - 27 .

VARTIAINEN J J , NISKANEN A O , NAKAHARA M , et al . Implementing Shor's algorithm on Josephson charge Qubits [J ] . Physical Review A , 2004 , 70 ( 1 ).

GLENDINNING I ÖMER B . Parallelization of the QC-Lib quantum computer simulator library [J ] . Lecture Notes in Computer Science , 2003 ,( 3019 ): 461 - 468 .

DE-RAEDT K , MICHIELSEN K , DE-RAEDT H , ET AL . Massively parallel quantum computer simulator [J ] . Computerphysicscommunications , 2007 , 176 : 121 - 136 .

GARCÍA-MATA I , FRAHM K M , SHEPELYANSKY D L . Effects of imperfections for Shor’s factorization algorithm [J ] . Physical Review A , 2007 ,( 75 ).

YANG C , DANIEL L , BROWNE E , YANG T , et al . Demonstration of a compiled version of Shor’s quantum factoring algorithm using photonic Qubits [J ] . Physical Review Letter , 2007 ,( 99 ).

THOMPSON M G , POLITI A , MATTHEWS J C F , et al . Integrated waveguide circuits for optical quantum computing [J ] . Institution of Engineering and Technology , 2011 , 5 : 94 - 102

付向群 , 鲍皖苏 . 具有高概率的量子计算算法研究 [D ] . 郑州:解放军信息工程大学 , 2011

FU X Q , BAO W S . Research on the quantum algorithm with high probability [D ] . Zhengzhou:PLA Information Engineering University , 2011

NAGAICH S , GOSWAMI Y C . Shor’s algorithm for quantum numbers using MATLAB simulator [C ] // The fifth International Conference on Advanced Computing ＆ Communication Technologies . 2015 : 165 - 168 .

DAVID S W , CHARIES D H , LLOYD C L , et al . Simulatiobs of shor’s algorithm using matrix product states [J ] . 2015 .

董付国 , 厉玉蓉 , 杜萍 . 方幂模快速计算的二进制分组查表法 [J ] . 计算机工程与应用 , 2009 , 45 ( 22 ): 71 - 73 .

DONG F G , LI Y R , DU P . Fast calculation of modular exponentiation binary group look-up table method [J ] . Computer Engineering and Applications , 2009 , 45 ( 22 ): 71 - 73 .

佐川弘幸 , 吉田宣章 , 著. 宋鹤山译. 量子信息论 [M ] . 大连 : 大连理工大学出版社 , 2007 .

SONG H S . Quantum information theory [M ] . Dalian : Dalian University of Technology PressPress , 2007 .

CHOI B S , METER R V . On the effect of quantum interaction distance on quantum addition circuits [J ] ..2010. ACM Journal on Emerging Technologies in Computing Systems , 2010 .

PARKER S , PLENIO M B . Efficient factorization with a single pure Qubit and log N mixed qubits [J ] . Physical Review Letter , 2000 ,( 85 ): 3048 - 3052

MICHAEL R.G , ZHOU Z Y . Factoring 51 and 85 with 8 Qubits [R ] . Scientific Reports , 2013 .

孙国栋 , 苏盛辉 , 徐茂智 . 求根问题的量子计算算法 [J ] . 北京工业大学学报 , 2015 ,( 41 ): 366 - 371 .

SUN G D , SU S H , XU M Z . Quantum computing algorithms of find roots problems [J ] . Journal of Beijing University of Technology , 2015 ,( 41 ): 366 - 371 .

浏览量

2088

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据