王宏，賴成喆，劉向陽(yáng)，曾晗

（1.國(guó)防科技大學(xué)信息通信學(xué)院，陜西 西安 710106；2.西安郵電大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，陜西 西安 710121）

0 引言

隨著無(wú)線通信、傳感器及人工智能等技術(shù)的不斷進(jìn)步，各種態(tài)勢(shì)感知網(wǎng)絡(luò)在氣象水文監(jiān)測(cè)、城市智慧交通、能源在線監(jiān)測(cè)等方面發(fā)揮著越來(lái)越重要的作用。技術(shù)進(jìn)步帶來(lái)便捷的同時(shí)，也導(dǎo)致人們受制于技術(shù)，尤其是個(gè)人信息的被盜、冒充或偽造等現(xiàn)象時(shí)有發(fā)生，極易造成態(tài)勢(shì)感知網(wǎng)絡(luò)的不暢，甚至癱瘓。因此，如圖1 所示，對(duì)網(wǎng)絡(luò)傳遞的消息進(jìn)行簽名，確保消息的可靠性、完整性和不可抵賴性成為一種重要的網(wǎng)絡(luò)安全措施。傳統(tǒng)的數(shù)字簽名采用逐一驗(yàn)證方法，當(dāng)中心型節(jié)點(diǎn)驗(yàn)證的簽名數(shù)量較少時(shí)，逐一驗(yàn)證方法尚且可以適應(yīng)要求；當(dāng)需要驗(yàn)證的簽名數(shù)量巨大時(shí)，逐一驗(yàn)證需要消耗大量時(shí)間，導(dǎo)致大量消息由于不能及時(shí)得到驗(yàn)證而被迫丟棄，比如龐大的車(chē)聯(lián)網(wǎng)系統(tǒng)每隔100～300 ms 就要實(shí)時(shí)地進(jìn)行消息傳輸，大量的消息連同附帶的簽名涌向中心節(jié)點(diǎn)等待馬上驗(yàn)證[1-2]，以保證它們來(lái)源的可靠性。因此，有關(guān)數(shù)字簽名的快速驗(yàn)證算法的研究成為近年密碼學(xué)的研究熱點(diǎn)。

圖1 中心型網(wǎng)絡(luò)消息匯聚

圍繞數(shù)字簽名快速驗(yàn)證算法，研究者所做的工作歸納為2 個(gè)方面：一是數(shù)字簽名的批量驗(yàn)證算法研究；二是分組檢測(cè)方案設(shè)計(jì)。數(shù)字簽名的批量驗(yàn)證通常采取聚合簽名算法，聚合簽名是將具有同態(tài)結(jié)構(gòu)的簽名算法進(jìn)行聚合驗(yàn)證，達(dá)到一次性驗(yàn)證多個(gè)數(shù)字簽名的目的，基于模指數(shù)運(yùn)算的數(shù)字簽名算法（DSA,digital signature algorithm）就具有這種同態(tài)結(jié)構(gòu)[3-7]。近年來(lái)，許多聚合簽名研究成果實(shí)現(xiàn)并證明了簽名密鑰的生成、分發(fā)和數(shù)字簽名的聚合驗(yàn)證[8-11]，但聚合簽名只能批量檢測(cè)多個(gè)數(shù)字簽名的集合中是否存在非法數(shù)字簽名，不能鑒別非法數(shù)字簽名在集合中的具體位置。為此，研究者紛紛引入已在生物醫(yī)學(xué)檢測(cè)中廣泛應(yīng)用的分組檢測(cè)理論進(jìn)行數(shù)字簽名的分組檢測(cè)。當(dāng)數(shù)字簽名集合中存在非法數(shù)字簽名時(shí)，通過(guò)將數(shù)字簽名分成不同的組，分組實(shí)施批量驗(yàn)證，從而逐步確定非法數(shù)字簽名。

分組檢測(cè)方案是針對(duì)數(shù)字簽名聚合驗(yàn)證存在至少一個(gè)非法數(shù)字簽名而進(jìn)行非法對(duì)象識(shí)別的分組聚合驗(yàn)證方法，按照分組之間的關(guān)系，可以分為序貫類分組檢測(cè)和非適應(yīng)性分組檢測(cè)[12]。序貫類分組檢測(cè)是按照一定規(guī)則對(duì)檢測(cè)對(duì)象進(jìn)行“多次”有序分組檢測(cè)，直到所有非法對(duì)象被全部識(shí)別。但在序貫類分組檢測(cè)中，前一次檢測(cè)的結(jié)果決定后一次分組的情況，檢測(cè)過(guò)程具有嚴(yán)格的順序性，只能一步一步按照分組順序完成，如基于二元分叉樹(shù)的分組檢測(cè)。非適應(yīng)性分組檢測(cè)是根據(jù)一定規(guī)則巧妙地將檢測(cè)對(duì)象“一次性”分成若干組，同一檢測(cè)對(duì)象可以包含在多個(gè)組中，使檢測(cè)具有一定數(shù)量的對(duì)象析取性，便于采用平行檢測(cè)的方法對(duì)各組進(jìn)行同時(shí)檢測(cè)，并通過(guò)檢測(cè)結(jié)果的呈現(xiàn)情況析取非法數(shù)字簽名[3]。序貫類分組檢測(cè)簡(jiǎn)單、實(shí)現(xiàn)容易，但運(yùn)算效率很難提高[13-14]。非適應(yīng)性分組檢測(cè)可以并行檢測(cè)，在多處理器的情況下，運(yùn)算效率較高，但分組方案構(gòu)造復(fù)雜?，F(xiàn)有的非適應(yīng)性分組檢測(cè)算法具有以下3個(gè)特點(diǎn)：一是分組檢測(cè)的次數(shù)、時(shí)間等參數(shù)界限研究探索較多[15-16]，而具體方案構(gòu)造研究成果較少；二是分組檢測(cè)方案構(gòu)造不準(zhǔn)確，存在非法數(shù)字簽名不能完全析出的情況，如隨機(jī)矩陣法[12]；三是分組檢測(cè)方案的存在性理論缺乏嚴(yán)格證明，如基于糾錯(cuò)碼（ECC,error correction code）的分組方案構(gòu)建，缺少檢測(cè)對(duì)象數(shù)量變化時(shí)的分組方案存在性證明[3,17-18]。

綜上所述，本文針對(duì)數(shù)字簽名的快速驗(yàn)證問(wèn)題，研究分組批量驗(yàn)證算法，基于拉丁方理論構(gòu)造分組方案，以較少次數(shù)的群組認(rèn)證完成非法數(shù)字簽名的識(shí)別，實(shí)現(xiàn)多個(gè)消息數(shù)字簽名的快速驗(yàn)證。本文主要貢獻(xiàn)如下。

1) 采用拉丁方理論構(gòu)建橫截設(shè)計(jì)。以有限域理論為基礎(chǔ)設(shè)計(jì)素?cái)?shù)冪階拉丁方，證明素?cái)?shù)冪階拉丁方存在性是橫截設(shè)計(jì)存在的充分必要條件，為數(shù)字簽名分組批量驗(yàn)證方案確立提供理論基礎(chǔ)。

2) 基于橫截設(shè)計(jì)理論構(gòu)建析取矩陣。證明當(dāng)橫截設(shè)計(jì)TD[k,;λm]的λ=1 時(shí)，其關(guān)聯(lián)矩陣M的轉(zhuǎn)置矩陣MT是一個(gè)析取矩陣，將區(qū)組設(shè)計(jì)與析取矩陣聯(lián)系起來(lái)，為析取矩陣的構(gòu)建提供具體方法。

3) 通過(guò)析取矩陣?yán)碚摯_定分組方案。以析取矩陣的列向量選擇性為基礎(chǔ)，根據(jù)檢測(cè)對(duì)象的總數(shù)量以及其中包含非法者的數(shù)量確定析取矩陣的階數(shù)，并由此構(gòu)建分組檢測(cè)方案，完成檢測(cè)，根據(jù)分組檢測(cè)結(jié)果推斷非法數(shù)字簽名在集合中的位置。

4) 對(duì)所提數(shù)字簽名分組批量驗(yàn)證方案進(jìn)行理論分析與仿真驗(yàn)證。理論分析證明了所提方案的正確性、安全性、高效性，并以Linux Ubantu20 為平臺(tái)、Python3.9 為編程語(yǔ)言，引入雙線性對(duì)函數(shù)庫(kù)pypbc，基于成熟的BGLS 聚合簽名算法[19]進(jìn)行數(shù)字簽名批量驗(yàn)證，仿真實(shí)現(xiàn)分組檢測(cè)算法并識(shí)別非法對(duì)象。結(jié)果表明，所提方案能準(zhǔn)確可靠地識(shí)別非法對(duì)象，同時(shí)在多個(gè)處理器并行計(jì)算時(shí)相較其他算法檢測(cè)效率有所提高。

1 相關(guān)知識(shí)

本節(jié)介紹析取矩陣、區(qū)組設(shè)計(jì)、關(guān)聯(lián)矩陣等非適應(yīng)性分組檢測(cè)的相關(guān)概念和背景知識(shí)。析取矩陣[12]用于非適應(yīng)分組檢測(cè)方案的非法數(shù)字簽名的識(shí)別分析；區(qū)組設(shè)計(jì)[20]用于構(gòu)造非適應(yīng)性分組檢測(cè)方案；關(guān)聯(lián)矩陣[21]用于區(qū)組設(shè)計(jì)的矩陣化表示，是區(qū)組設(shè)計(jì)研究的一個(gè)有力的代數(shù)工具。

定義1d階析取矩陣[12]。對(duì)于0-1 矩陣Mt×n，若任意d列的并集不包含其他列向量，即，則稱Mt×n為d階析取矩陣。換句話講，對(duì)于任意d+1 列，必然存在至少一行（不妨設(shè)為第i行），使d列的元素mij=0，即并集=0，而

定義2區(qū)組設(shè)計(jì)[20]。有限集合X上的任意一個(gè)子集族B={B1,…,Bt}為X上的一個(gè)區(qū)組設(shè)計(jì)，記作D={X,B}。X稱為此設(shè)計(jì)的基集，而子集族B中的諸子集Bi(i=1,…,t)則稱為此設(shè)計(jì)的區(qū)組。

常見(jiàn)的區(qū)組設(shè)計(jì)包括成對(duì)平衡設(shè)計(jì)（PBD,pairwise balanced design）、可分組設(shè)計(jì)（GDD,group divisible design）、橫截設(shè)計(jì)（TD,transversal design）、平衡不完全區(qū)組設(shè)計(jì)（BIBD,balanced incomplete block design）等[22]，本文主要應(yīng)用橫截設(shè)計(jì)進(jìn)行區(qū)組設(shè)計(jì)。

定義3橫截設(shè)計(jì)[22]。對(duì)于區(qū)組設(shè)計(jì)D={X,B}，若有限集合X的一個(gè)劃分為G={G1,…,G k}（其中Gj,j=1,…,k稱為組），且滿足以下三點(diǎn)。

1) 對(duì)任意B∈B，=k。

2) 對(duì)任意Gj∈G，=m。

3)X中屬于同一組的不同元素在區(qū)組中的相遇數(shù)λD(x,y)總為零，而屬于不同組的2 個(gè)元素x,y的相遇數(shù)λD(x,y)是不依賴于x,y的常數(shù)，即對(duì)于任意x,y∈X，x≠y，有

則稱其為橫截設(shè)計(jì)，記作TD[k,λ;m]。

定義4關(guān)聯(lián)矩陣[21]。對(duì)于區(qū)組設(shè)計(jì)D={X,B}，其中有限集合X={x1,…,xn}及其子集族B={B1,…,Bt}，存在 0-1 矩陣Mt×n={mij}，i=1,…,t，j=1,…,n，t表示區(qū)組個(gè)數(shù)，n表示基集X元素個(gè)數(shù)，且

則稱Mt×n為區(qū)組設(shè)計(jì)的關(guān)聯(lián)矩陣。

2 非適應(yīng)性分組檢測(cè)模型

根據(jù)分組檢測(cè)對(duì)象數(shù)量進(jìn)行區(qū)組設(shè)計(jì)，構(gòu)建非適應(yīng)性分組檢測(cè)模型，關(guān)鍵在于尋找相應(yīng)的析取矩陣，本文首先運(yùn)用拉丁方理論進(jìn)行區(qū)組設(shè)計(jì)——橫截設(shè)計(jì)，然后證明構(gòu)造的橫截設(shè)計(jì)對(duì)應(yīng)的關(guān)聯(lián)矩陣是析取矩陣，最后再運(yùn)用析取矩陣進(jìn)行分組檢測(cè)，完成非法對(duì)象的識(shí)別。

2.1 基于拉丁方理論的橫截設(shè)計(jì)

橫截設(shè)計(jì)是構(gòu)造區(qū)組設(shè)計(jì)的重要方法之一，它與正交拉丁方理論有著密切關(guān)系。正交拉丁方是組合設(shè)計(jì)的一個(gè)重要研究課題，在橫截設(shè)計(jì)的遞歸構(gòu)造方法中，正交拉丁方組對(duì)于橫截設(shè)計(jì)的存在性起著十分關(guān)鍵的作用。下面首先介紹正交拉丁方的一些概念和基本性質(zhì)，然后論證它與橫截設(shè)計(jì)的關(guān)系，最后給出正交拉丁方的構(gòu)造方法，從而完成橫截設(shè)計(jì)的構(gòu)造。

定義5拉丁方[22]。設(shè)S是一個(gè)m元集，若A為S上的一個(gè)m×m階陣列（即矩陣），其每一行與每一列都是集合S的一個(gè)全排列，則稱A是S上的一個(gè)m階拉丁方。

定義6正交拉丁方[22]。對(duì)于集合S和S′上的2 個(gè)m階拉丁方A=(aij)和B=(bij)，A和B在(i,j)位置上的有序?qū)?aij,bij)∈S×S′稱為一個(gè)對(duì)子，A和B在全部m2個(gè)不同位置上的對(duì)子兩兩不同，即=m2，則稱拉丁方A和B正交。若一組m階拉丁方A1,…,At兩兩正交，則稱其為一個(gè)正交拉丁方組。

對(duì)于矩陣

根據(jù)定義6，顯然H與其轉(zhuǎn)置矩陣G=HT正交。顯然，若A是{1,…,m}上的任一m×m階陣列，則A是m階拉丁方的充要條件是A與H及A與G都正交。

定理1[22]存在TD[k,1;m]的充要條件是存在一個(gè)k-2個(gè)m階正交拉丁方組。

證明令D=(X,G,B)是個(gè)TD[k,1;m]，根據(jù)TD 定義，則對(duì)任一B∈B 及任一Gj∈G，有=1，即任一區(qū)組B由每個(gè)組中各取一個(gè)元素組成。任取劃分G的2 個(gè)不同的組G1和G2（劃分的每個(gè)組中含有m個(gè)元素），由于B中的每個(gè)區(qū)組恰好包含了一個(gè)G1的元素和一個(gè)G2的元素，且由于λ=1，G1的元素和G2的元素在B的每個(gè)區(qū)組中總共相遇一次，因此B的區(qū)組數(shù)等于G1中所有元素和G2中所有元素的相遇總次數(shù)，即

因此，B中共有m2個(gè)區(qū)組，G1的m個(gè)元素和G2的m個(gè)元素在B的每個(gè)區(qū)組中僅僅相遇一次，故G1和G2元素在區(qū)組設(shè)計(jì)B 中組成的有序數(shù)對(duì){(g1,g2)|g1∈G1,g2∈G2}僅僅出現(xiàn)一次可以看成{1,…,m}上2 個(gè)正交的陣列，那么G1,…,G k的元素在區(qū)組設(shè)計(jì)B中兩兩組成的有序數(shù)對(duì)僅僅出現(xiàn)一次可以看成{1,…,m}上兩兩正交的陣列，除了H和G，則一定還存在k-2個(gè)正交拉丁方。

反之，若存在k-2 個(gè)m階正交拉丁方，加上H和G，便可以構(gòu)造k個(gè)兩兩正交的m階陣列組，這些陣列兩兩之間每個(gè)元素對(duì)僅僅出現(xiàn)一次，照此便可以構(gòu)造出一個(gè)TD[k,1;m]。證畢。

然而，并不是任意階的正交拉丁方都是存在的，Bose、Shrikhande 和Parker 三人經(jīng)過(guò)共同努力，證明了若n≠2,6則必定存在一對(duì)拉丁方。由上述定理可知，在構(gòu)造橫截設(shè)計(jì)時(shí)，需要盡可能多的拉丁方。根據(jù)有限域存在定理[23]，對(duì)于任意素?cái)?shù)冪pτ，存在一個(gè)含有pτ個(gè)元素的有限域，顯然TD[k,1;m]的約束和有限域的特征非常相似，下面介紹通過(guò)有限域構(gòu)造正交拉丁方組的方法。

則 (e1-e2)i=(e1-e2)k。

由于e1≠e2，故(e1-e2)-1，因此i=k，代入可得j=l。

綜上所述，A(1),A(2),…,A(m-1)是兩兩正交的拉丁方組。證畢。

2.2 基于橫截設(shè)計(jì)的析取矩陣

析取矩陣是一類二元疊加碼，可以用作分組檢測(cè)的一種數(shù)學(xué)模型，廣泛應(yīng)用在信息傳輸中的多路存取信道、分子生物學(xué)、基因遺傳測(cè)試、病毒分組檢測(cè)等諸多方面，橫截設(shè)計(jì)TD[k,1;m]關(guān)聯(lián)矩陣M的轉(zhuǎn)置矩陣具備析取矩陣的特征，以下將從理論上證明這種推斷。

在t行n列的0-1 矩陣M中，Cj表示第j列向量；wj表示第j列向量Cj的重量，即Cj中“1”的個(gè)數(shù)；λij表示列向量Ci與Cj的點(diǎn)乘，即Ci與Cj相同行上都為1的個(gè)數(shù)，也稱為Ci與Cj相交λij次。

定理3當(dāng)TD[k,;λm]設(shè)計(jì)的λ=1 時(shí)，其關(guān)聯(lián)矩陣M的轉(zhuǎn)置矩陣MT的λT=0 或1，則MT是k-1階析取矩陣。

證明當(dāng)λ=1 時(shí)，TD 區(qū)組設(shè)計(jì)對(duì)應(yīng)關(guān)聯(lián)矩陣M的任意兩列的內(nèi)積為1，即M的任意兩列僅僅有一次在相同位置（行）都為“1”，則M的任意兩行元素僅僅有一次在相同位置（列）都為“1”，下面用反證法進(jìn)行證明。假設(shè)M的任意兩行元素至少有兩次在相同位置（列）都為“1”，此時(shí)M的任意兩列元素至少有兩次在相同位置（行）都為“1”，與λ=1相矛盾，故M的轉(zhuǎn)置矩陣MT的λT=0或1，則=1，此時(shí)，由引理1可知MT是k-1（即w-1）階析取矩陣。證畢。

2.3 基于析取矩陣的分組檢測(cè)

采用分組檢測(cè)進(jìn)行數(shù)字簽名驗(yàn)證，將數(shù)字簽名進(jìn)行分組，分組結(jié)果用關(guān)聯(lián)矩陣Mt×n表示，其中矩陣的列對(duì)應(yīng)要檢驗(yàn)的數(shù)字簽名，矩陣的行對(duì)應(yīng)分組，Mt×n中元素{mij}的取值參考定義4。

不妨假設(shè)將要進(jìn)行分組批量驗(yàn)證的數(shù)字簽名集合Σ=(σ1,…,σn)的狀態(tài)為X=(x1,…,xn)，其中xi(i=1,…,n)表示每個(gè)數(shù)字簽名的實(shí)際狀態(tài)，xi=0表示第i個(gè)數(shù)字簽名合法，xi=1表示第i個(gè)數(shù)字簽名非法。為了快速進(jìn)行數(shù)字簽名驗(yàn)證，運(yùn)用2.1 節(jié)的橫截設(shè)計(jì)對(duì)數(shù)字簽名進(jìn)行分組，并行進(jìn)行分組檢測(cè)，用Y表示分組檢測(cè)結(jié)果，記為Y=(y1,…,yt)，其中yj=0(j=1,…,t)表示本組檢測(cè)的數(shù)字簽名集合全部合法，yj=1(j=1,…,t)表示本組檢測(cè)的數(shù)字簽名集合至少包含一個(gè)非法數(shù)字簽名，它與X和Mt×n的關(guān)系可以表示為

根據(jù)2.2 節(jié)的證明，上述分組批量檢測(cè)區(qū)組設(shè)計(jì)的關(guān)聯(lián)矩陣Mt×n為d階析取矩陣，當(dāng)數(shù)字簽名集合X中非法數(shù)字簽名的個(gè)數(shù)不超過(guò)d時(shí)，運(yùn)用算法1 便可以確定非法數(shù)字簽名。

算法1非法數(shù)字簽名分組檢測(cè)法

3 數(shù)字簽名分組檢測(cè)實(shí)施

網(wǎng)絡(luò)的中心節(jié)點(diǎn)每秒接收到大量節(jié)點(diǎn)發(fā)來(lái)的消息，為加快消息簽名的驗(yàn)證速度，通常采用“聚合簽名+分組檢測(cè)”的方法進(jìn)行數(shù)字簽名的驗(yàn)證，如圖2 所示。首先采用聚合簽名算法將所有來(lái)自不同節(jié)點(diǎn)的消息簽名設(shè)計(jì)為具有同態(tài)性特征，便于后續(xù)聚合驗(yàn)證作為中心節(jié)點(diǎn)的信息處理中心先將所有消息及其簽名進(jìn)行一次聚合驗(yàn)證，若驗(yàn)證成功，則表明所有消息合法；否則，證明消息集合中至少存在一個(gè)非法對(duì)象，需要進(jìn)一步采取非適應(yīng)性分組的思想進(jìn)行分組聚合驗(yàn)證，用i表示分組序號(hào)，i取遍t個(gè)分組，通過(guò)分組驗(yàn)證的結(jié)果排除合法對(duì)象，從而確定非法對(duì)象，當(dāng)出現(xiàn)無(wú)法確定的對(duì)象時(shí)還可以補(bǔ)充進(jìn)行個(gè)體認(rèn)證。由此可見(jiàn)，實(shí)現(xiàn)消息簽名批量驗(yàn)證的是聚合簽名算法，識(shí)別非法對(duì)象依靠分組檢測(cè)，不同的分組方案對(duì)應(yīng)著不同的識(shí)別效率。

圖2 數(shù)字簽名快速驗(yàn)證方法

3.1 聚合簽名

為提高數(shù)字簽名的驗(yàn)證效率，在一般數(shù)字簽名算法的基礎(chǔ)上，楊濤等[8]提出一種具有同態(tài)性結(jié)構(gòu)的變體數(shù)字簽名算法，驗(yàn)證者能夠?qū)?lái)自任意不同節(jié)點(diǎn)的多個(gè)數(shù)字簽名壓縮合成為與單個(gè)數(shù)字簽名幾乎同等大小的短簽名進(jìn)行批量驗(yàn)證，大大減小了多個(gè)簽名驗(yàn)證的工作量，這就是聚合簽名。聚合簽名由于其高效性、簡(jiǎn)捷性，廣泛應(yīng)用于安全路由協(xié)議、網(wǎng)云信息聚合、日志審計(jì)、分布式計(jì)算等方面，在諸多信息科技領(lǐng)域發(fā)揮著重要的安全保護(hù)作用，成為近年來(lái)被關(guān)注的一個(gè)研究熱點(diǎn)。本文采用經(jīng)典的BGLS 聚合簽名算法[19]完成消息簽名的批量驗(yàn)證，下面對(duì)該算法進(jìn)行闡述。

設(shè)G1和G2是2 個(gè)p階的乘法循環(huán)群（p為素?cái)?shù)），g1和g2分別是G1和G2的生成元；ψ:G1→G2是一個(gè)同構(gòu)映射，且ψ(g1)=g2；e:G1×G2→GT是一個(gè)雙線性對(duì)運(yùn)算；h:{0,1}*→G2是一個(gè)雜湊函數(shù)，可以看作一個(gè)隨機(jī)預(yù)言機(jī)。

密鑰生成。選擇隨機(jī)數(shù)x∈RZp，計(jì)算v=則v∈G1作為用戶的公鑰，x∈Zp作為用戶的私鑰。

簽名生成。對(duì)于用戶u i∈U，公鑰為vi，私鑰為xi，需要簽名的消息為Mi∈{0,1}*，可得hi=h(Mi)，σi=。

BGLS 聚合簽名算法的安全性等價(jià)于隨機(jī)預(yù)言模型下CDH（computational Diffie-Hellman）問(wèn)題的安全性。

3.2 實(shí)施步驟

假設(shè)檢測(cè)n=m2（m為素?cái)?shù)或素?cái)?shù)冪）個(gè)數(shù)字簽名集合，其中含有不超過(guò)d=k-1個(gè)非法數(shù)字簽名，根據(jù)拉丁方理論便可以構(gòu)造一個(gè)橫截設(shè)計(jì)TD[k,1;m]，當(dāng)m＞k時(shí)，通過(guò)km次分組檢測(cè)完成m2個(gè)數(shù)字簽名的驗(yàn)證，識(shí)別出非法數(shù)字簽名，如圖3所示，具體步驟如下。

圖3 數(shù)字簽名分組檢測(cè)實(shí)施步驟

步驟1確定分組檢測(cè)參數(shù)設(shè)置。根據(jù)需要檢測(cè)的數(shù)字簽名集合大小n以及非法對(duì)象數(shù)量上限d，確定橫截設(shè)計(jì)TD[k,1;m]的參數(shù)(k,m)，如果數(shù)字簽名的總數(shù)及非法對(duì)象的個(gè)數(shù)不滿足上述要求，可以進(jìn)行適當(dāng)?shù)娜哂嗵畛洌_(dá)到要求。

步驟2構(gòu)造k-2個(gè)正交拉丁方。采用定理2構(gòu)造k-2個(gè)m階正交拉丁方A(1),…,A(k-2)。

步驟3由H,G,A(1),…,A(k-2)構(gòu)造TD[k,1;m]。

步驟4編寫(xiě)TD[k,1;m]的關(guān)聯(lián)矩陣求出d階析取矩陣

步驟5 按照進(jìn)行分組檢測(cè)，通過(guò)檢測(cè)結(jié)果由算法1 推知非法數(shù)字簽名。

3.3 舉例說(shuō)明

如果對(duì)25 個(gè)數(shù)字簽名進(jìn)行驗(yàn)證，據(jù)前期統(tǒng)計(jì)估計(jì)其中包含非法數(shù)字簽名的數(shù)量不超過(guò)2 個(gè)，則令n=m2=52，d=k-1=2，則k=3，m=5，確定橫截設(shè)計(jì)為T(mén)D[3,1;5]。

利用定理2 構(gòu)造一個(gè)5 階拉丁方矩陣

連同H和G，按照定理1的方法，由3 個(gè)拉丁方一起構(gòu)成一個(gè)橫截設(shè)計(jì)TD[3,1;5]，其關(guān)聯(lián)矩陣為25 行15 列矩陣M25×15，轉(zhuǎn)置后得到15 行25 列0-1 矩陣其中每列有3 個(gè)“1”，每行有5 個(gè)“1”，如圖4 所示。

根據(jù)定理3可知，0-1矩陣TM為2 階析取矩陣。圖4 中的矩陣25 列表示需要驗(yàn)證的25 個(gè)數(shù)字簽名，15 行表示25 個(gè)數(shù)字簽名分成的15 個(gè)分組，矩陣中(i,j) 處的元素“1”表示j列的數(shù)字簽名屬于i行的分組；否則，表示不在此分組。析取矩陣的性質(zhì)表明，按照?qǐng)D4 中分組方案進(jìn)行批量驗(yàn)證，可以通過(guò)15 次分組檢測(cè)對(duì)25 個(gè)數(shù)字簽名完成不超過(guò)2 個(gè)非法對(duì)象的識(shí)別。

為了說(shuō)明分組方案在數(shù)字簽名批量驗(yàn)證中的使用思路，不妨假設(shè)第3、6 個(gè)數(shù)字簽名是非法的，在圖4 中用方框表示，按照分組方案調(diào)用聚合簽名算法完成15 個(gè)分組的批量驗(yàn)證，得到檢測(cè)結(jié)果Y=(1,1,0,0,0,1,0,1,0,0,0,1,1,0,0)T，由于15×25M是2 階析取矩陣，Y中的“0”表示本組檢測(cè)中所有數(shù)字簽名均為合法，根據(jù)算法1，采用排除法可以依次確定合法數(shù)字簽名x11、x12、x13、x14、x15、x16、x17、x18、x19、x20、x21、x22、x23、x24、x25、x2、x7、x4、x9、x5、x10、x1、x8，如圖4 中下劃線所示；根據(jù)析取矩陣的性質(zhì)可知，剩下的簽名x3、x6便為非法數(shù)字簽名。

圖4 15 個(gè)數(shù)字簽名的分組驗(yàn)證的分組情況

4 性能分析

本節(jié)通過(guò)理論證明和仿真實(shí)驗(yàn)，對(duì)本文算法進(jìn)行了可行性和復(fù)雜度分析，并對(duì)非法數(shù)字簽名數(shù)量估計(jì)不準(zhǔn)的情況討論了方案的容錯(cuò)性；同時(shí)借助開(kāi)源的雙線性對(duì)計(jì)算函數(shù)庫(kù)，編程實(shí)現(xiàn)了BGLS 聚合簽名方案和本文算法，仿真驗(yàn)證了數(shù)字簽名分組檢測(cè)方案。結(jié)果表明，在相同安全要求下，本文算法相較于逐一驗(yàn)證具有高效性，即使與經(jīng)典的二分法檢測(cè)相比也具有明顯的效率優(yōu)勢(shì)。

4.1 理論證明

1) 可行性分析

根據(jù)算法1的排除法可知，本文算法是通過(guò)分組檢測(cè)結(jié)果中合法結(jié)果（即檢測(cè)結(jié)果為“0”分組）選出合法數(shù)字簽名，然后取合法數(shù)字簽名對(duì)應(yīng)的余集作為可疑簽名集U=XV，若≤d則確定非法數(shù)字簽名。之所以能夠識(shí)別非法數(shù)字簽名，是因?yàn)殛P(guān)聯(lián)矩陣的析取性，下面根據(jù)析取矩陣的特性，對(duì)其進(jìn)行證明。

定理4群組認(rèn)證關(guān)聯(lián)矩陣是d階析取矩陣，則由分組檢測(cè)的結(jié)果Y通過(guò)算法1 可以識(shí)別不超過(guò)d個(gè)非法數(shù)字簽名。

2) 復(fù)雜度分析

本文算法對(duì)n個(gè)數(shù)字簽名進(jìn)行驗(yàn)證，初步估計(jì)非法數(shù)字簽名的數(shù)量不超過(guò)d個(gè)。下面對(duì)本文算法的復(fù)雜度進(jìn)行分析。

定理5 本文算法進(jìn)行分組檢測(cè)，通過(guò)個(gè)分組完成n個(gè)數(shù)字簽名進(jìn)行驗(yàn)證，非法數(shù)字簽名識(shí)別算法（算法1）的時(shí)間復(fù)雜度為其中d為非法數(shù)字簽名的數(shù)量上限，且d?n。

證明要完成n個(gè)數(shù)字簽名進(jìn)行驗(yàn)證，根據(jù)3.2 節(jié)中的實(shí)施步驟，首先基于拉丁方構(gòu)造了用于分組檢測(cè)的析取矩陣MT，它的行數(shù)為km，列數(shù)為m2，由于k=d+1，n=m2，則

另外，當(dāng)分組批量驗(yàn)證完成后，需要通過(guò)算法1運(yùn)用排除法完成非法數(shù)字簽名的識(shí)別，只有分組批量驗(yàn)證為“0”的分組才參與排除法，不妨用t0表示批量驗(yàn)證Y=(y1,y2,…,ykm)中為“0”的分組，根據(jù)橫截設(shè)計(jì)的“0”“1”分布特征，關(guān)聯(lián)矩陣MT的每列元素“1”的個(gè)數(shù)為k，分組批量驗(yàn)證結(jié)果Y=(y1,y2,…,ykm)便為MT的所有非法數(shù)字簽名對(duì)應(yīng)列的布爾和，因此結(jié)合非法數(shù)字簽名的數(shù)量上限d，可知Y中“0”的個(gè)數(shù)滿足

3) 容錯(cuò)性分析

容錯(cuò)性是指當(dāng)非法數(shù)字簽名數(shù)量估計(jì)不準(zhǔn)確時(shí)，分組檢測(cè)方案識(shí)別非法數(shù)字簽名的能力變化情況。顯然當(dāng)非法數(shù)字簽名的實(shí)際數(shù)量d′≤d時(shí)，關(guān)聯(lián)矩陣MT為d階析取矩陣的分組檢測(cè)方案識(shí)別能力沒(méi)有變化，因此重點(diǎn)討論d′＞d的情況，此時(shí)分組驗(yàn)證的結(jié)果Y=(y1,y2,…,ykm)便為所有d′列元素的布爾和。因?yàn)殛P(guān)聯(lián)矩陣MT為d階析取矩陣，所以無(wú)法通過(guò)算法1 準(zhǔn)確識(shí)別非法數(shù)字簽名，卻可以確定一個(gè)包含所有非法數(shù)字簽名的更大的可疑對(duì)象集合，此時(shí)可以采用圖1的方法對(duì)可疑對(duì)象進(jìn)行逐一驗(yàn)證，從而完成非法數(shù)字簽名的識(shí)別。具體舉例如下，參照?qǐng)D4的關(guān)聯(lián)矩陣，需要驗(yàn)證的數(shù)字簽名個(gè)數(shù)仍為25，初步估計(jì)其中非法者的個(gè)數(shù)不超過(guò)2 個(gè)，但實(shí)際第3、11、17 個(gè)數(shù)字簽名是非法的，利用上述分組檢測(cè)得到檢測(cè)結(jié)果Y=(1,0,1,1,0,1,1,1,0,0,0,0,1,0,1)T，由于15×25M是2 階析取矩陣，Y中的“0”表示本組檢測(cè)中所有數(shù)字簽名均為合法，采用排除法可以依次確定合法數(shù)字簽名x6、x7、x8、x9、x10、x21、x22、x23、x24、x25、x4、x14、x19、x5、x15、x20、x1、x18、x2、x6、x12、x16，剩下的數(shù)字簽名x3、x11、x13、x17都為可疑對(duì)象；此時(shí)剩下的數(shù)字簽名數(shù)量超過(guò)3，證明非法數(shù)字簽名數(shù)量估計(jì)偏少，2 階析取的關(guān)聯(lián)矩陣無(wú)法完成非法數(shù)字簽名的確定。如果剩余簽名數(shù)量和初始估計(jì)的簽名數(shù)量相差較大，則需要重新設(shè)計(jì)分組檢測(cè)方案；否則，便可以逐一認(rèn)證剩下的簽名，確定非法對(duì)象。因此，逐一驗(yàn)證x3、x11、x13、x17便可以完成所有數(shù)字簽名的驗(yàn)證。

4.2 仿真比較

為檢驗(yàn)本文算法的實(shí)際性能，在處理器為Intel Core i5-4200 2.5 GHz、內(nèi)存為4 GB的筆記本電腦的虛擬機(jī)VMware Workstation Pro 上安裝Linux Ubantu20 操作系統(tǒng)，在Python 3.9 編程環(huán)境下基于GMP（GNU multiple precision）和PBC（pairing-based cryptography）配置pypbc 雙線性對(duì)匹配加密庫(kù)，雜湊函數(shù)采用SHA-256，仿真環(huán)境配置如圖5 所示。

圖5 仿真環(huán)境配置

基于BGLS 聚合簽名方案進(jìn)行數(shù)字簽名的批量處理，以數(shù)字簽名的數(shù)量n及其所含非法數(shù)字簽名的上限d作為分組的依據(jù)，采用3.2 節(jié)的步驟進(jìn)行分組檢測(cè)，使用算法1 進(jìn)行非法對(duì)象的識(shí)別，部分仿真結(jié)果如表1 所示。

表1 數(shù)字簽名分組檢測(cè)部分仿真結(jié)果

分組檢測(cè)的完成時(shí)間主要與分組檢測(cè)次數(shù)相關(guān)，當(dāng)數(shù)字簽名的數(shù)量、非法數(shù)字簽名的數(shù)量增加時(shí)，分組個(gè)數(shù)必然增加，如圖6 所示。隨著分組檢測(cè)次數(shù)的增加，完成數(shù)字簽名驗(yàn)證的時(shí)間也在增加，正如表1 所示。另外，從仿真實(shí)驗(yàn)中發(fā)現(xiàn)，當(dāng)數(shù)字簽名的總數(shù)n不變，但非法數(shù)字簽名的數(shù)量增加到接近n/3 時(shí)，分組檢測(cè)的效果低于逐一驗(yàn)證的效率，與文獻(xiàn)[12]結(jié)論一致。

圖6 分組檢測(cè)次數(shù)與數(shù)字簽名的數(shù)量、非法數(shù)字簽名的數(shù)量的關(guān)系

非適應(yīng)性分組檢測(cè)方案與序貫性分組檢測(cè)方案比較，一個(gè)重要區(qū)別在于分組平行處理，本文仿真采用Thread 函數(shù)進(jìn)行平行檢測(cè)處理，如表2所示。當(dāng)數(shù)字簽名的數(shù)量和非法數(shù)字簽名的數(shù)量分別為n和d時(shí)，列出逐一驗(yàn)證、二分法驗(yàn)證和本文算法在不同處理器數(shù)量時(shí)的最大檢測(cè)數(shù)量。逐一驗(yàn)證需要對(duì)每個(gè)簽名進(jìn)行一次驗(yàn)證，驗(yàn)證次數(shù)為n，在p個(gè)處理器工作的情況下，可以將數(shù)字簽名分為p個(gè)分組，需要次檢測(cè)；二分法驗(yàn)證采用折半查找法，每次需要次檢驗(yàn)，只能檢測(cè)一個(gè)非法數(shù)字簽名，d個(gè)非法數(shù)字簽名需要次檢驗(yàn)，在p個(gè)處理器工作的情況下，可以將數(shù)字簽名分為p個(gè)分組，分別進(jìn)行折半查找，需要次檢測(cè)；本文算法通過(guò)個(gè)分組完成n個(gè)數(shù)字簽名中d個(gè)非法數(shù)字簽名識(shí)別，在p個(gè)處理器工作的情況下，可以將數(shù)字簽名分為個(gè)分組同時(shí)進(jìn)行，需要次驗(yàn)證。

本文算法采用并行處理的設(shè)計(jì)思想，為便于驗(yàn)證的同時(shí)進(jìn)行處理，設(shè)計(jì)了個(gè)獨(dú)立并行的分組進(jìn)行驗(yàn)證數(shù)字簽名。從表2 可以看出，單個(gè)處理器時(shí)二分法驗(yàn)證效率最高，達(dá)到O(logn)，而本文算法的僅比逐一驗(yàn)證的O(n)較好一些。當(dāng)多個(gè)處理器同時(shí)處理時(shí)，所有算法都可以并行處理，不管是逐一驗(yàn)證、二分法驗(yàn)證還是本文算法的檢驗(yàn)效率都有所提高，本文算法的效率提升明顯，提高到單個(gè)處理器時(shí)的p倍，而二分法驗(yàn)證提高了logn p倍，顯然（通常n＞p）。

表2 數(shù)字簽名分組檢測(cè)比較

如圖7 所示，將本文算法與逐一驗(yàn)證和二分法驗(yàn)證進(jìn)行比較發(fā)現(xiàn)，當(dāng)單個(gè)處理器串行驗(yàn)證時(shí)，二分法驗(yàn)證有相對(duì)較好的表現(xiàn)，同等數(shù)量的數(shù)字簽名需要的驗(yàn)證次數(shù)最少；當(dāng)多個(gè)處理器并行驗(yàn)證時(shí)，在非法數(shù)字簽名數(shù)量d=8、處理器個(gè)數(shù)p=100的情況下，雖然逐一驗(yàn)證和二分法驗(yàn)證可以用多個(gè)處理器同時(shí)進(jìn)行驗(yàn)證，效率有所提升，但是隨著數(shù)字簽名的數(shù)量增多，本文算法表現(xiàn)出較強(qiáng)的效率優(yōu)勢(shì)。當(dāng)數(shù)字簽名的總數(shù)大于3 000 時(shí)，本文算法與逐一驗(yàn)證相比才體現(xiàn)出優(yōu)勢(shì)，在多處理器保障的條件下，本文算法分組檢測(cè)的次數(shù)隨著數(shù)字簽名總數(shù)的變化不大，基本上保持在8 附近，與二分法驗(yàn)證、逐一驗(yàn)證相比，具有最少的驗(yàn)證次數(shù)，效率最高。隨著數(shù)字簽名的數(shù)量不斷增大，尤其是的增大，當(dāng)多處理器并行驗(yàn)證時(shí)本文算法會(huì)表現(xiàn)出更多優(yōu)勢(shì)。

圖7 分組檢測(cè)次數(shù)與數(shù)字簽名的數(shù)量的關(guān)系

5 結(jié)束語(yǔ)

數(shù)字簽名的非適應(yīng)性分組驗(yàn)證是為提高網(wǎng)絡(luò)中心節(jié)點(diǎn)數(shù)字簽名的驗(yàn)證效率，將組合設(shè)計(jì)理論與聚合簽名理論相結(jié)合，以橫截設(shè)計(jì)理論為基礎(chǔ)設(shè)計(jì)數(shù)字簽名分組方案，以聚合簽名理論為方法完成數(shù)字簽名的批量分組驗(yàn)證，實(shí)現(xiàn)數(shù)字簽名的并行快速驗(yàn)證。它通常應(yīng)用于傳感器網(wǎng)、交通網(wǎng)、物聯(lián)網(wǎng)等具有海量節(jié)點(diǎn)信息需要安全驗(yàn)證，且消息時(shí)敏性強(qiáng)的無(wú)線網(wǎng)絡(luò)環(huán)境。本文基于組合數(shù)學(xué)的拉丁方理論設(shè)計(jì)了數(shù)字簽名分組方案，并以經(jīng)典的BGLS 聚合簽名理論進(jìn)行數(shù)字簽名的批量驗(yàn)證，構(gòu)建了一個(gè)以次數(shù)完成n個(gè)數(shù)字簽名驗(yàn)證的非適應(yīng)性數(shù)字簽名分組驗(yàn)證方案。該方案與逐一認(rèn)證相比具有較高驗(yàn)證效率；在多處理器保障的條件下，與序貫類分組方案相比具有驗(yàn)證次數(shù)少、效率高的優(yōu)勢(shì)。但本文研究未考慮數(shù)字簽名在信道中的傳輸錯(cuò)誤問(wèn)題，需要進(jìn)一步研究加入檢錯(cuò)糾錯(cuò)機(jī)制，增強(qiáng)分組檢測(cè)的容錯(cuò)性能。