基于Grover量子中间相遇搜索算法的ECC攻击错误bit的修正

doi:10.3969/j.issn.1671-1122.2016.06.005

信息网络安全 ›› 2016, Vol. 16 ›› Issue (6): 28-34.doi: 10.3969/j.issn.1671-1122.2016.06.005

基于Grover量子中间相遇搜索算法的ECC攻击错误bit的修正

贾徽徽¹, 王潮^2,³(), 顾健¹, 陆臻¹

1. 公安部第三研究所检测中心,上海 200031
2. 上海大学特种光纤与光接入网省部共建教育部重点实验室,上海 200072
3. 天普大学计算机与信息科学系,美国费城 19019

收稿日期:2016-05-17 出版日期:2016-06-20 发布日期:2020-05-13
作者简介:
作者简介：贾徽徽（1987—）,男,山东,工程师,硕士,主要研究方向为网络与信息安全、智能卡安全、量子攻击密码分析;王潮（1971—）,男,江苏,教授,博士,主要研究方向为无线传感器网络、网络信息安全与椭圆曲线密码学、量子计算与量子攻击密码分析;顾健（1963—）,男,江苏,研究员,博士,主要研究方向为网络与信息安全、智能卡安全;陆臻（1976—）,男,浙江,副研究员,硕士,主要研究方向为网络信息安全、云安全与智能卡安全。
基金资助:
国家自然科学基金重点项目[61332019];国家自然科学基金[61572304,61272096,60970006];上海市教委创新基金重点项目[14ZZ089]

Error Bit Correction of ECC Attack Based on Grover Quantum Intermediate Encounter Search Algorithm

Huihui JIA¹, Chao WANG^2,³(), Jian GU¹, Zhen LU¹

1. Testing Center of the Third Research Institute of Ministry of Public Security, Shanghai 200031, China
2. Key Laboratory of Special Fiber Optics and Optical Access Networks, Ministry of Education (SCIE), Shanghai University, Shanghai 200072, China
3. Department of Computer & Information Science, Temple University,Philadelphia 19019, USA

Received:2016-05-17 Online:2016-06-20 Published:2020-05-13

摘要/Abstract

摘要：

在现有的针对ECC的侧信道攻击中,密钥出现错误bit难以避免,且无法快速修正。文章将Grover量子搜索算法和中间相遇攻击相结合,提出了一种新的搜索算法——Grover量子中间相遇搜索算法,并将其应用于针对ECC的侧信道攻击中。该算法可以在O( $N / M$ )步修正规模为N且存在M个错误bit的密钥,与传统搜索算法的计算复杂度O(N^M⁺¹)相比较,计算复杂度大幅度降低。通过对算法进行分析表明,该方法能够以成功率1修正ECC攻击中出现的错误bit。

关键词: 椭圆曲线密码, 侧信道攻击, Grover算法, 量子中间相遇搜索算法

Abstract:

The existing error bit in the side channel attacks of ECC is difficult to avoid, and can’t be modified quickly. In this paper, a new search algorithm based on the Grover quantum search algorithm is proposed, which combines the Grover quantum search algorithm and the meet in the middle attack, and applies it to the side channel attack for ECC. The algorithm can solve the key problem of n which has M error bit in O( $N / M$ ) steps. Compared with classical search algorithm, the computational complexity is greatly reduced. The analysis said that the success rate of modifying ECC attack error bit is 1, and the algorithm can effectively reduce the computational complexity.

Key words: elliptic curve cryptography(ECC), side channel attack, Grover algorithm, quantum intermediate encounter search algorithm

中图分类号:

TP309

贾徽徽, 王潮, 顾健, 陆臻. 基于Grover量子中间相遇搜索算法的ECC攻击错误bit的修正[J]. 信息网络安全, 2016, 16(6): 28-34.

Huihui JIA, Chao WANG, Jian GU, Zhen LU. Error Bit Correction of ECC Attack Based on Grover Quantum Intermediate Encounter Search Algorithm[J]. Netinfo Security, 2016, 16(6): 28-34.

图/表 2

参考文献 23

[1]	MILLER V S.Use of Elliptic Curves in Cryptography[C]//International Association for Cryptologic Research (IACR). Advances in Cryptology-CRYPTO’85 Proceedings, August 18-22, 1985, Santa Barbara, California, USA. Berlin: Springer, 1986: 417-426.
[2]	DIFFIE W, HELLMAN M E.Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard[J]. Computer, 1977, 10(6): 74-84.
[3]	MERKLE R, HELLMAN M E.On the Security of Multiple Encryption[J]. Communications of the Acm, 1981, 24(7): 465-467
[4]	FEYNMAN R P.Quantum Mechanical Compute[J]. Foundations of Physics, 1986, 16(6): 507-531.
[5]	DEUTSCH D.Quantum Theory: the Church. Turing Principle and Universal Quantum Computer[J].Proceedings of the Royal Society A Mathematical Physical & Engineering Sciences, 1985,400(1818): 97-117.
[6]	SHOR P W.Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[J]. Quantum Entanglement & Quantum Information-ccast Workshop, 1999, 26(5): 1484-1509.
[7]	GROVER L K.A Fast Quantum Mechanical Algorithm for Database Search[C]//Association for Computing Machinery (ACM).The 28th ACM Symposium on Theory of Computation, May 29, 1996, Philadelphia, PA, USA. New York: ACM, 1996: 212-219.
[8]	钟普查,鲍皖苏. 三重DES的量子中间相遇搜索算法[J]. 科学通报,2009,54(19):3003-3007.
[9]	BIHAM E, BIHAM O.Grover’s Quantum Search Algorithm for an Arbitrary Initial Amplitude Distribution[J]. Physical Review A, 1999, 60(4): 2742-2745.
[10]	BIHAM E, BIHAM O.Analysis of Generalized Grover Quantum Search Algorithms Using Recursion Equations[J]. Physical Review A, 2001, 63(1): 5348-5353.
[11]	BULGER D, BAEITOMPA W P, WOOD G R.Implementing Pure Adaptive Search with Grover’s Quantum Algorithm[J]. Journal of Optimization Theory and Applications, 2003, 116(3): 517-529.
[12]	GROVER J K.Fixed-point Quantum Search[J]. Physical Review Letters, 2005, 95(15): 1-4.
[13]	YOUNES A.Fixed Phase Quantum Search Algorithm[J]. Applied Mathematics & Informationences, 2007, 7(1): 93-98.
[14]	DHAWAN S, PERKOWSKI M.Comparison of Influence of Two Data-encoding Methods for Grover Algorithm on Quantum Costs[C]//IEEE. 41st IEEE International Symposium on Multiple-Valued Logic, May 23-25, 2011, Tuusula, Finland. New Jersey: IEEE, 2011: 176-181.
[15]	LONG G L, LI Y S, ZHANG W L.Dominant Gate Imperfection in Grover’s Quantum Search Algorithm[J]. Physical Review A, 2000, 61(4): 042-305.
[16]	LONG Guilu, LI Yansong, XIAO Li, et al.Phase Matching in Quantum Searching and the Improved Grover Algorithm[J]. Nuclear Physics Review, 2004, 21(2):114-116.
[17]	HAO Liang, LIU Dan, LONG Guilu.An N/4 Fixed-point Duality Quantum Search Algorithm[J]. Science China, 2010, 53(9): 1765-1768.
[18]	仲明,贾徽徽,姜丽莹,等. 基于量子退火算法的DPA防御系统优化[J]. 信息网络安全,2016(2):28-33.
[19]	PAGE D.Theoretical use of Cache Memory as a Cryptanalytic Side-channel[J]. Journal of Arid Envrionments, 2002, 2002(10): 393-446.
[20]	KOCHER P, JAFFE J, JUN B.Differential Power Analysis[C]//International Association for Cryptologic Research (IACR) .19th Annual International Cryptology Conference Santa Barbara, August 15-19, 1999, California, USA. Heidelberg: Springer, 1999: 388-397.
[21]	石军. 电磁泄漏耦合发射的应用研究[J]. 信息网络安全,2015(9):101-105.
[22]	BRUMLEY B B, HAKALA R M.Cache-Timing Template Attacks[C]//International Association for Cryptologic Research (IACR). 15th International Conference on the Theory and Application of Cryptology and Information Security, December 6-10, 2009, Tokyo, Japan. Heidelberg: Springer, 1999: 667-684.
[23]	陈宇航,贾徽徽,姜丽莹,等. 基于Grover算法的ECC扫描式攻击[J]. 信息网络安全,2016(2):28-32.

基于Grover量子中间相遇搜索算法的ECC攻击错误bit的修正

Error Bit Correction of ECC Attack Based on Grover Quantum Intermediate Encounter Search Algorithm

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 23

相关文章 11

编辑推荐

Metrics

本文评价

[1]	韦永霜, 陈建华, 韦永美. 基于椭圆曲线密码的RFID/NFC安全认证协议[J]. 信息网络安全, 2019, 19(12): 64-71.
[2]	张良峰, 汪毅, 吴源燚, 孔睿. 基于统计的浏览器指纹采集技术[J]. 信息网络安全, 2019, 19(11): 49-55.
[3]	周志彬, 张少波, 罗恩韬, 李超良. 一种无可信第三方的批量RFID所有权转移协议[J]. 信息网络安全, 2018, 18(6): 18-27.
[4]	张小红, 郭焰辉. 基于椭圆曲线密码的RFID系统安全认证协议研究[J]. 信息网络安全, 2018, 18(10): 51-61.
[5]	王庆, 屠晨阳, shenjiahui@iie.ac.cn. 侧信道攻击通用框架设计及应用[J]. 信息网络安全, 2017, 17(5): 57-62.
[6]	张言胜, 汪学明, 仇各各. 一种新的动态门限数字签名方案研究[J]. 信息网络安全, 2016, 16(6): 62-67.
[7]	陈宇航, 贾徽徽, 姜丽莹, 王潮. 基于Grover算法的ECC扫描式攻击[J]. 信息网络安全, 2016, 16(2): 28-32.
[8]	李明;王赛;李亮;严文涛. 边信道攻击防范措施的研究[J]. , 2013, 13(Z): 0-0.
[9]	秦文仙;王琼宵;高能;王跃武. 对SIP认证协议的安全性分析与改进[J]. , 2013, 13(10): 0-0.
[10]	黄世中;羊红光. NAF编码方法的分析与应用[J]. , 2012, 12(5): 0-0.
[11]	向永谦;陈建华. 一种基于身份的三方认证密钥交换协议[J]. , 2012, 12(11): 0-0.