（基础数学专业论文）伪辛几何上带仲裁的认证码的构作.pdf

中文摘要 本文利厢伪辛几何椅作了阿类具有伸裁的认证码并计算丁它们的参i t , 并在假定源状态和编码规则都是等概率分市选取时，计算了各种攻击成功的概 窜 关键词：认证码，仲裁人；伪辛几何 a b s t r a c t t w o c o n s t r u c t i o n u f a u t h c n i 】c a t i o n c o d e s w i t h a r b i t r a t i o n f o r m p s e u d e - s y m p l e e t i c g e o m e l r yi sg i v e n ，t h ep a r a m e t e r sa r ec o m p u t e d ，a s s u m i n gt h a n t h ep r o b e b i l i t yd i s t r i b u t i o n o f s o u r c cs t a t ea n de n c o d i n gr u l e s a r c u n i f o r m ，t h e p r o b a i l i t i e s o f s u c c e , s $ 一 f u la t t a o k sa ma l s oc o m p u t e d k e yw o r d s ：a u t h e n t i c a t i o nc o d e sw i t ha r b i t r a t i o n ；a r b i t e r ；p s e u d o s y m p l e l i c g e o m e t r y 第一章绪论 1 1 认证码的研究现状 在信息的传榆和存储过程中，信息的安全是至y e t 要的般的溅信息系 统的安全性是指保证信息在系统中的保密性，完整性和认证性。认证是防止敌 方的主动攻击的重要技术，而认证码是解决信息的认证问题的一种重要方法 假设在一个通信系统模型中，除了信息的发方和收方步卜，还存在一个敌方，敌方 掌握丁某种手段，可以截获信息系统中的信息，也叮以向系统中注入其它干扰 信息通常敌方对该系统进行两种主动攻击：是模仿攻d 嚣二是替换攻击所 谓模宙攻击，即敌方在未观测到信道中发方给收方发送的信息的条件t 瓶过 信道发送十他伪造的信息给收方；而替换攻击是敌方截获到发方给收方的一 个信息。并进行分析后再给收方发送另个信息替换原信息在这个信息系统 模型中，发方和收方使用同一编码规则收方收到信息后，检查是否包含编码规 则。如果包含收方解密信息得到相应的信源，否则收方认为是非法的，并拒绝 它认证码的概念【l 】是gjs i m m o n s 首先在1 9 8 4 年提出的，然后g j s i m m o n s 和d r s t o $ o n 以及我国的裴定一等许多数学家及密码学家分别从不同方面对 认证码进行了研充 尽管认证码能有教地防止敌手对信息系统进行主动攻击，但是不能防止发 方和收方欺骗的情 j 己。比如收方在来收到任何信息的情况下，町以称自己收到 了一个合法信息；类似地，收方在收到十台法信息后，可以声称自己收到的是 另一个信息在上述两种情况f 发方只能认为敌方对系统主动攻击成功另 外，发方发送一个信息后，可以称自已从未发送该信息，这时收方只能认为是敌 方对系统的主动攻击成功为了防止发方和收方之间的相互欺骗，gj s i m m u n s 又提出了异有仲裁的认证码【2 】 在带有仲裁的信息系统模型中，有四个参与者：发方、收方敌方和仲裁 人发方用自己的编码规则龟加密倍源s 得到信息m ，并将m 发送给收方；收 方收到信息m 后，根据自己的编码规则c ，和相应的认证条件判断m 是否合 法，若合法则解密信息m 得到信漂，否则拒绝信息m ；敌方是系统中的非授 权人，他想欺骗发方和收万，发起对系统的攻击，他知道认证系统( 即认证码的 构造) ，但不知道发方选用的编码规则e o 和收方选用的编码规则e ，；仲裁人是 系统中最权威的人，他知道整个信息系统、发方选用的编码规则以及收方选用 的编码规则但他不参d 口通信活动，他唯一的任务是在发方和收方发生争端时 调解争端， 1 9 9 4 年，t _ j o h a n s s o n 得到了带有仲裁的认证码被成功攻击的五种慨率的下 界 1 4 1 近年来认证码的主要研究领域主要集中在以下几个方面 ( 一) 认证码的性质的研究比如，认征码( 包含带有仲裁的认证码) 的各个 参数之间有什么样的关系? 它被成功攻击的各个概率有什么样的下界? 某些类 型的认证码( 如带有仲裁的认证码 除了具有认证码的按性外，还有哪些特性? 这些性质往往对于判断这种类型的认证码是否存在以及存在时如何构作有很 大的帮助 仁：) 认证码的存在性问吐假定巳经给出欲构作的认证码要满足的要求 ( 比如要求其被成功攻击的概率达到组合论下界或者信息论下界) ，研究得合该 要求的认证码是否存在以及存在的条件问题 三) 认证码的构作问题通过认证码的构作，可以进一步确定某种类型认 证码的存在性认证码的构作是认证码研究中既有理论价值又有实用价值的问 题 ( 四) 认证码的计数及分类问匦如果已知某类认证码存在，那么选种认证 码的个数( 当然同构的认证码在计数时算一个) 是多少? 认证码可以按什么规 则进行分类等? ( 五) 认证码之间的关系同题，已知两个认证码，它们是否同构。居否可由其 中的一个得到另外一十对于已经构作出来的c a r t e s i o n 认证码 4 】，能否找到 较诵用的方滋将它们转化为带有仲裁的认证码? ( 六) 认证码的实现问题，我们研究认证码的一个主要目的就是将它们应用 到实际i 自信系统中。这就要求我“j 研究如何实现已有的认证码模型 认证码的构作方面得到的结果在近二十年里异彩纷呈，有很多重要成果， 在这里不再一一叙述由于认证码的构作就其本质来说是组合设计问题，而有 限域上的典型群几何一射影几何仿射几何辛几何，伪辛几f 可，酉几何正交几 何等提供丁较好的组合结构，且易于计数，在六、七十年代就被用于研究区组设 计问题九 年代，万哲先院士玛荣权博士等用有限典型群几何构作丁一系 州没有仲裁的认证码 4 ，6 ，7 ，s l1 9 9 9 年以来，马文下、艺新梅，高锁刚高有、 李瑞虎等叉用有限典型群卜的几何构作丁带有仲裁的认证码【9 ，1 0 1 l ，1 2 ，1 3 1 所有这些对于认证码的研究具有重要的意义同时促进r 有限域卜的典型群的 2 研究 本文利用伪辛几何构作了两类新的带仲裁的认证码从掏作方法上它不同 丁- “往的构作，我相信它对认证码的研究有一定的积极童义 3 | i 1 2 本文研究的主要内容和主要结构 本文在第一章简要介绍了艋年来国内外在认证码方而研究的主要内容及 取得的主要成果 第二章介绍了认证码及伪辛几何的一些预备知识 第三章、第匹i 章利用有限城k 的伪辛几何构作了两类新的带仲裁的认证 码计算丁它的参数并在全部规则服从等概率分布的条件下计搏了这两个认证 码被成功的攻击的五种概率 4 第二章预备知识 下面引入认证码、伪辛几何的一些基本概念和性质 2 1 认证码的基本概念和性质 本节给出认证码的一些基本概念和性质关丁认证码更详尽的性质见文献 2 ，3 定义2 1 设s ， l 是三个非空有僻桌，：5 一朋是一个映托且鹕 足 t i ) 墩射f 是满特 劫砖任意的m m 和b e 若有s 5 使褥f c s ，目= m 刚速样晦s 由m 和曰唯一确定，刖称四元组( s ，m ，) 是一十认证码其中s 。和 m 分剥称作估源集、编码规则集和信息集，称为编码映射 定义厶2 设5 ，卸，e 月，朋是四个非空有限集合，：s 5 t 一朋，9 ：m e 凡一占u 欺诈，是两个映射，六元组p ，印，r ， 以； 9 ) 叫做一个带有仲裁的 仉证焉简称为a 2 一码如果 f 1 ) j ，9 是满船： 封畸任意m m ，e tee 靠若右s s 使得f 临、f - , r 、= m ? 飘s 由m 和e r 唯一确定? 倒著_ p ( 毋，) o 且，( s ，研) 一村则g ( m ，岛) 一s ? 否则( ，岛) 烹 欺诈 其中s ，5 r ，6 r ，m 分别称为信源集，发方编码规则氧收方编码规则篥和信 息集5 钾s r ，a d 的基敷i 别b l ，h f 1 a 4 f 称为这个码的参托 在带有仲裁的信息系境模型中有4 个参加方j 发方，收方故方及仲裁人 定义2 3 在带有仲裁舒认证码中敌方对系统进行的五种袁击夏其概率 f l 旬 f 最方的模仿攻击最方在未观测到任何信息的条件下，发送一个信息络 收方，若幔方书其当作合法信息而接收r 即该信息满足牧方的认证条件，则越 5 河北师范大学同等学力中请硕士学位论文 方的模仿攻击成功假定全部观则服n 等概率分布书敌方模仿攻击成功的最 大概率记为b 则 片= m e a d 丝甾燮 最方的替换攻击敌方在佶道中截获信息后加以分析，再向牧方发送另 一个信息佑息与原信息对应的信源不同j 替换原来的信息，若收方把敌方发遂 的信息当作合法信息而接收则敌方的替换攻击成功韫定全部规则服从等概 率分布将袭方替换攻击成功的置夫概年记为b ，则 fm a x 台于m 和m 7 中的e r 数) 1 b 2 鼢 坚气币而丽产 纠发方的模仿攻击发方发送一个信息给收方j 但这个信息不能由发方的 编码规则加密得到，然后发方否认霄矍送过它：著幔方把该信息当成合法信息 而接收，则称发方的模仿攻击成琉假定全部规则服从等概半分布我们鹊发方 模仿攻击成功的i 大概率记为厅，旦l j f 耻嘴i m “ 合于埘的与毋相关联的毋滋) 竺至丝皇墅竺童堡型 与e t 相关联的e r 数 阳收方的模仿攻击在收方没有收到任何信息的情况下，收方称自己收 到一个信息，若这个信息可以由发方的编码规则加密得到，则称收方的模仿攻 击成功韫定全部规则服从等概半分布将收方模仿攻击成功的最大概率记为 则 = 嘴 芝卷掣) ，”收方的替换攻击收方收到一个合法的信息m 后称自己收到的是另一 个信息 f m 和 r ) 对应的信源不同j ，著们7 可以由发才的编码规则加密得 到，则称牧方的苷挂攻击成功假岩全部y l g q 服从等概率分布，将收方替换攻击 成功的最大概率记为，k ，则 fm a x 奢干村和m ，中与如相关联的岛敷 1 婚一一蛩1 百了面f 甄葫五百鬲瓦夏一f 6 茎些竖塾主兰塑兰堂垄主堕硕走兰堡誊文 2 2 伪辛几何 岛= ( 三，7 ：_ ) 其中一 ( j 1 ) 1 ) ： 屁k ，“( 岛) 一 丁：? & ，”= 岛 定义2 6 设f + 5 是日上的( 2 p + 6 ) 维行向量空间，伪辛群如。+ 。( 晶) 以 曩”x + 。( 目) 一日2 ” 向量空问硝2 蚪4 连同伪辛群只z 卧d ( 品) 在它上面的作用称为e 上的 ( 2 p 十5 ) 维伪辛空问 定义2 7 设p 是伪辛空间可2 叶5 中的一个m 维子空间，我们仍用字母尸 牵记子空间p 的表示则p 岛p 7 同金于下面二种标准型之一： o ，( ” 盯( m 2 s 十曲：f 一叫o l ，中 pj ( 1 ) 一i ( ：1 。) 7 、， 一 hi _“ ， l 们枷司 卸 r r r r 塑! ! 堑蕉主兰璺量至垄士堕婴主堂竺堡圭 其中0 至s 【剖我们称p 为( m ，2 s + t - 5 ；e ) ( t = 0 1 2 ，e = 0 ，1 ) 型子 空问如果j o ) p s 5 p 。r 龠千m ( m 2 3 + t 8 i c l ； f 矽8 2 y + l p 或e , z 。十1 p 分别对应干= 0 或e = t 我们知道，伪辛空间2 “的同型子空同组成它在伪辛群。作用下 的一个轨道 定义2 8 设尸是伪辛空r , 3 砖2 ”+ 毋中的一个子空闻，定义p 的对偶子空l 司 p 1 为 尸1 盘扣：z 砖2 ”) ，z 矿= 0 ，矸 显然有 d i m 尸1 一( 2 v + 5 ) 一d i m p 本文中研究的是d = 2 的硝2 “5 伪辛空同 定义2 9 谖p 是硝2 h 4 中的一个培定的( m ，2 a + t ，8 ；) 型于空间用 m ( m l ，2 s 1 + 丁l ，s l ，“；竹，2 s + ls ；2 v + 定义可2 叶研中的包含于p 的 ( m 1 ，2 s l + q ，巩；e 1 ) 设 l v ( m 1 ，2 s l + - r , ，$ l ，l ；f f f f , ，2 a + 下，s ，5 ；2 v + 5 ) 聋 i m ( m 1 ，2 s l + q ，s l ，e l ；，n 2 日+ f ，s ，q 2 + 6 ) i 引理2 1 0 假设在帮”+ 中( 仇，2 s + t ，s ；e ) 型子空问存在，那么 当且仅当 j ( m 1 2 a x + q ，虮，e i ；，n ，2 s + 7 ，s e ，2 v + 2 ) 妒 ( r ，n ) = ( o ，o ) ( 2 ，0 ) ( 2 ，2 ) 和 。一 o ，。，一骘旦一。一。 兰m 血f m 一掣墙，m 。一华墙。 引理上1 1 刀设2 r m 砧，u 为可2 2 的( r ，0 ，o ：o ) 型于空j 可，m 为包含u 的( m + r ，2 r ，r ，e ) 型干空问，e 一0 或= l j 若m 1 1 3 u c o ) 则 m u u l 为m 中包含u 的唯一的( m ，0 ，0 ；e ) 型干空问 8 第三章带仲裁的认证码的构作， 引理3 1 - 设2 兰r m 竹，0 兰2 s m u 为硝2 时2 的( - 0 ，0 ；o ) 型子空 间m 为包含u 的( m + r ，2 ( r + s ) ，r + f ；e ) 型于空间且射上n u = ( o ) 则 m v l u l 为肘中包含u 的唯一的( m ，2 5 ，s ；s ) 型亍空间 厂u 、 证明：由 1 2 】白匀| 命题1 的证明可知：m iyl 是( f o ，o ，o ) 型子空 ， 问，wcu 1 ，v n u l = ( o ) 令s = u + w 则s = m n u l ，并且由于m 是 ( m + r ，2 p + s ) ，r + s ；f ) 刊子空间，所以 u 5 b u 7 c ，s t y 7 u 9 2 w t 0 u s u v r 盯岛 矿一ly 岛矿7 v s 2 v ry s 2 w 7l = iy 岛矿v s 2 v r w s ：5 r r w s y rw s 2 w 7 ， 0 w s u v r 意意) 由此可知r ( w s 2 w 7 ) = 2 8 ，并且( ；) 是( 2 r , 2 r , “o ) 型子空问赦此 ( 品) 岛( 品) 1 = gw 芝。) 是c m ，。以弗s ，型子空间若s = 。，则 。2 ，+ 1 喜m ，从而岛什l 隹s ，散s 为( m ，2 s ，8 ，0 ) 型子空间，若e = 1 ，则8 知+ l m ，由于u 为( r ，0 ，o ；0 ) 型子空间，则兜叶i 旷， 我们又已知矿n u l = ( 0 ) ，所以句。+ l w ，即句。+ 1 s s 为( m ，如，8 ；1 ) 型子空间若最为m 中包含u 的( m ，2 s ，s ；e ) 型于空闻则最cu 1 ，从而 曷c m n 矿1 由于d i m 马= d i m s 可知= s 练台以上可知s = m n u l 为m 中包吉u 的唯一的( m ，2 s ，ee ) 型子空 间 。鬻 y 河北师范大学同等学力中请确士学位论文 设n = 2 v + 2 ( 3 ) ，2 r m 2 s + i ( p r 固定r 是 2 v 十2 维伪辛空间曩2 。+ 习中取定的( r 0 ，o 0 ) 型子空间f 铲是碍2 中的一 个( 2 vr + 2 ，2 pr ) + 2 ，p r ；i ) 型子空阊 定y 3 2 信源臬 占= s 1 包含r 的( m ，2 5 ，s ；1 ) 型干空间) 发方编码规则集 c t = e l 研为2 ”+ 2 的r 一1 维子空间，且p d + 上岛为( 2 r 2 r ，q o ) 型干空问 收方编码规则集 e r = e n i e r 为砖2 “+ 2 的r 一1 维子空间， 且岛+ 如为( 2 r 一1 ，2 ( r 一1 ) ，r 一1 ；0 ) 型子空问 信息桌 t ； m i m 蔓j ( m + r 2 ( r + s ) ，r + s ；1 ) 型干空问，且m 1 、u 竺( o ) ) m 密函数j ，s 8 r 1 川 f s ，e 曲一s + e t 。 解密函数j 9 ：a 4xe b _ s u 欺诈) ，( m ，岛) = 欺毒：若$ 岛e a 仁c m m 旗中s = 村n 爿 为了证明上述构作得到的6 元组( s ，目，e h ，m ；， g ) 是一个印码，为此 需要 引理3 3 如上构作的，是一个满射 证明：( 1 ) 先证，是一个映射任取s s ，e t g t ，s 是剧中的一个包 含玮的( m ，2 a ，8 ：1 ) 型子空间令 s = ( 品) ，一时w 河北师范大学同等学力申请硕士学位论文 s 岛矿一( 品) 岛( 嚣) = ( 篇d s 妒2 w r ) ( ：w 芝0 ( 州炉( 嬲茹) = - 品缀) 岛村r = ( 昙) 岛( 昙) 7 = ( 量) 岛( 量) 7 tu s d 产u s 2 w 。u s 2 霹 = iw s 2 护w 岛胪w s 2 砰l 局，岛矿局岛7e r s 2 e ；7 ， = b 秦缝) 由于r ( u 岛e 笋) = r ，r ( w s 2 w 7 ) = 2 s ，所以m 是包含r 的( m + r ，2 p + e ) ，r + s 1 ) 型子空间，即m 朋，是一个映射 ( 2 ) ，是一个满射由命题1 可知，对于任取的m m ，都有唯一s s 及 局，即与之对应，并且s = m n 路是唯一的 引理3 4 如上构作的9 是一个满射 证明： ( 1 ) g 显然是一个映射 ( 2 ) 任取信源s = m n u l ，必有一个m 与之对应，由引理的证明可知，这 时必有e re5 n 使得s + 毋一m 。即岛m ，而岛，中必包含有限个e 疗即 1 1 河北师范大学同等学力申请硕士学位论文 西zce r m ，网此对于任取的s 5 必有m 与e r 与之对应由此可得g 是个满射 这时我们由定义2 2 可知构作j 是个a 2 一码 由于伪辛群在同型子空同上的可迁作用，为r 便于下文叙述，不失一般性 可固定 p o = ( ) 0 00 0 ) p 0 00 0 、 对：l 。0 一删0 旦0i k0 00o ( 2 i 证明：( 1 ) 任取m 朋，那么s = m f 尉，s 为m 包含的唯一倍源，夸 口：m 一2 5 一r 一1 由伪辛群在同型子空间上的可迁作用可设 s = ( 品) 1 2 ； ，0 o 0 1 0 r s o 0 o 0 0 一 s o o p o o r 0 0 0 0 0 l + f + 0 0 o 0 o m 一 伊o o o o p ，oo o o r p o o o o ，。 = 堑些堑苎查芏旦量芏垄堕塑主兰堡堕塞 从而m 具有矩阵表示 m = r，叮 一r n + 3 + l r， 一5 一r 11 ( r ) 0 0 0 0 0 0 一耐 0 0 u 0 0 0 0 0 缸) 0 0 0 0 0 o a 0 0 0 0 o j 扣) 0 0 j i ) 0 o 0 0 0 0 o o c 若e c m ，则由p 0 + e 为( 2 7 。，2 r , 一o ) 型子空问可知： rs旷p m + s + 1 西一( 蜀凰 ( 口= m 一2 $ 一r 一1 ) 0o 00 00 l0 00 oe rs一s r11 ，bgd 昱) r 这里x l ，j ，2 ，j b ，日，f 是任意的rx m 矩阵- 从而m 中马，的个数为q 一 即d 一口“ 若日c3 4 , 由于岛+ 凰是( 2 r 一1 ，2 ( r 1 ) ，r l ；0 ) 型子空间所以 p mq - 8q - 1r日f s r1【 风忌岛岛风廊、r 一1 其中( 而岛岛硒) 是，g d ) 的r 一1 维子空间于是( 凡魄岛焉) 的取 法有p 一1 ，r ) f h 由于甩，m ，岛，风，岛可作为任意( r 一1 ) m 矩p 咆所以 b = q l 一1 n ( q 7 + 1 ) 定理3 6 构造j 所得的p 码具有参数 o ) l s l = r 。1 n 二r 一1 ，5 ；2 p r ) ) ( 2 ) 1 5 t l = q 7 2 + 2 ) ( 3 ) 1 6 r i = q ( r - 1 ) 2 ”- r + 2 ) ( r 一1 ，r ) ( 4 ) i 引= 口一如一帕( m r 一1 ，2 s ；2 p r ) ) 口恐。如 r r ，k | l 昧 河北师范大学同等学力申请硕士学位论文 证明由引理2 的证明可知 s = ( 品) 并且是p 0 在对中的补空间的一个( m - - r , 2 s , s ；1 ) 型子空间 此时必有i s i = 1 w | 由于s 是一个( m ，2 s + r ，8 ；1 ) ( 丁= 0 ) ，并且e 2 l w ，则必有8 2 ，+ 2 w ，否则r = 2 这时令s p o ，l 并且w 。具有 r 口一r r口一r10 ( 吼o 肌眠o ) m r 一1 的形式速时( w 2w 4 ) 为2 ( ，一r ) 维伪辛空间的( m r 一1 ，s ) 型子空同而 w z 与w s 任意矩阵由此可得 此时我们可得 ( 2 ) 可设 w l = z c ( m r 一1 ，s ；2 ( 一r ) ) q ( r 一1 】p + s i = 矿4 1 ( f n r l ，s ；2 ( w r ) ) 遣时噩，码，乃，n 为任意矩阵，忙r i = 口t 2 + 咿 ( 3 ) 同理可设 其中子空间岛为，p ) 的r 一1 维子空间皿l ，岛，凡，皿为任意矩阵，则必 有i s r i 一日。+ 2 ) p 一1 ) ( r 一1 ，一 1 4 、1， 2 n r 一死 p ， r 一马 p r 丑 ， = 陆 、， 2 r 一 v ， r 一如 口 r 吼 ，、 = 毋 河北师范大学同等学力中请硕士学位论文 ( 4 ) 由于对任mem ，存在唯一的s s 及n 个马，6 n 使得m 兰 s + 岛。故 m 1 ：坦型 口1 ) q r ( 2 + ( m r 一1 ，5 ；2 p r ) ) 2 矿鬲+ i 1 ) ； 口扣2 一】+ 7 缸一m 一时1 | v ( m r 一1 ，5 ，2 p ) 引理3 7 ( 1 ) 任取岛- 即，上。包含的e r 的个薮为c n ( r l ，r ) ( 2 ) 任取e r 6 b 包含e r 的唧个数d = q 却呻+ 2 + 证t ( 1 ) 设马1 5 7 ，由于局+ 岛，为( 2 t 2 r ，r ；0 ) 型子空间设 若f , nc 曷t ，我们知道e r + p o 是( 2 r 一1 ，2 ( r 一1 ) ，r 一】；o ) 型子空间所以 在e r 中任取一个( r 1 ) 维子空间，都有( r + e 甜是( 2 r 一1 ，2 ( r 1 ) ， 1 ；0 ) 型子空问，所以 c = _ ( r 一1 ，r ) = q 一1 + + q + 1 ( 2 ) 设任取e r e r 。由于p 0 + e r 为( 2 r l ，2 ( r 一1 ) t r l ；0 ) 型子空间 可得 r一rr 一r 2 e r ( 而 飓岛 风 危) r 一1 其中子空间r 为，的( r 一1 ) 维子空问又因为岛，包含量r ，所以设 ，1 一r r 一r 2 岛= ( 三乏芝r 厶4 芝) ”j 1 由b r + p o ) 9 c a ，打，r ，。，型子空间可知( 芝) 必与子空间，相同工如，厶，如 为任意的矩阵，此时我们得到 d = 矿一“ 1 5 、l， 2 五 r 一死 ， r 一乃 vr n ，l 、 | l 毋 河北师范大学同等学力中请硕士学位论文 引理3 8 任取m 2 , 4 及任取f rc f m 中包含e b 的e 的个数为 e = g m 证明：令口一m 一2 s r 一1 ，设肼的矩阵表示与引理3 的形式一样， 其中子空问( 风玩岛风l 是( a ，( ”ge ) 的( r 一1 ) 维子空间，若 耳c m 且目) 如，则有 8口p m + s + 1 rb p 一8 一r 11 飓岛 凡_ r 5 风岛 风岛、r 一1 1 20 3q 40 5 0 b口7q 80 0 ，1 其中( 象荔2 乏) 与子空间似p ，。e ，耜同，印t ，如口s q e 为任意的l m 矩阵，所以e = q ” 引理3 9 若m 和m 2 是共同包含炭方的一个编码规则耳的两个不同估 怠，s 1 与岛分别为m 1 和 如包含的信潦设岛= 岛n s 2 设岛是( k ，2 a ，以1 ) 型千空间d i m s o = 岛则r k m 一1 ，0 兰8 ss ，0 2 s 屯并且有 ( 1 ) 以n 所包含的如教，2 q 一1 ) ( 一l 1 ( r 一1 ，r ) ( 2 ) 任取e r c ( m 1 n m z ) ，m l n m 2 中包含点k 的岛的个数为9 = 口( 扣7 - 1 ) 证明：因任取m = 最- b 毋( f l ，2 ) ，m l 尬。所以昌岛。又田 岛 c ，( = 1 ，2 ) ，故r k m 1 又由于r ( a 6 研) 车2 8 ，r ( 飓岛) = 2 s 并且e 2 p + 1 s l ，e 缸+ i 是，所以e 2 叶l 岛并且2 s = r ( 岛岛岛) 2 s 设s o 为( 七，2 s ，一；1 ) ，p o s t 0m 1 n 如= ( s l n 岛) + 辟一岛+ 正 由于 鲈n 昂= ( o ) “慧1 ，2 ) ，所以( 尬n 盹) 1 n p o ；( o ) 由引理1 可知m n 舰 是f k ，2 f 一+ r ) ，- t - q 1 ) 型子空问在引理3 与6 中，夸m = k ，s = s - 由引理3 可得，m n 肘j 中包含的置r 个数 由引理6 可得g = q 一口l i 1 ，( r 一1 ，r ) 1 6 一 卜 ，岛 r 一 。研 ，r + 一反 一 盯砒 ，如 ，吼 = 岛 ，见吼 ，、 i i 岛 河北师范太学同等学力申请硕士学住论立 定理3 1 0 在构作所得a 。码中着编码规则所及如郡接午概平骨干 连耽则各种攻击成功的概半分别为 r 一万丽而1 而 殆一南 p t = 而南 = 岛 n 。一i 1 证明：( 1 ) 设敌方用信息m 欺骗收方，模仿攻击成功，当且仅当m 包含收 方的编码规则，由于包含的毋i 的数目为b ，而e r 的总数为i 印| ，故 开e 南= 矛q ( 习- 1 ) 两o ：- 苒 - t 硒) f ( r = - l 丽, r ) = 孑面面 ( 2 ) 设敌方截获发方发送的信息 且用 如替换后发给对方，只有当m 包含的信息源鼠与 毛包含的信息探岛不同时，敌方的替换攻击才有可能成 功，由于正kc 岛，c 尬，故敌方的最优策略为选取上昂c = 丸，使 如= 岛+ 磷， 且c l i r a ( s - n 岛) = b 尽可能人k 最大为m 一1 p s ；篇= 击 ( 3 ) 设发方发送一个信息们且不包含发方的编码规则马，m 技发方 作为认证接受当且仅当m e r 由于百k c 岛，故发方要选取肘，使肼尽可 能多的包含e r ( 其中e rc 研) 且m e r 由维数公式可知m 至多包含个e ( e rf - e t ) ，否则必有正 cm 中， 。 l l 竹一面f 而一孑i f _ ：而 ( 4 ) 设收方在宋收到任何信息的情况下。声称收到信息m ，若m 包含发 方的编码规则e t ，则其模仿攻击成功由于e hce ，故收方要选取m 使 m 矗k 因中包古f r 的局，的个数为e ，故 e q ( ”一 1 。i 再丽2 孑i 蕊 1 7 河北师范土学同等学力中请硕士学位论文 ( 5 ) 设收方收到信息肘i 后却声称收到的信息捣。只有当m 1 包含的信源 焉与 如包含的信源不同时，其替换攻击才有可能成功，由于e 8c - 历，c m l ，故收方的最优策略为选取蜀，满足e kce 争c 以使得肘2 鼻f + 睇，设 击，n ( s l n s ) = k ，r ( ( s l n s ) 品( 马n s ) 7 ) = s ，并且七一s 尽可能尢由引理 6 及引理7 ( 2 ) 可得 磊，：牟：一1 口mg 第四章带仲裁的认证码的构作， 设0 m 帆， ，设晶是硝2 维伪辛空间中的( m o ，o ，o ；o ) 型 子空间则j 寸是巧。”2 维伪空问中的( 2 u r + 2 ，2 ( p r ) 十2 ，( p r ) ；1 ) 氆 子空问；p 0 在尉中的补空间是( 2 ( p r ) + 2 ，2 ( v r ) + 2 ，一r 1 ) 型子空问； 设矿是r 中取定的一千n 维子空间， 信源集s ： s = s l 包含v 的蜀中的m 维子空间 发方编码规则集： e t ：钾= e l 黠中的( m 1 ，2 s l ，s l ；1 ) 型子空间，且所n 岛= y 收方编码规则集： e r ：e 且= e r t 胃中的( m l 一1 ，2 ( s t 1 ) ，s l 一1 ；1 ) 型子空间，且e r n p o = y 信息集m ： a 4 一 m i 蹬中的( m + m l 一“2 8 1 8 1 ；1 ) 型子空间，且 mnp o 为包古矿的m 维子空间 对任取占s ，e - c 印定义加密函数 ，：sxe t 川 f ( s ，r - w ) 一s + 毋 对任取m 川，e re r ，定义解密函数 g ：a 4xe r s u 欺诈 州矧= 欺毒：喜岛e n cm m 引理4 1 如上构作的，和9 都是满射 证明：1 ，是一个满射 ( 1 ) ，是一个映射 设任取信源s s ，则s 是包含矿的一个m 维子空问，可记 s 一( 品) ，其中包古在y 在p 0 的补空间 河北师范大学同等学力申请硕士学位论文 任取历，卸，由易，屉礤巾的个( m l ，2 8 1 ，a z ；1 ) 型l 子空问，并且局- np o ! y ，可设 而且，由 可知 研一g ) 其中。c 对，并且。n p o = ( 。) 毋s 2 砰= 曰v 岛s , q v ，。v 岛s 2 。q ，t 、= g。品，) r ( q s 2 q r ) = 2 s 1 ，并且e 2 ，+ l 日 所以对任取s s 及毋e6 t 则 并且 s + 毋；y 。y 。国= f 品q 1 m m l ：- u 阱一睁 l v s 妒 2l 岛俨 l q 岛y 7瑟 ；睡曼) s + e t 是( m + m l 一位，2 s 1 ，日l ；1 ) 型子空问又由scj 寸，e rc 酣，所以 ( s 十_ 毋) c 础而且v p n 尸d ) 一只毋n 户口一v ，而s 是十r 中的饥 河北师范太学同等学力中请硬士学住论文 ( 2 ) 对任取m m ，则m n p o = s 是尸0 中的个包含y 的t ，z 维子空 问即s 1 5 。即s 是个信源，所以对任取m a t ，都有一个s 1 s 与 之对也由mc 蹬，且m np 0 = 岛。可设m = v 毋o 。，其中包 含于v 在岛的朴空问中，印包含于尸。在暗中的补空间中可知d i m ( w ) = m 一让，d i m ( 0 + y ) ；m l ，d i m ( v + w ) = d i m = m 1 由( 1 ) 的证明可知 r ( m s 2 m 7 ) = r ( q s 2 q 7 ) = 2 s 1 综上所述可知置= y 毋q 是一个( ”1 ，2 s l ，8 1 ；1 ) 型子空间，并且肼n 岛一y ， 并且s + e r m 从而我们得到，对任取m 州，都有s 5 ，岛- 5 t ，使得 _ s + e t 二m 综合( 1 ) ，( 2 ) 可知，是个浦射 2 9 是一十浦鼽 ( 1 ) g 显然是一个映射 ( 2 ) 任取s c s ，由于1 的证明可知必存在毋钉- ，使得s + 上矗= m 川义 由于对于任意的f - r 必包含有限个e k e n 使得置rc 局一c m ，所以对任取 的s 最必有m 川，5 m 并且岛c m ，使得g ( m ，e r ) = s ，由( 1 ) ( 2 ) 可知g 是一个满射， 引理4 2 如上构作互是一个a 2 一码 ( 1 y ，g 是一个满射； ( 2 ) 假设s ，是两个不同的信源，它在编码规则f - r j 昂下被编码成同一个信 息，即m = s + e r ，m = p + 正牛，这时必有驴c ( r n m ) = 口，又由 d i m a = d i m 0 = m ，可得口+ = q ，这说明信源口被吖唯一确息 ( 3 ) 若p ( e 。，e r ) o 且，( s 岛) = m ，由g 是个满射可知 ( m ，如) = s 否则 g ( m ，e i ) = 欺诈 由( 1 ) ( 2 ) ( 3 ) 可知构作是一个a 2 一码 由于伪辛群可迁地作用在同型子空间的集合上，为了下面叙述的方便和不失一 河北师范大学同等学力中请硕士学位论文 般性，我们可假设 y 2 ( m m o up m ot r i op 一伽 2 0000 o ) 一mr p m o2 o000l 000 0 ， o0 0o 、 0000 i ，f ”m 1o 00 f ooj ( m 。jol oo op ) j 引理4 3 一个信息中包台的发方编码规则个数为n = q 一砷( m 一哪，包含的 收方编码规则个数为6 = g 旧“) ( m h l ) ( m l 一2 ，凯一l ；m l 一“一1 ，s 1 ；2 ( 1 ，一 m o ) ) 证明：设m 是一个信息即mc 辟= 8 ，且mn 玮= s ，吖是一十 m + 仃h 一口，孙l ，以；1 ) 型子空间，由伪辛群可迁地作用在同类型子空问的集合 上，可设 则 m 一 0 l m 一“ 0 m m 0 o p 一，m 0 0 口 n ，n u伽一 p 一伽 毋一( 苫吴羔羔 椭一o2 0oo 、 o o0j m4 m o 一m 0o o0 o g p m o o0 0 五 u 砷 彳l 一 一 o 0 o o一。加。舯：。 ， 0 0 0 0 u m o n 、 = i _ 醋 昂 讪o。 m o o m 札 山 一。肛 m o ， 一 s u “ 一 一 m 帆 脚、，、， 2 0 o 口2 o 疋 u 产o o ，i、 = m 河北师范土学同等学力申请硕士学位论支 其中( 8ed ) 是( 2 v m o + 2 ) 维伪辛空闫中的( m l 一缸，2 s 】，s 1 ；1 ) 型 干空间由e cm 可知m 羁五磊) 与( 且bgd ) 是相同的子空 间，而n 是任意- 个( m 1 一“) x 忡) 矩阵，所以 设 口= q ( ”1 “】( ”一日 m 一m o my m om o 一m 000 00 r 1局毋0凰 其中( 玩风风】是2 ( v 一“硇) 维伪辛空间中的( m l 一1 一，2 ( s l 一1 ) ，( s l 一 1 ) ；1 ) 型子空闻由于e rc 村，所以( 飓凡凰) 是包古在( b ed ) 中 的( m 1 1 一u ，2 ( a l 一1 ) ，( s l 一1 ) ；1 ) 嘲干牢n 吼其个教为 n ( m t 一“一1 2 ( s l 一1 ) ，( s 1 1 ) ，l ；r n l 一u ，2 s t ，s l ，1 ；2 ( p 一 q ) + 2 ) v ( m 1 一。一2 ，s 1 1 ；t 件l 一“一1 ，8 1 ；2 ( 一，n o ) ) 当( 风风飓) 确定后，咒2 必固定，而r 1 为任意的一十( m 1 1 一句( m 一) 阵，其个数为g ( ”1 - 砷忡“ 所以6 = 口( m l _ 1 “) 坼“) ( m l u 一2 ，s l l ；m 1 一u 一1 ，s 1 ；2 扣一仃“ 定理4 4 构作，f 所得j 4 2 一码具有参数 1 s i = n 7 似，m ，m o ) i t i = g 一) ( 饥川( m 1 ，2 5 l ，s l ，1 ；2 一m o ) + 2 ) i 月f = q 一1 ) ( 删一”( m 1 1 ，2 ( 5 i 一1 ) ，5 l 一1 ，1 ：2 ( 一 幻) + 2 ) 1 m i = 町( m 1 4 ) l 啪o ( 钍，m ，m o ) ( m l ，2 a l ，以，1 ；2 p m o ) + 2 ) 证明：( 1 ) 由a 2 一码的构作可知，| 别是岛中包含一个给定u 维子空问y 的 m 维子空问个数，并且r 是m 维的，所以由【5 】推论1 9 可知 i s = n ( ，m “o ) ( 2 ) 对任取6 钉，局，c 甜且晶n r u 岛，是( m 1 ，2 s l ，5 1 ；1 ) 型子 室问，故可设 u e 1 目 一 n ， 2 0 u 似0 ，、 | | 河北师范大学同等学力申请硕士学位论文 “m n u m o p m o 2 昂= ( p 0 三吴。0 羔三) 。：。 其中( 乃马乃) 是2 p m o ) + 2 维伪辛空间中的( m 1 一u ，2 a l ，8 1 ；1 ) 型子空 间耳为任意的( 仇一u ) ( m o 一“) 阵，所以 i t i = q m 1 州( m 。叫( 而1 ，2 s 1 s l 1 ；2 ( v m o ) + 2 ) ( 3 ) 由z 瑶的规定可设 m 一“一m om o 一r n o 岛= ( ：三三 ：乏 其中( 尼忌风) 是2 ( p 什) + 2 维伪辛空问中的( m - 一u 一1 ，2 ( 3 l 一1 ) ，。一 1 ；1 ) 璀子牵间，r l 为任意的( m 】一u 一1 ) ( m o 一铒) 阵 所以 忙r i q ( m 州1 ) ( 哪“( 仇l 一1 ，2 ( s l 1 ) ，巩一1 ；2 扣一m o ) + 2 ) ( 4 ) 由于每个信息包含唯信a 毛面每十信源包含n 十发方编码规则，故 1 m l a l s c 1 ，i = 掣 一。扣佛，m o ) q ( 啪一砷_ m ) | ( m 1 ，2 s 1 ，s 1 ，1 ；2 ( p m o ) + 2 d 【 ”) ( ) 鲁q ( 仇l - - ) 叫( ，m ，m o ) ( m 】，2 s l ，轧，1 ；2 p m o ) + 2 ) 定理4 5 ，任取f - ree t ，则点吊包含的e 的个敷为 c = n ( m l 一“一2 ，5 1 1 ；m l 1 ，。1 ；2 ( p r n o ) + 2 ) r 甜4 1 t - 2 i , t 正k o 融则包含e r 的j 吕 的个敷为 d = q ( ”一呻( 2 p m o ) 一仇l - 4 - u + 1 ，p m o + 乱一m l + “+ 1 ； 2 p r n o ) 一t 1 7 * 1 + “+ 2 p 一啪+ 5 1 一m l 十口十l ；2 p 一伽) ) 2 4 u 一m 、， 2 o 凡 河北师范大学同等学力申请硕士学位论文 证明：( 1 ) 由定理5 的证明，可设 = ( 7 ：r 0 。嘞0。三三)。一i，,0 一。 o r l嘞墨 冗