魯 剛，聶旭云,3，秦志光，侯川勇

(1.電子科技大學(xué)信息與軟件工程學(xué)院 成都 610054；2.中國(guó)科學(xué)院信息工程研究所信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京 海淀區(qū) 100093；3.網(wǎng)絡(luò)與數(shù)據(jù)安全四川省重點(diǎn)實(shí)驗(yàn)室 成都 610054)

公鑰密碼學(xué)是現(xiàn)代化信息社會(huì)的一個(gè)重要工具。由于Shor的量子計(jì)算機(jī)攻擊[1]，基于大數(shù)分解和離散對(duì)數(shù)等數(shù)論困難問(wèn)題的傳統(tǒng)公鑰密碼體制的安全性受到了威脅，如RSA和ElGamal等。因此，有必要尋找基于其他困難問(wèn)題的公鑰密碼體制來(lái)替代RSA和ElGamal。

尋找可替代的公鑰密碼系統(tǒng)已有一些研究，多變量公鑰密碼體制也是其中一種。典型的多變量公鑰加密體制的設(shè)計(jì)方法主要有小域-大域方法和三角形逐步迭代方法兩種。

小域-大域方法是多變量公鑰密碼體制的公鑰映射定義在小域上，而中心映射定義在小域的某個(gè)擴(kuò)域上。比較典型的有MI體制[2]、HFE(隱藏域方程)體制[3]和Square體制[4]。原始的MI加密體制被文獻(xiàn)[5]利用線性化方程的攻擊方法破解了。HFE體制[3]自1996年提出之后，一直受到人們的關(guān)注，目前大量的研究集中在HFE抵抗解方程攻擊的復(fù)雜度估計(jì)以及合適的安全參數(shù)選擇。Square體制[4]其中心映射為奇特征有限域上的平方函數(shù)。原始的Square體制被文獻(xiàn)[6]利用差分攻擊破解。文獻(xiàn)[7]提出了雙層Square體制和Square+方案來(lái)抵擋差分攻擊。但是，文獻(xiàn)[8]對(duì)利用精煉的MinRank攻擊方法破解了這兩個(gè)體制。三角形逐步迭代方法指的是體制的中心映射可逐步迭代進(jìn)行求逆，其中較為典型的有MFE[9]、TTM[10]等。原始的MFE體制在2007年被文獻(xiàn)[11]利用二階線性化方程方法破解，因而是不安全的。TTM體制多數(shù)滿足線性化方程，也是不安全的[12]。目前，已有的多變量公鑰加密體制的安全性均有待研究。

2014年，文獻(xiàn)[13]提出了一種新多變量公鑰密碼體制，該體制結(jié)合了小域-大域方法和三角形逐步迭代方法，具有較高的加密和解密效率。雖然該體制滿足線性化方程，但是合適的參數(shù)選擇可以抵擋線性化方程攻擊，并且能夠抵擋秩攻擊和差分攻擊等。

通過(guò)理論分析和實(shí)驗(yàn)驗(yàn)證，本文結(jié)合線性化方程攻擊方法和差分攻擊方法給出了文獻(xiàn)[13]方案的破解，可恢復(fù)合法密文相應(yīng)的明文。首先利用線性化方程方法對(duì)文獻(xiàn)[13]公鑰進(jìn)行消元獲得與Square體制的等價(jià)方案，然后，利用差分攻擊找到該等價(jià)方案的等價(jià)密鑰，從而恢復(fù)合法密文相應(yīng)的明文。在普通PC機(jī)上，利用Magma實(shí)現(xiàn)并驗(yàn)證了破解的全過(guò)程。當(dāng)q=31，n=73，l=2，t=3時(shí)，給定公鑰，在計(jì)算復(fù)雜度為238次域GF(31)上運(yùn)算的預(yù)計(jì)算基礎(chǔ)上，恢復(fù)明文的計(jì)算復(fù)雜度約為233次域GF(31)上運(yùn)算；當(dāng)q=31，n=103，l=2，t=3時(shí)，給定公鑰，在計(jì)算復(fù)雜度為242次域GF(31)上運(yùn)算的預(yù)計(jì)算基礎(chǔ)上，恢復(fù)明文的計(jì)算復(fù)雜度約為235次域GF(31)上運(yùn)算。

1 預(yù)備知識(shí)

1.1 多變量公鑰密碼體制的一般形式

令K=Fq是一個(gè)q元域，n和m是兩個(gè)正整數(shù)。L1和L2分別是Kn和Km上的兩個(gè)隨機(jī)選取的仿射變換，為明文變量，為密文變量。令：

1.2 一階線性化方程

一階線性化方程形式如下：

線性化方程最早是Patarin提出用來(lái)破解MI體制，2007年，文獻(xiàn)[11]將該方法推廣提出了高階線性化方程方法，并用來(lái)破解MFE體制。

1.3 差分攻擊

公鑰多項(xiàng)式P在點(diǎn)a處的差分為：

作為一個(gè)二元映射DPa：是一個(gè)對(duì)稱雙線性映射。

利用公鑰函數(shù)差分的雙線性性，可對(duì)公鑰函數(shù)的構(gòu)造進(jìn)行分析。在多數(shù)情況下，差分攻擊明文空間的一個(gè)不變子空間用來(lái)恢復(fù)體制的私鑰。

1.4 Square公鑰加密體制

Square公鑰加密體制的中心映射為：

Square體制在2009年被差分攻擊破解[6]。

2 新多變量公鑰密碼體制簡(jiǎn)介

將φ:推廣為k-線性同構(gòu)

新的多變量公鑰加密函數(shù)P:kn→kn+l

，定義為：

1)F:Kt→Kt是該體制的中心映射，定義為：

3)T:為可逆仿射變換。

該多變量公鑰加密體制的公鑰為函數(shù)P的表達(dá)式，私鑰為兩個(gè)可逆仿射變換T和U。具體的加密、解密過(guò)程詳見(jiàn)文獻(xiàn)[13]。

為了抵擋現(xiàn)有攻擊，文獻(xiàn)[13]建議參數(shù)q=31，

3 新多變量公鑰密碼體制的破解

文獻(xiàn)[13]指出，該方案雖然滿足一階線性化方程，但是應(yīng)用線性化方程攻擊方法之后并不能得到破解該方案合法密文相應(yīng)的明文。同時(shí)該方案還可抵擋低秩攻擊和差分攻擊。

經(jīng)過(guò)理論分析和實(shí)驗(yàn)驗(yàn)證，本節(jié)提出將線性化方程和差分攻擊相結(jié)合的方法能夠恢復(fù)合法密文相應(yīng)的明文。

3.1 線性化方程

方程組(2)共包含t?1個(gè)方程，這些方程顯然是線性無(wú)關(guān)的。

為了找到所有的線性化方程，需要計(jì)算足夠多明密對(duì)，并將這些明密對(duì)代入式(3)得到以系數(shù)為未知數(shù)的線性方程組。令D為這個(gè)線性方程組解空間的維數(shù)，1≤m≤D}為其解空間的一組基。即得到了D個(gè)線性無(wú)關(guān)的一階線性化方程，記這組方程為：

以上步驟僅依賴于公鑰，與要破解的合法密文無(wú)關(guān)。因此對(duì)于給定公鑰，該步驟可以預(yù)計(jì)算。

3.2 惟密文攻擊

設(shè)該線性方程組的解空間為V′，維數(shù)為D′。解該方程組，可將D′個(gè)明文變量用其余h=n?D′個(gè)明文變量線性表出，記h個(gè)變量為將上述D′個(gè)表達(dá)式代入原公鑰中，可得到n+l個(gè)新的二次多項(xiàng)式，記為

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

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

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

當(dāng)t是偶數(shù)時(shí)，；當(dāng)t為奇數(shù)時(shí)，

文獻(xiàn)[6]中利用Square體制公鑰的差分性質(zhì)，成功地找到了該體制的私鑰，從而破解了該體制。

不失一般性，將消元后的公鑰函數(shù)寫成：

函數(shù)P在點(diǎn)a處的差分是指采用類似的符號(hào)，消元后的公鑰函數(shù)的差分映射為：

找到等價(jià)密鑰后，對(duì)于給定的合法密文，很容易恢復(fù)其相應(yīng)的明文。

3.3 具體的攻擊步驟及實(shí)驗(yàn)結(jié)果

給定新的多變量公鑰密碼體制的公鑰和一個(gè)待破解的合法密文，進(jìn)行如下步驟來(lái)恢復(fù)其相應(yīng)的明文：

1)找到所有的一階線性化方程。

找到所有的線性化方程等價(jià)于找到所有一階線性化方程的系數(shù)向量所張成的線性空間的一組基。

式(3)的系數(shù)個(gè)數(shù)為n(n+l)+2n+l+ 1個(gè)。因此，可利用公鑰隨機(jī)生成略多于n(n+l)+2n+l+1個(gè)明文/密文對(duì)，代入式(3)，求解以線性化方程系數(shù)為未知數(shù)線性方程組，即可得到式(4)。若使用一般的高斯消元，該步驟的計(jì)算復(fù)雜度為(n×(n+l)+2n+l+1)3次域k上的運(yùn)算。

實(shí)驗(yàn)結(jié)果表明，當(dāng)n=73，l=2，t=3時(shí)，D=50，該步驟的計(jì)算復(fù)雜度為238次域k上的運(yùn)算；n=103，l=2，t=3時(shí)，D=70，該步驟的計(jì)算復(fù)雜度為242次域k上的運(yùn)算。

2)獲取明文變量之間的線性關(guān)系。

實(shí)驗(yàn)結(jié)果表明，當(dāng)n=73，l=2，t=3時(shí)，D′=50，h=25；n=103，l=2，t=3時(shí)，D′=70，h=35。

3)得到等價(jià)的Square加密體制。

將步驟2)中獲得的明文變量線性關(guān)系代入公鑰多項(xiàng)式或式(1)中，可消去D′個(gè)明文變量，再對(duì)消元后的方程組進(jìn)行高斯消元，可得到等價(jià)的Square加密體制，而消元后方程組左邊為對(duì)應(yīng)的合法密文。

實(shí)驗(yàn)結(jié)果表明，當(dāng)n=73，l=2，t=3時(shí)，等價(jià)的Square體制的明文變量和密文變量個(gè)數(shù)均為25；n=103，l=2，t=3時(shí)，等價(jià)的Square體制的明文變量和密文變量個(gè)數(shù)均為35。

4)利用Square公鑰加密體制的破解方案求得h個(gè)明文變量的值。

該步驟最耗時(shí)的部分是求線性映射L，根據(jù)文獻(xiàn)[6]，該部分的計(jì)算復(fù)雜度為

實(shí)驗(yàn)結(jié)果表明，當(dāng)q=31，n=73，l=2，t=3時(shí)，該步驟的計(jì)算復(fù)雜度約為233次域k上的運(yùn)算；q=31，n=103，l=2，t=3時(shí)，該步驟的計(jì)算復(fù)雜度約為235次域k上的運(yùn)算。

5)將步驟4)求得的明文值，代入到步驟2)獲得明文變量間的線性關(guān)系，可恢復(fù)出剩余的明文，從而恢復(fù)出完成的明文

實(shí)驗(yàn)結(jié)果表明，當(dāng)q=31，n=73，l=2，t=3時(shí)，找到線性化方程的時(shí)間為531.557 s，而恢復(fù)明文所花費(fèi)的時(shí)間僅為16.611 s；q=31，n=103，l=2，t=3時(shí)，找到線性化方程的時(shí)間為8 504.909 s，而恢復(fù)明文所花費(fèi)的時(shí)間僅為52.947 s。

以上攻擊過(guò)程均在普通計(jì)算機(jī)上使用Magma軟件實(shí)現(xiàn)，計(jì)算機(jī)配置為Intel(R)Core(TM)i3-2 330 M CPU@2.20GHz, 2.00 G RAM。

4 結(jié)束語(yǔ)

本文結(jié)合線性化方程方法和差分攻擊方法破解了文獻(xiàn)[13]提出的新的多變量公鑰密碼體制，并且通過(guò)計(jì)算機(jī)實(shí)驗(yàn)完整地實(shí)現(xiàn)了整個(gè)攻擊過(guò)程。實(shí)驗(yàn)結(jié)果表明，攻擊是有效的。

設(shè)計(jì)安全、高效的多變量公鑰加密體制是目前多變量公鑰密碼研究的一個(gè)公開(kāi)問(wèn)題，需要考慮到所有的已有攻擊方法，特別是要避免線性化方程的產(chǎn)生。

[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]劉夢(mèng)娟, 聶旭云, 胡磊, 等.線性化方程方法破解TTM公鑰加密體制[J].電子科技大學(xué)學(xué)報(bào), 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.