具有動態(tài)發(fā)送功能的多信源認證碼的構(gòu)造

陳尚弟，常麗珍

（中國民航大學理學院，天津300300）

具有動態(tài)發(fā)送功能的多信源認證碼的構(gòu)造

陳尚弟，常麗珍

（中國民航大學理學院，天津300300）

在一個群通信體系中，最基本并且最具有實際意義的認證系統(tǒng)是指關(guān)于動態(tài)發(fā)送者的多接收認證碼（簡稱DMRA-code）。但目前，許多學者對其研究僅僅局限于對一個信源的認證。然而在網(wǎng)絡通信中，常常會有多信源傳播的場景?；谶@個問題，利用多項式構(gòu)造一個具有動態(tài)發(fā)送功能的多信源認證碼，并且驗證了該模型的合理性以及計算出了可能的攻擊概率，從而保證了所構(gòu)造的方案的安全性。

認證碼；多信源；動態(tài)；多項式

隨著計算機網(wǎng)絡的不斷發(fā)展，網(wǎng)絡通信技術(shù)在現(xiàn)實社會中的各個領域均得到了廣泛的應用，尤其是群通信技術(shù)越來越受到人們的青睞。對于安全的群通信體系，許多學者已經(jīng)做過不少研究，提供了許多安全的認證方案。其中Desmedt，F(xiàn)rankel和Yung[1]給出了一種多對一（多接收或多發(fā)送）的認證方案，但此構(gòu)造要求一個發(fā)送者（接收者）是提前固定的，在實際應用中不具有靈活性；后來，R.Safavi-Naini和Wang[2]進一步擴展了該思想，放寬了這種限制，引入了動態(tài)發(fā)送者（DMRA-codes）的概念，也就是說群通信中的任何一個成員都可能是發(fā)送者；接著，他們又給出了關(guān)于t個動態(tài)發(fā)送者（簡稱tDMRA-codes）的構(gòu)造[3]，在該文獻中將動態(tài)的發(fā)送者由一個擴展到了多個，從而發(fā)展了具有動態(tài)功能的認證碼；另外，杜慶靈針對多對一（多接收或多發(fā)送）的多信源認證問題進行了研究[4]，促進了多信源認證的發(fā)展；近年來，R.Aparna與B.B.Amberker對于動態(tài)的群通信系統(tǒng)構(gòu)造了一系列更為靈活和有效的模型[5-7]，極大地豐富和完善了群通信的認證。然而，在上述系統(tǒng)中，大多都是針對于一個信源的認證，對多信源認證的研究并不充分?？墒窃趯嶋H應用中，經(jīng)常會有多個信源的傳播?；谶@個問題，利用多項式構(gòu)造了一個無條件安全的具有動態(tài)功能的多信源認證碼，同時計算出了可能的攻擊概率。

1 預備知識

在一個DMRA-codes中，假設有n個參與者U1，U2，…，Un在一個公開的信道上通信，同時還有一個可信賴的密鑰分發(fā)中心（KDC），KDC的任務就是通過安全信道給每一個用戶分發(fā)密鑰，它只在密鑰分配階段起作用，并不參與后來的通信。在該模型中消息的傳送需要遵循下列協(xié)議：

1）密鑰分配KDC秘密地給每一個參與者分配密鑰，以及它們的身份信息；

2）廣播對于每個發(fā)送者Ui（1≤i≤n），利用自己的密鑰對一信源s進行編碼產(chǎn)生一個認證消息并廣播該認證消息；

3）驗證其余每個參與者Uj（j≠i）當收到消息后，利用其分得的密鑰對其進行身份驗證和信息驗證，判斷其真實性。

對于這種動態(tài)的認證系統(tǒng)，存在兩類攻擊：一種是外部攻擊，一種是內(nèi)部攻擊。內(nèi)部攻擊是指一些惡意的參與者聯(lián)合起來利用獲得的密鑰和觀察到的信息，對其他參與者進行攻擊。因為內(nèi)部參與者肯定比外部敵手擁有更多的信息量，所以攻擊成功的可能性更大，因此一般只考慮內(nèi)部攻擊。

假設有k-1個惡意參與者UL={Ul1，Ul2，…，Ulk-1}，勾結(jié)起來針對另外一對參與者{Ui，Uj}進行仿冒攻擊或者替換攻擊。在仿冒攻擊中，UL利用Ui的身份信息產(chǎn)生一個消息m并發(fā)送給Uj，若Uj接受m并且認為是由Ui所發(fā)出的，則表示攻擊成功，用PI[m；i，j；UL]表示這種攻擊成功的概率，對于整個系統(tǒng)而言，則有

這里{L，i，j}取遍了{1，2，…，n}中所有可能的k+1個元素。在替換攻擊中，當觀察到Ui發(fā)出一個有效的消息m后，UL構(gòu)造了一個偽消息m′（m′≠m）發(fā)送給Uj，若Uj接受m′并且認為是從Ui所發(fā)出的，則表示攻擊成功，用PS[m，m′；i，j；UL]來表示這種攻擊成功的概率，對于整個系統(tǒng)而言，則有

這里{L，i，j}取遍了{1，2，…，n}中所有可能的k+1個元素。

2 Safavi-Naini的DMRA-code

回顧文獻[2]中由R.Safavi-Naini和H.Wang給出的關(guān)于DMRA-code的構(gòu)造方案。假設有n個參與者U1，U2，…，Un，每一個參與者Ui所得到密鑰為由三個隨機選擇的系數(shù)為有限域GF（q）中的次數(shù)至多為k-1的多項式（F0（ix），F(xiàn)1（ix），F(xiàn)2（ix））組成，所得到的身份信息為有限域GF（q）中的元素ai，其中1≤i≤n。對于一個信源s∈S，參與者Ui利用其密鑰進行加密，得到

然后將（s，ai，G（1x），G（2x））傳播出去。其余參與者Uj（j≠i）收到信息后，利用自己的密鑰（F0（jx），F(xiàn)1（jx），F(xiàn)2（jx））進行驗證，計算兩個等式

是否成立。若成立，則接受；否則，拒絕。在該文獻中，已經(jīng)證明出在任何k個參與者中，至多有k-1個參與者所進行的聯(lián)合攻擊成功的概率不會超過。

3 關(guān)于動態(tài)發(fā)送者的多信源認證碼的構(gòu)造

在第2部分的基礎上，利用有限域上的多項式構(gòu)造一個具有動態(tài)發(fā)送功能的多信源認證碼。假設有n個用戶U1，U2，…，Un，同時還有一個可信賴的密鑰分發(fā)中心KDC，令S為信源集，且S?GF（q），（q≥|S|+ n），該構(gòu)造方案共分3個階段。

1）密鑰分配KDC隨機選擇了n個不同的元素ai∈GF（q）S，分別給了每個用戶Ui（1≤i≤n）作為其公開的身份信息；同時，KDC又選擇了w+2個系數(shù)為GF（q）上的次數(shù)至多為k-1的對稱多項式

其中Al（0≤l≤w+1）是一個對稱矩陣。對于每一個i （1≤i≤n），KDC生成w+2個多項式

然后它將這w+2個多項式（F0 i（x），F(xiàn)1i（x），…，F(xiàn)（w+1）i（x））秘密地發(fā)送給Ui，并作為其密鑰。

2）廣播對需要認證的信源s∈S，用戶Ui計算

然后對其余的用戶廣播（s，ai，G1（x），G2（x））。

3）驗證當用戶Uj（j≠i）收到信息（s，ai，G1（x），G2（x））后，用自己的密鑰進行驗證，若

則接受它，否則拒絕。

下面驗證所構(gòu)造方案的合理性及其安全性。

引理1在上述所構(gòu)造的方案中，每一個密鑰至多能夠認證w個信源。

證明假設用戶Ui想要對Uj廣播w+1個信源：s1，s2，…，sw，sw+1，先進行計算

然后將（ai，（s1，s2，…，sw+1），G（1x），G（2λ）（x））傳播出去，其中λ=1，2，…，w，w+1。因為通信的信道并不安全，所以在傳播過程中，完全有可能被攻擊者截獲，從而對Uj進行替換攻擊。事實上，當（ai，（s1，s2，…，sw+1），G（1x），）發(fā)送出去，攻擊者看到信息后，可以利用用戶Uj的身份信息aj進行驗證，通過計算如下等式

因為等號右邊矩陣為Vandermonde矩陣，所以可得到唯一的解

令X=（1，x，…，xw+1），對于一個確定的值m=若有方程式

其中：XT為X的轉(zhuǎn)置，則X的解至多有w+1個。那么攻擊者完全可以選擇另一個信源s′（s′≠sλ）來代替sλ發(fā)送給Uj，并且由上述驗證得知：Uj一定會接受它并以為是從Ui發(fā)出的，說明此時攻擊者攻擊成功的概率為1，所構(gòu)造的方案并不安全。反之，若Ui只發(fā)送出w個信源，由上述分析得知攻擊者不可能得到唯一的解

那么不可能攻擊成功，系統(tǒng)是安全的。綜上，得證：所構(gòu)造的方案中，每一個密鑰至多能夠認證w個信源。

引理2該方案至多能夠防止k-1個用戶的聯(lián)合攻擊。

證明假設有k個用戶勾結(jié)者為L=（U1，U2，…，Uk），則L知道自己的密鑰

而Al（0≤l≤w+1）是一個k×k階的對稱矩陣，下面只考慮l=0時的情形，其它情形類似。不妨假設

其中：1≤i≤k?，F(xiàn)在考慮最高次項的系數(shù)，可以得到下列方程組

其中：δ′，δ″，…，δ（k）均是確定的值。因為上述方程組的系數(shù)矩陣為k×k階的Vandermonde矩陣，所以可得到唯一的解：d1k，d2k，…，dkk；同理，通過計算其余次項的系數(shù)，也會得到唯一的解，這樣A0就被確定了。同樣的道理，A1，A2，…，Aw+1也會被唯一確定，那么整個系統(tǒng)的密鑰就會被L確定，則它進行攻擊的概率就為1。反之，如果有k-1個人聯(lián)合攻擊，得到的上述方程組的系數(shù)矩陣并非Vandermonde矩陣，所以它的解并不唯一，那么L確定不了系統(tǒng)的密鑰，攻擊概率必定小于1，說明系統(tǒng)是安全的。綜上所述，得證：該方案至多能夠防止k-1個用戶的聯(lián)合攻擊。

證明根據(jù)引理1，已知上述所構(gòu)造的方案是一個合理的具有動態(tài)功能的多信源認證碼，它能同時認證w個信源。下面計算攻擊成功的概率。在這里只考慮替換攻擊，仿冒攻擊類似可得證。

說明（k，n）型是指在任意k個人之中，至多有k-1個人進行聯(lián)合攻擊的概率不會超過。事實上，令k-1個聯(lián)合攻擊者為L=（U1，U2，…，Uk-1），假設用戶Ui發(fā)送出認證消息

其中：G1（x），，λ=1，2，…，w同引理1。當L看到此消息后，想構(gòu)造一個新的消息

也就是說，L想用另一個信源s′（s′≠sw）來替換其中一個信源sw，將所產(chǎn)生的消息（2）廣播出去，若用戶Uj接受了該消息，并認為是從Ui發(fā)送出來的，則L攻擊成功。首先，L是想猜測Uj的密鑰（F0 j（x），…，F(xiàn)（w+1）j（x）），從而使得

現(xiàn)在來考慮L所擁有的信息，消息（1）被傳出后，根據(jù)所構(gòu)造的協(xié)議，L會計算

其中：λ=1，2，…，w。又因?qū)θ魏我粋€信源s′∈GF（q）而言，L中每一個Ut（1≤t≤k-1）均可以利用他自己的密鑰計算

綜合方程組（3）和方程組（4）中的w+2個等式，L也不能確定（A0，A1，…，Aw+1）。下面研究在整個方案中（A0，A1，…，Aw+1）所有可能的取法。方程組（3）與（4）要有多個公共解等價于至少存在一個（A0，A1，…，Aw+1）≠（0，0，…，0）滿足

對所有的s′∈GF（q）以及λ=1，2，…，w都成立?？紤]一個關(guān)于x，y的對稱多項式

其中：A是一個k×k階的對稱矩陣并且A≠0；再不妨假設w是一個奇數(shù)，令一個多項式

其中：Σsk1sk2…ski表示集合{ai，s1，…，sw}中所有可能的i個不同元素的乘積之和。定義A0=（ais1…sw-1sw）A，

A，通過對w運用歸納法，可以證得（A0，A1，…，Aw+1）滿足方程組（5）~（7），則對任意一個r∈GF（q），容易得到（rA0，rA1，…，rAw+1）也同樣滿足方程組（5）~（7）。由此說明在整個方案中KDC在選擇（A0，A1，…，Aw+1）時有q種等可能的取法，也就是說它在選擇初始密鑰（M（0x，y），…，Mw+（1x，y））時有q種等可能的取法?，F(xiàn)在設（A0，A1，…，Aw+1）滿足方程組（5）~（7），那么對于任何一個s′∈GF（q），并且s′≠ai和s′≠（s1，s2，…，sw），則有

因為g（s′）=（s′-a）i（s′-s1）…（s′-sw）≠0，所以有d=g（s′）M（ai，aj）≠0。這說明q個不同的（A0，A1，…，Aw+1）會相應地產(chǎn)生q個不同的d，也就是說等式（F0（ja）i+s′F（1ja）i+…+s′w+1F（w+1）（ja）i會有q個等可能的值，但是L只可能選擇其中一個，所以得證L進行替換攻擊的概率為，即：PS=；同理也可證得：L進行仿冒攻擊的概率為，即：PI=。最后綜合引理1、引理2，得證：所構(gòu)造的方案是一個無條件安全的多信源認證碼，它能夠同時認證w個信源；在任意k個人當中至多能夠防止k-1個人的聯(lián)合攻擊，并且攻擊成功的概率不會大于。

4 結(jié)語

在DMRA-code的基礎上，構(gòu)造了具有動態(tài)功能的多信源認證的模型，也就是將原來僅僅對一個信源的認證系統(tǒng)擴展到了同時對w個信源的認證。一方面，該模型的構(gòu)造在通信系統(tǒng)中更加符合實際情況，具有現(xiàn)實意義。另一方面，構(gòu)造的方案無條件安全，各種攻擊成功的概率與只認證一個信源時的情形類似，但相比之下雖更具實時性和有效性。

[1]DESMEDT Y，F(xiàn)RANKLE Y，YUNGM.Multi-Receiver/Multi-Sender Network Security：Efficient AuthentiCated Multicast/Feedback[J].Florence：IEEE Infocom，1992，3：2045-2054.

[2]SAFAVI-NAINI R，WANG H.New results on multi-receiver authentication codes[J].Advances in Crrptoligy-Eurocrypt LNCS，1998，1438 （98）：527-541.

[3]SAFAVI-NAINI R，WANG H.Broadcast authentication for group communication[J].Theoretical Computer Science，2001，269（1-2）：1-21.

[4]杜慶靈.多信源認證系統(tǒng)與構(gòu)造[D].鄭州：中國人民解放軍信息工程大學，2002.

[5]APARNA R，AMBERKER B B.Multi-sender multi-receiver authentication for dynamic secure group communication[J].IJCSNS International Journal of Computer Science and Network Security，2007，7（10）：310-315.

[6]APARNA R，AMBERKER B B.Dynamic authenticated secure group communication[J].Proceedings of World Academy of Science，Engineering And Technology，2007，25：1307-6884.

[7]APARNA R，AMBERKER B B.Authenticated Secure Group Communication using Broad-cast Encryption Key Computation[C]//LasVegas，NV：Fifth International Conference on Information Technology，2008，348-353.

（責任編輯：黨亞茹）

Construction of multiple authentication codes with dynamic senders based on symmetric polynomials over finite fields

CHEN Shang-di，CHANG Li-zhen
（College of science，CAUC，Tianjin 300300，China）

In a group communication system，the basic authentication systems refer to the multi-receiver authentication codes with dynamic senders（DMRA-code）.At present，many scholars have a lot of researches，in which the authentication of source state is restricted as only one.However，in the network communication，there are always scenarios in which multiple source states are required to be authenticated.Based on this problem，a multiple message authentication code with dynamic senders is constructed with symmetric polynomials.In addition，the probabilities of possible attacks are computed to ensure the scheme security.

authentication code；multiple message；dynamic；plynomial

TN918

A

1674-5590（2013）05-0060-05

2012-06-11；

2012-09-09

中央高?；究蒲袠I(yè)務費專項（ZXH2012K003）；中國民航大學科研基金項目（2012KYM01）

陳尚弟（1964—）男，山西應縣人，博士，中國民航大學理學院教授，主要研究方向為代數(shù)、圖論、密碼與編碼.