![点击分享此内容可以赚币 分享](/master/images/share_but.png)
对称密码体制的量子攻击.pdf
《对称密码体制的量子攻击.pdf》由会员分享,可在线阅读,更多相关《对称密码体制的量子攻击.pdf(14页珍藏版)》请在咨信网上搜索。
1、第42卷 第1期2024年1月应用科学学报JOURNAL OF APPLIED SCIENCESElectronics and Information EngineeringVol.42 No.1Jan.2024DOI:10.3969/j.issn.0255-8297.2024.01.004对称密码体制的量子攻击冯晓宁,吴洪宇哈尔滨工程大学 计算机科学与技术学院,黑龙江 哈尔滨 150001摘摘摘要要要:该文梳理了近年来量子攻击在对称密码体制的研究脉络,分析了主流攻击方法的研究趋势与各文献之间的关系,并将主流攻击方法分为量子周期攻击、Grover 算法相关攻击、量子差分攻击 3 类,分别介绍了
2、具有代表性的攻击方法,呈现了各攻击方法的核心思想。立足于现有的攻击方案,展望了这一领域可能会出现的热门研究方向。关键词:密码分析;量子算法;对称密码体制;量子攻击中图分类号:TP309文章编号:0255-8297(2024)01-0039-14Quantum Attacks on Symmetric CryptosystemsFENG Xiaoning,WU HongyuCollege of Computer Science and Technology,Harbin Engineering University,Harbin 150001,Heilongjiang,ChinaAbstract
3、:This paper undertakes an investigation of recent research trends in quantumattacks on symmetric encryption schemes,offering an analysis of the connections betweenmainstream attack methods and various literature sources.Mainstream attack methodsare systematically categorized into three types:quantum
4、 period attacks,Grover algorithm-related attacks,and quantum differential attacks.For each category,representative attackmethods are introduced,accompanied by an elucidation of the core concepts underlyingeach approach.Furthermore,we contemplate future research directions within this domain,consider
5、ing potential advancements in light of existing attack schemes.Keywords:cryptanalysis,quantum algorithm,symmetric cryptosystem,quantum attack美国物理学家费曼在 1982 年提出了量子计算的概念1,该技术引起了世界各国的广泛关注。量子计算在大整数分解、离散对数计算等多个计算问题上展现出了显著优势。量子密码分析学(亦称为量子攻击)是量子计算与密码分析相交叉的新学科,具有经典密码分析不能拥有的资源及速度优势。本文主要介绍了量子密码分析学中针对于传统密码体制中对
6、称密码体制的部分,即量子(对称)密码分析学。并把使用量子算法进行密码分析的过程称为量子环境设置,把未使用量子算法进行密码分析的过程称为经典或传统环境设置。量子计算对非对称密码分析学产生了深远影响。Shor 算法2和 Grover 算法3作为两种经典的量子计算方法,开启了量子密码分析的先河。1994 年,Shor 提出了在多项式时间内收稿日期:2023-06-29基金项目:国家自然科学基金(No.51979048)资助通信作者:冯晓宁,教授,研究方向为网络安全与密码学。E-mail:40应用科学学报第42卷分解大整数的算法2。大整数分解在传统计算机中被视为经典困难问题,很多非对称密码体制就是为了
7、解决这种困难问题而设计的,比如 RSA 加密算法4。Shor 算法理论上对传统密码造成了巨大威胁5。时隔 20 年,当初提出的理论算法已变成现实,量子计算机已经可以分解 13 位的大整数6,表明量子计算在破解非对称密码方面已经取得了实质性的突破。在对称密码体制中,量子计算的影响是有限的。Grover 算法3应用于穷举攻击,可以产生二次加速的效果7。尽管 Grover 算法在密码分析领域产生了广泛的影响,但除 Grover 算法之外,绝大多数量子算法只能提供亚指数或多项式级别的加速,在对称密码分析方面的实际影响尚不明显。这也导致了密码学领域一个长期存在的共识:简单地将传统对称密码算法的密钥长度加
8、倍,可确保对称密码算法在量子计算模型下的安全性。美国国家科学院关于量子计算的报告中指出:可能存在一些迄今未知但性能远超 Grover算法的量子攻击。许多密码学家正在探索比 Grover 算法更为高效的密码分析手段。例如,量子差分密码分析将经典差分密码分析的环境置为量子环境,旨在得到相比于经典情况下二次甚至指数级别的加速8。密码学家在诸多量子密码分析方面取得了长足的进步,有些甚至能够在多项式时间内破坏许多对称密码系统。1研究脉络及分类近年来,涉及量子对称密码分析学的研究成果显著增多,多数研究都在探索比传统密码分析所需资源更少的量子密码分析方法。对称密码体制的量子密码分析主流研究有两个重要特点:1
9、)绝大多数量子攻击基于量子选择明文攻击模型(quantum chosen plaintext attack,qCPA)9。作为一个通用的攻击模型,一旦实施了攻击,则说明对称密码体制在量子设置下是不安全的。2)有两种逐步上升的研究趋势,一种是通过将经典密码分析算法转换为量子设置进行攻击,另一种是以低资源量子消耗为目标设计量子密码分析算法10。这两个研究趋势说明,在经典设置下可能无效的攻击方法,但在量子设置下可能会有效。为了更深入地理解对称密码体制量子攻击的研究历史沿革以及各文献之间的关系,图 1 展示本文重点文献关系。其中箭头表示研究的递进关系,虚线表示同类研究,红色表示高被引用文章,蓝色表示出
10、现的2010 Kuwakado?162012 Kuwakado?172013 Rotteler?18?Simon?2019 Bonnetain?192020 Dong?20?Simon?2016 Kaplan?21(?)2022 Shinagawa?322022 Zhang332020 Ni?342018 Dong?35(?)2017 Alagic?232018 Bonnetain?24(?)2017 Leander?30(Grover meetsSimon)2019 Bonnetain?25(Offline simon)Grover?2020 Rahman?272020 Bonnetain?
11、28(offline simon?)2022 Ulitzsch?292018 Hosoyamada?44(?Demiric&selcuk?)2022 Frixons?482020 Hosoyamada?51(?)2022 Schrottenloher?54?372017 Grassl?382018 Almazrooie?392020 Langenberg?40(?AES?)2020 Anand?432021 Liu?432015 Zhou?662015 Li612017 Xie?622019 Xie?632020 Xie?64(?)2020 Xie?642021 Zhou?362018 Li?
12、69(?)?II?I?2022 Denisenko?682015 Kaplan?652021 Jojan?671997 Simon112022 Canale?221993 Bernstein?56(Bernstein-Vazirani?)2020 Aaronson?70(?)2019 Chen?71(?/?)?图 1 对称密码体制量子攻击的研究脉络Figure 1 Research context of quantum attack on symmetric cryptosystem第1期冯晓宁,等:对称密码体制的量子攻击41重点或有前景的攻击方法。根据上述研究脉络,本文将现有对称密码体制的量
13、子攻击划分为量子周期攻击、Grover算法相关攻击及量子差分攻击,如图 2 所示。量子周期攻击以 Simon 算法为基础,主要关注Simon 算法中的弱化条件情况。除此之外,本文介绍了基于 Simon 算法的周期构建攻击,以及 Simon 算法的离线计算方式。在 Grover 算法相关攻击的研究中,主要介绍 Grover meetsSimon 算法、Grover 算法的穷举攻击以及近来基于 Grover 算法中备受关注的量子中间相遇攻击。量子差分算法是基于 B-V 算法进行研究的,随后本文分两阶段进行详细阐述。?Grover?Simon?Grover on X?Grover meets X?B
14、-V?图 2 对称密码体制的量子攻击分类图Figure 2 Classification diagram of quantum attacks on symmetric cryptosystems2量子周期攻击2.1Simon算法的研究目前,Simon 算法11已经成为一种基础性的量子密码分析算法。为获取布尔函数的周期,经典算法需要指数式查询复杂度。使用 Simon 算法获得布尔函数周期的步骤如下:首先通过多次使用 Simon 算法获得 n 1 个线性独立的变量,然后使用经典算法(如高斯消除算法)解个数为 n 1 的二值线性方程组。使用 Simon 算法的主要优势在于它能够在多项式查询复杂度下
15、获得函数 f(x)的周期。对 Simon 承诺条件弱化情形的研究起步较早。文献 12 说明了 Simon 函数的碰撞与测量结果之间的确切关系,证明了在大多数随机情况下,额外的碰撞不会导致 Simon 算法攻击的复杂性显著增加。Simon 函数应避免碰撞过大,现在大多数基于 Simon 算法的密码分析都使用以下的冲突假设(f,s)=maxt0,1n0,sPxf(x)=f(x t)612(1)式中:max 为取最大值函数;Px为概率;(f,s)为量化函数 f(x)距离 Simon 承诺远近的参数。(f,s)与 Simon 算法的失效概率有着紧密联系。(f,s)越接近 1,则函数发生冲突的概率越大,
16、Simon 算法的失效概率越大;(f,s)越接近 0,函数越接近一个完美的周期函数,Simon算法的失效概率越低。给出(f,s)6 1/2 的假设意味着使用 Simon 函数可以在 O(n)次的查询后找到周期 s。文献 12 的进一步结论是,经过 cn 次查询后,可返回计算周期 s 的概率为1 2n(0.6454)cn。特殊地,当取 c=4,n=8 时,得到周期 s 的概率约为 0.998。即 Simon算法作为子程序(重复地执行 4n 次)将保证成功概率接近 1。文献 13 对上述的结论进行了泛化:定义了 4 个扩展的布尔隐藏周期问题,利用函数的周期个数以及是否具有额外碰撞这两个属性进行划分
17、,扩展了 4 种弱化的 Simon 算法的承42应用科学学报第42卷诺条件,经证明这 4 种弱化的承诺条件均可以使用 Simon 算法进行多项式求解。弱化承诺下Simon 算法仍有很多其他相关的重要性质,文献 14 发现在弱化承诺下 Simon 算法具有以下重要性质:若一个函数存在周期,则该函数只存在唯一周期的概率接近 1。文献 15 指出只需要前向蕴含的承诺 x=y s f(x)=f(y)就能够利用 Simon 算法获得独立向量。弱化承诺下 Simon 算法在对称密码分析中具有很强的实用性,促使量子周期攻击快速发展。2.2基于周期构建的攻击量子周期攻击是利用解布尔函数周期问题的量子算法进行密
18、码分析的攻击方法。Simon算法完成量子周期攻击的主要思路是:在目标密码体制中构建函数,该函数即为布尔隐藏周期问题中的函数 f,通过结合 Simon 算法和解传统方程组的方法来确定函数的周期,进而对指定密码体系进行分析。文献 16 利用 Simon 算法实现了开创性的量子密码分析。其中展示的攻击方法是利用量子叠加模型在 O(n)的量子时间复杂度下构建了一个区分器。随后,文献 17 通过构建 Even-Mansour 密码体制上的周期函数实施了量子周期攻击,获取了 Even-Mansour 密码体制的密钥,表明 Even-Mansour 密码体制是不安全的。文献 15 利用 Simon 算法对固
19、定长度密码块链消息认证码(cipher block chaining message authentication code,CBC-MAC)进行了伪造攻击,能够为以前未查询过的消息生成有效的标签。文献 18 所构建的函数f(x)=Ex(m),Exs(m)周期为 s,而 s 正好是相关密钥攻击模型中需要寻找的密钥 K。使用 Simon 周期构建可形成量子滑动攻击。文献 19 针对替换-置换网络(substitution-permutation network,SPN)和 Feistel 密钥簇,在经典滑动攻击的基础上,根据不同的滑动类型(如扭曲滑动,互补滑动和镜像滑动),提出了较为完整的量子滑
20、动攻击。这种量子滑动攻击的主要思路是:使用经典滑动攻击满足的滑动属性构建 Simon 函数,构建的周期 s 中包含所寻找的密钥值 K。文献 20 使用量子滑动攻击对 2/4K-Feistel 和 2/4K-DES 进行密码分析,相比经典的滑动攻击,该方法在时间复杂度上获得了指数级的加速。文献 21 给出了一种在旋转密码块结构上构建周期函数的新方法。对于可调整分组密码,固定 t06=t1,构建函数 f(x)=Ek(x h(t0)h(t0)Ek(x h(t1)h(t1),此函数的周期为 s=h(t0)h(t1)。文献 22 提出了一种自动搜索周期函数的方法,其主要思想是将计算复杂度中的电路理论引入
21、自动测试中。这种方法涉及使用一系列电路来表示对应密码体制中的合理函数,然后测试所有可能的电路配置来确定这些函数的周期性特征。通过这种自动化方法结合 Simon 算法,实施了有效密钥恢复攻击。在 2017 年的欧洲密码学会议上,文献 23 介绍了一种新策略来对抗文献 21 中描述的攻击方法。这种策略建议用更复杂的运算方法替换传统的异或运算,以增强安全性。鉴于效率和实现方案的均衡,常见的替换方案是模加运算。文献 23 说明此改进可以抵抗量子选择明文攻击。文献 24 对 Kuperberg 算法进行了改进,显著降低了针对 Poly1305(使用模加运算的加密算法)的攻击成本。相较于通用攻击的复杂度为
22、2n,这种改进将复杂度降至 2O(n),显著提高了效率。2.3离线计算方式的攻击在特定的攻击场景中,假设敌方只能通过传统(经典)方式访问加密体系,这种假设被称为离线计算方式。文献 25 对 Grover meets Simon 算法进行了改进,并提出了离线 Simon 算法。这种算法是 Q1 模型下的一种 Simon 算法,适用于在有限条件下进行加密分析。算法的主要思路是利用目标密码体制 g 以及密码体制中的公开函数 f 构造函数 g?f,在目标体制密码 g 上做经典查询得到量子态|gi。通过对 f 的量子叠加查询得到 g?f,在 g?f 上应用并行第1期冯晓宁,等:对称密码体制的量子攻击43
23、化的 Simon 算法判定 g?f 是否具有周期性:如果 g?f 显示出周期性,则表明找到了正确的密钥。在这种情况下,可以利用 Grover 算法搜索正确密钥。文献 26 对离线 Simon 算法进行了更广泛的推广,指出 g 与 f 的结合方式不必局限于异或的方式。同时,g 也不需要仅限于排列函数。上述离线计算方式以高概率寻找到正确密钥和周期值,具有如下定理:当攻击者具有对 g 的经典查询权限时,离线 Simon 算法对 g 进行了 O(2n)次经典查询,时间复杂度为O(n3+nTf)2m/2),其中 Tf表示量子查询一次 f 的时间,m 是 Grover meets Simon 算法中的常数
24、。在实现离线计算方式的算法中,主要难点在于正确选择并组合 g 和 f。文献 27 在文献 25 的基础上使用离线计算方式构造对哈希计数器的新攻击。文献 28 给出了 Simon 离线计算方式的第 1 个完整实现,并估计了多种轻量级密码体制的攻击成本。文献 29 在对移动通信网中的 Milenage 算法集进行量子密码分析时,实现了离线 Simon 算法对相关密钥分析进行加速。3Grover 算法相关攻击的研究Grover 算法是典型的量子搜索算法,可解决无序搜索问题。Grover 算法作为一种高性能量子搜索算法,实现了对经典搜索算法的二次加速,在密码分析领域中备受瞩目。3.1Grover me
25、ets X算法Grover 算法能够与其他量子算法进行结合并作用在量子对称密码分析中,这一类算法被称为 Grover meets X 算法,其中 X 指结合的量子算法。将 Grover 算法整合到密码分析算法中被视为一种臃肿的操作。许多研究者应用了与 Grover 算法具有等效的放大器定理:设 A 是在量子比特上无测量的量子算法,量子算法 B:0,1q 0,1 是量子算法 A 的分类器,将 A 作用的结果分成 0 和 1,分类器 B 判定态 A|0i 为 1 的成功概率为 p,定义k=d/(4)e,sin2()=p,酉矩阵 Q=Q(A,B)=AS0A1SB,S0仅在|0i 态上起作用,那么经过
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 对称 密码 体制 量子 攻击
![提示](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。