（基础数学专业论文）抛物矩阵在glnfq）作用下的标准型及其应用.pdf

摘要 令e 是特征为p 的有限域，其中p 为不等于2 的素数 a 是 日上的抛物矩阵，即a p = i 本文中作者讨论了n 凡( n 茎p ) 阶抛物 矩阵在g l 。( f 口) 作用下的相似标准型进而利用一部分p p 阶抛物 矩阵的相似标准型构造了c a r t e s i a n 认证码，计算出了认证码的所有参 数，并在假定编码规则按照统一的概率分布所选取时，计算了成功模仿 攻击概率马和成功替换攻击概率b 关键词：有限域，抛物矩阵，相似变换，矩阵标准型，c a r t e s i a n 认证码 i i a b s t r a c t l e teb eaf i n i t ef i e l d ，a n dc h a r f q = p t h em a t r i xai sc a l l e d p a r a b o l i cm a t r i xi ft h e r ei s a p = if o ra ne l e m e n tao fg l n ( b ) i n t h ep r e s e n tp a p e r ，w ec o n s i d e rt h ep r o b l e mo ft h en o r m a lf o r mo ft h e p a r a b o l i cm a t r i x i ng l n ( 日) o n ec o n s t r u c t i o no fc a r t e t i a na u t h e n t i c a - t i o nc o d e sf r o mt h en o r m a lf o r mo fp a r a b o l i cm a t r i c e so v e rf i n i t ef i e l d s a r ep r e s e n t e da n di t ss i z ep 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 e t h a tt h ee n c o d i n gr u l e sa x ec h o s e na c c o r d i n gt oau n i f o r mp r o b a b i l i t y d i s t r i b u t i o n ，t h eb a n dp s ，w h i c hd e v o t et h el a r g e s tp r o b a b i l i t i e so fa s 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 ls u b s t i t u t i o na t t a c k r 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 ：f i n i t ef i e l d ，p a r a b o l i cm a t r i x ，s i m i l a rt r a n s f o r m a t i o n ，n o r m a lf o r m ，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 i i i 独创性声明 本人声明：所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表的研究成果，也不包含他人为获得东北师范 大学或其它教学机构的学位或证书而取得的研究成果与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 谢意。 签名 赵蟹 日期 2 - , l ，e 奠z 乙 关于论文使用授权的说明 本人了解并遵守东北师范大学有关保留、使用学位论文的规定， 即：学校有权保留、向国家有关部门送交学位论文的复印件，允许论文 被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、 缩印或其它复印手段保存论文。 ( 保密的论文在解密后应遵守此规定) 作者签名：垄兰翌垫指导教师签名南乏睇髓丛垫 日期：迎竺! 玉兰! 日 期：皇翌尘兰 1 引言 华罗庚等在文【1 】中给出了抛物矩阵的定义，并且确定了体上的 2 2 阶抛物矩阵在相似变换下的标准型在本文中作者给出了特征为 p 的有限域上n 礼( 扎p ) 阶抛物矩阵在相似变换下的标准型，进而 利用其中一部分抛物矩阵的相似标准型构造了c a r t e s i a n 认证码，并且 计算出了该码的所有参数及成功模仿攻击概率和成功替换攻击概率 因为在文f 1 】中已给出p = 2 时的结果，因此本文通篇假设p 为 不等于2 的奇素数令f 是有限域，特征数是p ，l f i = q ，显然，q 为 素数p 的幂 引理1 1若c h a f f = p ，则扩= l 在f 上有p 重根，即 护一1 = ( 石一1 ) p 引理1 2 若c h a r f = p ，a g l 。( ) ，则印一i = ( a 一，) 在信息的传送和存储中，安全是最重要的一般来说，信息系统的 安全，是指保证信息在系统中的保密性、完整性和认证性保密性，即 使非授权人不能提取系统中的信息，通常用密码方法来解决这一问题； 完整性，即表示在有干扰的条件下，系统保证能恢复接收到的信息和原 来发送的信息一致，这常借助于纠错码来完成；认证性，即接收者要能 够识别和确认信息的真伪，防止信息被敌方篡改、删除和伪造等，认证 是防止敌方这些主动攻击的重要技术，而认证码是解决信息的认证问题 的一种方法，它由g j ，s i m m o n s 首先提出 定义1 3 设s 、e 和m 是三个非空的有限集合，：s e m 是一个映射，它满足； 1 ) 映射，：s e m 是满射， 2 )对任意的m m 和e e ，如果存在一个s s 使得 ，( s ，e ) = m ，则这样的8 是被m 和e 所唯一确定的， 则我们称四元组( s ，e ，m ；，) 为一个认证码 在一个认证码( s ，e ，m ；，) 中，s 、e 和m 分别被称为信源集， 编码规则集和信息集，称为编码映射对s s ，e e ，m m ， 如果m = ，( s ，e ) ，则称信源s 在编码规则下加密成信息m ，简称m 包 含编码规则e ，也说8 是相应于信息m 的信源，基数吲、i e i 和i m i 称为这个码的参数 认证码用于解决信息传输中的认证问题假设在一个通信系统模 式中，除了信息的发方和接方外，还存在一个敌方，而且敌方掌握某种 技术可以截收系统中的信息，也可以向系统注入信息通常敌方对系统 进行两种攻击：模仿攻击和替换攻击所谓模仿攻击，是指敌方在未观 测到信道中发方给收方的信息条件下，通过信道发送一个他伪造的信息 给收方；替换攻击，是敌方截收到发方给收方的一个信息后，进行分析 并且发另一个信息给收方的攻击 下面我们假设发方和收方互相信任，且共同对付敌方为防止敌 方的这两种攻击，发方和收方可以选用一公开的认证码( 只e ，：，) ，但 在通信前约定一个固定的编码规则g e ，这个选定的编码规则是保密 的，并不被敌方所知如发方想把信源s s 发送给收方，首先他用选 定的编码规则e 将s 加密为信息m = f ( s ，e ) ，然后把m 通过信道发送 给收方当对方接收到信息m 后，首先他要判定t $ 是否合法，即选 定的e 是否包含在m 中，如果e m ，则收方以为m 是合法的，然 后在e 下解密得到信源s 使得m = ，( s ，e ) 由认证码的定义，我们 知道是被m 和e 所唯一确定的如果egm ，则收方以为m 是非 法的敌方虽然知道发方和收方所采用的认证码，但不知道发方和收方 所具体采用的编码规则，他便选取信息发送给收方，如果他发送的信息 可以用发方和收方事先约定的编码规则解密，则收方认为该信息是正确 的，即敌方的攻击成功；如果敌方伪造的信息恰好与发方发给收方的某 个信息相同，我们认为敌方的攻击成功下面我们分别用片和b 表 示敌方采用模仿攻击和替换攻击成功的概率的最大值，并分别称为成功 的模仿攻击概率和成功的替换攻击概率 2 一般地，b 和岛尽可能的小并且编码，译码都容易实现的认证 码是好的、实用的认证码计算片和b 时，采用的公式为 p r = 。m 。a m x 鳖铲，m ml e l b = m ，r n t m 。m a x ，。；。，丛三彳蠢乇 ；群， 其中e m 表示编码规则e 包含在信息m 中，即存在信源s s 使得 ( s ，e ) = m ， 保密和认证是系统安全的两个重要方面，但它们是两个不同属性 的问题认证不能自动提供保密，保密也不能自动提供认证 定义1 4 设( s ，e ，吖；，) 是一个认证码，如果对任意的m m 总存在唯一的s s 使得f ( s ，e ) = m ，其中e 是包含在m 中的任意编 码规则，则称这样的认证码为c a r t e s i a n 认证码 与此对应，我们有 定义1 5 设( s ，e ，m ；f ) 是一个认证码，如果对任意的m m 和5 s 。总存在g e ，使得，( s ，e ) = m ，即任一信息都能被每个 信源在适当的编码规则下加密而成，则称这样的认证码为完全保密的认 证码 c a r t e s i a n 认证码没有保密的功能 2 几n ( 礼p ) 阶抛物矩阵在g k ( r ) 作用下的相似 标准型 令是特征数为p 的q 阶有限域，且p 为不为2 的素数，显然 g 是p 的幂。( ) 表示b 上扎n 方阵的全体g l 。( e ) 表示 上的n n 可逆矩阵的全体 定义2 1 【1 】设a g l 。( 日) ，且a ，如果有印：i ，那么 我们称4 为抛物矩阵 显然，与抛物矩阵相似的矩阵仍为抛物矩阵 3 我们先讨论p p 阶抛物矩阵在g l ，( 日) 作用下的相似标准型 文中用l ，a 一，a 。】表示对角矩阵，”一”表示矩阵的相似，显然 ”一”关系是等价关系 引理2 2 设矩阵a = f ； 中r p ，且有a v = 0 ，则有a i = 0 ，i 肚 a 。a = a a 。= m r ( r ) ，其 a p = 0 ，那么a 必为不可逆矩阵，因此a l = 0 a a 2 a 2 i a i i = 2 a a i g i t = 2 a r i a i = 2 根据上面的关系，我们发现岔+ 1 的前r 一1 列即为a 1 的第2 列 到第r 列而a 件1 的最后- - n r 与心+ 1 的倒数第- 7 - n ，也就是斗的 最后一列，及9 2 ，0 3 ，脚有关 我们首先说明下面的事实：如果a 的最后一列为零时，那么或 者a i + t 的倒数第二列，也就是搿的最后一歹i j 为零，或者9 2 = a 3 = t = a ，= 0 4 、， 吼她吣坼 0 0 o l 一 1 0 o 1 = 、if o o 蚴 叭 o ，jlti、蛳毗 o ! | 岍 、， 吩 ，碑 吣 0 m 卅 。 嘶 以。螂 一 一 n 嘶 删蚴 帆。伽!|一 。 唧 卿 ” ，一，；，一 当a 件1 的最后一列为零时，由a = 4 ，即有 0 2 口r r = n 2 r + 口3 n r r = = 坼一1 r + n r r = 0 矿1 2 怯吼曼_ 吼曼， 1 ( 2 ) 当o ”= 0 时，a 州的最后一列为零，即n 2 0 ，= 口2 ，+ 3 ，： 由上，得到或者a 的倒数第二列，也就是a i 的最后一列为零， 因为a = 0 ，由a 2 与a ”1 关系，可知当i = p 一1 时，有 旷1 蓦卜 n rl o ，2 o r r o r io o ，0 0 0o o 、 。i 6 2 l 屯2 b 2 p 20 2 l 0 i 依次类推，则a 一件1 = i6 3 。6 3 2 6 3 r - ：o ；：oi 5 根据我们上面得到的结论，因为舻1 “的最后一列为零，所以 有，或者0 2 = 0 3 一= q r = 0 ，或者a , 2 1 舭0 , 3 1 。= a r z = 0 如果a 2 = a 3 一= a ，= 0 ，则引理的结果已证 如果a 2 l = a 3 l 一= a ，l = 0 ，那么我们考虑 ，o oo 0 0 、 l c 2b 2 lb 2 2 b 2 r 一2 o l a p 5i c 3b 3 1b 3 2 b 3 r 一2 0 l ， i l c rk l “2 - - b r r - 20 类似的，我们可以得到 a 2 = a 3 = _ a r = 0 或6 2 r - 2 = b 3 ，一22 = b r r 一2 = 0 同样的，如果a 。= a 3 = = a ，= 0 ，则引理的结果已证+ 如果 b 2 ，一2 = b 3 ，2 _ - 一b ，一2 = 0 ，我们继续考虑小一1 依此类推，如果我们在a 的i ( i 3 ) 次幂时得到a 2 a 3 = a ，= 0 ，则引理的结果已证若不然，则有 拈( 00 00 00 0o 0o0 0 2a 2 a r 0 0 3 n 2 + a 3 a r 0 0 4d 3 + a 4 a r 0 因为a 3 的最后一列为零，所以或者a t = a 3 一= ，= o ，或者 a 2 a ，= a 2 + a 3 a r 一一= a t - l + a ：= 0 如果a 2m a 3 - = a r = 0 ， 则引理的结果已证如果a 2 a ，= a 2 + a 3 a ，一- = a ，一1j - n i = 0 我们 继续考虑a 2 ，此时 拈f o 0o0 0 a 2a 2 a r o a 3a 2 + a 3 a ， 6 h 0 0 1 ；| | a 2 的最后一列均为零，这时一定有 a 。= a 。= 一a ，= 0 因此有a l = a 2 = a 3 = = a ，= 0 结论得证 引理2 3 设矩阵 b = 10 其中i = l ，m i n r ，s 一1 ) 山= 以c p a r + l2a r + 22 = a r + s = 0 7 b p = 0 ，所 毗7研吣吣 0 l o 1 + 或 、 卜 惰 “ 日 吼 |， p b ? _ 有 b 且p 一 s+r 中其 哪 鼢 、， ， o、ll 舯时 - l 0 1 ill有 = 则 g ， 令 七2 知 理 已 引 由 由 叉 明 仉 汪 i | 即此时b o l 10 0 o 1 a l a 2 ： 0 r 0 0 ： l0 若矩阵b 中的。，令矩阵p l = ( l ) ，则有 r 州= ( l ) b ( l ) 0 1 0 1 a r 10 再令b = ( l 。r ) ，则有 = b l f i s f i s、 p 2 b l p ；- 1 = i o i l i b 1l0 1 l 、 l 0 1 10 10 a 2a l 8 a r 10 o 虮 眈 l 类似地，我们可以将b - 做相似变换得到 b 2 = o 1 10 10 0 2 1 o ， 10 令b = ( l ：1 耋1 。 ，那么有 p 3 8 2 厅1 f l 。 1f l 。 l 川2 1 l b 2l 口2 1 i 1i ； 一r 1 n r o 1 10 10 口2 1 o r l 10 ( s + 1 列) 9 、， 1 类似的用p 3 形的消法变换做相似变换，得到 b 一鼻+ 。 下面考虑若a l = 0 ，设啦+ l 是n 2 ，a 3 ，a ，中第一个不为零的 数此时b = 0 1 我们分别对下面两种情况讨论 b p 4 b 巧1 = 1 f 1 ) i s o l + 1 ： 口 0 0 0 ( 2 ) i 8 厶l ，用p 4 对b 做相似变换得到 0 ， 0 l o 1 10 再利用p 2 形矩阵可将毗化为1 ，且可将次对角线上不为零的位置均化 为1 ，进而利用岛形矩阵做相似变换，可将a ，a 件2 ，化为零 1 0 o 1 0 0 l ， 0 t 寸 仆 ， 0 | | 当 r q 令 o q 吣 1 l 00 0 o o 得到下面的矩阵 b b 1 d 2 0 3 b r - 2 + 1 0 1 l0 10 毗+ 1 1 a r 一1 10 继续利用消法变换将a m ，a 。2 ，a ，l 消为零，最后得到 b 。b 3 ：f 轰，1 ，其中d 。 u lj r + s i 再利用矩阵p 5 = 变换，得到 b b 4 = d 2 厶一1 o0 o0 00 o0 1 d ，l d r l + 1 1 01 f o ，1 ，其中d 。：l o j + 3 一。 lo 0 1 l o o d 1 d h + l 对b 3 做相似 00 j i d t 0 i i 西一h l 0 1 00 1 ，、 因为i s ，因此这样依次做下去，可以得到 b 一岛= ( 当+ 。一，) ，其中 。= 再利用矩阵p 6 = d 1 ，d 2 ，d r l + l 消为零，得到 b f 五 ( 2 ) 当i 8 时， 令q t = 换，则 q b q i l = ( 五曼) = b ，其中。：= f ， 1 2 o 0 o 0 _ o - 0 o0 0 即可将b 5 中的 用q 1 对b 做相似变 0 _ 啦+ 1 _ a r 0 + o 也一一 d 、 一如 矗 譬卧 。 l l 令q 2 = 变换，则 五一2 1 l ( 1 | l q - 1 ： a r l q 。b ，q i l = ( 甓) ，其中。：= 1 用q 2 对b l 做相似 0o 0 o 0 a i + l 0 0 - 0 0 a ，00 00 0 ooo 类似的，用这样的消法变换对b 继续做相似变换，且因为i s 所以可以得到 b 。f 号1 ，其中d j s 再令q 3 = 相似变换，则得到 结论得证 l l b 一( 4 00 a i + i 0 a ，0 o0 j 1 l一。，用仇对b继续做 例：曲”日= p = s ，矩阵b = ( ? ：。07 | | ) 例s c 利用引理2 3 的方法将口化为( 五工+ 。) 形 互t 舞s ，由弓i 型t 。z 务un t = 。s = 。，s nb = ( ：喜 ( 厶厶) b ( 厶 1 0 1 = b 1 10 i 1 0 r ) ， ( 疋n i l 。i - 。i 。) b ，( 如n l 。，。) = ( ；萎；。) = b 2 三-a：21 ，h h ( 厶一：。) b a ( 厶之，) = r ，： c 。，如果。t2 。，啦。，此时b = f ； 0 m 0 l ，。 = 、 如 3 日= 、， 0 o l 如敛】我 ， 、，、， o 0 啦幻o o 0 1 0 1 0 l 0 0 o 1 d l 下的相似变换： ( 1 如0 如0 ) b ( 1 芝台) = ( 如。i 1 。i 。) b ，( 厶。：口。) 1 ， - a 3 1 。h 五 b 3 1 ( 3 ) 如果a l = a 2 = 0 ，a 3 0 ，此时b = l 1 0 o 10 1 0 o o 1 = b 3 我 这个例子中运用了引理2 3 的方法，得到了b 的一种相似矩阵的 岛 h | i b、，ll_、 = o 、 0 1 0 0 l 0 l ， o 啦 o l o 1 o 一吡 o l，一 r l lij、ll_、 o 0 o 0 o o l 0 l 0 l 0 1 o 0 1 c 6 6、liij ，。，。 ， l o h 垃0 l l 2 (。o山曲。 日 |、， 、ll 0 0 o 1 钆 0 1 0 o 0 0 0 l o 1 0 1 0 1，一 ，。一 = =、 l l 哪 ， 咄 。 l l ， b 燃儿 i相 q自 1 ， l t如 l 敞 们，lll 1 ，。，。 状形 引理2 4 设a 为b 上的n n 阶抛物矩阵，那么a 必相似于一 个( 2 ，1 ) 位置是1 的抛物矩阵 吼la 1 2 吼p 、 证明设抛物矩阵a ：l n 2 1 。2 2 叻9 i ， ：艺：， ( 1 ) 若a z t 0 ，那么我们可以利用如下的相似变换将( 2 ，1 ) 位置 元素变为1 ： ( i | ： ( 2 ) 若a 2 1 = 0 ，下面往证只要存在某个a i j 0 ，其中i j ，则可 经过相似变换使( 2 ，1 ) 位置不为零令e 0 为表示将i ，j 行对换的置换 矩阵 若3 a i ，0 ，则有 岛，e u a e 弓1 12 【鼍 la 3 1 若3 a o 0 ，旦其中i i ，i j ，则有 易t e u a e 才坛1 = ( 警 以上两种相似变换均使a 在经过变换后( 2 ，1 ) 位置不为零 事实上，在抛物矩阵a 中必存在某个a i j 0 ，其中i j 若不 然，任意的。幻= 0 ，i j ，则a = 【a l l ，a 2 2 ，a n n j ，因为a 是抛物矩 阵，即a p = j ，所以砖= 1 ，由引理1 1 ，故有a l l a 2 2 = a 卯= 1 ， 即a = ，与a 矛盾 1 6 、ij 十 、， l l l l2 口 l ，。， a 、， l l l _ 虬 0 l ，i，i_llll_f-l、 、， 十 因此，对a 先后用( 2 ) ，( 1 ) 的步骤即可将( 2 ，1 ) 位置化为1 结论得证 定理2 5 目上的p p 阶抛物矩阵在g l p ( 舀) 作用下的相似标 准型为 h = 【珥。，珥。 其中皿2 ( 1 1 ：) 。，且有。茎r s 他s - s h ，m 芝 ha p ：嘞 丑= a 一，= i 1 。2 ：_ 1 ： 。印 i ，目pb ：( 6 。) 令兄，= ( 1i i ；。 ，则且：曰冗i 1 = ( ；蓉!) 同样的，这里已经改变，不妨仍这样记以下均如此表示 此时若| 6 t 2 0 ( i 3 ) ，则可经过相似变换，使得b 3 2 = 1 ，且不 1 7 改变b l 企 记为b 2 、0 o lf 10 i ，则r 2 b l 筋1 = i o1 。j。 j 这样可一直找到某个k ，使得b k j = 0 ( 彤k + 1 ) ，即 日。f c 1 r m1 其中c l ： u 2 因为b p = 0 ，所以有四= 0 ，钟= 0 又由于sp ，由引理2 2 ，有 b l k = b 2 k = = 6 k = 0 此时考虑q ，设c 2 = ( c i j ) c p 一 ) 。( p k 1 如果v c 0 = 0 ，其中i j ，那么q = ( c 1 1 c 2 2 ，c p 一女p 一】，因 为c ；= o ，所以c l l c 2 2 一c p 一p k = o ，即c 2 = o 那么 b “ 为( 00 1 ，其中m ：( m 玎) ，容易看到经过相似变换可将m 化 再利用引理2 3 的方法，容易得到 b 一( 4 ：) 这里的工如引理2 3 中表示 如果j 勺0 ，其中i j ，那么由引理2 4 的方法知道，可利用 1 8 1t + 咿咿j 咿 吣嘞：吣 一一 一 例n 、 静 | l 的 、lf 姥 一跳 b 6 b 6o：o l o 0 、， 5 吼o o m o o ， g m 0 ，一 相似变换使c 2 。位置为1 ，依次讨论，可得到 b 。fc 3 二1 ，其中c z ： 0 4 00 10 0 b l 一1 1 b u 同理因为b ，= 0 ，所以有四= 0 ，q = 0 又由于f p ，由引理2 3 ，可 利用相似变换使g 一( 五14 。) ，则此时，b 一( q 邑) ，其中 q 一( l 。) ，r l + r 2 = i ，o 2 ，q p 一一1 1 ，故 q p - k - 1 ( 矿一。一1 ) 1 ， 所以 f ( p 一1 ) f ( p 一2 ) f ( 1 ) 假定编码规则按照统一的概率分布所选取，则由引理3 2 ，3 3 和关于 f ( k ) 的不等式的性质有 耻m a x 些酱型 = m k e a x k 舒e = 哿e il ii 和 b = 。，。，m 。m a ，x 。；。，丝兰j ；： _ 刍掣 ( q 一1 ) q 印。2 妒1 i g l p b l ( 日) k：(q-1)q2p-k2-21glp_k。_l(fq) 定理3 7 前面我们所构造的认证码的成功的模仿攻击概率b 和 成功的替换攻击概率b 分别为： 毋= 矿 r ：兰 q 证明由上面我们进行的讨论知道 b = 麟酱= 舒= 矿击 p s 2 2 m k a ，x k ! ! 二1 2 1 ：竺：l 堡生二垒二! ! 墨! ! 女。( g 一1 ) q 2 p 2 i c l p e 。一l ( 日) l 1 2 2 m 耳a ，x 女脚一q k 2 - 1 1 一叮 假定编码规则按照统一的概率分布所选取，则分别有 p ，= 矿责嘉习 p s ：一1 q 参考文献 1 华罗庚，万哲先著，典型群，上海科学技术出版社，1 9 6 3 2 万哲先，戴宗铎，冯绪宁，阳本傅，有限几何与不完全区组设计 的一些研究，科学出版社，1 9 6 6 3 z w a n ，g e o m e t r yo 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 ，l u n d ，s w e d e