（应用数学专业论文）利用有限域上奇异辛几何构造具有仲裁的认证码.pdf

ab s t r a c t ab s t r a c t i d凡b e t h e f i n it e f i e l d o f c h a r a c t e r i s t i c p w i t h q e ! e m e n t s , w h e r e p i s a p r i m e a n d q = p 0 f q (- ) o f d e g r e e . l e t e , b e t h e i u n it v e c t o r o f t h e s i n g u l a r s y m p l e c t i c s p a c e 2 v + 1 o v e r f i n it e f i e ld凡 ， w h e r e i = 1 ,2 , . . . ,2 v + 1 . l e t q b e a s u b s p a c e o f ty p e ( 2 + 1 ,1 ,1 ) g e n e r a te d b y e , , e , + , , e 2 . , ,p b e a s u b s p a c e o f t y p e ( 2 v 一 2 + 1 , ， 一 1 , 1 ) g e n e r a t e d b y e e 2 ， . . . ， e , - , , e _ a, e - 2 , . . . , e 2 , :, e 2 , + ue 2 o + 2 , . . . , e 2 , . , t h e s u b s p a c e s o f ty p e ( 2 v 一 3 + k , v 一 2 , k ) c o n t a in i n g q a n d c o n t a in e d in p a r e r e g a r d e d a s s o u r c e s t a t e s , w h e r e l _ k s u 欺 骗 .六 元组 ( s , e t ,e r , m f ,g ) 称 为一个具有 仲 裁的 认 证 码， 如果: ( 1 ) f g 是满射; ( 2 ) 对任意m e m , 对任意e t e e t , 若有s e s 使得a s , e t ) = m ， 则s 由m , e t 唯 一确定; ( 3 ) 若p ( e t , e r ) 4且a s , e t ) = m ， 则g ( m ,e r ) = s ; 否 则g ( m ,e r ) =欺骗. 分别 称s ,e t ,e r , m为 信源集、 编码规则集、 解码规则集和信息集， 集合s ,e t ,e r , m 的 基数is i, i e d , ie r i, im i称为这个认证 码的 参数j 具 有 仲 裁的 认 证 码 简 称矛 一 码。 若a s ,e t ) = m ， 则 称 信 源: 在 加 密 规则e t 下 加 密得到 信息m , s 是m对应的 信源， 也称信息m包含加密规则e t ; 若g ( m ,e r ) = s , 则称信息m包含解码规则e r ， 如果e r 是收方取定的解码规则，则称信息m是合 法的 . 这里p ( e r , e r ) :a 0 是指任意s c- s 经过e t 加密后的 信息均可以 通过e r 的认证， 我们称发方的加密规则e t 和收方解码规则e r 相互关联. 在具有仲裁的信息系统模型中， 有四个参与者: 发方、 收方、 敌方和仲裁人; 发方用自己 选定的编码规则e t 加密信源s 得到信息m ，并将m发送给收方，收 方收到信息m后， 根据自己选定的解码规则e r 和相应的认证条件判断m是否合 法 ( 这里要求e t 和。 ， 满足p ( e t ee r ) r o ) ， 若合法则解密信息m得到信源s ， 否则 拒绝信息m ; 敌方是系统中的非授权人， 他想欺骗发方和收方， 发起对系统的攻 击，他知道认证系统 ( 即认证码的构造) ，但不知道发方选取的加密规则和收方 选取的解码规则; 仲裁人是系统中最权威的人， 他知道整个信息系统、发方选取 的加密规则和收方选取的解码规则， 但他不参加通信活动， 他唯一的任务是在发 方和收方发生争端时调解。在具有仲裁的认证系统中，共有下面五种攻击: ( 1 ) 敌方的模仿攻击 敌方在未观察到 任何信息的条件下， 发送一个信息给收方， 若收方将其当作合法信息接受 ( 即该信息满足收方的认证条件) ，则称敌方的模 仿攻击成功。 假定编码规则服从均匀分布， 将敌方的模仿攻击成功的最大概率记 为pi，则 界= m a x. . m 一c r 。 e r i e . 。 m ) ie . i ( 2 ) 敌方的替换攻击 敌方在信道中 截获 信息m后加以分析， 再向 收方发送另一个 信息m ( 信息m 与原信息m对应的 信源不同 ) 替换原来的 信息， 若收方把敌方发 送的信息当成合法信息接收， 则称敌方的替换攻击成功。 假定编码规则服从均匀 分布，将敌方的替换攻击成功的最大概率记为p s ，则 第 i 章 引言 p s = 嘿xf m a x , , ic r 。 e r i o r 。 m 且 e , 。 m 一 ， 。 e r i e r 。 m ( 3 ) 发 方的 模仿攻击 发方发送一个信息 给收方， 但这个信息不能由 发方的加密规 则得到， 然后发方否认曾发送过它; 若收方把该信息当成合法信息接收， 则称发 方的模仿攻击成功。 假定编码规则服从均匀分布， 将发方的模仿攻击成功的最大 概率记为p t ，则 p t =m a x , . e , m a x m 不 。 。 ，:加 . ， 。 卜 : 。 二 : le , 。 m 且 ， e t ,e r / * 0 一 : 。 e r ip ( e r , e r ) * 0 ( 4 ) 收方的 模仿攻击 在收方没有收到任何信息的 情况下， 收方称自己 收到一个信 息， 若这个信息可以由发方的加密规则加密得到， 则称收方的模仿攻击成功。 假 定 编 码 规 则 服 从 均 匀 分 布 ， 将 发 方 的 模 仿 攻 击 成 功 的 最 大 概 率 记 为p ,% ， 则 p r , = m a xlr e e q ma x m . , t 。 e t i- t e m a p (e t ,e , ) * 0 i ，; 。 二 ; i p (e t , e r ) * 0 ) 使下.一法冲 ( ) 收方的替换攻击 收方收到一个合法信息 m后称自己 收到的是另一个信息 m ( 信息m 与原信息m对应的 信源不同 ) ， 若m ，可以由 发方的加密规则加密得到， 则称收方的替换攻击成功。 假定编码规则服从均匀分布， 将收方的替换攻击成功 的 最 大 概 率 记 为p r . ， 则 p r . = 口s ax . . . e , - m m a x . ,e m i c t 。 e r i e t 。 m ,m ，且 p (e , , e r ) * o ) l : 。 e t ie t e m - .p (e r , e r ) * 0 1 . 2认证码研究的主要内 容 ( i ) 认证码的 性质的 研究. 如认证码各个参数之间的关系、 认证码中各种攻击成功概率最大值的组合论 下界和信息论下界及编码规则个数的界等; ( i i ) 认证码的存在性问 题. 假定己 给出欲构作的认证码要满足的要求( 如要求其被成功攻击的概率达到 组合论下界或信息论下界) ，研究符合该要求的认证码是否存在以及存在的条件 问题; ( i i i ) 认证码的构作问 题。 通过认证码的构作， 可以进一步确定某种类型认证码的存在性。 认证码的构 作是认证码研究中既有理论价值又有实际应用价值的问题; ( i v ) 认证理论与组合设计及纠错码理论之间的关系; ( v ) ia 证码之间的关系及分类问 题。 己 知两个认证码，它们是否同构? 如果已知某类认证码存在，在同 构意义下，这类认证码有多少? ( v i ) 认证码的实 现问 题。 研究认证码的一个主要目的就是将它们应用到实际的通信系统中， 这就要求 第 1 章 引言 研究如何实现已有的认证码模型。 1 . 3认证码研究的概况 认证码是解决认证问题的一种重要方法，自 从认证码理论在 1 9 7 9 年被提出 以来， 世界上许多数学家和密码学家都致力于这方面的研究。 特别是g j . s im m o n s 教 授 给出了 认证码的 数学模型 【 1 ,2 1 ， 并 把香 农的 信息 论引 入 认证码的 研究以 后， 对认证理论的研究可以说是硕果累累。 这些研究主要集中在认证码的性质、 构造 及身份认证方案的设计。目 前， 在认证码研究中，比较有代表性的成果包括: 认 证码中各种攻击成功概率最大值的组合论下界和信息论下界及编码规则个数的 界，某些类型认证码所满足的充要条件及达到攻击成功概率最大值的界时的条 件， 认证理论与组合设计及纠错码理论之间的关系， 给出了众多的认证码的构造。 认证码的创始人g j . s i m m o n s 及d .r . s t i s o n 、我国的裴定一、杨义先教授等 在认证码性质的研究方面作了大量的工作， 得到了认证码被敌方模仿攻击和替换 攻 击 的 概 率的 组 合 论 下 界 和 信息 论 下 界 3 5 1 , 1 9 9 4 年， t .j h o n a n s s o n 得到了 带 有 仲裁的 认证码被成功攻 击的 五种概率的 下界6 1 。 在认证码的 构造方面也取得了 较 为丰富的成果，基于许多理论给出了众多的认证码的构造如利用组合设计 ( t 设 计、p b i b设计、垂直阵列、拉丁方阵等) 对认证码的构造;利用射影几何、典 型群上的几何等构造认证码。 国外学者d .r .s t i s o n . g v s e r g e 等人利用结合方案、 组合 设 计、 代数几 何等构 造认证码7 - 9 1 取 得了 一系列的 成果。 认证码的 构造问 题 就其本质来说是组合设计问题，而有限域上的典型群的几何 ( 辛几何、酉几何、 伪辛几何、 正交几何) 提供了较好的组合结构， 且易于计数。 在上世纪六七十年 代， 我国著名数学家万哲先与他的学生和合作者们对有限域上的典型群的几何理 论进行了 系统的 研究， 并将其用于区 组设计问 题【 1 0 1 . 9 0 年代， 万哲先在国际上首 次利用有限 域上的典型群作用下的几 何空间的 子空间构造无仲裁的认证码d o 。 之 后， 冯荣权、 游宏、高有、 高锁刚等人利用有限域上的典型群作用下的各种几何 空间 的 子空间以 及有限 域上的 矩阵的 标 准形 构 造无仲裁的 认证码 12 - 1 7 1得到一 系列的成果。 根据通信双方的互相信任程度， 认证码可分为无仲裁的认证码和有仲裁的认 证码。 由于有仲裁的认证系统与现实生活更加接近， 因此有仲裁的认证码的研究 是非常有意义的， 近几年这一课题引 起了 许多数学家和密码学家的重视。 自1 9 9 8 年来， 王新梅、 马文平等人又将有限域上的典型群的几何用于构造有仲裁的认证 码 18 - 2 0 1， 同 一 时 期， 裴 定 一、 李 育强 等 人 利 用 组 合 设 计 构 造 最 优带 仲裁的 认 证 码 2 1 - 2 2 1 第 2 章 预备知识 2 . 1 第2 章 预备知识 有限域上的辛群和辛空间 定 义2 .1设 凡是 一 个 有4 个 元 素 的 域 ， 其 中9 是 一 个 素 数 的 幕 。 一 个 n x n 矩阵k = ( 气 ) is ,j ，被称为是交错的， 如果气= - k q ( i * j ,1 5 i , j n ) 并且 气二 0 ( i = 1,2 , - -, n ) o k 是 交 错 的 的 等 价 定 义 是 对 d x e 凡 间 有 x k x = 0 0 定 理2 .1设k 是 凡 上 的 ， x n 交 错 矩 阵 ， k 的 秩 必 然 是 偶 数 ， 进 一 步 ， 如 果k 的 秩是2 v ( x 2 , - ， x 2 . ) , t ) h ( x x 2 , . . . ， x 2 v ) t 定 义2 .3 s p 2v ( 凡 ) 的 元 素 也 称 为 辛 变 换 。 向 量 空 间 凡 (2 ,， 联 同 辛 群 s p 2 v ( 凡 ) 在 其 上 的 作 用 称 为 凡上2 v 级 辛 空 间 在 s p 2 v ( 凡 ) 的 作 用 下 ， f (2 ,9， 的 子 空 间 分 成 若 干 轨 道 。 定 义 2 .4 一 个 向 量 二 。 凡 (2 v， 称 为 迷 向 向 量 ， 如 果 x k x = 0 . 显 然 所 有 凡 (2 ,， 的 向 量 都 是 迷 向 的 。 定 义 2 .5 设 p 是 凡 (2 v， 的 m 维 向 量 子 空 间 。 我 们 用 字 母p 表 示 向 量 子 空 间 p 的 矩 阵表示，则p是一个秩为m的mx 2 v 矩阵，它的行组成 p的一组基。显而易见 p k p是一个交错矩阵。 由定理2 . 1 ， 设p k p的秩为2 s ， 则我们称向量子空间p 为 伽 , s ) 型 子空 间 。 显 然: ， 且2 s _ m 。 特 别 是， ( m ,0 ) 型 子 空 间 称 为 m 维 的 全 第2 章 预备知识 迷 向 子 空 间 ， ( 2 s , s ) 型 子 空 间 称 为 2 s 维 非 迷 向 子 空 间 。 显然，子空间p是全迷向 子空间当且仅当p k p= 0 ，其是非迷向子空间当 且仅当p k p是非奇异的。 定 义2 .6 凡 (2 ,， 的 两 个 向 量 二 和 y 称 为 正 交 的( 关 于k ) , 如 果 x k y = 0 e 定 义2 .7设p 是 凡 (2 ,) 的 m 维 子 空 间 。 用 尸表 示 由 与 p 中 所 有 元 素 正 交 的 向 量 组成的集合，则 p 一 卜 。 f c(2,) iy k ，二 = o ,v x 。 p 显 然 ， p i 是 凡 (2 .， 的 ( 2 v 一 m ) 维 子 空 间 ， 称 为 p 的 对 偶 子 空 间 。 定理2 .4 一个子空间p是全迷向 的当 且仅当p cp -1 ; p是非迷向的当且仅当 p n p l = 0 o 引 理 2 .5设p 是 f (2 ,v， 的 ( m , s ) 型 子 空 间 。 则 2 s 二 或 v + s - m 0 ， 则 我 们 有n ( m , s ;2 v ) = 0 。 因 此 下 面 我 们 总 是 假 设 2 s!5房 _ v+s. 0i( - /1苦eseses胜、 m ( m , s ) = i ( ) 0( 1 . 3 ) 0 ( m - z a ) 如 果p 是 一 个 伽, s ) 型 子 空 间 ， 则 由 定 理2 . 1 ， 我 们 可 以 选 择 一 个 子 空 间p 的 矩 阵 表示尸使得 p k p = m ( m , s ) . ( 1 . 4 ) 用 。 ( m , s ;2 v ) 表 示 满 足 定理2 . 1 2 设2 s _ m n ( m , s ;2 v ) ( 1 . 4 ) 兰v+s 的秩为m的mx 2 v 矩阵p 的数目。则我们有 ，则 = i s p z , (f j i g l m -zs (f , ) q z.( 一 ，)n (m , s ;2 v ) 显然， js p z, (f , i = n (2 s ,s ;2 s ) 为 计 算n ( m , s ;2 v ) ， 必 须 计 算出 。 ( m , s ;2 v ) 第z 章 预备知识 我 们 说 明 一 下 下 列 记 号， 设a 是 一 个二 、 m 矩 阵 ， 0 5 r :5 m in ( m , n ) 。 用a 。 表 示a 左 上 角 ; 、 ， 子 矩 阵 。 现 设2 s _ m _ v + ， 且 。 _ r r 2 , r , + r 2 _ m ， 设n ( r , ) 为 秩 为 。 且 使 得 p , k p , = m (m , s 天 的 r , x 2 v 矩 阵 的 数目 。 对 一 取 定 的 秩 为 r , 且 使 只几 2矛leses吸、 一- p ,k p , = m ( m , s ) 。 的 r , x 2 ， 矩阵p 。 设n ( p , , r 2 ) 为 使p p k p 一 m (m , s 。 的 r 2 x 2 v 矩 阵 p 2 的 数 目 。 则 我 们 有 秩为r , 十 几且 引 理2 . 1 3设2 s :5 m _ ， 十 : 且。 5 r , 几， 十 几 5 m 。 则n 伍几) 与 月 的 选 择 无 关 ， zl-l). 且 n ( r , + r 2 ) = n ( r , ) , ( p , r 2 ) 对 任 意 p , 成 立 。 引理2 . 1 4设s v ，则 n ( s ,0 ;2 v ) = 。 ， . 护 一 5 + 1 引理2 . 1 5 设s _ v ，则 n (2 s , s ;2 v ) = 9 (2-sk 六 (9 2， 一 1) - - l 定理2 . 1 6 1s p 2,(f , )l一 ， n (4 2 一 1) . 引理2 . 1 7 设2 s 5 m_ v + s ，则 n (m ,s;2 v ) 一 。 (2v-.i)+(m-2.xm-2:-12 1 1 (9 2， 一 1) . 厅 . ， 体， 价+1 定 理2 .1 8设 2 s _ m _ v + s ， 则 凡 上 2 v 维 辛 空 间 内 (km , s ) 型 子 空 间 的 数 目 是 n (q ， 一 1) n (m , s;2 v) 一 q 2+ “ 一” 高.s. itt ! 2i ,17 t ( ., .1 l l l q 一 i i i 1 1 q一 2 1 推 论2 . 1 9设 m :5 2 v ， 则 凡上 2 v 维 辛 空 间 内 m 维 完 全 迷 向 子 空 间 的 数目 是 n (q tr 一 ;) n (m ,0 ;2 v) = - 片 .1 ， 1 1 诊 一 1 推 论2 .2 0设 ， ， ， 则凡上2 v 维 辛 空 间 内 2 s 维 非 迷向 子 空 间 的 数目 是 第z 章 顶备知识 n (2 s , s ;2 v ) = q 2 (- ) n (q 2， 一 1) n (q 21 一 1) 2 . 3 有限域上的奇异辛几何 我 们 也 可 以 计 算 凡 上 2 v 维 辛 空 间 内 取 定 的 (- , s ) 型 子 空 间 包 含 的 (m i l s , ) 型 子 空 间 的 数目 。 这自 然 地 引 导 我 们 介 绍 f q 上 的 奇 异 辛 空 间 。 定义 2 . 8 现设 ( k、 k , = 。 ， 其 中 k 为( 1 .1 ) o 凡 上 满 足 t k ,t = k , 的 所 有 价 ， + 小仁 v + l ) 非 奇 异 矩 阵 构 成 一 个 群 ， 称 为 凡 上 2 v 十 级 ， 指 数 为 ， 的 奇 异 辛 群 ， 用 s p 2 v+ l,. 帆) 表 示 。 容 易 证 明 ， s p 2 r+ /, (f v ) 由 所 有 形 如 2 v 1 : = 伪 州2 v 戈 0 7 云 )1 的 仁 ， + 小仁 v + 1 ) 非 奇 异 矩 阵 构 成 ， 其 中 双 1 k 不 ， = k 且 t 2 2 是 非 奇 异 的 。 首 先 ， 我 们 有 s p 2,+ l., (f q ) 的 阶 定理2 . 2 1 1s p 2,+l., (f e 卜 、 ” ，“ /(i- i)2 t7 q 2， 一 ，11 l (q ， 一 :) . 1 = 1， ， 1 定 义 2 .9设 f (2,na， 是 f q 上 的 (2 v + 1) 维 向 量 空 fei 我 们 定 义 s p 2,+l, (f , ) 在 f (2,+/)a 上的作用如下: f (2 ,+ /) x9助 2 r+ 1,r ( f 9 ) *9 2 ， 十 1 , v ) 表 示 f , (2 v+ 1)9 的 所 有 (m ， 5) 型 子 空 间 组 成 的 集 合 。 设 e , (1 - i - 2 v + 1 ) 是 f , (2 - 1)9 的 一 个 行 向 量 ， 它 的 第 i 个 分 量 是 1 ， 其 它 分 量 为 0 ， 用e 表 示由 e 2 .* l i e 2 . 2 * - 2 、生 成的 i 维 子 空间。 定 义 2 . 1 0 一 个 f , (2 ,+ i)v 的 m 维 子 空 间 p 称 为 是 ( m , s , k ) 型 子 空 间 ， 如 果 下 列 条 件 成 立 ( i ) p k , p 与 m 伽 ， 习 合 同 ( ii ) d im ( p ( 1 e ) = * 用 m (m , s , k ;2 ， 十 l , v ) 表 示 f , (2 .+ i)v 中 所 有 ( m , s ,k ) 型 子 空 间 组 成 的 集 合 ， 则 有 定 理2 .2 2 m ( m , s , k ;2 v + l , v ) 非 空 当 且 仅 当 k - i 且2 s - m 一 k - v + s , ( 1 .5 ) 或当且仅当 m a x 和 , m - v - s j 5 k 5 m in l , m - 2 s ) . ( 1 .6 ) 进 一 步 ， 如 果 m ( m , s , k ;2 v + l , v ) 非 空 ， 则 在 s p 2 ,+ i,. 帆) 作 用 下 它 形 成 了 一 个 子空间轨道。 推 论2 .2 3 m(m , s ;2 v + l , v ) 非 空 当 且 仅 当 m a x o ,m 一 v 一 s 5 m in l , m 一 2 s 进一步，m (m , s ;2 v + 1 , v ) 是在s p 2 ,+ i, 帆) 作用下互不相交的轨道 m (m , s , k ; 2 v + ! , v ) 的 并 集 。 其 中 * 满 足 ( 1 .6 ) 0 记 n (m , s , k ;2 v + l , v ) = im (m , s , k ;2 v + l , v i 定理2 .2 4设 m a x 0 , m 一 v 一 s l k 、 m in i , m 一 2 s 则 n (m , s , k ;2 v + 1 , v ) 一 ， 2s (v+ a- m + k ). (m - k ” 一 ) ft (q 2， 一 1) 六 l9 ， 一 1) l . -x - m + k + l . 1 - k + l 21 一 1 k-21f 1 1 (9 一 1h (9 一 1) ( 1 . 7 ) 了儿再 ，n，-j 第2 章 预备知识 推论2 . 2 5 设 m a x o , m 一 v 一 s 卜m in l , m 一 2 s n 伽 , s ;2 v + 1 , v ) = * z.,)，n (m , s,t mmc,ojm-r-a) k ;2 v + 1 , v ) 其 中 n ( m , s , k ;2 v + 1 , v ) 由 ( 1 .7 ) 给 出 . 现我们将利用上述计数定理得非奇异辛几何上的一个计数定理. 设 扩. ) 是 2 v 维 空 间 ， s p 2, 帆) 作 用 其 上 。 设 p 是 扩师一 个 取 定 的 (m s ) 型 子 空 间 ， 用 m ( m , , s , ; m , s ;2 v ) 表 示 包 含 于 p 的 ( m s , ) 型 子 空 间 组 成 的 集 合 。 设 n ( m , , s , ; m , s ;2 v ) = i m ( m s , ; m , s ;2 v ) 由 定 理2 .7 知 n (m s , ; m , s ;2 v ) 与 (m ， 5) 型 子 空 间 p 的 选 取 无 关 。 我 们 有 定 理2 .2 6 m ( ms , ; m , s ;2 v ) 非 空 当 且 仅 当 2 s_m5v +s 2 s , _ m , _ v + s , 0 s 一 s , _ m一 m , 这三个条件等价于下列条件 2 sm_v +s ( 1 . 8 ) m a x 0 , m , 一 s 一 s , 卜m in 伽一 2 s , m ， 一 2 s , ( 1 . 9 ) 定理2 .2 7设 2 s_m 5v+s m a x j 0 , m , 一 s 一 s , ) :5 m in m 一 2 s , m , 一 2 s , l n 伽 s , ; m , s ;2 v ) “ 加 褚 毕 .玄 亡 二 一 ，_ x献 石 - m , + k 只m , - t x m - i r - k ) n (9 z 一 1) 竹 l9 ， 一 1) 1 = s + s , - m , + k + 1 i = m - i s - k s l 1 1 (g 21 一 1f 讯， 一 1)a (9 7 一 1) 1 -1 i =1 第z 章 预备知识 n ( ms , ; m , s ; 2 v ) (vt 朴n - 2 s , 1 六 (q 一 ) g 3 ,.(r+ r ,- n y + k h (m ,- k )(m - 2 r - k 7 - r + s , - m , + k + 1 i - m - 2 r - k + 1 一 ， ，蛋 n (g ，一 1f l-? r,一1/1 1 9 ， 一 1j 卜, / d 现 研 究 在 奇 异 辛 几 何 中 的 相 似 问 题 。 设 p 是 一 个 f (z v+ l)9 中 的 (- i s , 劝 型 子 空 间 ， 用m ( msk , ; m , s , k ;2 v + l , v ) 表 示 包 含 于p 的( m , r s , , k , ) 型 子 空 1 j 组 成 的 集 合，则 n (ms k , ; m , s , k ;2 v + 1, v ) = im (ms k , ; m , s , k ;2 v + 1 , v ) 由 定 理2 .2 2 知 该 值 与恤， s k , ) 型 子 空 间p 的 选 取 无 关。 首 先 我 们 有 定 理2 .2 8 m ( msk , ; m , s , k ;2 v + l , v ) 非 空 当 且 仅当 气 k _ 1 2 s 5 m一k _v +s 2 s , m 。 一 k , _ v + s , 0 ， 一 : ， 、 (m 一 ; ) 一 (m : 一 k , ( 1 . 1 0 ) 这四 个条件与下列条件等价: 权:5 k :5 1 2 s 5m一k5v +s ( 1 . 1 1 ) m a x 0 , m ， 一 k , 一 s 一 s , 1 :5 m in m 一 k 一 2 s , m ， 一 k , 一 2 s , 定理2 .2 9 假设 ( 1 . 1 1 ) 成立，则 n (ms k , ; m , s , k ;2 v + 1 , v ) = n (m ， 一 k s , ;2 s + (m 一 k - 2 s l s )n (k k )q (一 , x k - k, ) ( 1 . 1 2 ) 第3 章 具有仲裁的认证码构造及参数计算 第3 章. 具有仲裁的认证码的构造及参数计算 3 . 1 认证码的构造 设 凡 表 示 特 征 为 p 的 9 元 有 限 域 ， r = p 0 , p 为 素 数 。 设 e , 是 有 限 域 凡 上 2 v + l 维 奇 异 辛 空 间 凡 (2w /， 的 第 i 个 单 位 坐 标 向 量 ， 其 中 1 = 1,2 , . . .,2 v + 1 。 令 q 为 由 eve十 。 生 成 的 仁 十 1 ,1 ,1 ) 型 子 空 间 ， 由 e , ， e 2 ， -, e , e , e , . , , . . . ， e 2 , - i , e 2 , + , , e 2 , + 2 , . . . , e 2 - i 生 成 的 仅 ， 一 2 + 1 , v - l , l ) 型 子 空 间 记 为 p . 源 状 态 为 p 中 包 含 q 的 仁 二 一 3 十 k , ; 一 2 , 劝 型 子 空 间 ， 其 中 1 e 2 , + , , e 2 . + 2 , . . . l e 2 - k 由于收方的解码规则是由 且a ., 则。 e , ，? 2 e 2 + - - - + a , e , + e , + , + a ., + z e ,+ z + 一+ a 2 . e 2 . + a 2 - ie 2 . 1 + 一+ a z - , e 2 - , ， 凡 ， 不 同 时 为 零 生 成 的 子 空 间 ， 因 此 m 中 含 有 位 2 - 1 为 2 r- 5 + k 个 收 方 解 码 规 敌方模仿攻击成功的概率为 二 二 - q 卜五 辛 1. 任 意 两 个 消 息 最 多 包 含 (q 41 “ 十 个 收 方 解 码 规 则 ， 因 此 敌 方 替 换 攻 击 成 功的概率为 q2 _ 1 21-6+k = 1q2 _ 1 2- 5+1 - 9 0 证毕 引理3 . 6 . 发方模仿攻击成功的概率 p r = 共 q+k 证明: 任取发方的一个编码规则，由可迁性， 我们不妨假定这个编码规则为子空 间 ( e e , , e ,+i e 2 . e 2 ,+ , 其 中 含 有 收 方 解 码 规 则 为 ( e , , , ,e , + e ,+ , + 12e2, + a n . + ,e z . + , 卜其 中 凡 ， 凡 ， 不 同 时 为 零 。 因 此 ， 一 个 发 方 编 码 规 则 含 有 位 ， 一 1 为 个 收 方 解 码 规 则 。 任 意 一 个 不 是 发 方 第3 章 具有仲裁的认证码构造及参数计算 编码规则产生的消息最多含有( q - 1 ) q个与取定发方编码规则 ( 0 1 1 0e , + n e ze z . + 1 ) 相 关 联 的 收 方 解 码 规 则 ， 否 则 ， 这 个 消 息 就 含 有 取 定 发 方 编 码 规 则 ( e 1 1 e , 1 e ,+ 1 1 0 2 9 1 0 2 .+ 1 卜因 此 p r = q + l 证毕. 引理3 . 7 . 收方模仿攻击和替换攻击成功的概率为 当 ， 二 3 时 ， p ,. = - r ， p r , = 兴; n一k ” ” ” ， 气 一 1p q一k t t i - , , 1 11 w 一o f 才 一 1 1e , 1 一 ; 2v-s+ 2(i- p (q 2.- ， 一 ; z-0 + 1) ; ie r i = 。 ，一 ，)+ (q 一 1 ) ; i i (9 一 1) im i一 q (” 一xi-t) 彭下 下 l l l y一 2 ) q 2 ( q 2(一 ， ， 一 1 q 一 1 第3 章 具有仲裁的认证码构造及参数计算 p , =下 二* t ; = 生 : 当 ， = 3 时 ， p 当 ， 3 时 ， p 3 . 3 结论 设凡表 示 特 征 为p 的q 元 有限 域, q 丫 , p 为 素 数。 设e : 是 有限 域凡上2 v + 1 维 奇 异 辛 空 间 f ,9 (2 v + 1) 的 第i 个 单 位 坐 标 向 量 ， 其 中i= 1 ,2 , - 二 ， 2 v + 1 。 令q 为 由 e l , e + 1 , e 2 v + i 生成的 ( 2 + 1 , 1 , 1 ) 型子空间，由 e 1 , e 2 , . . . , e v - i , e v + i , e , . + 2 ， 一， e 2 -1 , e 2 v + i , e 2 + 2 ， 一 ， e 2 , + i 生成的 ( 2 v - 2 + 1 , v - l , o 型子空间记为p v 源状态为尸 中 包含q的 ( 2 v - 3 十 k ,- 2 ,k ) 型 子空间， 其中1 k 3 时，凡 = 一 q ! - k a ，p e = 生 : 该文章属于认证码方案的构作问题， 这个问题对于研究现代密码学既有理论价值 又有实际应用价值。 该文不仅丰富了 有限域上典型群的 几何学的应用内容， 而且 对于认证码的研究有重要意义。 致 谢 致 谢 在本文形成的过程中得到了我的导师南开大学数学学院金应烈教授和中国 民航大学高有教授的很多热情帮助和耐心指导， 他们对我的初稿提出了许多宝贵 的意见， 根据这些意见， 笔者进行了认真考虑和修改， 才使得本文能够比较好地 完成。 在此特向我的导师金应烈教授和高有教授表示衷心的感谢! 还要感谢我在 南开大学学习期间的诸位授课老师和郭振远老师的辛勤工作以及他们给予我的 许多帮助和教诲 参 考 文 献 参 考 文 献 1 g j . s i m m o n s . a u t h e n t i c a ti o n t h e o r y / c o d i n g t h e o ry . a d v a n c e i n c r y p t o l o g y - c ry p t d 8 4 . l e c t u re n o t e s i n c o m p u t e r s c i e n c e 1 9 6 . s p r i n g e r - v e r i a g . b e r l i n 1 9 8 5 , 4 1 1 - 4 3 1 . 2 g j .s i m m o n s . m e s s a g e a u t h e n t i c a t i o n w i t h a r b i t r a t i o n o f t r a n s m i tt e r / r e c e i v e r d i s p u t e s . p r o c . e u r o c r y p t 8 7 . l e c t u r e n o t e s i n c o m p u t e r s c i e n c e 3 0 4 . s p r i n g e r - v e r l a g . b e r l i n 1 9 8 5 , 1 5 1 - 1 6 5 . 3 杨义先， 孙伟，钮心忻.现代密 码新理论.科学出版社，北京， 2 0 0 2 . 4 王永川， 杨义先. 有仲裁人认证码的信息论下界.电 子学报，1 9 9 9 , 2 7 ( 4 ) : 9 0 - 9 3 . 5 裴定一a p r o b l e m o f c o m b i n a t o r i a l d e l a t e d t o a u t h e n t i c a t i o n c o d e s . j . o f c o m b i n a t o r i a l d e s i g n s . 1 9 9 8 , 6 :4 1 7 - 4 2 9 . 6 t .j o h a n s s o n . l o w e r b o u n d s o n t h e p ro b a b i l i t y o f d e c e p t i o n i n a u t h e n t ic a t i o n w it h a r b itr a t i o n . i e e e t r a n s a c t i o n s o n i n f o r m a t i o n t h e o ry , v o l .4 0 .n o 5 . s e p t e m b e r 1 9 9 4 7 d . r . s t i n s o n . a c o n s t r u c ti o n f o r a u t h e n t i c a t i o n / s e c r e c y c o d e s fr o m c e r ta i n c o m b i n a t o r i a l d e s i g n s . c ry p t o 8 7 , s p r i n g e r - v e r l a g , 3 5 5 - 3 6 5 8 1 y .s o n g , k .k u r o s a w a , s .t s u j i i . a u t h e n t i c a t i o n c o d e s b a s e d o n a s s o c i a t i o n s c h e m e s . i e i c e t r ans . f u n d a m e n t a l s , 1 9 9 6 , e 7 9 - a ( 1 ) : 1 2 6 - 1 3 0 . 9 g v s e r g e . a n o t e o n a u t h e n t i c a t i o n c o d e s fr o m a l g e b r a i c g e o m e t ry . i e e e t r a n s a c t i o n s o n i n f o r m a t i o n t h e o r y , 1 9 9 8 , 4 4 ( 3 ) 1 0 万哲先，戴宗铎， 冯绪宁等. 有限几何与不完全区组设计的一些研究. 科学出版社， 北 京， 1 9 6 6 . 1 1 万哲先. c o n s t r u c t io n o f c a rt e s i a n a u t h e n t i c a t i o n c o d e s fr o m u n i t a ry g e o m e t ry . d e s ig n s , c o d e s and c r y p t o l o g y . 1 9 9 2 , 2 : 3 3 3 - 3 5 6 . 1 2 冯荣权 n o t h e r c o n s t r u c t i o n o f c a r t e s i a n a u t h e n t i c a t i o n c o d e s fr o m g e o m e t ry o f c l a s s i c a l g r o u p s . n o rt h e a s t m a t h e m a t i c a l j o u rn al . 1 9 9 9 , 1 5 ( 1 ) : 1 0 3 - 1 1 4 仁 1 3 游宏， 高有. s o m e n e w c o n s t r u c t i o n s o f c a r t e s i an a u t h e n t i c a t i o n c o d e s fr o m s y m p l e c t i c g e o m e t rys y s t e m s c i e n c e an d m a t h e m a t i c a l s c i e n c e . 1 9 9 4 , 7 ( 4