英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料
SM2密钥交换协议的部分已知信息攻击
摘要：SM2密钥交换协议是国家密码局在2010年发布的基于椭圆曲线的SM2公钥密码算法的一部分。在中国政府的指导下，SM2在中国的商业中得到了广泛的应用。本文给出了对SM2密钥交换协议的第一个部分已知信息攻击。我们的攻击是基于隐藏数问题（HNP）的改进技术，该技术最初是为了研究Diffie-Hellman的比特安全性和相关方案而引入的。本文提出了一种多项式时间算法，在每个同余的两个未知中间值中约有一半的最小有效位在30到40个实例中恢复用户的密钥。与标准的HNP方法相比，我们的方法处理了包含两个独立未知变量的同余，并且每个变量都具有与密钥相同的大小。此外，考虑到完全揭示一个变量的极端情况，我们的结果几乎与先前同一领域中的最佳结果一致。
关键词：SM2密钥交换协议；密码分析；信息泄漏；格点攻击；扩展隐数问题
引文：魏伟，陈俊智，李德，等。对SM2密钥交换协议的部分已知信息攻击。Sci中国信息科学，2019，62（3）：032105，https://doi.org/10.1007/s11432-018-9515-9
1简介
基于椭圆曲线的SM2公钥密码算法是中国国家密码管理局2010年发布的国家标准[1]，其初衷是指导制造商开发中国商用信息安全产品。近年来，SM2在TPM 2.0[2]和ISO/IEC 14888-3[3]等国际安全领域的应用越来越广泛。SM2主要由数字签名算法、公钥加密算法和密钥交换协议三部分组成。本文主要研究SM2密钥交换协议。SM2密钥交换协议是椭圆曲线Diffie-Hellman密钥交换协议的变体[4]。调用Diffie-Hellman密钥交换协议。设（G，·）是一个具有g isin; G的群，有两个参与者分别选择随机u和v，他们计算gund-gv，然后相互交换。那么Diffie-Hellman的秘密钥匙就是guv。从理论上讲，SM2密钥交换协议的安全性是基于椭圆曲线上离散对数问题（ECDLP）的计算稳定性。基于ECDLP的密码系统需要较小的参数才能达到相同的安全级别，这与其他许多基于有限域上的硬问题的公开密钥方案不同。尽管如此，由于侧通道攻击、错误注入攻击或软件缺陷，在实现过程中仍然存在许多实际的密码漏洞。因此，在建立共享密钥时，必须特别注意nonce和其他中间值。本文主要研究了部分已知信息对SM2密钥交换协议的攻击。具体来说，在计算一个参与者的共享密钥时，由于中间值的泄漏，我们的目标是公开私钥。
在基于ECDLP的公钥密码系统中，针对信息泄漏的攻击有很多种，如数字签名算法（DSA）和椭圆曲线数字签名算法（ECDSA）等[5-8]。但是基于ECDLP的密钥交换协议在安全性方面的研究成果较少，特别是对于SM2。1996年，Boneh和Venkatesan[9]首先利用一个名为HNP[9]的工具研究了Diffie-Hellman和其他相关方案在素数域中的nonce泄漏，证明了密钥中radic;logp最重要位的位安全性。事实上，HNP可以看作是截断变量的多维线性同余。它不仅在Diffie-Hellman及其相关方案的比特安全性证明[10]中起着重要作用，而且在攻击DSA类的签名方案中也起着重要作用。在1999年，Howgrave-Graham和Smart[5]攻击了160位DSA，基于对每个对应nonce的一些位的了解的合理数量的签名。随后，Nguyen和Shparlinski[8]在对DSA的一些假设下给出了一个可证明的多项式时间攻击，其中nonce是部分已知的。这一结果在[6]中得到了改进。对256位SM2数字签名方案[11]实施了类似的部分已知nonce攻击，在该方案中，可以通过100个签名恢复私钥，每个nonce的知识为3位。以上攻击大多是在相关方案的安全性由生成步骤中选择的名词的随机性所保证的情况下成功的。与此不同，部分信息泄漏产生的统计偏差也被用于密钥恢复[12–15]。这种类型的攻击预计会成功，只需知道较少的位，但会牺牲更多的实例。
HNP通常处理与一个未知目标相关的问题及其若干随机近似。当给定的近似值不连续时，会出现一个实际的密码分析问题，这意味着所公开的比特分布是离散的。为了放松对一致性的限制，提高HNP在实际攻击中的可用性，在不同的应用中采用了这个问题的各种变体[8,16,17]。2006年，Hlavaˇc和Rosa[18]提出了一个扩展隐数问题（EHNP）和一个多项式时间的密钥恢复算法。EHNP显著放宽了HNP中信息泄漏位置的严格限制，这对当前的侧信道攻击非常重要。然后对该技术进行了改进，并将其应用于攻击ECDSA上具有窗口非相邻形式（wNAF）的OpenSSL实现[19]。
格基归约算法是求解HNP（和EHNP）的关键工具，因为一个短格向量或相关格的一个闭格点往往揭示了HNP（或EHNP）的解。格基归约一直是基于格的密码构造和密码分析中的一个热点问题。自1982年LLL算法的开创性工作[20]提出以来，许多改进算法相继出现。目前最实用、应用最广泛的算法是陈和阮在2011年提出的BKZ 2.0[21]，它是在Schnorr Euchner的BKZ[22]的基础上改进的。近年来，一些在实践中表现更好的BKZ变体已经被研究过[23-25]。
到目前为止，针对椭圆曲线密钥交换协议的部分信息攻击的研究成果很少。在部分信息攻击方面，与其他类似DSA的方案相比，SM2密钥交换协议的情况更为棘手，因为存在与nonce相关的额外未知随机变量，这使得即使可以完全公开nonce，私钥仍然被覆盖。本文讨论了在生成SM2共享密钥时，中间变量的部分信息被泄漏的问题，这在现实场景中更为自然。这是针对SM2密钥交换协议的部分信息泄漏攻击的第一个结果。为了从一组实例中恢复私钥，我们首先将其转化为一个类EHNP问题，然后使用格基归约作为关键工具，将问题归约为对应于某个目标向量的相关格中的最近向量搜索问题。
尽管这种构造与经典技术非常相似，由于问题与标准EHNP之间的细微差别，成功概率的证明更加复杂。此外，我们的实验表明，在40个实例中，每个实例中有512个未知比特，如果中间变量中有265个以上的最低或最高有效比特是已知的，我们就可以在成功概率大于0.95的个人笔记本电脑中恢复私钥的最大对应部分。此外，在比例优化下，已知的比特数可以减少到259。当考虑到一个变量被完全揭示的极端情况时，这个结果几乎与先前同一领域中的最佳结果[11]一致。本文的主要内容如下：第二部分是对SM2密钥交换协议的介绍和一些必要的背景知识的介绍。在第三节中，我们给出了在已知部分信息的情况下对SM2密钥交换协议的攻击。第4节给出了我们对第3节中提出的攻击的实验结果。第五节对论文进行总结。
2准备工作
在这一节中，我们简要回顾了SM2密钥交换协议，以及格的一些基本知识。文中还介绍了HNP和EHNP符号作为攻击的重要工具。
2.1 SM2密钥交换协议概述
本文在对SM2密钥交换协议的研究中，重点研究了特征pgt;3的素数域FP上定义的椭圆曲线。对于参数a，bisin;Fp满足4a3 27b26=0，由椭圆曲线的有理点和无穷点O构成的群E（Fp）定义为：
E(Fp) = {P = (x, y) | y2 = x3 ax b mod p, x, y isin; Fp} cup; {O}.
在密钥生成阶段，选择一个素数阶为n的基点G=（xG，yG）isin;E（Fp），SM2协议客户端a（和B）随机选择dAisin;[1，n-1]和dBisin;[1，n-1]作为其私钥。对应的公钥是PA=dAG（分别为PB=dBG）。此外，下面列出了SM2密钥交换协议中使用的一些其他必要的符号。综合描述可参照官方标准[1]。
（1） h：辅因子，h=#E（Fp）/n，其中#E（Fp）是E（Fp）的大小。
（2） 会话密钥的位长。
（3） KDF（Z，klen）：输出长度为klen的单向派生哈希函数。
（4） ZA:客户端A标识的哈希值。
（5） ZB：客户端B标识的哈希值。
（6） Hash（）：哈希函数。
（7） ||：两个字符串的连接。
SM2密钥交换协议的主要过程如下。作为发起方，客户端A将与客户端B建立会话密钥。表示w=lceil;（lceil;log2（n）rceil;/2）rceil;-1。
客户A.
（1）随机选择一个整数rAisin;[1，n-1]。
（2） 计算RA=rAG=（x1，y1）。
（3） 发送RAto客户端B。
客户B。
（1）随机选择一个整数rBisin;[1，n-1]。
（2） 计算RB = rBG = (x2, y2), xmacr;2 = 2w (x2amp;(2w minus; 1)), tB = (dB x2 · rB) mod n, xmacr;1 = 2w (x1amp;(2w minus; 1)) RA, V = (h · tB)(PA xmacr;1RA) = (xV , yV ), 和KB = KDF(xV ǁ yV ǁ ZA ǁ ZB, klen)。
（3）（对于密钥确认是可选的）计算SB = Hash(0x02 ǁ yV ǁ Hash(xV ǁ ZA ǁ ZB ǁx1 ǁ y1 ǁx2 ǁ y2))。
（4） 向客户A发送RB（和SB，密钥确认可选）。
客户A
（1）计算xmacr;1 = 2w (x1amp;(2w minus; 1)), tA = (dA x1 · rA) mod n, xmacr;2 = 2w (x2amp;(2w minus; 1)) from RB, U = (h · tA)(PB xmacr;2RB) = (xU , yU ),和 KA=KDF(xU ǁ yU ǁ ZA ǁ ZB, klen)。
（2） （对于密钥确认是可选的）计算S1 = Hash(0x02 ǁ yU ǁ Hash(xU ǁ ZA ǁZB ǁ x1 ǁ y1 ǁx2 ǁ y2))并验证S1=SB。如果不正确，则终止。
（3） （密钥确认可选）计算
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[237787]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
