構造一類cartesian認證碼的新方法

趙永鵬，周厚春

1.山東師范大學 數學科學學院，濟南 250014

2.臨沂大學 理學院，山東 臨沂 276005

構造一類cartesian認證碼的新方法

趙永鵬1，周厚春2

1.山東師范大學 數學科學學院，濟南 250014

2.臨沂大學 理學院，山東 臨沂 276005

1 引言

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

2 預備知識

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

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

下面介紹將用到的一些記號及定義：

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

定義2不包含圈的圖稱為無圈圖，連通的無圈圖稱為樹。

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

定義4有k個點的生成樹稱為一個k-生成樹，用T(n，k)來表示完全圖Kn中的k-生成樹的個數。

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

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

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

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

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

3 認證碼的構造及主要結果

下面將用完全圖中的k-生成樹知識來構造一類cartesion認證碼，且推導出r階欺騙攻擊成功的概率估計式的新下界。

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

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

同理，若確定了兩個消息m1，m2，則共有個編碼規則，從而：

引理證畢。

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

其中l＜n為正整數。

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

引理證畢。

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

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

所以當n≥4時，|Μ|≥2n。定理證畢。

4 結束語

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

[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]王永傳，楊義先.利用集合知識構造認證碼[J].通信保密，1997（1）：61-63.

[5]裴定一.認證碼及其構造的一些研究[C]//密碼學進展-Chinacrypto’92，第二屆密碼學術會議論文集.北京：科學出版社，1992：66-73.

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

[7]高有，陶亞媛.利用有限域上交錯矩陣構造cartesion認證碼[J].高校應用數學學報，2007（4）：385-390.

[8]李殿龍.一類新的Cartesian認證碼[J].計算機工程與應用，2010，46（24）：124-125.

[9]高有，霍立群.利用有限域上奇異辛幾何構造一個新的帶仲裁的認證碼[J].工程數學學報，2011（10）：629-641.

[10]王紅麗.利用有限域上向量空間構造cartesian認證碼[J].計算機工程與應用，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-生成樹性質構造了一個新的cartesian認證碼，計算了碼參數，當編碼規則按照均勻的概率分布被選取時，計算了該碼的成功冒充攻擊概率、成功替換攻擊概率和r階欺騙攻擊成功的概率，改進了已有的相關結果。

cartesian認證碼；k-生成樹；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.

國家自然科學基金（No.10771120）；山東省自然科學基金（No.Y2008A27）。

趙永鵬（1984—），男，碩士研究生，主要研究領域為認證碼，組合最優化；周厚春（1964—），男，博士，教授，主要研究領域為運籌學與控制論。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