基于有限域上射影空间构造分裂认证码

陈尚弟，张小连

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

基于有限域上射影空间构造分裂认证码

陈尚弟，张小连

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

传统的认证码中，报文由信源和编码规则唯一确定，但现实情况中，信源在同一编码规则作用下能够产生不止一个报文。分裂认证码正是基于这种现状而产生。本研究的目的是构造新的分裂认证码。运用有限域上射影空间的子空间结构和相关计数定理，构造了两个分裂认证码，并计算其参数。当所有规则都按等概率分布选取时，计算了敌方的假冒攻击和替代攻击成功的概率。结果表明，所构造的码能有效地抵抗敌方的假冒和替代攻击。

有限域；射影空间；分裂认证码

1 预备知识

定义1 设S、E、M为3个非空有限集合。f：S× E→M为满足下列条件的映射。四元组（S，E，M；f）称为一个认证码[1]，如果：

1）f：S×E→M是满射；

2）对任意的m∈M，任意的e∈E，若存在一个s∈S满足f（s，e）=m，则这样的s由给定的m和e唯一确定。

分别称S、E、M为信源集合、编码规则集合和报文集合，f为编码映射。基数称为这个码的参数。

定义2 设（S，E，M；f）为一个认证码，若一个信源s∈S在相同的编码规则e∈E的作用下能够产生不止一个报文，即报文m∈M不是由信源s∈S和编码规则e∈E唯一确定的，则称该认证码是分裂的[2]。

此时报文m∈M是由m=e（s，r）计算而得，其中r是某个特定有限集合中的随机数。令对于某些r使得e（s，r）=m成立}，则分裂认证码中必有

定义3 在分裂认证码中，若对任意的信源s∈S和编码规则e∈E都有则称该认证码是c-分裂的[2]。

在分裂认证模型中包括3个参加方：发方、收方和敌方。发方与收方事先约定好编码规则e∈E，发方欲传送信源信息s∈S给收方。发方将信源s用编码规则e编译成报文e（s）∈M并随机地选取其中一个报文m∈e（s）将其发送给收方，收方收到报文m后利用编码规则e判定m是否合理。若合理则可由消息m得到信源s，若不合理，则拒绝消息m。敌方在发方未发送任何报文的前提下，通过信道发送一个他伪造的报文给收方，称为假冒攻击。若收方将其作为合理报文并接收，则称敌方假冒攻击成功。将敌方假冒攻击的最大概率记为PI。敌方在截获到报文m后，用另一报文m′代替原来的报文并发送给收方，称为替代攻击。若收方以m′为合法报文，且m与m′代表不同的信源，则称敌方替代攻击成功，记这种攻击成功的最大概率为PS。

认证码是用于在公用信道实现消息认证的编码办法，多年来，人们通过有限域上的典型群几何学构造了多种多样参数优良的认证码，如Chen在文献[3]中基于奇异辛空间构造了多重多接收认证码，在文献[4]中基于伪辛空间构造了带仲裁的认证码。又如Gao于文献[5]基于射影空间构造了A3-code。然而基于有限域上典型群的几何学上研究分裂认证码的文献寥寥无几。分裂认证码最先是由Simmons于文献[6]引入的。在分析带仲裁认证码参数和攻击概率方面，分裂认证码作用显著。特别地，Kurosawa和Obana[7]给出了一个分裂认证码和带仲裁的认证码之间的弱等价关系。王永传、杨义先在文献[8]中发现，分裂认证码与纠错码也有密切联系。另外，Huber[9]也刻画了分裂认证码的组合论界。进而，杜北梁和梁淼[2]创造性地将构造最优分裂码的问题转化为构造相应的带约束的部分平衡区组t-设计的问题，运用组合设计的思维方式拓宽了分裂认证码的构造。本文旨在探究基于有限域上典型群的几何学特别是射影空间经过创新性加工构造具有可行性的、参数较优的分裂认证码。

2 有限域的射影空间

由文献[10]得到以下内容。

定理1 在PG（n，Fq）中：

2）包含在给定m-flat的k-flat（0≤k≤m≤n）的数量为

3）包含在给定k-flat的m-flat（0≤k≤m≤n）的数量为

这里

是高斯系数，其中0≤m≤n为正整数，q为素数幂。

3 分裂认证码的构造

3.1 构造Ⅰ

3.1.1 构造方案

在PG（3，Fq）中固定一条直线L，令

给定编码规则e与信源s，取e上任意一点α。由信源s和点α两点唯一地确定一条直线，该直线是与L相交于一点的直线。由于α的任意性，c=q+1。3.1.2 认证码的参数

定理2 该认证码的参数为

证明1）直线L上有q+1个点，故信源的个数为

固定L上一点α，则在PG（3，Fq）中包含点α的直线的个数为

2）在射影空间PG（3，Fq）中直线总数为

从而与L相交于一点的直线有与L不相交的直线有

（q4+q3+2q2+q+1）-（q3+2q2+q）-1=q4即编码规则个数为

3）从上述编码规则个数计算过程可知，与L交于一点的直线条数为q3+2q2+q，即信息的个数为

3.1.3 欺骗攻击类型和攻击成功概率

定理3 该方案中欺骗攻击成功的概率为

证明1）假设m为报文，则m是与L交于一点的直线，且交点为信源s。对报文m有效的编码规则集合记为E（m），则即E（m）是与L不相交且与m只交于一点的直线的集合。由定理2可知，与m相交于一点的直线的个数为q3+2q2+ q，与m、L相交于同一点的直线的个数为q2+q-1，与m、L相交于不同两点的直线的个数为q2，从而则

2）设m、m′是同时对编码规则e有效的不同报文，令s、s′分别是m、m′对应的信源。不失一般性，设e与m相交于点A，与m′相交于点B，则同时对m、m′有效的编码规则e只能是直线AB，即因此替代攻击成功最大的情形是m、m′相交于一点P，编码规则是过点P与L不相交的直线。由于s、s′、P三点不共线，从而唯一地确定一个平面Π，则对m、m′同时有效的编码规则e为与平面Π只交于点P的直线。在PG（3，Fq）中除去平面Π的共有点的个数为q3，又任意q点共线，从而

3.2 构造Ⅱ

在PG（4，Fq）中固定一直线L，令

给定编码规则e与信源s，取e上两点α1、α2，信源s为α3。由于L与e不相交，从而L不包含在α1、α2、α3所生成的平面T上。由于在射影空间内，一个平面内的任意两条直线相交，从而不在T上的任意一点与T生成一个包含e和s的超平面。

不在T上的点共有

在一个包含e和s的超平面中，不包含在T上的点有

包含e和s的超平面中有一个超平面包含L。因此

定理4 该认证码的参数为

证明1）在直线L上有q+1个点，故信源的个数为

2）在射影空间PG（4，Fq）中直线总数为

又由于通过一固定点的直线的个数为

从而与L相交的直线有

编码规则是与L不相交的直线，因此编码规则的个数为

3）固定L上一点α，则包含α的超平面个数为

在PG（4，Fq）中，包含L的超平面的个数为

从而与L相交于点α的超平面的个数为q3。

由α的任意性可知

定理5 该方案中欺骗攻击成功的概率为

证明1）假设m为报文，对报文m有效的编码规则集合记为E（m），则E（m）中元素为超平面m中不过点s的直线。超平面m中直线总数为

超平面m中过点s的直线个数为

Construction splitting of authentication codes from projective space over finite field

CHEN Shang-di，ZHANG Xiao-lian
（College of Science，CAUC，Tianjin 300300，China）

In traditional authentication codes，messages are determined by source state and encoding rule.However，the source state can produce more than one messages under the same encoding rule in reality.Splitting authentication codes are produced in this situation.The main focus of this research is the construction of new splitting authentication codes.Based on subspace structures from projective space over finite fields and basic counting theories，two splitting authentication codes splitting are constructed，and their size parameters are computed. Assuming that the encoding rules are chosen according to a uniform probability distribution，the probabilities of a successful impersonation and a successful substitution by the opponent are computed.Results indicate that the newly constructed codes can effectively resist the enemy’s impersonation and substitution attack.

finite field；projective space；splitting authentication codes

O157

：A

：1674－5590（2015）06－0047－03

2014-09-12；

：2014-11-12

国家自然科学基金项目（61179026）；中国民航大学学生科技立项项目（152A035473026）

陈尚弟（1964—），男，山西应县人，教授，博士，研究方向为代数、图论、编码与密码.