沈榮耀 馬利民 王佳慧 張 偉

1(北京信息科技大學(xué)北京未來(lái)區(qū)塊鏈與隱私計(jì)算高精尖中心 北京 100101)

2(北京信息科技大學(xué)計(jì)算機(jī)學(xué)院 北京 100101)

3(北京信息科技大學(xué)國(guó)家經(jīng)濟(jì)安全預(yù)警工程北京實(shí)驗(yàn)室 北京 100101)

4(國(guó)家信息中心信息與網(wǎng)絡(luò)安全部 北京 100045)

數(shù)字簽名是一種可以有效保障網(wǎng)絡(luò)安全的密碼技術(shù),廣泛應(yīng)用于我國(guó)政府、金融、商業(yè)等領(lǐng)域.在實(shí)際場(chǎng)景中,會(huì)持續(xù)產(chǎn)生海量的數(shù)字簽名,占據(jù)大量存儲(chǔ)空間,且對(duì)簽名逐個(gè)驗(yàn)證會(huì)帶來(lái)較大計(jì)算開銷,因此,如何提高海量簽名的驗(yàn)證效率,降低簽名存儲(chǔ)占用顯得尤為重要.

由于聚合簽名(aggregate signature, AS)可以提高批量驗(yàn)證效率,降低存儲(chǔ)占用,所以尤其適用于解決大量簽名的存儲(chǔ)以及驗(yàn)證的問(wèn)題.聚合簽名由Boneh等人[1]于2003年首次提出.然而,對(duì)聚合簽名驗(yàn)證時(shí),驗(yàn)證方需要獲取完整明文集合,當(dāng)聚合的簽名數(shù)量較多時(shí),驗(yàn)證聚合簽名所需明文數(shù)量也隨之增大.有時(shí)驗(yàn)證方僅需驗(yàn)證指定明文,獲取完整明文集合會(huì)為驗(yàn)證方增加計(jì)算負(fù)擔(dān).針對(duì)這種情況,采用局部可驗(yàn)證的聚合簽名可以大大降低驗(yàn)證方的計(jì)算負(fù)擔(dān).局部可驗(yàn)證的聚合簽名由Goyal等人[2]首次提出.

SM2算法[3]由國(guó)家密碼管理局于2010年底發(fā)布,是一種基于橢圓曲線的密碼算法,其具有自主可控、安全性高、易于實(shí)現(xiàn)等優(yōu)點(diǎn),廣泛應(yīng)用于各類信息系統(tǒng)之中.

本文提出一種安全、高效的基于國(guó)密SM2的局部可驗(yàn)證聚合簽名方案.方案采用聚合簽名技術(shù),提高批量驗(yàn)證效率,同時(shí)采用局部可驗(yàn)證技術(shù),使驗(yàn)證方對(duì)聚合簽名及指定明文驗(yàn)證時(shí),無(wú)需獲取全部明文,僅需短提示即可,進(jìn)一步降低驗(yàn)證方計(jì)算成本.

1 相關(guān)工作

根據(jù)采用的公鑰密碼體制,聚合簽名可以劃分成3類:基于身份的聚合簽名(identity-based aggregate signature, IBAS)、無(wú)證書聚合簽名(certificateless aggregate signature, CLAS)以及基于公鑰基礎(chǔ)設(shè)施(public key infrastructure, PKI)的聚合簽名.

1) 基于身份的聚合簽名:2006年,Gentry等人[4]提出一種高效的IBAS方案,然而該方案需要所有簽名者共享狀態(tài)信息,使應(yīng)用場(chǎng)景受到限制;2007年,Boldyreva等人[5]提出有序IBAS方案,克服了Gentry方案的共享問(wèn)題;2016年,Muranaka等人[6]改進(jìn)了Boldyreva方案,針對(duì)動(dòng)態(tài)源路由協(xié)議提出有序IBAS方案,該方案相較于Boldyreva方案,計(jì)算性能明顯提高;2019年,Kojima等人[7]在Muranaka方案基礎(chǔ)上進(jìn)行改進(jìn),引入分布式密鑰生成中心(key generation center, KGC),消除集中式KGC;2020年,安濤等人[8]針對(duì)車輛自組織網(wǎng)(vechicular adhoc network, VANET)提出一種基于國(guó)密SM9算法的IBAS方案,然而該方案聚合簽名長(zhǎng)度和簽名車輛數(shù)量呈線性相關(guān),導(dǎo)致通信開銷較大.基于身份的聚合簽名雖然性能較好,但是其密鑰生成必須借助可信第三方,導(dǎo)致密鑰托管的問(wèn)題無(wú)法避免.

2) 無(wú)證書聚合簽名:2018年,Kumar等人[9]針對(duì)醫(yī)療無(wú)線傳感器網(wǎng)絡(luò)(healthcare wireless sensor networks, HWSNs)構(gòu)造CLAS方案,該方案計(jì)算開銷小于其他同類方案;2019年,Kumar等人[10]針對(duì)VANET,在其之前方案[9]上構(gòu)造CLAS方案,通過(guò)偽身份實(shí)現(xiàn)車輛的隱私保護(hù);2022年,蒙彤等人[11]針對(duì)HWSNs提出支持并行密鑰隔離CLAS方案,有效降低HWSNs系統(tǒng)的延遲.無(wú)證書聚合簽名方案中部分私鑰由半可信的第三方生成,另一部分私鑰由用戶自身產(chǎn)生,所以消除了密鑰托管問(wèn)題.當(dāng)前大部分CLAS方案中都基于雙線性對(duì),導(dǎo)致效率較低,實(shí)用性較差.

3) 基于公鑰基礎(chǔ)設(shè)施的聚合簽名:2019年,Verma等人[12]針對(duì)醫(yī)療監(jiān)控提出無(wú)配對(duì)的基于證書的AS方案,然而該方案存在聚合簽名長(zhǎng)度與簽名者數(shù)量呈線性相關(guān)的問(wèn)題;同年,Verma等人[13]提出另一種基于證書的AS方案,該方案聚合簽名更為緊湊;2021年,Verma等人[14]針對(duì)物聯(lián)網(wǎng)環(huán)境提出無(wú)配對(duì)的基于證書的短聚合簽名方案,計(jì)算開銷更小;同年,Zhu等人[15]分析文獻(xiàn)[14]方案安全缺陷,針對(duì)無(wú)線醫(yī)療傳感器網(wǎng)絡(luò)提出一種支持用戶匿名保護(hù)的基于證書的AS方案并證明其安全性.基于公鑰基礎(chǔ)設(shè)施的聚合簽名需要對(duì)證書的管理付出一定的代價(jià),由于PKI已經(jīng)廣泛應(yīng)用于各種現(xiàn)實(shí)場(chǎng)景中,因此基于PKI的聚合簽名可以更好地與已部署的公鑰基礎(chǔ)設(shè)施相結(jié)合.

2022年,Goyal等人[2]針對(duì)驗(yàn)證者驗(yàn)證指定明文和聚合簽名時(shí),仍需獲取完整明文集合的問(wèn)題,提出局部可驗(yàn)證聚合簽名的概念.驗(yàn)證方對(duì)聚合簽名驗(yàn)證時(shí),無(wú)需完整明文集合,僅需指定消息及對(duì)應(yīng)短提示即可,并給出基于RSA以及雙線性對(duì)的2種局部可驗(yàn)證聚合簽名構(gòu)造方案,并證明其安全性.

2 基于SM2的局部可驗(yàn)證聚合簽名方案

本文基于聚合簽名和局部可驗(yàn)證簽名的思想,對(duì)SM2算法進(jìn)行適當(dāng)?shù)母脑?提出了一種基于國(guó)密SM2算法的局部可驗(yàn)證聚合簽名方案(locally verifiable aggregate signature scheme based on SM2, SM2-LVAS).形式化地表示為SM2-LVAS=(Setup,Key-Gen,Sign,Verify,Aggregate-Signature,Aggregate-Verify,Local-Open,Local-Aggregate-Verify),算法共8個(gè)步驟.

2.1 系統(tǒng)建立

定義大素?cái)?shù)p,Fp為有限域,a,b∈Fp為橢圓曲線E的參數(shù),橢圓曲線上的基點(diǎn)(x,y),其中x,y∈Fp,n為群G的階,Hv()為摘要長(zhǎng)度為v(單位為b)的哈希算法.

2.2 密鑰生成

SM2算法密鑰生成流程如下:

1) 選取隨機(jī)數(shù)d,并且d∈[1,n-2];

2) 計(jì)算P=dG,則其公私鑰對(duì)為(P,d).

2.3 單個(gè)SM2簽名

假設(shè)簽名者為A,其公私鑰對(duì)為(PA,dA),對(duì)于待簽名消息Mi,隨機(jī)選取ki∈[1,n-1].

1) 計(jì)算ZA=H256(ENTLA‖IDA‖a‖b‖xG‖yG‖xA‖yA),其中IDA為用戶可辨識(shí)標(biāo)識(shí),ENTLA為IDA長(zhǎng)度轉(zhuǎn)化而成的2B數(shù)據(jù);

4) 計(jì)算(xi,yi)=kiG;

5) 計(jì)算ri=(ei+xi) modn;

6) 計(jì)算si=((1+dA)-1·(ki-ridA)) modn;

7) 計(jì)算vi=(ei+yi) modn.

單個(gè)簽名為(ri,si,vi).

2.4 單個(gè)SM2驗(yàn)簽

對(duì)收到的消息Mi及其數(shù)字簽名(ri,si,vi)進(jìn)行驗(yàn)簽,其過(guò)程如下:

1) 檢驗(yàn)ri,si,vi∈[1,n]是否成立,若不成立,則驗(yàn)證不通過(guò);

2) 計(jì)算ZA=H256(ENTLA‖IDA‖a‖b‖xG‖yG‖xA‖yA);

5) 計(jì)算ti=(ri+si) modn;

6) 計(jì)算(xi,yi)=siG+tiPA;

7) 計(jì)算R′=(ei+xi) modn.

檢查R′=ri是否成立,成立則驗(yàn)證通過(guò),否則失敗.

2.5 簽名聚合

消息集合{M1,M2,…,Mi,…,ML}的數(shù)字簽名為{(r1,s1,v1),(r2,s2,v2),…,(ri,si,vi),…,(rL,sL,vL)}.簽名聚合過(guò)程如下:

1) 計(jì)算E=Hv(e1‖e2‖…‖eL);

2) 計(jì)算xi=(ri-ei) modn;

3) 計(jì)算yi=(vi-ei) modn;

5) 計(jì)算R=(E+x) modn;

7) 計(jì)算ti=(ri+si) modn;

聚合簽名為σ=(R,U,W,t1,t2,…,tL).

2.6 聚合驗(yàn)證

驗(yàn)證方收到消息集合{M1,M2,…,Mi,…,ML}和聚合簽名σ.聚合驗(yàn)證過(guò)程如下:

2) 計(jì)算ZAi=H256(ENTLAi‖IDAi‖a‖b‖xG‖yG‖xAi‖yAi);

5) 計(jì)算d=Hv(e1‖e2‖…‖eL);

7) 計(jì)算R′=(d+x) modn.

當(dāng)簽名者相同時(shí),橢圓曲線上的點(diǎn)(x,y)的計(jì)算可簡(jiǎn)化為(x,y)=UG+WPA.

檢查等式R′=R是否成立,若成立則驗(yàn)證通過(guò),否則驗(yàn)證失敗.

2.7 提示生成

提示生成算法一般由存儲(chǔ)服務(wù)器或簽名聚合方進(jìn)行計(jì)算.通過(guò)消息明文集合計(jì)算得到指定消息的短提示auxj.提示生成過(guò)程如下:

1) 計(jì)算ZAi=H256(ENTLAi‖IDAi‖a‖b‖xG‖yG‖xAi‖yAi);

4) 計(jì)算E=Hv(e1‖e2‖…‖eL);

5) 計(jì)算auxj1=(E-ej) modn;

6) 計(jì)算h1=Hv(auxj1);

8) 計(jì)算auxj2=(h1+x) modn;

9) 計(jì)算auxj3=(h1+y) modn;

10)輸出短提示auxj=(auxj1,auxj2,auxj3).

2.8 局部驗(yàn)證

驗(yàn)證方收到指定消息明文Mj、聚合簽名σ和短提示auxj.局部驗(yàn)證過(guò)程如下:

2) 計(jì)算ZAj=H256(ENTLAj‖IDAj‖a‖b‖xG‖yG‖xAj‖yAj);

5) 計(jì)算d=(auxj1+ej) modn;

6) 計(jì)算h1=Hv(auxj1);

7) 計(jì)算xj=(auxj2-h1) modn;

8) 計(jì)算yj=(auxj3-h1) modn;

9) 計(jì)算(x,y)=(xj,yj)+UG+tjPAj;

10) 計(jì)算R′=(d+x) modn.

檢查等式R′=R是否成立,若成立則驗(yàn)證通過(guò),否則驗(yàn)證不通過(guò).

3 方案分析

3.1 正確性分析

令E=Hv(e1‖e2‖…‖eL),則相同簽名者時(shí)的聚合驗(yàn)證公式為

(1)

則只需驗(yàn)證

(2)

其證明過(guò)程如式(3)所示.不同簽名者時(shí)及局部驗(yàn)證時(shí)的證明過(guò)程與相同簽名者時(shí)相似,不再贅述.

(3)

3.2 安全性分析

SM2-LAVS方案單個(gè)SM2簽名步驟,相較于標(biāo)準(zhǔn)SM2算法簽名流程,對(duì)于明文Mi,生成簽名由(ri,si)變?yōu)?ri,si,vi),其中vi=(ei+yi).如果敵手得到明文Mi哈希值ei,則可計(jì)算出yi,而在SM2算法標(biāo)準(zhǔn)驗(yàn)簽流程中,檢驗(yàn)

R′=(ei+xi)=ri,

(4)

其中xi通過(guò)(xi,yi)=siG+tiPA計(jì)算得到.由此可知,敵手可通過(guò)一定的計(jì)算得到簽名時(shí)的xi,yi,因此,在單個(gè)SM2簽名步驟中新增vi字段并不會(huì)使本文方案安全性低于SM2標(biāo)準(zhǔn)算法.

在聚合驗(yàn)證步驟時(shí),需要驗(yàn)證

(5)

(6)

在局部驗(yàn)證步驟時(shí),需要驗(yàn)證

R′=R,

(7)

auxj1+ej+x=R.

(8)

4 方案實(shí)現(xiàn)與性能分析

本文使用C++語(yǔ)言實(shí)現(xiàn)SM2-LAVS方案并調(diào)用GmSSL庫(kù)實(shí)現(xiàn)SM2中橢圓曲線上計(jì)算.實(shí)際開發(fā)環(huán)境中CPU為Intel i5-9400,內(nèi)存為8GB,操作系統(tǒng)為Ubuntu 18.04.

表1定義了密碼運(yùn)算的符號(hào),并通過(guò)重復(fù)運(yùn)行1000次運(yùn)算取其平均值的方法得出單次運(yùn)算所消耗時(shí)間.

表1 單次密碼運(yùn)算所消耗時(shí)間 ms

表2分析了在相同簽名者和不同簽名者2種情況下各個(gè)步驟計(jì)算成本對(duì)比.

表3對(duì)比了幾種聚合簽名方案及本文方案的計(jì)算成本.

圖1所示為不同聚合簽名方案聚合驗(yàn)證時(shí)間開銷對(duì)比.

由圖1可知,隨著明文消息數(shù)量增大,本文方案聚合驗(yàn)證開銷在幾個(gè)方案中最小,因此,本文方案與同類方案相比,具有較高性能.

表2 各個(gè)步驟計(jì)算成本對(duì)比

表3 各個(gè)聚合簽名方案計(jì)算成本對(duì)比

圖1 不同聚合簽名方案時(shí)間開銷對(duì)比

5 結(jié) 語(yǔ)

本文基于國(guó)密SM2算法設(shè)計(jì)一種局部可驗(yàn)證聚合簽名方案,利用聚合簽名提高驗(yàn)證方驗(yàn)證效率,通過(guò)局部可驗(yàn)證使驗(yàn)證方對(duì)聚合簽名及指定明文驗(yàn)證時(shí),無(wú)需獲取全部明文.通過(guò)與現(xiàn)有若干個(gè)聚合簽名方案對(duì)比,證明本文方案聚合驗(yàn)證開銷更低,具有一定優(yōu)勢(shì).但本文方案聚合簽名長(zhǎng)度與簽名者數(shù)量呈線性相關(guān),將來(lái)可以進(jìn)一步優(yōu)化,將簽名長(zhǎng)度優(yōu)化為常量值,降低通信開銷.