王 鑫,韓志宇,王新梅,楊 帆

(1.陜西科技大學(xué) 電子信息與人工智能學(xué)院，陜西 西安 710021;2.西安電子科技大學(xué) 通信工程學(xué)院,陜西 西安 710126)

0 引言

后量子密碼體制已經(jīng)發(fā)展了大約30年.特別是近10年來簽名領(lǐng)域發(fā)展迅猛,涌現(xiàn)出許多引人注目的研究成果，如同態(tài)哈希函數(shù)多變量簽名方案[1]，以及擴(kuò)展merkle簽名方案(XMSS)[2]和G-Merkle[3,4]XMSS等.此外,尋找新一代的公鑰密碼體制以抵抗量子計(jì)算機(jī)的攻擊,已經(jīng)成為近年來一項(xiàng)重要的挑戰(zhàn).美國(guó)科學(xué)家Peter Shor于1995年提出了一種量子分解算法[5,6],它通過利用量子計(jì)算的并行性,可以在多項(xiàng)式時(shí)間內(nèi)快速分解出大數(shù)的質(zhì)因子和離散對(duì)數(shù)問題,對(duì)現(xiàn)有基于傳統(tǒng)密碼體制的數(shù)字簽名的安全性構(gòu)成了嚴(yán)重威脅.

后量子密碼體制的研究方向主要基于如下四類：基于格理論的密碼體制[7]、基于編碼理論的密碼體制[8]、基于Hash函數(shù)的密碼體制[9]和多變量公鑰密碼體制.多變量公鑰密碼體制是有限域上根據(jù)多變量非線性方程組的求解問題而設(shè)計(jì)的密碼體制,其安全性基于求解一組多變量多項(xiàng)式方程,是一個(gè)NP-C困難問題[10].類似的是對(duì)稱密碼體制中分組密碼AES的S盒其本質(zhì)即為有限域上一個(gè)高次多變量多項(xiàng)式方程組.多變量公鑰密碼體制目前被認(rèn)作是量子時(shí)代的一種安全的密碼體制備選方案.2019年1月30日,美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究院(NIST)啟動(dòng)一項(xiàng)關(guān)于后量子公鑰加密標(biāo)準(zhǔn)草案的全球征集活動(dòng).經(jīng)過一年的草案收集和第一輪審核,從最初的69種算法中選擇了26種算法,進(jìn)入后量子密碼的半決賽.在候選的9種簽名算法中,有4種是基于多變量公鑰密碼體制[11-14].

MI (Matsumoto and Imai)方案[15]是多變量公鑰密碼體制的一個(gè)基礎(chǔ)性突破，隨后又有很多新方案被提出，大致可以分為四類：MI體系、HFE(Hidden Field Equation)體系、OV (Oil Vinegar)體系和TTM(Tame Transformation Method)體系.不幸的是，這些體系的大多數(shù)密碼方案已被攻破，現(xiàn)存的方案普遍被認(rèn)為不適合加密，只適用于簽名如UOV (Unbalanced Oil Vinegar)簽名方案[11]和Rainbow簽名方案[12].后續(xù)學(xué)者也投入了更多精力在這兩種簽名方案上[16-18].

然而,目前現(xiàn)有的基于多變量公鑰密碼體制的研究絕大部分集中在中心映射的設(shè)計(jì)上,通常采用如圖2所示的簽名結(jié)構(gòu)；該模型還存在以下問題：按照該模型設(shè)計(jì)的簽名產(chǎn)生和驗(yàn)證算法,隱含著簽名驗(yàn)證僅依賴于外部公鑰,并不涉及產(chǎn)生該消息簽名時(shí)所對(duì)應(yīng)的內(nèi)部流程信息.這就使得在對(duì)方案進(jìn)行攻擊分析時(shí),常常以尋找公鑰方程之間潛在的內(nèi)部代數(shù)關(guān)系為攻擊目標(biāo)[19,20].

基于線性化分析思想的偽造簽名攻擊即為這樣一種有效分析方法,方法通過尋求或重新構(gòu)造公鑰P的外部結(jié)構(gòu),將內(nèi)部隱藏的變量關(guān)系顯性表達(dá),構(gòu)造更多的獨(dú)立方程,再通過矩陣秩攻擊對(duì)新方程求解[21,22].由于多變量體制核函數(shù)的構(gòu)造使得大多數(shù)現(xiàn)有的加密或簽名方案容易遭受此類攻擊[23-27].特別是多變量體制的密鑰具有冗余特性,通過該攻擊所得到的解統(tǒng)計(jì)意義為其合法私鑰對(duì)應(yīng)的等價(jià)私鑰,并非簽名者的合法私鑰,詳細(xì)分析見文[28,29],矩陣秩的攻擊方法可見文獻(xiàn)[15]等.

原有簽名模型中的簽名驗(yàn)證“僅涉及消息和簽名”而“不涉及內(nèi)部過程信息”的驗(yàn)證是導(dǎo)致方案被攻破的關(guān)鍵所在.因?yàn)槎嘧兞抗€密碼體制的中心映射是多對(duì)一的映射,所以自然就存在一個(gè)像對(duì)應(yīng)多個(gè)原像的現(xiàn)象.而截至目前,多變量密碼方案的設(shè)計(jì)多集中于中心映射的不斷改進(jìn)和新結(jié)構(gòu)的不斷提出,從簽名模型的角度分析抵抗基于線性化分析思想的偽造簽名攻擊還未給出過相關(guān)研究.本文主要對(duì)原有簽名模型存在的這一問題進(jìn)行深入分析,通過借助簽名附加值,增強(qiáng)簽名驗(yàn)證條件,使得簽名不僅確保外部信息的一致性,還必須具有內(nèi)部信息的一致性,并以MI方案[15]為例進(jìn)行具體分析.

本模型改進(jìn)算法為量子時(shí)代安全簽名方案設(shè)計(jì)提供了有益補(bǔ)充,并且方案運(yùn)算僅涉及有限域上的加、乘,具有較高的效率和安全性,特別適用于存儲(chǔ)空間和運(yùn)算時(shí)間受限的場(chǎng)合,如智能卡、無線傳感網(wǎng)絡(luò)和動(dòng)態(tài)RFID標(biāo)簽,為量子計(jì)算機(jī)時(shí)代的信息安全和信任體系的建立提供了必要的基礎(chǔ)技術(shù)支撐.

1 多變量公鑰密碼體制的原有簽名模型

多變量公鑰密碼體制具有龐大的代數(shù)結(jié)構(gòu)[30,31],其公鑰由一組非線性多變量多項(xiàng)式方程組構(gòu)成.公鑰P可看作三個(gè)映射的合成：P=ToQoS，符號(hào)o表示映射的合成，其中

分別為Fn和Fm上隨機(jī)選取的可逆仿射變換，它們共同"掩藏"中心映射Q的結(jié)構(gòu)，是私鑰的重要部分.這里用Aff-1(Fn,Fm)表示Fn到Fm上的所有仿射變換，Aff-1(Fn)和Aff-1(Fm) 分別為Aff-1(Fn,Fn)和Aff-1(Fm,Fm)的縮寫.

中心映射Q，是由n個(gè)變量m個(gè)多項(xiàng)式的方程組：

Q(x1,…,xn)|→

(q1(x1,…,xn),…,qm(x1,…,xn))

Q的結(jié)構(gòu)通常公開，亦可部分保密，構(gòu)成中心映射的方程稱為中心方程.

三元組(T,Q,S)為私鑰，對(duì)應(yīng)的公鑰即：

P(x1,…,xn) =

ToQoS(x1,…,xn)=

(p1(x1,…,xn),…,pm(x1,…,xn))

圖1 多變量公鑰密碼系統(tǒng)的簽名結(jié)構(gòu)圖

1.1 簽名生成

已知一個(gè)消息M，取一個(gè)哈希函數(shù)H，使v=H(M)，依次計(jì)算y=T-1(v)，x=Q-1(y)和u=S-1(x).其中，S-1，T-1均為私鑰S和T的可逆仿射變換.Q-1是中心映射Q的逆，求解Q-1時(shí)，需要結(jié)合Q的具體結(jié)構(gòu).

向量u=(u1,…,un)即是消息M的簽名.

1.2 簽名驗(yàn)證

由圖1可知，簽名驗(yàn)證即利用公玥P計(jì)算v=P(u)，若等式成立即為合法簽名，否則簽名無效.

1.3 MI方案

MI加密體制[15]通過使用基域及其擴(kuò)域構(gòu)造多變量公鑰密碼體制.

1.3.1 MI加密方案

設(shè)F是一q階有限域，E是F的n次擴(kuò)域，π:E→Fn是擴(kuò)域到向量空間的同構(gòu)映射，為

π(a0+a1x+…+an-1xn-1)=(a0,…,an-1)

Q(x1,…,xn)=

(q1(x1,…,xn),…,qn(x1,…,xn))=

其中，qi(x1,…,xn)i=1,…,m是n個(gè)變量的二次多項(xiàng)式方程.令S，T是Fn上的兩個(gè)隨機(jī)可逆仿射變換，則有公鑰

P(x1,…,xn)=

(p1(x1,…,xn),…,pn(x1,…,xn))=

ToQoS(x1,…,xn)

其中，每一個(gè)多項(xiàng)式pn(n=1～n)均為二次.

1.3.2 MI簽名方案

設(shè)消息為M，其編碼值為(u1,…,um)，簽名者的私鑰為SSiger，TSiger,公鑰為PSiger.簽名者對(duì)消息M進(jìn)行如下計(jì)算：

(1) 計(jì)算：

(2)計(jì)算：

(x1,…,xn)=Q-1(y1,…,ym)=

(3)計(jì)算：

則(v1,…,vn)即是消息(u1,…,vm)的簽名.

1.4 線性化分析思想

多變量公鑰密碼體制的線性化分析思想是通過對(duì)已知的公鑰方程或中心映射結(jié)構(gòu)進(jìn)行等價(jià)變形,將被隱藏的大量?jī)?nèi)部信息顯性表達(dá),通過產(chǎn)生更多的明密文方程,以期獲得足夠的線性無關(guān)方程,進(jìn)而嘗試消元求解.

然而,通過分析我們發(fā)現(xiàn)在多變量的簽名產(chǎn)生和驗(yàn)證算法過程中,內(nèi)部節(jié)點(diǎn)信息并未有效體現(xiàn),也就是缺少和私鑰相關(guān)聯(lián)的內(nèi)部信息流的有效驗(yàn)證.因此,對(duì)于多變量公鑰密碼體制的原有簽名模型-簽名有效判斷僅通過公鑰驗(yàn)證,借助對(duì)公鑰的線性化分析勢(shì)必會(huì)增加敵手成功的概率.

MI方案在高秩、低秩等直接分析中表現(xiàn)良好，卻無法抵抗線性化分析的攻擊求解等價(jià)私鑰.對(duì)于公鑰密碼體制而言,若存在兩個(gè)(甚至多個(gè)) 私鑰和對(duì)應(yīng)著同一公鑰,那么我們就稱這兩個(gè)(多個(gè)) 私鑰“等價(jià)”.多變量公鑰密碼體制的等價(jià)私鑰是由于其本身龐大代數(shù)結(jié)構(gòu)帶來的,并且容易看出等價(jià)私鑰的存在給簽名的偽造提供了外部可能.基于線性化分析思想的攻擊基本思路如下[32]：

設(shè)一組變量數(shù)為m的εm2個(gè)二次方程組，變量為x1,…,xm，其中ε為常數(shù).通過變量代換變量為yij=xixj，原方程組變?yōu)樽兞繑?shù)約有m2/2的εm2個(gè)線性方程組，其中i≤j.對(duì)于任何滿足1≤a≤b≤c≤d≤m的四元組xaxbxcxd，存在三種不同的方式：

(xaxb)(xcxd)=(xaxc)(xbxd)=

(xaxd)(xbxc)?yabycd=

yacybd=yadybc

每互不相同的四元組都會(huì)產(chǎn)生2個(gè)方程，共存在大約m4/4!種不同的方程.進(jìn)而，約產(chǎn)生m2/2個(gè)變量yij的m4/12 個(gè)二次方程，由于這些方程是線性獨(dú)立，因此可再通過將每個(gè)變量yij替換為新變量zk的線性組合來表示，此時(shí)變量個(gè)數(shù)減少為(1/2-ε)m2個(gè).進(jìn)而，再對(duì)(1/2-ε)m2個(gè)關(guān)于變量zi的m4/12個(gè)二次方程繼續(xù)用新變量vij替換每個(gè)乘積zizj(其中i≤j)做再次線性化.最終，得到具有m4/12個(gè)線性方程的新方程組，其中變量vij為((1/2-ε)m2)2/2個(gè).

線性化過程中方程數(shù)與變量之間的關(guān)系如表1所示.

表1 線性化過程

借助于線性化分析方法，構(gòu)造足夠多的公鑰方程，通過求解尋找合法私鑰對(duì)應(yīng)的等價(jià)私鑰，進(jìn)而可構(gòu)造同一消息的一個(gè)有效簽名，得以偽造簽名成功.

2 改進(jìn)簽名模型描述

針對(duì)多變量密碼體制簽名模型的這一問題，通過重新設(shè)計(jì)公鑰，增強(qiáng)簽名生成和驗(yàn)證過程的嚴(yán)格性，提出一種可有效抵抗基于線性化分析思想攻擊的改進(jìn)模型.

2.1 參數(shù)生成

設(shè)有限域F，正整數(shù)n和m，F(xiàn)的n次擴(kuò)域記為Fn，F(xiàn)的m次擴(kuò)域記為Fm.取Fn到Fm上的一組多變量二次多項(xiàng)式方程q1(x1,…,xn),…,qm(x1,…,xn)為多變量公鑰密碼體制的中心映射，記為Q，其中輸入變量為n，輸出變量為m，Q-1即為多項(xiàng)式Q的逆多項(xiàng)式.另取Fn和Fm上可逆仿射變換S和T為私鑰，其逆多項(xiàng)式分別記為S-1和T-1.隨機(jī)選取Fn上的一組n個(gè)n元二次多項(xiàng)式方程組(g1(x1,…,xn),…,gn(x1,…,xn))，記為G，即G(x1,…,xn)=(g1(x1,…,xn),…,gn(x1,…,xn))，以及一個(gè)具有hash特性的單向不可逆的多項(xiàng)式方程組H.

用戶私鑰由S、T、G三部分構(gòu)成，均為可逆仿射變換.H為可信第三方秘密選取，但僅用于公鑰的產(chǎn)生，其中G的逆多項(xiàng)式表示為G-1.對(duì)應(yīng)的公鑰也由三個(gè)多項(xiàng)式構(gòu)成，分別為P=ToQoS,HoG-1oS,HoS.

2.2 簽名生成

已知消息M的編碼為向量(u1,…,um) ，記做u，如圖2所示，簽名則按以下步驟產(chǎn)生：

圖2 改進(jìn)模型中的簽名生成

(S1)外部簽名

已知消息M的編碼值u=(u1,…,um)，依次由T-1，Q-1，S-1，計(jì)算得(v1,…,vn)，記為v，則v即為消息M的編碼u的外部簽名.

(S2)內(nèi)部簽名

對(duì)u=(u1,…,um)，經(jīng)由T-1和Q-1計(jì)算結(jié)果為(x1,…,xn)，記為x.將x代入到G中，得G(x1,…,xn)=(g1(x1,…,xn),…,gn(x1,…,xn))=(g1,…,gn)記為g.

再將g代入到S-1中，得到S-1(g)oG(x)=(vg1,…,vgn)，記為vg.則vg即為消息M的編碼u的內(nèi)部簽名.

將外部簽名和內(nèi)部簽名級(jí)聯(lián)得到v‖vg，即為消息M編碼u的最終簽名.

2.3 簽名驗(yàn)證

改進(jìn)模型中簽名驗(yàn)證原理如圖3所示.

圖3 改進(jìn)模型中簽名驗(yàn)證

(V1)公鑰P驗(yàn)證

(V2)公鑰HoS和HoG-1oS驗(yàn)證

將外部簽名v=(v1,…,vn)代入到公鑰HoS中，得

HoS(v)=HoS(v1,…,vn)=H(S(v1,…,vn))

記結(jié)果為h=(h1,…,hn)；將內(nèi)部簽名vg=(vg1,…,vgn)代入到公鑰HoG-1oS中，得

HoG-1oS(vg)=HoG-1oS(vg1,…,vgn)=

H(G-1(S(vg1,…,vgn)))

2.4 安全性分析

2.4.1 正確性

驗(yàn)證者收到按上述步驟產(chǎn)生的簽名v‖vg，則有：

P(v)=P(S-1oQ-1oT-1(u1,…,um))=

PoS-1oQ-1oT-1(u)=

ToQoSoS-1oQ-1oT-1(u)=u

以及：

S(v)=(x1,…,xn)=G-1oS(vg)

HoS(v)=HoG-1oS(vg)

由上述可知其正確性成立.

2.4.2 安全性

相對(duì)于原有簽名模型，改進(jìn)模型實(shí)現(xiàn)了簽名產(chǎn)生過程中內(nèi)部信息流予以外部校驗(yàn)，有效簽名必須結(jié)合內(nèi)部節(jié)點(diǎn)信息的驗(yàn)證，而不僅僅依賴于外部公鑰的唯一驗(yàn)證.實(shí)現(xiàn)每一簽名的產(chǎn)生與合法私鑰實(shí)現(xiàn)一致性綁定，有效阻止包括線性化分析思想在內(nèi)的偽造簽名攻擊.

此外，隨機(jī)秘密仿射變換的選取不泄露中心映射的結(jié)構(gòu)信息，不影響簽名的原有驗(yàn)證.使得改進(jìn)模型具有一般通用性，保持原有方案核映射結(jié)構(gòu)不變.因此，多變量公鑰密碼體制的其它類型的安全性分析，如高/低秩、差分分析等，均不受改進(jìn)模型影響，安全級(jí)別保持不變.方案在不同參數(shù)下的具體體現(xiàn)可見文獻(xiàn)[29].事實(shí)上，改進(jìn)簽名模型揭示了能通過公鑰驗(yàn)證的簽名并非一定是合法的，合法簽名必須確保內(nèi)部節(jié)點(diǎn)信息的一致性的事實(shí).因此，增強(qiáng)內(nèi)部節(jié)點(diǎn)信息準(zhǔn)確一致性的驗(yàn)證，是提高簽名有效性的一種有效方法.

3 MI在原有模型和改進(jìn)模型中性能對(duì)比

3.1 改進(jìn)模型MI簽名方案

原簽名模型只利用公鑰驗(yàn)證P(v)=u，而改進(jìn)模型，簽名由兩部分v和vg構(gòu)成，除原有公鑰驗(yàn)證P(v)=u，還利用公鑰HoS和HoG-1oS驗(yàn)證內(nèi)部節(jié)點(diǎn)的一致性：

HoS(v)=HoG-1oS(vg).

(1)計(jì)算：

(2)計(jì)算：

(x1,…,xn)=Q-1(y1,…,ym)=

(3)計(jì)算：

(4)計(jì)算：

GSigner(x1,…,xn)=

(g1(x1,…,xn),…,gn(x1,…,xn))=

(g1,…,gn)

(5)計(jì)算：

將(v1,…,vn)和(vg1,…,vgn)級(jí)聯(lián)，得v1,…,vn‖vg1,…,vgn即為消息(u1,…,um)簽名.

驗(yàn)證者收到消息(u1,…,um)和簽名v1,…,vn‖vg1,…,vgn，對(duì)簽名進(jìn)行驗(yàn)證：

(2)將外部簽名(v1,…,vn)代入簽名者的公鑰HoSSigner，得

(h1,…,hn)=HoSSigner(v1,…,vn)

3.2 性能分析

從表2可以看出，隨著參數(shù)的增大，簽名和驗(yàn)證所耗時(shí)間均有所增加；相對(duì)于原有模型，新模型下所耗時(shí)間主要體現(xiàn)在簽名的驗(yàn)證，特別是大參數(shù)時(shí)的簽名驗(yàn)證，新模型所耗時(shí)間增加較大，這主要因?yàn)樾履Ｐ拖?，簽名?yàn)證由原有模型的一個(gè)公鑰驗(yàn)證增加為兩個(gè)條件，每判斷一個(gè)簽名的合法性至少需要計(jì)算3次，加之所增加的驗(yàn)證條件為非線性的公鑰方程，因此，越大參數(shù)對(duì)新模型的影響越大.而對(duì)于簽名的產(chǎn)生，較原有模型，新模型所耗時(shí)間增加較小.

表2 MI在原有模型及改進(jìn)模型下簽名驗(yàn)證時(shí)間對(duì)比

為進(jìn)一步說明參數(shù)對(duì)時(shí)間的影響，按照不同參數(shù)給出圖4～7的時(shí)間對(duì)比.

由圖4至圖7可以看出：

圖4 (q,λ)=(4,3)，原有模型和改進(jìn)模型下簽名時(shí)間對(duì)比

圖5 (q,λ)=(4,3)，原有模型和改進(jìn)模型下驗(yàn)證時(shí)間對(duì)比

圖6 (q,λ)=(25,3)，原有模型和改進(jìn)模型下簽名時(shí)間對(duì)比

圖7 (q,λ)=(25,3)，原有模型和改進(jìn)模型下驗(yàn)證時(shí)間對(duì)比

(1)取(q,λ)=(4,3)，從圖4和圖5可以看出，新模型下的MI簽名及驗(yàn)證時(shí)間較原模型下的時(shí)間基本相當(dāng)，但有增長(zhǎng)趨勢(shì).考慮到n是關(guān)于方程的數(shù)量，如果繼續(xù)增加n的取值，簽名和驗(yàn)證的時(shí)間均會(huì)大幅度增加；

(2)取(q,λ)=(25,3)，從圖6和圖7可以看出，q取值均略小時(shí)，新模型較原有模型下所用時(shí)間基本相當(dāng)，增加不多，但是對(duì)于大數(shù)值的q，新模型中驗(yàn)證的時(shí)間是原模型的近百倍，這說明，大參數(shù)q的取值對(duì)新模型下方案影響較大.因此，新模型中應(yīng)根據(jù)具體情況適當(dāng)控制q的取值，以至于獲得合理的簽名和驗(yàn)證時(shí)間.

(3)不管是新模型還是原模型，λ的取值對(duì)簽名時(shí)間和驗(yàn)證時(shí)間沒有太大影響.

綜上，原有模型以及改進(jìn)模型的簽名驗(yàn)證時(shí)間都隨著參數(shù)的增大而變長(zhǎng)，而改進(jìn)模型下所用簽名和驗(yàn)證都比原有模型所用時(shí)間有所增加，特別是簽名時(shí)間，這是源于改進(jìn)模型中簽名由原來的一部分增加為二部分構(gòu)成.驗(yàn)證時(shí)，驗(yàn)證公鑰由原來的一個(gè)條件增至為兩個(gè).但改進(jìn)模型比原有模型可抵抗偽造簽名攻擊，具有更高的安全性.

4 結(jié)論

基于線性化分析思想的偽造簽名攻擊是分析多變量公鑰密碼體制的一種常用且有效的分析方法，多變量公鑰密碼體制的原有簽名模型在最初設(shè)計(jì)時(shí)還未遇到如線性化分析類的攻擊，因此在涉及到具體方案時(shí)屢被攻破.為克服原有簽名模型的設(shè)計(jì)缺陷，本文提出一種更為安全有效、可有效抵抗此類偽造簽名攻擊的多變量簽名模型.該方法是在原有模型的基礎(chǔ)上，通過增加額外公鑰，將單一的公鑰驗(yàn)證增強(qiáng)為必需結(jié)合內(nèi)部節(jié)點(diǎn)信息進(jìn)行驗(yàn)證，從而有效遏制基于線性化分析思想的偽造簽名攻擊帶來的的潛在危脅.本文最后以經(jīng)典方案MI為例，對(duì)原有模型和改進(jìn)模型進(jìn)行了對(duì)比分析，分析顯示，改進(jìn)模型可有效抵抗此類偽造簽名攻擊，為量子時(shí)代安全的數(shù)字簽名方案的設(shè)計(jì)和研究提供了有益補(bǔ)充.