破解R. S. Bhalerao 公钥加密方案

破解R. S. Bhalerao 公钥加密方案 Break R. S. Bhalerao’s Public Key Encryption Scheme 1 2 first-author 贾建卫, 男, 博士生, 现从事密码学和信息安全方面的研究. E-mail:jjwwhu@whu.edu.cn 贾建卫, 男, 博士生, 现从事密码学和信息安全方面的研究. E-mail: jjwwhu@whu.edu.cn jjwwhu@whu.edu.cn 1 2 3 1 2 corresp E-mail:liss@whu.edu.cn E-mail:liss@whu.edu.cn liss@whu.edu.cn 4 武汉大学 计算机学院, 湖北 武汉 430072 武汉大学 计算机学院, 湖北 武汉 430072 School of Computer， Wuhan University, Wuhan 430072, Hubei, China School of Computer， Wuhan University, Wuhan 430072, Hubei, China 武汉大学 空天信息安全与可信计算教育部重点实验室, 湖北 武汉 430072 武汉大学 空天信息安全与可信计算教育部重点实验室, 湖北 武汉 430072 Key Laboratory of Aerospace Information Security and Trusted Computing, Ministry of Education, Wuhan University, Wuhan 430072, Hubei, China Key Laboratory of Aerospace Information Security and Trusted Computing, Ministry of Education, Wuhan University, Wuhan 430072, Hubei, China 石家庄学院 计算机系, 河北 石家庄 050035 石家庄学院 计算机系, 河北 石家庄 050035 Computer Department, Shijiazhuang University, Shijiazhuang 050035, Hebei, China Computer Department, Shijiazhuang University, Shijiazhuang 050035, Hebei, China 中国建设银行陕西省分行, 陕西 西安 710002 中国建设银行陕西省分行, 陕西 西安 710002 China Construction Bank Shaanxi Branch, Xi’an 710002, Shaanxi, China China Construction Bank Shaanxi Branch, Xi’an 710002, Shaanxi, China R. S. Bhalerao 等人设计了建立在矩阵群上的R.S.公钥加密方案. 本文利用矩阵的一些性质, 在不需要找到私钥的情况下, 多项式时间内恢复出明文, 并给出了方法描述和时间复杂度分析, 破解了R. S. Bhalerao 公钥加密方案. R.S. Bhalerao et al . designed a public key encryption scheme based on matrix group. By using some properties of matrix, in the case of not finding a private key, we can recover the plain text in polynomial time, and present a method to describe and analyze of time complexity, which cracked R.S. Bhalerao’s scheme. 密码学 公钥加密 密码分析 云计算 线性方程组 cryptography public key encryption cryptanalysis cloud computing linear equations 引 言 1 云计算自被提出以来就受到了广泛的关注,它的出现大大推动了 IT 产业的发展,提高了社会的生产效率并节约了社会成本，因此各大公司及机构都大力推广云计算服务. 从安全角度来说,在云计算环境中,用户的数据往往都被储存在看不到摸不到的远程服务器中,而云计算服务提供商并不是可以信任的第三方,因此个人数据的保密性安全性的问题也就日益凸显. 围绕云计算的安全,国内外都已经进行了广泛的研究 [ 1 1 ~ 5 5 1~5 ] . 2015年,Bhalerao等 [ 6 6 ] 提出了一种简单有效的方法(简称R.S.公钥加密方案),使在不牺牲数据拥有者匿名性的前提下,能够确保云数据的完整性. 并且为了确保数据的保密性,Bhalerao等在文章中设计了一个适用于云的基于矩阵群的公钥加密方案,并声称他设计的公钥密码方案是建立在困难问题上的. Bhalerao声称攻击者必须计算出 XB = A -1 X 中确定的 X 的解,由于解的个数很多,攻击者并不能从中得到加密方确定的私钥,因此他的公钥密码方案是安全的. 基于矩阵的非交换结构具有抗量子计算机攻击的潜力和计算效率高的优点，近年来,设计和分析基于矩阵的公钥密码体制成为了研究热点 [ 7 7 ~ 11 11 7~11 ] . 本文通过构造矩阵的线性表达式,通过巧妙的构造，在不找出私钥的情况下恢复出明文,破解了该方案. 知识准备 1 首先，我们在这一部分简单的介绍一些涉及到的基本的数学表示形式和符号: ${{\mathbb{Z}}_{n}}$表示整数环｛0,1,2，…， n －1｝， GL m (${{\mathbb{Z}}_{n}}$)表示环${{\mathbb{Z}}_{n}}$上的 m × m 可逆矩阵集合， ${{\mathbb{R}}^{m\times m}}$表示实数域$\mathbb{R}$上的 m × m 矩阵， A T 表示矩阵 A 的转置,$\overrightarrow{X}$表示将 n × n 的矩阵 X 按行拉直得到一个 n 2 维行向量,⊗表示Kronecker积. 定理1 (Hamilton-Cayley定理)设 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464713&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464713&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464713&type=middle 则存在 b 1 ,…， b m ∈${{\mathbb{Z}}_{n}}$使得 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464724&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464724&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464724&type=middle 性质1 Kronecker积有以下的性质: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464732&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464732&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464732&type=middle 性质2 拉直运算有如下的性质: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464739&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464739&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464739&type=middle R. S. Bhalerao等人的公钥加密方案 1 为了完整性,在这一部分我们将回顾文献 [ 6 6 ] 中Bhalerao 等人的公钥加密方案,在下面的运算中,如无特殊说明,都是在 GL 2 (${{\mathbb{Z}}_{n}}$)上进行运算. 密钥生成: n是一个半素数, X 和 A 是随机选自 GL 2 (${{\mathbb{Z}}_{n}}$)的矩阵,且保证 XA -1 ≠ AX ,然后随机的选择一自然数 r 并计算: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464748&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464748&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464748&type=middle 将 n , A,B 和 R 作为公钥,私钥为 X . 公钥加密: 发送者随机的选择一自然数s并依次序计算得到: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464756&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464756&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464756&type=middle 将明文转化为2×2矩阵 Y 的形式,计算密文 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464763&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464763&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464763&type=middle 将 Y ′和 E 发送给接收方. 私钥解密:计算 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464771&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464771&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464771&type=middle 正确性证明: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464776&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464776&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464776&type=middle 破解方案 1 本文通过分析上述R.S.公钥加密方案,在没有求出私钥 X 的情况下，能够求出 K ,从而恢复明文,下面给出破解的具体方法. 性质3 存在 b 1 , b 2 ∈${{\mathbb{Z}}_{n}}$使得 Q 可以表示成 Q = b 1 R + b 2 I . 证 由定理1可知,存在 c 1 , c 2 ∈${{\mathbb{Z}}_{n}}$使得 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464782&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464782&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464782&type=middle 那么 R 3 = c 1 R 2 + c 2 R =( c 2 1 + c 2 ) R + c 2 I 通过迭代,对于任意的自然数 k , R k 都可以用 R 和 I 线性表示,所以 R s 可以用 R 和 I 线性表示. 因为 Q = R s , 所以存在 b 1 , b 2 使得 Q 可以表示成 Q = b 1 R + b 2 I ,证毕. 那么由性质3就有方程组: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464787&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464787&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464787&type=middle 应用性质1和性质2,上式方程组可写成下面的形式: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464789&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464789&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464789&type=middle 将(2)式代入到(1)式得: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464791&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464791&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464791&type=middle 其中 b i 为未知量,其他均为已知矩阵. 求解方程并选取其中一个解 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464809&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464809&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464809&type=middle ,就得到了 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464812&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464812&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464812&type=middle 且保证 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464817&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464817&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464817&type=middle 可逆. http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464793&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464793&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464793&type=middle 那么明文 Y = K -1 Y ′ K -1 . 下面用算法1描述破解R.S.公钥加密方案的过程. 算法1 恢复出明文 Y . 输入: 公钥 E，A，R 和密文 Y ′ 输出: 明文 Y 步骤1 计算矩阵 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464795&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464795&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464795&type=middle 步骤2 求解线性方程组 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464820&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464820&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464820&type=middle 的解,并从中选取一个解 B ,计算得到 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464823&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464823&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464823&type=middle 且保证 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464824&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464824&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464824&type=middle 可逆; 步骤3 计算得到 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464827&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464827&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464827&type=middle 和 K -1 ; 步骤4 计算 Y = K -1 Y ′ K -1 ; 步骤5 返回明文 Y . 显然私钥 Q 是方程(3)的一个解,所以方程(3)至少存在一个解. 当方程(3)只存在惟一非零解时,则 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464832&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464832&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464832&type=middle 当方程(3)存在多解时,从中挑选一可逆解${\hat{Q}}$. 命题1 对于不同的可逆解${\hat{Q}}$, K 的值是惟一的. 证 不妨假设真实的 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464797&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464797&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464797&type=middle d 1 , d 2 是方程的另外一组解,即 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464839&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464839&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464839&type=middle ,下面我们证明 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464845&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464845&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464845&type=middle . http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464800&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464800&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464800&type=middle 因为 R = X s ，所以 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464802&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464802&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464802&type=middle 下面对算法1评估其计算复杂度. 在${{\mathbb{Z}}_{n}}$上,求解 m × m 矩阵的逆和两个 m × m 的矩阵乘法的计算复杂度都是 Ο ( m ω )( ω ≈1.375 5)${{\mathbb{Z}}_{n}}$操作,每个${{\mathbb{Z}}_{n}}$操作大约需要Ο( log 2 n)bit操作 [ 12 12 ~ 14 14 12~14 ] . 算法1的计算复杂性分析如 表 1 表 1 . 内容 bit复杂性 解释 步骤1 Ο (2 2 ω -1 log 2 n ) 矩阵相乘 步骤2 Ο (2 ω +1 log 2 n ) 求解线性方程组 步骤3 Ο (2 3 ω +1 log 2 n ) 矩阵相乘和矩阵求逆 步骤4 Ο (2 ω +1 log 2 n ) 两个2阶矩阵相乘 通过 表 1 表 1 可知,忽略小的固定参数,算法1攻击R.S.公钥加密方案的bit复杂度是 Ο (log 2 n ). 实例( n =26) 1 本节通过实例演示破解R.S.公钥算法. 首先随机生成 X 和 A ; 随机选取自然数 r 和 s ,计算并公布 A,B,R,E ; 然后根据算法1求解出 K －1 ; 最后根据破解方案就恢复了明文. 参数生成: 选取可逆矩阵 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464848&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464848&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464848&type=middle ,选取自然数 r =3, s =6,计算得 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464806&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464806&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464806&type=middle 公钥: A,B,R,E , n 私钥: X 根据算法1计算得到一个解 b 1 =1, b 2 =10 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464851&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464851&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464851&type=middle 验证: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464853&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464853&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464853&type=middle 输出明文 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464860&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464860&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464860&type=middle 从而破解了该公钥方案. 结 论 1 本文针对文献 [ 6 6 ] 在整数环上的R.S.方案给出了有效的攻击方法,通过分析可知,在log 2 n 的bit复杂度内可以攻破该协议,并通过计算一个实例演示了该方案的破解过程. R.S.方案是建立在矩阵群的基础上的,本文主要是运用矩阵的一些性质对该方案进行了分析,因此该方案如果能够避开矩阵群,而选择其他的非交换群,就有可能避开本文的攻击,则仍不失为一个有效的公钥方案.如何在云计算环境下设计一个安全的公钥密码方案仍然需要进一步的研究. 参考文献 DINH H T, LEE C, NIYATO D, et al . A survey of mobile cloud computing: architecture, applications, and approaches[J]. Wireless Communications & Mobile Computing , 2013, 13 (18):1587-1611. HASHIZUME K, ROSADO D G, FEMNDEZ M E, et al . An analysis of security issues for cloud computing[J]. Journal of Internet Services and Applications , 2013, 4 (1): 1-13. 胡刚, 邹德清, 孔华峰, 等. 云防御系统中用户隐私保护机制[J]. 武汉大学学报(理学版), 2014, 60 (6):491-496. HU G, ZOU D Q, KONG H F, et al . User’s privacy protection on cloud-based anti-malware system[J]. Journal of Wuhan University (Natural Science Edition) , 2014, 60 (6):491-496(Ch). RONG C, NGUYEN S T, JAATUN M G. Beyond lightning: A survey on security challenges in cloud computing[J]. Computers & Electrical Engineering , 2013, 39 (1):47-54. 羌卫中, 秦攀, 邹德清,等. 云防御系统中多引擎检测机制[J]. 武汉大学学报(理学版), 2014, 60 (5):393-398. QIANG W Z, QIN P, ZOU D Q, et al . Multi-engine detection in cloud-based defence system[J]. Journal of Wuhan University(Natural Science Edition), 2014, 60 (5):393-398(Ch). BHALERAO R S, ROKADE S M, Public-key encryption scheme for scalable data sharing with others in cloud storage[J]. International Journal of Informative & Futuristic Research , 2015, 2 (5): 1486-1491. DUCAS L, MICCIANCIO D. Improved Short Lattice Signatures in the Standard Model . http://link.springer.com/chapter/10.1007/978-3-662-44371-2_19 http://link.springer.com/chapter/10.1007/978-3-662-44371-2_19 . PEIKERT C.Lattice Cryptography for the Internet. http://link.springer.com/chapter/10.1007/978-3-319-11659-4_12 http://link.springer.com/chapter/10.1007/978-3-319-11659-4_12 . MYASNIKOV A D, USHAKOV A. Cryptanalysis of matrix conjugation schemes[J]. Journal of Mathematical Cryptology , 2014, 8 (2): 95-114. BRAKERSKI Z, SEGEV G. Better security for deterministic public-key encryption: The auxiliary-input setting[J]. Journal of Cryptology , 2014, 27 (2):210-247. 刘金会, 张焕国, 贾建卫, 等. HKKS密钥交换协议分析. 2015 http://www.cnki.net/kcms/detail/11.1826.TP.20150723.0954.076.html. http://www.cnki.net/kcms/detail/11.1826.TP.20150723.0954.076.html. LIU J H, ZHANG H G, JIA J W, et al . Cryptanalysis of HKKS key exchange protocols. http://www.cnki.net/kcms/detail/11.1826.TP.20150723.0954.076.html http://www.cnki.net/kcms/detail/11.1826.TP.20150723.0954.076.html (Ch). 张焕国, 刘金会, 贾建卫, 等. 矩阵分解在密码中应用研究[J]. 密码学报, 2014, 1 (4):341-357. ZHANG H G, LIU J H, JIA J W, et al. A survey on applications of matrix decomposition in cryptography [J]. Journal of Cryptologic Research, 2014, 1 (4): 341-357(Ch). GASHKOV S B, SERGEEV I S. Complexity of computation in finite fields[J]. Journal of Mathematical Sciences , 2013, 191 (5): 661-685. GU L, ZHENG S. Conjugacy systems based on nonabelian factorization problems and their applications in cryptography[J]. Journal of Applied Mathematics , 2014,(2014):1-9. 10.14188/j.1671-8836.2016.05.004 TP 309 whdxxblxb-62-5-425 国家自然科学基金资助项目(61303212, 61170080, 61202386); 国家自然科学基金资助重点项目 (61332019,U1135004); 国家自然科学基金资助重大项目 (91018008); 国家重点基础研究发展计划(973)项目 (2014CB340600); 湖北省自然基金项目 (2011CDB453,2014CFB440) 2015-09-15 2020-12-10 版权所有 © 《武汉大学学报(理学版)》编辑部 Copyright © 2016 Journal of Wuhan University (Natural Science Edition). All rights reserved. 2016 武汉大学学报(理学版) 5 62