（运筹学与控制论专业论文）分裂认证码的平衡化方法及其伪造概率界的研究.pdf

摘要 本文主要研究分裂认证码的最大伪造概率下界。引入平衡化的方法，发现并 证明了一般分裂认证码和分裂系统认证码在编码规则概率空间服从均匀分布时最 大伪造概率的新下界。 关键词分裂认证码；分裂系统认证码；平衡化 a b s t r a c t t h i sn o t e g i v e s al o w e rb o u n do fm a x i m u mp r o b a b i l i t i e so fas p l i t t i n g a u t h e n t i c a t i o nc o d e 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 ，a n e wl o w e rb o u n do fm 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 lf o r g e r yf o ra l lg e n e r a l s p l i t t i n ga u t h e n t i c a t i o nc o d e sa n ds p l i t t i n gs 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 si sd e r i v e di f e 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 k e yw o r d ss p l i t t i n ga u t h e n t i c a t i o nc o d e s ，s p l i t t i n gs y s t e m a t i ca u t h e n t i c a t i o n c o d e s ，u n i f o r m i z a t i o n 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。除了文中特 别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果。 参与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 张缛受魄切口 o 本论文使用授权说明 本人完全了解上海大学有关保留，使用学位论文的规定，即：学校有权保留 论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容。 ( 保密的论文在解密后应遵守此规定) 始俗凌翩张彬钐帆w 弘。 上海大学硕士学位论文 第一章引言 随着信息时代的来临，信息论与编码理论在军事、通讯、经济、安全等许多领域得到了 广泛的应用，并产生了深远的影响。1 9 4 8 年，c e s h a n n o n 的一篇通信中的数学理论标 志着编码理论的开端。近年来，随着计算机技术的日新月异，认证理论是现代密码编码学中 防止主动攻击的重要手段，它对于开放环境中各种信息系统的安全有着重要作用。传统上， 密码学的主要目的是提供机密性，以保证机密信息只能被系统中授权的各方所获得。随着技 术的发展和各种新型应用的不断出现，如何防止攻击者对信息系统进行主动攻击变得越来越 重要。认证的主要目的有两个：第一，信源识别，即验证发信人确实不是冒充的；第二，检 验发送信息的完整性，也就是说，即使信息确实是经过授权的信源发送者发送的，也要验证 在传送过程中是否被篡改，重放或延迟。认证理论主要是由g j s i m m o n s 发展起来的，他证 明了该领域的许多基本结果；这一理论也是将s h a n n o n 的信息论用于研究认证系统的理论安 全性和实际安全性问题，指出认证系统的性能极限( 欺骗概率的下限) ，以及设计认证码必须 遵循的原则。认证码有无分裂的认证码与有分裂的认证码两种。一般地，编码规则将一个信 息编码成为一个对应的消息，这时称为无分裂的认证码；若编码规则编码一个信息成为多个 消息，则称为是有分裂的认证码，而本文主要研究有分裂的认证码，并总假设敌方有无限的 计算资源，即认证码为无条件安全。本文主要从以下两个角度研究：一方面，我们采用一种 平衡化的方法得到了更好的分裂平衡码，另一方面，我们则要研究分裂认证码或系统分裂认 证码的界，这里主要考虑的是最大伪造概率下界。 1 1 分裂认证码的简介与研究现状 1 1 1 分裂认证码的概率下界问题来源 认证码起源于通信编码理论，在保护数据安全传输方面有着不可替代的研究意义。当今 的社会是信息化的社会，未来的竞争，也将朝着电子信息对抗的方向发展。随着世界政治经 济全球化、多极化浪潮的推进，我们已不满足于将秘密锁于密码箱中，如何在硬件条件无法 满足需要的信息传递通道上，安全地传递机密信息，验证信息来源，是我们最为关心的问题。 认证码理论所提供的数学模型，正是为处理此类问题应运而生的。1 9 7 4 年，g i l b e r t ，s l o a n e 和m a c w i l l i a m 首次提出了认证码的概念，并用有限几何构造了认证码。2 0 世纪8 0 年代初期， s i m m o n s 等人系统的发展了认证理论。文献 1 给出的数学模型，包括三个参加方：发方、收 1 上海大学硕上学位论文2 方和敌方。发方欲传送信源信息给收方，先将信源编码成为消息，发方与收方事先规定编码 规则，敌方知道编码规则集合，但不知道发方与收方在传送信息过程中所采用的编码规则。 记信源集合为s ，消息集合为膨，编码规则集合为e 。发方要送信源s s 给收方，将s 用与 收方约定好的编码规则e e 编码成为消息m m ，收方收到消息后利用e 恢复为传送的信 源信息s 。敌方在发方未发送任何消息时伪造一个消息发送给收方，称为模仿攻击；若收方 作为合法的消息接收，称为攻击成功，记这种攻击成功的最大概率为p 。敌方观察到一个消 息m 后，用一个不同的消息m 7 代替m 发送给收方，称为替换攻击；若收方m 作为合法消息 接收，且m 与m 代表不同的信源，称为替换攻击成功，记这种攻击成功的最大概率为只。 一个认证码的最大的成功模仿攻击和替换攻击的概率表征了该码应对强大信息攻击的能力。 因此，为了构造性质更好的认证码，研究最大的成功模仿攻击和替换攻击的概率的下界是十 分有意义的，其处于认证码研究领域的中心位置。所有其他问题都是围绕着它逐步展开的。 一般地，编码规则将一个信息编码成为一个对应的消息，这时称为无分裂的认证码，即 通常意义的认证码：若编码规则编码一个信息成为多个消息，则称为是有分裂的认证码，而 本文主要研究有分裂的认证码，并总假设敌方有无限的计算资源，即认证码为无条件安全。 对于任意的p e ，任意s s ，p 0 ) cm 。若认证码为有分裂的，i i j l e ( s ) i 1 ( 分裂认证 码模型见图一) 。为了使收方能够唯一的确定有消息传送的信源信息，须有：对于任意的s s ， 任意的e e ，s s 7j e ( s ) n e ( s ) = 矽。2 0 0 4 年，o g a t a 、k u r o s a w a 、s t i n s o n 和s a i d o 等人 在研究b i b d 理论3 1 时，给出了分裂认证码在参数蚓= 尼，e l = l m i = 6 ，l e ( s ) i = ，确定且编码 规则概率空间服从均匀分布时的最大伪造概率下界公式为鼢6 。而本文作者则是通过平衡化 的方法，研究分裂认证码和分裂系统认证码在上述参数更为复杂情况下的最大伪造概率下界， 并验证了上述结果。详细的工作将在第二章和第三章中展开。 随机时间触发器 图一：分裂认证码模型 2 上海人学硕士学位论文3 1 1 2 认证理论饼艽士见状 认证理论是- f l 涉及代数编码理论、纠错码理论、组合设计、密码学、仿射几何、有限 群、代数几何的交叉热点学科。下面，对国际国内已经有研究成果给出综述。 对于任意一+ l s l = 尼，i m i = v 的认证码，e 告，b 了s - i 1 ，显然是成立的。 1 9 8 4 年，s i n u n 。n s 发现，对于任何一+ i s i = 尼，i m i = ，的认证码，e 等等号成立， 当且仅当 ，。p小)=告e。e：mem(e) y 之后，m a s s e y 和s t i n s o n 分别在1 9 8 6 年和1 9 8 8 年发现了对于任何一+ i s i - k ，i m i = ， 的认证码，b ! ；等号成立，当且仅当 ，一l p z ( e ) p s ( e 一( 肌) ) e e e ：m e m ( e ) p e ( p ) 风( p 1 ( 聊) ) e e e ：m e m ( e ) 对于m 中的每一对m m7 都成立。 七一1 v 一1 s i m m o n 和b r i c k e l l 等人，从信息论的角度，于1 9 8 4 年分别证明了e 和b 下界的另一个 估计，即著名的s i m m o n s 界： 名2 叫眦，b 2 - z ( e l m ) , 俐 2 其中，h ( x ) 表示随机变量x 的熵，而，( ；y ) 表示随机变量x 和】，的交互信息。 s i m m o n s 界，让我们能更好地理解认证码保护数据的机制。从中可以看出，为了更好地保 护数据使其不被伪造( 即，使得成功伪造信息的概率另尽可能的小) ，我们不得不泄露关于编 码规则的许多信息；然而，另一方面，为了更好的保护数据不被替换，编码规则的不确定性 需要尽可能的大。也就是说，我们不能把所有的关于编码规则的熵都花费在保护数据不被伪 造上，同时需要用一定量的编码规则的不确定性来减少替换攻击成功的概率。于是，数学家 们做了许多的研究工作以调和这对矛盾。并且构造出了许多性质很好的认证码子类。 认证码与组合设计有着密切的联系。b r i c k e 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 等人第一次将认证码与平衡不完全区组设计联系在了一起， 3 上海大学硕士学位论文 4 并且发现弓= v 和层= k - 1 v 一1 时，b v ( v 一1 ) k ( k 一1 ) 等号取到，当且仅当编码规则 矩阵为一个( v ，k ，1 ) - - b i b d 且信源和编码规则都是等概率分布。 从此组合设计方法，开始引入到认证码的影f 冗之中o 1 9 9 3 年，s t i n s o n 进一步得出，对于任何一个蚓= 尼，i m l = v 的认证码，若e = b = k v = 1 1 ，有 ( i ) b ，2 等号取到，当且仅当认证矩阵是一个正交阵o a ( ，k ，1 ) 且认证规则是等概率的。 ( i i ) b k ( 1 - 1 ) + 1 等号取到，当且仅当认证矩阵是一个正交阵o a ( i ，尼，五) 且认证规则 是等概率的，其中，旯= ( 尼( ，一1 ) + 1 ) 1 2 。 s t i n s o n 还对几类特殊的认证码，对称认证码进行了一系列研究继s t i n s o n 等人在仿射 空间、射影空间中对认证码的组合特征的研究之后，万哲先等人于1 9 9 4 年开始把问题延伸到 比仿射空间稍复杂一些的辛空间，( ) 来构造系统认证码，并且成功构造了参数为 y lv - i 1 - q 2 卜1兀9 2 卜1 k = v 一所+ v l 兀 i = 1 b = q 2 ( v - i ) , ，= v 一1 q 卜1 兀q 卜1 扛l q 2 ( ”一”+ ”一1 的系统认证码并且给出了，编码规则空间服从均匀分布时，成功伪造攻击概率和成功替换攻击 概率，分别为 毋= 寿水吉 以及参数为 k = q 2 v - 3 ，b = ( g 一1 ) q 2 ”- 3 , 1 ，= 9 2 啦 的系统认证码，并且给出了编码规则空间服从均匀分布时，成功伪造攻击概率和成功替换攻 击概率，分别为 卑一q ，层= 士q 1 - 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 等人，发现了认证码理论与纠错码 理论的内在联系：在给定e ，层和编码规则数的条件下，构造一个具有最大信源集的认证码， 4 上海大学硕士学位论文 5 等价于，在给定最小距离条件下，构造一个具有最大基数和妈长的纠错码。即，假议j 手在一 个参数为( n , m ，d ) 内的纠错码，使得如果c c ，那么对于所有旯、有- c + 2 1 c 那 么就存在一个对应参数为 i s = 均一，i 占l 叫，毋= 吉，层= 1 - 鲁 的认证码。 1 9 9 9 年，王永传和杨义先对t 分裂认证码与纠错码之间的关系进行了研究，得出了两 个结论。一、给定一个，一t 均等有分裂认证码c ( s ，e ，m ) ，可得到一个i 均等的无分裂认证 m c ( s ，e ，m ，) ，当p ：一t ，e 7 ：! ，且：曝，存在一个对应的纠错码，参数为( ”，d ) = ( i e i ，g ( g 一1 ) 蚓+ g ，i e l ( 1 一 b ) ) ；二、对于一个，一f 均等有分裂的认证码c ( s ，e ，肘) ， 当日= b = i t 时，有i s l 1 e 9 1 一- _ _ 2 1 。但是，如何由纠错码构造出有分裂的认证码，并利用纠错 码揶诊研究有分裂的认证码。仍是需耍进一步研究的问题。 1 1 3 分裂认证码理论的实际背景和研究方法 近几年来，数学家们在研究组合设计时，对分裂认证码的攻击概率下界做了大量的研究 工作。2 0 0 4 年，o g a t a 、k u r o s a w a 、s t i n s o n 和s a i d o 等人在研究三种组合设计e d f 、e b i b d 和分解b i b d 时，通过( “，c ，a ) u - - e d f 构造了最优分裂认证码。下面就他们在研究最优分 裂认证码的过程给予详细的描述。 分裂认证码的定义详见第二章定义1 1 。 在模仿攻击中，定义其成功的最大概率为 只( c ) 2 景野e ( 肌m 0 ) ) 在替换攻击中，定义其成功的最大概率为 b = 一y e m 。a m x p ( m p 0 ) ，廊ee ( g ) , s ；i 班m ( p ) ) ( 乞指发方发送所的概率 由相关文献已给出分裂认证码的攻击概率界。 5 上海大学硕士学位论文 6 吲口曾智 随9 惮呀学 毹e 去 我们说，如果敌方得到一个消息m 后，无法得到信源信息s ，则称该认证码为具有理想 的保密性。用公式来描述就是 p ( s = sm = m ) = 尸( s = s ) ( 对任意的j s ，m m ) 下面将从 ，c ，五) “- - e d f 中得到最优分裂认证码。 定理1 4 如果在交换空间( x ，+ ) 上，存在一个 ，c ，；0 u e d f d i ，见) ，则存在一 个具有理想保密性的分裂认证码，满足命题1 1 、1 2 和1 3 的下界公式，并且 i e i = l m i = 6 ，s i = 七，i p ( s ) i = r ( v e ，5 ) 证明：关于如何从似，c ，五) “- - e d f 中得到最优分裂认证码的过程我们不再阐述，具体 可看文献【3 。关键是计算e 的结果。 p ： 舭忙婴竺竺三竺型：一krmax 耻跏洲( 砌= 业二雨二2 i 黝墙给出了b = 万1 ，矗2 ( 1 ) 文献 3 】仅给出了分裂认证码在参数f e | _ j m | _ 6 ，i s l = 后，l e ( s ) | 厂( v 岛j ) 明确下的最 小伪造概率下界，而本文作者则是通过平衡化的方法，证明了分裂认证码在上述参数更为一 般化的最大伪造概率下界公式，并验证了上述结果。同时，还对分裂系统认证码的最大伪造 概率下界做了深入研究。 1 2 本文主要工作 本文主要做了以下两方面的工作。 6 上海大学硕士学位论文7 一、在第二章中，作者通过一种平衡化方法证明了编码规则概率空间服从均匀分布时， 分裂认证码在参数i s i = 尼，陋l = 6 ，l m i = 1 ，i 勺( s f ) l = 勺o = 1 ，k ；j = l ，6 ) 确定的最大伪 造概率下界公式为| - 骞喜勺厂 卢；并在l e c s ) l = ，的情况下，证明了分裂认证码可转换为 认证码，且最大伪造概率下界公式为= | - r 驯v 6 ； 主、第三章中，作者引入余一法等来进一步研究分裂系统认证码，证明了其在参数i s i = 尼， i e i = b ，l m i = ，确定，以及l 勺( t ) l = 勺o = l ，k ；j = 1 ，6 ) 分别在4 种情况下的最大伪造 概率下界。 7 上海大学硕士学位论文8 第二章分裂认证码 定义2 1 设s 、e 、m 是非空召限集合，分别为源码集合、密钥集合和密文集合。矽为 s x e - - - p ( m ) 的一个映射，其中p ( m ) 为m 的幂集。如果缈满足下列条件： ( a ) ：对于任意的s 1s 2 s 和任意的e e ，有妒( 而，e ) n 缈( s 2 ，p ) = ； ( b ) ： u 缈( s ，p ) = m ， ( s e ) e s x e 则称c = ( s ，e ，m ，缈) 是一个分裂认证码。特别当i 伊( s ，e ) i = 1 ( v ( s ，p ) s x e ) ，则称c = ( s ，e ，m ，缈) 为认证码。 在下文中，我们总假设i s i = 尼，i e l = 6 ，i m i = 1 ，且设s = s l ，一，& ，e = q ，e b ) ， 对任意的( s ，p ) s e ，定义p ( s ) = 缈( e ，s ) ，i e j ( s f ) l = ，；，( f = 1 ，七；j = l ，6 ) ，贝, l j k 2 r = 勺 胁，且记彳( 尼，6 ，r ) = c i c 为具有参数七，6 ， ，肋分裂认证码 。如果勺= l ( v f ，- ，) ， 显然为认证码，则简记a ( k ，b ，v ，r ) = a ( k ，b ，v ) 。 下面，我们举个分裂认证码的例子。 例2 1 s ls 2 q ，) 鸭，鸭) 乞 m 2 ，m 3 m 。，m 6 ，嘞) 巳 ，m 4 m 7 气 m ： ，z 。，聊， m 4 ，m 。) ，m ，) ，l l ，m r ) m 4 ，m 6 ) 已 ，1 2 ，m 3 ，m ， ，m 。，m ， m 3 码，m 。，z ， 我们从例2 1 中可以看出，v e e 有e ( s 1 ) a e ( s 2 ) = 矽，up ( s ) = 确，m 2 ，m 3 ，m 4 ， ( s ，e ) e s 匕 8 上海大学硕上学位论文9 m 5 ，m 6 ，m 7 ，则该c 为具有参数( 2 ，8 ，7 ， ) 的分裂认证码。 对于任意分裂认证码c a ( k ，b ，r ) ，其最大的伪造概率定义如下： 其中e ( ，z ) = p l 存襁s 使得m e o ) 。由于本文总假设p 为均匀分布，则此时 e ( c ) = m 盟! a 丝x e ( m ) 二 一m a x e ( m ) tb 我们定义另( 尼，b ，v ，尺) = m i n p ，( c ) ic a ( k ，b ，v ，r ) ，在本文中我们总假设勺 v ，则有： 引理2 1a ( k ，b ，v ，r ) 矽。 定义2 2 对于c a ( k ，b ，1 ，r ) ，令k ( c ) 2 m 噼ie ( m ) l ，及乙( c ) = m i 卫ie ( m ) i 。若 m m朋m c 满足k ( c ) 乙( c ) + 1 ，则称码c 为分裂平衡码。 下面将证明对任意参数尼，b ，1 ，r ，分裂平衡码是存在的，且任意一个分裂认证码c 彳( 后，b ，v ，r ) ，都可以通过一种平衡化方法转化为分裂平衡码。为方便起见，t i 受i m ( c ) = k ， f m ( c ) = 乙。假设o 乙+ 1 ，且设而y o m ，使i e ( ) i = o 及l e ( 儿) i = 乙。由o l m + l 知，存在ske o z ( x o ) 使而e o ( s o ) 且岳m ( e o ) 。定义 9 2 3 2 2 2 2 3 3 2 2 2 1 2 3 3 l 力e矽 曲 拶 xam = p 蛳 黝 =c 弓 上海大学硕士学位论文 1 0 p o c 而，= 而，五，吒) ，磊c s ，= 。e 。，i 芝；，u 萋；三未， 贝, u e o ( s 。) = y o ，毛) ，且设e = ( e - e o ) u e o ) ，由于y 。萑m ( e o ) ，则知磊 ) n 磊( y ) = 矽，v u ，y s ，“y ，此时有c 7 = ( s ，e ，m ) a ( k ，b ，v ，r ) 。 引理2 2 设e ，e 如上，则 ff e ( m ) l ，v m m 一 x o ，y o i e ( 酬= i e ( m ) l 一1 ，m = x o u e ( m ) l + 1 ， 聊= 其中，e 7 ( ，z ) = e e 7i 存在s s 使所e o ) 。 证明： ( i ) i e 7 ( m ) l = l e ( m ) l ，v m m - x o ，y o ( i ) 若存在s s ，使_ r ，z 爵( s ) 且朋，贝l j n s s o ，故所e o ( s ) = ( s ) ，由此 e ( 扰) = e ( m ) n ( e - - e o ) u e o = ( e ( ，z ) n e 一 ) u e ； = ( e ( m ) 一 e o ) u ， 从而j e ( ，z ) l = l e ( m ) - 1 l + l = j e ( 朋) i ( i i ) 若不存在s s ，使聊e o ( s ) ，则不存在s s ，使聊e ( s ) ，故 e ( 历) = e ( 川) n ( e 一 ) ) ：( ，z ) n e e ( m ) n ) = e ( 川) ； 即l e 7 ( m ) l = l e ( m ) l 。 ( i i ) i e ( 而) l = l e ( x o ) l - 1 ，i e 7 ( ) i = i e ( y o ) i + i 由于而萑m ( 磊) ，敬五( 而) = e ( x o ) n ( e 一 ) ) = e ( x o ) - e o ) ，从而 p ( 而) i = i e ( x o ) - 1 ， 同理有i 0 o ) l - - i e ( y o ) l + 。证毕。 应用引理2 2 ，有 1 0 上海火学硕士学位论文 i e 7 ( m ) j 2 = l e ( m ) 1 2 + 乙( c ) + l 由前知，存在c 1 使得d ( c 1 ) d ( c 1 ) d ( g ) ，其中q 满足 i l u ( c ) l m ( c f ) + l ，i = 1 ，咒- 1 【乙( c ：) 乙( c i ) + 1 ， i = ，l 且有c ( c ) 弓( g ) ，因此，由p i 的定义可知e 为所求的分裂平衡码，故命题得证。 栅1 化：掣 证明：由定理2 1 知，存在码c o 满足乙( c o ) = 乙( c o ) 或0 ( c 0 ) = 乙( c o ) + l 。 ( i ) 若乞( g ) = 乙( c 0 ) ，知乙( c 0 ) = b k 勺i o ，且有 j = lf _ l ， e ( c ：d ) ：m l 6 ( 粪喜，；卢2 t m ( c o ) 6 矧c ) ( i i ) 若乙( g ) = ，m ( c o ) + l ，则设满足i e ( ，1 ) l = 乙的m 有y f 个，其中o f y ，则有 ( v t ) t 。+ f ( 乙+ 1 ) = b k 勺，故v 乙+ f = b k 勺，o l 。令e ( 玉) = 白，吃，e 1 ) ( z ( c ) + 1 ，由前知，存在c 1 使得d ( c 1 ) d ( c 1 ) d ( c ”) ，其中c 满足 iv m ( c ) ( c ) + 1 ，i = 1 ，以一1 ； 【v m ( c 。) ( c 。) + 1 ，i = n 且有e ( c ) e ( c ”) ，因此c “即所求的分裂系统平衡码，故命题得证。 1 9 上海大学硕士学位论文 码的每个子码进行有限次定理2 1 所述的平衡化，使其成为平衡子码，然后再对该码进行定理 3 1 所述的平衡化，从而任何满足条件r = r j 的分裂系统认证码，在进行了有限次系统平衡 化后，都可以转化为分裂系统平衡码。 下艄k , b , v , r ，：学。 设c a s ( k ，b ，u 尺) ，则由前知，有一个分裂系统平衡码c 言= u c o , a s ( k ，b ，尺) 使 e ( g ) c ( 。，( q ) ：m 弓( 口) ，毋( c 0 ) ：生幽剑b ，其叫m ( 口) i _ 【v 后】 或i v k 忆因艄k , b , v , r ) ：掣撇立。 法。 下面，我们来举例说明分裂系统认证码c a s ( k ，b ，v ，r ) ( 其中，r = r j ) 的平衡化方 例3 2 而s 2s 3 q ，z l ，聊： m 6 ，m 7 ，z 9 ，。 吃 m ：，m ， m 6 ，聊7 鸭，z l ： 巳 ，) ，) 。，。 m 2 ，m 。 历，) 竹。，：) 略 鸭，z 。 ， ，z 9 ，： 1 将原模型c = ( s ，e ，m ，r ) a s ( 3 ，5 ，1 2 ，2 j ) 转换为新模型，见下图： 墨 s 25 3 鸭m 6m 7 所r 鸭01，z 1 2 11000ll0lol0 q o 1 l 0o1lo1 00 1 e 2 l00ol10l0 110 乞 2 0 上海大学硕_ ：学位论文2 l o lo l 00110 011 0o110 0 1l 1 00 1 2322l3433l33 2 因v m ( c ) = m ( c ) = 5 ，v m ( c ) = v 2 ( c ) = 3 ，：f f v m ( c ) ( c ) + l ，恰好c l 中的 f ( m 5 ) = 1 ，则可省去余一法的步骤，又因e ( m 6 ) = 3 1 ，因此可直接将c = ( s ，e ，m ，r ) 按 照定理3 1 的方法进行平衡化，使( _ ) = 码，m s ，( j ：) = ，m s ，其他维持不变，则 e = ( e 一 白) ) u 弓) ，通过e e 7 对c 进行平衡化后得到c = ( s ，e 7 ，m ，r ) ，如下图所 不： 岛s 2s 3 川1聊2 刀聊4，z 5m 6聊7m 8m 9m l oi玛2 彳 llo00110l 0 1o 0ll00l101 001 ， 10 【i 】0 1 】【0 】0 10 1 10 乞 呓 0l0lo0l10 011 ， 0ol1oo1ll 00l 岛 2332l2433133 3 因q 已达到平衡，x c c 中的q ，c ：；分别按照定理2 i 的方法进行平衡化，使得承s 2 ) = 聊，聊。 ，讯屯) = 。，铂。 ，其他不变，e - - e 7 一 ) ) u ，通过e 7 专e 。对c 进行平衡化后得到c 。= ( s ，e 。，m ，r ) ，如下图所示： s 1j 2 s 3 聊2聊3聊4聊5m 6所7 聊8 m 9m om l i玛2 耳 lloo 1 】 1 【0 】0 0 】【1 】 10 01 l0 0l1o 1001 lolo100l0 l10 2 l 上海大学硕士学位论文 订 0lo 100l1 0 0 l1 00l1o 011 1 001 233222 33 2233 4 此时，v l ( c 。) = 屹( c ”) = 嵋( c ) = 4 ，c 为所求的分裂系统平衡码，则有 芹( 3 ，5 ，1 2 ， 2 22 、 i 2 22 3 2 2 2i ) = 二- 2 22 5 2 2 2 ) 。- ，r = 三 ，c ，为全是的x 6 矩阵，且满足喜1 w c z = ， 栅描r = 则e s ( k ，：) ：堂： v 七 j ( j 为全是1 的l 6 矩阵) ，且= 口，；满足a i v r ( i = 1 ，七) ， 七 证明：设c - - u c , a s ( k ，b ，v ，尺) ，其中c i ( i = l ，七) 为分裂平衡码，v = m f ( c ) ， = v r i a ( i = 1 ，七) 。由条件置= r j ( i = 1 ，七) 知v f ，r i b v “= 1 ，尼) 。 若u t i 一1 ， 必然存在满足t j + 1 ，反之亦然。不妨 设_ = 一n i ( f = 1 ，t ) ；v j = t j + 玎( = f + 1 ，七) ( 吩为 0 的整数，n i 为0 的整数) ， p 蚴二竺门 b ( v a - n ，r , 一) l bb ( f = 1 ，f ) ，且另( q ) 2 a ( v u 矿+ n , o 一) l ，( ：f + 1 ，后) ，则有e ( c ) 毋( c ：，) 。将c l ，c 2 ，g 按照e ( c 1 ) g ( q ) - - e ( g ) 排列，并设m 。( c ) = ，h ) ，m 。( c ) = m ， ) ，有 掣 刮 吩 。m = ，吖 。 由则 = 、j e ，- 弓 有 。卢 = 阼 ，阍 则 上海大学硕士学位论文 一m 耐赤w 志侈 当n a = 0 时，由e ( c i ) e ( c 2 ) 弓( g ) 知n z2 = n t = 0 ，所以e ( c ? ) = e ( q ) = = 毋( q ) = a b l v ，则结论成立。 下面讨论啊 0 的情况。 若，z i o ，至少有蜘em l ( c ) ，使得i e ( 甄) l 2 。 若不然，跏叫( c ) ，) i = 1 ，贝, q v t 咄2 f l 呻又因为饥u ，所以半 y k ，即，则生+ 盟o ，与啊 0 矛盾。 ，i，i吃 因此，i e ( y o ) 2 。，则仇 0 ，v k = 气+ 以女= ! 生+ 甩女+ r k ， 口 则对任意p e ，存在“( p ) ，v ( e ) m t ( c ) ，i 马u ( e ) v ( e ) ，使得“( p ) e ( s 女) ， v ( e ) 仨 p ( & ) 。因此，可对上述g 通过余一法，不妨设五( & ) ，x t 仨0 ( t ) ( f = 2 ，6 ) ，y o ( _ ) 。 又因m 。( 6 3 r m 女( c ) = ，定义 e t ( s ) = 则类似引理3 2 ，有 彰( s ，) = 巳( s ，) ，- ，七，_ ，1 ； 彰( 0 ) ，i = 2 ，b ；j = l ，尼； ( 彰( s ) 一 五 ) u 1 ，( q ) ) ，i = l ，= 尼； ( 彰( s ) u 五) ) 一 ) ，i = 1 ，- ，= 1 c = ( s ，e 。，m ) ，i m 又c ) l = i m ( c ) l + 1 ，i m z ( c ) i = m 。( c ) i 一1 ，则 e ( c ”) ：匦堕生b 剑 ：b(va-(na-1)r-)l只(c) = 一、，- i - b 。、7 。卢 = 传 ，瑚 因 l 织一 乩咄户 ， ，卜卜乙 五五= u 一 ， c c c m m m = c 吖八 m 上海人学硕士学位论文 因此，l ：r = ，z l 一1 ，形= 刀，一1 ， f 4 v r j a ，经过有限次转化后， 可使d 中的彬= o ( f _ l ，七) ，因此弓( q ) = 另( d ) = = 只( ) ：r a b v l l b 。则有 证毕。 蛳川垆幽b 下面，我们来举例说明分裂系统认证码c 彳s c 七，6 ，y ，尺，c 其中，尺= 三 ，且满足 k 1 w ( f = 1 ，尼) ) 的平衡化方法。 f = l 例3 3 墨s 2 q 码，m ： m 6 ，m 7 ，m s ，m 9 ，m a o ，m a l 乞 m a ，m 4 m 6 ，m 7 ，m 8 ，t r i 9 ，o ，铂2 巳 m 2 ，m 3 m 6 ，鸭，z b ，m a o ，m a l ，2 ) 乞 m 2 ，m 4 ) m 6 ，m 8 ，m 9 ，m a o ，m a l ，z 1 2 吃 m 3 ，m 5 ) 聊6 ，z 7 ，m s ，m 9 ，铂o ，m a 2 ) 1 将原模型c = ( s ，e ，m ，尺) a s ( 2 ，5 ，1 2 ， 26 2 6 26 2 6 2 6 ) 转换为新模型，见下图： 。一 = n ，m 于由 上海大学硕士学位论文 墨s 2 ，7 2 1m 2 ，聊4聊5 m 6m 7m 8m 9 r r 6 0 m l im 1 2 l1oooll1lll0 q l00l0l11l 10 l 吃 011ool l1 0 l1 l p 3 0 l 0 1010ll 111 乞 o0101l111 l0l 巳 232215454534 2 因a = + r 2 = 8 ， = v r , a = 3 ，t 2 = v r 2 a = 9 ，m ，已有e ( _ r ，z 5 ) = 1 ，则对c l 进 行余一法使e ( ) = 1 ，即使得( j 。) = ，l l ，m 2 ，其余不变，则f = ( e 一 ) u 气 ，得 到c = ( s ，e ，m ，r ) ，如下图所示： 墨 s 2 ，m 2聊3聊4m 5聊6m 7m 8玛。 玛i ，z 1 2 彳 1l0001l11ll0 lo0l0lll1 101 0ll00ll10 11l 1 】 10 【0 】0 10l1 111 ， o0l0l 1 l 11 1 0 1 e 5 3321l5454534 3 e ( m 6 ) = 5 1 ，e ( ，1 8 ) = 5 i ，按照定理3 2 对q 中的m 4 ，m 5 转移至q 中，即使得 ( s 。) = _ ，l l ，鸭) ，( s ：) - m 。，鸭，1 8 ，鸭，z l 。，l i ： ，e 5 一( s 。) = _ r ，z l