基于有限域上的射影空间构造完善的A3码
2018-05-28陈尚弟梁俊英
陈尚弟，梁俊英
（中国民航大学理学院，天津 300300）
1 认证码及其研究状况
保密和认证是保障信息安全的两个重要手段。保密的目的是阻止秘密信息被敌手解密，该问题可通过密码技术来解决；认证的目的是保障信源的真实性和信息的完整性，数字签名和认证码是解决这一问题的有效方法。事实上，数字签名是计算安全的，而认证码是无条件安全的。因此，认证码在各种开放的通信系统中起着重要的作用。1974年，Gilbert等[1]首次提出认证码的概念，并基于射影几何构造了第一个认证码，这是认证码发展的一个里程碑。同时，Simmons[2]拓展了认证系统的信息论，引入了认证信道的概念。Simmons的认证模型（简称A码）包括信息的发送方和接收方，其被认为是相互可信、共享一个相同的秘密密钥。通过认证码的使用，能够保证所传送的信息免遭敌人的欺骗攻击。欺骗攻击的一种方式是敌方模仿发送方在通信信道中插入一个信息让收方接收，这种欺骗攻击称为敌方的模仿攻击；另一种方式是敌方截获发送方发送的一个消息后，将这个消息用另一个不同的消息替代，然后将替代后的消息插入信道让收方接收，这种攻击称为敌方的替代攻击。在这个模型中，由于发方和收方共享一个密钥，这就要求发方和收方必须是彼此绝对可信的。显然，这是一个不完全符合现实环境的模型。实际上，发送者完全有可能发送一个消息后，事后又否认发送过那个消息；同样，收方在接收到发方的消息后，也可能否认接收过这个消息。为解决由于收方和发方不信任而产生的争执，Simmons扩展了此模型，引入带仲裁的认证码的模型（简称A2码）。在这个模型中，除了发方和收方外，增加了一个第三方称为仲裁，并被认为是可信的，其知道收发双方的密钥信息，但其不参与整个通信过程，其任务是解决发方和收方之间的争执，阻止发方和收方之间的欺骗攻击。
下面给出A2码的精确定义：
定义 1令 S、ET、ER、M 是 4 个非空有限集，f：S ×ET→M，g：M × ER→S∪{拒绝}，称六元组（S，ET，ER，M；f，g）为一个A2码，需满足下列3个条件：
1）映射 f、g是满射；
2）对任意的 m∈M，et∈ET，如果存在 s∈S 使得f（s，et）=m，则s被m和et唯一决定；
3）当p（et，er）≠0，且f（s，et）=m时，必有g（m，er）=s；否则，g（m，er）∈{拒绝}。
其中，p（et，er）≠0指任何被et加密的信息s都能通过er的认证。
S、ET、ER和M分别称为源状态集、发送者的加密规则集、接收者的解密规则集和信息集；f和g分别称为加密函数和解密函数，而称为码的参数。
拥有仲裁的认证码可有效地抵抗来自外部敌人（不掌握系统的密钥信息）和内部人士（发送者和接收者，其掌握系统的部分密钥信息）的欺骗攻击。对于带有仲裁的认证码已有深入的研究和广泛的应用[2-12]。
拥有仲裁的认证码可分为两类：仲裁绝对可信的认证码的A2码和仲裁不可信的认证码的A3码。Johansson[13]定义的A3码就是能抵抗仲裁欺骗攻击的A2码。也就是说，在一个A3码中，发方、收方和仲裁方没有一方是可信的。
基于有限域上的射影空间，很多完善的A2认证码已经被构造，但是，还未发现完善的A3码构造。Desmedt等[14]通过增加一些额外的比特让参加方分享（如让发方和收方分享而不让仲裁分享）的方法来解决仲裁不可信的问题。Johansson[13]给出了带仲裁认证码受到各种攻击成功的概率的界，并基于有限域构造了一个完善的A3码。
2 A3码的模型
在一个A3码中，有3个参与方：一个发方T、一个收方R和一个仲裁A。他们中没有一个被认为可信，但都有其秘密密钥信息用于抵抗来自于系统的各种欺骗攻击。尽管仲裁可能干扰通信，但在仲裁阶段仍认为仲裁是可信的。另外，还有一个外部的攻击者O，其不掌握系统的任何密钥信息。
令S、ET、ER、EA和M分别表示源状态集、发送者的加密规则集、收方的解密规则集、仲裁的密钥集和信息集。类似于A2码，发送者的密钥et∈ET确定了加密函数，即
接收者的密钥er∈ER确定了解密函数，即
仲裁的密钥ea∈EA确定了一个子集，即
如果m∈M（ea），则仲裁断定m是发方发送的有效信息，这里M（ea）表示所有对于密钥ea有效的信息集合。
发送者T用其密钥信息et∈ET加密一个源状态s∈S成一个信息m，即m=f（s，et），并通过一个公开渠道将m发送给接收者R，而R用其密钥er验证信息m的真实性。当发送者T和接收者R发生争执时，仲裁A用其密钥信息ea解决T和R之间的纠纷。
对于任意m∈M，假定至少存在一个er∈ER和一个ea∈EA，使得m∈M（er）∩M（ea）；否则，这个信息m可从M中删去。给定接收者一个密钥er，仲裁一个密钥ea，对于任何信息m∈M（er）∩M（ea）（如果假定至少存在发方的一个密钥et∈ET（er）∩ET（ea），使得m∈M（et）；否则，这个信息可以从M（er）∩M（ea）中删去。
接收者和仲裁必须承认所有来自于发送者的合法信息，各参与方的密钥必须进行合适的选择。假设对于一个可能的密钥对（et，er），对任何一个s∈S被et加密后都能通过er的认证，也假定对一个可能的密钥对（et，ea），发送者根据 et生成信息 m，仲裁总能根据密钥ea确定m来自于发方。
A3码的运行分3个阶段：
1）密钥生成和密钥分配
这一阶段可通过一个诚实可信的权威机构（密钥分配中心KDC）来执行。权威机构选取一个有效的三元组（et，er，ea），并秘密地将 et、er和 ea分别发送给发方T、收方R和仲裁A。一个有效的三元组具有以下性质：如果f（s，et）=m，则g（m，er）=s，且m∈M（er）∩M（ea）。
2）广播
为了认证一个信源s∈S，发方T用所持有的密钥et将s加密成一个信息m=f（s，et），然后通过一个公开的信道将m发给收方R。
3）验证
收方R用持有的密钥er验证收到的信息m的真实性。如果g（m，er）∈S，则接受m为发方发送的真实信息，否则拒绝m。
4）仲裁
发方和收方之间可能发生争执。如果发方和收方发生争执，仲裁能够用他所持有的密钥ea判断m是否由发方生成。如果m∈M（ea），则仲裁判定m由发方生成；如果m∉M（ea），则仲裁判定m不是由发方生成。
由于在A3码中，仲裁也可能参与对系统的欺骗攻击，故此系统存在7种类型的攻击：
1）敌方的模仿攻击I
敌方在通信信道中插入一个消息m发给收方。如果m被收方接受，则敌方模仿攻击成功。
2）敌方的替换攻击S
敌方在截获到一个合法消息m后，用一个不同于m的消息m′替换m，并将m′发给收方。如果m′被收方接受，则敌方替换攻击成功。
3）发方的模仿攻击T
发方向收方发送一个假的消息m，这个消息不能由发方的加密密钥et生成。如果m被收方接受，则发方模仿攻击成功。
4）收方的模仿攻击R0
收方声称收到一个消息m。如果m对发方的密钥et有效，则收方模仿攻击成功。
5）收方的替换攻击R1
发方发送一个合法的消息m给收方，而收方却声称用其密钥er收到消息m′（m′≠m）。如果m′对发方的密钥et有效，则收方的替换攻击成功。
6）仲裁的模仿攻击A0
仲裁用其密钥ea将一个消息m插入通信信道发给收方。如果m被收方作为一个真实的消息接受，则仲裁的模仿攻击成功。
7）仲裁的替换攻击A1
仲裁观察到发方发送的一个消息m，用另一个不同于m的消息m′替换m并将其发送给收方。如果m′被收方作为一个真实的消息接受，则仲裁的替换攻击成功。
对于以上各种类型的攻击，用 PI、PS、PT、PR0、PR1、PA0和PA1分别表示各种类型欺骗攻击成功的最大概率。
定义2各种攻击成功的最大概率为
其中表示与发方的密钥et相关联的消息集合。进一步引入下列记号：
1）与接收者密钥er相关联的消息集合
2）加密产生消息m的发方的加密密钥集合
3）使m有效的接收者的密钥集合
4）与收方密钥er相关联的发方的加密密钥集合
5）与发方密钥et相关联的收方的密钥集合
6）与仲裁密钥ea相关联的收方的密钥集合
运用上述记号，可重新将定义2改写如下：
定义3在假定源状态和发方的加密密钥随机选取的条件下，各种欺骗攻击成功的最大概率为
运用式（8）～式（14）可方便地计算各类欺骗攻击成功的概率。
定理1对于任何A2码或A3码，下列参数的界成立
如果一个A3的参数使定理1中4个不等式成立，这样的A3码称为完善的A3码。当参数大小相同时，完善的A3码受到的欺骗攻击成功的最大概率最小，即完善的A3码安全水平最高；或在安全水平相同的情况下，完善的A3码对存储要求最小。
3 射影几何
本节简要介绍所用到的一些射影几何的知识。未加说明的符号参见文献[15]。
令n是一个正整数，q是一个素数方幂，Fq是q元有限域表示Fq上的n+1维行向量空间。的一维子空间称为点，二维子空间称为线，三维子空间称为面，n维子空间称为超平面。更一般地的一个r+1维子空间称为一个射影r-flat（0≤r≤n）。所有点的集合和所有的r-flat（0≤r≤n）以及连同定义在他们之间的关联关系称为有限域Fq上的n维射影空间，记为PG（n，Fq）。
定理2在 PG（n，Fq）中：
1）m-flats的个数为
2）包含在一个给定的m-flat中的k-flats的个数为
3）包含一个给定的k-flat的m-flats的个数为
称为高斯系数。
定理3在 PG（n，Fq）中：
1）通过任意两个不同的点有且仅有一条线；
2）任何3个不共线的点恰好在一个面上；
3）任何r+1个点，其中任何r个点不在任何一个（r-1）-flat中，恰好包含在一个 r-flat中（1≤ r≤ n）。而在任何一个r-flat（1≤r≤n）中存在r+1个点不包含在任何一个（r-1）-flat中。
4 构造
本节给出A3码的一个新构造。
令W是PG（4，q）中一个固定平面，L是W上一条固定的线。
源状态集为
是L上的点}
发送者的加密密钥集为
是一条线
接收者的密钥集为
中不在 W 中的点}
仲裁的密钥集为
是W中的点且ea∉L}
消息集为
定义加密映射为
定义解密映射为
g：M × ER→S∪{拒绝}
三元组（et，er，ea）是有效的当且仅当 er、ea包含在et中，且ea是W中一个点。换句话说，KDC秘密地且随机地选取一条线et作为发方的加密密钥，其中et与L不相交，但与W交于一点；然后在et中选择一个不在W中的点作为收方的密钥er；选择一个既在et又在W中的点ea作为仲裁的密钥。
定理4以上构造的码是一个合理的A3码，且
1）对任意的 s∈S，et∈ET，
2）对任意的m∈M，s∈m∩L是m包含的唯一的源状态，且有一个 et∈ET使得 m=
证明1）对任意s∈S，s是L中的一个点。对于任意et∈ET，et是一条线，其与W交于一个点，而这个点不在L上。显然，m=
2）对于 m∈M，令 s∈m∩L，则 s∈L，从而 s是一个源状态。令l是m和W的交线，则点s在l上。令et是一条不在W中的线，且与l交于一个不同于s的点，则et是一个加密规则且
假如s′是另一个包含在m中的源状态，则s、s′是L上两个不同的点，且都在m中，从而L包含在m中，这与矛盾。因此，s′=s，s是包含在 m 中的唯一源状态。
定理5所构造的A3码的参数是：
证明由于是L中点的数目，故
令B是任意一个不在W中的点，C是任一个不在L但在W中的点。由于对每个et∈ET满足所以 et可由 B、C 生成，即 et=
由于有Q4（0，1）-Q2（0，1）=q3（q+1）个点不在W中，有Q2（0，1）-Q1（0，1）=q2个点在W中而不在L中，所以
由于有Q4（0，1）-Q2（0，1）=q3（q+1）个点不在W中，所以
由于有q2+q+1个点在面W中，有q+1个点在线L中，所以
假定l是一条包含在W中的一条线且与L交于一点。在PG（4，q）中，包含l的面有Q4（1，2）=q2+q+1（含W）。在面W中，与L交于一点的线有q2+q条，因此
定理6假定所有源状态的选取是等可能的，所有的加密规则服从均匀分布，则所构造的A3码受到的各种欺骗攻击成功的最大概率分别是
证明1）对于任意的m∈M，m中除了属于W的点都可作为接收者的解密密钥，即则
2）如果则
如果则
如果则
敌人的最优攻击策略是选择m′使得其与m的交是一条线，且交线是一个加密规则，从而
3）对于给定的加密规则et，由于有q个点不在W中，所以从而
4）对于一个给定的er∈ER，ET（er）是过er而与平面W交于一个不在L上的点，故
对于m∈M，则et∈ET（er）∩ET（m）当且仅当et包含在m中而与L不交，则
5）收方收到消息m但却声称收到消息m′，其中m′包含的源状态s′不同于m包含的源状态s。而et∈ET（er）∩ET（m）∩ET（m′）仅当et过er且m∩m′=et。而m与m′至多交于一条线，于是
6）对于仲裁的一个密钥ea∈EA，接收者的每一个密钥都有可能与ea关联，故ER（ea）=ER。因此，仲裁对收方的攻击能力并不比敌方的攻击能力强，故
由定理1和定理6，可得下面的推论。
推论1所构造的码是一个完善的A3码。
5 仿真结果
在这一部分给出一个仿真例子：当n=4，q=23时，对敌方的模仿攻击效率进行了仿真。仿真结果表明，随着攻击强度的增强，实际攻击成功的概率越来越低于理论值，如图1所示。同时与Gao等[16]和Jahasson构造的A3码进行对比，本研究的构造有更好的优势，如表1所示。
图1 仿真结果Fig.1 Simulation result
表1 三种算法比较结果Tab.1 Comparison result
6 结语
研究主要基于有限域上的射影空间构造一个完善的A3码。Gao等[16]构造的认证码也是一个基于有限域上射影空间PG（n，Fq）构造的A3码，其构造是不完善的。Johansson基于有限域给出一个A3码的构造，尽管是完善的，但本研究的构造有两个概率更小，更具优势。
参考文献：
[1]GILBERT E N,WACWILLIAMS F J,SLOANE N J A.Codes which detectdecption[J].BellSystemTechnicalJournal,1974,53(3)：405-424.
[2]SIMMONS G J.Message Authentication with Arbitration of TransmitterReceiver Disputes[C]//AdvancesinCryptology-EUROCRYPT’87,LNCS 304,Berlin,Heidelberg：Springer-Verlag,1988：151-165.
[3]JOHANSSON T.Lower bounds on the probability of deception in authentication with arbitration[J].IEEE Transactions on Information Theory,1994,40(5)：1573-1585.
[4]KUROSAWA K,OBANA S.Combinatorial bounds for authentication codes with arbitration[J].Designs,Codes and Cryptography,2001,22(3)：265-281.
[5]CHEN SHANGDI,ZHAO DAWEI.Two constructions of optimal cartesian authentication codes from unitary geometry over finite fields[J].Acta Mathematicae Applicatae Sinica,Enghlish Series,2013,29(4)：829-836.
[6]CHEE Y M,ZHANG XIANDE,ZHANG HUI.Infinite families of optimal splitting authentication codes secure against spoofing attacks of higher order[J].Advances in Mathematics of Communication,2011,5(1)：59-68.
[7]BRICKELL E F,STINSON D R.Authentication Codes with Multiple Arbiters[C]//AdvancesinCryptology-EUROCRYPT188,LNCS 330,Berlin,Heidelberg：Springer-Verlag,1988：51-55.
[8]WANG Y,SAFAVI-NAINI R.A3-Codes under Collusion Attacks[C]//ASIACRYPT’99,LNCS1716,Berlin,Heidelberg：Springer-Verlag,1999：390-398.
[9]ZHOU ZHI.The constructions of A2-codes from conventional A-codes[J].Journal of Electronics&Information Technology,1997,19(4)：489-493.
[10]PEI DINGYI.Message Authentication Codes[M].Hefei：University of Science and Technology of China Press,2009：200-203.
[11]TOMPA M,WOLL H.How to Share a Secret with Cheaters[C]//Advances in Cryptology-CRYPT0 ’86,LNCS 263,Berlin,Heidelberg：Springer-Verlag,1987：261-265,.
[12]HANAOKA G,SHIKATA J,HANAOKA Y,et al.The Role of Arbiters in Asymmetric Authentication Schemes[C]//Information Security,LNCS 2851,Berlin,Heidelberg：Springer-Verlag,2003：428-441.
[13]JOHANSSON T.Further results on asymmetric authentication schemes[J].Information and Computation,1999,151(1/2)：100-133.
[14]DESMEDT Y,YUNG M.Arbitrated Unconditionally Secure Authentication can be Unconditionally Protected Against Arbiter’s Attacks[C]//Advances in Cryptology-CRYPTO’90,LNCS 537,Berlin,Heidelberg：Springer-Verlag,1991：177-188.
[15]WAN ZHEXIAN.Geometry of Classical Groups over Finite Fields[M].Beijing：Science Press,2002：61-72.
[16]GAO YOU,LIU YANQIN.The construction of A3-code from projective spaces over finite fields[J].WSEAS Transactions on Mathematics,2013,12(10)：1024-1033.
