構(gòu)造一類cartesian認(rèn)證碼的新方法

趙永鵬，周厚春

1.山東師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，濟(jì)南 250014

2.臨沂大學(xué) 理學(xué)院，山東 臨沂 276005

構(gòu)造一類cartesian認(rèn)證碼的新方法

趙永鵬1，周厚春2

1.山東師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，濟(jì)南 250014

2.臨沂大學(xué) 理學(xué)院，山東 臨沂 276005

1 引言

信息認(rèn)證是信息安全的重要內(nèi)容之一，它是檢驗(yàn)收到的信息是否被篡改，檢驗(yàn)收到的信息是否來(lái)自真正的發(fā)方以及防止非法接收者接收信息的一種重要技術(shù)。認(rèn)證碼是解決信息認(rèn)證問(wèn)題的一種有效方法，認(rèn)證編碼是認(rèn)證系統(tǒng)中實(shí)現(xiàn)安全認(rèn)證的基本途徑，是防止主動(dòng)攻擊的重要手段。認(rèn)證理論自從1979年提出以后，世界上許多密碼學(xué)家和數(shù)學(xué)家都致力于這一方向的研究。Simmons在1984年于文獻(xiàn)[1]中系統(tǒng)地提出了認(rèn)證碼理論。從此，人們的研究主要集中在認(rèn)證碼的構(gòu)造和身份認(rèn)證方案的設(shè)計(jì)及性質(zhì)上。基于不同的理論，國(guó)內(nèi)外許多學(xué)者給出了多種性能很好的cartesian認(rèn)證碼的構(gòu)造方法，如利用有限域上的交錯(cuò)矩陣、有限域上的辛幾何、有限域上的對(duì)合陣、可逆變換、組合設(shè)計(jì)、射影幾何、跡函數(shù)等得到了不同的認(rèn)證碼[1-7]。近幾年，高有、霍立群等利用有限域上奇異辛幾何構(gòu)造一個(gè)新的帶仲裁的認(rèn)證碼；王紅麗利用有限域上向量空間構(gòu)造了cartesian認(rèn)證碼[8-10]。本文利用完全圖中的生成樹(shù)給出了一類cartesian認(rèn)證碼構(gòu)造的新方法，并計(jì)算了相應(yīng)的參數(shù)和各種攻擊成功的概率。

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

定義1設(shè)S，E，Μ為三個(gè)非空集合，f:S×E→Μ為一個(gè)滿映射，且滿足條件：對(duì)于m∈Μ，e∈E，如果存在s∈S，使得m=f(s，e)，則s是由m和e所唯一確定的。稱(S，E，Μ;f)為一個(gè)認(rèn)證碼，|S|，|E|，|Μ|稱為碼參數(shù)，其中S表示信源集合，E表示編碼規(guī)則，Μ表示消息集合，f表示編碼函數(shù)。

一個(gè)認(rèn)證有三個(gè)參加方分別為發(fā)方、收方和敵方。發(fā)方和收方是互相信任的，它們共同約定好要使用哪一種編碼規(guī)則，而敵方則試圖欺騙收方。假如發(fā)方、收方約定好要使用的編碼規(guī)則后，連續(xù)發(fā)出了r個(gè)消息m1，m2，…，mr，這時(shí)敵方觀察得到這r個(gè)消息之后，利用這r個(gè)消息分析得到關(guān)于所用編碼規(guī)則的一些重要信息，這時(shí)敵方可以根據(jù)所得到的編碼規(guī)則信息發(fā)出偽造的消息m，希望收方能夠把它當(dāng)做真的消息來(lái)接受，就稱為r階欺騙攻擊，用pr來(lái)表示r階欺騙攻擊成功的概率。當(dāng)r=0時(shí)稱為冒充攻擊，用pI表示冒充攻擊成功的概率；當(dāng)r=1時(shí)稱為替換攻擊，用pS表示替換攻擊成功的概率。

下面介紹將用到的一些記號(hào)及定義：

E(mr)={e∈E|mi在e下能被接受且fe(mi)兩兩不同，1≤i≤r}

定義2不包含圈的圖稱為無(wú)圈圖，連通的無(wú)圈圖稱為樹(shù)。

定義3設(shè)G=(V，E)，圖G的一個(gè)生成子圖T如果是一棵樹(shù)，則稱T為圖G的一棵生成樹(shù)。

定義4有k個(gè)點(diǎn)的生成樹(shù)稱為一個(gè)k-生成樹(shù)，用T(n，k)來(lái)表示完全圖Kn中的k-生成樹(shù)的個(gè)數(shù)。

定義5給定一個(gè)認(rèn)證碼 (S，E，Μ;f)，若對(duì)任意的m∈Μ，存在唯一的s∈S，使f(s，e)=m，其中e是包含于E中的任意編碼規(guī)則，則稱(S，E，Μ;f)為cartesian認(rèn)證碼。

1995 年，裴定一給出了下面的信息論下界：

定理1[2]對(duì)于任意無(wú)仲裁的認(rèn)證碼，r階欺騙攻擊成功的概率有下界：

且等式成立的充要條件是，對(duì)任意的mr∈Μr及m∈Μ，若Sr，E上的概率分布是均勻的，則

定理2[4]設(shè)n為任意大于2的整數(shù)，則具有n個(gè)信源，2n個(gè)消息及個(gè)編碼規(guī)則的認(rèn)證碼是存在的，且r階欺騙攻擊成功的概率，其中l(wèi)＜n為正整數(shù)。

3 認(rèn)證碼的構(gòu)造及主要結(jié)果

下面將用完全圖中的k-生成樹(shù)知識(shí)來(lái)構(gòu)造一類cartesion認(rèn)證碼，且推導(dǎo)出r階欺騙攻擊成功的概率估計(jì)式的新下界。

信源集合為S={a1，a2，…，an}

引理1具有n(n≥3)個(gè)信源，|Μ|個(gè)消息以及個(gè)編碼規(guī)則的認(rèn)證碼是存在的，且 (S，E，Μ;f)是 cartesian認(rèn)證碼。

同理，若確定了兩個(gè)消息m1，m2，則共有個(gè)編碼規(guī)則，從而：

引理證畢。

引理3對(duì)于引理1中所述的cartesian認(rèn)證碼，其r階欺騙攻擊成功的概率pr達(dá)到式（1）的信息論下界，即對(duì)于：

其中l(wèi)＜n為正整數(shù)。

證明假如已經(jīng)確定了一個(gè)消息m，則共有個(gè)編碼規(guī)則。類似地，若確定了r個(gè)消息m1，m2，…，mr，則共有個(gè)編碼規(guī)則，根據(jù)定理1中式（2）有：

引理證畢。

定理3設(shè)n≥3為任意整數(shù)，則具有n個(gè)信源，| |Μ個(gè)消息以及個(gè)編碼規(guī)則的認(rèn)證碼是存在的，其r階欺騙攻擊成功的概率Pr達(dá)到式（1）的信息論下界，即對(duì)于，其中l(wèi)＜n為正整數(shù)。

證明只需證明對(duì)?n≥4，|Μ|＞2n即可。而由引理2知

所以當(dāng)n≥4時(shí)，|Μ|≥2n。定理證畢。

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

本文利用完全圖中的k-生成樹(shù)知識(shí)構(gòu)造了一類cartesian認(rèn)證碼，在引理1中給出了這個(gè)碼的各種參數(shù)，當(dāng)收方和發(fā)方的編碼規(guī)則按等概率分布選取時(shí)，引理2分析了這個(gè)碼的安全性，給出了這個(gè)碼被幾種攻擊成功的最大概率。由定理3知，本文的pr遠(yuǎn)遠(yuǎn)小于文獻(xiàn)[4]中的pr。所以從子集角度來(lái)看，文獻(xiàn)[4]中的pr包含于本文構(gòu)造的pr，從而推廣了王永傳、楊義先在文獻(xiàn)[4]中的信息論下界，同時(shí)也說(shuō)明了本文構(gòu)造的認(rèn)證碼有更復(fù)雜的編碼規(guī)則，因此在通信過(guò)程中信息被插入、偷看、刪除或者偽造的可能性更小，從而加大了保證信息的安全性。

[1]Simmons G J.Authentication coding theory[C]//Lecture Notes in Computer Science：Advances in Cryptology-crypto’84，1985：411-431.

[2]Pei Dingyi.Information-theoretic bounds authentication codes and block designs[J].Cryptology，1995，8：177-188.

[3]Wan Z.Further constructions of cartesian code from symplectic geometry[J].Northeastern Mathematical Journal（China），1992，8：4-20.

[4]王永傳，楊義先.利用集合知識(shí)構(gòu)造認(rèn)證碼[J].通信保密，1997（1）：61-63.

[5]裴定一.認(rèn)證碼及其構(gòu)造的一些研究[C]//密碼學(xué)進(jìn)展-Chinacrypto’92，第二屆密碼學(xué)術(shù)會(huì)議論文集.北京：科學(xué)出版社，1992：66-73.

[6]王永傳，楊義先.一類分裂的cartesian認(rèn)證碼的構(gòu)造[J].通信保密，1997（4）：48-51.

[7]高有，陶亞媛.利用有限域上交錯(cuò)矩陣構(gòu)造cartesion認(rèn)證碼[J].高校應(yīng)用數(shù)學(xué)學(xué)報(bào)，2007（4）：385-390.

[8]李殿龍.一類新的Cartesian認(rèn)證碼[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（24）：124-125.

[9]高有，霍立群.利用有限域上奇異辛幾何構(gòu)造一個(gè)新的帶仲裁的認(rèn)證碼[J].工程數(shù)學(xué)學(xué)報(bào)，2011（10）：629-641.

[10]王紅麗.利用有限域上向量空間構(gòu)造cartesian認(rèn)證碼[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（1）：114-115.

ZHAO Yongpeng1,ZHOU Houchun2

1.School of Mathematical Sciences,Shandong Normal University,Jinan 250014,China
2.School of Sciences,Linyi University,Linyi,Shandong 276005,China

The cartesian authentication codes based onk-spanning tree are constructed and their parameters are derived.The probabilities of success for the impersonation attack,the substitution attack andr-spoofing attack are also computed respectively based on the assumption of the encoding rules which are chosen according to a uniform probability distribution.These results extend results given by Wang Yongchuan and Yang Yixian.

cartesian authentication code;k-spanning tree;r-spoofing attack;lower bound of information theory

利用完全圖Kn中的k-生成樹(shù)性質(zhì)構(gòu)造了一個(gè)新的cartesian認(rèn)證碼，計(jì)算了碼參數(shù)，當(dāng)編碼規(guī)則按照均勻的概率分布被選取時(shí)，計(jì)算了該碼的成功冒充攻擊概率、成功替換攻擊概率和r階欺騙攻擊成功的概率，改進(jìn)了已有的相關(guān)結(jié)果。

cartesian認(rèn)證碼；k-生成樹(shù)；r階欺騙攻擊；信息論下界

A

TP393

10.3778/j.issn.1002-8331.1112-0379

ZHAO Yongpeng,ZHOU Houchun.New construction of cartesian authentication codes.Computer Engineering and Applications,2013,49（18）：86-88.

國(guó)家自然科學(xué)基金（No.10771120）；山東省自然科學(xué)基金（No.Y2008A27）。

趙永鵬（1984—），男，碩士研究生，主要研究領(lǐng)域?yàn)檎J(rèn)證碼，組合最優(yōu)化；周厚春（1964—），男，博士，教授，主要研究領(lǐng)域?yàn)檫\(yùn)籌學(xué)與控制論。E-mail：zhouhouchun@163.com

2011-12-20

2012-03-06

1002-8331（2013）18-0086-03

CNKI出版日期：2012-05-21 http://www.cnki.net/kcms/detail/11.2127.TP.20120521.1141.037.html