认证码的几种构建方法讲解

1、目录摘要 IAbstractI.I.1 前言 1.1.1 认证码的概念 1.1.2 认证码的研究现状 4.1.3 目前的一些问题和本文的主要工作 6.2 组合论中的一些基本知识 7.2.1 外差族( EDF) 7.2.2 外平衡不完全区组设计(EBIBD) 9.2.3 分裂平衡不完全区组设计( Splitting BIBD ) 1. 02.4 强限制部分平衡设计( RSPB)D 1. 13 分裂认证码的构造 1.2.3.1 分裂认证码 1.2.3.2 由 EDF构建最优分裂认证码 1.33.3 EBIBD 构建分裂认证码 1.43.4 Splitting BIBD 与分裂认证码 1. 53.5

2、 EDF，EBIBD，Splitting BIBD 的关系 1. 73.5.1 EDF 与 EBIBD1.73.5.2 EDF 与 Splitting BIBD 1.83.6 Splitting BIBD 构建的最优分裂认证码的进一步的讨论 .2 03.6.1 (v,2 2, )-Splitting BIBD 2.13.6.2 (v,2 3, )-Splitting BIBD 2.23.6.3 (v,2 4, )-Splitting BIBD 2.43.6.4 (v,2 5, )-Splitting BIBD 2.53.6.5 小结 2.7.4 带仲裁的认证码的构造 2.95 本文总结 3.2

3、.致 谢 错. 误！未定义书签。参考文献 3.4.认证码的几种构建方法摘要本文主要用组合的方法构造具有完美的界的分裂认证码 （A- 码）和带仲裁的 认证码（ A2-码）。首先介绍了几种组合设计： 外差族（EDF）、外平衡不完全区组设计 （EBIBD ）、 分裂平衡不完全区组设计（ Splitting BIBDs ）、强限制部分平衡设计（ RSPBD）。然后，说明外差族、外平衡不完全区组设计、分裂平衡不完全区组设计都可 以用来构建最优分裂认证码。并且说明了这三种组合设计之间的联系。1EDF 是 EBIBD 的一种特殊形式，故存在 EDF 即存在 EBIBD 。 2EDF 可以得到 Splitti

4、ng BIBD 。讨论了 Splitting BIBD 的存在性，并且用它实际构作了一些最优分裂认证码。最后， 本文讨论了认证码的推广模型：带仲裁的认证码。 并由最优强限制部 分平衡设计实际构作了一些最优带仲裁的认证码。关键词 组合设计 差族 区组设计 认证码 仲裁Some Method to Construct Authentication CodesAbstractThis paper constructs optimal splitting authentication codes (A-codes) and 2authentication codes with arbitration

5、(A -codes) by using combinatorial designs.First, we introduce some types of combinatorial designs, which we call external difference families (EDF), external BIBDs (EBIBD), Splitting BIBDs and RSPBD. And some relations of these designs.Then, we show that splitting authentication codes can be constru

6、cted by EDF, EBIBD, Splitting BIBDs and that some relations of these designs.1. An EDF is a special type of EBIBD, so if we have an EDF, we have an EBIBD.2. EDF can imply a splitting BIBD.Also we discuss the existence condition of some splitting BIBDs, and construct optimal splitting A-codes from th

7、ese splitting BIBDs.Finally, we discuss authentication codes with arbitration and construct optimal authentication codes with arbitration by ORSPBD.Keywords Combinatorial design; Difference family; Blocks Design; Authentication code; ArbitrationII1 前言 编码理论作为一门年轻的学科，却已经在国防、军事、通讯、经济等很多领 域 有 了 较 为 广 泛

8、的 应 用 。 C.E.Shannon 的 论 文 “ Mathematical theory of communication” 1 标志着编码理论的开端。 现在，随着计算机技术的迅速发展， 认证理论作为编码理论的一个重要分支， 已经在信息安全领域展现出其独有的魅 力。编码理论主要讨论的是信源编码和信道编码。在信道编码理论的研究中， 又 有两大主流，一是不断提出新的方法， 改进构造出性能更好的码； 二是研究在引 入某种代数结构后的码的界。 本文所说的认证码 (Authentication Code)以及认证理 论，也是从这两条主流出发，加以研究的。一方面，采用组合的方法得到了认证 码，另一

9、方面 ，则 研 究该认证码的界，这 里主要考虑的是最大 伪造 攻击 ( Impersonat ion Attack )概率的下界和最大替换攻击 ( Substituti on Attack ) 概率的下 界。就当前而言，处理传输信息的认证，主要有以下三种形式：无条件安全认证 码、信息认证码 (MAC)2 、以及数字签名。 信息认证码和数字签名分别对应一种 对称加密技术和不对称加密技术， 其优点是密钥的可重复利用性大大降低了网络 数据流量， 但是随着计算机计算能力的不断升级， 对称加密和不对称加密的安全 性在不断遭受质疑， 一个个加密标准被证明无法面对越来越强大的信息攻击。 无 条件安全认证码作

10、为唯一一种可以应对拥有无限计算能力攻击的认证方法， 研究 其性质以及构造方法，具有很大理论意义与实际意义。习惯上， 我们简称无条件 安全认证码为认证码。本文讲的认证码使用的就是这种认证方法。1.1 认证码的概念认证码起源于通信编码理论， 在保护数据安全传输方面有着不可替代的研究 意义。当今的社会是信息化的社会，未来的竞争，也将朝着电子信息对抗的方向 发展。随着世界政治经济全球化、多极化浪潮的推进，电子商务、电子政务、网 上会议等，给人们的生活、 工作带来了巨大的变革。我们已能将绝密信息锁于密 码箱中，但如何在硬件条件无法满足需要的信息传递通道上， 安全地传递机密信 息，验证信息来源，是我们最为

11、关心的问题。信息的安全性主要有两个方面，即 信息的保密和认证。保密是指通过数据加密，防止对手破译系统中的机密信息。 认证的目的有两个：一是验证信息的发送者是真正的，而不是冒充的， 二是验证 信息的完整性，在传送或存储过程中未被窜改、 重放或延迟等。认证码理论所提 供的数学模型，正是为处理此类问题应运而生的。认证码最早的由Gilbert ，MacWilliams 和 Sloane于 1974年提出的 3 。认证理论的数学模型则是由 Simmons 在 80 年代初期建立起来的 4,5 。下面给出认证码( A 码)的定义。定义 1.1 设S，E，M 是非空有限集， f :S E M 是一个映射，则

12、称(S, E,M ,f) 为一个认证码，如果满足(1) f :S E M 是一个满射；(2) f (s1,e) f (s2,e)，对 s1 s2 S， e E 。其中 S称为信源集合， E 称为密钥集合， M 称为消息集合， f 称为认证函数。 定义 e(s) m:m f (s, e) ， (e)e(s)。|S| u，|E | b，|M | v称为该认sS图1 1认证码模型中涉及三个参与者：发送者 T，接收者 R，敌手O 。发送者 T通 过一个不安全的信息通道(公共信道)把信息发送给接收者 R，发送者 T和接收 者 R 是相互信任的，他们共享一个编码规则(密钥) e E ，如果发送者 T 需要

13、 发送一个信源(明文) s S，则通过密钥 e，加密成敌手 O 无法识别的消息 m f(e,s) M ，然后发送消息 m给接收者 R，接收者 R根据密钥 e验证消息 m 的合法性(接受 m并解密 s或者拒绝 m )。一般来说消息集合 M 会比信源集合 S 大的多。验证接受 m并解码得 s拒绝 m信源s 发送者 T 编码得 m 接收者 R 公共信道 ee编码规则 e图1 2而敌手 O可以介入此公共信道， 他掌握密钥集合 E中所有的密钥， 但他不知 道发送者和接收者使用的是具体的哪一个密钥。 敌手以伪造信息和替换消息两种方式进行破坏，即伪造攻击(模仿攻击)和替换攻击，在伪造攻击中，敌手O 在公共信

14、道中插入伪造消息 m发送给接收者 R，如果接收者 R将m 当作合法消息接受，则攻击成功，伪造攻击成功的概率记为 PI 。则(1-1)maxmMPIPr(R接受 m) max Pr(m (e)编码规则 e图1 3在替换攻击中，敌手 O在公共信道中截获到发送者 T 发送的一个消息 m 后， 用伪造的消息 m?替换 m发送给接收者 R，如果接收者 R将m?当作合法消息接受， 则攻击成功，替换攻击成功的概率记为 PS 。PSPr(T发送m) max Pr(R接受 m?|R接受m)Pr(T发送m) max Pr(m e( s),m? e( s?), s s?|m (e) (1-2) m? Mm编码规则

15、e图1 4m m? m M一个认证码的最大的成功伪造攻击和替换攻击的概率体现了该码应对强大 信息攻击的能力。 因此，为了构造性质更好的认证码，研究最大的成功伪造攻击 和替换攻击的概率的下界是十分有意义的，它处于认证码研究领域的核心地位， 所有其他问题都是围绕着它逐步展开的。1988年 Simmons发展了认证码的模型，如果发送者 T和接收者 R也是可以 相互欺骗的， 发送者发出消息后可以否认， 接收者可以说收到了一条由发送者发 送的消息(事实上根本不存在) 。从而引入了第四方：仲裁者，并假设仲裁者是 可信的，他可以对发送者和接收者产生的矛盾纠纷进行仲裁， 这种认证码模型被 称为带仲裁的认证码(

16、 A2 码)。定义为 定 义 1.2 设 S ， ET ， ER ， M 是 非 空 有 限 集 ， f :S ET M ， g:M ER S 拒绝 是两个映射，则称 (S, ET , ER , M , f , g)为一个带仲裁的认 证码，如果满足(1) f :S ET M ， g:M ER S 拒绝是满射；(2) f (s1,eT ) f (s2,eT ) ，对 s1 s2 S ， eT ET ；(3) g(m,eR) s，如果 f(s,eT) m且 P(eT,eR) 0，否则 g(m,eR) 拒绝 。 其中 S称为信源集合， ET 称为发送密钥(编码规则) 集合， E R称为接收密钥 (解

17、 码规则)集合，M 称为消息集合， f 称为编码函数， g称为解码函数。 | S |，| ET |， |ER |， |M |称为该认证码的参数。1.2 认证码的研究现状Simmons 的认证理论给出了在 |S| u，|E | b，|M | v确定且编码规则概 率空间服从均匀分布时的最大伪造概率下界 PI u/v(参见4，5，6)，此后的 许多文献 7 ，8，9， 10，11都以此为依据。认证理论是一门涉及代数编码理论、纠错码理论、组合设计、密码学、仿射 几何、有限群、 代数几何的交叉热点学科下面， 对国际国内已经有研究成果给出 综述。对于任意一个 |S| u，|M | v认证码，PI u/v

18、，PS (u 1)/(v 1) (1-3)1984 年， Simmoms4,5发现，对于任何一个 | S| u ， |M | v 的认证码，PI u / v等号成立，当且仅当e E|m (e) pE (e) u/v之后 Massey 和 Stinson10分别在 1986 年和 1988 年发现了对于任何一个|S| u ， |M | v 的认证码， PS (u 1)/(v 1)等号成立，当且仅当e E|mm? (e) pE (e)pS (e (m) u 1e E|m (e) pE(e)pS(e 1(m) v 1对于 M 中的每一对 m m? 都成立。Simmons和 Brickell 等人，从

19、信息论的角度，于 1984年分别证明了 PI 和PS 下界的另一个估计，即著名的 Simmons界10, 4PI 2 I(M;E)，PS 2 H(E|M) ，|S| u (1-4) n其中， H ( X )表示随机变量 X 的熵 H(X)p(xi)log p(xi)，H(X |Y)表i1示条件熵 H(X |Y)p( x, y) log p(x|y)，而 I (X;Y)表示随机变量 X 和Y的交x,y互信息。Simmons界，让我们能更好地理解认证码保护数据的机制。从中可以看出，为了更好地保护数据使其不被伪造， (即，使得成功伪造信息的概率 PI 尽可能的 小)我们不得不泄露关于编码规则的许多信

20、息；然而，另一方面，为了更好的保 护数据不被替换， 编码规则的不确定性需要尽可能的大也就是说， 我们不能把所 有的关于编码规则的熵都花费在保护数据不被伪造上， 同时需要用一定量的编码 规则的不确定性来减少替换攻击成功的概率。 于是，数学家们做了许多的研究工 作以调和这对矛盾，并且构造出了许多性质很好的认证码。1985 年 Gabidulin12 利用秩距离码和线性化多项式构造了认证码。 C 是有 限域 GF (q N )上的 n, k , d 最大秩距离码， |S| qN，|M | (qN)k 1，|E | q2Nk， PI PS 1/qNk 。认证码与组合设计有着密切的联系， Brickel

21、l 和 Stinson 等人，将特定参数的 认证码与特定的组合设计一一对应起来。包括，横截设计、正交区组、平衡不完 全区组设计等。1992年，Brickell 和 Stinson13等人第一次将认证码与平衡不完全区组设计 联系在了一起，并且发现 PI u/v ，PS (u 1)/(v 1) 时，b u(u 1)/c(c 1)等 号取到，当且仅当编码规则矩阵为一个 (v,u,1) BIBD 且信源和编码规则都是等 概分布。从此组合设计方法，开始引入到认证码的研究之中。1993年，Stinson10进一步得出，对于任何一个 |S| u ，|M | v 的认证码， 若 PI PS u/v 1/l ，

22、有(i)b l 2等号取到，当且仅当认证矩阵是一个正交阵 OA(l,u,1) 且认证规则是 等概率的。(ii) b u(l 1) 1等号取到，当且仅当认证矩阵是一个正交阵 OA(l,u, ) 且认 证规则是等概率的，其中， (u(l 1) 1)/l 2 。Stinson 还对几类特殊的认证码，对称认证码进行了一系列研究 14。15用正交排列的方法来构造最优认证码。其中 |S| n ，|E| n2 1， PI PS 1/n 。说明一个认证码，若编码规则空间服从均匀分布， PI PS 1/l ，则它是一 个正交排列 OA(n,k, ) ；反之，若存在一个正交排列 OA(n,k, ) ，则可以构造一

23、 个具有 k 个信源， n 2个编码规则，信源和编码规则等概分布的认证码。继 Stinson 等人在仿射空间、射影空间中对认证码的组合特征的研究之后， 万哲先、冯荣权 16 ， 17，18， 19，20，21， 22利用有限域上对称阵和酉阵构造 认证码，游宏、南基洙 23，24，25 利用有限域上矩阵的标准型去构造认证码， 还有26，27，28，29，30，31等，人们开始把问题延伸到比仿射空问稍复杂一 些的辛空间 V2 (Fq ) 中来构造系统认证码，并且成功构造了系统认证码，其参数 为1 2i 1 2i(q2i 1)(q2i 1)c 1 ， b q ，v 1 q (1-5) (qi 1)(

24、qi 1)i 1 i 1 并且给出了编码规则空间服从均匀分布时， 成功伪造攻击概率和成功替换攻击概 率分别为PI 1/q2 m 1，PS 1/q。(1-6)以及参数为c q2 3，b (q 1)q2 3， v q2 2 (1-7) 并且给出了编码规则空问服从均匀分布时， 成功伪造攻击概率和成功替换攻击概 率，分别为PI 1/q， PS 1/(q 1)。(1-8)的系统认证码。1994 年，T. Johansson，G. Kabatianskii 和 B. Smeets等人32 ，利用代数几何 的手法建立了认证码理论与纠错码理论的内在联系：在给定PI ， PS和编码规则数的条件下， 构造一个具有

25、最大信源集的认证码，等价于，在给定最小距离条件 下，构造一个具有最大基数和码长的纠错码。即，假设存在一个参数为 (n,M ,d) 的纠错码，使得如果 C C ，那么对干所有 Fq有C 1 C ，那么就存在一个 对应参数为|S| Mq 1，|E| nq，PI 1/q， PS 1 d/n (1-9) 的认证码。 1996年， G.Kabatianskii 等人32 ，进一步发展了这一结果。1.3 目前的一些问题和本文的主要工作前面所讲的很多研究认证码的方法， 都是从理论上来讲述或者证明用某些方 法可以得到某些满足条件的最优认证码， 却很少用这些方法真正去构作实际的认 证码。主要是由于复杂繁多的数据

26、中去真正筛找出符合条件的部分非常困难， 仅 靠人工计算几乎无法完成， 用计算机编程解决也不容易， 取决于程序和计算机的 能力。而另一方面，一些实际使用认证码的编码人员往往花很多时间找到了一个认 证码，却不能从原理上认识到他得到的码本质上来说和数学上的某种结论是完全 吻合的，这样就不能举一反三来得到其他的码。6本文首先介绍了用组合的方法可以构作最优分裂认证码， 并且由此通过计算 来实际构造出一些符合条件的具有信息论意义上完美界的认证码。 从而对以上问 题作出了一个较好的解决。使用的方法是三种的组合设计：外差族( EDF )、外平衡不完全区组设计 (EBIBD )、分裂平衡不完全区组设计( Spl

27、itting BIBDs )。本文将用它们来得到 同时达到欺骗概率的下界和密钥大小的下界 4,33 且有完美安全性的最优分裂认 证码。认证码模型中，如果消息不是由信源(明文)和密钥惟一确定的，这样的认 证码就称为分裂的，这个概念对于带仲裁的认证码(见 34，35，36，37，7，38， 39)模型来说是非常重要的。本文接下来用另一种组合设计：强限制部分平衡 设计( RSPBD)来构建最优带仲裁的认证码。2 组合论中的一些基本知识 这部分内容将介绍几种组合设计：外差族( EDF)和外平衡不完全区组设计 ( EBIBD )，分裂平衡不完全区组设计( Splitting BIBD )，强限制部分平衡

28、设计 (RSPBD)。2.1 外差族( EDF)在介绍 EDF 之前，先给出差集与差族的定义。定义 2.1 40 设(X, )是一个 v阶Abel群， X 的子集 D称为一个 (v,c, ) 差集， 如果|D | c且x y:x,y D,x y (X 0) 。 (2-1) 例 2.1 D 0,1,3 是群 (Z7, )的一个 (7,3,1) 差集。事实上在 mod7 的前提下， 1 0 1，3 0 3，3 1 2，0 1 6，0 3 4，1 3 5。见表 2-1， Z7 0 的每个元素只出现一次。表 2-10130-1316-2345-定 义 2.2 40 设 (X, ) 是一个 v 阶 Ab

29、el 群， X 上的 u 个子 集组 成的 集合 D1, ,Du称为 X的一个 (v,c, )u 差族，如果 |D1 |Du | c且x y:x,y Di,x y (X 0) 。 (2-2) i例 2.2 D1 0,1 ，D2 0,2 ，D3 0,3 ，D4 0,4 是群(Z9, )的一个 (9,2,1)4 差族。见表 2-2， Z9 0 的每个元素在对角子矩阵中只出现一次。表 2-2010203040-118-0-227-0-336-0-445-定义 2.3 设(X, )是一个 v阶 Abel群， X 上的u个子集组成的集合 D1, ,Du称 为 X的一个 (v,c, )u EDF (外差族

30、)，如果| D1 |Du | c且Di Dj(X 0) ， (2-3)ij其中 Di D j表示重集 x y:x Di,y Dj 。例 2.3 D1 0,1,2 ，D2 3,6,9 是群 (Z19, )的一个 (19,3,1)2 EDF 。见表 2-3， Z 19 0 的每个元素在非对角子矩阵中只出现一次。表 2-3012369036912582147316171861314159101112现在给出 EDF 的两个基本性质。首先，易见如果存在一个 (v,c, )u EDF ， 则(v 1) l(l c) c2u(u 1) ，(2-4)其中 l cu 。定理 2.1 在群 X 上的(v,c,

31、)u EDF (D1, , Du )中，对于 a X ，0a0Na |x:x Di,x a Dj,i j | 。 (2-5) a0证 显见 N0 0 ，对于任意 a 0，由定义可知|( x,y): x y a,x Di,y Dj,i j |x:x Di,x a Dj,i j | Na令 y x a 2.2 外平衡不完全区组设计( EBIBD)这里先给出平衡不完全区组设计( BIBD )的定义。定义 2.440 (v,b,r,l, ) BIBD 是一个二元组 (X,B)，其中 X为 v称为点的元素 组成的集合， B B1, ,Bb为 X的b个l 子集的集合，称为区组， X 中每一个 元素恰好包含

32、在 r 个区组中， X 中每一对不同元素恰好包含在 个区组中。如果 v b (等价地，若 r l )，则 BIBD 称为对称的，记作 (v,l, ) SBIBD 。现在定义外平衡不完全区组设计( EBIBD )。定义 2.5 (v,l, )c EBIBD 是一个二元组 (X ,B) ，其中 l cu，u 2为整数，且 满足以下特征：1. |X | |B | v；2. 任意一个 B B均可表示为 u 个互不相交的子区组的并： B B1Bu ，其中|B1 |Bu | c，B X (对任意一个 B B，|B| l )；3. 对每一个 i ，1 i u ，重集的并 Bi cX ；BB是群 (Z9, )

33、的一个 (9,4,1)2 EBIBD 。检验条件 4，任意两个区组， 例如 B3和B7， B13 B27 2,3 8,1，B23 B17 4,6 6,7 6， |Bi3 B7j | 1，满足ij条件 4。EBIBD 的各个参数不是相互独立的，事实上有以下结果。 引理 2.2 每个元素 x都包含在 l 个区组中。证 假设 x包含在 r 个区组中，用两种方法计算 (B,x)的点的个数， x B，其中 B 是一个区组。得到 vl vr (因为 |X | |B | v ， |B | l )，即 r l 。 定理 2.3 在 (v,l, )c EBIBD 中，(v 1) l(l c) 。 (2-6) 证

34、 任意给一个区组 A，用两种方法计算 ( B, x)的点的个数 N，其中 B A是一个 区组， x Ai 且 x Bj ， i j 。首先，共有 v 1个这样的区组 B ，对每一个 B A ，根据上面的特征 4 可以 得到 x 的个数为 ，所以 N (v 1)。接着假设 x Ai ，由引理 2.2，x都包含在l个区组中，再由特征 3满足x Bj 的区组 B的个数为 l c，其中 i j ，所以 N l(l c)。所以 (v 1) l(l c) 命题 2.4 在(v,l, )c EBIBD 中，不存在两个区组 A和B，使得 Ai Bi，1 i u。 证 假设 Ai Bi，1 i u ，根据上面的

35、特征 4 可以得到0，由定理 2.3可以得到 l c，即u 1，这与 u 2矛盾。 2.3 分裂平衡不完全区组设计( Splitting BIBD )这里给出分裂平衡不完全区组设计( Splitting BIBD )的定义。定义 2.6 一个(v,b,l cu, ) Splitting BIBD 是一个二元组 (V ,B) ，满足以下条件， 其中 Bi B 称为区组并且 Bi V 。1. |V | v，|B | b；2. 任意一个 Bi B 均可表示为 u个互不相交的子区组的并： Bi Bi,1Bi,u ，其中| Bi ,1 |Bi,u | c，|Bi| l cu；3. 对任意 x,y V(x

36、 y) ，存在恰好 个区组 Bi Bi,1Bi,u ，使得x Bi,j,y Bi,k, j k。例 2.5 取V 1,2,3,4,5,6,7,8,9 ，B1 1,3,6,7, 4,5,8,9 ，10B2 1,2,8,9, 4,5,6,7 ，B3 1,5,6,8, 2,3,7,9 ，B4 1,3,5,9, 2,4,7,8 ，B5 1,3,4,8, 2,5,6,9 ，B6 1,4,7,9, 2,3,6,8 ，B7 1,2,5,7, 3,4,6,9 ，B8 1,2,4,6, 3,5,7,8 ，B9 2,3,4,5, 6,7,8,9 。是一个 (9,2 4,4) Splitting BIBD ，检验条

37、件 3，任意 x,y V(x y) ，例如，取 x 2， y 7，则 B2， B6，B8， B9满足条件 3。2.4 强限制部分平衡设计( RSPB)D这里先介绍限制部分平衡设计( RPBD)的定义。定义 2.7 一个限制部分平衡 t 设计 RPBDt (v,b,l cu; ,0) 是一个二元组 (V ,B) ，满足以下条件，其中 Bi B称为区组并且 Bi V 。1. |V | v，|B | b；2. 任意一个 B B均可表示为 u 个互不相交的子区组的并： B B1Bu ，其中 |B1 |Bu | c ， |B| l cu ；3. 对V 的任意的 t子集v1,v2, , vt ，或者存在恰

38、好 个区组 B B1Bu，使得 v1 Bi1，v2 Bi2 ， vt Bit ,(其中 ij 两两不同， j 1,2, ,t )，或者不 出现在任何区组中。下面介绍强限制部分平衡设计( RSPBD)的定义。定义 2.8 如果一个限制部分平衡 t 设计 RPBDt (v,b,l cu; ,0) 同时也是一个 限制部分平衡 s 设计 RPBDs (v,b,l cu; s,0) ，其中 0 s t ，则称强限制部 分平衡 t 设计，记作 RSPBDt (v,b,l cu; ,0) 。易见一个强限制部分平衡 t 设计 RSPBDt (v,b,l cu; ,0) 一定是一个 1 设计，其中 1 rv ，

39、为包含一个不动点的区组数。一个强限制部分平衡t 设计RSPBDt (v,b,l cu; ,0) 称为最优设计如果 b 是所有 RSPBDt (v,b,l cu; ,0) 中的区组数的最大值 (或者说， rv是所有 RSPBDt (v,b,l cu; ,0) 中包含一个不 动点的区组数的最大值) 。这里将一个最优强限制部分平衡 2 设计简记为 ORSPBD(v,l cu, ) 。例 2.6 取V Z15 ，11 0,1, 7,8 , 2,3,7,8 , 4,5,6,7 , 0,1, 9,10 , 2,3, 9,10 , 4,5, 8,9 , 0,1, 11,12 , 2,3, 11,12 , 4

40、,5,10,11 , 0,1, 13,14 , 2,3, 13,14 , 4,5,12,13 , 6,7, 8,9 , 6,10, 11,14 , 6,14, 12,13 。为一个 ORSPBD(15,2 2,1) ，其中 rv 4，b 15达到了最大值。3 分裂认证码的构造这部分将介绍最优分裂认证码( A- 码)的构造。3.1 分裂认证码在认证码(A-码)模型中，发送者 T 与接收者 R 共享一个公共的编码规则 (密 钥) e，密钥 e符合某个指定的概率分布。给出一个信源(明文)s，T 计算出消息 m e(s)并将 m传送给 R， R根据e来接受或拒绝 m。可能有不止一条消息可以传递某一信源

41、 s ，这就称为分裂的。 在这种情况下， 消息 m由m e(s, r )算出，其中 r是某个特定有限集中的随机数，如果定义e(s) m: 对某些r使e(s,r) m则分裂即 |e(s) | 1。注意到如果 s s?，则 e(s) e(s?) ，否则解码将变得不可能。记 S s ， M m ， E e ， (e)e(s) 。sS如果 m (e) ，则称 e承担 m 。在伪造攻击中，对手O传送一个消息 m给接收者，如果 m (e)则O成功了。 伪造攻击成功概率 PI 定义为PI max Pr(m (e) ， (3-1) 其中概率从密钥集合 E 上计算出来。在替换攻击中，对手 O收到从 T 发出的消

42、息 m ，然后用另一条消息 m?替换 m，如果 m e(s)且m? e(s?) ，其中 s s?，则O成功了。换言之，接收者把 m?当 作从信源发出的合法消息接受了。替换攻击成功的概率定义为PSPr(T发送m) max Pr(m e( s),m? e(s?), s s?|m (e) ， (3-2)m? Mm其中概率从密钥集合 E上计算出来。 对于(分裂) A-码中攻击成功的概率和密钥 个数的界，有以下已知结论：12命题 3.18 PI min | (e)| 。I e E |M |命题 3.28，41 PS min | (e)| maxs S |e(s)|。e E |M | 1 1命题 3.34

43、，33 |E | 1 。PIPS定义 3.1 称分裂 A- 码为 c 分裂的如果|e(s)| c 对任意 e E 和任意 s S。设|M | v ，|S| u ，| (e)| l( cu),S s1, su ,1e 1(m) s如果 m e(s,r) 对某些 r则命题 3.1 和命题 3.2 即(3-3)(3-4)A-码具有(3-5)PI c|S|， PS c(|S| 1)。|M | S |M | 1 对一个 c 分裂 A-码，从公式 (3-3) 可以得到以下推论。推论 3.6 在一个 c 分裂 A-码中，PI l /v， PS (l c)/(v 1)。最后，如果对手 O没有关于信源 s得到的

44、消息 m 的任何信息，则 完美安全性。形式上Pr(S s|M m) Pr(S s)对所有的 s S及 m M 。3.2 由 EDF构建最优分裂认证码下面看到最优分裂 A-码可以由 (v,c, )u EDF 构建。定理 3.4 设存在一个 Abel加群 (X, )上的(v,c,1)u EDF D1, ,Du ，则存在一 个符合命题 3.1，3.2和 3.3的具有完美安全性的分裂 A-码，使得|E | |M | v，|S| u，|e(s)| c， e,s。证 考虑分裂 A-码，E M X ，S 1, ,u ，e(i) e x:x Di 对于所有 e X 和 i S ，有|E | |M | |X |

45、 v c2u(u 1) 1 (公式(2-4)，|e(i)| |Di | c，13| (e)| |e(i) | uc ， e E 。iS设 E 和 S 是均匀分布的，这个分裂 A- 码具有完美安全性。 因为 m e x和e在 X 上均匀分布，计算 PI ，(3-6)PImax Pr( m (e) maxn M |e E:m (e) | uc。n M |E | v|E|(3-7)因为 |M | v，在命题 3.1 中等式成立。接下来计算 PS，设 m,m? M ， m m?，首先显见Pr(m e(i),m? e(j),i j |m (e) |e E:m e(i),m? e(j),i j|e E :

46、m (e) |e E:m e Di,m? e Dj,i j | 1 uc|e E:m (e) |因为 m m?作为差在 (Di Dj) 中只出现一次。另一方面，对于任意 e E ij，有所以| (e)| max|e(i)| uc c c(u 1) ，|M | 1 c2u(u 1) ，| (e)| miaSx|e(i) | 1|M | 1即得到命题 3.2 中的等式，最后计算uc1vPI PS ucuc v |E |即是命题 3.3 中的等式。3.3 EBIBD 构建分裂认证码这里我们将可以看到 (v,l, )c EBIBD 可以构建分裂认证码。定理 3.5 如果存在一个 (v,l, )c EB

47、IBD ，则存在一个 c 分裂 A-码，使得 1. 公式(3-3) 中所有等号成立；2. |M | v，|S| u； 3每个信源等概率发生。 证 设 |M | v ，对每个区组B B1Bu ，定义编码规则为14e(s1) B1, ,e(su) Bu 。例 3.1 由例 2.4 中给出的 (9,4,1)2 EBIBD 得到满足定理 3.5 的最优的 2 分裂A-码表 3-1s1s2e1m0 ,m1m2 ,m4e2m1,m2m3,m5e3m2 ,m3m4,m6e4m3,m4m5,m7e5m4 ,m5m6,m8e6m5,m6m7,m0e7m6 ,m7m8 ,m1e8m7 ,m8m0,m2e9m8,m

48、0m1,m3其中 PIc|S| 4， Pc(|S| 1) 1| M | 9 PS|M | 1 43.4 Splitting BIBD 与分裂认证码接着看一下 c 分裂 A-码与 Splitting BIBD 的关系。定理 3.7 如果存在满足推论 3.6 中等号成立的 c 分裂 A-码，则|E|v(v 1) l(l c)(3-8)并且，如果上式等号成立，则编码矩阵的行可构建一个(v,| E |,l cu,1) Splitting BIBD 。证 如果命题 3.2 等号成立，则|e:e 1(m) e 1(m ) | 1对任意 m m (41 中证明)。对某些 e，用两种方法数出使 e 1(m)

49、e 1(m )的 m,m 的个数。因为每个 e承担 l c|S| cu个消息，|E |l(l c) v(v 1)。所以公式 (3-8) 成立。下面，如果公式 (3-8) 取等号，则|e:e 1(m) e 1(m) | 1 (3-9) 对任意 m m 。设Be e(s1) e(s2)e(su ) ，15则从公式(3-9) 得(V,B) (M ,Be |e E) 是一个(v,|E |,l cu,1) Splitting BIBD 。定理 3.8 如果存在一个 (v,| E|,l cu,1) Splitting BIBD ，则存在一个 c 分裂 A- 码，使得1. 公式(3-4) 和(3-8) 中所

50、有等号成立；2. |M | v，|S| u； 3每个信源等概率发生。证 设 |M | v ，对每个区组B B1Bu ，定义编码规则为e(s1) B1, ,e(su) Bu 。例 3.2 从(9,2 2,1) Splitting BIBD (其中V 1,2,3,4,5,6,7,8,9 )B1 1,2, 3,5 ，B2 2,3, 4,6 ，B3 3,4, 5,7 ，B4 4,5, 6,8 ，B5 5,6,7,9 ，B6 6,7, 8,1 ，B7 7,8, 9,2 ，B8 8,9, 1,3 ，B9 9,1, 2,4 。可以得到一个满足定理 3.8 的最优的 2 分裂 A- 码。表 3-2s1s2e1

51、m1,m2m3,m5e2m2 ,m3m4,m6e3m3,m4m5,m7e4m4 ,m5m6,m8e5m5,m6m7,m9e6m6 ,m7m8 ,m1e7m7 ,m8m9,m216e8e9m8,m9 m1,m3 m9 ,m1 m2 ,m4PI PS1|E | 9 1其中 PIcu4，PSc(u 1)1，v9 v 143.5 EDF ，EBIBD， Splitting BIBD 的关系3.5.1 EDF与 EBIBD(v,c, )u EDF 等价于一个带特殊自同构的 (v,l, )c EBIBD 。设(X,B)是一个(v,l, )c EBIBD ，设Sym ( X )为X的元素的所有 n!个置换构

52、 成的对称群。一个置换Sym( X )称为 (X,B)的一个自同构映射，如果存在 B的一个置换 ，使得(Bi ) ( (B)i其中 B B，1 i u，换言之 是一个遵循 B B1Bu 的区组与区组之间的一个映射。 ( X ,B)的全体自同构映射的集合(记作 Aut(X ) )，是 Sym(X )的一个 子群，称为 (X,B) 的自同构群。Sym( X )的子群 称为强可迁的，如果对于任意的 x X以及 x X，都存在 惟一的 ，使得 (x) x 。任何一个 Abel加群 (X, ) ，都有一个自然表示： Sym(X )的强可迁子群。准确来说， X的任意一个元素 g就相应有 X 的一个置换 g

53、 ，使得 g g h ， h X 。设(X, ) 是一个 Abel加群， 是它的表示： Sym( X )的强可迁子群。再设 (X,B)是一个(v,l, )c EBIBD ，使 成为 Aut ( X )的一个子群，则( X ,B)以( X , ) 为强可迁自同构群。在证明一个引理后，将给出并证明本节的主要定理。 引理 3.9 设T1,T2 X ，(X, )是一个 Abel加群， a X ，则|T1 (T2 a)| |(s,t):s T1,t T2,s t a|。(3-10)证 记 Da (s,t):s T1,t T2,s t a ， 设 x T1 (T2 a) ， 则 x T1 且 x a T2，故(x,x a) Da 。反过来，如果 (x,y) Da，则x T1 (T2 a)。这 样得到了 Da与T1 (T2 a) 的一个双射。定理 3.10 设(X, )是一个v阶Abel加群，一个 (v,l, )c EBIBD 以(X, )为强可 迁自同构群，记作 (X,B)，等价于 X上的一个 (v,c, )u EDF ，使 l cu。 证 设D1, ,Du为X上的一个 (v,c, )u EDF ，对于1 i u及g X ，定义Big Di g，定义Bgiu 1 Big ，定义包含了 v个区组 B g的区组集合为 B17现在不知道这些区组是否是互异的，下面证明 (