基于Grover算法的ECC扫描式攻击

doi:10.3969/j.issn.1671-1122.2016.02.005

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

基于Grover算法的ECC扫描式攻击

陈宇航¹, 贾徽徽², 姜丽莹¹, 王潮^1,³()

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

收稿日期:2016-01-14 出版日期:2016-02-10 发布日期:2020-05-13
作者简介:
作者简介：陈宇航（1991—）,男,浙江,硕士研究生,主要研究方向为量子算法与密码学;贾徽徽（1987—）,男,上海,硕士,主要研究方向为网络与信息安全、云安全、智能卡安全;姜丽莹（1988—）,女,河北,硕士研究生,主要研究方向为量子算法与密码学;王潮（1971—）,男,山东,教授,博士,主要研究方向为无线传感器网络、网络信息安全与椭圆曲线密码学、量子计算与量子攻击密码分析。
基金资助:
国家自然科学基金重点项目[61332019];国家自然科学基金[61572304,61272096,60970006];上海市教委创新基金重点项目[14ZZ089];上海市特种光纤与光接入网重点实验室开放课题[SKLSFO2014-06]

ECC Scanning Attack Based on Grover Algorithm

Yuhang CHEN¹, Huihui JIA², Liying JIANG¹, Chao WANG^1,³()

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

Received:2016-01-14 Online:2016-02-10 Published:2020-05-13

摘要/Abstract

摘要：

相对于传统的RSA等公钥密码,ECC具有密钥长度短,计算复杂度高等特点,因此针对ECC加密体制的攻击复杂度高、难度大。研究针对ECC公钥密码的攻击方法有利于提前完善和防止不必要的损失。Grover算法作为一种量子搜索算法,将搜索步数从经典算法的N缩小到 $N$ ,实现了对经典搜索算法的二次方加速作用,能更快速地寻找所需的解。扫描式攻击作为一种新生的侧信道攻击技术,它的出现给当前密码系统的安全性带来了极大的威胁。文章利用量子Grover搜索算法的快速搜索优点,对Rynuta提出的针对ECC密码芯片的扫描式攻击进行了改进,提出了基于Grover算法的ECC扫描式攻击方法。该算法对于密钥长度为N的ECC,计算复杂度由2^N降低到2N^3/2,进一步提高了破解效率。由于Grover搜索算法的确定性,该算法的攻击成功率为100%。

关键词: ECC扫描式攻击, Grover算法, 椭圆曲线密码, 侧信道攻击, 计算复杂度

Abstract:

Compared with the traditional public key cryptography such as RSA, ECC has a shorter key length but a higher computational complexity. So the attack against ECC encryption system is much harder. Research on the attacks to ECC public key cryptography is in favor of improving and preventing nonessential losses. Grover’s algorithm as a quantum search algorithm, which makes the number of steps of the search of the problem from the classic algorithm of N reduced to $N$ . It realized the secondary acceleration to classical algorithm. It can more quickly find the solutions. Meanwhile, scanning attack, which is a new side channel attack techniques, brings great threat to the current cryptographic system. Utilizing the advantages of the quantum Grover search algorithm, we improve the scanning attack on ECC, and then propose a new scanning attack on ECC which based on the Grover algorithm. For the ECC key length of N, the computational complexity is reduced from 2^N to 2N^3/2, furthering improve the efficiency of the cracks. Because of the determinate of Grover algorithm, the algorithm can success attack the cryptographic algorithms with the success rate of 100%.

Key words: ECC scanning attack, Grover algorithm, ECC, side channel attack, computation complexity

中图分类号:

TP309

陈宇航, 贾徽徽, 姜丽莹, 王潮. 基于Grover算法的ECC扫描式攻击[J]. 信息网络安全, 2016, 16(2): 28-32.

Yuhang CHEN, Huihui JIA, Liying JIANG, Chao WANG. ECC Scanning Attack Based on Grover Algorithm[J]. Netinfo Security, 2016, 16(2): 28-32.

图/表 2

参考文献 19

[1]	KOBLITZ N.Elliptic Curve Cryptosystems[J]. Mathematics of Computing American Mathematical Society, 1987(48): 203-309.
[2]	MILLER V S.Use of Elliptic Curves in Cryptography[C]//International Association for Cryptologic Research (IACR). Advances in Cryptology-CRYPTO’85, August 18-22, 1985, Santa Barbara, California, USA. Berlin: Springer, 1986: 417-426.
[3]	侯玉灵,卞阳东,胡广跃,等. 星际骨干网的轻量级密码体制研究[J]. 信息网络安全,2015(2):33-39.
[4]	QUISQUATER J J, SAMYDE D. ElectromagneticAnalysis (EMA): Measures and Counter Measures for Smart Cards[C]//The Java Card Forum, Eurosmart and INRIA. Smart Card Programming and Security, International Conference on Research in Smart Cards, E-smart 2001, September 19-21, 2001, Cannes, France. Berlin: Springer, 2001: 200-210.
[5]	王敏,饶金涛,吴震,等. SM4密码算法的频域能量分析攻击[J]. 信息网络安全,2015(8):14-19.
[6]	PADE D. Theoretical Use of Cache Memory as a Cryptanalytic Side-channel[R]. Bristol: Department of Computer Science, University of Bristol, Technical Report CSTR-02-003, 2002.
[7]	赵新杰,郭世泽,王韬. 针对AES和CLEFIA的改进Cache踪迹驱动攻击[J]. 通信学报,2011,32(8):101-110.
[8]	陈福臻,程久军,廖竞学,等. 基于网络编码的同态HASH抗污染攻击系统研究[J]. 信息网络安全,2015(6):33-40.
[9]	张金中,寇应展,王韬. 针对滑动窗口算法的椭圆曲线密码故障分析[J]. 通信学报,2012,33(1):71-78.
[10]	YANG Bo, WU Kaijie, KARRI R.Scan-based Side-Channel Attack on Dedicated Hardware Implementations of Data Encryption Standard[C]//IEEE. International Test Conference, October 26-28, 2004, Charlotte, NC, USA. New Jersey: IEEE, 2004: 339-344.
[11]	NARA R, TOGAWA N, YANAGISAWA M, et al.Scan-based Attack for an AES-LSI Included with Other IPs[J]. Ieice Technical Report Dependable Computing, 2008, 108(298): 49-53.
[12]	NARA R, TOGAWA N, YANAGISAWA M, et al.Scan-Based Attack Against Elliptic Curve Cryptosystems[C]//IEEE. The 2010 15th Asia and South Pacific Design Automation Conference, January 18-21, 2010, Taipei. New Jersey: IEEE, 2010: 407-412.
[13]	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.
[14]	GROVER L K.A Fast Quantum Mechanics Algorithm for Database Search[C]//Association for Computing Machinery (ACM). The 28th ACM Symposium on Theory of Computation. 1996, Philadelphia, PA, USA. New York: ACM Press, 1996: 212-219.
[15]	钟普查,鲍皖苏. 三重DES的量子中间相遇搜索算法[J]. 科学通报,2009,54(19):3003-3007.
[16]	叶峰,袁家斌. AES加密算法的密钥搜索量子线路的设计[J]. 西南交通大学学报,2010,45(2):302-306.
[17]	LONG Guilu.Grover Algorithm with Zero Theoretical Failure Rate[J]. Physical Review A, 2001, 64(2): 436-454.
[18]	龙桂鲁,李岩松,肖丽,等. Grover 量子搜索算法及改进[J]. 原子核物理评论,2004,21(2):114-116.
[19]	王勇. 新型数学难题及其在分组密码中的应用研究[J]. 信息网络安全,2014(11):79-82.

基于Grover算法的ECC扫描式攻击

ECC Scanning Attack Based on Grover Algorithm

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 19

相关文章 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]	贾徽徽, 王潮, 顾健, 陆臻. 基于Grover量子中间相遇搜索算法的ECC攻击错误bit的修正[J]. 信息网络安全, 2016, 16(6): 28-34.
[7]	张言胜, 汪学明, 仇各各. 一种新的动态门限数字签名方案研究[J]. 信息网络安全, 2016, 16(6): 62-67.
[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.