（基础数学专业论文）cartesian认证码的构造及矩阵的计数问题.pdf

摘要 摘要 本论文将讨论有限域上一些矩阵的计数，并且利用有限域上一些矩阵构作了 c a r t e s i a n 认证码 第一章，首先计算了ca n 阶幂等矩阵的个数，月阶对合矩阵的个数和秩为r 且满 足a3 = a 的肛阶矩阵a 的个数其次，当v q 的特征数不为2 时，计算了上2 v 阶 ( p ，v p ) 辛对合矩阵的个数：当的特征数为2 时，计算了f q _ k n d p 对合矩阵的个 数， 第二章，利用有限域上4 3 = 彳的矩阵和辛对合矩阵构造了c a r t e s i a n 认证码，并计算 了它们的参数假设编码规则按均匀概率分布时，计算了模仿攻击成功的概率只和替换 攻击成功的概率b 关键词有限域；幂等矩阵；对合矩阵；辛对合矩阵；认证码 a b s t r a c t a b s t r a c t s t h ep a p e rm a i n l yd i s c u s s e st h ec o u n to fs o m em a t r i x e so v e rf i n i t ef i e l d ，a n dc o n s t r u c t s o fc a r t e s i a na u t h e n t i c a t i o nc o d e sb vu s i n gs o m em a t r i x e s i nt h ef i r s tp a r t ，t h en u m b e r so fi d e m p o t e n tm a t r i x e so fo r d e rn ，i n v o l u t o r ym a t r i x e so f o r d e rn t h em a t r i x e ss a t i s f y i n ga 3 = aa n dn o r d e rs y m p l e c f i ci n v o l u t o r ym a t r i x e so v e r f ，a r ed i s c u s s e d ，w h e r et h ec h a r a c t e r i s t i cn u m b e r so ff q i sn o te q u a l2 i nt h es e c o n dp a r t ，t h ec a r t e s i a na u t h e n t i c a t i o nc o d e sa n dt h es i z ep a r a m e t e r sa r e c o n s t r u c t e db yu s i n gs y m p l e c t i ci n v o l u t o r ym a t r i x e so v e rt h ef i n i t ef i e l d w h e nt h ee n c o d i n g r u l e ss a t i s f y i n gu n i f o r mp r o b a b i l i t yd i s t r i b u t i o n , t h ep r o b a b i l i t i e so fs u c c e s s f u li m p e r s o n a t i o n a t t a c ka r ea l s oc o m p u t e d k e yw o r d s f i n i t ef i e l d ；i d e m p o t e n tm a t r i x e s ；i n v o i n t o r ym a t r i x e s ；s y m p l e c t i ci n v o l u t o r y m a t r i x e s ；a u t h e n t i c a t i o nc o d e s i i 河北大学 学位论文独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教 育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了致谢。 作者签名：至赶磅日期：塑! 年旦月生日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存 论文。 本学位论文属于 1 、保密口，在年月日解密后适用本授权声明。 2 、不保密劬。 ( 请在以上相应方格内打“4 ”) 作者签名： 导师签名： 日期：兰! 竺年王月上日 日期：善区2 # 年一工乏胡羔二日 典型群作为群论的一个重要分支，它是许多与矩阵相关的数学分支和其他科学的基 础，目前典型群在组合数学、图论、编码学中的应用也较多典型群包括线性群、辛群、 酉群、正交群和伪辛群五大类，这几类群分别作用在向量空间上的性质的研究统称为典 型群的几何学典型群在近代数学的发展中占有很重要的地位典型群是由d i c k s o n 在 上世纪初开始研究的，其背景是有限单群的分类我国典型群的研究，是华罗庚在上世纪 4 0 年代开创的，特点是在几何背景的指导下，用矩阵方法研究典型群从2 0 世纪5 0 年 代到6 0 年代，华罗庚、万哲先、严士健、王仰贤等人在典型群理论研究方面的工作处于 国际领先地位，被国际同行誉为中国学派6 0 年代，万哲先院士又开创了有限典型群的几 何学及其在组合设计等方面应用的研究领域，取得了国际上前沿性系统成果华罗庚和 万哲先把我国学者关于典型群的结果总结在典型群书中，该书1 9 6 3 年由上海科学 技术出版社出版该书在我国有许多读者，不少人是通过读这本书起步，从事典型群及其 应用的研究的上世纪9 0 年代起，万哲先、游宏、高有等人进一步深入研究有限域上典型 群的几何学的应用，其应用所涉及的内容有：结合方案、认证码、射影码、子空间轨道生 成的格等，有限典型群的结构是典型群研究的另一重要课题，得到许多群论学者的重视， 上世纪9 0 年代国内外在这方面的研究主要集中在有限典型群的极小生成元集与有限典 型群的子群结构方面 关于有限域上典型群几何学的研究实际上是典型群研究的继续和发展，在有限几 何与不完全区组设计的研究这部专著中( 1 9 6 6 年由科学出版社出版) ，万哲先院士带领 他的学生戴宗铎、冯绪宁、阳本傅等用各种类型几何学中的1 维( 或极大) 全迷向子空间 作点( 或称处理) 构造了一些结合方案，并计算了它们的参数，再用任一子空间轨道中的 子空间作区组构造了一些p b i b 设计，也计算了它们的参数，给出了有限域上向量空间中 的记数定理本论文将讨论有限域上一些矩阵的计数 人类历史上很早就开始使用加密技术，古希腊人在战场上传递信件时，就知道将信 的内容加密，这样即使一旦被敌人俘获，敌人也很难得到信件中所包含的军事机密，尽 管他们的加密方法较简单，遇到聪明的敌人，有可能被破译人们使用的加密方法不断改 进，越来越不容易被敌人破译但直到上世纪二十年代，密码技术仍停留在“一张纸一 河- 1 e 大学理学硕士学位论文 支笔”的状态，之后出现了电子密码，使密码技术进入一个新阶段，数学工具在其中开 始发挥越来越重要的作用在第二次世界大战中，密码的应用与侦破成为影响战争胜负 的一个重要因素第二次世界大战后，密码研究出现了一个高潮 除了信息的保密之外，信息的认证是网络通信中信息安全的另一个重要方面当人 们从网络上收到一个信息时，在有些情况下( 例如网络银行) ，收信方十分关心信息发送 方的真实身份，十分关心信息内容在传输过程中是否被他人非法篡改，信息的认证技术 就是要保证信息的来源方的真实性( 不是假冒的) ，保证收到的信息的可靠性( 没有被 非法篡改) s h a n n o n 利用信息论方法研究加密问题，s i m m o n s 在上世纪八十年代利用信 息论方法研究了信息认证问题，提出了完善认证码的概念。他研究的认证模型中包括三 方面：信息的发方、收方以及敌方，发方要向收方发送信息，而敌方想假冒发方，或篡 改发方的信息，用以欺骗收方，达到他的某种目的，在三方认证模型中，假定发方和收方 是互相信任的，我们仅考虑敌方的欺骗攻击敌手想欺骗他们，敌手知道整个认证系统，但 不知道发方和收方所采用的秘密的编码规则做手的攻击有两种：模仿攻击和替换攻击 6 0 年代中期，万哲先是由于数理统计中实验设计( 特别是结合方案和区组设计) 的需 要而研究有限域上典型群的几何学1 9 7 2 年，万哲先在中国科学院数学研究所组织编码 讨论班，介绍国际上编码学和密码学的新发展1 9 7 4 年，g j s i m m o n s 首先提出了认证码 的概念( 参见文 7 ) ，9 0 年代初万哲先用有限域上典型群的几何学构造了许多认证码( 在 这方面工作的还有万的学生冯荣权以及哈尔滨工业大学的游宏等) 本论文利用有限域 上一些矩阵构作了c a r t e s i a n 认证码 本文内容分为两部分：第一章，首先计算了当e 的特征数不为2 时，疋上m 阶幂等矩 阵的个数，胛阶对合矩阵的个数和秩为r 且满足a 3 = a 的n 阶矩阵a 的个数，c 上2 v 阶 辛对合矩阵的个数：其次，当只的特征数为2 时，计算了瓦上n 阶p 对合矩阵的个数。第 二章，利用有限域上满足条件a 3 = a 的矩阵一和辛对合矩阵构造了c a r t e s i a n 认证码，并 计算了它们的参数假设编码规则按均匀概率分布时，计算了模仿攻击成功的概率只和 替换攻击成功的概率只 茎! 耋童堡塑士= 兰堡! 兰墼! ! 茎 第1 章有限域上一些矩阵的计数 1 1 预备知识 设是一个g 元域，其中9 是一个素数的方幂g l 。( ) 表示上的月次般线性群 称甄( ) = r g l 。( ) d e t t = 1 ) 为上的n 次特殊线性群用s p ：。( ) 表示上的 由。阶交错矩阵r ：f k - 。i ，： 定义的。次辛群设p = ( ：三 ：是上个 2 v 2 v 矩阵，则由文 1 知 尸印2 ，( c ) 当且仪当a b 一b a = o , c d7 一z ) c7 = 0 ，a d b c = i ( 1 ) 用1g l 。( ) 【，is l 。( ) 1 ，印：。( ) 分别表示吼。( ) 、s l 。( ) 、印：。( ，j ) 三个 群的计数：即群中所含矩阵的个数( 见文2 ) 设4 是c 上的一个n 阶矩阵如果存在7 1tg l 。( f ，) ，使 t a t ： 最 ，5 2 1 则称矩阵4 在f 上可以对角化，其中 ，如， 是只中t ( t 兰g ) 个互异的元素， s 。= n 设a 是e 上的。一个 阶矩阵，如果a 2 = a ，则称a 是一个幂等矩阵关于幂等矩阵 有引理 引理1 1 一设4 是上的一个秩为，的h 阶幂等矩阵，h 存在丁s 瓯( ) ，使得 丁q 一丁= “。妇训 如果丁2 = j ，丁+ - 1 ，。t g l 。叱) 则称t 是一个”阶对合矩阵关于对台矩阵，有f 如果丁2 = j ，丁+ - 1 ，。t 血。叱) 则称t 是一个”阶对台矩阵关于对台矩阵，有下 列引理 嗣北大掌理学硕士学位论文 ! ! ! ! ! ! ! ! ! ! ! s ! ! 目_ 目自! ! ! ! ! ! ! s ! ! ! ! ! ! s ! ! ! ! ! s ! ! ! ! ! ! 1 0 ， 引理1 1 2 “设是一个特征数不为2 的含g 个元素的有限域，a 是c 上任一个 阶对合矩阵，则存在，s l 。( e ) ，使得 rt ( r ) 丁1 胛2 r ) j ( 2 ) i一，一”j 并且其标准形式( 2 ) 唯一确定 引理1 1 3 设是一个特征数为2 的含口个元素的有限域，a 是只上任个胛阶 对合矩阵，则存在r 血。( e ) ，使得 r 1 爿，= i t p ：i ( p 1 d1 p ) od 0 d i , - i p ) 设是一个特征数为2 的有限域，上相似于( 3 ) 的门阶对合矩阵称为n 阶p 对合 矩阵由文 1 知，n d p 对合矩阵在g 上。( ) 之下的标准形( 3 ) 唯一确定 上的一个矩阵tes p ：，( ) 称为辛对合矩阵，如果t 2 = j 、关于辛对合矩阵有引 理 引理1 1 4 设是一个特征数不为2 的有限域，a 是c 上任一个2 v 阶辛对合矩 阵，则存在r 印：，( e ) ，使得 r ( ，j 其中，= d f 昭( 1 , - - - , 1 ，一1 , - - - , - 1 ) 是由p 个l 和v p 个一1 组成的对角形矩阵 设是一个特征数不为2 的有限域，c 上相似于( 4 ) 的2 v 阶辛对合矩阵称为 ( p ，v p ) 辛对合矩阵由文 1 知，2 vl g r ( p ，v p ) 辛对合矩阵的标准形( 4 ) 唯一确定 引理1 1 5 设是一个特征数不为2 的有限域，a 是只上任一个秩为r 且满足 a 3 = a 的n g r 矩阵- ，则存在r s l 。( 疋) ，使得 丁1 4 t = 并且标准形( 5 ) 唯一确定 ( ，5 ) 、110 吖” ， o p 一 ，一 r 第1 章有限域上一些矩阵的计数 ! 。! ! f ! 。! 目e ! e ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! e ! ! ! 自! ! ! ! ! ! ! ! ! ! ! ! e ! ! ! 一 证明白文 1 可知，存在，es l 。( 只) ，使得 。4 正= ( 舌“a 。2 “i ) 由4 ，；4 得( 五一1 a t i ) ，= 正一1 4 互，从而4 2 ( a l ，4 ：) = ( 4 ，爿：) 注意到( 爿。，a ：) 是行满秩矩 阵，故4 2 = ，再由引理1 1 2 知，存在疋s l ，( ) ，使 瓦。爿。t = 。1r ) 一，。一， ，。p 一 于是取r = 五( 考- ，a i - 1 。a 2 ，贝u 丁e 乩。c ，并且r 1 爿丁= 其中r 是4 的秩，它是由a 唯一决定的，而p 是4 的属于特征值l 的特征子空间的维数， 也是由a 唯一决定的 类似于引理1 1 5 的证日月，根据引理1 i 3 可得下列引理 引理1 1 6 设只是一个特征数为2 的有限域，4 是上任一个秩为，且满足 爿3 = 爿的竹阶矩阵，则存在丁g l 。( ) ，使得 丁一1 爿丁= ( 6 ) 并且标准形( 6 ) 唯一确定 下面利用吼。( c ) 或印：，( ) 在某个集合上的可迁性计算上一些 阶或2 v 阶矩 阵的个数 1 2 计数公式 设瓦是g 元有限域 p 五 ， ， 印 ， p ， 河北大学理学硕士学位论文 a = 九l i l s ； 九。l t3 ； l 这里 ，如，磊是中t ( t g ) 个互异的元素，s 1 , 5 2 ，s ，是f 个正整数，s ，= 记 r = 1 = r 1 a t l t g l 。( ) ) ，那么有下列定理 定理1 1 i ：g ，磊当q h ( q r - 1 nt兀s,2 n 1 ) ( g ，一1 ) 定理1 1 i = 扩“nn ( g l l ) f = 1 j = 】j = l 证明首先求集合m = 丁g l 。( c ) 1 t - l a t = 彳) 所含元素的个数 设t m ，记 于是由t a t = a 即4 r = t a 得 五i五2 五。正： 瓦 瓦， l j f s l 屯 毛= 乃巧， f = 1 , 2 ，t 由于丑，a ：，丑互不相同，因此 = 0 i - 故t= 这说明集合吖含有元素的个数为 l ml = l g l 。( ) 卜i g l 。( ) i g l 。( ) 下面再求i n 映射皿。( ) g l 。( ) 专g l 。( ) ：( b ，r ) 卜t - t b t 是皿。) 在集合g 三。( ) 上的 一个作用n 是这个作用形成的包含矩阵爿的一条轨道，m 是矩阵a 的稳定子群故 6 - 第1 章有限域上一些矩阵的计数 n j 2g l 。( c ) mf 从而得证 由引理1 1 1 和定理1 2 1 可得 定理1 2 - 2 设。圭，”，则上秩为r 的n 阶幂等矩阵的个数是鱼亭! 三 “) 因此，f q 上门阶幂等矩阵的个数是兀善“ ，= oj _ r + t q l 定理1 23 设1 r 门一1 ，是特征数不为2 的有限域，则上以( 2 ) 为标准形的门 阶对合矩阵的个数是丌为“因此，只上即阶对合矩阵的个数是 ，c r + 1 q 一1 瓤r=in s 对q - i m 现在计算只上2 v 阶辛对合矩阵的个数， 类似于定理l 。2 1 的讨论，上2 v 阶( p ，v p ) 辛对合矩阵的个数等于集合 = ，1 j ， r f 丁e ，跏：，c ， 所含的元素的个数，其中( ， 见c a ，令 叫r 酬砷。r = ( j 埘 则l n l 2 f s p ：，( c ) i m i 下面求i m i 设r = ( 乏毛) ：点多。c ，贝u 由，一1 ( ， ，= ，) ，即( ，t = t f ，j 一 河北火学理学硕士学位论文 s ! ! ! ! ! ! ! ! ! e s ! ! ! ! ! ! ! ! s e ! ! ! ! ! s ! ! ! ! ! ! ! ! s ! ! ! ! 。! ! ! 一2置三；j。一p，b=岛b1竺。一p，c=。c，a暑。!，。=d1。一pp p c c p p 1 爿，4 。v 一，l 岛b v 一， l ，。j v 一，“一n v p p ”一p pv p pv p p ”一p 由a j = j a ；a 2 = a 3 = 0 ，类似得下面结论： 爿= 爿14 。) ，b = 占1 蜀 ，c = ( c 1c 。 ，。= ( d 1 。 注意到t 是印：，( c ) 中的元，于是由( 1 ) 得 4 b l2 b i a l ，c 1 d l = d 1 c l ，a i d i b 1 c 1 = i ， a 4 8 4 = b 4 a 4 ，c 4 d 4 = d 4 c 4 ，a 4 d 4 一b 4 c 4 = i 因此，( 善盖 和( 害暑 分别是印：，c ，和印：。，c ，中的元进而得 j m l 2 s p ：，( ) js p ：( ，) ( ) i 定理1 - 2 4 设o s p v ，是特征数不为2 的有限域，则c 上2 v 阶( p ，v p ) 辛 对合矩阵的个数是 兀( g “一1 ) q 一 兀( 9 2 - 1 ) q ，n ( g “一1 ) q “_ 了生蒿一= 9 2 川”力 因此，上2 v 阶辛对合矩阵的个数是q 2 9 “一 r = 0 兀( g “一1 ) n ( 9 2 1 兀( 9 2 定理1 2 5 设是特征数不为2 的有限域，e 上秩为r 且满足一3 = a 的”阶矩阵 爿的个数为 二 n ( g - 1 ) g 7 ”+ 9 一- ；! ：! = ! ! ! - i ：；一 ”。 n ( g 1 ) l - - ( q 一1 ) 证明与定理1 2 1 和定理1 2 4 讨论的方法相似，只上秩为，且满足43 = a 的胛 阶矩阵一的个数为 d 一 ，兀州p 第l 苹有# 域上一些矩阵的计数 亡l 呱( ) i 备l g l ，( f q ) i | g l ，( ) l g l 。( ) i ，兀( g 。一1 ) ；y q 7 ( ”) + ，( w ) 一坦二盟一 删 兀( g 。一1 ) h ( g 一1 ) 下面假设只是特征数为2 的g 元有限域 令足= 仃g l 。( ) l t - 1 p t = 彤，这里p = j 09 f i t j p 1 【00 则世由形如 的可逆矩阵组成，注意群k 到直积群配，( ) 吼。，( ) 的映射 足啼g l ，( ) g l n - 2 p ( ) 曙 正2 五1 五2 是从置到g l ，( ) g l 。，( ) 上的同态满射，同态核k 。由一切形如 r ，五：毛、 o， o 【 1 0e ：，j 的可逆矩阵组成于是fk i = 1 g l ，( ) f | g l 。，( ) k 。f ，再注意从k 。到上的 p ( n - 2 p ) 矩阵全体组成的加群州”2 与“。2 心9 的直和州”2 9 o “。办9 的映 射 f ，五：互0 o，o l 寸瓴，五：) l o 正：，j 是从墨到”“。2 9 o “却“9 上的满同态，同态核k ：由一切形如 、， d d 由 ， 亿 斗 ，ll d k 问北大学理学硕士学位论文 f 舌暑 i oo ，j 的可逆矩阵组成，其中五：是一个p p 矩阵，于是k 1 q 和”2 ，fk ：显然k 2b q p 2 因此，f k l = q 9 。“加1 g l ，( ) i i g l 。，( ) 】于是上的p 对合矩阵的个数为 f g z o ( f g ) f i kj 由上面讨论可得下面定理： 定理12 6 设2 2 p 行，则疋上胛阶p 对合矩阵的个数为 p ( p - 1 ) 丌( g 一1 ) g t 等l n 吲一1 ) 第2 章利用矩阵a ( a 3 = a ) 和辛对合矩阵构造c 白r 把j 尬 认证码 第2 章利用矩阵爿( 4 ，：爿) 和辛对合矩阵构造c a r t e s j a n 认证码 2 1 基本概念 设s ，e 和m 是三个非空有限集，f ：s e 斗m 是一个映射，如果以下条件被满足， 则称四重组( s ，e ， 以) 是一个认证码： 1 ) 厂：s e 斗m 是满射： 2 ) 对任给的m m ，e e ，存在一个s s 使得f ( s ，e ) = m ，这样的s 是由给定的m 和e 唯一确定的 在认证码( s ，e ， 以厂) 中，s ，e ，m 分别叫做信源集，编码规则集和信息集：f 叫做 编码映射，基数i s l ，l e i ，l m i 叫做这个码的参数当m = f ( s ，e ) 时，称信源s 在编码规则e 之下被编码成信息m ，并且为方便起见，称信息m 包含编码规则e 如果这个码还满足： 给定任何信息m ，存在唯一的信源s ，使得对包含在m 中的每个编码规则e 都有 m = f ( s ，e ) ，那么称这个码是一个c a r t e s i a n 认证码假设编码规则集按均匀概率分布选 取，分别用只和b 来表示敌方采用模仿攻击和替换攻击成功的概率的最大值，并分别称 之为成功的模仿攻击概率和成功的替换攻击概率 我们用表示含g 个元素的有限域，这里g 是一个奇素数的幂，上所有即。n 非奇 异矩阵的全体对于矩阵乘法来说组成一群，称为兄上的n 阶一般线性群，记作 吼。( ) ，s l 。( f 0 = 口g l ( ) ld e t t = 1 ) 称为上的胛阶特殊线性群 设x 是e 上的一个n x t r l 矩阵。如果k = 一k ，那么量叫做斜对称矩阵；世叫做交 错矩阵，如果除了k = 一k 之外，还要求k 的主对角线上的元素都是0 当只的特征数 2 时，斜对称矩阵都是交错矩阵 设k 是j z 啪2 v x 2 v 非奇异交错矩阵，上的2 v 2 v 矩阵r 称为关于k 的辛矩阵， 如果 脚= k 上所有关于世的2 v 2 v 辛矩阵的集合，对于矩阵乘法组成一群，叫做上关于丘的 2 v 阶辛群，记作印：，( e ，k ) 1 1 嗣北大学理学硕士学位论文 取世= o p ) 三 ，并将由茁定义的辛群简记作印) 只上的一个矩阵a s p ：，( c ) 称为辛对合矩阵，如果a 2 = 2 2 利用 阶矩阵a ( a 。：a ) 构作c 缸船j 口疗认证码 设集合 n = a。，=7。一，(，一”。，ir = 1 , 2 , - n - 1 。 c 。 p ，蔓n ， 以下设是一个特征数不为2 的有限域，a 是上任一个秩为r 且满足43 = a 的醉 阶矩阵，易见n p ，3 = 虬， 构作方法片，定义集合为信源集s ，集合扛s m 。( ) 1r a n k a = r ，彳3 = a y 瞻g 集m ，集合仳。( ) 为编码规则集e 定义映射f ：s e 哼m ；( 。，丁) p t n ，t 1，=，i一c，一p)(，。一， c 。 r 2 ，p l p 2 等 一p 1 r 2 一p 2 得 0 0 ， 一 f d 叫 e o p d 0 d 第2 章利用矩阵a ( a3 = a ) 和辛对合矩阵构c a r t e s i a n 认证码 丁一1 r = c p t p 2 一p l 乇一p 2 ，1 一，2 一r l 所以两个不同信息包含的相同的编码规则个数是： g 三。( ) 川皿。( ) 川吼。：( ) 吼。( ) g l 。( ) 为 兀p l ( g 一1 ) p n 2 - p 1 ( 叮，一1 ) r 丌z - p 2 ( g 一1 ) n - r t ( g 一1 ) n r l - r 2 ( g m 一1 ) g 旦三1 里二鱼z 蔓生二旦；兰旦! 。塑兀( g 。一1 ) n ( 叮一1 ) 丌( g 一1 ) ( g 一1 ) n ( g “一1 ) g 2 = l j ；】 = 1l = lm = l 假定编码规则按均匀分布选取，由引理2 和引理4 ，得到模仿攻击成功的概率最大值 只：maxi g l p ( f q ) i igl,_，(fq)jig l , _ , ( f q ) 。 l 自一l 】g l n ( e ) l ： 鱼二1 2 ： ( 9 4 一1 ) ( g ”一一1 ) 9 2 ”一3 b 2 雨q 而葫q1 ) q 。 ( + 1 ) ( 9 2 + + ：n ( n ；- 1 ) ，：n n g 掣川腓抄叫州。，錾 z ”1 ”o n ( g 一1 ) l - i ( q 一1 ) 只= 矿斋每 。 ( g ”一1 ) ( g ”一一1 ) 9 2 ”一3b = 雨丽丽1 2 3 利用辛对合矩阵构作c a r t e s i a n 认证码 上的一个矩阵4 s p ：。( ) 称为辛对合矩阵，如果a 2 = ， 设集合 河北大学理学硕士学位论文 p = 1 , 2 ，v 一1 构作方法h 2 定义集合n 为信源集s ，集合翻爿2 = ，4 s p ：，( ) ) 为信息集 m ，集合印。，( ) 为编码规则集e 定义映射：s x e m ；( p , v - pj ) 卜s n p ，s - 1 引理2 3 1 构作方法马确定了一个c 乜r 把s f 口珂认证码 证明设a 是只上的一个2 v 阶辛对合矩阵，则存在r 印：，( ) ，使得 r 一1 4 丁= ( ”一，) ( 1 0 ) 相似于( 1 0 ) 的2 v 阶辛对合矩阵称为2 v d ( p ，v p ) 辛对合矩阵构作方法凰定义的映射 是满射同时，在相似作用下，上式是唯一确定的，这证明信息的信源是唯一确定的，即信 息具有认证性，因此构作方法确定了一个c a r t e s i a n 认证码 引理2 3 2l s v - - 1 ， l e l = 1 3 ( 9 2 7 - o q ” t = l 证明l s v 一1 是显然的 由e = s p ：，( ) ，所以后一结论也成立( 见文 2 ) 引理2 3 3 l m 9 2 巾训 p = q n ( g “一1 ) n ( g “一1 ) 证明设4 是一个信息，则爿2 = ，0 s p ：，( ) ) ，有j 印：，( ) 使得爿= s n 。一，s 一1 若有，s p ：，( ) 也使得一= j n p ，p 厂，则 即n p , v - p j 一1 厂= s - i j n p v _ p s n p , v ：p s 。= 州 p f 由( 1 1 ) 有 fab ief l j lm 得 所以 令a = 则 r 口 所以 由a 1 b ： i a p 。p b 。c ”? p s 一1 ，= le 阡( v ，- ，p 。) ，x p f ( ，v _ ，p 。) 。：! 二) g ，( v 。- ，p 。：9 l m ( ，一p ) 。p ( 。- 】) m n r ( v p ) p j 一p ) b = d = e = g = j = l = m 0 e ，一跏( 。一p ) 0 ( v 一，) 。( ，一p ) = r = 0 c p 。， d日 k p 0x q = ( ) ， ( p p k ( v - - p ) 盆= k 盖) s f s p 2 ，( ) ， a i b ；一日4 i = 0 ，c i d i d - c ：= 0 ，a l d j 一日e j 2 ， - 置“= 0 ，得 由g 纠一 麟= k w 同样可得 a c = c a t 。f h f = h f d 1 q = 0 ，a 1 纠一b i c ；= ， 可得 t n x = x n ，a k f c w = l 。f x ? 一h n 一= 1 f h = h f ，n x t = x n p d p ( v p ) h ( v p ) 。( v p ) 巨 这样( 参主 和( 嚣萎 分别是印：，c ，和印z c 。，c ，中的元，因此j 1 厂所含元的个数 是【s p ：，( ) 【is p 2 ( v - p ) ( ) 1 所以不同信息的个数为 1 7 p 肿 p 一 “ p p 一 三 “ f 叭圳川州 c g 足r 口f j 、0，i， p p ( f ， 一 p ， ， 一v f p ， ， p 岬 ， p f ，、，i、 、，0， d h 上x c g 西r 忡 d d p p p 缸o d rll 、bj h 、i 蜀坊 r l ，。 = 4 q 丑 = ， 、，二， ， f s 凋北大学理学硕士学位论文 砉面s p s 罴p 而 觚 笥i ：，( ) | | ：( 。) ( ) l 一 引理2 3 4 一个信息包含有的编码规则的个数： f s p ：，( ) s p 孙刊( ) i - i ( 矿一1 ) i - i ( g “一1 ) q 9 2 m 训2 引理2 3 5 设彳。、鸣是任意两个不同的信息，其中a 1 是2 v 阶( p 。，v p 。) 辛对合矩 阵a ：是2 v 阶( p ：，v p ：) 辛对合矩阵，且p ，p ：则a 。、a 2 包含相同的编码规则是 l s p 2 ，：( ) l f s p ：( 。m ) ( ) 1 2 i s p 砷。) ( ) 1 证明由已知条件，a - 是2 v 阶( p 。，v p 1 ) 辛对合矩阵，a 2 是2 vg 玢f ( p ：，v p z ) 辛对合 矩阵，设j 是两个不同信息a ，、a ：包含的一个相同编码规则，即 a 1 2 s n n s ，a 2 = 州j ：，：j ，s s p 2 ，( ) 这里不妨设p l p 2 ，否则a = p 2 若有，s p ：。( ) 使得弧 厂1 = a ，强。厂1 = a ：，则f 也是不同信息爿。和a 2 包 含的一个相同的编码规则类似引理8 证明有 s q 厂= 由p l p 2 ，n - p 2 i 1 一p l ，得 令 4 m 。 0 。 0 b p 2 。p 2 0 u p 一 d 岬 州 州 叫 。睾qd苫一 目 墨 g i 铲扩，铲铲 d d o d 印 脚 印 掣d苫啪d警琳 瓦 心 瓦 乙 d r d z 风 k 他 儿 o o 如 n n p o k d p ， 肪 m 也 啦 厶d 艮d 第2 章利用矩阵4 ( 以3 = 4 ) 和辛对合矩阵构造c d m s f 删认证码 a j = 尸 i ，b ，= d 因为s 。，s p ：，( ) ， 所以a ，纠一b i a 卜o , c l 纠一d 1 q = 0 ，a 。纠一b 1 c 卜， 由a ，b ：一b ，a 卜0 ，得 b p f 上 d q 日 r b ，7 f 从雨b d = d b ，p q = q p 7 ，f h = h f ，l t = t l 由c l 叫一d 1 q = 0 ，a 1 叫一b i c ：= ，分别得 u j = 彤，r s = s r ，n x = x n ，v z = z v ， b j 一d u = i ，p s 一缈= i ，f x = h n = ，l z 一r 矿= i 这样，( 孑；) ，( ； ，( ：詈 ，( 吉三 分别是 印：。( ) ，s p 2 ( v - p 1 ) ( ) ，s p z ( 。) ( ) ，s p ：( a 一一( ) 中的兀 所以两个不同信息包含的相同的编码规则个数是： s p ：p ：( ) 印：( ”( ) 1 2 i 印z ( 。) ( ) | 假定编码规则按均匀分布选取，得到模仿攻击成功的概率最大值为 只：m 缸l 望! ! ! 墨生! 望型掣 1 l 印一1 l s p 2 ，( c ) l ：垡鲨二1 2 ( g “一1 ) q 2 ”1 替换攻击成功的概率的最大值为： m 心a x 。一t 坠篙粉倦铲 。l s p l 是g 5 ，! ) 1 1 物m 、( ，。) l q 2 1 q ( 口2 + 1 3 z = d 、， 矿 足 u 河北大学理学硕士学位论文 综上，得如下结论： 定理23 1 利用辛对合矩阵构作了一个c a r t e s i a n 认证码，其参数是 s i = v 一1 ，i e 净兀( g2 。- 1 ) q ”，i m i = j 1 1 p = o 成功的攻击概率分别是 b = 秽靴怊b 老南 球丽 第3 苹结论 第3 牵结论 本文讨论了两个问题：有限域上矩阵的计数问题和c a r t e s i a n 认证码的构造问题 主要完成了以下工作： 对于有限域上矩阵的计数问题，得到下列结论： 1 、设o ， ，则e 上卯阶幂等矩阵的个数是 砉黼鹿扩q ，- 一i 产蚺； 2 、设l sr 月一1 ，e 是特征数不为2 的有限域，则上一阶对合矩阵的个数是 霎鱼赫山； 3 、设o p v ，是特征数不为2 的有限域，2 2 2 v 阶辛对合矩阵的个数是 。n ( q “一1 ) 9 2 “”笔l _ ； ”o 兀( 9 “一1 ) = i 4 、设是特征数不为2 的有限域，上秩为，且满足爿3 = a 的”阶矩阵4 的个数为 ，兀( g 一1 ) g ”小烈了。业_ ； 础h ( g 一1 ) 兀( g 一1 ) j = t= t 5 、当疋是一个特征数为2 的有限域时，设2 2 p n ，则a z n 阶p 对合矩阵的个 数为 删) n ( g 。一1 ) q2 与堡l 一一 1 - i 国一1 ) 利用矩阵4 ( 4 3 = a ) 和辛对合矩阵构造了c a r t e s i a n 乇h i f _ u 4 ，并计算了它们的参 数假设编码规则按均匀概率分布时，计算了模仿攻击成功的概率只和替换攻击成功的 概率b 利用矩阵a ( a 3 = a ) 构造的c a r t e s i a n 认证码的参数为： 河北大学理学硕士学位论文 昨掣，i e i = i = i n 吲- 1 ) g t n ( n - o ，：黟小肿训 利用辛对合矩阵构造了c a r t e s i a n 认证码的参数为 s 卢v 一1 ，i e 卢兀( g “一1 ) q ”， ( g 一1 ) 血( g ，一1 ) n r - p ( g 。一1 ) 由于本论文是对一些特殊的矩阵进行了研究，对于有限域上一般矩阵的计数问题以 及利用矩阵构造c a r t e s i a n 认证码问题是以后要继续研究的问题 糕 p p p 矿 ，脚 = 村 参考文献 1 】 2 3 】 4 5 【6 7 【8 9 【1 0 1 2 】 1 3 】 1 4 【1 5 1 1 6 】 参考文献 华罗庚，万哲先典型群【m 上海：上海科技出版社，1 9 6 3 5 6 1 1 0 万哲先，戴宗铎，冯绪宁等有限几何与不完全区组设计的一些研究 m 】北京：科学出版 社1 9 6 6 i 5 w a n z h e x i a n g e o m e t r yo f c l a s s i c a lg r o u p so v e rf i n i t ef i e l d m l u n d ：s t u d e n t l i t t e r a t u r , 1 9 9 3 2 4 7 8 w a nz h e x i a n ，f u r t h e rc o n s t r u c t i o n so fc a r t e s i a na u t h e n t i c a t i o nc o d e sf r o ms y m p l e c t i cg e o m e t r y j 】n o t h e r e a s t e mm a t h e m a t i c a lj o u m a l ，1 9 9 2 ，8 ( 1 ) ：4 2 0 ， 张海权，游宏抽象代数【m 】长春：东北师范大学出版社，1 9 9 3 1 0 1 8 y o uh o n g ，g a oy o u s o m en e wc o n s t r u c t i o no f c a r t e s i a n a u t h e n t i c a t i o nc o d e sf r o ms y m p l e c t i o n g e o m e t r y s y s t e m ss c i e n c ea n dm a t h e m a t i c a ls c i e n c e s ，19 9 4 ，7 ( 4 ) ：8 5 411 2 s i m m o n sgj a u t h e n t i c a t i o nt h e o r y c o d i n gt h e o r y m 1 c r y t o 8 4 n e wy o r k ：s p r i n g e r v e r l a g ， 1 9 8 5 4 1 1 4 3 1 李莉利用对合矩阵构作的c a r t e s i a n 认证码【j 东北师大学报自然科学版，1 9 9 7 ，2 ：1 5 4 1 8 w a nz h e x i a n ，b e ns m e e t s ，p e t e rv a n r o s e o nt h ec o n s t r u c t i o no fc a r t e s i a na u t h e n t i c a t i o nc o d e so v e r s y m p l e c t i cs p a c e y 1 i e e et r a n s a c t i o no ni n f o r m a t i o nt h e o r y ，1 9 9 4 ，4 0 ( 3 ) ：8 6 9 0 y o u i - i o n g ，n a n j i z h u u s i n gn o r m a lf o r mo fm a t r i c e so v e rf i n i t ef i e l d s t oc o n s t r u tc a r t e s i a n a u t h e n t i c a t i o nc o d e s 川j o u r n a lo f m a t h e m a t i c a lr e s e a r c h e x p o s i t i o n v o l u m e 1 8n o 3 ，3 4 1 3 4 6 a u g u s t1 9