具有动态发送功能的多信源认证码的构造

陈尚弟，常丽珍

（中国民航大学理学院，天津300300）

具有动态发送功能的多信源认证码的构造

陈尚弟，常丽珍

（中国民航大学理学院，天津300300）

在一个群通信体系中，最基本并且最具有实际意义的认证系统是指关于动态发送者的多接收认证码（简称DMRA-code）。但目前，许多学者对其研究仅仅局限于对一个信源的认证。然而在网络通信中，常常会有多信源传播的场景。基于这个问题，利用多项式构造一个具有动态发送功能的多信源认证码，并且验证了该模型的合理性以及计算出了可能的攻击概率，从而保证了所构造的方案的安全性。

认证码；多信源；动态；多项式

随着计算机网络的不断发展，网络通信技术在现实社会中的各个领域均得到了广泛的应用，尤其是群通信技术越来越受到人们的青睐。对于安全的群通信体系，许多学者已经做过不少研究，提供了许多安全的认证方案。其中Desmedt，Frankel和Yung[1]给出了一种多对一（多接收或多发送）的认证方案，但此构造要求一个发送者（接收者）是提前固定的，在实际应用中不具有灵活性；后来，R.Safavi-Naini和Wang[2]进一步扩展了该思想，放宽了这种限制，引入了动态发送者（DMRA-codes）的概念，也就是说群通信中的任何一个成员都可能是发送者；接着，他们又给出了关于t个动态发送者（简称tDMRA-codes）的构造[3]，在该文献中将动态的发送者由一个扩展到了多个，从而发展了具有动态功能的认证码；另外，杜庆灵针对多对一（多接收或多发送）的多信源认证问题进行了研究[4]，促进了多信源认证的发展；近年来，R.Aparna与B.B.Amberker对于动态的群通信系统构造了一系列更为灵活和有效的模型[5-7]，极大地丰富和完善了群通信的认证。然而，在上述系统中，大多都是针对于一个信源的认证，对多信源认证的研究并不充分。可是在实际应用中，经常会有多个信源的传播。基于这个问题，利用多项式构造了一个无条件安全的具有动态功能的多信源认证码，同时计算出了可能的攻击概率。

1 预备知识

在一个DMRA-codes中，假设有n个参与者U1，U2，…，Un在一个公开的信道上通信，同时还有一个可信赖的密钥分发中心（KDC），KDC的任务就是通过安全信道给每一个用户分发密钥，它只在密钥分配阶段起作用，并不参与后来的通信。在该模型中消息的传送需要遵循下列协议：

1）密钥分配KDC秘密地给每一个参与者分配密钥，以及它们的身份信息；

2）广播对于每个发送者Ui（1≤i≤n），利用自己的密钥对一信源s进行编码产生一个认证消息并广播该认证消息；

3）验证其余每个参与者Uj（j≠i）当收到消息后，利用其分得的密钥对其进行身份验证和信息验证，判断其真实性。

对于这种动态的认证系统，存在两类攻击：一种是外部攻击，一种是内部攻击。内部攻击是指一些恶意的参与者联合起来利用获得的密钥和观察到的信息，对其他参与者进行攻击。因为内部参与者肯定比外部敌手拥有更多的信息量，所以攻击成功的可能性更大，因此一般只考虑内部攻击。

假设有k-1个恶意参与者UL={Ul1，Ul2，…，Ulk-1}，勾结起来针对另外一对参与者{Ui，Uj}进行仿冒攻击或者替换攻击。在仿冒攻击中，UL利用Ui的身份信息产生一个消息m并发送给Uj，若Uj接受m并且认为是由Ui所发出的，则表示攻击成功，用PI[m；i，j；UL]表示这种攻击成功的概率，对于整个系统而言，则有

这里{L，i，j}取遍了{1，2，…，n}中所有可能的k+1个元素。在替换攻击中，当观察到Ui发出一个有效的消息m后，UL构造了一个伪消息m′（m′≠m）发送给Uj，若Uj接受m′并且认为是从Ui所发出的，则表示攻击成功，用PS[m，m′；i，j；UL]来表示这种攻击成功的概率，对于整个系统而言，则有

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

2 Safavi-Naini的DMRA-code

回顾文献[2]中由R.Safavi-Naini和H.Wang给出的关于DMRA-code的构造方案。假设有n个参与者U1，U2，…，Un，每一个参与者Ui所得到密钥为由三个随机选择的系数为有限域GF（q）中的次数至多为k-1的多项式（F0（ix），F1（ix），F2（ix））组成，所得到的身份信息为有限域GF（q）中的元素ai，其中1≤i≤n。对于一个信源s∈S，参与者Ui利用其密钥进行加密，得到

然后将（s，ai，G（1x），G（2x））传播出去。其余参与者Uj（j≠i）收到信息后，利用自己的密钥（F0（jx），F1（jx），F2（jx））进行验证，计算两个等式

是否成立。若成立，则接受；否则，拒绝。在该文献中，已经证明出在任何k个参与者中，至多有k-1个参与者所进行的联合攻击成功的概率不会超过。

3 关于动态发送者的多信源认证码的构造

在第2部分的基础上，利用有限域上的多项式构造一个具有动态发送功能的多信源认证码。假设有n个用户U1，U2，…，Un，同时还有一个可信赖的密钥分发中心KDC，令S为信源集，且S⊆GF（q），（q≥|S|+ n），该构造方案共分3个阶段。

1）密钥分配KDC随机选择了n个不同的元素ai∈GF（q）S，分别给了每个用户Ui（1≤i≤n）作为其公开的身份信息；同时，KDC又选择了w+2个系数为GF（q）上的次数至多为k-1的对称多项式

其中Al（0≤l≤w+1）是一个对称矩阵。对于每一个i （1≤i≤n），KDC生成w+2个多项式

然后它将这w+2个多项式（F0 i（x），F1i（x），…，F（w+1）i（x））秘密地发送给Ui，并作为其密钥。

2）广播对需要认证的信源s∈S，用户Ui计算

然后对其余的用户广播（s，ai，G1（x），G2（x））。

3）验证当用户Uj（j≠i）收到信息（s，ai，G1（x），G2（x））后，用自己的密钥进行验证，若

则接受它，否则拒绝。

下面验证所构造方案的合理性及其安全性。

引理1在上述所构造的方案中，每一个密钥至多能够认证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），）发送出去，攻击者看到信息后，可以利用用户Uj的身份信息aj进行验证，通过计算如下等式

因为等号右边矩阵为Vandermonde矩阵，所以可得到唯一的解

令X=（1，x，…，xw+1），对于一个确定的值m=若有方程式

其中：XT为X的转置，则X的解至多有w+1个。那么攻击者完全可以选择另一个信源s′（s′≠sλ）来代替sλ发送给Uj，并且由上述验证得知：Uj一定会接受它并以为是从Ui发出的，说明此时攻击者攻击成功的概率为1，所构造的方案并不安全。反之，若Ui只发送出w个信源，由上述分析得知攻击者不可能得到唯一的解

那么不可能攻击成功，系统是安全的。综上，得证：所构造的方案中，每一个密钥至多能够认证w个信源。

引理2该方案至多能够防止k-1个用户的联合攻击。

证明假设有k个用户勾结者为L=（U1，U2，…，Uk），则L知道自己的密钥

而Al（0≤l≤w+1）是一个k×k阶的对称矩阵，下面只考虑l=0时的情形，其它情形类似。不妨假设

其中：1≤i≤k。现在考虑最高次项的系数，可以得到下列方程组

其中：δ′，δ″，…，δ（k）均是确定的值。因为上述方程组的系数矩阵为k×k阶的Vandermonde矩阵，所以可得到唯一的解：d1k，d2k，…，dkk；同理，通过计算其余次项的系数，也会得到唯一的解，这样A0就被确定了。同样的道理，A1，A2，…，Aw+1也会被唯一确定，那么整个系统的密钥就会被L确定，则它进行攻击的概率就为1。反之，如果有k-1个人联合攻击，得到的上述方程组的系数矩阵并非Vandermonde矩阵，所以它的解并不唯一，那么L确定不了系统的密钥，攻击概率必定小于1，说明系统是安全的。综上所述，得证：该方案至多能够防止k-1个用户的联合攻击。

证明根据引理1，已知上述所构造的方案是一个合理的具有动态功能的多信源认证码，它能同时认证w个信源。下面计算攻击成功的概率。在这里只考虑替换攻击，仿冒攻击类似可得证。

说明（k，n）型是指在任意k个人之中，至多有k-1个人进行联合攻击的概率不会超过。事实上，令k-1个联合攻击者为L=（U1，U2，…，Uk-1），假设用户Ui发送出认证消息

其中：G1（x），，λ=1，2，…，w同引理1。当L看到此消息后，想构造一个新的消息

也就是说，L想用另一个信源s′（s′≠sw）来替换其中一个信源sw，将所产生的消息（2）广播出去，若用户Uj接受了该消息，并认为是从Ui发送出来的，则L攻击成功。首先，L是想猜测Uj的密钥（F0 j（x），…，F（w+1）j（x）），从而使得

现在来考虑L所拥有的信息，消息（1）被传出后，根据所构造的协议，L会计算

其中：λ=1，2，…，w。又因对任何一个信源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都成立。考虑一个关于x，y的对称多项式

其中：A是一个k×k阶的对称矩阵并且A≠0；再不妨假设w是一个奇数，令一个多项式

其中：Σ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种等可能的取法。现在设（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）会相应地产生q个不同的d，也就是说等式（F0（ja）i+s′F（1ja）i+…+s′w+1F（w+1）（ja）i会有q个等可能的值，但是L只可能选择其中一个，所以得证L进行替换攻击的概率为，即：PS=；同理也可证得：L进行仿冒攻击的概率为，即：PI=。最后综合引理1、引理2，得证：所构造的方案是一个无条件安全的多信源认证码，它能够同时认证w个信源；在任意k个人当中至多能够防止k-1个人的联合攻击，并且攻击成功的概率不会大于。

4 结语

在DMRA-code的基础上，构造了具有动态功能的多信源认证的模型，也就是将原来仅仅对一个信源的认证系统扩展到了同时对w个信源的认证。一方面，该模型的构造在通信系统中更加符合实际情况，具有现实意义。另一方面，构造的方案无条件安全，各种攻击成功的概率与只认证一个信源时的情形类似，但相比之下虽更具实时性和有效性。

[1]DESMEDT Y，FRANKLE 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]杜庆灵.多信源认证系统与构造[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

中央高校基本科研业务费专项（ZXH2012K003）；中国民航大学科研基金项目（2012KYM01）

陈尚弟（1964—）男，山西应县人，博士，中国民航大学理学院教授，主要研究方向为代数、图论、密码与编码.