![点击分享此内容可以赚币 分享](/master/images/share_but.png)
基于量子Simon算法对分组密码类EM结构的密钥恢复攻击.pdf
《基于量子Simon算法对分组密码类EM结构的密钥恢复攻击.pdf》由会员分享,可在线阅读,更多相关《基于量子Simon算法对分组密码类EM结构的密钥恢复攻击.pdf(7页珍藏版)》请在咨信网上搜索。
1、NETINFOSECURITY理论研究doi:10.3969/j.issn.1671-1122.2024.01.0102024年第1期基于量子 Simon算法对分组密码类EM结构的密钥恢复攻击张兴兰,郭艳琨,陈菲,张丰,(北京工业大学信息学部,北京10 0 0 2 0)摘要:文章基于量子Simon算法(一类经典量子周期寻找算法)的量子过程以及应用,对类EM结构进行基于量子Simon算法的密码分析,以类EM结构的加密算法为研究对象,运用量子Simon算法,构造适用于Simon算法的函数,对类EM加密结构的5轮加密过程进行密钥恢复攻击。结果显示,在密钥长度的多项式时间内,文章所提方法可以成功恢复出
2、第五轮加密密钥,且根据此密钥可以分析出其他轮密钥。研究结果表明,在密钥长度的多项式时间内,可以找到其中一个密钥,量子条件下密钥的可恢复性说明该结构的安全轮数应当高于5轮,为未来对称密码体制的研究和发展奠定了一定的基础。关键词:量子;分组密码;Simon算法;密钥恢复攻击中图分类号:TP309文献标志码:A文章编号:16 7 1-112 2(2 0 2 4)0 1-0 10 6-0 7中文引用格式:张兴兰,郭艳琨,陈菲,等.基于量子Simon算法对分组密码类EM结构的密钥恢复攻击.信息网络安全,2 0 2 4,2 4(1):10 6-112.英文引用格式:ZHANG Xinglan,GUO Ya
3、nkun,CHEN Fei,et al.Key Recovery Attacks on Block CipherEM-Like Structures Based on Quantum Simons AlgorithmJJ.Netinfo Security,2024,24(1):106-112.Key Recovery Attacks on Block Cipher EM-Like Structures Based onQuantum Simons AlgorithmZHANG Xinglan,GUO Yankun,CHEN Fei,ZHANG Feng(Faculty of Informati
4、on Technology,Beijing University of Technology,Beijing 100020,China)Abstract:This paper studied the quantum process of Quantum Simons algorithm(one of classical quantum cycle finding algorithms)as well as its applications,and conductscryptanalysis based on quantum Simon algorithm on EM-like structur
5、es,takes the encryptionalgorithm of EM-like structures as the object of research,applies quantum Simon algorithm,constructs the function applicable to Simon algorithm,and performs the key recovery收稿日期:2 0 2 3-0 6-2 5基金项目:北京市自然科学基金42 12 0 15作者简介:张兴兰(197 0 一),女,山西,教授,博士,主要研究方向为密码和量子计算;郭艳琨(1998 一),女,天津
6、,硕士研究生,主要研究方向为对称密码和量子计算;陈菲(1999一),女,北京,硕士研究生,主要研究方向为量子密码;张丰(1998 一),男,江西,硕士研究生,主要研究方向为量子机器学习。通信作者:郭艳琨dimple_106NETINFOSECURITY2024年第1期理论研究attack on the 5-round encryption process of the encrypted structure of EM-like structures.The results show that the fifth round of encryption key can be successfu
7、lly recovered inpolynomial time of the key length,and other keys can be analyzed based on this key.The keyrecovery indicates that the quantum version of the structure is insecure,i.e.,one of the keyscan be found at polynomial time of the key length.It provides some basis for future researchand devel
8、opment of symmetric cryptosystems.Key words:quantum;block cipher;Simons algorithm;key recovery attack0引言Shor算法表明,如果可伸缩的量子计算机可用,那么许多广泛使用的非对称密码系统将被打破,如Rivest-ShamirA d l e m a n(RSA)公钥密码系统。这引发了后量子密码学研究热潮。为了应对量子计算的威胁,美国国家标准与技术研究院(National InstituteofStandards and Technology,NIST)启动了对后量子公钥算法的标准化过程2。目前量子
9、信息处理已深刻改变了经典密码学的模式,特别地,所有基于整数分解和离散对数的密码系统对于量子计算机来说都是不安全的。关于公钥密码学,后量子密码学正在研究许多不同的方法,如基于格问题、编码问题和椭圆曲线同源等问题的密码学。这些方法旨在在量子计算机也难以解决的问题上建立公钥加密机制。对称密码也面临量子攻击的威胁。量子计算机可以为某些信息处理任务加速,如穷举搜索和碰撞搜索,有助于对对称密码系统进行密码分析。使用Grover算法3,一般的穷举搜索攻击可以获得二次加速4。由于对称密码的安全性由轮数和密钥长度保证,因此,如果量子算法在穷举搜索密钥过程中进行二次加速,那么理论上在后量子世界中对称密码的密钥长度
10、需要加倍,才能获得等效的安全性。虽然Grover算法只提供二次加速,但量子算法已经可以有效攻击一些已被证明是安全的、可以对抗经典对手的对称系统。近年来,研究者们在量子计算对对称密码学在安全性方面的影响的研究取得了一些进展5-9,也有一些学者在前人研究的基础上进行了进一步的研究10-14。例如,KAPLAN5等人和XIE6等人分别提出了一种基于传统差分和线性密码分析的量子分析方案,促进了量子密码学分析领域的发展。MALVIYA!等人综合当前的研究进展进行了概述分析。Simon算法10 I 是量子算法理论的核心之一,同时,Simon算法也应用于对称密码学。例如,KUWAKADO8等人使用Simon
11、算法构造了Fesitel方案的三轮区分器,它已被证明是一种安全的伪随机排列。他们还使用Simon算法提取了Even-Mansour密码8 的私钥。后来,SANTOLI1I等人和MALVIYAI等人独立地扩展了他们的结果,并将Simon算法应用于其他对称原语,如GaloisGMAC和CLOC。D O NG 15等人基于文献8 提出的量子区分器对任意轮的Feistel方案进行量子密钥恢复攻击。除攻击特定的对称原语外,量子算法还被用于传统的密码分析工具中。KAPLAN16等人将Grover算法应用于线性密码分析和差分密码分析的几种变体。2 0 15年,LEVERRIER17等人在差分攻击中使用Gro
12、ver算法,得到二次加速度。XIE4等人研究了量子差分攻击,并利用BermsteinVazirani(BV)算法18 寻找高概率差分19。KAPLAN201先结合量子算法与传统的密码分析方法中间相遇攻击给出一个量化版本的中间相遇攻击,再证明它是较优使用广义对手的方法,表明结合量子攻击比传统的量子攻击有更好的结果。目前,对对称密码系统的量子攻击主要是基于Grover算法、Simon算法和BermsteinVazirani(BV)算法。大多数块密码都是迭代块密码,即通过轮函数和轮数共同保证迭代块密码的安全性。轮函数中常用一种替换置换设计结构(SubstitutionPermutation),在著名
13、的高级加密标准(Advanced Encryption Standard,A ES)密码设计中使用。其中较原始的密码方案是SHIMON21等人提出的Even-Mansour密码结构。Even-Mansour密码系统具有107NETINFOSECURITY理论研究2024年第1期简单的结构和防止破解和伪造攻击的安全下限证明。因此,这种结构经常被用作块密码设计的基本组成部分。Even-Mansour系统是近年来块密码的普遍研究热点,关键密码学会议上许多论文都与EM结构相关2 2。综上所述,利用量子算法对Even-Mansour结构进行分析已取得了一些结果,为未来的密码分析提供了基础。本文研究了通过
14、变换Even-Mansour结构得到的密码系统,即类似EM的结构,该结构具有软硬件实现简单、计算速度快、能抵抗差分攻击和线性攻击的优点。因此,对该结构的密码分析具有现实意义。本文通过Simon算法对类EM结构的5轮加密过程进行密钥恢复攻击:第一章介绍了Simon算法的原理和该算法所解决的问题;第二章介绍了类EM结构的加密方法,并使用Simon算法对该结构进行了攻击,给出了攻击所用的量子电路以及攻击效果和可行性;第三章进行了该密码攻击的复杂度分析。1 Simon 算法1.1Simon问题和算法Simon算法是一种量子算法,它可以用于求解经典计算难题“黑箱问题”,即给定一个函数,要求找出这个函数的
15、性质。Simon算法可以在多项式时间内解决这个问题,而经典计算机需要指数时间才能求解。KAPLAN16等人对Simon问题以及求解它的量子算法进行了描述,假设了解量子电路模型的基本知识,分别使用“”和“”表示一个具有2 个元素的域的加法和乘法。Simon问题的输入是函数f,可以通过查询得到。一个经典的oracle是函数xf(x),需要通过量子力学的方式查询函数f,来运行Simon算法。更准确地说,在后续计算中,可以假设该算法可以对)形式的量子叠加进行任意的查询。Simon问题的内容如下:对于一个布尔函数f:(0,1(0,1),该函数满足存在一个串se(0,,使得f(x)=f(y)-xy e 0
16、 ,s)对于任意(x,)e0,1)成立,目标是找到s。这个问题通常可以通过搜索碰撞来解决,传统算法解决它的最佳时间是(2 /2),而Simon算法用量子复杂度O(n)解决了这个问题。该算法重复以下5个量子步骤:1)准备2 n个量子位的状态0 0 ,对第一个寄存器应用Hadamard变换Hn得到量子叠加Zx)0);2)将函数f的量子查询映V2 xe(0,1射到上一步得到的状态上,得到在计算基础中测量第二个寄存器会产生一个f(2),并将第一个寄存器塌缩到以下状态-(Iz)+zs);4)V2再次将Hadamard变换H应用到第一个寄存器得到11=(-1)(1+(-1)y ;5)使y-s=l 的向量J
17、,振幅为0,因此,在计算基上测量状态得到一个使yS=O随机向量y。通过重复这个子程序O(n)次,得到n个与s正交的独立向量,s可以用基本线性代数来恢复。1.2处理不必要的碰撞在密码分析过程中,Simon问题的承诺并不总是能够得到完全的满足。更准确地说,通过构造,总是存在一个s,对于任何输人x,满足f(x)=f(xs),但可能存在比这种形式更多的碰撞。如果这种不必要的碰撞数量太多,在O(n)次查询后,人们可能无法从Simon的子例程中得到一个完整的秩线性方程组。对于f:0,1)0,1)对所有 x满足f(xs)=(x),考这个参数量化了该函数离满足Simon的承诺有多远,对于一个随机函数,本文期望
18、c(f,s)=(n2)。KAPLANl6等人给出了定理,显示不必要的碰撞对Simon算法成功概率的影响。前提是f对于某些t0,s没有太多f(x)=f(xt)形式的碰撞。2使用Simon算法对类EM结构的密钥恢复攻击量子Simon算法可以在线性时间内,对于给定函数f(x)=f(xs)求出周期s,给对称密码的后续研究提供了思路和基础。本章将针对5轮类EM结构,基于已知明文攻击构造适用于量子Simon算法的周期函Z.Ix)/f(x);3)V2xe(0,1)108NETINFOSECURITY2024年第1期理论研究数,并使用该算法进行密钥恢复攻击。同时,介绍类EM结构、攻击策略需要使用的经典攻击和具
19、体的攻击策略。2.1已知明文攻击研究密码算法的理论安全性往往基于Kerckhoffs假设,即密码分析中,除了密钥以外,密码分析者知道密码算法的每一个设计细节。根据Kerckhoffs假设可知,密码算法的安全性依赖于密钥的保密性,而不是算法本身的保密性。在密码体制的基本模型中,密码分析者的任务就是获取适量的明文及其相应的密文,分析这些明文和密文得到密钥消息。本文使用的攻击方法为已知明文攻击,即攻击者掌握了某段明文和对应的密文。而已知明文攻击也假设攻击者能够获取部分明文和相应密文,如截取信息前段,该类型攻击获取加密的方式更有助于破解后段密文。由于本次基于量子Simon算法的密钥恢复攻击,只需知道明
20、文以及对应的密文,不依赖特定的、具有特殊结构的明密文对,因此已知明文攻击可以满足本次攻击的要求。本次攻击没有使用对明密文要求更高的选择明文攻击和选择密文攻击,说明量子计算对密码分析提供了更快更好的方法。2.2类EM结构Even-Mansour结构是AES的主要构成结构,类EM结构是基于该结构进行变形得到的,具有软硬件实现简单、计算速度快、能抵抗差分攻击和线性攻击的优点。该结构的加密流程是将明文分为4组,进行32 轮加密后,再通过一次反序变换得到最终密文。轮函数借鉴了AES加密算法中的S盒(Substitution-Box),并加人线性变换,有较好的抵御经典攻击的效果,具体如下。128bit的明
21、文被分为4个32 bit的字,记为(Xo,X1,X2,X),密文也被分为4个字,记为(Yo,Y,Y,Y),假设32bit的中间变量为X,4i35,则加密流程如下:1)Xi+4=F(Xi,Xi+1,Xi+2,Xi+3,rk)=X,T(Xi+I Xi+2 Xi+3 rk),i=0,1,31;2)(Yo,Y,Y2,Y)=R(X32,X33,X34,X3s)=(X35,X34,X33,X32)。其中,F是轮函数,T是合成置换(包括由S盒组成的非线性变换以及线性变换L),r k;是第i+1轮轮密钥,R是反序变换。2.3攻击策略本节将对5轮类EM密码结构进行密钥恢复攻击,首先构造适用于Simon算法的Si
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 量子 Simon 算法 分组 密码 EM 结构 密钥 恢复 攻击
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。