基于有限域上的射影空間構(gòu)造完善的A3碼

陳尚弟，梁俊英

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

1 認證碼及其研究狀況

保密和認證是保障信息安全的兩個重要手段。保密的目的是阻止秘密信息被敵手解密，該問題可通過密碼技術(shù)來解決；認證的目的是保障信源的真實性和信息的完整性，數(shù)字簽名和認證碼是解決這一問題的有效方法。事實上，數(shù)字簽名是計算安全的，而認證碼是無條件安全的。因此，認證碼在各種開放的通信系統(tǒng)中起著重要的作用。1974年，Gilbert等[1]首次提出認證碼的概念，并基于射影幾何構(gòu)造了第一個認證碼，這是認證碼發(fā)展的一個里程碑。同時，Simmons[2]拓展了認證系統(tǒng)的信息論，引入了認證信道的概念。Simmons的認證模型（簡稱A碼）包括信息的發(fā)送方和接收方，其被認為是相互可信、共享一個相同的秘密密鑰。通過認證碼的使用，能夠保證所傳送的信息免遭敵人的欺騙攻擊。欺騙攻擊的一種方式是敵方模仿發(fā)送方在通信信道中插入一個信息讓收方接收，這種欺騙攻擊稱為敵方的模仿攻擊；另一種方式是敵方截獲發(fā)送方發(fā)送的一個消息后，將這個消息用另一個不同的消息替代，然后將替代后的消息插入信道讓收方接收，這種攻擊稱為敵方的替代攻擊。在這個模型中，由于發(fā)方和收方共享一個密鑰，這就要求發(fā)方和收方必須是彼此絕對可信的。顯然，這是一個不完全符合現(xiàn)實環(huán)境的模型。實際上，發(fā)送者完全有可能發(fā)送一個消息后，事后又否認發(fā)送過那個消息；同樣，收方在接收到發(fā)方的消息后，也可能否認接收過這個消息。為解決由于收方和發(fā)方不信任而產(chǎn)生的爭執(zhí)，Simmons擴展了此模型，引入帶仲裁的認證碼的模型（簡稱A2碼）。在這個模型中，除了發(fā)方和收方外，增加了一個第三方稱為仲裁，并被認為是可信的，其知道收發(fā)雙方的密鑰信息，但其不參與整個通信過程，其任務(wù)是解決發(fā)方和收方之間的爭執(zhí)，阻止發(fā)方和收方之間的欺騙攻擊。

下面給出A2碼的精確定義：

定義 1令 S、ET、ER、M 是 4 個非空有限集，f：S ×ET→M，g：M × ER→S∪{拒絕}，稱六元組（S，ET，ER，M；f，g）為一個A2碼，需滿足下列3個條件：

1）映射 f、g是滿射；

2）對任意的 m∈M，et∈ET，如果存在 s∈S 使得f（s，et）=m，則s被m和et唯一決定；

3）當p（et，er）≠0，且f（s，et）=m時，必有g(shù)（m，er）=s；否則，g（m，er）∈{拒絕}。

其中，p（et，er）≠0指任何被et加密的信息s都能通過er的認證。

S、ET、ER和M分別稱為源狀態(tài)集、發(fā)送者的加密規(guī)則集、接收者的解密規(guī)則集和信息集；f和g分別稱為加密函數(shù)和解密函數(shù)，而稱為碼的參數(shù)。

擁有仲裁的認證碼可有效地抵抗來自外部敵人（不掌握系統(tǒng)的密鑰信息）和內(nèi)部人士（發(fā)送者和接收者，其掌握系統(tǒng)的部分密鑰信息）的欺騙攻擊。對于帶有仲裁的認證碼已有深入的研究和廣泛的應(yīng)用[2-12]。

擁有仲裁的認證碼可分為兩類：仲裁絕對可信的認證碼的A2碼和仲裁不可信的認證碼的A3碼。Johansson[13]定義的A3碼就是能抵抗仲裁欺騙攻擊的A2碼。也就是說，在一個A3碼中，發(fā)方、收方和仲裁方?jīng)]有一方是可信的。

基于有限域上的射影空間，很多完善的A2認證碼已經(jīng)被構(gòu)造，但是，還未發(fā)現(xiàn)完善的A3碼構(gòu)造。Desmedt等[14]通過增加一些額外的比特讓參加方分享（如讓發(fā)方和收方分享而不讓仲裁分享）的方法來解決仲裁不可信的問題。Johansson[13]給出了帶仲裁認證碼受到各種攻擊成功的概率的界，并基于有限域構(gòu)造了一個完善的A3碼。

2 A3碼的模型

在一個A3碼中，有3個參與方：一個發(fā)方T、一個收方R和一個仲裁A。他們中沒有一個被認為可信，但都有其秘密密鑰信息用于抵抗來自于系統(tǒng)的各種欺騙攻擊。盡管仲裁可能干擾通信，但在仲裁階段仍認為仲裁是可信的。另外，還有一個外部的攻擊者O，其不掌握系統(tǒng)的任何密鑰信息。

令S、ET、ER、EA和M分別表示源狀態(tài)集、發(fā)送者的加密規(guī)則集、收方的解密規(guī)則集、仲裁的密鑰集和信息集。類似于A2碼，發(fā)送者的密鑰et∈ET確定了加密函數(shù)，即

接收者的密鑰er∈ER確定了解密函數(shù)，即

仲裁的密鑰ea∈EA確定了一個子集，即

如果m∈M（ea），則仲裁斷定m是發(fā)方發(fā)送的有效信息，這里M（ea）表示所有對于密鑰ea有效的信息集合。

發(fā)送者T用其密鑰信息et∈ET加密一個源狀態(tài)s∈S成一個信息m，即m=f（s，et），并通過一個公開渠道將m發(fā)送給接收者R，而R用其密鑰er驗證信息m的真實性。當發(fā)送者T和接收者R發(fā)生爭執(zhí)時，仲裁A用其密鑰信息ea解決T和R之間的糾紛。

對于任意m∈M，假定至少存在一個er∈ER和一個ea∈EA，使得m∈M（er）∩M（ea）；否則，這個信息m可從M中刪去。給定接收者一個密鑰er，仲裁一個密鑰ea，對于任何信息m∈M（er）∩M（ea）（如果假定至少存在發(fā)方的一個密鑰et∈ET（er）∩ET（ea），使得m∈M（et）；否則，這個信息可以從M（er）∩M（ea）中刪去。

接收者和仲裁必須承認所有來自于發(fā)送者的合法信息，各參與方的密鑰必須進行合適的選擇。假設(shè)對于一個可能的密鑰對（et，er），對任何一個s∈S被et加密后都能通過er的認證，也假定對一個可能的密鑰對（et，ea），發(fā)送者根據(jù) et生成信息 m，仲裁總能根據(jù)密鑰ea確定m來自于發(fā)方。

A3碼的運行分3個階段：

1）密鑰生成和密鑰分配

這一階段可通過一個誠實可信的權(quán)威機構(gòu)（密鑰分配中心KDC）來執(zhí)行。權(quán)威機構(gòu)選取一個有效的三元組（et，er，ea），并秘密地將 et、er和 ea分別發(fā)送給發(fā)方T、收方R和仲裁A。一個有效的三元組具有以下性質(zhì)：如果f（s，et）=m，則g（m，er）=s，且m∈M（er）∩M（ea）。

2）廣播

為了認證一個信源s∈S，發(fā)方T用所持有的密鑰et將s加密成一個信息m=f（s，et），然后通過一個公開的信道將m發(fā)給收方R。

3）驗證

收方R用持有的密鑰er驗證收到的信息m的真實性。如果g（m，er）∈S，則接受m為發(fā)方發(fā)送的真實信息，否則拒絕m。

4）仲裁

發(fā)方和收方之間可能發(fā)生爭執(zhí)。如果發(fā)方和收方發(fā)生爭執(zhí)，仲裁能夠用他所持有的密鑰ea判斷m是否由發(fā)方生成。如果m∈M（ea），則仲裁判定m由發(fā)方生成；如果m?M（ea），則仲裁判定m不是由發(fā)方生成。

由于在A3碼中，仲裁也可能參與對系統(tǒng)的欺騙攻擊，故此系統(tǒng)存在7種類型的攻擊：

1）敵方的模仿攻擊I

敵方在通信信道中插入一個消息m發(fā)給收方。如果m被收方接受，則敵方模仿攻擊成功。

2）敵方的替換攻擊S

敵方在截獲到一個合法消息m后，用一個不同于m的消息m′替換m，并將m′發(fā)給收方。如果m′被收方接受，則敵方替換攻擊成功。

3）發(fā)方的模仿攻擊T

發(fā)方向收方發(fā)送一個假的消息m，這個消息不能由發(fā)方的加密密鑰et生成。如果m被收方接受，則發(fā)方模仿攻擊成功。

4）收方的模仿攻擊R0

收方聲稱收到一個消息m。如果m對發(fā)方的密鑰et有效，則收方模仿攻擊成功。

5）收方的替換攻擊R1

發(fā)方發(fā)送一個合法的消息m給收方，而收方卻聲稱用其密鑰er收到消息m′（m′≠m）。如果m′對發(fā)方的密鑰et有效，則收方的替換攻擊成功。

6）仲裁的模仿攻擊A0

仲裁用其密鑰ea將一個消息m插入通信信道發(fā)給收方。如果m被收方作為一個真實的消息接受，則仲裁的模仿攻擊成功。

7）仲裁的替換攻擊A1

仲裁觀察到發(fā)方發(fā)送的一個消息m，用另一個不同于m的消息m′替換m并將其發(fā)送給收方。如果m′被收方作為一個真實的消息接受，則仲裁的替換攻擊成功。

對于以上各種類型的攻擊，用 PI、PS、PT、PR0、PR1、PA0和PA1分別表示各種類型欺騙攻擊成功的最大概率。

定義2各種攻擊成功的最大概率為

其中表示與發(fā)方的密鑰et相關(guān)聯(lián)的消息集合。進一步引入下列記號：

1）與接收者密鑰er相關(guān)聯(lián)的消息集合

2）加密產(chǎn)生消息m的發(fā)方的加密密鑰集合

3）使m有效的接收者的密鑰集合

4）與收方密鑰er相關(guān)聯(lián)的發(fā)方的加密密鑰集合

5）與發(fā)方密鑰et相關(guān)聯(lián)的收方的密鑰集合

6）與仲裁密鑰ea相關(guān)聯(lián)的收方的密鑰集合

運用上述記號，可重新將定義2改寫如下：

定義3在假定源狀態(tài)和發(fā)方的加密密鑰隨機選取的條件下，各種欺騙攻擊成功的最大概率為

運用式（8）～式（14）可方便地計算各類欺騙攻擊成功的概率。

定理1對于任何A2碼或A3碼，下列參數(shù)的界成立

如果一個A3的參數(shù)使定理1中4個不等式成立，這樣的A3碼稱為完善的A3碼。當參數(shù)大小相同時，完善的A3碼受到的欺騙攻擊成功的最大概率最小，即完善的A3碼安全水平最高；或在安全水平相同的情況下，完善的A3碼對存儲要求最小。

3 射影幾何

本節(jié)簡要介紹所用到的一些射影幾何的知識。未加說明的符號參見文獻[15]。

令n是一個正整數(shù)，q是一個素數(shù)方冪，F(xiàn)q是q元有限域表示Fq上的n+1維行向量空間。的一維子空間稱為點，二維子空間稱為線，三維子空間稱為面，n維子空間稱為超平面。更一般地的一個r+1維子空間稱為一個射影r-flat（0≤r≤n）。所有點的集合和所有的r-flat（0≤r≤n）以及連同定義在他們之間的關(guān)聯(lián)關(guān)系稱為有限域Fq上的n維射影空間，記為PG（n，F(xiàn)q）。

定理2在 PG（n，F(xiàn)q）中：

1）m-flats的個數(shù)為

2）包含在一個給定的m-flat中的k-flats的個數(shù)為

3）包含一個給定的k-flat的m-flats的個數(shù)為

稱為高斯系數(shù)。

定理3在 PG（n，F(xiàn)q）中：

1）通過任意兩個不同的點有且僅有一條線；

2）任何3個不共線的點恰好在一個面上；

3）任何r+1個點，其中任何r個點不在任何一個（r-1）-flat中，恰好包含在一個 r-flat中（1≤ r≤ n）。而在任何一個r-flat（1≤r≤n）中存在r+1個點不包含在任何一個（r-1）-flat中。

4 構(gòu)造

本節(jié)給出A3碼的一個新構(gòu)造。

令W是PG（4，q）中一個固定平面，L是W上一條固定的線。

源狀態(tài)集為

是L上的點}

發(fā)送者的加密密鑰集為

是一條線

接收者的密鑰集為

中不在 W 中的點}

仲裁的密鑰集為

是W中的點且ea?L}

消息集為

定義加密映射為

定義解密映射為

g：M × ER→S∪{拒絕}

三元組（et，er，ea）是有效的當且僅當 er、ea包含在et中，且ea是W中一個點。換句話說，KDC秘密地且隨機地選取一條線et作為發(fā)方的加密密鑰，其中et與L不相交，但與W交于一點；然后在et中選擇一個不在W中的點作為收方的密鑰er；選擇一個既在et又在W中的點ea作為仲裁的密鑰。

定理4以上構(gòu)造的碼是一個合理的A3碼，且

1）對任意的 s∈S，et∈ET，=m∈M；

2）對任意的m∈M，s∈m∩L是m包含的唯一的源狀態(tài)，且有一個 et∈ET使得 m=。

證明1）對任意s∈S，s是L中的一個點。對于任意et∈ET，et是一條線，其與W交于一個點，而這個點不在L上。顯然，m=是一個面，且交L于點s，與W的交恰好是一條線。因此，確實是一個消息。

2）對于 m∈M，令 s∈m∩L，則 s∈L，從而 s是一個源狀態(tài)。令l是m和W的交線，則點s在l上。令et是一條不在W中的線，且與l交于一個不同于s的點，則et是一個加密規(guī)則且=m。

假如s′是另一個包含在m中的源狀態(tài)，則s、s′是L上兩個不同的點，且都在m中，從而L包含在m中，這與矛盾。因此，s′=s，s是包含在 m 中的唯一源狀態(tài)。

定理5所構(gòu)造的A3碼的參數(shù)是：

證明由于是L中點的數(shù)目，故

令B是任意一個不在W中的點，C是任一個不在L但在W中的點。由于對每個et∈ET滿足所以 et可由 B、C 生成，即 et=。

由于有Q4（0，1）-Q2（0，1）=q3（q+1）個點不在W中，有Q2（0，1）-Q1（0，1）=q2個點在W中而不在L中，所以

由于有Q4（0，1）-Q2（0，1）=q3（q+1）個點不在W中，所以

由于有q2+q+1個點在面W中，有q+1個點在線L中，所以

假定l是一條包含在W中的一條線且與L交于一點。在PG（4，q）中，包含l的面有Q4（1，2）=q2+q+1（含W）。在面W中，與L交于一點的線有q2+q條，因此

定理6假定所有源狀態(tài)的選取是等可能的，所有的加密規(guī)則服從均勻分布，則所構(gòu)造的A3碼受到的各種欺騙攻擊成功的最大概率分別是

證明1）對于任意的m∈M，m中除了屬于W的點都可作為接收者的解密密鑰，即則

2）如果則

如果則

如果則

敵人的最優(yōu)攻擊策略是選擇m′使得其與m的交是一條線，且交線是一個加密規(guī)則，從而

3）對于給定的加密規(guī)則et，由于有q個點不在W中，所以從而

4）對于一個給定的er∈ER，ET（er）是過er而與平面W交于一個不在L上的點，故

對于m∈M，則et∈ET（er）∩ET（m）當且僅當et包含在m中而與L不交，則

5）收方收到消息m但卻聲稱收到消息m′，其中m′包含的源狀態(tài)s′不同于m包含的源狀態(tài)s。而et∈ET（er）∩ET（m）∩ET（m′）僅當et過er且m∩m′=et。而m與m′至多交于一條線，于是

6）對于仲裁的一個密鑰ea∈EA，接收者的每一個密鑰都有可能與ea關(guān)聯(lián)，故ER（ea）=ER。因此，仲裁對收方的攻擊能力并不比敵方的攻擊能力強，故

由定理1和定理6，可得下面的推論。

推論1所構(gòu)造的碼是一個完善的A3碼。

5 仿真結(jié)果

在這一部分給出一個仿真例子：當n=4，q=23時，對敵方的模仿攻擊效率進行了仿真。仿真結(jié)果表明，隨著攻擊強度的增強，實際攻擊成功的概率越來越低于理論值，如圖1所示。同時與Gao等[16]和Jahasson構(gòu)造的A3碼進行對比，本研究的構(gòu)造有更好的優(yōu)勢，如表1所示。

圖1 仿真結(jié)果Fig.1 Simulation result

表1 三種算法比較結(jié)果Tab.1 Comparison result

6 結(jié)語

研究主要基于有限域上的射影空間構(gòu)造一個完善的A3碼。Gao等[16]構(gòu)造的認證碼也是一個基于有限域上射影空間PG（n，F(xiàn)q）構(gòu)造的A3碼，其構(gòu)造是不完善的。Johansson基于有限域給出一個A3碼的構(gòu)造，盡管是完善的，但本研究的構(gòu)造有兩個概率更小，更具優(yōu)勢。

參考文獻：

[1]GILBERT E N,WACWILLIAMS F J,SLOANE N J A.Codes which detectdecption[J].BellSystemTechnicalJournal,1974,53(3)：405-424.

[2]SIMMONS G J.Message Authentication with Arbitration of TransmitterReceiver Disputes[C]//AdvancesinCryptology-EUROCRYPT’87,LNCS 304,Berlin,Heidelberg：Springer-Verlag,1988：151-165.

[3]JOHANSSON T.Lower bounds on the probability of deception in authentication with arbitration[J].IEEE Transactions on Information Theory,1994,40(5)：1573-1585.

[4]KUROSAWA K,OBANA S.Combinatorial bounds for authentication codes with arbitration[J].Designs,Codes and Cryptography,2001,22(3)：265-281.

[5]CHEN SHANGDI,ZHAO DAWEI.Two constructions of optimal cartesian authentication codes from unitary geometry over finite fields[J].Acta Mathematicae Applicatae Sinica,Enghlish Series,2013,29(4)：829-836.

[6]CHEE Y M,ZHANG XIANDE,ZHANG HUI.Infinite families of optimal splitting authentication codes secure against spoofing attacks of higher order[J].Advances in Mathematics of Communication,2011,5(1)：59-68.

[7]BRICKELL E F,STINSON D R.Authentication Codes with Multiple Arbiters[C]//AdvancesinCryptology-EUROCRYPT188,LNCS 330,Berlin,Heidelberg：Springer-Verlag,1988：51-55.

[8]WANG Y,SAFAVI-NAINI R.A3-Codes under Collusion Attacks[C]//ASIACRYPT’99,LNCS1716,Berlin,Heidelberg：Springer-Verlag,1999：390-398.

[9]ZHOU ZHI.The constructions of A2-codes from conventional A-codes[J].Journal of Electronics&Information Technology,1997,19(4)：489-493.

[10]PEI DINGYI.Message Authentication Codes[M].Hefei：University of Science and Technology of China Press,2009：200-203.

[11]TOMPA M,WOLL H.How to Share a Secret with Cheaters[C]//Advances in Cryptology-CRYPT0 ’86,LNCS 263,Berlin,Heidelberg：Springer-Verlag,1987：261-265,.

[12]HANAOKA G,SHIKATA J,HANAOKA Y,et al.The Role of Arbiters in Asymmetric Authentication Schemes[C]//Information Security,LNCS 2851,Berlin,Heidelberg：Springer-Verlag,2003：428-441.

[13]JOHANSSON T.Further results on asymmetric authentication schemes[J].Information and Computation,1999,151(1/2)：100-133.

[14]DESMEDT Y,YUNG M.Arbitrated Unconditionally Secure Authentication can be Unconditionally Protected Against Arbiter’s Attacks[C]//Advances in Cryptology-CRYPTO’90,LNCS 537,Berlin,Heidelberg：Springer-Verlag,1991：177-188.

[15]WAN ZHEXIAN.Geometry of Classical Groups over Finite Fields[M].Beijing：Science Press,2002：61-72.

[16]GAO YOU,LIU YANQIN.The construction of A3-code from projective spaces over finite fields[J].WSEAS Transactions on Mathematics,2013,12(10)：1024-1033.