王秀麗，曹 苗，王利娜

1.中國民航大學(xué)理學(xué)院，天津300300

2.北京師范大學(xué)靜海附屬學(xué)校中學(xué)部, 天津301600

隨著信息技術(shù)的快速發(fā)展，信息安全問題在人們的生活中變得越來越重要.信息安全的兩個(gè)主要研究內(nèi)容是信息的保密和認(rèn)證.信息保密是通過對所需傳送的信息進(jìn)行加密來保護(hù)信息，防止信息被他人竊取.信息認(rèn)證的目的在于防止非法用戶進(jìn)入認(rèn)證系統(tǒng)，防止接收不明身份的信息，使接收方在收到信息后能夠確認(rèn)信息的來源是正確的.此后，對兩個(gè)方面進(jìn)行認(rèn)證：對信息的發(fā)送者和接收者的身份進(jìn)行驗(yàn)證；對信息的完整性進(jìn)行驗(yàn)證，驗(yàn)證信息在信道傳輸過程中，是否有被篡改或延遲的情況發(fā)生.

在研究保密問題中，Shannon[1]于20世紀(jì)40年代首次利用信息論的方法并提出了完善保密系統(tǒng)的概念.Simmons[2]在研究信息的認(rèn)證問題時(shí)也應(yīng)用了信息論的方法.這些工作為信息認(rèn)證奠定了理論基礎(chǔ).1985年，Simmons[2]首次提出了認(rèn)證碼的概念，現(xiàn)在認(rèn)證碼已成為研究認(rèn)證理論的重要問題之一.1974年，Gilbert 等[3]第一次進(jìn)行認(rèn)證碼的構(gòu)造.

有限幾何是研究認(rèn)證碼的有力工具.2014年，邱雙月[4]利用有限域上參數(shù)δ=0 的奇異酉空間構(gòu)造了Cartesian 認(rèn)證碼，但這種方法對于參數(shù)δ=1 的奇異酉空間計(jì)算較為復(fù)雜.2015年，邱雙月等[5]對此進(jìn)行了改進(jìn)，在參數(shù)δ=1 的奇異酉空間中構(gòu)造了Cartesian 認(rèn)證碼.此外，陳尚弟等[6]利用有限域上的酉幾何構(gòu)造了具有可信仲裁的認(rèn)證碼.代數(shù)組合方法是研究認(rèn)證碼的重要方法.2010年，李殿龍[7]利用代數(shù)學(xué)中的立方冪零矩陣的若爾當(dāng)標(biāo)準(zhǔn)型構(gòu)造了Cartesian 認(rèn)證碼，該方法在同等條件下能夠認(rèn)證更多的信源，從而節(jié)省了通信成本，并且認(rèn)證碼的安全性得到進(jìn)一步提升.2009年，裴定一[8-9]在消息認(rèn)證碼中詳細(xì)介紹了完善認(rèn)證系統(tǒng)和組合設(shè)計(jì)之間的關(guān)系，并給出了最優(yōu)認(rèn)證碼、完善認(rèn)證碼的定義及實(shí)例.2015年，Safavi-Naini 等在文獻(xiàn)[10]中討論了敵方對接收方進(jìn)行攻擊的最優(yōu)策略，給出了認(rèn)證碼欺騙成功概率的下界，得到了最優(yōu)認(rèn)證碼的組合特征.

在傳統(tǒng)的認(rèn)證碼中，主要考慮模仿攻擊和替換攻擊成功的概率，但是在實(shí)際通信中，收發(fā)雙方一般是彼此不信任的[11]，Simmons[12]提出了認(rèn)證碼的擴(kuò)展-帶仲裁的認(rèn)證碼，而分裂認(rèn)證碼是研究帶仲裁的認(rèn)證碼的一種重要手段.Simmons[12]首次提出分裂認(rèn)證碼的定義，后來眾多學(xué)者嘗試?yán)酶鞣N方法構(gòu)造性能優(yōu)良的分裂認(rèn)證碼.Kurosawa 和王永傳等[13-14]給出了分裂認(rèn)證碼和帶仲裁認(rèn)證碼之間的對應(yīng)關(guān)系.

組合設(shè)計(jì)作為一種重要的組合結(jié)構(gòu)，在構(gòu)造認(rèn)證碼和分裂認(rèn)證碼[15-16]中也被廣泛采用.其中用帶約束的部分平衡t-設(shè)計(jì)（restricted strongly partially balanced design, RSPBD）構(gòu)造帶仲裁的認(rèn)證碼，是由裴定一等[17]首次提出和運(yùn)用的，而在利用分裂不平衡區(qū)組設(shè)計(jì)（splitting balanced incomplete block design,SBIBD）構(gòu)造分裂認(rèn)證碼方面，Huder 和Ogata等[15,18]都進(jìn)行了開創(chuàng)性的研究并得到了重要的成果.2012年，Liang 等[19]利用可裂設(shè)計(jì)研究了三重完善分裂認(rèn)證碼.近年來，關(guān)于分裂認(rèn)證碼的新成果也很豐碩：2015年，Chen[20]利用射影空間中的特殊子空間及線和面的關(guān)聯(lián)關(guān)系，構(gòu)造了分裂認(rèn)證碼；Matsubara 等在文獻(xiàn)[21]中主要研究了可裂平衡區(qū)組設(shè)計(jì)（splitting block design, SBD）的可分解性，提供了具有可分辨性的SBD與其他組合設(shè)計(jì)的一些等價(jià)性，還提供了可解的SBD與其他組合設(shè)計(jì)的一些等價(jià)性.2017–2018年，Liang[22]、Li[23]和王利娜[24]繼續(xù)利用特殊的組合設(shè)計(jì)分別構(gòu)造了幾類新的最優(yōu)分裂認(rèn)證碼，但所用到的理論稍顯復(fù)雜，組合技巧不易掌握.

本文所構(gòu)造的認(rèn)證碼創(chuàng)新性主要體現(xiàn)在：基于有限域Fq上的二維向量空間，巧妙地借助線性方程組的理論，構(gòu)造了帶約束的強(qiáng)部分平衡設(shè)計(jì)；相對于文獻(xiàn)[22-23]，本文所用理論簡單易懂，模擬仿真易于實(shí)現(xiàn)；本文是文獻(xiàn)[24]研究方法的繼續(xù)，研究結(jié)果同時(shí)也將文獻(xiàn)[8]中關(guān)于完善認(rèn)證碼的構(gòu)造推廣至完善c-分裂認(rèn)證碼；通過舉例與文獻(xiàn)[15]的相關(guān)結(jié)果對比發(fā)現(xiàn)，在編碼規(guī)則數(shù)目相同的前提下，本文的信源數(shù)目大于文獻(xiàn)[15]的信源數(shù)目；本文所構(gòu)造的認(rèn)證碼的各階攻擊成功概率都達(dá)到了最小.

1 預(yù)備知識

本節(jié)給出認(rèn)證碼的相關(guān)概念，組合設(shè)計(jì)和分裂認(rèn)證碼的相關(guān)定義，兩者的關(guān)系以及所需結(jié)論.

1.1 分裂認(rèn)證碼及Cartesian 認(rèn)證碼的定義

定義1[11]對于一個(gè)認(rèn)證碼(S,E,M,f)，若編碼規(guī)則e將信源s編碼成多個(gè)消息m，則稱之為分裂認(rèn)證碼.

此時(shí)，對任意消息m ∈M，有m=e(s,r)，其中r ∈R，R是特殊的有限集合.對于?s ∈S,?e ∈E，定義

分裂是指對于某些信源s ∈S和編碼規(guī)則e ∈E，有|e(s)| >1.為了能夠順利譯碼，規(guī)定若則有

定義2[11]對于每一個(gè)信源s ∈S和每一個(gè)編碼規(guī)則e ∈E，如果|e(s)|=c，那么這個(gè)分裂認(rèn)證碼就稱為c-分裂認(rèn)證碼.

定義3[8]對于任意信源s ∈S，令M(s)={m ∈M|?e ∈E,e(s)=m}，M(s)是能代表s的所有報(bào)文的集合.如果對于任意兩個(gè)不同的信源s1和s2，M(s1)與M(s2)沒有公共元，那么這時(shí)認(rèn)證碼(S,M,E)就稱為Cartesian 認(rèn)證碼.

1.2 帶約束的部分平衡t-設(shè)計(jì)

定義4[20]設(shè)v,b,k,c,λ,t為正整數(shù)，tk.一個(gè)帶約束的部分平衡t-設(shè)計(jì)RPBDt ?(v,b,k×c;λ,0)是一個(gè)二元組(X,B), 其中X具有v個(gè)元素，B是區(qū)組集且滿足以下條件，

1）每個(gè)區(qū)組Bi ∈B(1i|B|=b)，都可以表示成長度為c的k個(gè)互不相交的子區(qū)組的并，即Bi=Bi,1∪Bi,2∪···∪Bi,k,其中|Bi,1|=|Bi,2|=···=|Bi,k|=c；

2）X中任意t子集{x1,x2,···,xt}，或在λ個(gè)區(qū)組Bi=Bi,1∪Bi,2∪···∪Bi,k中同時(shí)出現(xiàn)，且xm ∈Bi,jm(jm=1,2,···,k)，其中j1,j2,j3,···,jt互不相同，或它們不在任一區(qū)組中出現(xiàn).

定義5[20]一個(gè)帶約束的部分平衡t?(v,b,k×c;λ,0)設(shè)計(jì)，如果同時(shí)也是帶約束的部分平衡r ?(v,b,k×c;λr,0)設(shè)計(jì)，1rt ?1，則稱(X,B)為帶約束的強(qiáng)部分平衡t-設(shè)計(jì)（RSPBD），記為t ?(v,b,k×c;λ1,λ2,···,λt,0).

定理1[20]假設(shè)存在一個(gè)RSPBDt ?(v,b,k×c;λ1,λ2,···,λt?1,1,0)設(shè)計(jì)，其中t2，則對于k個(gè)等可能出現(xiàn)的信源，存在一個(gè)t-階完善c-分裂認(rèn)證碼，具有v個(gè)信息和b個(gè)編碼規(guī)則的.相反，如果有一個(gè)具有k個(gè)信源，v個(gè)信息和b個(gè)編碼規(guī)則的t-階完善c-分裂認(rèn)證碼，那么也就存在一個(gè)RSPBDt ?(v,b,k×c;λ1,λ2,···,λt?1,1,0)，其中λr=(PrPr+1···Pt?1)?1，1rt ?1.

Pr為r-階最佳欺騙攻擊成功的概率，r-欺騙攻擊是指敵方在觀察方使用相同的編碼規(guī)則，取M為認(rèn)證碼的信息的集合，也是區(qū)組設(shè)計(jì)中樣本的集合.取信源S=Fq，在觀察到發(fā)方發(fā)送r(r0)個(gè)消息后，敵方在信道中放入不同于發(fā)方發(fā)送的r個(gè)虛假消息，試圖使收方接收，并認(rèn)為它們是真實(shí)可靠的.

定義6[8]設(shè)Mi1,···,it={mt=(m1,m2,···,mt)|mr ∈M(sir),1rt}，在一個(gè)t-階完善Cartesian 碼中，假設(shè)存在信源集S的一個(gè)固定子集si1,···,sit，使任一mt ∈Mi1,···,it，其中Mi1,···,it={mt=(m1,m2,···,mt)|mr ∈M(sir),1rt}，都有|E(mt)|=1，那么稱這個(gè)認(rèn)證碼是I 型完善認(rèn)證碼，否則為II 型完善認(rèn)證碼.

定義7[8]設(shè)t為正整數(shù)，當(dāng)編碼規(guī)則的數(shù)目|E|達(dá)到下界(P0P1···Pt?1)?1，即|E|=(P0P1···Pt?1)?1，這個(gè)認(rèn)證系統(tǒng)稱為t-階完善認(rèn)證系統(tǒng).

對于認(rèn)證碼的構(gòu)造，主要考慮下述問題：1）Pr盡可能小，保證安全性；2）編碼規(guī)則盡可能少，減少傳輸過程中的存儲量；3）信源數(shù)目盡可能多，增大傳輸?shù)男畔⒘浚?）與普通認(rèn)證碼相比，可裂認(rèn)證碼需增加一定的變量，對消息進(jìn)行合理的劃分，這樣有利于實(shí)現(xiàn)對高階攻擊的保護(hù).而利用帶約束的強(qiáng)部分平衡t-設(shè)計(jì)構(gòu)造分裂認(rèn)證碼的關(guān)鍵問題是：樣本中任意t個(gè)元素恰好出現(xiàn)在所構(gòu)造出來的區(qū)組中的λ個(gè)中，且這t個(gè)元素中的每一個(gè)又恰好分別出現(xiàn)在這λ個(gè)區(qū)組劃分出來的不同的t個(gè)子區(qū)組中.

2 在有限域Fq 上的二維向量空間中構(gòu)造分裂認(rèn)證碼

本節(jié)研究分裂認(rèn)證碼的構(gòu)造.根據(jù)1.2 節(jié)所述，一個(gè)完善認(rèn)證系統(tǒng)與一個(gè)帶約束的強(qiáng)部分平衡t-設(shè)計(jì)有一一對應(yīng)關(guān)系，也就是構(gòu)造完善分裂認(rèn)證碼等價(jià)于構(gòu)造一個(gè)帶約束的強(qiáng)部分平衡t-設(shè)計(jì).本文就是在有限域Fq上的二維向量空間中構(gòu)造一個(gè)帶約束的強(qiáng)部分平衡t-設(shè)計(jì)，從而由這種設(shè)計(jì)構(gòu)造兩個(gè)完善分裂認(rèn)證碼.下面給出分裂認(rèn)證碼的具體構(gòu)造.

2.1 分裂認(rèn)證碼的構(gòu)造I

在Fq上的二維向量空間中，利用線性方程組的知識，將

作為編碼函數(shù)，常數(shù)變量λj用來實(shí)現(xiàn)可裂.

2.1.1 一種帶約束的強(qiáng)部分平衡t-設(shè)計(jì)的構(gòu)造

設(shè)Fq為含有q個(gè)元素的有限域，t為正整數(shù)且t < q，取樣本集X為{(x,y)|x,y ∈Fq}.對Fq上的任意t元組(at?1,at?2,···,a0)，取定任一λj ∈ Fq，定義區(qū)組為其中u=1,2,···,q;j=1,2,···,c，且滿足c

記B為Fq上的任意t元組(at?1,at?2,···,a0)的集合，即為區(qū)組的集合，這樣的t元數(shù)組數(shù)目為qt，即|B|=qt.

每一個(gè)區(qū)組Bi可以表示為互不相同的長度為c的q個(gè)子區(qū)組的并Bi=Bi1∪Bi2∪···∪Biq，其中

對于每一個(gè)區(qū)組B(at?1,at?2,···,a0)，取Fq中t個(gè)互不相同的元素x1,x2,···,xt，對于M中任意t個(gè)點(diǎn)

它們滿足

方程組(5)看作以at?1,at?2,···,a0為未知數(shù)的線性方程組，其系數(shù)矩陣為

顯然，式(6)的行列式不為0.因此秩為t，故線性方程組(5)有唯一解，那么這t個(gè)點(diǎn)就被包含在由at?1,at?2,···,a0所定義的唯一區(qū)組里.根據(jù)Bi=Bi1∪Bi2∪···∪Biq的定義可知：(xu,yuj)恰好出現(xiàn)在Bi=Bi1∪Bi2∪···∪Biq的某個(gè)子區(qū)組Biu(=1,2,···,q)中.因此二元組(M,B)是一個(gè)RPBDt ?(q2,qt,q×c;1,0).

對于M中的任意s(1st ?1)個(gè)點(diǎn)，

如果它們在一個(gè)區(qū)組B(at?1,at?2,···,a0)中，則有以at?1,at?2,···,a0為變量的方程組

由于方程組(8)的系數(shù)矩陣中存在s階范德蒙德矩陣，所以秩是s，從而該方程組剛好有qt?s個(gè)解，這就意味著|λs|=qt?s.

因此二元組(M,B)是一個(gè)RSPBDt ?(q2,qt,q×c;λ1,λ2,···λt?1,1,0)，其中λs=qt?s(1st ?1).

2.1.2 分裂認(rèn)證碼的構(gòu)造

本節(jié)研究目標(biāo)是利用2.1.1 節(jié)中所構(gòu)造的帶約束的強(qiáng)部分平衡t-設(shè)計(jì)構(gòu)造分裂認(rèn)證碼.設(shè)認(rèn)證碼的信源集合為S=Fq，消息集合M，編碼規(guī)則的集合E分別為上述設(shè)計(jì)中樣本的集合X和區(qū)組的集合B.對于每一個(gè)區(qū)組B(at?1,at?2,···,a0)和Fq中給定的λj ∈Fq ,可定義一個(gè)編碼規(guī)則e ∈E，使得

因此，編碼規(guī)則e的數(shù)目|E|取決于t元數(shù)組(a0,a1,···,at?1)的數(shù)目.這樣的t元組數(shù)目為qt，即|E|=qt.由2.1.1 節(jié)可知：對任意s個(gè)消息有效的密鑰數(shù)為|E(ms)|=λs=qt?s.

根據(jù)定理1，由2.1.1 節(jié)中所構(gòu)造的

可以得到一類t-階完善c-分裂認(rèn)證碼，其中信源數(shù)|S|=q，消息數(shù)|M|=q2，編碼規(guī)則數(shù)|E|=qt.假設(shè)編碼規(guī)則E和信源S具有一致分布，則有

通過消息(xu,yuj)就可以知道對應(yīng)的信源xu，所以這個(gè)碼是一個(gè)Cartesian 認(rèn)證碼.因此這個(gè)Cartesian 認(rèn)證碼是t-階完善c-分裂認(rèn)證碼.

如果s=t，那么方程組(8)存在唯一的解，由定義6 可得，該碼是I 型的完善認(rèn)證碼.

2.2 分裂認(rèn)證碼構(gòu)造II

式中，u=1,2,···,q, j=1,2,···,c，滿足c

對于每一個(gè)區(qū)組(at?1,at?2,···,a0)，定義一個(gè)編碼規(guī)則，使得

即一個(gè)信源xu被加密成消息(xu,yuj)，j=1,2,···,c，編碼規(guī)則的數(shù)目即為Fq中t元組(at?1,at?2,···,a0), at?10的數(shù)目.這樣的t元組的數(shù)目為(q ?1)qt?1，所以編碼規(guī)則數(shù)目=(q ?1)qt?1.

對于區(qū)組(at?1,at?2,···,a0), at?10,在Fq中取t個(gè)互不相同的元素x1,x2,···,xt，對于M中任意t個(gè)點(diǎn)

適合下列方程組

在方程組(16)中，未知量為at?1,at?2,···,a0.設(shè)

有|E(ms)|=qt?1?s(q ?1).

故(M,B)是一個(gè)RSPBDt?(q2,(q ?1)qt?1,q×c;λ1,λ2,···,λt?1,1,0)，根據(jù)定理1，一

個(gè)新的t-階完善c-分裂Cartesian 認(rèn)證碼可以被得到.

假定編碼規(guī)則E和信源Sr滿足等概率分布，可以得到

與構(gòu)造I 類似，該碼也是一個(gè)t-階完善c-分裂Cartesian 認(rèn)證碼.根據(jù)定義6，該認(rèn)證碼是II 型的完善認(rèn)證碼.

2.3 實(shí)例驗(yàn)證和性能分析

在構(gòu)造I 中，令q=3, c=2, t=2.由構(gòu)造可知其中x ∈F3.λj分別取1 和2，信源S={s1,s2,s3}=F3.對應(yīng)的設(shè)計(jì)為RSPBD 2-(9,9,3×2;3,3,10)，所構(gòu)造的分裂認(rèn)證碼的編碼矩陣如表1所示.

表1 分裂認(rèn)證碼構(gòu)造I 的編碼矩陣Table 1 Coding matrix of splitting authentication code I

值得說明的是，當(dāng)λj分別取0,1 和0,2 時(shí)，又會得到其他兩種編碼矩陣.根據(jù)構(gòu)造，對于固定的λj，由編碼矩陣也可看出，兩種攻擊成功概率都是.取λj=1，對編碼矩陣進(jìn)行數(shù)值仿真，結(jié)果如圖1所示.

圖1 編碼矩陣仿真Figure 1 Coding matrix simulation

仿真分析：圖1以信源S作為橫坐標(biāo)，編碼函數(shù)e(s)為縱坐標(biāo).任意選取消息（0,2），通過圖像可知，有三條線通過該點(diǎn)，即對消息（0,2）有效的編碼規(guī)則數(shù)目為3，總的線數(shù)即為編碼規(guī)則數(shù)目為9，從而模仿攻擊成功的概率為；任意選取兩個(gè)消息（0,2），（1,2），通過圖像可知，只有一條線通過這兩點(diǎn)，即對消息（0,2），（1,2）都有效的編碼規(guī)則數(shù)目為1，從而替換攻擊成功的概率為.通過仿真圖像所得的結(jié)論與構(gòu)造方案結(jié)果一致，故本文的構(gòu)造合理可行.

在構(gòu)造I 的基礎(chǔ)上，要求a10可得到構(gòu)造II，因此上例對應(yīng)的構(gòu)造II 的編碼矩陣如表2所示.

值得說明的是，當(dāng)λj分別取0,1 和0,2 時(shí)，又會得到其他兩種編碼矩陣.根據(jù)構(gòu)造，對于固定的λj，由編碼矩陣也可看出，兩種攻擊成功概率都是.取λj=1，對編碼矩陣進(jìn)行數(shù)值仿真，結(jié)果如圖2所示.

表2 分裂認(rèn)證碼構(gòu)造II的編碼矩陣Table 2 Coding matrix of splitting authentication code II

圖2 編碼矩陣仿真Figure 2 Coding matrix simulation

仿真分析：圖2以信源S作為橫坐標(biāo)，編碼函數(shù)e(s)為縱坐標(biāo)，任意選取消息（0,2），通過圖像可知，有兩條線通過該點(diǎn)，即對消息（0,2）有效的編碼規(guī)則個(gè)數(shù)為2，此時(shí)編碼規(guī)則個(gè)數(shù)為6，從而模仿攻擊成功的概率為.任意選取兩個(gè)消息，通過圖像可知，只有一條直線通過這兩點(diǎn)，即對消息（0,2），（1,2）都有效的編碼規(guī)則個(gè)數(shù)為1，從而替換攻擊成功的概率為.通過仿真圖像所得的結(jié)論與構(gòu)造方案結(jié)果一致，故本文的構(gòu)造合理可行.

性能分析：

1）在上例中，將所構(gòu)造的分裂認(rèn)證碼的相關(guān)參數(shù)與文獻(xiàn)[15]中利用可裂設(shè)計(jì)構(gòu)造的分裂認(rèn)證碼進(jìn)行比較可知，在編碼規(guī)則數(shù)目|E|=9 相同的前提下，本文的信源數(shù)目為3，大于文獻(xiàn)[15]的信源數(shù)目2.

2）本文以線性方程組的理論為基礎(chǔ)，構(gòu)造了帶約束的強(qiáng)部分平衡設(shè)計(jì)，與文獻(xiàn)[15，21-23]相比，構(gòu)造方法相對簡單易懂，編碼復(fù)雜度較低.

4）本文將文獻(xiàn)[8]中關(guān)于完善認(rèn)證碼的構(gòu)造推廣至完善c-分裂認(rèn)證碼，即本文所構(gòu)造的分裂認(rèn)證碼滿足|E|=(P0P1···Pt?1)?1，達(dá)到了組合論中完善的界.

3 結(jié) 論

本文主要利用有限域上二維向量空間，借助線性方程組的理論，構(gòu)造了帶約束的強(qiáng)部分平衡設(shè)計(jì)，在強(qiáng)部分平衡設(shè)計(jì)的基礎(chǔ)上構(gòu)造了兩類t-階完善c-分裂認(rèn)證碼.

優(yōu)點(diǎn)主要體現(xiàn)在三方面：1）用線性方程組求解等簡單的理論知識使編碼算法相對簡單，復(fù)雜度較小；2）在編碼規(guī)則數(shù)目相同的前提下，本文的信源數(shù)目大于文獻(xiàn)[5]的信源數(shù)目，有利于提高信息傳輸?shù)男剩?）認(rèn)證碼的各階攻擊成功概率均達(dá)到了最小，且滿足完善性的條件，從信息安全性的角度來看，也是較好的.

不足主要體現(xiàn)在兩方面：1）在構(gòu)造組合設(shè)計(jì)時(shí)樣本選擇的條件可以更嚴(yán)謹(jǐn)一些，在后續(xù)的研究中將繼續(xù)進(jìn)行改進(jìn)；2）Cartesian 認(rèn)證碼對信源不具有保密性，用類似方法構(gòu)造對信源具有保密功能的非Cartesian 認(rèn)證碼，在后續(xù)的研究中將繼續(xù)進(jìn)行探索.