一種優(yōu)化的多變量加密方案*

趙菲菲，魏仕民

(淮北師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，安徽淮北235000)

量子計(jì)算機(jī)的發(fā)展對(duì)目前廣泛使用的公鑰密碼體制構(gòu)成了潛在的威脅。而多變量公鑰密碼體制被認(rèn)為是能抵御未來(lái)基于量子計(jì)算機(jī)攻擊的幾種公鑰密碼體制之一，其安全性基于有限域上求解多變量多項(xiàng)式方程組為一NP-C問(wèn)題。體制具有較高的效率和安全性，且易于硬件實(shí)現(xiàn)，因此被認(rèn)作量子計(jì)算機(jī)時(shí)代一種安全的密碼體制和數(shù)字簽名備選方案。

多變量公鑰密碼體制代數(shù)結(jié)構(gòu)龐大。設(shè)F為有限域，公鑰P=T°Q°S:Kn→Km(符號(hào)°表示映射的合成)。其中，S:u→x=MSu+CS∈Aff－1［Kn］，T:y→v=MTy+CT∈Aff－1［Km］分別為 Kn、Km上隨機(jī)選取的可逆仿射變換，MS、MT分別是F上的n階矩陣，CS、CT是F上的n維向量。它們共同掩藏中心映射Q的結(jié)構(gòu)，是私鑰的重要部分。

中心映射Q，也稱核映射，構(gòu)成中心映射的方程成為中心方程，它是n個(gè)變量m個(gè)多項(xiàng)式組成的方程組:

Q(x1，x2，…，xn)→(q1(x1，x2，…，xn)，q2(x1，x2，…，xn)，…，qm(x1，x2，…，xn))，Q 的結(jié)構(gòu)可以公開(kāi)也可以保密，三元組(T，Q，S)為私鑰，對(duì)應(yīng)的公鑰即為:

1 MFE加密方案及其相關(guān)問(wèn)題

1.1 MFE 加密方案

設(shè)K為有限域，L為其r次擴(kuò)域，即中等擴(kuò)域“Medium Field”。定義K-線性同構(gòu)π:L→Kr，即取L在K上的一組基［θ1，θ2，…，θr］，則 π 為:π［a1θ1+a2θ2+ … +arθr］=［a1，a2，…，ar］，a1，a2，…，ar∈K。

自然地可推得兩個(gè)K-線性同構(gòu)π1:L12→K12r和π2:L15→K15r。MFE的私鑰由定義在K12r和K15r上的兩個(gè)可逆仿射變換 Φ1和 Φ3構(gòu)成。Φ2:L12→L15為中心映射。中心映射 Φ2:［X1，X2，…，X12］=［Y1，Y2，…，Y15］表達(dá)如下:

其中Q1，Q2，Q3構(gòu)成一個(gè)三元組［Q1，Q2，Q3］，為K4r到自身的三角形映射。加密是對(duì)公鑰方程組賦值的過(guò)程，解密則依次計(jì)算 φ－11°π1°φ－12°π－12°φ－13。關(guān)鍵是計(jì)算 φ－12，可通過(guò) φ2的三角結(jié)構(gòu)來(lái)解決。首先將 X1，X2，…，X12，Y1，Y2，…，Y15寫(xiě)成 6 個(gè) 2 階矩陣:

依次令為 M1，M2，M3，Z1，Z2，Z3，，則中心映射對(duì)應(yīng)即:Z1=M1M2，Z2=M1M3，Z3=M1M4，則有:

當(dāng) M1，M2，M3均可逆，已知密文 Y4，Y5，…，Y15，由式(1)可分別得到 det M1，det M2，det M3，再由式(1)中的前3個(gè)等式可得X1，X2，X3，進(jìn)而由det M1式求出X4。進(jìn)而令A(yù)=(det M1)－1，則:

1.2 SOLE 攻擊方法

設(shè)M*是二階矩陣M的伴隨矩陣。由:

方程關(guān)于明文分量ui為線性，密文分量vj是二次。故稱之為二階線性化方程Second Order Linearization Equation，簡(jiǎn)稱 SOLE。

在唯密文攻擊時(shí)，首先將足夠多明密文對(duì)代入式(3)，確定出線性獨(dú)立的SOLEs，然后代入已知的密文分量，通過(guò)Gauss消元法減少明文分量，再代入原公鑰方程，得到具有較少變量數(shù)的新的公鑰方程組。當(dāng)明文分量的個(gè)數(shù)足夠小時(shí)，就利用Grobner基的方法求出明文值。

2 改進(jìn)的MFE加密方案及其方案分析

2.1 改進(jìn)的MFE加密方案

類似的，K為特征為2的基域，L為擴(kuò)域。兩個(gè)K-線性同構(gòu)和。重新定義中心映射:

把式(6)代入式(4)前3個(gè)等式里，可求出 X1，X2，…，X3，再由求出 X4，余下的等式求出 X5，X6，…，X12，令

2.2 性能分析

(1)任何一個(gè)MPKC都將擁有一種不同的中心映射，而中心映射Q:Fn→Fm并非一定為雙射，為確定唯一原像可采用一些技巧，即先由一個(gè)固定的擴(kuò)展函數(shù)或Hash函數(shù)將明文增加一個(gè)冗余，改進(jìn)方案經(jīng)過(guò)如下擴(kuò)展:

然后又具體到一般，將其總結(jié)，得到一般的明文長(zhǎng)度為4n(n≥3)的高次MFE加密方案，同時(shí)得到的擴(kuò)展的長(zhǎng)度為2n2－n(n≥3)，這樣就可以保證密文得到唯一的原文。

(2)在特征為2的域上進(jìn)行乘、逆運(yùn)算時(shí)，常常把域擴(kuò)張看成冪形式的二次擴(kuò)張。擴(kuò)張的次數(shù)越多，該域上計(jì)算量也呈非線性的增大。由于新方案是由五次多變量多項(xiàng)式方程組構(gòu)成，因而可取更小的域K和L。密鑰大小:設(shè)n=12r，m=15r，私鑰即映射φ1，φ3及Qi中方程的系數(shù)，約n2+m2。公鑰大小為公鑰方程φ2的系數(shù)量。雖然新方案的公鑰長(zhǎng)度有所增加，但是可以取更小的參數(shù)r和K使運(yùn)算在更小的域上進(jìn)行，就可以在一定程度上平衡由于公鑰量的增大所帶來(lái)的開(kāi)銷，同時(shí)可進(jìn)一步提高其運(yùn)算速度。

2.3 安全性分析

2.3.1 SOLE 攻擊

在式(3)中的二階線性化方程，關(guān)于密文分量為二次，明文分量為一次，因此等式中應(yīng)包含中某兩個(gè)的乘積。不妨設(shè)等式左端包含，即:

2.3.2 秩攻擊

秩攻擊包括高秩攻擊、低秩攻擊和分離的油醋攻擊。它們都是MQ方案基陷門(mén)STS或UOV的基本攻擊。其中高秩攻擊和低秩序攻擊的基本思想是將公鑰方程的二次項(xiàng)部分寫(xiě)成對(duì)稱矩陣的形式，通過(guò)尋找具有某些特殊秩的矩陣的線性組合來(lái)恢復(fù)私鑰。但是新方案公鑰方程為五次，目前為止還無(wú)有效辦法把五次項(xiàng)轉(zhuǎn)化為對(duì)稱矩陣的形式。因此秩攻擊無(wú)效。

2.3.3 Grobner基攻擊

求解一族多變量方程組的經(jīng)典算法是構(gòu)造Grobner基利用Buchberger算法來(lái)解決。該算法是按一定次序?qū)雾?xiàng)式排序，通過(guò)適當(dāng)系數(shù)的兩個(gè)多項(xiàng)式將首項(xiàng)單項(xiàng)式消掉，不斷執(zhí)行該過(guò)程進(jìn)行消元，直至最后一個(gè)變量。但隨著消項(xiàng)過(guò)程的不斷進(jìn)行剩余單項(xiàng)式的次數(shù)將急速增長(zhǎng)。分析表明，該算法復(fù)雜度平均為單指數(shù)級(jí)，最差達(dá)到雙指數(shù)級(jí)，故僅適用于中等數(shù)值個(gè)變量。盡管目前對(duì)高次方程組算法復(fù)雜度尚不清楚。

3 結(jié)論

MFE是第一個(gè)定義在較小域上的MPKC，因此相對(duì)于以往定義在大域的體制來(lái)說(shuō)具有更快的加密體制，遺憾的是其中心映射不一定是雙射，而且不能抵抗SOLE攻擊和秩攻擊。在原有的基礎(chǔ)上，通過(guò)重新設(shè)計(jì)中心映射，提出一種改進(jìn)方案。新方案不僅能抵抗各種攻擊，而且對(duì)一定固定的明文長(zhǎng)度都可以進(jìn)行加密，安全性更高，保證了可以確定唯一原像。同時(shí)如果能使公鑰方程組為稀疏多項(xiàng)式，則更能有效的減少公鑰大小，進(jìn)一步提高算法效率。

［1］王鑫，張美玲，王新梅.高次MFE多變量加密方案［J］.四川大學(xué)學(xué)報(bào):工程科學(xué)版，2009，41(4):171-174

［2］王志偉，鄭世慧，楊義先，等.改進(jìn)的Medium-Field多變量公鑰加密方案［J］.電子科技大學(xué)學(xué)報(bào)，2007，36(6):1152-1159

［3］呂文剛，王尚平.MFE多變量加密方案研究［D］.西安:西安理工大學(xué)

［4］DOUGLASR S.Cryptography Theory and Practice Third Edition［M］.Canada:Electronics Industry，2011

［5］萬(wàn)哲先.代數(shù)和編碼［M］.3版.北京:高等教育出版社:2009

［6］王后珍，張煥國(guó)，管海明，等.多變量代數(shù)理論及其在密碼學(xué)中的應(yīng)用［J］.北京:北京工業(yè)大學(xué)學(xué)報(bào)，2010，36(5):627-634

［7］袁峰，胡予濮，歐海文，等.多變量公鑰密碼中等價(jià)密鑰問(wèn)題［J］.北京:北京郵電大學(xué)學(xué)報(bào)，2010，33(3):97-101

［8］孫小雁，張茂勝.多模式多變量公鑰密碼體制［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2012，33(11):4095-4099