基于0.1π旋转相位Grover算法的ECC电压毛刺攻击算法

doi:10.11959/j.issn.1000-436x.2017158

通信学报 ›› 2017, Vol. 38 ›› Issue (8): 1-8.doi: 10.11959/j.issn.1000-436x.2017158

• 学术论文 • 下一篇

基于0.1π旋转相位Grover算法的ECC电压毛刺攻击算法

王潮¹,曹琳¹,贾徽徽²,胡风¹

¹ 上海大学通信与信息工程学院特种光纤与光接入网重点实验室，上海 200072
² 公安部第三研究所，上海 200031

修回日期:2017-06-01 出版日期:2017-08-01 发布日期:2017-09-07
作者简介:王潮（1971-），男，江苏镇江人，博士，上海大学教授，主要研究方向为无线传感器网络、网络信息安全与椭圆曲线密码学、量子计算与量子攻击密码分析。|曹琳（1991-），女，山东临沂人，上海大学硕士生，主要研究方向为量子计算与量子攻击密码分析。|贾徽徽（1987-），男，山东临沂人，公安部第三研究所工程师，主要研究方向为网络与信息安全、智能卡安全、量子攻击密码分析。|胡风（1991-），男，浙江温州人，上海大学博士生，主要研究方向为信息安全、量子计算密码、社会网络。
基金资助:
国家自然科学基金资助项目(61572304);国家自然科学基金资助项目(61272096);国家自然科学基金资助项目(61332019)

ECC fault attack algorithm based on Grover's quantum search algorithm with 0.1π phase rotation

Chao WANG¹,Lin CAO¹,Hui-hui JIA²,Feng HU¹

¹ Key Lab of Specialty Fiber Optics and Optical Access Network，School of Communication and Information EngineeringShanghai University，Shanghai 200072，China
² The Third Research Institute of Ministry of Public Security，Shanghai 200031，China

Revised:2017-06-01 Online:2017-08-01 Published:2017-09-07
Supported by:
The Nationa1 Natura1 Science Foundation of China(61572304);The Nationa1 Natura1 Science Foundation of China(61272096);The Nationa1 Natura1 Science Foundation of China(61332019)

摘要/Abstract

摘要：

将Grover算法应用到对公钥密码的故障攻击中，提出一种基于固定相位旋转Grover量子算法，当旋转相位为0.1π时，仿真实验搜索成功率提高到99.23%。进一步与故障攻击结合，提出基于0.1π旋转相位Grover算法的椭圆曲线密码电压毛刺攻击算法，仿真实验以100%的概率攻击了NIST公布的Kob1itz安全曲线K-163，其计算复杂度呈指数级降低。这是除 Shor 算法之外量子计算对公钥密码的一种新的有效攻击途径，有助于拓展量子计算对其他公钥密码体制的攻击。

关键词: 量子搜索算法, Grover算法, 相位匹配, 量子计算, 电压毛刺攻击

Abstract:

The Grover's a1gorithm was used for fau1t attack against the pub1ic key cryptography.A fixed phase rotation based Grover's a1gorithm was proposed，and the probabi1ity of success achieved 99.23% with 0.1π phase rotation.Combined with the fau1t attack further，ECC（e11iptic curve cryptography）vo1tage burr attack a1gorithm based on Grover a1gorithm with 0.1π phase rotation was proposed.Then a safety Kob1itz curve，K-163，pub1ished successfu11y attacked by NIST on binary domain in simu1ation and the success rate was 100%.The comp1exity of the attack great1y reduces on the exponentia1.It was a new effective way，except the Shor's a1gorithm，to attack pub1ic key cryptography by quantum computing，and it contributed to extend the attack ways to the other pub1ic key cryptography.

Key words: quantum search a1gorithm, Grover's a1gorithm, phase matching, quantum computing, vo1tage burr attack

中图分类号:

TP309.7

王潮,曹琳,贾徽徽,胡风. 基于0.1π旋转相位Grover算法的ECC电压毛刺攻击算法[J]. 通信学报, 2017, 38(8): 1-8.

Chao WANG,Lin CAO,Hui-hui JIA,Feng HU. ECC fault attack algorithm based on Grover's quantum search algorithm with 0.1π phase rotation[J]. Journal on Communications, 2017, 38(8): 1-8.

图/表 9

图1

图2

图3

图4

图5

表1

4种Grover算法的性能指标对比"

性能指标	Grover算法（α=0.1π）	Younes固定相位算法（α=1.825π）	Younes局部扩散算法（α=0.5π）	经典Grover算法
$P_{\min}$	0.992 3	0.980 7	0.847 6	0.500 0
${(\frac{N}{N})}_{P = P_{\min}}$	0.511 8	0.514 1	0.307 9	0.500 0
$R_{\max}$	159	90	35	24

表1

图6

图7

表2

参考文献 22

[1]	ZHANG F , GUO S Z , ZHAO X J . A framework for the analysis and evaluation of algebraic fault attacks on lightweight block ciphers[J]. IEEE Transactions on Information Forensics and Security, 2016,11(5): 1039-1054.
[2]	ZHAO X J , GUO S , ZHANG F . Algebraic fault analysis on GOST for key recovery and reverse engineering[C]// 2014 Workshop on Fault Diagnosis and Tolerance in Cryptography(FDTC). 2014: 29-39.
[3]	BIHAM E , SHAMIR A . Differential fault analysis of secret key cryptosystem[J]. Springer Berlin Heidelberg, 1997,1294: 513-525.
[4]	BIEHL I , MEYER B , MULLER V . Differential fault attacks on elliptic curve cryptosystems[C]// CRYPTO 2000,LNCS 1880. 2000: 131-146.
[5]	DOMINGUE-VIEDO A , HASAN MA , ANSARI B . Fault-based attack on Montgomery′s ladder ECSM algorithm[J]. Journal of Cryptology, 2011,24(2): 346-374.
[6]	赵彦光, 白国强, 陈弘毅 ,等. ECC专用密码芯片的功耗分析研究[J]. 计算机工程与应用, 2006,42(16): 25-28.
	ZHAO Y G , BAI G Q , CHEN H Y ,et al. Study of power analysis attack to ECC in ASIC chip[J]. Computer Engineering and Applications, 2006,42(16): 25-28.
[7]	张金中, 寇应展, 王韬 ,等. 针对滑动窗口算法的椭圆曲线密码故障分析[J]. 通信学报, 2012,33(1): 71-78
	ZHANG J Z , KOU Y Z , WANG T ,et al. Fault analysis on elliptic curve cryptosystems with sliding window method[J]. Journal on Communications, 2012,33(1): 71-78.
[8]	王潮, 王云江, 胡风 . 量子计算机的商业化进展以及对信息安全的挑战[J]. 网络与信息安全学报, 2016,2(3): 17-27.
	WANG C , WANG Y J , HU F . Shaping the fature of commercial quantum computer and the challenge for information security[J]. Chinese Journal Network and Information Security, 2016,2(3): 17-27.
[9]	陈宇航, 贾徽徽, 姜丽莹 . 基于Grover算法的ECC扫描式攻击[J]. 信息网络安全, 2016(2): 28-32.
	CHEN Y H , JIA H H , JIANG L Y . ECC scanning attack based on Grover algorithm[J]. Net Info Security, 2016(2): 28-32.
[10]	BIHAM E , BIHAM O . Grover's quantum search algorithm for an arbitrary initial amplitude distribution[J]. Physical Review A, 1999,60(4): 2742-2745.
[11]	BIHAM E , BIHAM O . Analysis of generalized Grover quantum search algorithms using recursion equations[J]. Physical Review A, 2001,63(1): 5348-5353.
[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]// The 41st IEEE International Symposium on Multiple-Valued Logic. 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(042305): 1-5.
[16]	LONG G L , LI Y S , XIAO L . Phase matching in quantum searching and the improved Grover algorithm[J]. Nuclear Physics Review, 2004,21(2): 114-116.
[17]	LI P C , LI S Y . Phase matching in Grover's algorithm[J]. Physics Letters A, 2007,366(1-2): 42-46.
[18]	YOUNES A , ROWE J , MILLER J . Quantum search algorithm with more reliable behaviour using partial diffusion[C]// The 7th International Conference on Quantum Communication,Measurement and Computing. 2004.
[19]	GROVER L K . Quantum mechanics helps in searching for a needle in a haystack[J]. Physical Review Letters, 1997,79(2): 325-328.
[20]	GROVER L K , . A fast quantum mechanical algorithm for database search[C]// The 28th Annual ACM Symposium on the Theory of Computing. 1996: 212-219.
[21]	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.
[22]	LONG G L , LI Y S , ZHANG W L . Phase matching in quantum searching[J]. Physics Letters A, 1999,262(1): 27-34.

功击类型	复杂度
功击类型	m=8	m=16	m=32	m=64
原电压毛刺攻击	O（2¹²）	O（2¹⁹）	O（2³⁴）	O（2⁶⁵）
加入Grover算法	O（5× 2⁸）	O（5× 2¹¹）	O（5× 2¹⁸）	O（5× 2³³）

基于0.1π旋转相位Grover算法的ECC电压毛刺攻击算法

ECC fault attack algorithm based on Grover's quantum search algorithm with 0.1π phase rotation

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 22

相关文章 2

Metrics

推荐阅读 0

[1]	杜小妮, 王香玉, 梁丽芳, 李锴彬. 轻量级分组密码Piccolo的量子密码分析[J]. 通信学报, 2023, 44(6): 175-182.
[2]	王后珍, 蔡鑫伟, 郭岩, 张焕国. 基于矩阵填充问题的五轮零知识身份认证方案[J]. 通信学报, 2021, 42(11): 79-86.