量子计算密码攻击进展  

Progress in Quantum Computing Cryptography Attacks

作　　者：王潮[1,2,3] 姚皓南 王宝楠 胡风 张焕国[6] 纪祥敏 WANG Chao;YAO Hao-Nan;WANG Bao-Nan;HU Feng;ZHANG Huan-Guo;JI Xiang-Min(Key Laboratory of Specialty Fiber Optics and Optical Access Networks,Joint International Research Laboratory of Specialty Fiber Optics and Advanced Communication,Shanghai University,Shanghai 200444;State Key Laboratory of Cryptology,Beijing 100878;Center for Quantum Computing,Peng Cheng Laboratory,Guangdong Shenzhen 518000;College of Computer Information Science,Fujian Agriculture and Forestry University,Fuzhou 350002;College of Computer Science and Technology,Shanghai University of Electric Power,Shanghai 200090;School of Cyber Science and Engineering,Wuhan University,Wuhan 430072)

机构地区：[1]特种光纤与光接入网重点实验室,特种光纤与先进通信国际合作联合实验室上海大学,上海200444 [2]密码科学技术国家重点实验室,北京100878 [3]鹏城实验室量子计算中心,广东深圳518000 [4]福建农林大学计算机与信息学院,福州350002 [5]上海电力大学计算机科学与技术学院,上海200090 [6]武汉大学国家网络安全学院,武汉430072

出　　处：《计算机学报》2020年第9期1691-1707,共17页Chinese Journal of Computers

基　　金：“国防创新特区项目”;国家自然科学基金项目(61572304,61272096);国家自然科学基金重点项目(61332019);密码科学技术国家重点实验室开放课题基金资助.

摘　　要：通用量子计算机器件进展缓慢,对实用化1024-bit的RSA密码破译尚不能构成威胁,现代密码依旧是安全的.量子计算密码攻击需要探索新的途径:一是,量子计算能否协助/加速传统密码攻击模式,拓展已有量子计算的攻击能力;二是,需要寻找Shor算法之外的量子计算算法探索密码攻击.对已有的各类量子计算整数分解算法进行综述,分析量子计算密码攻击时面对的挑战,以及扩展至更大规模整数分解存在的问题.结合Shor算法改进过程,分析Shor算法对现代加密体系造成实质性威胁前遇到的困难并给出Shor破译2048位RSA需要的资源.分析基于D-Wave量子退火原理的RSA破译,这是一种新的量子计算公钥密码攻击算法,与Shor算法原理上有本质性不同.将破译RSA问题转换为组合优化问题,利用量子退火算法独特的量子隧穿效应跳出局部最优解逼近全局最优解,和经典算法相比有指数级加速的潜力.进一步阐述Grover量子搜索算法应用于椭圆曲线侧信道攻击,拓展其攻击能力.探讨量子人工智能算法对NTRU等后量子密码攻击的可能性.Due to the limitations of hardware,the development of universal quantum computer devices is slow.At present,the maximum integer factorization by general Shor’s algorithm is 85(using the characteristics of Fermat numbers to factor the integer 85 with 8 qubits),which is not a threat to the practical 1024-bit RSA by Shor’s algorithm.Since the universal quantum computer cannot be practical in a short time,the modern cryptography is still secure enough now.Quantum computing cryptography attack needs to explore new ways to enhance its quantum attacking ability:Firstly,whether quantum computing can assist/accelerate traditional cryptography attack mode and expand its more powerful quantum attacking ability on the basis of the existing quantum computing.Secondly,it is necessary to find quantum computing algorithms other than Shor’s algorithm to explore quantum computing cryptographic attack.In this paper,various existing algorithms for integer factorization algorithms of quantum computing are studied and show optimistic potentials of quantum annealing algorithm and D-Wave quantum computer for deciphering the RSA cryptosystem.Such as Shor’s algorithm(factor up to 85)via different platforms(like Hua-Wei quantum computing platform),quantum adiabatic computation via NMR(291311),D-Wave(purchased by Lockheed Martin and Google etc.,has been initially used for image processing,machine learning,combinatorial optimization,and software verification etc.)quantum computer(factored up to 376289),quantum computing software environment provided by D-Wave(factor the integer 1001677 with 87 qubits)to obtain a higher success rate and extend it to a larger factorization scale.Actually,D-Wave using quantum annealing may be closer to cracking practical RSA codes than a general-purpose quantum computer(IBM)using Shor’s algorithm.In addition,the model limitations and precision problems existing in the expansion of integer factorization to a larger scale are discussed.Majorities of scholars think Shor’s algorithm as the unique and po

关 键 词：量子计算 量子退火 量子计算密码 量子攻击 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]