（基础数学专业论文）利用有限域上一类幂零阵的标准形构造cartesian认证码.pdf

摘要 本文介绍作者在认证码理论方面的研究成果文中第一部分介绍 认证码理论的基本概念；第二部分利用有限域f 。上一类幂零阵的相似 标准形，构作了一个笛卡尔认证码，并计算出该码的所有参数进而，假 定编码规则按照统一的概率分布所选取，该码的成功模仿攻击概率片 与成功替换攻击概率b 亦被计算出来 关键词：认证码，有限域，幂零阵曲标准形 i i i a b s t r a c t s o m er e s u l t sa b o u tt h ea u t h e n t i c a t i o nc o d e sa r ei n v o l v e di nt h e p r e s e n tp a p e r f i r s t l y ，w ei n t r o d u c es o m eb a s i cc o n c e p t s s e c o n d l y , o n 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 ef r o mn o r mf o r mo f o n ec l a s so fn i l p o t e n tm a t r i c e so v e rf i n i t ef i e l di sp r e s e n t e da n di t ss i z e p a r a m e t e r sa r ec o m p u t e d m o r e o v e r ，a s s u m et h a tt h ee n c o d i n gr u l e sa r e c h o s e na c c o r d i n gt oau n i f o r m p 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 s 片a n dp s ，o fas u c c e s s f u li m p e r s o n a t i o na t t a c ka n do fas u c c e s s f u l s u b s t i t u t i o na t t a c kr e s p e c t i v e l y , o ft h e s ec o d e sa r ea l s oc o m p u t e d k e y w o r d s ：c a r t e s i a na u t h e n t i c a t i o nc o d e s ，f i n i t e f i e l d ，n i l p o _ t e n tm a t r i c e s i v 独创性声明 本人声明：所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表的研究成果，也不包含他人为获得东北师范 大学或其它教学机构的学位或证书而取得的研究成果与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 谢意 签名：塾垫丕日期：垫坚墨! 至i 关于论文使用授权的说明 本人了解并遵守东北师范大学有关保留、使用学位论文的规定， 即：学校有权保留、向国家有关部门送交学位论文的复印件，允许论文 被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、 缩印或其它复印手段保存论文 ( 保密的论文在解密后应遵守此规定) 作者签名； 日期： 螂 b 以5 弓l 。“。一 指导教师签名 日期 i i 捌 如j s ，5 5 1 引言 在信息的传输和存储中，安全是至关重要的一般来说，信息系 统的安全，是指保证信息在系统中的保密性、完整性和认证性而认证 码是解决信息的认证问题的一种方法，它由g j s i m m o n s 首先提出： 定义1 设s 、e 和m 是三个非空的有限集合，f ：s e om 是一个映射，它满足： 1 映射，：s e m 是满射， 2 对任意的m m 和e e ，如果存在一个s s 使得 f ( s ，e ) = m ，则这样的8 是被m 和e 所唯一确定的， 则我们称四元组( s ，e ，m ；f ) 为一个认证码 在一个认证码( s ，e ，m ；，) 中，s 、e 和m 分别被称为信源集、 编码规则集和信息集，称为编码映射对8 s ，e e ，和m m ， 如果m = f ( s ，e ) ，则称信源8 在编码规则e 下加密成信息m ，简称m 包含编码规则e ，也说s 是相应于信息m 的信源，基数蚓，l e i 和f m i 称为这个码的参数 认证码用于解决信息传输中的认证问题假设在一个通信系统模 式中，除了信息的发方和接方外，还存在一个敌方，而且敌方掌握某种 技术可以截收系统中的信息，也可以向系统注入信息通常敌方对系统 进行两种攻击：模仿攻击和替换攻击所谓模仿攻击，是指敌方在未观 测到信道中发方给收方的信息条件下，通过信道发送一个他伪造的信息 给收方；替换攻击，是敌方截收到发方给收方的一个信息后，进行分析 并且发另一个信息给收方的攻击 下面我们假设发方和收方互相信任，且共同对付敌方为防止敌 方的这两种攻击，发方和收方可以选用一公开的认证码( s ，e ，m ；，) ，但 在通信前约定一个固定的编码规则e e ，这个选定的编码规则是保密 的，并不被敌方所知如发方想把信源8 s 发送给收方，首先他用选 定的编码规则e 将8 加密为信息m = f ( s ，e ) ，然后把m 通过信道发送 1 给收方当收方接收到信息m 后，首先他要判定m 是否合法，即选 定的e 是否包含在m 中，如果e m ，则收方以为m 。是合法的，然 后在e 下解密得到信源8 ，使得耐= ，( s 。，e ) 由认证码的定义，我们 知道s 是被m 和e 所唯一确定的如果e 隹m ，则收方以为m 是非 法的敌方虽然知道发方和收方所采用的认证码，但不知道发方和收方 所具体采用的编码规则，他便选取信息发送给收方，如果他发送的信息 可以用发方和收方事先约定的编码规则解密，则收方认为该信息是正确 的，即敌方的攻击成功；如果敌方伪造的信息恰与发方发给收方的某个 信息相同，我们认为敌方的攻击成功下面我们分别用局和岛表示 敌方采用模仿攻击和替换攻击成功的概率的最大值，并分别称为成功的 模仿攻击概率和成功的替换攻击概率 举个简单的例子设s = o ，1 ) ，m = o o ，0 1 ，1 0 ，l a ，定义四个不 同的编码规则e o ，e 1 ，e 2 ，e 3 ： 0 00 1 1 01 1 e o 01 8 1 01 e 2 01 e 3 01 这样就构成一个认证码发方和收方在通信前先秘密约定使用的 编码规则，例如，若决定采用e o ，则以发送信息0 0 代表信源0 ，发送信 息1 0 代表信源1 ，我们称信息0 0 和1 0 在e o 之下是合法的，而信息0 1 和1 1 在e o 之下不合法，收方将拒收这个信息假定敌方知道所有的编 码规则，但不知道在特定的时间发方和收方约定使用的编码规则由上 述编码表可看出，敌方若从肘中任取一个信息发给收方，该信息为合 法的可能性是；仅当该信息合法时，收方才接受它，所以敌方模仿发 方欺骗成功的概率为 如果敌方观察到发方发出的一个信息，例如 1 0 ，敌方可知道这时使用的编码规则或为e o ，或为e 2 ，他若想把发方所 送的信源1 窜改为0 ，则他必须在信息0 0 与0 1 中任选一个发给收方， 所发信息合法的概率为；，所以替换成功的概率也是i 1 2 一般地，片和b 尽可能性小并且编码、译码都容易实现的认证 码是好的、实用的认证码计算乃和b 时，采用的公式为 耻m a x 睦掣1 5 + m m li p s = 。，。，m 。m a ，x 。，i i 三j i 呈； i i 宅；：；寺早! h 其中e m 表示编码规则e 包含在信息m 中，即存在信源s s 使得 f ( s ，e ) = m 保密和认证是系统安全的两个重要方面，但它们是两个不同属性 的问题认证不能自动提供保密。保密也不能自动提供认证 定义2 设( s ，e ，m ；，) 是一个认证码，如果对任意的m m ， 总存在唯一的e e 和8 s 使得s ( s ，e ) = m ，其中e 是包含在m 中 的任意编码规则，则称这样的认证码为c a r t e s i a n 认证码 与此对应，我们有 定义3 设( s ，e ，m ；，) 是一个认证码，如果对任意的m m 和 8 s ，总存在e e ，使得s ( 8 ，e ) = m ，即任一信息都能被每个信源在 适当的编码规则下加密而成，则称这样的认证码为完全保密的认证码 c a r t e s i a n 认证码就没有保密功能当敌方观察到信息m 时，他 能断定m 唯一代表的信源8 前面所举的例子即为c a r t e s i a n 认证码 稍作改变，可得到如下具有保密功能的认证码： 0 00 1 1 01 1 e 0 11 e l 10 e 2 10 e 3 01 关于具有保密功能的认证码的进一步研究，可参阅d s t i n s o n 9 3 2 认证码的构造 设日表示含有q 个元素的有限域，其中q 2 是某个素数的幂 a 是域上的n 阶方阵若a “= 0 ，我们称4 为幂零的设尬。( 日) 表示有限域日上所有n 阶方阵构成的集合，g 厶( 玛) 表示有限域上 的n 阶一般线性群 再设 j = ，o 1 。) 。： = i 。 l，i = 2 ，3 1 l o 州 n ( f q ) = a em n ( f q ) ：a ”= 0 ，a n ，n 以 我们如下定义认证码 s = z m = k ( 日) ，e = g l 。( b ) ，：s e _ m ， 8 g _ g s g - 。 其中g g l 。( 日) 由以上定义，知( 日) 中的任意元素在相似变换之下，都能等价 于形如集合j 中的某个标准形，且这种变换之下的标准形是唯一确定 的，所以我们定义的映射，是满射，并且满足c a r t e s i a n 认证码定义中 的其它要求 引理1 设 j = ( 。：j 。 4 即 4 = ( 0 1 ：! j ； ，啦目，i = - ，。，一，n 证明设a = ( o 巧) ，i ，j = 1 ，2 ，n ，并且a 厶= 厶a ，则 0 a 1 1 0 a 2 1 0 a 3 1 of ，0 11 a 2 n il 0 - i _ a b bj i 。1j a l l 1 2 0 1 。、 li 蚴钇。啦nl 1 il j 0j o n l o n 2 o n n a 1 2 a 2 2 a 3 2 0 a n 一1 1a n 一1 2 0 a n la n 2 =享a21霉a22喜a23雾a24至享a2n a 2 1 。a 3 2 。a 4 32a 5 43 2a n n 一1 。0 a 3 12a 4 22a 5 32 = a n n 一2 。0 他毖一 吨 o o n 1 0 i 1 m 眈一0 ，一， | i 2 警芝毗!| 且 因此 n 4 l2 5 22 一0 n n - - 3 o n 一1 1 2 o n 2 20 n n l = 0 ”= a 2 2 = 啦硌= 。= 口”一】n l = a n n a 1 22a 2 32 2a n - 2 n l2a n l n a 1 3 2 2 a n _ 3 n 一12a n 一2 n 口1 n 一1 3 n 凯 a = ( 。1 ：；j 圣 ，。t j j ，i = - ，z ，n a 具有引理中所要求的形式 6 引理2 _ ( f q ) 中所有秩是r 一1 的礼阶幂零矩阵的个数n ( n ，r ) 等于 i g l 。( f q ) l ( q 一1 ) q “一1l g l 。一，( r ) i 证明我们知道j ( 日) 中任意一个秩是r 一1 的礼阶幂零矩阵x 必相似于它的j o r d a n 标准形，即若r a n k ( x ) = r 一1 ，则 x 一( 。) ， 其中 工= 0l 0 即存在peg l n ( b ) ，使得p x p 一1 = f 中秩是r 一1 的n 阶幂零矩阵在下面群在集合的作用下是在同一轨道 里定义群在集合上的作用为： g l 。( f 口) k ( 日) - k ( f q ) 则由群在集合上的作用定理有 ( p x ) _ p x p 。 咖，归篱，( 1 ) 其中g x 是元素x 的固定子群 又l g x i = j g 7 所以我们只 说 是就电 、 0 圳 需计算 g ( 0 即满足下面条件的可逆矩阵p 的个数 p ( 鼻。) 尸一= ( 。) ，- c 。， 其中p 6 g l ( f j 将矩阵p 按照( 。) 的形式分块，设 p = ( p 岛i 。1b p l 。2 ) ， 于是 即 0 一f ，工p 1 1 j ，p 1 2 0 厂00 p 1 1 工= 五p 1 1 ，p 1 2 = 0 ，p 2 1 = 0 通过计算及引理l 可知，最- ，r 2 ，岛- 应满足如下形状 耻卜 m 甜5 1 7 童1 0 。, 2 。j o o 耻( i ；叠封 8 鼻口三：嘞 ，ll、 ii g ( 山。) l 2 q 一1 g 1 q ”一g ”l g l n r j ；j = ( q 一1 ) q 2 ”1l g l 。一，( ) 1 从而由( 1 ) 可得命题结论 引理3 以上构造的认证码的参数吲，i e i 和l m l 分别为 s i = n 一1 ， 吲：g 掣行( 矿一1 ) ， i m i = 脚【q 一i g l 一，( f l b q ) 。i i 丽丽 证明i s l ：几一l 是显然的，i e i = q ! 嘎型且( q t 一1 ) 参看文献 【5 】即得至于i m f 由引理2 计算可得 引理4 设m m ，r a n k ( m ) = r 一1 ，则属于信息m 的编码规则 的个数为 ( q 一1 ) q 2 ”1i g l 。一，( 日) i 证明设 a = ( 4 。) 是与m 对应的信息，则属于信息m 的编码规则的个数为满足矩阵方程 u a u 一。= m ，( 3 ) 的解的个数，其中u g l 。( f 口) 并且我们知道至少有一个矩阵u o g l ( 日) 使得 所以 u o a u f l = m 9 设 w 1 u a ( 陌1 u ) 。= a f = f u g l 。( 日) iu a u _ = m ) g = x g l 。( 日) ix a x = a ) 定义集合f 与g 之间的映射 西：f 斗g u o 酊1 u 其中u o 是满足方程( 3 ) 的一个固定解我们容易指出垂是单、满射， 所以属于信息m 的编码规则的个数等于i c i ，因此，我们只须计算满足 矩阵方程x a x 一1 = a 的解的个数，当然，x g l 。( 日) 事实上，这 等价于计算满足x a = a x 的解的个数，其中x g l n ( f o 由引理 2 可知属于信息m 的编码规则的个数为 ( q 一1 ) q 2 ”1i g l 。一，( 日) i 引理5 设m 1 和m 2 是两个不同的信息，且有共同的编码规则属 于m 1 和m 2 ，则属予m 。和m 2 的编码规则的个数为 ( 口一1 ) q 2 ”。2 n + 1i g l n - - r l ( f 口) 其中r a n k ( m 1 ) = r l 一1 ，r a n k ( m 2 ) = , r 2 1 ，2 r 2 r 1 n 和 证明设 忙( 矗。) 如( 厶。) 1 0 是分别与m 1 和m 2 对应的信息，则所求的属于m l 和m 2 的编码规则 的个数即为满足下面矩阵方程的解的个数，其矩阵方程为 fx a l x 。= m l 1x a 2 x _ 1 = m 2 其中x g l 。( 塌) 我们不妨设r 。r 2 ( 否则m - = m 。，矛盾) ，则用与引理2 类似的 方法，只须考虑如下的矩阵方程 fx a l x 1 = a l 1x a 2 x 。= 喊 其中m ：= x 0 1 m 2 x o ，x o g l 。( f g ) 是x a l x _ 1 = m l 的一个固定 解由引理4 我们可设 其中 x l l ：出口a 2 。 x = ( 而x l 。l x 2 1 = a r l _ ： a 2 a l 兄：是仃一7 l 阶可逆矩阵， 1 ，2 ，礼一r ，且6 1 0 1 , x 1 2 ：i b 。l j o 下面为计算方便，我们首先来求x ，设 1 1 b 2 6 竹一r 。、 0 0 l 1 o o = n ， | | 、一 2 二唱 0 0一o吆 一 一 一 一 0 中 0 0 一o 其 由x 。x = ，可知 所以易知 设 y 1 一，三 l 】2 、 l 2 1l 2 2 l 1 l 置2 + l 1 2 x 2 2 、r l 2 1 x 1 2 + l 2 2 x 如j 2 1 l 1 1 = ( x 1 1 一x 1 2 a 1 局1 ) _ l 1 2 ( x l l x 1 2 x 面l x 2 1 ) x 1 2 x 五1 = x 5 1 x 1 2 x 。- 2 1 l 2 1 = 焉i 1 蜀1 x 5 1 l 2 2 = 糍1 ( x l l 划( 屯o ，。l 如2 2 ) ：? t i l l m 2 2 ) 其中 他拢 l l+ + x x n 组 l l ， 、 0 、， 0 五 ，t ， f f 2 ， a 即喊 | j o x 2 ax为因 我们有 则 ， ，m l lm 1 2 、 ”2 。im z - m z z o rm 。，。、 oj3 呦嘞， ( 厶。) “一， x n 相应于( 如。) 分块，设 = ( r 芋) ， l 1 1 = ( x 1 1 一x 1 2 x 易1 x 2 1 ) - 1 = ( 0 1 0 r 2 2 + 1 a la 2 a l r 孚1 - 1 r l 一血 a r l - - r 2 + 1 嘶1 一n l 、 巳 0 吼 如 。 严 i m r，i他 | | m 以所 因此 = ( 冗 r 1 s 1 t t 一1 ；。= ( r 丁s ) ( 工2 。) ( r 一1 一r ；妥t 一1 r j t 2 r 2 1 0 ) t ：一 。f 0 = f 2 一见k r 一1 s l 丁 0 4 ：研t 。 o 如s t 。1 、 0 因为m 2 是给定的信息，所以m 1 1 不会随x 的改变而改变，又由 r a n k ( m 1 1 ) = r a n k ( m ) = r 2 ，我们必有 其中 m n = ( 名2b 。) 6 n6 1 2 口：一i 6 2 16 2 2 i ：。： n r 2 1d r 2 2 。 b 玎日，i = 1 ，2 ，r 2 ，j = 1 ，2 ，r l r 2 - 于是 即 一 。s t = b 1 4 n 他 仉 并j ，一 所以 ：s = 一b t ：竺犷：； 。二。jl o ，l、 a t l - l i l o ，1 一仰+ 1 a r 2 = b l l a l ，a t 2 - l 。b 2 1 a l ，a 22 6 r 2 一l l a l ， a r 2 + l = b n a 2 + b 1 2 a 1 ， a r 2 + 2 = b n a 3 + b t 2 a 2 + b 1 3 a l ， a r l l 2 b l t a t l r 2 + b 1 2 a r l r 2 1 + 。十6 l n r 2 a l 从而a 2 ，a 3 ，a ，。一1 皆可由a l 来确定所以x l l 的取法数为( q 一1 ) q 再由矩阵x 的形式，我们进行简单的整理计算即可得到所要的结果 1 5 + + 3 n 靶一 0 n n 吣t 眈 ，一 、 1 o 1 0 彬j 舻 吣h | ， = 一f哪。 西西 ” 叶铂o 0 、l， 地 眈吼 0 眈 虮 毗 簪一 吣；|眈。 j | ! | | ! | j (彬彬j舻舭j 纠，。一 为计算和讨论竹和b ，我们引进函数 ，( r ) = ( g 一1 ) q 2 ”1l g l 。一，( 日) ：一1 ) g z n 一，口虹毕业疗( 矿一1 ) t = 1 其中r = r a n k ( m ) + 1 ，m 。( f 口) ，我们有 揣叫- r ( 扩l 1 ) 当r = 2 ，3 ，一，他一1 时，t t r 1 ，且q 2 ，有q ”一 2 ，q ”一1 1 故口”( 矿一1 ) 1 ，所以 f ( n ) - g ，( n 一1 ) - kf ( 2 ) 假定编码规则按照统一的概率分布所选取，则我们由引理3 ，引理 4 和关于函数f ( r ) 的不等式有 b = 旷高斋习 由引理4 ，引理5 和以上结果有 b ( a 2i 定理前面我们构造的认证码的参数为 s i = n 一1 ， e j = g 掣鱼( g i 一1 ) ， m l = r 皂= 2 两齿 1 6 止r盟州k 际 坐训 竺抄祭 笋r 延= j j 假定上面构造的认证码的编码规则按照统一的概率分布所选取，则分别 有 和 b = 旷 p s ：! q 1 7 、p、-p，tti，。 ；弋p； 7 ；i、，、 ， 0卜：“，- 参考文献 f 1 1e n g i l b e r t ，f j m a c w i l l i a m sa n dn j s l o a n e ，c o d e sw h i c hd e t e c t d e c e p t i o n b e l ls y e s t e m t e c h n i c a lj o u r n a l ，1 9 7 4 ，5 3 ，4 0 5 4 2 4 【2 1 g s i m m o n s ，a u t h e n t i c a t i o nt h e o r y s e c r e c yt h e o r y ，a d v a n c e si nc r y p - t o g r a p h y p r o c o fc r y p t o 8 4 ，l e c t u r en o t e s i nc o m p u t e rs 。i n 。8 n o 1 9 6 ，s p r i n g e r ，1 9 8 5 ，4 1 1 4 3 1 4 g s i m m o n s ，ac a r t e s i a np r o d u c t c o n s t r u c t i o nf o ru n c o n d i t i o n a l l y s e c u r e a u t h e n t i c a t i o nc o d e s t h a tp e r m i ta r b i t r a t i o n ，j o u r n a lo f c r y p t o l o g y , 1 9 9 0 ， 3 7 7 1 0 4 z w a n ，c 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 sf r o mu n i t a r y g e o m e t r y ，d e s i g n s ，c o d e sa n dc r y p t o g r a p h y ，1 9 9 2 ，2 ，3 3 5 3 5 6 z w a n ，g e o m e t r y o fc 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 s ，s t u d e n tl i t t e r a t u r c h a r tw e l lb r a t t