[1]凃玲英,胡一凡,张洪涛,等.对Shor算法破解RSA的探讨[J].华侨大学学报(自然科学版),2015,36(6):640-644.[doi:10.11830/ISSN.1000-5013.2015.06.0640]
　TU Lingying,HU Yifan,ZHANG Hongtao,et al.Discussion on Cracking RSA With Shor Algorithm[J].Journal of Huaqiao University(Natural Science),2015,36(6):640-644.[doi:10.11830/ISSN.1000-5013.2015.06.0640]
点击复制

对Shor算法破解RSA的探讨()
分享到：

《华侨大学学报（自然科学版）》[ISSN:1000-5013/CN:35-1079/N]

卷:
第36卷
期数:
2015年第6期
页码:
640-644
栏目:
出版日期:
2015-11-10

文章信息/Info

Title:
Discussion on Cracking RSA With Shor Algorithm
文章编号:
1000-5013(2015)06-0640-05
作者:
凃玲英1; 2;  胡一凡1; 2;  张洪涛1; 2;  代永涛1; 2;  熊红梅1; 2
1. 湖北工业大学 纳米电子技术与微系统实验室, 湖北 武汉 430068;2. 湖北工业大学 电气与电子工程学院, 湖北 武汉 430068
Author(s):
TU Lingying1; 2;  HU Yifan1; 2;  ZHANG Hongtao1; 2;  DAI Yongtao1; 2;  XIONG Hongmei1; 2
1. Nanoelectronics and Microsystems Technology Laboratory, Hubei University of Technology, Wuhan 430068, China; 2. School of Electrical and Electronic Engineering, Hubei University of Technology, Wuhan 430068, China
关键词:
Shor算法;  非完全平方数;  RSA算法;  公钥密码体制;  蒙特卡洛法
Keywords:
Sahor algorithm;  non-perfect squares;  RSA algorithm;  public key password system;  Monte Carlo method
分类号:
TP301.6
DOI:
10.11830/ISSN.1000-5013.2015.06.0640
文献标志码:
A
摘要:
针对Shor算法具有随机性,会导致破解RSA公钥密码体制成功率不高的问题,对Shor算法原理、RSA公钥密码体制特点和大量计算结果进行分析,提出量子函数式f(x)=axmod n对a值的随机选取是有规律的.结合数论知识和蒙特卡洛法证明,结果表明:随机数a取完全平方数,所求周期r很可能不满足Shor算法要求;a取非完全平方数可以提高Shor算法破解RSA的成功率.
Abstract:
Since the randomness of Shor algorithm could lead to low success rate in cracking RSA. By analyzing the principle of Shor algorithm, characteristics of RSA public key password system and lots of data, the view that the way for quantum functional in randomly selecting value is regular was putting forward.Verified by number theory and Monte Carlo method, the results showed that if takes a perfect square, the cycle probably can’t meet the requirements of Shor algorithm. It comes to a conclusion that take a non-perfect square can improve the success rate of Shor algorithm in cracking RSA.

参考文献/References:

[1] HARDY G H,WRIGHT E M.An introduction to the theory of numbers[M].张晓尧,译.5版.北京:人民邮电出版社,2009:58-102.
[2] 朱和贵.探析初等数论基本知识在密码学中的应用[J].山东工业技术,2014(21):253.
[3] 李海峰,马海云,徐燕文.现代密码学原理及应用[M].北京:国防工业出版社,2013:110-114.
[4] NAM Y S,BLUMEL R.Sealing laws for Shor’s alglorithm with a banded quantum fourier transform[J].Physica Review A,2013,87(3):032333.
[5] 彭卫丰,孙力.SHOR量子算法的优化及应用研究[J].计算机应用与软件,2009,26(5):239-240,246.
[6] NIELSEN M A,CHUANG I L.量子计算和量子信息(一)[M].赵千川,译.北京:清华大学出版社,2009:199-223.
[7] 王蕴,黄德才,俞攸红.量子计算及量子算法研究进展[J].计算机系统应用,2011,20(6):228-231.
[8] 徐炜,肖智,杨道理.量子算法在大数据挖掘中的应用前景浅析[C]//中国信息经济学会学术年会暨博士生论坛论文集.广东:中国信息经济学会,2013:2-7.
[9] 付向群,鲍皖苏,王帅.ZN上离散对数量子计算算法[J].计算机学报,2014,37(5):1058-1062.
[10] GARCIA-MATA I,FRAHM K M,SPEPELYANSKY D L.Effects of imperfections for Shor’s factorization algorithm[J].Physical Review A,2007,75(5):2311.
[11] LUCERO E,BARENDS R,CHEN Y,et al.Computing prime factors with a Josephson phase qubit quantum processor[J].Nature Physics,2012,8:719-723.
[12] THOMPSON M G,POLITI A,MATTHEWS J C F,et al.Integrated waveguide circuits for optical quantum computing[J].Circuits, Device and System, IET,2010,5(2):94-102.

备注/Memo

备注/Memo:
收稿日期: 2015-05-24
通信作者: 凃玲英(1963-),女,副教授,主要从事量子通信与量子计算、视频监控系统的研究.E-mail:947392311@qq.com.
基金项目: 湖北省武汉市科技局“十城千辆新动力汽车计划”项目(2013011801010600)
更新日期/Last Update: 2015-11-20