一种多变量公钥密码体制的安全性分析

鲁 刚，聂旭云,3，秦志光，侯川勇

(1.电子科技大学信息与软件工程学院 成都 610054；2.中国科学院信息工程研究所信息安全国家重点实验室 北京 海淀区 100093；3.网络与数据安全四川省重点实验室 成都 610054)

公钥密码学是现代化信息社会的一个重要工具。由于Shor的量子计算机攻击[1]，基于大数分解和离散对数等数论困难问题的传统公钥密码体制的安全性受到了威胁，如RSA和ElGamal等。因此，有必要寻找基于其他困难问题的公钥密码体制来替代RSA和ElGamal。

寻找可替代的公钥密码系统已有一些研究，多变量公钥密码体制也是其中一种。典型的多变量公钥加密体制的设计方法主要有小域-大域方法和三角形逐步迭代方法两种。

小域-大域方法是多变量公钥密码体制的公钥映射定义在小域上，而中心映射定义在小域的某个扩域上。比较典型的有MI体制[2]、HFE(隐藏域方程)体制[3]和Square体制[4]。原始的MI加密体制被文献[5]利用线性化方程的攻击方法破解了。HFE体制[3]自1996年提出之后，一直受到人们的关注，目前大量的研究集中在HFE抵抗解方程攻击的复杂度估计以及合适的安全参数选择。Square体制[4]其中心映射为奇特征有限域上的平方函数。原始的Square体制被文献[6]利用差分攻击破解。文献[7]提出了双层Square体制和Square+方案来抵挡差分攻击。但是，文献[8]对利用精炼的MinRank攻击方法破解了这两个体制。三角形逐步迭代方法指的是体制的中心映射可逐步迭代进行求逆，其中较为典型的有MFE[9]、TTM[10]等。原始的MFE体制在2007年被文献[11]利用二阶线性化方程方法破解，因而是不安全的。TTM体制多数满足线性化方程，也是不安全的[12]。目前，已有的多变量公钥加密体制的安全性均有待研究。

2014年，文献[13]提出了一种新多变量公钥密码体制，该体制结合了小域-大域方法和三角形逐步迭代方法，具有较高的加密和解密效率。虽然该体制满足线性化方程，但是合适的参数选择可以抵挡线性化方程攻击，并且能够抵挡秩攻击和差分攻击等。

通过理论分析和实验验证，本文结合线性化方程攻击方法和差分攻击方法给出了文献[13]方案的破解，可恢复合法密文相应的明文。首先利用线性化方程方法对文献[13]公钥进行消元获得与Square体制的等价方案，然后，利用差分攻击找到该等价方案的等价密钥，从而恢复合法密文相应的明文。在普通PC机上，利用Magma实现并验证了破解的全过程。当q=31，n=73，l=2，t=3时，给定公钥，在计算复杂度为238次域GF(31)上运算的预计算基础上，恢复明文的计算复杂度约为233次域GF(31)上运算；当q=31，n=103，l=2，t=3时，给定公钥，在计算复杂度为242次域GF(31)上运算的预计算基础上，恢复明文的计算复杂度约为235次域GF(31)上运算。

1 预备知识

1.1 多变量公钥密码体制的一般形式

令K=Fq是一个q元域，n和m是两个正整数。L1和L2分别是Kn和Km上的两个随机选取的仿射变换，为明文变量，为密文变量。令：

1.2 一阶线性化方程

一阶线性化方程形式如下：

线性化方程最早是Patarin提出用来破解MI体制，2007年，文献[11]将该方法推广提出了高阶线性化方程方法，并用来破解MFE体制。

1.3 差分攻击

公钥多项式P在点a处的差分为：

作为一个二元映射DPa：是一个对称双线性映射。

利用公钥函数差分的双线性性，可对公钥函数的构造进行分析。在多数情况下，差分攻击明文空间的一个不变子空间用来恢复体制的私钥。

1.4 Square公钥加密体制

Square公钥加密体制的中心映射为：

Square体制在2009年被差分攻击破解[6]。

2 新多变量公钥密码体制简介

将φ:推广为k-线性同构

新的多变量公钥加密函数P:kn→kn+l

，定义为：

1)F:Kt→Kt是该体制的中心映射，定义为：

3)T:为可逆仿射变换。

该多变量公钥加密体制的公钥为函数P的表达式，私钥为两个可逆仿射变换T和U。具体的加密、解密过程详见文献[13]。

为了抵挡现有攻击，文献[13]建议参数q=31，

3 新多变量公钥密码体制的破解

文献[13]指出，该方案虽然满足一阶线性化方程，但是应用线性化方程攻击方法之后并不能得到破解该方案合法密文相应的明文。同时该方案还可抵挡低秩攻击和差分攻击。

经过理论分析和实验验证，本节提出将线性化方程和差分攻击相结合的方法能够恢复合法密文相应的明文。

3.1 线性化方程

方程组(2)共包含t−1个方程，这些方程显然是线性无关的。

为了找到所有的线性化方程，需要计算足够多明密对，并将这些明密对代入式(3)得到以系数为未知数的线性方程组。令D为这个线性方程组解空间的维数，1≤m≤D}为其解空间的一组基。即得到了D个线性无关的一阶线性化方程，记这组方程为：

以上步骤仅依赖于公钥，与要破解的合法密文无关。因此对于给定公钥，该步骤可以预计算。

3.2 惟密文攻击

设该线性方程组的解空间为V′，维数为D′。解该方程组，可将D′个明文变量用其余h=n−D′个明文变量线性表出，记h个变量为将上述D′个表达式代入原公钥中，可得到n+l个新的二次多项式，记为

得到的明文变量的线性方程都是式(5)的线性组合，也就是方程组(6)在V′上成立。

整理方程组(6)，可得：

将式(7)代入原公钥的中心映射式(2)中，可得：

当t是偶数时，；当t为奇数时，

文献[6]中利用Square体制公钥的差分性质，成功地找到了该体制的私钥，从而破解了该体制。

不失一般性，将消元后的公钥函数写成：

函数P在点a处的差分是指采用类似的符号，消元后的公钥函数的差分映射为：

找到等价密钥后，对于给定的合法密文，很容易恢复其相应的明文。

3.3 具体的攻击步骤及实验结果

给定新的多变量公钥密码体制的公钥和一个待破解的合法密文，进行如下步骤来恢复其相应的明文：

1)找到所有的一阶线性化方程。

找到所有的线性化方程等价于找到所有一阶线性化方程的系数向量所张成的线性空间的一组基。

式(3)的系数个数为n(n+l)+2n+l+ 1个。因此，可利用公钥随机生成略多于n(n+l)+2n+l+1个明文/密文对，代入式(3)，求解以线性化方程系数为未知数线性方程组，即可得到式(4)。若使用一般的高斯消元，该步骤的计算复杂度为(n×(n+l)+2n+l+1)3次域k上的运算。

实验结果表明，当n=73，l=2，t=3时，D=50，该步骤的计算复杂度为238次域k上的运算；n=103，l=2，t=3时，D=70，该步骤的计算复杂度为242次域k上的运算。

2)获取明文变量之间的线性关系。

实验结果表明，当n=73，l=2，t=3时，D′=50，h=25；n=103，l=2，t=3时，D′=70，h=35。

3)得到等价的Square加密体制。

将步骤2)中获得的明文变量线性关系代入公钥多项式或式(1)中，可消去D′个明文变量，再对消元后的方程组进行高斯消元，可得到等价的Square加密体制，而消元后方程组左边为对应的合法密文。

实验结果表明，当n=73，l=2，t=3时，等价的Square体制的明文变量和密文变量个数均为25；n=103，l=2，t=3时，等价的Square体制的明文变量和密文变量个数均为35。

4)利用Square公钥加密体制的破解方案求得h个明文变量的值。

该步骤最耗时的部分是求线性映射L，根据文献[6]，该部分的计算复杂度为

实验结果表明，当q=31，n=73，l=2，t=3时，该步骤的计算复杂度约为233次域k上的运算；q=31，n=103，l=2，t=3时，该步骤的计算复杂度约为235次域k上的运算。

5)将步骤4)求得的明文值，代入到步骤2)获得明文变量间的线性关系，可恢复出剩余的明文，从而恢复出完成的明文

实验结果表明，当q=31，n=73，l=2，t=3时，找到线性化方程的时间为531.557 s，而恢复明文所花费的时间仅为16.611 s；q=31，n=103，l=2，t=3时，找到线性化方程的时间为8 504.909 s，而恢复明文所花费的时间仅为52.947 s。

以上攻击过程均在普通计算机上使用Magma软件实现，计算机配置为Intel(R)Core(TM)i3-2 330 M CPU@2.20GHz, 2.00 G RAM。

4 结束语

本文结合线性化方程方法和差分攻击方法破解了文献[13]提出的新的多变量公钥密码体制，并且通过计算机实验完整地实现了整个攻击过程。实验结果表明，攻击是有效的。

设计安全、高效的多变量公钥加密体制是目前多变量公钥密码研究的一个公开问题，需要考虑到所有的已有攻击方法，特别是要避免线性化方程的产生。

[1]SHOR P, ONG B S, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J].SIAM Rev, 1999, 41(2): 303-332.

[2]MATSUMOTO T, IMAI H.Public quadratic polynominaltuples for efficient signature-verification and messageencryption[C]//EUROCRYPT’88: Proceedings of International Conference on the Theory and Application of Cryptographic Techniques 1988.Heidelberg: Springer, 1988.

[3]PATARIN J.Hidden fields equations (hfe)and isomorphisms of polynomials (IP): Two new families of asymmetric algorithms[C]//Eurocrypt'96: Proceedings of International Conference on the Theory and Application of Cryptographic Techniques 1996.Heidelberg: Springer, 1996.

[4]CLOUGH C, BAENA J, DING J, et al.Square, a new multivariate encryption scheme[C]//CT-RSA 2009:Cryptographers’ Track at the RSA Conference 2009.Heidelberg: Springer, 2009.

[5]PATARIN J.Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt'88[C]//Eurocrypt'95:Proceedings of International Conference on the Theory and Application of Cryptographic Techniques 1995.Heidelberg:Springer, 1995.

[6]BILLET O, GILLES M R.Cryptanalysis of the square crypto systems[C]//ASIACRYPT 2009: Proceedings of Annual International Conference on the Theory and Applications of Cryptology and Information Security 2009.Heidelberg: Springer, 2009.

[7]CLOUGH C, DING J.Secure variants of the square encryption scheme[C]//PQCrypto 2010: Proceedings of International Conference on Post-Quantum Cryptography 2010.Heidelberg: Springer, 2010.

[8]THOMAE E, WOLF C.Roots of square: Cryptanalysis of double-layer square and square+[C]//PQCrypto 2011:Proceedings of International Conference on Post-Quantum Cryptography 2011.Heidelberg: Springer, 2011.

[9]WANG L, YANG B, HU Y, et al.A “medium-field”multivarite public-key encryption scheme[C]//CT-RSA 2006:Cryptographers’ Track at the RSA Conference 2006.Heidelberg: Springer, 2006.

[10]MOH T T.A fast public key system with signature and master key functions[J].Comm in Algebra, 1999, 27:2207-2222.

[11]DING J, HU L, NIE X, et al. High order linearization equation (HOLE)attack on multivariate public key cryptosystems[C]//PKC 2007: Proceedings of International Conference on the Theory and Practice of Public-Key Cryptography 2007.Heidelberg: Springer, 2007.

[12]刘梦娟, 聂旭云, 胡磊, 等.线性化方程方法破解TTM公钥加密体制[J].电子科技大学学报, 2010, 39(2):293-297.LIU Meng-juan, NIE Xu-yun, HU Lei, et al.Linearization equation attack on TTM public key cryptosystems[J].Journal of University of Electronic Science and Technology of China, 2010, 39(2): 293-297.

[13]YUAN F, SUN Y, JIANG J, et al.A multivariate public key cryptographic scheme[J].Communications China, 2014,11(12): 120-124.