一種基于多變量公鑰密碼體制的改進(jìn)簽名模型

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

(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īng)成為近年來一項重要的挑戰(zhàn).美國科學(xué)家Peter Shor于1995年提出了一種量子分解算法[5,6],它通過利用量子計算的并行性,可以在多項式時間內(nèi)快速分解出大數(shù)的質(zhì)因子和離散對數(shù)問題,對現(xiàn)有基于傳統(tǒng)密碼體制的數(shù)字簽名的安全性構(gòu)成了嚴(yán)重威脅.

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

MI (Matsumoto and Imai)方案[15]是多變量公鑰密碼體制的一個基礎(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è)計上,通常采用如圖2所示的簽名結(jié)構(gòu)；該模型還存在以下問題：按照該模型設(shè)計的簽名產(chǎn)生和驗證算法,隱含著簽名驗證僅依賴于外部公鑰,并不涉及產(chǎn)生該消息簽名時所對應(yīng)的內(nèi)部流程信息.這就使得在對方案進(jìn)行攻擊分析時,常常以尋找公鑰方程之間潛在的內(nèi)部代數(shù)關(guān)系為攻擊目標(biāo)[19,20].

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

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

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

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

多變量公鑰密碼體制具有龐大的代數(shù)結(jié)構(gòu)[30,31],其公鑰由一組非線性多變量多項式方程組構(gòu)成.公鑰P可看作三個映射的合成：P=ToQoS，符號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個變量m個多項式的方程組：

Q(x1,…,xn)|→

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

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

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

P(x1,…,xn) =

ToQoS(x1,…,xn)=

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

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

1.1 簽名生成

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

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

1.2 簽名驗證

由圖1可知，簽名驗證即利用公玥P計算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個變量的二次多項式方程.令S，T是Fn上的兩個隨機(jī)可逆仿射變換，則有公鑰

P(x1,…,xn)=

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

ToQoS(x1,…,xn)

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

1.3.2 MI簽名方案

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

(1) 計算：

(2)計算：

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

(3)計算：

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

1.4 線性化分析思想

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

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

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

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

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

(xaxd)(xbxc)?yabycd=

yacybd=yadybc

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

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

表1 線性化過程

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

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

針對多變量密碼體制簽名模型的這一問題，通過重新設(shè)計公鑰，增強(qiáng)簽名生成和驗證過程的嚴(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上的一組多變量二次多項式方程q1(x1,…,xn),…,qm(x1,…,xn)為多變量公鑰密碼體制的中心映射，記為Q，其中輸入變量為n，輸出變量為m，Q-1即為多項式Q的逆多項式.另取Fn和Fm上可逆仿射變換S和T為私鑰，其逆多項式分別記為S-1和T-1.隨機(jī)選取Fn上的一組n個n元二次多項式方程組(g1(x1,…,xn),…,gn(x1,…,xn))，記為G，即G(x1,…,xn)=(g1(x1,…,xn),…,gn(x1,…,xn))，以及一個具有hash特性的單向不可逆的多項式方程組H.

用戶私鑰由S、T、G三部分構(gòu)成，均為可逆仿射變換.H為可信第三方秘密選取，但僅用于公鑰的產(chǎn)生，其中G的逆多項式表示為G-1.對應(yī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，計算得(v1,…,vn)，記為v，則v即為消息M的編碼u的外部簽名.

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

對u=(u1,…,um)，經(jīng)由T-1和Q-1計算結(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)部簽名級聯(lián)得到v‖vg，即為消息M編碼u的最終簽名.

2.3 簽名驗證

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

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

(V1)公鑰P驗證

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

將外部簽名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 正確性

驗證者收到按上述步驟產(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 安全性

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

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

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

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

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

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

(1)計算：

(2)計算：

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

(3)計算：

(4)計算：

GSigner(x1,…,xn)=

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

(g1,…,gn)

(5)計算：

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

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

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

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

3.2 性能分析

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

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

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

由圖4至圖7可以看出：

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

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

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

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

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

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

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

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

4 結(jié)論

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