（基础数学专业论文）认证码的平衡化方法及其概率界的研究.pdf

摘要 本文引入一种全新的编码算法( 称其为平衡化方法) 证明了任意一个认 证码( 或系统认证码) 都可以通过平衡化方法转化为一种新的认证码，即罩 衡认证码( 或平衡系统认证码) ，并依此得到了一般认证码在编码规则概率空 间服从均匀分布时最大伪造概率的新下界然后通过建立仿射平面、两两 正交的拉丁方阵以及正交组与系统码的设计矩阵之闻的联系，证明了不同 参数类型下系统码的新的最大替换概率下界最后，研究了部分参数确定 下的平衡认证码和平衡系统码，其伪造概率可能的取值范围，即确定了所 谓认证码的伪造概率谱系 关键词认证码；系统认证码；平衡码；平衡化；仿射平面；拉丁方阵 正交组；概率谱系 a b s t r a c t b yc o n s t r u c t i n gan e wc o d i n ga l g o r i t h m ，c a l l e du n i f o r m i z a t i o n w ep r o v e t h a ta l la u t h e n t i c a t i o nc o d e s ( o rs y s t e m a t i ca u t h e n t i c a t i o nc o d e s ) c a nb eu n i f o r m i z e di n t oan e wc l a s so fa u t h e n t i c a t i o nc o d e s ，c a l l e du n i f o r m i z e da u t h e n t i c a - t i o nc o d e s ( o ru n i f o r m i z e ds y s t e m a t i ca u t h e n t i c a t i o nc o d e s ) ，b yw h i c hw ed e r i v ea n e wl o w e rb o u n do ft h em a x i m u mp r o b a b i l i t i e so fas u c c e s s f u li m p e r s o n a t i o nf o r a l lg e n e r a lc o d e s i fe n c o d i n gr u l ed i s t r i b u t i o n sa r ee q u i p r o b a b l e b yi n v e s t i g a t i n g t h er e l a t i o n s h i pa m o n ga f f i n ep l a n e s ，m u t u a l l yo r t h o g o n a ll a t i ns q u a r e s o r t h o g - o n a r r a y s ，a n dd e s i g nm a t r i xo fs y s t e m a t i ca u t h e n t i c a t i o nc o d e s 、w ep r o v et h e n e wl o w e rb o u n d so ft h em a x i m u m p r o b a b i l i t i e so fas u c c e s s f u ls u b s t i t u t i o nf o r 出l s y s t e m a t i ca u t h e n t i c a t i o nc o d e st h e n ，w es t d u yt h eu n i f o r m i z e da u t h e n t i c a t i o n c o d e sa n du n i f o r m i z e ds y s t e m a t i ca u t h e n t i c a t i o nc o d e sw i t hp a r t i a lp a r a m e t e r s a n dg e tt h ep o s s i b l er e g i o n so ft h em a x i m u mp r o b a b i l i t i e so fas u c c e s s f u li m p e r s o n a t i o n ，c a l l e ds p e c t r u mo fp r o b a b i l i t i e s k e yw o r d s a u t h e n t i c a t i o nc o d e s s y s t e m a t i ca u t h e n t i c a t i o nc o d e s ， u n i f o r m i z e dc o d e s ，u n i f o r m i z a t i o n ，a f f i n ep l a n e s ，m u t u a l l yo r t h o g o n a ll a t i ns q u a r e s o r t h o g o n a la r r a y , s p e c t r u mo fp r o b a b i l i t i e s 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作除了 文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过 的研究成果参与同一工作的其他同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示了谢意 签名 本论文使用授权说明 本人完全了解上海大学有关保留，使用学位论文的规定，即：学校有权 保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文 的全部或部分内容 ( 保密的论文在解密后应遵守此规定) 签名者撬批嗍一，一 ，铀 第一章引言 编码理论是一门年轻的学科，但是在军事，国防、通讯、经济等诸多领 域已有了广泛的应用c e s h a n n o n 的论文。m a t h e m a t i c a l t h e o r yo fc o m m u n i c a t i o n ”( 1 9 4 8 ) 标志着编码理论的开端近年来，随着计算机技术的日新 月异，认证理论做为编码理论一个重要分支，已在信息安全领域展现出其 独有的魅力编码理论主要讨论的是信源编码和信道编码在信道编码理 论的研究中，又有两大主流，一是不断提出新的方法，改进构造出性能更 好的码；二是研究在引入某种代数结构后的码的界我们所研究的认证码 ( a u t h e n t i c a t i o nc o d e s ) 以及认证理论，也是从这两条主流出发，加以研 究的一方面，我们采用一种所谓的平衡化的方法得到了更好的平衡认证 码，另一方面，我们则要研究平衡认证码的界，这里主要考虑的是最大伪造 概率下界和最大替换概率下界，进而研究更加精细的概率谱系目前，处 理传输信息的认证，主要有以下三种形式，审：无条件安全认证码，信息认 证码( m a c s ) ，以及数字签名信息认证码和数字签名分别对应一种对称 加密技术和不对称加密技术，其优点是密钥的可重复利用性大大降低了网 络数据流量，但是随着计算机计算能力的不断升级，对称加密和不对称加 密的安全性在不断遭受质疑，一个个加密标准被证明无法面对越来越强大 的信息攻击作为唯一一种可以应对拥有无限计算能力攻击的认证方法， 研究其性质以及构造方法，具有很大理论意义与实际意义习惯上，我们简 称无条件安全认证码为认证码本文主要就是讨论这种认证方法 1 1 认证码的概率界问题的简介与研究现状 1 1 1 认证码的概率界问题的来源 认证码起源于通信编码理论，在保护数据安全传输方面有着不可替代 的研究意义当今的社会是信息化的社会，未来的竞争，也将朝着电子信息 1 2 0 0 7 上海大学硕士学位论文 2 对抗的方向发展随着世界政治经济全球化多极化浪潮的推进，我们已不 满足于将绝密信息锁于密码箱中，如何在硬件条件无法满足需要的信息传 递通道上，安全地传递机密信息，验证信息来源，是我们最为关心的问题 认证码理论所提供的数学模型，正是为处理此类问题应运而生的认证码 最早的由g i l b e r t ，m a c w i l l i a m s 和s l o a n e 于1 9 7 4 年在“c o d e sw h i c hd e t e c t d e c e p t i o n ”一文中提出的认证理论的数学模型则是由s i m m o n s 4 1 在8 0 年 代初期建立起来的 图1 1 1 经典的认证模型 它表达了这样一个信息传递的问题。即考虑一个信息发送者，一个信 息接收者在一个不安全的信息通道上传递信息，而他们的对手试图以伪造 信息和替换信息两种方式破坏这种通信，即所谓的模仿攻击和替换攻击 信息发送者发送的信息，称为源语句，记作s ，其取自一个有限的源语句集 合s ( 即ses ) ，源语句通过一一映射的且只有信息收发两方知道的编码 规则e e ，加密成对手无法识别的信息m m 对于任何e e 定义 m ( e ) = e ( s ) ：s s ) ，则信息接收者接受认证信息当且仅当m m ( e ) 进而 对信息m 进行了解密，e - 1 ( m ) = s 骨e ( s ) = m ( 既然e 是一一映射，故 e 一1 有意义) 我们记对手最大的成功模仿攻击和替换攻击的概率分别是p j 和p s 一个认证码的最大的成功模仿攻击和替换攻击的概率表征了该码应对强大 信息攻击的能力因此，为了构造性质更好的认证码，研究最大的成功模仿 攻击和替换攻击的概率的下界是十分有意义的，其处于认证码研究领域的 中心位置所有其他问题都是围绕着它逐步展开的 2 0 0 7 上海大学硕士学位论文 3 s i m m o n s 的认证理论给出了在l s i = ，i e = b ，l m i = l ，确定且编码规 则概率空间服从均匀分布时所谓的最大伪造概率下界公式p i = k v ( 参见 【4 ，5 7 】) ，并且此后的许多文献【1 8 ，8 ，1 1 ，1 0 ，2 4 都以此为依据但是作者通过 一种所谓平衡化方法证明了认证码和系统认证码在参数，b 确定且编码规 则概率空间服从均匀分布时的最大伪造概率下界公式并非p 1 ( k ，b ，口) = 加， 而是p ，( 女，b ，口) = k b u 1 6 ( 一般认证码) 和p f ( k ，b ，口) = v 叫 6 ( 系统认证 码) 详细的证明将在第二章中给出 1 1 2 研究现状与研究方法 认证理论是一门涉及代数编码理论、纠错码理论，组合设计、密码学、 仿射几何、有限群、代数几何的交叉热点学科下面，对国际国内已经有研 究成果给出综述 对于任意一个l s i 一七，i m i = u 认证码， p 1 生up s 暑 ( 1 1 j 1 ) t ，一i 以及对于系统认证码， p s p 1( 1 1 2 ) 是容易证明的【19 】 1 9 8 4 年，s i m m o m s 4 ，5 】发现，对于任何一个i s i = 自，i m i = 的认证 码，p 1 2k v 等号成立，当且仅当 船( e ) = ： ( 1 13 ) e e ：m m ( e ) ) 之后m a s s e y 和s t i n s o n 7 分别在1 9 8 6 年和1 9 8 8 年发现了对于任何一个 l s i = 女，i m i = 的认证码，p 8 一1 v 一1 等号成立，当且仅当 疑= 篙器崭= 等1 “， e e ：，l m ( 。) p b ( e ) 阳( e 一1 ( m ) ) 口一 ” 对于m 中的每一对m m ，都成立 s i m m o n s 和b r i c k e l l 等人，从信息论的角度，于1 9 8 4 年分别证明了p ， 和p s 下界的另一个估计，即著名的s i m m o n s 界【6 ，4 ； 2 0 0 7 上海大学硕士学位论文 4 p ，2 - 1 ( m ；b ) p s 2 - h ( e i m ) ，i s i22( 11 ，5 ) 其中，h ( x ) 表示随机变量x 的熵，而，( x ；y ) 表示随机变量x 和y 的交 互信息 s i m m o n s 界，让我们能更好地理解认证码保护数据的机制从中可以 看出，为了更好地保护数据使其不被伪造，( 即，使得成功伪造信息的概率 p ，尽可能的小) 我们不得不泄露关于编码规则的许多信息；然而，另一方 面，为了更好的保护数据不被替换，编码规则的不确定性需要尽可能的大 也就是说，我们不能把所有的关于编码规则的熵都花费在保护数据不被伪 造上，同时需要用一定量的编码规则的不确定性来减少替换攻击成功的概 率于是，数学家们做了许多的研究工作以调和这对矛盾并且构造出了许 多性质很好的认证码子类 认证码与组合设计有着密切的联系b r i c k c l l 和s t i n s o n 等人，将特定 参数的认证码与特定的组合设计一一对应起来包括，横截设计、正交区 组、平衡不完全区组设计等 1 9 9 2 年，b r i c k e l l 和s t i n s o n 9 】等人第一次将认证码与平衡不完全区 组设计联系在了一起，并且发现p t = k v 和p s k1 v 1 时，b 口扣一1 ) k ( k 一1 ) 等号取到，当且仅当编码规则矩阵为一个( ，k ，1 ) 一b i b d 且信源和编码规则都是等概分布 从此组合设计方法，开始引入到认证码的研究之中 1 9 9 3 年，s t i n s o n 1 0 】进一步得出，对于任何一个i s i = ，| m = 口的认 证码，若p 1 = p s = k v = 1 t ，有 ( i ) b 2 2 等号取到，当且仅当认证矩阵是一个正交阵o a ( t ，k ，1 ) 且认证 规则是等概率的 ( i i ) b k ( 1 1 ) + 1 等号取到，当且仅当认证矩阵是一个正交阵o a ( 1ka ) 且认证规则是等概率的，其中，a = ( k ( t 一1 ) + x ) z 2 s t i n s o n 还对几类特殊的认证码，对称认证码进行了一系列研究 2 0 】 继s t i n s o n 等人在仿射空间射影空间中对认证码的组合特征的研究之 后，万哲先等人【2 2 】，于1 9 9 4 年，开始把问题延伸到比仿射空间稍复杂一些 2 0 0 7 上海大学硕士学位论文 5 的辛空问k ，( k ) 中来构造系统认证码，并且成功构造了参数为 k = i i ( g “一1 ) v - - 1 ( 矿一1 ) b = 9 2 ( ”一1 ) ，u = ! ：! i ；? 兰一q 2 ( ”一“) + ”一1 ( 1 1 6 ) i i ( q i 1 ) l = l 的系统认证码并且给出了编码规则空间服从均匀分布时。成功伪造攻击概 率和成功替换攻击概率。分别为 p 产考矗，p s 一- 百1 ( 1 1 7 ) 以及参数为 k = q 3 ，b = ( q 一1 ) 口2 ”3 ，u = 矿一2( 1 ，1 8 ) 的系统认证码，并且给出了编码规则空间服从均匀分布时，成功伪造攻击 概率和成功替换攻击概率，分别为 p ，= ：，p s = 击 ( 1 1 9 ) 口口一l 1 9 9 4 年，t j o h a n s s o n ，g k a b a t i a n s k i i ，和b s m e e t s 等人f 1 9 ，利用代数 几何的手法建立了认证码理论与纠错码理论的内在联系：在给定p ，p s 和 编码规则数的条件下，构造一个具有最大信源集的认证码，等价于，在给 定最小距离条件下，构造一个具有最大基数和码长的纠错码即，假设存 在一个参数为( n ， 厶d ) 的纠错码，使得如果c c ，那么对于所有a f 口有 c + a 1 g 那么就存在一个对应参数为 i s l = m q 一1 ，l e i = 伽，p x = 孑1 ，p s = 1 一i d ( 1 1 1 0 ) 的认证码1 9 9 6 年，g k a b a t i a n s h i 等人【1 9 】，进一步发展了这一结果 1 2 本文主要工作 本文主要做了三方面的工作 一，在第二章中，作者通过一种所谓平衡化方法证明了认证码和系统 认证码在参数k ，b ， 确定且编码规则概率空闻服从均匀分布时的最大伪造 苛 2 0 0 7 上海大学硕士学位论文 6 概率下界公式并非p d k ，b ， ) = 口，而是p 1 ( k ，b ，v ) = k b v l b ( - - 般认证码) 和p f ( k ，b ，口) = b l v l k l l b ( $ 统认证码) 二，第三章主要是通过建立仿射平面、两两正交的拉丁方阵( m o l s ) 以及正交组( o a ) 与系统码的设计矩阵之问的联系，证明了a s ( n ，6 ，n 2 ) 、 a s ( k ，b ，k 1 ) 新的最大替换概率下界，以及a s ( k ，b ，t ，) 参数b 的上界和下界 ( 1 ) 对于a s ( n ，b ，犯2 ) 有如下结论；如果n = p ，其中p 为素数，且t 1 ， 则对于系统认证码a s ( ，b ，舻) 其中b 墨舻，有 硝m6 ，舻) 2i i 与 ( 1 2 1 ) ( 2 ) 对于a s ( k ，b ， ) 有如下结论。对于任意的参数k ，l ，存在参数6 ( t ，f ) ， 使得对于系统认证码c a s ( k ，b ，k 0 ，有p s ( c ) = 且p i ( c ) = 设 p ；( ，口) = m i n p s ( c ) l c a s ( k ，6 ，口) ) ，则对于任意的参数k ，z 有 p g ( ，k 1 ) = ( 1 2 2 ) ( 3 ) 对于系统码c a s ( k ，b ， ) ，记 a ( c ) - 。m a x 。i e ( m 1 ) ne ( m 2 ) l ， 则有 6 a ( c ) ( ；) 2 且等号取到当且仅当k j t ，且存在正交组2 _ ( ，k ，a ) 一o a t - 、第四章讨论了，认证码的伪造概率谱系 印e c ( ， ) = ；qi 存在平衡码c eb ( k ，口) 使得p ，( c ) 2 ；q ) ( 1 2 3 ) 和系统码的伪造概率谱系， s p e c s ( ，口) = ；i 存在平衡码c es b ( k ，口) 使得p ，( c ) = ；q ) ( 1 2 4 ) 即对于任意的具有参数i s l = k ，i m | = 的平衡认证码和平衡系统码， 其伪造概率可能的取值 得到结论，对于平衡认证码， 2 0 0 7 上海大学硕士学位论文 7 当2 时， 唰啪) = ；q p 里【：，警) 且了q - 1 口时， 职( 啪) = ；ql ；q 知且孚 d ( c 1 ) d ( c 。) ，其中c 。满足 ! _ ( c f ) k ( q ) + 1 ，江1 ，“一1 ；( 2 2 6 ) it m ( c i ) ? m ( c i ) + 1 ，t = n 且有p t ( c ) 2p 1 ( c 。) ，因此c 。即所求的平衡码，故命题得证口 定理2 2 2p ，( ，6 ，口) = f k b v b 证明由定理2 2 1 知存在码c o 满足l m ( c 幻= k ( c o ) 或k ( c o ) = ! m ( c b ) + 1 ( i ) 若i m ( c o ) = k ( c o ) ，则由。l e ( m ) i = k b ，知i m ( c o ) = k b v ，印口i 以 且有p l ( c o ) = ( , b b v ) b = k v = j e ( m ) l b = i m ( c o ) b p i ( c ) ( i i ) 若m ( c o ) = l m ( c o ) + 1 ，则设满足1 e ( m ) i = 2 m 的m 有t ，一t 个，其 中0 t ，则有扣一t ) f m + t ( 1 m + 1 ) = k b ，故口k + t = k b 。0 ( c ”) ，其中c 满足 2 ( c 9 t m ( c 。) + 1 ，4 = 1 ，”。1 ；( 2 删 lt m ( c 4 ) k ( c 1 ) + 1 ， = n 且有p i ( c ) 2 p i ( c ”) ，因此c ”即所求的系统平衡码，故命题得证口 注：在上述定理证明中，对系统码进行的每一次系统平衡化时，都需要 先对该码的每个子码进行有限次定理2 2 1 所述的平衡化，使其成为平衡子 码，然后再对平衡子码的并进行定理2 3 1 所述的平衡化从而任何系统认 证码，在进行了有限次系统平衡化后，都可以转化为系统平衡码 定理2 3 2p s s ( k ，b ， ) = b v k b 证明设c a s ( k ，b ， ) ，则由前知，有一个平衡系统码c o o = u c ? a s ( k ，b ) 使p s ( c 8 ) p i ( c ) p i ( c o o ) = m a x i p i ( c 0 ) 。p ，( c ? ) = b l l m ( c o ) 1 l b ，其 中i m ( c t ) 1 = 【v l k l 或 v l k 】+ 1 因此p j ( c 8 ) = b l l v l k l l b 由此结论成立口 例2 2 2 对于一个系统码c a s ( 4 ，6 ，1 1 ) ，我们可以通过设计矩阵给出 2 0 0 7 上海大学硕士学位论文 1 7 其平衡化的过程，如下 23 4 m lm 2m s 01 01 10 10 ol 10 10 0 010 010 0 01 0 01 001 100 01o 0 01 0 0 o 10 o o o 0 2 m 4 10 01 10 01 10 o1 2 3 m tm 2 0l 01 l0 l0 0l l0 100 01o 010 0 01 0 01 l0 0 生 m s 100 0 l 垒 00 量 000 10 o 一 0 00 2 一 m 4 10 0l 10 01 10 o1 3 312 量211 23 3 i e ( 呐) i 3 3 2 2 2 21123 3 3 m 2 l0 0 010 01 0 0 01 001 1o 0 3 m 3 100 010 00 立 0 01 10 0 00 l 3 m 4 010 001 1 10 001 010 00 l 23 m 1m 2 0l 0l 10 1o o1 1o 100 o10 o1o 0 01 001 1o 0 33 m sm 4 l0 0 010 001 o o1 _ - 1 00 0 0l 0l0 0 01 10 0 0 0t 010 00 三 3 3 2 2 2 212133 3 3 2 2 2 2 1 墨一1 2 墨 3 m 2 100 010 010 0 01 001 10 0 33 m sm 4 lo0 0lo 0 01 010 10 0 oo1 010 001 10 0 0 01 010 lo0 3 322 2222 222 平衡化后的系统码c a s ( 4 ，6 ，1 1 ) 其p f ( c 7 ) = 1 2 ，是a s ( 4 ，6 1 1 ) 中最 大伪造概率最小的系统码 2 h 1 1 o o l 0 h 0 0 1 1 o 1 2 h 1 l o 0 1 o h o o 1 1 o 1 2 0 0 7 上海大学硕士学位论文 1 8 第三章系统认证码的最大替换概率下界 本章主要是通过建立仿射平面，两两正交的拉丁方阵( m o l s ) 以及正交 组( o a ) 与系统码的设计矩阵之间的联系，证明了a s ( n ，b ，n 2 ) 和a s ( k ，b ，k 1 ) 新的最大替换概率下界，以及a s ( k ，b ， ) 参数b 的界 3 1 系统认证码a s ( n ，b ，佗2 ) 的p g 界 在标准的( 欧氏) 平面几何中，常把一个基本集合p 称作点的集合，其 元素称作点，而把p 的子集c 称作线 定义3 1 1 1 3 】若集合p 和p 的子集满足公理 ( a 1 ) p 中两个不同的点a 和b ，包含于且仅包含于一条c 之中的线( 该 线常记为l ( a ，b ) ) ； ( a 2 ) p 中有四个不同的点，其中任意三点不在同一条线上； ( a 3 ) 对于任意一条线l c 及任意一个点p p 且p l ，则存在唯一的 线m c 使得p m 且m nz = 0 ， 则将结构( p ，c ) 称为仿射平面 定理3 1 1 【1 3 ，1 2 ，1 ，3 】令( p ，c ) 为一个n 阶仿射平面，则有 ( 1 ) 任意一点恰落在n + 1 条线上； ( 2 ) 任意一条线恰包含n 个点； ( 3 ) 恰包含舻个点； ( 4 ) 恰包含舻+ n 条线； ( 5 ) 对于任意一条线，有( 包含自身的) n 条线与其平行 定理3 1 2 【1 3 1 如果n = 矿，其中p 为素数，且t 1 ，则存在一个阶数为 n 的仿射平面 引理3 1 1 若( p ，c ) 是一个n 阶仿射平面，删去平面内任意n 条平行 线，则对于平面内任意一个点，存在另外”一1 个点，使得以上这n 个点中， 任意两点不共线 2 0 0 7 上海大学硕士学位论文 1 9 证明对于”阶仿射平面( p ，c ) ，若删去其中任意n 条平行线，则由定理 3 1 1 ( 2 ) 知，该仿射平面内每条直线上恰有n 个点，所以删去的n 条平行线 上共有舻个点而由定理3 1 ，1 ( 3 ) 知，n 阶仿射平面恰有舻个点，所以该仿 射平面内的任意一个点，都对应一条被删除的线，从而在该线上存在n 一1 个点，使褥删去该线后，由定义3 1 i ( a 1 ) 知，这总共n 个点两两不共线口 例3 1 1 若p = z 3 z 3 = “o ，b ) ：n ，b z 3 ) ， = l b 。：口，b ，c z 3 ，o 0 ，或b o ) ，其中， k ，6 ，c = ( 霉，耖) 7 , 3 z 3 ：n z + b u + c = o ) 则( p ，c ) 是具有9 个点和1 2 条线的3 阶仿射平面，记作a e ( z 3 ) 如左下 图 图3 1 1 在3 阶仿射平面a p ( z 3 ) 上删除3 条平行线 由引理3 1 1 ，删除a p ( z 3 ) 上的3 条平行线( 如右上图) ，可使其中任意一 个点都可以在仿射平面内找到另外2 个点，使这3 个点两两不共线事实 上，通过在n 阶仿射平面上删除n 个点，可以将仿射平面内的点分成n 组， 每组内的点两两不共线 定理3 1 3 如果t l = ，其中p 为素数，且t 1 ，则对于系统认证码 a s ( n ，b ，n 2 ) ，其中b s 舻，有 咄m 埽) 。习每 ( 3 川 证明首先用反证法证明 蝮m 乱舻) 南 ( 3 1 2 ) 2 0 0 7 上海大学硕士学位论文 假设p g ( n ，6 ，n 2 ) i 两1 ，则由编码规则服从均匀分布时最大成功替换概率 的计算公式知，存在系统认证码c a s ( n ，b ，舻) 使得 剐c ) = 点掣 t l 一譬1 ，即 i e ( m 1 ) i n i r n - - b j + l ( 3 1 7 ) 而对于所有系统码a s ( n ，b ，n 2 ) 都有 n 2 i e ( m o i = n b ( 3 1 8 ) 从而 ：差 n2一了n2-bie(m1)l n 2 ( n) ，l 6 = 一司+ 1 ) 饰一( 掣+ 1 ) + 1 ) = 矛盾原假设不成立故p ；( n ，6 ，舻) 云鬲1 成立 下面，我们通过仿射平面，构造码c a s ( 礼，6 ，n 2 ) 使得p s ( c ) = i 雨1 从而进一步证明p a s ( n , b , n 2 ) 2 = 鬲1 由定理3 1 2 知。存在一个阶数为n 的仿射平面由定理3 1 1 ( 4 ) ( 5 ) 知该 仿射平面内有n + 1 个平行线组，每个平行线组恰包含 条平行线考虑让仿 2 0 0 7 上海大学硕士学位论文 2 1 射平面内的每组平行线交于仿射平面外一个无穷远点，由此得到的n + 1 个 无穷远点 o o l ，o o 。+ 1 1 对应一条无穷远线c 。我们常常将如此添加n + 1 个无穷远点和一条无穷远线的n 阶仿射平面，称为n 阶射影平面( 射影平 面与仿射平面可以等价地转化，故这里不对射影平面做进一步的展开，更 多关于射影平面的结果可以参考【1 3 】) 将c 。上的无穷远点看作源语句，将 仿射平面上的点看作是编码规则，将仿射平面上的线看作是信息，则由源 语句集合s 和编码规则e 到信息集合m 的映射即可表示为联接源语句s 和 编码规则e 生成的唯一一条线m ，即信息从而满足系统认证码的定义条件 ( 1 ) 若线m 1 交。于8 1 ，线m 2 交c o o 于8 2 ，8 1 8 2 ，m l ，m 2 都经过点e ，则有 m l r n 2 故满足系统认证码的定义条件( 2 ) 同理，若线m 1 交c 。于钆线 m 2 交c 。于s 2 ，t n l = 2 ，则有8 1 = 8 2 故满足系统认证码的定义条件( 3 ) 又 由定理3 1 1 ( 3 ) ( 4 ) ( 5 ) 知j s i = ( 舻+ n ) 加= n + 1 ，l e i = n 2 ，i m i = 舻+ n ，从而建 立了一个系统认证码c a s ( n + 1 ，n 2 ，n 2 + ) 与n 阶仿射平面之问的对应关 系若有如下定义t 定义3 1 2 若( p ，c ) 是一个n 阶仿射平面，c 7 = g l ，如，靠 是c 的n 元子集，且n ，如，靠两两平行，称( p ，c c 7 ) 为n 阶拟仿射平面 则同时存在一个系统认证码c a s ( n n 2 n 2 ) 对应于t l 阶拟仿射平面 图3 1 23 阶仿射平面与系统认证码a s ( 4 ，9 ，1 2 ) 和a s ( 3 ，9 ，9 ) 的关系 ( i ) 当b = n 2 时，对于任意一个系统码c a s ( n ，n 2 ，舻) 有 p s ( c ) 2p ，( c ) 2p ，矿，n 2 ) = 元1 ( 3 i g ) 此时存在一个系统认证码c o a s ( n ，舻，舻) ，对应于一个n 阶拟仿射 平面由定义3 1 i ( a 1 ) ，任意两条线至多交于一点，即峨n 易i 1 ，其中 2 0 0 7 上海大学硕士学位论文 i , j l 2 ，舻) 且i j 当磊不平行于易时，等号取到另外，由定理 3 1 1 ( 2 ) ，对于任意的i 1 ，2 ，舻 有= n 从而 晰，。毒瞥2 臀锴= ： n 1 1 。， 所以，p s ( n ，舻，n 2 ) = ； ( i i )当b 舻的情形， 也同样非常值得研究 3 2 系统认证码a s ( k ，b ，k 1 ) 的p g 界 定义3 2 1 【1 3 ，3 】n 阶拉丁方阵是一个t i 的矩阵，其元素取自集合 o 0 1 0 1 o o o o o o o l l o 0 o 1 也0 o 1 0 h 1 1 o 0 t，。 培o 0 1 k o l 0 h l 0 0 ，i、 2 0 0 7 上海大学硕士学位论文 f 1 ，2 ，n ) ，并且每个元素在每行每列都只出现一次一对拉丁方阵a = ( ) 和b = ( ) ，如果对于所有的，l l ，2 ，n ) 都存在唯一的( i ，j ) ，使得叼= 女 且= l ，称为它们为正交拉丁方阵 例3 2 13 阶正交拉丁方阵如下， 譬圜耻圜 令l ( n ) 为两两正交的 阶拉丁方的最大个数，则有 定理3 2 1 【3 至多存在n 一1 个两两正交的n 阶拉丁方阵即l ( n ) n 一1 定理3 2 2 【3 】令自然数t l 2 ，那么存在n 阶仿射平面当且仅当存在n 一1 个两两正交的n 阶拉丁方阵 定义3 2 2 【3 】令t ，n ，k 和a 是正整数使得女t 2 一个扛( ，a ) 正交组 ( 记做t - ( n ，a ) 一o a ) 是一个满足下述条件的二元组( x ，d ) ： ( 1 ) x 是含有”个元素的集合，称其中的元素为点 ( 2 ) d 是一个a n t 乘的组，其元素取自集合x ( 3 ) d 中的任意t 列中，每t 点对都恰含于a 行中 当t = 2 且 = 1 时i 我们也将扛( ，k ，a ) 一o a 简记为o a ( k ，n ) 定理3 2 3 【3 】3 假设整数n 1 且整数k 3 ，则存在一2 个两两正交的n 阶拉丁方阵m o l s ( n ) ，当且仅当存在正交组o a ( k ，n ) 定理3 2 4 【3 】3 由任何一个正交组僻，d ) = o a ( k ，z ) 可以构造一2 个两两 正交的l 阶拉丁方阵l 1 ，工t 一2 如下t 岛( d ( f ，1 ) ，d ( i ，2 ) ) = d ( i ，j + 2 ) ( 3 2 1 ) 其中 i = 1 ，1 2 , j = l ，k 一2 ， 定理3 2 5 由任何一个正交组( x ，d ) = o a ( k ，z ) 可以构造一个系统码 c a s ( k ，户，k 1 ) 的o _ 1 设计矩阵日如下： 。 日= ( h 1 ，1 t 2 ，巩)( 3 22 ) 其中 2 0 0 7 上海大学硕士学位论文 哪一) _ 1 ，乳_ d o j ) 时，( 3 删 、i d d ， i 毋( 1 ，z ) = 0 当z d ( i ，j ) 时 i = 1 ，j 2 ，j = l ，k ， 使得 ( 1 ) h 中任意一列都恰舍有z 个1 ( 2 ) h j 中任意两列的交为空集o = 1 ，k ) ( 3 ) g j ，与日五中任意两列的交为1 ，j 1 ，如 1 ，k ) 且j l 虎 证明( 1 ) 考虑正交组( x ，d ) = 2 - ( t ，k ，1 ) 一o a = o a ( k ，z ) ，因为参数a = 1 且 t = 2 ，则由正交组的定义中第3 条知，在d 的任意两列申，每个点对都恰出 现在某一行中，而由于x 中有1 个点，所以在d 的任意两列中，每个点都 恰有1 个不同的点对包含该点故在d 的任意一列中每个点都恰出现在l 行 中故日中任意一列都恰含有1 个1 ( 2 ) 下面证明h i 中任意两列的交为空集o = 1 ，k ) 因为对于任意的 ：t 1 ：9 2 x ，不存在一个t 1 ，产，使得g j ( i ，z 1 ) = 马( ，t , 2 ) = 1 既然上式 成立必须x l = d ( i ，j ) = # 2 与z l 现矛盾，所以这样的的i 是不存在的 ( 3 ) 因为在d 的任意两列中，每个点都恰有z 个不同的点对包含该 点，所以对于任意x l ，$ 2 x ，一定存在 1 z 2 使得当j 1 如时， x l d ( i ，j 1 ) ，t , 2 = d ( i ，j 2 ) 故一定存在i 使得玛。( ，z 1 ) = 日j ：( i ，x 2 ) = 1 印巧， 与如中任意两列的交为1 ，j l ，杰 1 ，埘且歹1 力口 同理，对于任何一个h = ( 凰，凰，g k ) ，满足| 皿= = i 凰i ，则可以 构造一个正交组o a ( k ，1 ) 如下； d ( i ，j ) = o( 3 2 4 ) 当场( 1 ，z ) = 1 时 这样就建立了系统码c a s ( k ，6 ， z ) 的0 - l 设计矩阵h 与正交组o a ( k ，f ) 之间的一一对应关系 例3 2 2 由o a ( 4 3 ) 和对应的2 个m o l s ( 3 ) ，构造c a s ( 4 ，9 ，1 2 ) 的设计 2 0 0 7 上海大学硕士学位论文 矩阵如下 1111 1222 l3 3 3 212 3 2 2 31 2 312 3l32 3 2l3 3 3 21 ，10 0l0 010 0100 、 10 0010 01o 010 100001o 0l0 01 010100010 o 0l o10 010 001l0 0 01 0 0 0110 00 10 0 01 10 0 0 01010 0 01010 10 00 01 0 010 0101010 0 圜园 注意到，由定理3 2 4 ，上图中的2 个拉丁方阵是由o a ( 4 3 ) 的最后2 列得到 的由定理3 2 5 ，它们又同时对应于a s ( 4 ，9 ，1 2 ) 的设计矩阵的最后两个列块 定理3 2 6 对于任意的参数k ，f ，存在参数b ( k ，z ) 使得对于系统认证码 c a s ( k ，b ，k z ) ，有p s ( c ) = 且p z ( c ) = 证明( i ) 若( f ) + 2 ，即存在k - 2 个两两正交的f 阶拉丁方阵m o l s ( ) 则由定理3 2 3 和定理3 2 5 知，可以构造一个系统码c ( o ) a s ( k ，f 2 ，肼) 再由 定理3 2 5 知，c ( o ) 的o _ 1 设计矩阵日( o ) 满足。定理3 2 5 的条件( 1 ) ( 2 ) ( 3 ) ，即 ( 1 ) 日( o ) 中任意一列都恰含有f 个1 ( 2 ) 碰唧中任意两列的交为空集u = 1 ，k ) ( 3 ) 日；? 与日等中任意两列的交为1 ，1 ，血 1 ，k ) 且血庇 由( 1 ) 知p z ( c ( o ) ) = 古= ，由( 1 ) ( 3 ) 知p s ( c ( o ) ) = 2 0 0 7 上海大学硕士学位论文 ( i i ) 通过定义新的0 1 设计矩阵，日( ”，h ( ”，其中 日0 ) ： 1 所： l 1 月j： 1 1 肺 ： 1 ( 3 2 5 ) 研= = 凰= 日( “) ，江l ，2 ( 3 2 6 ) 我们可以构造系统码c ( 0 a s ( k + i ，f ， + i ) f ) 首先，日( f ) 是符合d o 的参数条件的，其次，如果日( 一1 ) 满足定理3 2 5 的条件( 1 ) ( 2 ) ( 3 ) 则日( ) 同 样满足定理3 2 5 的条件( 1 ) ( 2 ) ( 3 ) ，即t ( 1 ) 日( ) 中任意一列都恰含有z 个1 ( 2 ) 叫”中任意两列的交为空集0 = i ，k ) ( 3 ) 彤：与碟中任意两列的交为1 ，j 1 ，如 1 ，+ ，且j l 虎 这样则有p j ( c ( ) ) = p s ( c ( ) = 既然我们已经由( i