（基础数学专业论文）特征数为2的有限域上的辛对合的结构及其应用.pdf

摘要 本文确定了睾对含矩阵的结檎，势计算了特鬣数为2 酶有限城上酌辛对和矩解的个数，然后 刹用宝构造了一个e 8 毒e r s i 躲认谖码，势计算了该认迁码的备个参数+ 在假宠售源秘缀码规则按 照等概率均匀分布的条件下，给出了认证码的成功模仿攻击概率砰和替换攻击概率b 美键词；c a n e s i 认诞码；辛对台；有限城；群穗集会上的作用 a b s t r a c t i nt h ep r e 吕e n 七p a p e r ，w ed i s c l l s st h ec o n s t r u c t i o no fs y l n p l e c t i ci n v o l u t t i o n0 v e r 矗n i t e 丑e l d s w i t hc h a r f = 2 a tt h es a j et i m e o n ec a r t e 8 i a na u t h e n 七i c a t i o nc o d e 8i so b t a i n e da n da l s oi t ss i z e p a r a m e t e r sa r ec o m p u t e de o m p l e t e l y m o r e 0 、r e ra s 8 u m et h a tt h ec o d i n gr m e sa r ec h 0 8 e a c c o d i n g t oau 1 1 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 i t h eba n dj 0 ，w 1 1 i c hd e 0 t et h 垂i 熹二垦喜i 兰i 、囊耋主枣l i l 耋! j 女 嚣 在信息的传输和贮存过程中。安全问题是至关重要的一般地说，信息系统的安全性是指保证 信息在系统中的保密性，完整性和认证性认证性就是要使接收者能够识别和确认信息的真伪， 防止信息被敌方篡改，删除，伪造等认证是防止敌方这些主动攻击的重要技术，而认证码是解 决信息的认证问题的一种重要方法 定义l设s ，f ，m 是三个非空的有限集，：s e m 为映射，且满足以下条件： ( 1 ) ，是满射 1 2 ) 对任意给的m 时，及e e ，存在惟一的s s 使得，( s ，e ) = m 刚我们称这样的四元组 ( s e ，m ；力为个认证码 在一个认证码( s 。e ，盯；，) 中，s ，e ，m 分剥称为倍源集，编码集，信息集，称为编码映 射对帕f 和m 埘，如果m = ，( s ，e ) ，就称信源，在编码规则e 下加密成信息m 。或简草 地说信息m 包含编码规则e ，也就是说s 是相对于信息m 的信源，基数，i 引l m l 称为这个码 的参数对m m ，令e ( m ) = 例e 是包含在”。中的编码规则 m 1 ，m 2 m ， 令e ( m l ，m 2 ) = e ( m 】) n e ( ”也) 为同时包含在m 1 。m 2 中的编码规则集设四元组( s ，e ，；，) 是 一个认证码，如果对任意的m m ，存在惟一的s s ，使得，( ee ) = m 。其中e 是包含在m 中的任一编码规则，则称这棒的认证码为c a t e 商a n 认证码 信息传输中的认证过程中应注意以下三方面的问题 1 ) 敌方对通信系统的攻击： 假设在一个通信系统模型中，除了信息的发方和收方外，还存在一个敌方，敌方可截收系统 中的信息，也可向系统注入信息通常敌方对系统进行两种主动攻击：模仿攻击和替换攻击所 谓模仿攻击，即敌方在未观测到信遭中发方给收方发送的信息的条件下通过信道发送一个伪造 的信息给收方；而替换攻击是在敌方截收到发方发送给收方的一个信息后，进行分析，破译部分 内容，并发去另一个信息来替换它 2 ) 信息收方对信息的认证： 信息的收方和发方为了防止敌方的以上两种攻击行为，在互棺信任的条件下可选则一公开的 认证码( s ，e ，m ：，) ，且在通信前事先约定好一个固定的编码规则e f 这个编码规则是保密 的，不被敌方所知若发方想把信源s s 发送给收方，首先用选定的编码规则e 将s 加密为信 息m = ，( 。，e ) ，然后通过倍道把m 发送给收方当收方受到信息m ，后，首先要判断t n 。是否正 确，即选定的e 是否包含在m ，中如果e 属于“，则收方认为信息m 是正确的，然后在e 下 解密得到信源s ，使得，( s 7 ，e ) = m ，根据认证码定义中的条件( 2 ) 知。s 7 是被e 和m 唯 一确定的如果e 不属于m ，收方便认为m 7 是伪造的错误的倍息 一确定的如果e 不属于m ，收方便认为m 7 是伪造的错误的倍息 3 ) 成功攻击概率： 敌方虽然知道收方和发方所采用的认证码，但不知道收方和发方具体使用韵编码规则e 若 他将信息m 发送给收方，如果e 属于m ，则收方认为这个信息m 是正确的，这时我们便认为敌 方攻击成功了 ( 如果敌方伪造的信息恰与发方发送给收方的某个信息相同，我们仍认为敌方攻 击成功) 敌方采用模仿攻击和替换攻击成功的最大概率分别称为成功模仿攻击概率和替换攻击 概率，分别用毋和硌来表示 由于本文中我们主要利用了群在集合上的作用来进行计算的，所以在此给出群在集合上作用 的有关知识 定义2 设群g 到某集合m 的变换群阮f 有一同态t ，将群g 的任一元9 对应于s m 的 变换t ( 9 ) ，而对m 进行变换，就说口作用于m 上，且称该同态t 是群g 在集合m 上的一个群 作用。记作 g m _ m ( 吼m ) 一t 0 ) m = 9 。m 定义3 群g 作用在集合m 上，对z m 称集合 以= go 。i 口研 为z 在g 作用下的轨道 m 中两个元素在同一条轨道上，是肘上的一种等价关系，因此两个轨道如与q 或者重合 或者不相交 定义4 群g 作用在集合m 上，对z m ，令 乳n 6 g ( z ) = 9 g igo 。= z ) 称它为群g 作用下群z 的稳定化子 轨道长l 吼j 满足公式i g i = | 研。6 g ( z ) l 仇i 2 辛对合的结构 设k 为体，d 一百为上的反自同构，若看= o ，k ，则称此反自同构为对合性反自同 构，或简称为对合若n n 矩阵b 满足可= 丑，则称之为对于对合n a 而言的日n m m o n 矩 阵如果矩阵日满足冒= 一日，则称之为对于对合。一a 而言的斜耳a m t c t o n 矩阵如果对于任 意的n 维向量z ，都有z b 可= 。+ 瓦，而。，这时称日2 引o n 矩阵b 为迹式日。m t 托m 矩阵 我们把特征数2 的具有对合n a 的体上的斜日n m m m 矩阵及特征数任意的具有对 合n i 的体k 上的迹式h n m m m 矩阵统称为对于对合n + i 而言的日矩阵 2 ( i ) 考虑s 不是交错矩阵的情形根据命题l ，s 一定与如下对角阵合同 0 0 其中a l ，如巧= 如，g o ) ，设r 。n 口一) = r m ( s ) = r 令 p ：f 一砭 。hz 2 其中增= z 2 iz 日) 事实上， 对任意的z ，蠕，若z 2 = 2 ，则0 一目) 2 = o ，于是z = 玑因而p 为单射；又由于瑶为目的子 集，所以p 为同构从而 合同于 即存在可逆矩阵q ，使得 令 o q s q = ( j ：) 一= ( ： 0 q 兰，) x 4 则 从而 设 令 f ： p 一1 t p = l “ i o o f i 越；1 g = pe ，c 岛，| p ( i ；。；) - p l = ( i ； ； 易知g 为乘法群 事实上，设0 是由辛对合构成的集合，就会得到群昂。，( 日) 在0 上的作用 昂。( 晶) 舀，0 令 ( 只t ) 一p t 尸一1 5 一 p 、， 0 0 0 j p o j 0 ， 0 ，0 0 、， 4 4 4 4 m 1 船m 3 3 3 3m 他船m 2 2 2 2 m j m m i lm 沈阳m ， | | p ，0 0 0 ，。o。 | l 已知 令 容易验证是双射从而 ，op ) o 、 ? = p i ojoo 1 p 一， l oo，o i o oo j 乒：s t n 6 s p 2 。( 岛) ( ) s t n 6 昂。( f g ) ( t ) y h p y p 一1 s 执6 品”( f q ) ( t ) l = l 矾n 6 品。( r 】( ) i = l g 根据群在集合上的作用的轨道公式，那么t 的个数即1o rl _ 璺 毒掣 故若计算t 的个数，只须计算f g | 又 即 p 1 1m 2 f 船1 忱2 i 阳1p 3 2 p 4 1p 4 2 p n 十p 1 3 m 1 十p 2 3 p 3 1 十p 3 3 p 4 l + m 3 6 、， o 0 0 ， p o ，0 o 0 0 f 0 0 0 ，。一 | | l p 、， o 0 0 ， p 0 ，0 r o ，0 0 工0 0 0 ，j，t-jl_l-_il、 p p 、 o 0 0 ，一o ，0 0 ，0 0 ，0 0 o ，。一 = 、0， o 0 0 ， p o ，0 r 0 ，o 0 ，0 0 o ，。一 p 、 m 姒m 肌 m l 釜m 蛳 地 蛆 鼢 蛇 p p p pm 船 呈m ，。、lij 0 0 0 j p 0 ，0 0 f o 0 ，0 o 0 ，。 | | 、， o 0 0 ，一0 ，0 f0 f 0 o ，0 0 0 ，j。、， 4 4 4 4m 纯船mm 蛳姗m 2 2 2 2m 抛i 望m m m 船m ，。 、， 弘 m 三m m m 篡m 昭 ： j 至 十m m 灿 ，-ltlilllll_1、 = 、 m 莹粗础 p l l = p 3 3 ，p 4 l = 船1 = 0 ，p 3 2 = p 3 4 = p 2 1 = o 又因为p 是辛矩阵，所以 p ，1 儿f 1 o ，o p i l p i 2 p i 3 p i 4 o o o ，o o ，o 癌2 o p ：2 ll oo o ，l 鸸。西。幽。l 。i ，o oo i 如。叱io jo o p 1 3 p i l + p 1 4 西2 + p 1 1 西3 + p 1 2 西4p 1 4 鸸2 + m l p 5 3 + p 1 2 呓4p 1 1 科l p 1 4 或2 + p 1 1 p 如+ p 1 2 以4 p 2 3 珥1 + p 2 4 p i 2 十p 2 2 硝4p 2 4 畦2 + p 2 2 建4 o p 2 4 硝2 + p 2 2 硝4 p n 西1 o oo p 4 3 一l + p 4 4 砖2 + p 4 2 p i 4 m 畦2 + p 4 2 p ；4 o p 4 4 比+ m 2 p 0 p 2 4 鸸2 + p 2 2 p ：4 = o p 4 4 吐2 + p 4 2 吐4 = o p 2 4 p 如+ p 2 2 p 么= j m 舻：2 + p 4 2 p ：4 = j ( 1 ) ( 篡：) 一熙， 7 、 i 兰阻。阻 3 3 1 3 m 船m m 2 2 2 m 沈0 m n o o o ，j_j_-i = p 、 0 ，0 0 ，0 0 0 0 0 0 ， 0 0 j 0 ，一 | | 、 o叱如叱 o 0 以0 o如如出 ，j。一、， 0 ，0 0 ，0 0 0 0 o 0 0 0 ，0 ，j、， m 姒。灿 i 3 m 船m m m 勉。 舭 m 0 0 0 ，。 吐衄西西 ，。 、 m 勉。 勉 m o 0 o m m o 眦 3 3 1 3 n 抛m m ， 、， 0 ，0 0 ，o 0 0 0 0 0 j 0 o ，0 ，ffi_lll、 = 于是g 中的元素p 形如 且满足( 1 ) 式令 妒：g + s p 。( 目) 对任意的q 2 ( ：篆) e 昂+ 。c 日，存在p = ；曼；量) e g 对任意的p e ”妒，妒( p ) 即p 2 2 = p 4 4 = ，p 2 4 = m 2 = o 所以由( 1 ) 式有 ：；) ip 1 4 = p i l p ；3 jp 1 1 p i 3 = p 1 2 ip l l p i l = ip 1 3 p i l + p l l p i 3 = p 1 4 殖2 + p 1 2 矾4 下面计算矩阵块p 1 1 的取法数 设”l ，坼为m 1 的行向量，则 砘呓= 如= f ：i ；其中- t ，r 1j j 兰眦。触 3 3 1 3 n 船m m 2 2 2 m 抛0 m m o o 0 ，。 、 4 4阮m 2 2船m ， 、 4 4 4 m 阮0 m 3 3 l 3 轨船n m 2 2 2 m m 0 m n 0 0 0 ，。，。 因此p - 1 是可逆矩阵，并且它的行向量是线性无关的，两两正交的单位向量所以p 。，p ，。的行向 量可以如下选取： 从诈( 日) 中任选一非零向量x ，则盈的取法数为矿一l ；设巩为由x l 生成的w ( f 口) 的子空 间，则k ( 日) ；巩。时，在时中任取一非零向量恐。则恐的取法数为口一1 1 ；设为 由墨和尥生成的线性空间，则诈( 岛) = 巩。时，在略中任取非零向量j ，3 ，则函的取法数 为矿1 ；如此继续下去选取扎，墨 令= 缅，则地= 如从而p l l 的取法数为 r ( 矿一1 ) ( r 1 1 ) ( g 1 ) = ( 矿一1 ) t = l p 。喜主；i；常圆蓑瀚强 14就 唯一确定了下面 计算p 1 3 取法数，为此考虑如下矩阵方程a + a7=b其中 b 为已知的一个固定矩阵设 则 nll 012l 幻l n22 a 2 i ln r l o也 f 0 812+02la + a 一= f 。1 2 + b 2 1 o i 口1 r + 坼ln2r+nr2 nlr+脚1、 r = ( q 一1 ) 口”( 4 闷州) 2 i = 1 g i = l ”纠is p 2 ( ，一，) ( 岛) 1 ) ( 口一1 ) 口”2 + ”( 1 一) 2 幽墨峪= 旦坐：竺：竺 h ( 矿一1 ) t = ：l p 蠢刎) 玺h 呻 p ，000，( r ) 00 ，p )0 00，00 000，0 0o00j o0000 的矩阵p 的个数即可 设 o 0 0 一一2 r ) 0 0 ， p = p ： 000，( r ) 0j0j ( r )0 00j 0o 000j0 000o， o0oo0 o 0 0 ( v 一2 r ) 0 0 j ( 2 ) 尹 一博 = “ 艇 就 班 班 戗 p p p p p p 5 5 5 5 5 5 l 2 3 4 i p p p p p pi；m 船m 舢船船 3 3 3 3 3 3i! p p p p p 鼢 2 2 2 2 2 2 m 陇m m 船船m 船船m 船拂 从而 即 由于p 品。( 日) ，所以 p 1 4p 1 5p 1 6 f 它4p 2 5 p 2 6 p 3 4p 3 5p 3 6 p 2 2 船1 0 p 1 2p l l 0 p 6 4p 6 5 p 6 6 令= p l p = p 满足( 2 ) 式) ，易知是一个乘法群 ( 3 ) im 船船im 沈m 4 4 4m 船船 3 3 3m 抛m 2 2 m i 0 1 1 m m 0 o o 蛳! m m 娜i砘m 蛐3 0 0 船 0 0 o 0 0 0 、 f ，0 o p ， ， p 、 y f 0 0 p f ， p 0 0堍吨砖璐 o 0 0破耐0 0 0 0畦畦0 0 0砖砖西砖嘲如如比如如 西西西西西矾 0 0o ，o o 0 0 0 o 0 f 0 0 0 0 0 0 0 0 o 0 f 0 0 0 o 0 0 0 j j 0 0 0 6 6 6 m 船船：bm 船船 4 4 4m 抛m 3 3 3m 沈乳 2 2 n 阮0 m m 0 6 0 o !耽m 砧i 仡m m 3 0 0 m 0 0 0 0 0 0 0 0 0 ，o o o 0 0 0 0 j 0 0 0 0 0 0 0 o 00 ， 0 0 0 0 o o o j ，0 o o 0 o0 ，o 0 o 0 0 0 0 f o 0 0 o 0 0 o 0 0 0 ， 0 0 0 o o 0 0 f，0 0 0 0 0璐砖菇砖 0 0 0西西0 0 o o畦畦0 o o如幽如、善如如如如如如 l 2 3 4 5 6西西西西或西 3 3m 阮 2 2m 沈 1 1m 讫 l 莹o 0 0 0 0 o m 0 0 0 0 代入( 3 ) 式，得到 与( i ) 中求p 2 3 的取法数相同，p 1 3 p 1 6 ，m ，p 2 6 的取法数均为口r ( ”。) ，p 1 5 的取法数为矿；与( i ) 中求p 1 3 的取法数相同，p 1 4 ，p 2 5 的取法数均为g r ( r + 1 ) 2 从而 k e rg i = q r 2 口r ( 件1 ) 2 矿( r + 1 ) 2 q 4 r ( ”一2 r ) = 矿( 4 ”一阶+ 1 ) 因为9 为满射，所以根据群的同态基本定理，g 同构于南于是 = i g 川妇9 l = i ，( 日) | | 。( 玛) “。+ 1 ) rv 一2 ” 一( q “一1 ) ( 口 _ 1 j = l 所以此时辛对合t 的个数为 幽墨峪= 墨! 竺竺： m 卉( g a 1 ) 综上述，辛对合t 的个数为 j 墨堑( 墨! j 。l 勤：f 墨! j | g ii v i h( 口巧一1 ) g ( 卜1 ) 2 兀( g 可一1 ) 矿一一1 ) = 里：二= = 一+ 里= 告一1 1 ( 口i 一1 )丌( 口2 i 一1 ) f 1 ( 一1 ) g 小_ 1 ) 2 百( q2 f 一1 ) 矿) 2 + 矗( 矿+ 1 ) j 十r + 1= p 一2 r + 1 l = l 兀( q “一1 ) ；= 1 3 构造认证码 1 9 8 4 年，gj s i m m o n s 首先提出了认证码的概念自提出认证码至今，世界上许多数学家 和密码学家都对它进行了研究，这些研究主要集中于认证码的性质和构造问题构造方面问题很 多，例如假定某类认证码存在，如何将它们构造出来有时也通过构造反过来确定了某类认证码 1 4 l | | | = 0 o 吐畦砖 | | | | ”篡笼协 斗斗t t蚶蚶州埘“=1|叱、誉、誉畦殖m 融m + + + + + 船船m 船5 呈 结论 本文确定了睾对台矩阵的结构，并计算了特征数为2 的有限域上的辛对和矩降的个数，然后 帮j 甭它褐造了一个g 矗t e r s i m 议溢弱，辫计算了该议证礴酚各个参数在假惫信源和编褥规涮按 照等搬率均匀分带的条件下，绘出了认证码螅成功模傍攻毒概率岛和鐾换攻击概枣段。 本文用的主要刨新点在于在计算道程中巧妙选取遗当的已知群( 集合) ，匈要计算的群( 集合) 建立群嚣态f 涣翁) ，这蓬群鬻态或尝是满蠢态，或耱是褥梅( 浚射巍双豺) ，及精茛聚本 # 常繁杂静 计算变褥简单明了，大大简化了计算过程，同时也减少了出错的机会。 2 l 参考文献 s l m m o gj a u t h e n t i c a t l o nt h e 。r y a o d l n gt h e 。h a d v a n c e 8i no y p t o l o g 矿8 4 l e c t u r en o t c si n e o m p u t e rs c l e n c e ，1 9 8 j1 9 6 ：4 1 1 4 3 1 2 ly o u ，n 趾jz u s i n gn o r m