陳尚弟，常麗珍

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

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

陳尚弟，常麗珍

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

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

認(rèn)證碼；多信源；動(dòng)態(tài)；多項(xiàng)式

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

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

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

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

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

3）驗(yàn)證其余每個(gè)參與者Uj（j≠i）當(dāng)收到消息后，利用其分得的密鑰對(duì)其進(jìn)行身份驗(yàn)證和信息驗(yàn)證，判斷其真實(shí)性。

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

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

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

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

2 Safavi-Naini的DMRA-code

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

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

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

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

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

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

其中Al（0≤l≤w+1）是一個(gè)對(duì)稱矩陣。對(duì)于每一個(gè)i （1≤i≤n），KDC生成w+2個(gè)多項(xiàng)式

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

2）廣播對(duì)需要認(rèn)證的信源s∈S，用戶Ui計(jì)算

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

3）驗(yàn)證當(dāng)用戶Uj（j≠i）收到信息（s，ai，G1（x），G2（x））后，用自己的密鑰進(jìn)行驗(yàn)證，若

則接受它，否則拒絕。

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

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

證明假設(shè)用戶Ui想要對(duì)Uj廣播w+1個(gè)信源：s1，s2，…，sw，sw+1，先進(jìn)行計(jì)算

然后將（ai，（s1，s2，…，sw+1），G（1x），G（2λ）（x））傳播出去，其中λ=1，2，…，w，w+1。因?yàn)橥ㄐ诺男诺啦⒉话踩?，所以在傳播過(guò)程中，完全有可能被攻擊者截獲，從而對(duì)Uj進(jìn)行替換攻擊。事實(shí)上，當(dāng)（ai，（s1，s2，…，sw+1），G（1x），）發(fā)送出去，攻擊者看到信息后，可以利用用戶Uj的身份信息aj進(jìn)行驗(yàn)證，通過(guò)計(jì)算如下等式

因?yàn)榈忍?hào)右邊矩陣為Vandermonde矩陣，所以可得到唯一的解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

[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]杜慶靈.多信源認(rèn)證系統(tǒng)與構(gòu)造[D].鄭州：中國(guó)人民解放軍信息工程大學(xué)，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.

（責(zé)任編輯：黨亞茹）

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è)務(wù)費(fèi)專項(xiàng)（ZXH2012K003）；中國(guó)民航大學(xué)科研基金項(xiàng)目（2012KYM01）

陳尚弟（1964—）男，山西應(yīng)縣人，博士，中國(guó)民航大學(xué)理學(xué)院教授，主要研究方向?yàn)榇鷶?shù)、圖論、密碼與編碼.