多變量公鑰密碼的發(fā)展過程

多變量公鑰密碼的開展過程摘要：多變量公鑰密碼系統(tǒng)作為一種可替代RSA和ECC的可以抵抗量子攻擊的公鑰密碼體制，是近幾年的研究熱點。這種體制的平安性基于在有限域上求解多變量多項式方程組是NP-困難問題。關(guān)鍵詞：多變量公鑰密碼，代數(shù)攻擊1引言眾所周知，傳統(tǒng)的密碼體制如RSA和ECC，他們的平安性基于數(shù)論困難問題和離散對數(shù)問題的困難性。但是，量子計算機(jī)的開展對基于數(shù)論問題的密碼體制的平安性造成了本質(zhì)威脅，因為在量子計算機(jī)上存在著在多項式時間內(nèi)求解數(shù)論問題的方案。因此有必要去尋找更高效、更平安的公鑰密碼體制來代替?zhèn)鹘y(tǒng)密碼體制。多變量公鑰密碼系統(tǒng)將會是一種可能的選擇。多變量公鑰密碼的平安性是建立在求解有限域上隨機(jī)多變量多項式方程組是NP-困難問題的根底之上。多變量公鑰密碼的加密效率非常高，且能抵抗量子攻擊，因此成為近幾年的研究熱點。目前已經(jīng)構(gòu)造出了多種多變量公鑰密碼體制，其中有一些非常適用于計算能力有限的低耗設(shè)備上。2003年，一種多變量簽名體制，SFlash，被歐洲NESSIE密碼方案接受用于低耗智能卡的推薦算法。2多變量公鑰密碼的一般形式多變量公鑰密碼〔multivariatepublickeycryptosystem，MPKC〕的一般形式如下。令是一個有限域，和是正整數(shù)，和分別是和上的隨機(jī)選取的可逆放射變換。取映射為一個從到的容易求逆的非線性映射。令，其中是一個到的映射。它總可以被表示成有限域上個元多項式，其最高次數(shù)等于的次數(shù)。在多變量公鑰密碼系統(tǒng)中，的表達(dá)式設(shè)為公鑰，它是一組多變量多項式，而私鑰設(shè)為和的表達(dá)式。多變量密碼設(shè)計的關(guān)鍵在于構(gòu)造映射，后者稱為多變量密碼的中心映射。為了節(jié)省公鑰多項式的存儲，中心映射和公鑰多項式通常選取為最簡單的非線性函數(shù)，即二次函數(shù)。3MPKC的構(gòu)造現(xiàn)有的MPKC體制大致分為四類：1、MI；2、隱藏域方程〔HFE〕；3、油醋機(jī)制；4。、三角形機(jī)制。下面我們簡單的介紹這幾種體制。3.1MI密碼體制MI加密體制是Matsumoto和Imai在1988年提出的。它是第一個使用“小域-大域〞思想來構(gòu)造多變量公鑰密碼體制的方法。它的公鑰是小域上的多元多項式，而它的中心映射可以用的擴(kuò)域〔大域〕上的單項式來表示。令是特征為的有限域，是的次擴(kuò)域。在MI體制中，域上的元素與中的向量通過線性同構(gòu)等同看待，即我們?nèi)≡谏系囊唤M基，定義為，其中。MI的中心映射首先定義在域上，形式如下：，其中滿足和。這個條件是確保了是個可逆函數(shù)。事實上，假設(shè)是一個滿足的整數(shù)，那么可簡單的表示為。通過映射，不難將看成是從到自身的映射，即。3.2HFE密碼體制在破解了MI加密體制后，Patarin將MI體制的中心映射作了推廣，提出了“隱藏域方程〞體制。HFE的中心映射不再是一個大域上的單項式，而是一個多項式。HFE加密體制的中心映射定義在域上，形式如下：，其中系數(shù)為隨機(jī)選取的，限定和是為了滿足的次數(shù)小于某個參數(shù)的需求。HFE的解密需要在域上求解，這可以用Berlekamp算法的變型算法來求解。假設(shè)，那么這一步驟的復(fù)雜度為。因此，不能太大，也就是說和不能太大。3.3油醋機(jī)制油醋機(jī)制是patarin在1997年根據(jù)線性化方程的形式構(gòu)造出來的簽名體制。這個體制的關(guān)鍵是應(yīng)用了一種所謂的油醋多項式。令是一個含個元素的有限域。定義：設(shè)，我們稱如下形式的多項式為油醋多項式：，其中，稱為油變量，稱為粗變量。注意在油醋多項式中，假設(shè)給定醋變量的值，那么油醋多項式就轉(zhuǎn)變?yōu)殛P(guān)于油變量的一次多項式。油醋簽名體制的中心映射就有一組油醋多項式構(gòu)成。生成簽名時只需隨機(jī)選取一組醋變量的值，然后解一個關(guān)于油變量的線性方程組。3.4三角形體制現(xiàn)在的多變量公鑰密碼體制的構(gòu)造中，三角形體制是最特殊的一種，因為它們起源于代數(shù)幾何。馴順變換方法〔TTM〕密碼體制是一類著名的三角形體制，這一體制的動機(jī)是基于分解非線性可逆多項式映射的復(fù)合的困難性。一類著名的可逆三角形映射是deJonquires映射。一個deJonquires映射的形式如下：，其中是任意域，是任意多項式。這種映射的結(jié)構(gòu)比擬特殊，容易求逆，因而也稱為馴順變換。但是從密碼學(xué)的觀點來看，這種映射不能直接用于構(gòu)造MPKC，因為它滿足線性化方程。T．T．Moh基于這種映射構(gòu)造了很巧妙的新映射，并將其應(yīng)用在TTM體制當(dāng)中。其形式如下：，其中稱為鎖多項式，它們是次數(shù)大于2的多項式，但卻是的二次多項式。這種設(shè)計是使用鎖多項式來隱藏映射中的線性化結(jié)構(gòu)以防止線性化方程的出現(xiàn)。4MPKC的攻擊方法現(xiàn)有的針對多變量密碼體制的分析工具主要有以下幾種：線性化方程、XL算法、Grobner基方法、秩攻擊和差分攻擊。本節(jié)簡單介紹這幾種攻擊方法。4.1線性化方程線性化方程的攻擊方法最早是Patarin在1995年攻擊MI加密體制時提出的，所以線性化方程有時也稱為Patarin關(guān)系式。對于一個密碼體制，一個線性化方程是一個對任意合法密文及其相應(yīng)明文的分量成立的如下形式的恒等式：。分析一個多變量密碼體制是否存在線性化方程可從理論上直接分析其中心映射的構(gòu)造是否滿足線性化方程，也可以通過計算機(jī)試驗檢測其公鑰和明文分量之間是否滿足線性化方程。4.2XL算法和Grobner基方法XL算法和Grobner基算法都是解多元多項式方程組的方法，即解方程組。對于一個多變量公鑰密碼體制，一旦給定公鑰和一個合法密文就可以得到一個多元多項式方程組。所以自然就會想到去找一種算法能解一個多元多項式方程組。XL算法是2000年由Courtois等人推廣線性化方程方法提出來的解有限域上多元多項式方程組的一種算法。4.3秩攻擊秩攻擊的出發(fā)點是將MPKC的二次公鑰多項式用矩陣的形式表示，然后結(jié)合中心映射的構(gòu)造及矩陣的秩來進(jìn)行密碼分析。秩攻擊可分為以下三種形式：低秩攻擊；高秩攻擊；油-醋攻擊。4.4差分攻擊2005年，F(xiàn)ouque等人引入了差分攻擊來分析PMI加密體制。該攻擊有計算二次函數(shù)的雙線性型出發(fā)，找到一個明文空間的子線性空間，將公鑰限制在這個空間上可使得所有的內(nèi)部擾動項均變?yōu)槌?shù)，寵兒可以使用Patarin的線性化方程攻擊方法恢復(fù)給定合法密文的相應(yīng)明文。5結(jié)論多變量公鑰密碼被認(rèn)為是一種有希望替代傳統(tǒng)公鑰密碼的密碼體制。但是，隨著各種攻擊方法的提出，目前大局部多變量公鑰密碼體制均遭受到不同程度的攻擊。因此，有必要去尋找新的方法來設(shè)計多變量公鑰密碼，和尋找新的方法來增強(qiáng)多變量公鑰密碼的平安性。多變量公鑰密碼的開展帶動了代數(shù)攻擊方法的開展。代數(shù)攻擊方法不僅僅可以用于分析多變量公鑰密碼，還可以用來分析對稱密碼。對多變量公約密碼體制的研究能夠使我們熟悉各種代數(shù)攻擊工具，進(jìn)一步豐富密碼分析方法，推動整個密碼學(xué)領(lǐng)域的開展。參考文獻(xiàn)[1]W.Di±eandM.Hellman.Newdirectionsincryptography.IEEETransac-tionsonInformationTheory,22(6):644{654,1976.[2]R.Rivest,A.Shamir,andL.Adleman.Amethodforobtainingdigitalsignaturesandpublickeycryptosystems.CommunicationsoftheACM,21(2):120{126,1978.[3]P.Shor.Polynomial-timealgorithmsforprimefactorizationanddiscretelogarithmsonaquantumcomputer.SIAMRev.,41(2):303{332,1999.[4]L.Vandersypen,M.Ste?en,G.Breyta,C.Yannoni,M.Sherwood,andI.Chuang.ExperimentalrealizationodShor'squantumfactoringalgorithmusingnuclearmagneticresonance.Nature,414:883-887.2001.[5]O.Goldreich，S.Goldwasser,andS.Halevi.Public-keycryptosystemsfromlatticereductionproblem.AdvancesinCryptology-CRYPTO'97,LNCS,volume1294,pages112-131.Springer,1997.[6]J.Ho?tein,J.Pipher,andJ.Silverman.NTRU:aringbasedpublickeycryptosystem.Algorithmicnumbertheory-ANTSIII,LNCS,volume1423,pages267-288.Springer,1998.[7]R.M