多變量公鑰密碼

多變量公鑰密碼系統(tǒng)摘要量子計算機(jī)的出現(xiàn)對傳統(tǒng)公鑰密碼體制的平安構(gòu)成威脅，多變量公鑰密碼應(yīng)運(yùn)而生，并成為近年來密碼學(xué)的研究熱點(diǎn)之一。多變量公鑰密碼的平安性依賴于解多變量非線性多項式方程組的困難性，并且多變量公鑰密碼在存儲空間和執(zhí)行時間上比起傳統(tǒng)公鑰密碼體制具有明顯的優(yōu)勢。本文對多變量公鑰密碼系統(tǒng)進(jìn)行了學(xué)習(xí)與研究，總結(jié)了多變量公鑰密碼學(xué)的開展歷史和研究現(xiàn)狀，對陷門函數(shù)的構(gòu)造做了簡要介紹，并闡述了針對多變量公鑰密碼體制的主要攻擊方法。關(guān)鍵詞：公鑰密碼數(shù)字簽名多變量AbstractTheappearanceofthequantumcomputerisathreattothesecurityoftraditionalcryptosystems,sothemultivariablecryptographywasborn,andattractedmoreandmoreattentionsrecently.Themultivariatepublickeycryptosystemsareconnectedtothehardnessofsolvingrandomlychosensystemsofmultivariatepolynomialequationsoverafinitefield,andithasbetterperformancebothinmemoryspaceandtimeefficiencythanthetraditionalcryptosystems.ThispaperdoessomestudyandresearchontheMPKCs,sumsupthedevelopmenthistoryandresearchsituation,doesabriefintroductiontotheimplementationoftrapdoorfunctions,andpresentsthemainattacks.Onthisbasis,themaincontributionsareasfollows.Keyword:PublickeycryptographySignatureMultivariate一、研究多變量公鑰密碼系統(tǒng)的背景及意義信息平安技術(shù)是一門綜合的學(xué)科，它涉及信息論、計算機(jī)科學(xué)、密碼學(xué)等多方面的知識，它的主要任務(wù)是研究計算機(jī)系統(tǒng)和通信網(wǎng)絡(luò)內(nèi)信息的保護(hù)方法以實(shí)現(xiàn)系統(tǒng)內(nèi)信息的平安、保密、真實(shí)和完整。而密碼技術(shù)那么是信息平安技術(shù)的核心，它是實(shí)現(xiàn)信息的保密性、完整性、不可否認(rèn)性的關(guān)鍵。通常情況下，在一個完整的密碼系統(tǒng)里，把沒有加密的消息稱為明文，用m表示；把所有可能明文消息的有限集合稱為明文空間，用M來表示；把加密后的消息稱為密文，用c表示，把所有可能密文消息的有限集合稱為密文空間，用C來表示；把將明文變換成密文的過程稱為加密變換，用E來表示；將密文恢復(fù)成明文的過程稱為解密變換，用D來表示；加密變換和解密變換是一對逆變換，它們通常是在一組密鑰的控制下進(jìn)行的，密鑰分別稱為加密密鑰和解密密鑰，分別用QUOTE
和QUOTE
來表示，所有可能密鑰的有限集合稱為密鑰空間，用K表示。那么加密過程可記為：QUOTE
式(1-1)解密過程可記為：QUOTE
式(1-2)密碼體制就是完成加密和解密功能的密碼方案，從原理上可分為兩大類：單鑰體制和公鑰體制，或稱為對稱密碼體制和非對稱密碼體制。單鑰體制的根本特征是加密密鑰和解密密鑰相同。單鑰體制對明文消息的加密有兩種方式：一是明文消息按字符逐位地加密，稱為流密碼；另一種是將明文消息分組，逐組地進(jìn)行加密，稱為分組密碼。采用單鑰體制的系統(tǒng)的保密性主要取決于密鑰的保密性，與算法的保密性無關(guān)，也就是由密文和加解密算法不可能得到明文。密鑰產(chǎn)生、分配、存儲、銷毀等問題，統(tǒng)稱為密鑰管理。密鑰管理是影響系統(tǒng)平安的關(guān)鍵因素。單鑰體制不僅可以用于數(shù)據(jù)加密，還可以用于消息的認(rèn)證。單鑰密碼體制可以在一定程度上解決保密通信的問題，但隨著信息技術(shù)的飛速開展，保密通信的需求越來越廣泛，單鑰密碼體制在密鑰管理上的困難性、陌生人間保密通信和數(shù)字簽名上的局限性等問題就逐漸表現(xiàn)了出來。在美國密碼學(xué)者WhitfieldDiffie和MartinHellman發(fā)表的論文“密碼學(xué)的新方向〔NewDirectionsinCryptography〕〞[1]中，首次提出了公鑰密碼體制的新思想，為解決傳統(tǒng)經(jīng)典密碼學(xué)中面臨的諸多難題提供了一個新的思路。在公鑰密碼體制中，加密密鑰與解密密鑰不同，對應(yīng)的形成一個密鑰對，用戶用其中一個密鑰加密的結(jié)果，可以用另外一個密鑰來解密。加密密鑰公之于眾，誰都可以使用，稱為公鑰；而解密密鑰只有解密人自己可以知道，稱為私鑰。公鑰密碼體制可以實(shí)現(xiàn)經(jīng)多個用戶加密的消息由一個用戶來解讀，或者由一個用戶加密的消息多個用戶可以解密。前者可以在公共網(wǎng)絡(luò)中實(shí)現(xiàn)保密通信，而后者可用于實(shí)現(xiàn)對用戶的認(rèn)證。公鑰密碼體制的出現(xiàn)在密碼學(xué)史上是迄今為止最大而且是唯一真正的革命。在公鑰密碼體制出現(xiàn)之前，幾乎所有的密碼編碼體統(tǒng)，不管是手工計算的還是計算機(jī)或機(jī)械設(shè)備實(shí)現(xiàn)的，都采用根本的代替和換位方法。而公鑰密碼體制的出現(xiàn)為密碼學(xué)的開展提供了新的理論和技術(shù)根底，一方面公鑰密碼算法基于數(shù)學(xué)函數(shù)；另一方面公鑰密碼體制由兩個不同的密鑰形成一個密鑰對，一個歸密鑰擁有者自己管理，不涉及分發(fā)問題，另一個可以公開，并可以基于公開渠道分發(fā)。密鑰對的使用對保密性、密鑰分配、認(rèn)證等都有著重要而深刻的意義。隨著公鑰密碼的迅速開展，涌現(xiàn)出了大量公鑰密碼算法，大致可以劃分為兩類：其一是基于大整數(shù)因子分解和基于離散對數(shù)問題的公鑰密碼算法，如RSA[2],Diffie-Hellman[7],ElGamal[3]，ECC[4,5]和大量基于身份的加密算法等。其二是新型快速公鑰密碼算法，如橢圓曲線公鑰密碼，格公鑰，多變量公鑰密碼[1]等。前者中基于大整數(shù)因子分解的RSA是目前應(yīng)用與研究的最廣泛的公鑰算法，它是由美國MIT的三名數(shù)學(xué)家R.Rivest，A.Shamir和L.Adleman于1978年提出的，該算法以兩個大素數(shù)的乘積作為算法的公鑰來加密消息，而密文的解密必須知道相應(yīng)的兩個大素數(shù)?？梢奟SA算法的平安性完全依賴于對大數(shù)分解問題困難性的推測上，隨著人類計算能力的不斷提高和自分解算法的進(jìn)一步改良，RSA算法為了保證其平安性，就必須增加模數(shù)的長度?，F(xiàn)在公認(rèn)的RSA模數(shù)有2048比特長才相對平安。這樣對于像智能卡這樣計算能力和存儲能力有限的小設(shè)備來說是不能容忍的，并且隨著現(xiàn)代網(wǎng)絡(luò)的快速開展，各種無線網(wǎng)絡(luò)越來越受到重視，而這些計算復(fù)雜度較高的算法是無法應(yīng)用到這些資源受限的環(huán)境中去的。此外，量子計算的開展對基于大整數(shù)因子分解和離散對數(shù)問題的算法造成了極大的威脅，特別是PeterShor于1995年提出了一種量子分解算法[6]，它能夠利用量子計算機(jī)在多項式時間內(nèi)解決大整數(shù)因子分解和離散對數(shù)問題。2007年中國科技大學(xué)潘建偉教授等與英國牛津大學(xué)的研究人員合作，在國際上首次利用光量子計算機(jī)演示了Shor的算法，雖然僅僅實(shí)現(xiàn)的是15=3×5這一非常簡單的質(zhì)因子分解，但這預(yù)示著，一旦量子計算機(jī)問世，基于大整數(shù)因子分解和基于離散對數(shù)問題的傳統(tǒng)公鑰密碼體制將受到嚴(yán)重的威脅。這就提出了一個新的問題，那就是如何能夠構(gòu)造出新的公鑰密碼體制，使其能夠抵御基于未來量子計算機(jī)的攻擊方法。在新型的快速公鑰密碼算法中，多變量公鑰密碼就是能夠抵抗未來基于量子計算機(jī)攻擊方法的體制之一。在最近十幾年中，多變量公鑰密碼受到越來越多的關(guān)注，已經(jīng)成為了研究的熱點(diǎn)。它的平安性根底是求解有限域上的多元多項式方程組，大多是二次多項式，而這一問題已經(jīng)被證明是NP-困難問題[1]，其詳細(xì)證明可參見文獻(xiàn)[8]。此外，由于多變量公鑰密碼多是在小的有限域上進(jìn)行運(yùn)算，因此要比基于數(shù)論的傳統(tǒng)密碼體制在計算上更加高效。迄今為止，已經(jīng)出構(gòu)造出了許多的多變量公鑰密碼體制，例如Matsumoto-Imai公鑰密碼體制及其變體、Oil-Vinegar公鑰密碼體制及其變體、HFE公鑰密碼體制及其變體、TTS及其變體等，其中有一些可適用于計算能力有限的設(shè)備，如無線傳感器網(wǎng)絡(luò)、射頻識別(RFID)標(biāo)簽和智能卡等。事實(shí)上，SFlash[9,10]，一個多變量簽名方案，已經(jīng)被歐洲NESSIE(NewEuropeanSchemesforSignatures,IntegrityandEncryption)作為用于低耗智能卡的歐洲平安標(biāo)準(zhǔn)被接受[11]。多變量公鑰密碼系統(tǒng)的研究始于20世紀(jì)80年代中期，1988年，Matsumoto和Imai提出了第一個多變量公鑰方案，即著名的MI加密體制[12]。該體制將“小域-大域〞思想引入了多變量公鑰密碼方案的設(shè)計當(dāng)中。然而，原始的MI加密體制于1995年被證明是不平安的，Patarin用一種線性化方程的攻擊方法[13]破解了原始的MI體制。隨后，Patarin改良了MI體制，提出了HFE密碼體制[14]，這個體制也受到了各種方法的攻擊。1997年，Patarin受到線性化方程攻擊的啟發(fā)，又提出了油-醋〔Oil-Vinegar〕簽名體制[15]。此外，在所有現(xiàn)存的多變量公鑰密碼系統(tǒng)中，還存在一種三角形體制，該體制的起源可以追溯到1986年Fell和Diffie的工作[16]。近十年來，人們在根本的多變量公鑰密碼體制的根底上，通過許多變形的方法設(shè)計出平安性有所提高的多變量方案。較為典型的變形方法有：加方法[17]、減方法[18]、醋變量方法[19]以及內(nèi)部擾動方法[20,21]等，其中減方法和醋變量方法主要用于設(shè)計數(shù)字簽名方案，內(nèi)部擾動方法那么是由丁津泰提出的一種系統(tǒng)化的增強(qiáng)多變量公鑰密碼平安性的方法。較為著名的變形后的方案有：附屬于MI減體制的SFlash簽名體制、Rainbow簽名體制[34]、對MI體制進(jìn)行內(nèi)部擾動的變體PMI[20]、對HFE體制進(jìn)行內(nèi)部擾動的變體IPHFE[21]等。最近，Tsujii，Tadaki和Fujita提出了一種與內(nèi)部擾動方法類似的PieceinHand(PH)方法[22,23]用來加強(qiáng)多變量公鑰密碼的平安性，這種方法所使用的思想與內(nèi)部擾動方法類似。近幾年還出現(xiàn)了概率化多變量密碼體制，即在多變量公鑰體制中應(yīng)用概率驗證的思想，以及利用多變量多項式構(gòu)造哈希函數(shù)等。目前，從嚴(yán)格的理論上來說，并沒有公認(rèn)的既平安又高效的多變量公鑰加密體制，相對較為平安的如PMI+[24]〔即結(jié)合了內(nèi)部擾動和加變形對PMI進(jìn)行改造〕。而平安高效的多變量簽名體制的設(shè)計那么相對要容易一些，比方TTS簽名體制[25]、TRMS[26,27]。大多數(shù)的方案，例如前邊提到的SFlash簽名方案、PMI、IPHFE等均已被各種方法攻破。比擬常見的攻擊方法大致有：窮舉搜索，差分攻擊，解非線性方程，秩攻擊以及Patarin的線性化方程方法等，其中解非線性方程主要是XL算法和Gr?bner基算法，而秩攻擊包括高秩、低秩以及別離Oil和Vinegar變量攻擊，這些攻擊方法將在本文的2.5節(jié)中詳細(xì)介紹。目前，對多變量公鑰系統(tǒng)的研究還遠(yuǎn)遠(yuǎn)不夠成熟，大量的科研工作者正投入努力。一方面，多變量公鑰的高效率一直吸引著人們?nèi)ピO(shè)計更平安和更實(shí)用的加密體制。另一方面，雖然多變量公鑰密碼體制的效率較高，但相比于傳統(tǒng)的公鑰密碼體制，多變量公鑰具有密鑰量較大的缺點(diǎn)。因此密鑰量較小的多變量體制的設(shè)計也是一個具有吸引力的方向。此外，對多變量公鑰密碼系統(tǒng)的研究熱點(diǎn)還表達(dá)在對概率化方法的改良、對內(nèi)部擾動變形的分析等。二、多變量公鑰密碼系統(tǒng)公鑰密碼體制是信息平安的一個重要工具。傳統(tǒng)的公鑰密碼體制，如RSA、ElGamal等的平安性依賴于數(shù)論的困難問題，即大整數(shù)的因子分解和離散對數(shù)問題。多變量公鑰密碼體制[1](MPKC)的平安性那么依賴于求解多變量非線性多項式方程組的困難性。本章將對多變量公鑰密碼系統(tǒng)所涉及的根底知識做簡要的介紹，并對其一般形式、陷門構(gòu)造、密碼學(xué)分析方法等進(jìn)行了簡要的概括?！惨弧掣字R為了嚴(yán)謹(jǐn)且有條理地闡述本文的研究成果，有必要對一些重要的根底知識做簡單的介紹，同時引入一些相關(guān)符號。在后續(xù)的章節(jié)中，如果不做特殊說明，符號代表的意義與本節(jié)定義的相同。1.有限域多變量公鑰密碼學(xué)基于有限域上的多變量多項式方程組，所以本小節(jié)簡要介紹有限域的根本知識。定義2.1(群)設(shè)G是非空集合，并在G內(nèi)定義了一種代數(shù)運(yùn)算(+)，假設(shè)滿足下述條件，那么稱G構(gòu)成一個群。具有封閉性。即對任意的a,b∈G,恒有a+b∈G。結(jié)合率成立。即對任意的a,b,c∈G,有(a+b)+c=a+(b+c)。集合G中有一個恒等元e存在。即對任意的a∈G,有e∈G,使得a+e=e+a=a。對任意的a∈G，存在a的逆元b∈G，使得a+b=e。定義2.2(Abel群)假設(shè)群G中，對于任意的a,b∈G,有a+b=b+a,那么稱G為交換群或者Abel群。定義2.3(域)非空元素集合k，假設(shè)在k中定義了兩種運(yùn)算：加法和乘法，并且滿足下述條件：k關(guān)于加法構(gòu)成Abel群，其加法恒等元記為0。k中除零元素外全體對乘法構(gòu)成Abel群，其乘法恒等元記為1。加法和乘法有如下分配律：a(b+c)=ab+ac(b+c)a=ba+ca那么成k是一個域。定義2.4(有限域)假設(shè)域k中只含有有限個元素，那么稱該域k為有限域，亦稱Galois(伽羅瓦域)。其中q為域中元素個數(shù)。域中元素的個數(shù)稱為有限域的階。q階有限域，常用GF(q)或Fq表示。定理2.1[22]每一個有限域的階必為素數(shù)的冪。定理2.2設(shè)k為q階的有限域，那么k中的非零元素可組成一個(q-1)次的乘法循環(huán)群。定義2.5(素域)設(shè)q是一個素數(shù)，集合k為{0,…,q-1}，加法和乘法運(yùn)算分別為取模q的整數(shù)加法和整數(shù)乘法運(yùn)算，那么稱k為一個素域。定義2.6(域上的多項式環(huán))含有一個未定元x的域k上的多項式定義為式(2-1)且用k[x]表示系數(shù)取自域k的一切多項式的集合，那么該集合關(guān)于多項式的加法和乘法構(gòu)成環(huán)。定義2.7(不可約多項式)設(shè)f(x)是次數(shù)大于零的多項式，假設(shè)除了常數(shù)和常數(shù)與本身的乘積以外，再不能被域上的其他多項式除盡，那么稱f(x)為域GF(q)上的不可約多項式。定義2.8(本原多項式)設(shè)f(x)是QUOTE
上的n次不可約多項式，如果滿足QUOTE
的最小正整數(shù)l為QUOTE
，那么稱f(x)為QUOTE
上的本原多項式。定理2.3設(shè)k為一個有限域，那么對于每個正整數(shù)n，k[x]中存在n次的不可約多項式。定義2.9(域的擴(kuò)張)設(shè)k是一個域，f(x)∈k[x]是一個n次既約多項式，以f(x)為模的剩余類的全體構(gòu)成一個環(huán)，稱為多項式剩余類環(huán)，記為QUOTE
，其中“加〞法運(yùn)算即為通常的多項式加法，“乘〞法運(yùn)算為多項式模多項式f(x)的乘法。那么稱K為一個多項式域，也稱之為基域k的n次擴(kuò)域。定義2.10(Frobenius自同構(gòu))設(shè)k是q階有限域，那么對任意的x∈k有QUOTE
，稱該映射為Frobenius映射。引理2.1使得為一個多項式映射，其中為上的最大總次數(shù)為1的多項式，又為形如的映射。那么映射，形式為：式(2-2)2.有限域上多元多項式方程組多元多項式方程組的一般形式設(shè)是有限域k上的n個變量，那么在域k上關(guān)于n個變量的某個多項式用fi表示，次數(shù)為d，m個這樣的多項式構(gòu)成一個多項式組，用F來表示。那么：其中所有的fi，形式如下：式(2-3)那么令是有限域k上的元素，定義多變量多項式方程組形式為：式(2-4)二次多變量多項式方程組當(dāng)多項式fi的次數(shù)d=2時，有限域k上的二次多變量多項式方程組被稱為二次多變量多項式方程組，一般形式如下：式(2-5)其中變量∈k，函數(shù)值∈k，為二次項系數(shù)，為一次項系數(shù)，為常數(shù)，且,,∈k。3.MQ-問題MQ(MultivariateQuadratic)-問題是指求解如下在域中的二次多項式方程組：式(2-6)其中fi為域k上的多項式方程，定義同式(2-5)中的fi。已經(jīng)證明MQ-問題是NP-困難問題，即使是最小的域也不例外[23,24]。因此MQ-問題成為了構(gòu)造有限域上公鑰密碼體制的重要工具?！捕扯嘧兞抗€密碼系統(tǒng)的一般形式多變量公鑰密碼系統(tǒng)(MultivariatePublicKeyCryptosystems，MPKC)具有如下一般形式：令k是一個有限域，n和m是正整數(shù)，L1和L2分別是和上隨機(jī)選取的可逆仿射變換。取映射F為一個從到的容易求逆的非線性映射。令式(2-7)其中表示映射的合成，是一個從到的映射。它總可以被表示成有限域k上m個n元多項式，形式如下：式(2-8)為域k上的n元多項式，其最高次數(shù)等于F的次數(shù)。公鑰在多變量公鑰密碼系統(tǒng)中，的表達(dá)式設(shè)為公鑰，即。私鑰一般情況下，私鑰為兩個可逆仿射變換L1和L2及映射F。F的結(jié)構(gòu)可以公開，也可以保密。加密過程給定明文消息，經(jīng)加密，得到密文，即對于有式(2-9)由于加密過程采用的是公鑰，那么任何人均可完成此過程。解密過程解密過程是通過私鑰計算的逆，對應(yīng)于每一個的逆，輸入密文，得到明文，即對于有式(2-10)由于計算需要得知私鑰，所以解密過程只能由擁有私鑰的人來完成。在多變量公鑰密碼系統(tǒng)中，映射F又稱為中心映射，是多變量公鑰密碼設(shè)計的關(guān)鍵。仿射變換L1用來隱藏明文變量，L2用來隱藏中心映射F的特殊結(jié)構(gòu)。為了節(jié)省公鑰多項式的存儲，中心映射F和公鑰多項式通常選取為最簡單的非線性函數(shù)——二次函數(shù)。〔三〕多變量公鑰密碼系統(tǒng)的分類目前，所有存在的多變量密碼系統(tǒng)(MPKCs)除了IP方案以外可以分成兩類：一類為雙極(bipolar)系統(tǒng)，一類為混合(mixed)系統(tǒng)。1.雙極系統(tǒng)(BipolarSystems)令k是一個有限域，，在一個雙極多變量公鑰系統(tǒng)中，密文由從到的映射給出，式(2-11)其中是中的n元多項式。從到的中心映射F的構(gòu)造過程如下：(1)，其中(2)對于任意的等式，式(2-12)可以很容易的解決。相應(yīng)的，能夠快速的找到唯一的原像。這里需要注意的是，僅僅意味著能夠找到原像，而不是說映射F是可逆的。一旦找到這樣的一個映射，那么加密過程就可以表示成由三個映射合成的組合映射：，式(2-13)其中L1是一個隨機(jī)選定的從到的可逆仿射變換，L2那么是一個隨機(jī)選定的從到的可逆仿射變換。公鑰雙極系統(tǒng)的公鑰包括兩個局部，其一是域k及其域結(jié)構(gòu)；其二是的m個多項式。私鑰私鑰包括L1和L2，映射F是否為私密鑰的一局部可視具體情況而定。圖2.1合成映射加密過程假設(shè)要加密明文消息，我們僅需要將其帶入公鑰多項式，計算，得到的即為加密后的密文。解密過程假設(shè)要解密一個密文消息，那么需要求解方程，式(2-14)這個求解，可以通過先求，然后計算，再計算就可以得到對應(yīng)的明文。簽名過程如果要對信息進(jìn)行簽名，只需求解方程，式(2-15)得到解，即運(yùn)行了一遍解密過程。驗證過程任何人只要將簽名代入等式，式(2-16)看是否相等即可驗證。雙極多變量系統(tǒng)的主要思想是引入L1和L2到達(dá)“隱藏〞或者“掩蓋〞映射F的目的，否那么映射F的求逆過程將會變得很容易。很多情況下映射F的選擇是相當(dāng)有限的，隨便選取的映射很容易被攻擊者獲知。這也就解釋了為什么有時候F是否做為秘鑰對體制的平安性來說并沒有本質(zhì)的影響。當(dāng)前，大多數(shù)多變量公鑰密碼系統(tǒng)都是雙極型的。2.混合系統(tǒng)(MixedSystems)一個混合型多變量公鑰方案使用從到的映射作為它的公鑰，即，式(2-17)其中每一個均為中的多項式。與雙極系統(tǒng)一樣，為了構(gòu)建這樣的一個方案，需要找到映射，即其中每一個均為中的多項式，并滿足以下條件：對于任意給定的，方程組，式(2-18)很容易求解。在多數(shù)情況下，式(2-18)是一個關(guān)于變量的線性方程組。對于任意給定的，方程組，式(2-19)很容易求解。式(2-19)是一組特別設(shè)計的非線性方程組。一旦找到這樣的映射，可以表示為如下的形式：，其中和的定義與雙極系統(tǒng)中的定義相同。L3是一個從到的線性映射。公鑰混合多變量公鑰系統(tǒng)的公鑰包括兩局部：其一是有限域k及其域結(jié)構(gòu)；其二是映射的l個多項式。私鑰私鑰局部包括線性可逆映射L1、L2和線性映射L3。方程根據(jù)不同的情況，可以是密鑰的一局部也可以是公鑰的一局部。加密過程如果要加密明文消息，可直接將其帶入式(2-17)中，并求解方程組，式(2-20)得到解，這個就是相應(yīng)的密文。解密過程假設(shè)要解密密文消息，應(yīng)先計算，令，再把代入式(2-19)中，并求解方程，式(2-21)得到方程的解，那么明文就由產(chǎn)生。簽名過程如果要對消息進(jìn)行簽名，執(zhí)行解密過程找到，那么即為消息的簽名。驗證過程任何人可以通過驗證是否滿足方程，式(2-22)來驗證簽名的合法性?；旌隙嘧兞抗€密碼系統(tǒng)的主要思想是用三個映射L1、L2和L3來隱藏方程，否那么在給定Y的情況下此方程的求解將變得很容易。與雙極系統(tǒng)一樣，隱藏H的結(jié)構(gòu)形式并不是必須的。目前，混合系統(tǒng)相對較少，其中Patarin的龍(Dragon)加密體制[25]較為有名。3.IP方案多項式同構(gòu)(IP)問題產(chǎn)生于對多變量公鑰系統(tǒng)的尋找密鑰攻擊，令，是兩個從到的多項式映射，即。式(2-23)IP問題就是尋找兩個可逆線性仿射變換上的和上的使得。式(2-24)這個問題和尋找一個多變量公鑰密碼系統(tǒng)的密鑰的攻擊密切相關(guān)，例如Matsumoto-Imai加密系統(tǒng)。IP密碼系統(tǒng)由Patarin首先提出[26]，驗證的過程就是通過尋找兩個不同映射的同構(gòu)來進(jìn)行的。一個簡化版的IP密碼方案為單密鑰IP(IP1s)，在這個方案中它只需要找到映射，因為找到的同時映射已經(jīng)確定?！菜摹扯嘧兞抗€密碼系統(tǒng)的根本構(gòu)造根據(jù)中心映射的種類，現(xiàn)有的多變量公鑰密碼體制的陷門構(gòu)造大體上可分為以下幾類：MI(Matsumoto-Imai)、隱藏域方程(HFE)、油醋(OV)、三角階梯(STS)體制。其中三角體制主要的代表有馴順變換方法(TTM)[26]，中間域方程(MFE)[27]和可解有理映射(TRMC)[28]等。在本節(jié)中，作者將對基于這幾種典型陷門構(gòu)造的體制做簡單的介紹。1.MI(Matsumoto-Imai)體制MI(Matsumoto-Imai)公鑰加密體制是由Matsumoto和Imai于1988年首先提出，并因此而得名，也稱為C*方案。設(shè)k一個特征為2的q階有限域，并且為n次不可約多項式。定義域為k的n次擴(kuò)域。一般情況下，這一條件對于以下的構(gòu)造并不是必要的。設(shè)是由K到k的k-線性同構(gòu)，由下式給出:。式(2-25)域K的子域k嵌入到的標(biāo)準(zhǔn)形式為：。式(2-26)選取，滿足且。定義域K上的映射為式(2-27)其中的限制條件是確保是一個可逆映射；事實(shí)上，如果t是一個整數(shù)，并且滿足：，式(2-28)那么就是。現(xiàn)在域上的映射F可以定義為：，式(2-29)其中。為了完成MI構(gòu)造的描述，現(xiàn)在再選擇域上的兩個可逆仿射變換和，域上的映射定義為：式(2-30)其中。圖2.2為描述MI根本構(gòu)造的映射圖。圖2.2MI構(gòu)造中的合成映射在MI算法中，公鑰由的n個多項式及有限域k的域結(jié)構(gòu)組成；私密鑰由、和組成。1995年，雖然MI體制被Patarin發(fā)現(xiàn)了其內(nèi)在的代數(shù)結(jié)構(gòu)并利用線性化方程的方法攻破，但該體制還是具有很重要的理論意義，它的出現(xiàn)是多變量公鑰體制開展的里程碑，它為這個領(lǐng)域帶來了全新的數(shù)學(xué)思想，其后來的多個變形版本得到了廣泛的研究并具有很大的潛力，如Flash簽名體制和PMI+加密體制，前者被NESSIE方案接收，后者具有較高的平安性。2.隱藏域方程(HFE)隱藏域方程(HiddenFieldEquations)體制是由Patarin推廣了MI體制的中心映射而提出的。由節(jié)的介紹可以看出，MI體制的中心映射采用的是擴(kuò)域上的一元單項式，而HFE的中心映射那么是擴(kuò)域上的多項式。根本的HFE構(gòu)造：設(shè)k為q階有限域，K為k的n次擴(kuò)域，不同于MI體制的是，HFE不要求域k的特征為2，假設(shè)是一個n次不可約多項式，那么。令為K到的標(biāo)準(zhǔn)k線性映射，即，，式(2-31)HFE的中心映射為式(2-32)其中是隨機(jī)選取的，和r2的選取要使得的次數(shù)小于參數(shù)d。公鑰多項式的合成為式(2-33)其中為kn上秘密的可逆仿射變換。在該體制中，公鑰包括域k及其結(jié)構(gòu)和映射，私鑰包括和兩個仿射變換。解密過程中，需要對求逆，可以用Berlekamp算法的變體求解，具體方法可參見文獻(xiàn)[29]中的第四章。由于求解的復(fù)雜度為，因此d不能太大。該體制當(dāng)時一度被認(rèn)為是最平安的多變量公鑰體制。后來這種體制被Kipnis和Shamir利用再線性化方法提出的密鑰恢復(fù)攻擊[30]攻破。為了抵抗陸續(xù)出現(xiàn)的攻擊，HFE體制使用減方法和加方法得到了一些變體，比方HFE-、HFE±等，但人們更多的關(guān)注是使用醋變量方法和減方法混合構(gòu)建的變種HFEv和HFEv-，尤其是HFEv-產(chǎn)生了一種實(shí)用的Quartz簽名體制[31]。3.油醋(OV)體制原始的油醋(Oil-Vinegar)體制[32]是Patarin在利用線性化方法攻破MI體制后，根據(jù)線性化方程的形式構(gòu)造出來的數(shù)字簽名體制。Kipins等人隨后對OV體制進(jìn)行了擴(kuò)展，提出了不平衡的油醋(UnbalancedOilandVinegar)體制[33]，簡記UOV體制。OV體制的關(guān)鍵在于應(yīng)用了Oil-Vinegar多項式。設(shè)k是一個階為q的有限域，變量稱為Oil變量，變量稱為Vinegar變量，設(shè)。定義2.12(Oil-Vinegar多項式)Oil-Vinegar多項式是最高次數(shù)為2次的多項式，且具有如下形式：，式(2-34)其中。由式(2-34)不難發(fā)現(xiàn)，Oil-Vinegar多項式是二次多項式，在固定了所有的Oil變量之后，多項式f是關(guān)于Vinegar變量的二次多項式；在固定了Vinegar變量之后，多項式f是關(guān)于Oil變量的線性多項式。定義2.13(Oil-Vinegar映射)假設(shè)是一個具有如下形式的多項式映射：，式(2-35)其中是Oil-Vinegar多項式，那么稱F為Oil-Vinegar映射。油醋(OV)體制在產(chǎn)生簽名時只需要隨機(jī)選取一組Vinegar變量，然后求解一個關(guān)于Oil變量的線性方程組。油醋(OV)體制分為三類：平衡油醋體制、不平衡油醋體制以及Rainbow體制[34]。平衡油醋體制受到采用了可逆子空間的Kipnis-Shamir攻擊[35]，不平衡油醋體制受到了Kipnis-Patarin-Goubin攻擊[36]，而OlivierBillet和HenriGilbert提出了對Rainbow的一種密碼分析[37]，為攻擊者提供了一種密鑰的等價表示，從而允許高效地偽造任何消息的簽名，Rainbow的平安性也遭受了威脅。4.三角階梯(STS)體制三角階梯體制(Step-wiseTriangularSystems,STS)的起源來自于代數(shù)幾何，首先由提出，1986年Tsujii等人提出了一個更一般的形式。不過，這些體制很快分別被Hasegawa和Kaneoka，以及Okamoto和Nakamura攻破。STS體制的平安性建立在分解一個非線性的可逆多項式映射的復(fù)合的困難性上。現(xiàn)在介紹STS的根本架構(gòu)。令是個可逆映射的組合：，其中每個，且。此外，對于給出的，是易于計算的。假設(shè)只給出，很難恢復(fù)出的組合。三角階梯體制與其他多變量算法結(jié)構(gòu)最根本的不同在于STS在組合中用到了多于一個的非線性變換。如果考慮公鑰的大小和運(yùn)算復(fù)雜度，一般要求F是二次的，但是如果要求更高的平安性，就需要更高的次數(shù)。一個二次的中心映射形式表示如下：式(2-36)假設(shè)為，那么定義為，其中是可逆的線性映射，是deJonquiere映射。為二維的變換，為高維的變換，映射為：。式(2-37)其中是上的可逆仿射變換。STS體制的關(guān)鍵運(yùn)算在于一個特別的多變量多項式，稱為，由一組特別的二次多項式組成。三、多變量公鑰密碼體系面臨的幾種常用攻擊方法現(xiàn)有的對多變量密碼體制的攻擊方法除了窮舉搜索外主要有以下幾種：Patarin的線性化方程[39]、解非線性方程[40]、秩攻擊[41]以及差分攻擊[42,43]等方法。在本節(jié)中將簡單介紹一下這幾類攻擊方法。〔一〕Patarin的線性化方程1995年P(guān)atarin在攻擊MI加密體制時提出了線性化方程的攻擊方法。對于一個密碼體制，滿足線性化方程式指任意合法的密文變量和相應(yīng)的明文變量滿足恒等式：式(2-38)分析一個多變量密碼體制是否存在線性化方程除了從理論上進(jìn)行分析之外，也可通過計算機(jī)實(shí)驗直接檢測公鑰和明文變量之間是否滿足線性化方程。從理論上分析也就是從中心映射的表達(dá)式出發(fā)，通過數(shù)學(xué)方法，尋求關(guān)于明文的線性化方程。計算機(jī)實(shí)驗的方法有兩種：一種是隨機(jī)選取足夠多的明文，得到足夠多的明文密文對，然后將這些明密文對代入式(2-38)中，得到一組關(guān)于系數(shù)的線性方程組；另一種是將密文變量關(guān)于明文變量的表達(dá)式代入式(2-38)中，展開化簡，比擬等式兩邊的系數(shù)，也可得到關(guān)于系數(shù)的一個線性方程組。如果這個關(guān)于系數(shù)的方程組有非零解，那么說明該體制存在線性化方程。反之，假設(shè)該方程只有零解，那么說明該體制不存在線性化方程。假設(shè)可判斷出存在線性化方程，那么解這個方程，得到所有線性獨(dú)立的線性化方程。將的合法密文代入此組方程，得到關(guān)于的線性方程組，求解，得到關(guān)于某些的線性關(guān)系。將這些線性關(guān)系代入原公鑰多項式，通過消元，即得到新的關(guān)于約減了的明文分量的公鑰多項式，然后再對這組新的公鑰多項式進(jìn)行分析，重復(fù)上述步驟，直到不能消元為止。最后利用XL算法或Gr?bner基算法求解最后一次消元后余下的變量的值，然后將這些值代入消元所使用的線性表達(dá)式中，并計算出明文所有變量的值。至此，恢復(fù)原明文。線性化方程優(yōu)勢在于，解式(2-38)得到所有線性獨(dú)立的線性化方程，這一步驟與密文無關(guān)，對于給定公鑰，該過程總是可以執(zhí)行?！捕辰夥蔷€性方程解非線性方程的方法，主要是XL算法和Gr?bner基算法，這里僅介紹這兩種算法。對于一個多變量公鑰密碼體制，公鑰和一個合法密文就可得到一個關(guān)于明文的多元多項式方程組，所以很自然就會想到去找一種算法，這種算法可以通過求解多變量方程組來獲得合法密文對應(yīng)的明文或者進(jìn)行偽造簽名。XL(eXtendedLinearization)算法是由Courtois、Klimov、Patarin和Shamir通過推廣線性化方程方法提出來的解有限域上多變量多項式方程組的一種算法。多變量多項式方程組具有如下形式：式(2-39)那么XL算法可描述如下：令A(yù)是一組多變量二次方程的集合，其中，。令D為自然數(shù)，考慮所有次數(shù)小于整數(shù)D的多項式。令是這些方程所張成的線性空間。XL算法的步驟如下：(1)乘。由乘法生成所有形如的乘積式，其中。(2)線性化。將所有的次數(shù)不大于D的單項式都作為一個新的變量。對(1)所得到的所有方程進(jìn)行高斯消元。并將僅含一個變量的項在最后消元。(3)求解關(guān)于新變量的一次方程。假設(shè)經(jīng)過(2)可得到至少一個單變量方程，那么在有限域上求解這些方程得到原始變量。(4)將原始變量代入簡化方程，重復(fù)上述步驟重復(fù)上述步驟尋求其它變量的值。實(shí)際上，XL算法也是一種計算既約Gr?bner基的算法[44]，它可表示成另一種求Gr?bner基的算法F4[45]算法的冗余變體。同時，根據(jù)文獻(xiàn)[44]，當(dāng)時，XL算法的復(fù)雜度約為其中使用一般高斯消元法時，=3；而使用改良算法，=2．3766。Gr?bner基是關(guān)于多元多項式理想的一個理論，典型的求Gr?bner基的方法是Buchberger算法，后來產(chǎn)生的方法幾乎都是在Buchberger算法的根底上改良而來的。其實(shí)，對單變量形式而言，Gr?bner基算法即為求最大公因式的歐幾里德算法，而對于線性方程那么可看作求三角陣的高斯消元法。目前最有效的求Gr?bner基的方法是Faugère提出的F4[38]、F5[39]算法，其中Faugère利用F5算法破解了HFE的挑戰(zhàn)1[40]。根據(jù)文獻(xiàn)[40]，F(xiàn)5算法的復(fù)雜度約為?！踩持裙糁裙羰菍⒍味嘧兞抗€多項式的系數(shù)寫成矩陣形式，結(jié)合中心映射的構(gòu)造以及矩陣的秩(奇異性)進(jìn)行密碼分析。秩攻擊可分為三種：低秩攻擊[30]。這一類攻擊最早是由Shamir和Kipnis提出的用于攻擊HFE加密體制的。低秩攻擊主要是去發(fā)現(xiàn)一組線性組合，這組線性組合能夠使得公鑰矩陣所組成的矩陣到達(dá)最小的秩。設(shè)k為q階有限域，r是中心方程線性組合的最小秩，m是中心映射的方程個數(shù)，n是變量數(shù)，令。那么低秩攻擊的復(fù)雜度約為。高秩攻擊或雙秩攻擊。這一類攻擊最早是由Coppersmith[等人引入，用于攻擊Shamir提出的基于雙有理置換的簽名體制。高秩攻擊主要是利用中心映射方程中某些變量出現(xiàn)較少次數(shù)，將一個二次多元多項式方程與一個系數(shù)矩陣對應(yīng)起來。根據(jù)文獻(xiàn)[41]，高秩攻擊的復(fù)雜度約為，其中u是中心映射中出現(xiàn)最少的變量出現(xiàn)的次數(shù)，n為中心映射方程個數(shù)，q為有限域的階。別離Oil變量和Vinegar變量攻擊。這一類攻擊是Kipnis[19]等人引入用來分析平衡油醋(OV)體制和不平衡油醋(UOV)體制的。在一個多項式方程集合中，變量能被分成兩個集合，這兩個集合中的變量分別被稱作Oil變量和Vinegar變量，假設(shè)給定所有Vinegar變量的值，多項式方程集合能變成一個關(guān)于Oil變量的線性方程組，將具有如此結(jié)構(gòu)的多項式方程集合稱作具有UOV結(jié)構(gòu)的多項式方程集合。Kipnis等人在文獻(xiàn)[19]中給出了他們攻擊的復(fù)雜度別離Oil和Vinegar變量攻擊的復(fù)雜度是，其中，分別為Oil變量和Vinegar變量個數(shù)，為有限域的階?！菜摹巢罘止舨罘止粲蒄ouque等人分析PMI加密體制時引入。該攻擊主要是計算中心映射的雙線性型(差分)，找到一個明文空間的子線性空間，將公鑰限定在此空間上，使得所有的內(nèi)部擾動項變?yōu)槌?shù)，然后使用線性化攻擊方法恢復(fù)密文的相應(yīng)明文。函數(shù)F的差分形式如下：，式(2-40)式(2-40)為域上的一個雙線性函數(shù)。Fouque等人于2023年利用差分攻擊成功地攻擊了l-IC方案。2023年，Billet等人開展了差分攻擊，利用該方法成功地攻擊了Square-Vinegar簽名方案和Square加密方案。計算差分可以降低函數(shù)的次數(shù)，而且便于尋找隱藏在私鑰中的某些特殊的線性關(guān)系。隨著差分攻擊的開展，它已經(jīng)成為分析多變量公鑰密碼體制的一個強(qiáng)有力的工具，在今后密碼體制的設(shè)計過程中需要重視此類攻擊。多變量公鑰密碼被認(rèn)為是一種有望代替?zhèn)鹘y(tǒng)公鑰密碼的密碼體制，近年來，逐漸成為密碼學(xué)研究的一個熱點(diǎn)。在本章中，作者對多變量公鑰系統(tǒng)進(jìn)行了簡單的介紹。多變量公鑰密碼系統(tǒng)雖然開展歷史不那么長，其整個體系尚未完整，但開展?jié)摿Σ蝗轃o視。尤其是隨著信息技術(shù)的開展，人們對更快更高效的公鑰密碼體制有著迫切的需求。基于有限域上多元多項式的運(yùn)算，使得多變量公鑰密碼與傳統(tǒng)公鑰密碼相比在存儲空間和執(zhí)行時間上具有明顯的優(yōu)勢，因此，對多變量公鑰密碼系統(tǒng)的研究非常有意義。由于作者理論水平有限，論文中的缺乏之處在所難免，敬請各位評審老師和讀者批評指正！參考文獻(xiàn)DingJ,GowerJE,SchmidtDS.Multivariatepublickeycryptosystems[M].Berlin:Springer,2006:2-3.RivestRL,ShamirA,AdlemanLM.Amethodforobtainingdigitalsignatureandpublickeycryptosystems.CommunicationsoftheACM.1978.21(2):120-126.ElGamalT.Apublickeycryptosystemandasignatureschemebasedondiscretelogarithms.IEEETransactiononInformationTheory.1985.IT-31(4):469-472.KoblitzN.Ellipticcurvecryptosystems.MathematicsofComputation.1987.48:203-209.MillerV.Useofellipticcurvesincryptography.inAdvancesinCryptology,CRYPTO1985,LNCS218.Berlin:Springer-Verlag,1986:417-426.ShorPW.Polynomial-timealgorithmsforprimefactorizationanddiscretelogarithmsonaquantumcomputer.SIAMJournalofComputer.1997.26:1484-1509.W.Diffie,M.E.Hellman.NewDirectionsinCryptography,IEEETransactiononInformationThery,1976,Vol.IT22,No.6,pp.644-654.LouisGoubin,JacquesPatarin．Trapdooronewaypermutationsandmultivariatepolynomials[G]．In:ISICS’97,LNCS1334.Berlin:Springer-Verlag,1997.356-368PatarinJ,CourtoisN,andGoubinL.Flash,afastmultivariatesignaturealgorithm.ProgressinCryptology,CT-RSA2001,LNCS,Springer,2001,vol.2023,pp.298-307.AkkarM,CourtoisN,DuteuilR,andGoubinL.AfastandsecureimplementationofSflash.InPKC-2003,LNCS,Springer,2003,vol.2567,pp.267-278.MatsumotoT,ImaiH.Publicquadraticpolynomial-tuplesforefficientsignatureverificationandmessageencryption.Advancesincryptology-EURO-CRYPT’88,LNCS,volume330,Springer,1988:419-453.J.Patarin．CryptanalysisoftheMatsumotoandImaipublickeyschemeofEurocrypt’88．AdvancesinCryptology-Crypto’95，LNCS，volume963，1995：248—261．J.Patarin.Hiddenfieldequations(HFE)andisomorphismofpolynomials(IP):Twonewfamiliesofasymmetricalgorithms．Eurocrypt’96,LNCS,volume1070,Springer,1996:33-48.J.Patarin.Theoilandvinegarsignaturescheme.DagstuhlWorkshoponCryptography,September1997.FellHarrietandDifficWhitfield.AnalysisofaPublickeyapproachbasedonPolynomialsubstitution[C],Cryptology-CRYPTO’85,LNCS218.Berlin:Springer-verlag,1986:340-349.JacquesPatarn．Asymmetriccryptographywithahiddenmonomial．InAdvancesinCryptology-CRYPTO1996,vol．1109,LNCS,Springer,l996,pp．45-60．J．Patarin,L．Goubin,N．Courtois．C*-+andHM：variationsaroundtwoschemesofT．MatsumotoandH．Imai．AdvancesinCryptology-ASIACRYPT’98,LNCS,volume1514，Springer,1998：35-50．KipnisAviad,PatarinJacques,andGoubinLouis.Unbalancedoilandvinegarsignatureschemes.InAdvancesinCryptology-EUROCRYPTl999,LNCS,Springer,l996,vol.1592,pp.206-222.J.Ding.AnewvariantoftheMatsumoto-Imaicryptosystemthroughperturbation.PublickeyCryptography,(PKC’04),LNCS,volume2947,Springer,2004:305-318.J.Ding,D.Schmidt.CryptanalysisofHFEVandtheinternalperturbationofHFE.PublickeyCryptography-(PKC’05),LNCS,volume3386,Springer,2005:288-301.胡向東，魏琴芳。應(yīng)用密碼學(xué)教程。北京：電子工業(yè)出版社，2005.pp.49-51PatarinJ,GoubinL.Trapdoorone-waypermutationsandmultivariatepolynomials.InInternationalConferenceonInformationSecurityandCryptologyl997,LNCS,Berlin:Springer,l999,vol.1334.pp.356-368.WolfChristopherandPreneelBart.Taxonomyofpublickeyschemesbasedontheproblemofmultivariatequadraticequations．Patarin,Jacques(1996a).Asymmetriccryptographywithahiddenmonomial.InKoblitz,N.,editor.Advancesincryptology,CRYPTO'96,volume1109ofLNCS,pages45-60.Springer.T.Moh.AfastPublickeysystemwithsignatureandmasterkeyfunctions[R].CA:EEdepartmentofStanfordL.Wang,B.Yang,Y.Hu.AMedium-FieldMultivariatePublickeyEncryptionScheme,CT-RSA2006,LNC