基于有限域上射影空間構(gòu)造分裂認(rèn)證碼

陳尚弟，張小連

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

基于有限域上射影空間構(gòu)造分裂認(rèn)證碼

陳尚弟，張小連

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

傳統(tǒng)的認(rèn)證碼中，報(bào)文由信源和編碼規(guī)則唯一確定，但現(xiàn)實(shí)情況中，信源在同一編碼規(guī)則作用下能夠產(chǎn)生不止一個(gè)報(bào)文。分裂認(rèn)證碼正是基于這種現(xiàn)狀而產(chǎn)生。本研究的目的是構(gòu)造新的分裂認(rèn)證碼。運(yùn)用有限域上射影空間的子空間結(jié)構(gòu)和相關(guān)計(jì)數(shù)定理，構(gòu)造了兩個(gè)分裂認(rèn)證碼，并計(jì)算其參數(shù)。當(dāng)所有規(guī)則都按等概率分布選取時(shí)，計(jì)算了敵方的假冒攻擊和替代攻擊成功的概率。結(jié)果表明，所構(gòu)造的碼能有效地抵抗敵方的假冒和替代攻擊。

有限域；射影空間；分裂認(rèn)證碼

1 預(yù)備知識(shí)

定義1 設(shè)S、E、M為3個(gè)非空有限集合。f：S× E→M為滿足下列條件的映射。四元組（S，E，M；f）稱為一個(gè)認(rèn)證碼[1]，如果：

1）f：S×E→M是滿射；

2）對(duì)任意的m∈M，任意的e∈E，若存在一個(gè)s∈S滿足f（s，e）=m，則這樣的s由給定的m和e唯一確定。

分別稱S、E、M為信源集合、編碼規(guī)則集合和報(bào)文集合，f為編碼映射?；鶖?shù)稱為這個(gè)碼的參數(shù)。

定義2 設(shè)（S，E，M；f）為一個(gè)認(rèn)證碼，若一個(gè)信源s∈S在相同的編碼規(guī)則e∈E的作用下能夠產(chǎn)生不止一個(gè)報(bào)文，即報(bào)文m∈M不是由信源s∈S和編碼規(guī)則e∈E唯一確定的，則稱該認(rèn)證碼是分裂的[2]。

此時(shí)報(bào)文m∈M是由m=e（s，r）計(jì)算而得，其中r是某個(gè)特定有限集合中的隨機(jī)數(shù)。令對(duì)于某些r使得e（s，r）=m成立}，則分裂認(rèn)證碼中必有

定義3 在分裂認(rèn)證碼中，若對(duì)任意的信源s∈S和編碼規(guī)則e∈E都有則稱該認(rèn)證碼是c-分裂的[2]。

在分裂認(rèn)證模型中包括3個(gè)參加方：發(fā)方、收方和敵方。發(fā)方與收方事先約定好編碼規(guī)則e∈E，發(fā)方欲傳送信源信息s∈S給收方。發(fā)方將信源s用編碼規(guī)則e編譯成報(bào)文e（s）∈M并隨機(jī)地選取其中一個(gè)報(bào)文m∈e（s）將其發(fā)送給收方，收方收到報(bào)文m后利用編碼規(guī)則e判定m是否合理。若合理則可由消息m得到信源s，若不合理，則拒絕消息m。敵方在發(fā)方未發(fā)送任何報(bào)文的前提下，通過信道發(fā)送一個(gè)他偽造的報(bào)文給收方，稱為假冒攻擊。若收方將其作為合理報(bào)文并接收，則稱敵方假冒攻擊成功。將敵方假冒攻擊的最大概率記為PI。敵方在截獲到報(bào)文m后，用另一報(bào)文m′代替原來的報(bào)文并發(fā)送給收方，稱為替代攻擊。若收方以m′為合法報(bào)文，且m與m′代表不同的信源，則稱敵方替代攻擊成功，記這種攻擊成功的最大概率為PS。

認(rèn)證碼是用于在公用信道實(shí)現(xiàn)消息認(rèn)證的編碼辦法，多年來，人們通過有限域上的典型群幾何學(xué)構(gòu)造了多種多樣參數(shù)優(yōu)良的認(rèn)證碼，如Chen在文獻(xiàn)[3]中基于奇異辛空間構(gòu)造了多重多接收認(rèn)證碼，在文獻(xiàn)[4]中基于偽辛空間構(gòu)造了帶仲裁的認(rèn)證碼。又如Gao于文獻(xiàn)[5]基于射影空間構(gòu)造了A3-code。然而基于有限域上典型群的幾何學(xué)上研究分裂認(rèn)證碼的文獻(xiàn)寥寥無幾。分裂認(rèn)證碼最先是由Simmons于文獻(xiàn)[6]引入的。在分析帶仲裁認(rèn)證碼參數(shù)和攻擊概率方面，分裂認(rèn)證碼作用顯著。特別地，Kurosawa和Obana[7]給出了一個(gè)分裂認(rèn)證碼和帶仲裁的認(rèn)證碼之間的弱等價(jià)關(guān)系。王永傳、楊義先在文獻(xiàn)[8]中發(fā)現(xiàn)，分裂認(rèn)證碼與糾錯(cuò)碼也有密切聯(lián)系。另外，Huber[9]也刻畫了分裂認(rèn)證碼的組合論界。進(jìn)而，杜北梁和梁淼[2]創(chuàng)造性地將構(gòu)造最優(yōu)分裂碼的問題轉(zhuǎn)化為構(gòu)造相應(yīng)的帶約束的部分平衡區(qū)組t-設(shè)計(jì)的問題，運(yùn)用組合設(shè)計(jì)的思維方式拓寬了分裂認(rèn)證碼的構(gòu)造。本文旨在探究基于有限域上典型群的幾何學(xué)特別是射影空間經(jīng)過創(chuàng)新性加工構(gòu)造具有可行性的、參數(shù)較優(yōu)的分裂認(rèn)證碼。

2 有限域的射影空間

由文獻(xiàn)[10]得到以下內(nèi)容。

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

2）包含在給定m-flat的k-flat（0≤k≤m≤n）的數(shù)量為

3）包含在給定k-flat的m-flat（0≤k≤m≤n）的數(shù)量為

這里

是高斯系數(shù)，其中0≤m≤n為正整數(shù)，q為素?cái)?shù)冪。

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

3.1 構(gòu)造Ⅰ

3.1.1 構(gòu)造方案

在PG（3，F(xiàn)q）中固定一條直線L，令

給定編碼規(guī)則e與信源s，取e上任意一點(diǎn)α。由信源s和點(diǎn)α兩點(diǎn)唯一地確定一條直線，該直線是與L相交于一點(diǎn)的直線。由于α的任意性，c=q+1。3.1.2 認(rèn)證碼的參數(shù)

定理2 該認(rèn)證碼的參數(shù)為

證明1）直線L上有q+1個(gè)點(diǎn)，故信源的個(gè)數(shù)為

固定L上一點(diǎn)α，則在PG（3，F(xiàn)q）中包含點(diǎn)α的直線的個(gè)數(shù)為

2）在射影空間PG（3，F(xiàn)q）中直線總數(shù)為

從而與L相交于一點(diǎn)的直線有與L不相交的直線有

（q4+q3+2q2+q+1）-（q3+2q2+q）-1=q4即編碼規(guī)則個(gè)數(shù)為

3）從上述編碼規(guī)則個(gè)數(shù)計(jì)算過程可知，與L交于一點(diǎn)的直線條數(shù)為q3+2q2+q，即信息的個(gè)數(shù)為

3.1.3 欺騙攻擊類型和攻擊成功概率

定理3 該方案中欺騙攻擊成功的概率為

證明1）假設(shè)m為報(bào)文，則m是與L交于一點(diǎn)的直線，且交點(diǎn)為信源s。對(duì)報(bào)文m有效的編碼規(guī)則集合記為E（m），則即E（m）是與L不相交且與m只交于一點(diǎn)的直線的集合。由定理2可知，與m相交于一點(diǎn)的直線的個(gè)數(shù)為q3+2q2+ q，與m、L相交于同一點(diǎn)的直線的個(gè)數(shù)為q2+q-1，與m、L相交于不同兩點(diǎn)的直線的個(gè)數(shù)為q2，從而則

2）設(shè)m、m′是同時(shí)對(duì)編碼規(guī)則e有效的不同報(bào)文，令s、s′分別是m、m′對(duì)應(yīng)的信源。不失一般性，設(shè)e與m相交于點(diǎn)A，與m′相交于點(diǎn)B，則同時(shí)對(duì)m、m′有效的編碼規(guī)則e只能是直線AB，即因此替代攻擊成功最大的情形是m、m′相交于一點(diǎn)P，編碼規(guī)則是過點(diǎn)P與L不相交的直線。由于s、s′、P三點(diǎn)不共線，從而唯一地確定一個(gè)平面Π，則對(duì)m、m′同時(shí)有效的編碼規(guī)則e為與平面Π只交于點(diǎn)P的直線。在PG（3，F(xiàn)q）中除去平面Π的共有點(diǎn)的個(gè)數(shù)為q3，又任意q點(diǎn)共線，從而

3.2 構(gòu)造Ⅱ

在PG（4，F(xiàn)q）中固定一直線L，令

給定編碼規(guī)則e與信源s，取e上兩點(diǎn)α1、α2，信源s為α3。由于L與e不相交，從而L不包含在α1、α2、α3所生成的平面T上。由于在射影空間內(nèi)，一個(gè)平面內(nèi)的任意兩條直線相交，從而不在T上的任意一點(diǎn)與T生成一個(gè)包含e和s的超平面。

不在T上的點(diǎn)共有

在一個(gè)包含e和s的超平面中，不包含在T上的點(diǎn)有

包含e和s的超平面中有一個(gè)超平面包含L。因此

定理4 該認(rèn)證碼的參數(shù)為

證明1）在直線L上有q+1個(gè)點(diǎn)，故信源的個(gè)數(shù)為

2）在射影空間PG（4，F(xiàn)q）中直線總數(shù)為

又由于通過一固定點(diǎn)的直線的個(gè)數(shù)為

從而與L相交的直線有

編碼規(guī)則是與L不相交的直線，因此編碼規(guī)則的個(gè)數(shù)為

3）固定L上一點(diǎn)α，則包含α的超平面?zhèn)€數(shù)為

在PG（4，F(xiàn)q）中，包含L的超平面的個(gè)數(shù)為

從而與L相交于點(diǎn)α的超平面的個(gè)數(shù)為q3。

由α的任意性可知

定理5 該方案中欺騙攻擊成功的概率為

證明1）假設(shè)m為報(bào)文，對(duì)報(bào)文m有效的編碼規(guī)則集合記為E（m），則E（m）中元素為超平面m中不過點(diǎn)s的直線。超平面m中直線總數(shù)為

超平面m中過點(diǎn)s的直線個(gè)數(shù)為

Construction splitting of authentication codes from projective space over finite field

CHEN Shang-di，ZHANG Xiao-lian
（College of Science，CAUC，Tianjin 300300，China）

In traditional authentication codes，messages are determined by source state and encoding rule.However，the source state can produce more than one messages under the same encoding rule in reality.Splitting authentication codes are produced in this situation.The main focus of this research is the construction of new splitting authentication codes.Based on subspace structures from projective space over finite fields and basic counting theories，two splitting authentication codes splitting are constructed，and their size parameters are computed. Assuming that the encoding rules are chosen according to a uniform probability distribution，the probabilities of a successful impersonation and a successful substitution by the opponent are computed.Results indicate that the newly constructed codes can effectively resist the enemy’s impersonation and substitution attack.

finite field；projective space；splitting authentication codes

O157

：A

：1674－5590（2015）06－0047－03

2014-09-12；

：2014-11-12

國家自然科學(xué)基金項(xiàng)目（61179026）；中國民航大學(xué)學(xué)生科技立項(xiàng)項(xiàng)目（152A035473026）

陳尚弟（1964—），男，山西應(yīng)縣人，教授，博士，研究方向?yàn)榇鷶?shù)、圖論、編碼與密碼.