（基础数学专业论文）用线性码构造认证码.pdf

扬州大学硕士学位论文 摘要 消息认证是信息安全领域里的一个重要研究课题，认证码是用于在公用信道上实现消 息认证的编码办法，这一问题的研究起源于上世纪7 0 年代，g i l b e r t ，m a c w i l l i a m s 和s l o a n e 提出了认证码( a u t h e n t i c a t i o nc o d e ) l 拘概念。多年来，人们通过代数、有限几何、组合设计 和编码理论的各种方法得到了一系列安全性能良好，参数灵活的认证码。它们对于解决信 息安全领域的实际问题，具有重要的理论价值。 在现代认证码的理论模型中，对信息发送过程的攻击有两种，一种是冒充信息的合法 发送者伪造虚假信息，称为冒充攻击( i m p e r s o n a t i o na t t a c k ) ；另一种是将合法发送方的消息 篡改，再将其发送给接收者( r e c e i v e r l , 称为替换攻击( s u b s t i t u t i o na t t a c k ) ，通常记这两种攻 击成功的概率分别为只和只认证码研究的一个重要课题是如何确定这两个概率的下界； 另一个研究课题是构造一些能够达到或者渐进达到这些下界的认证码。 认证码按照是否带有加密功能分为两种。近年来，通过代数纠错码理论构造不具有加 密功能的认证码得到了广泛的研究。但是一般说来，完全确定一种认证码的e 和只仍然是 一个非常困难的问题。很多构造方案只能大略估计这两个指标，这给认证码的安全性能分 析造成很多不便。 本文考虑了有限域上的某些线性码，用通过它们构造出三种新的认证码。利用这些线 性码的已有结果，和指数和这有力工具，计算出了码字任一码字中的各字母出现的次数。 由此计算出了所构造出的认证码的冒充攻击概率和替换攻击概率，且此种认证码的冒充攻 击概率和替换攻击概率能达到组合界 我们可以计算出三种认证码能够成功抵抗冒充攻击和替换攻击的概率，这是衡量认证 码安全性能的重要指标。这三种新认证码的上述指标均达到或是渐进达到了理论上的最优 结果。对比近年前人通过代数纠错码构造的结果，在源消息空间同样大的情况下，这三种 新的认证码能够使用比其它认证码小的密钥空间达到同样的安全性能。 关键词：认证码冒充攻击替换攻击纠错码指数和 涂睿：j j 线性码构造认证码 a bs t r a c t 3 一 m e s s a g ea u t h e n c a t i o ni sa r l i m p o r t a n ts u b j e c to fi n f o r m a t i o ns e c u r i t y a u t h e n c a t i o nc o d ei sa s u b c l a s so fc o d i n gt h e o r yf o rm e s s a g ea u t h e n t i c a t i o no np u b l i cc h a n n e l i nm a n yy e a r s ，b y m e a n so fa l g e b r a ，f i n i t eg e o m e t r y , c o m b i n a t o r i a ld e s i g n sa n dc o d i n gt h e o r y , al o to fg o o d a u t h e n t i c a t i o nc o d e sh a v eb e e nc o n s t r u c t e d t h e ya r ev a l u a b l ef o rs o l v i n gt h ep r o b l e m si n i n f o r m a t i o ns e c u r i t y a u t h e n t i c a t i o nc o d ei nt h em o d e mt h e o r ym o d e l ，t h ei n f o r m a t i o ns e n tt oa t t a c kt h ep r o c e s s t h a tt h e r ea r et w ot y p e so fi n f o r m a t i o np o s i n ga sal e g i t i m a t es e n d e rf o r g e df a l s ei n f o r m a t i o n ， k n o w na st h ei m p e r s o n a t i o na r a c k t h eo t h e ri sal e g i t i m a t es e n d e rw i l ld i s t o r tt h em e s s a g ea n d t h e ns e n di tt ot h er e c e i v e r , k n o w na st h es u b s t i t u t i o na a a c k ，u s u a l l yi nm i n dt h et w oa t t a c k s w e r es u c c e s s f u la n dt h ep r o b a b i l i t y a u t h e n t i c a t i o nc o d ea sa ni m p o r t a n tr e s e a r c hi s s u ei sh o wt o d e t e r m i n et h e s et w oi nt h el o w e rb o u n do fp r o b a b i l i t y ；a n o t h e rr e s e a r c ht o p i ci st h es t r u c t u r ec a n b ea c h i e v e dan u m b e ro fp r o g r e s s i v ea c h i e v e m e n to ft h e s el o w e rb o u n d so ra u t h e n t i c a t i o nc o d e s t h e r ea r et w ok i n d so fa u t h e n c a t i o nc o d e s ：a u t h e n c a t i o nc o d e sw i t he n c r y p tf u n c t i o na n d a u t h e n c a t i o nc o d e sw i t h o u te n c r y p tf u n c t i o n r e c e n t l y , c o d e sw i t h o u te n c r y p t i o nh a v eb e e n s t u d i e db ym e a n so fc o d i n gt h e o r y i nt h i sa r t i c l e ，w ec o n s i d e ru n i f o r me n c o d i n gc o d e si ng a l o i s f i e l d ，a n du s et h e mt oc o n s t r u c tn e wa u t h e n c a t i o nc o d e s b yu s i n gc e r t a i nr e s u l t s ，w ec o m p u t e t h ep r o b a b i l i t i e sp la n d p 。o ft h o s en e wc o d e s ，w h i c ha r ei m p o r t a n tc r i t e r i a f o re v a l u a t i n gt h e s e c u r i t yl e v e lo fa u t h e n c a t i o nc o d e s t h ec o d e sw ep r o d u c e dh e r ea r ea l lo p t i m a lo ra s y m p t o t i c o p t i m a l w ec o m p a r eo u rc o d e sw i t hr e s u l t sc o n s t r u c t e di nr e c e n ty e a r sa n df i n do u tt h a tw h e n t h es o u r c es t a t es p a c e sa r et h es a m es i z e ，o u ra u t h e n c a t i o nc o d e su s es m a l l e rk e ys p a c et o a c h i e v et h es a m es e c u r i t yl e v e l k e y w o r d s ：a u t h e n t i c a t i o nc o d e si m p e r s o n a t i o na t t a c k s u b s t i t u t i o na t t a c k e r r o r c o r r e c t i n gc o d e se x p o n e n t i a ls u m 涂睿：h j 线性码构造认证码 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研究成果。 除文中已经标明引用的内容外，本论文不包含其他个人或集体已经发表的研究成果。对本 文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人 承担。 ：粥 年二月严，日 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，l i p 学校有权保留并向国家有关 部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅。本人授权扬州大 学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。同时授权中国科学技术信息研究所将本学位论文收录 到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。 学位论文作者签名： 签字日期年f 月，嵋 导师签名臻键沙 签字日期一年么月，彳 l 本页为学位论文末页。如论文为密件可不授权，但论文原创必须声明。1 名 签 者作 ： 文 期 论 日 位 字 学 签 扬州大学硕士学位论文 4 第1 章引言弗l 早 了li 1选题背景及意义 认证码是编码理论和信息安全领域的一个重要课题。这一问题的研究起源于上世纪7 0 年代，g i l b e r t ，m a c w i l l i a m s 和s l o a n e 提出了认证码( a u t h e n t i c a t i o nc o d e ) 的概念，这是一种 在公开信道( p u b l i cc h a n n e l ) 上对信息实现消息认证的编码方法，能够确认消息来自正确的 发送者( t r a n s m i t t e r ) 而不是敌对者( o p p o n e n o ，从而可以防止消息被敌对者冒充或者篡改。 到2 0 世纪8 0 年代，s i m m o n s 建立了无条件认证理论，使认证码的理论逐步完善。 在现代认证码的理论模型中，对信息发送过程的攻击有两种，一种是冒充信息的合法 发送者伪造虚假信息，称为冒充攻击( i m p e r s o n a t i o na t t a c k ) ；另一种是将合法发送方的消息 篡改，再将其发送给接收者( r e c e i v e r ) ，称为替换攻击( s u b s t i t u t i o na t t a c k ) ，通常记这两种攻 击成功的概率分别为异和只。认证码研究的一个重要课题是如何确定这两个概率的下界； 另一个研究课题是构造一些能够达到或者渐进达到这些下界的认证码。 自认证码的概念提出以来，运用代数、组合、编码理论和概率统计等各种工具，人们 提出了多种构造认证码的方法。这些方法构造的认证码有些能够达到或者渐进达到只和只 的下界。但是一般说来，完全确定一种认证码的e 和只仍然是一个非常困难的问题。很多 构造方案只能大略估计这两个指标，这给认证码的安全性能分析造成很多不便。 这篇论文利用有限域上的某些线性码构造新的认证码。利用这些线性码的已有的结果， 我们可以计算出只和只的准确值，它们均能达到或者渐进达到理论上的下界。与已有的构 造方法相比，这些新方法构造的认证码在源信息空间( s o u r c es p a c e ) 、安全性能和其他认证 码差不多的前提下，具有较小的密钥空间。因此，这些认证码都是好码。 2 本文的结构安排 本文的结构安排如下： 第二章主要介绍认证码和线性码的基本概念，通过线性码构造认证码的方法等。 第三章构造第一种新的认证码，我们主要利用有限域上的线性码权分布的相关结果。同时 将我们的构造方法和已有的构造方法相比较。 第四章构造第- 种新的认证码，主要利用线性码权重的迹表达式，分析这种认证码的安全 性能。 涂存： f j 线性码构造认证码 第五章构造第三种新的认证码，主要利用一类线性码的权分布的结果，同时分析这种认 码的相关性能。 扬州大学硕士学位论文 第2 章基本概念和准备知识 2 1 认证码的基本概念和相关知识 在认证码的基本模型中，有三个主要角色：发送者，接收者和敌对者。发送者希望通 过一个公用信道发送消息给接收者。为此，发送者和接收者需要共享一个密钥r ，所有的 密钥构成一个集合，称为密钥空间k 。同时，每一个密钥髟对应一个映射e 。，将信息s 转 换成一个消息m = ( s ，e 。( s ) ) 所有可能的信息s 构成信息空间s ，所有的消息m 构成消息 空间m 所有的编码规则e 。也构成一个空间，记为q 总之，一个基本的认证码可以表 示为四元组( s ，k ，m ，q ) 一般的，对于不加密的认证码，消息m = ( s ，t ) ，s 是源信息，f 称 为标记( t a g ) 所有的标记构成的集合称为标记空i 司( t a gs p a c e ) ，记为r 当发送者发送信 息s 时，先计算出t = e 。( s ) ，然后再将m = ( s ，t ) 发送给接收者。接收者收到消息m 后，再 验证是否有t = e 。( j ) 成立。如果成立，则说明消息来源于正确的发送者；否则就拒绝接受 此消息。 由于信道的公用性，敌对者可以截获甚至篡改消息。在s i m m o n s 引入的认证码模型中， 敌对者可以在信道中插入一个消息或者将截获的消息替换成另外的消息。这样就产生的两 种攻击方式：冒充攻击和替换攻击。冒充攻击是敌对者选择一个消息m = ( s ，t 。) ，通过公 用信道发送给接收者，让接收者误认为是正确的发送者发出的，为此必须满足f = e 。( s ) 我们用只表示这种攻击成功的最大概率。另一种攻击称为替换攻击，是指敌对者截获来自 发送者的一个消息m = ( s , t ) ，将其替换成另一个消息m = ( s ，t ) 并将它发送给接收者，让接 收者误认为是正确的消息从而欺骗成功。我们用只表示这种攻击成功的最大概率。这两种 概率的计算公式分别是 p ：m a x ! ! 竺三垦些盟三生 。 s e s ，r e r k i 涂容：刖线性码构造认证码 7 一 ，：；=：。，m。，a，x，；，!j!：!；：i；i；!群 为了增加欺骗成功的概率，敌对者会选择特定的消息发送，因此我们必须考虑最坏的 情况，这样我们就取最大值。衡量一个认证码的性能的好坏，只和只是一个重要的指标。 能够达到或者渐进达到弓和b 值下界的认证码被认为是好的认证码。 t i 面- - t 2 , i f 介绍弓和b 的几个重要的下界。 定理2 1 ( b r i c k e l 界，见 1 ) 只2 m m n m 们 这里( ) 表示的熵( e n t r o p y ) 定理2 2 ( 信息论界，见 2 ) 定理2 3 ( 组合界，见 3 ) 只2 m 州) 一( m ，b 2 刊m 2 m 州) 只盟，只上坚 。 im 3 iml _ 1 如果上面的等号都成立，我们有l q | i mi 2 2 线性码和循环码的概念 下面我们介绍有限域上的线性码和循环码的一些基本概念。关于有限域的详细内容， 参见 4 。关于编码理论基本知识的详细陈述，参见 5 记g f ( q ) 是有q 个元素的有限域。有限域的基本知识告诉我们q = p 。，其中p 是一个 素数，称为g f ( q 1 的特征( c h a r a c t e r i s t i c ) 定义2 1 设圪= g f ( q ) “表示g f ( q ) 上的n 维向量空间。k 的一个非空子集c 称为一个q 元 码，n 叫做该码的码长，c 中的向量称为码字( c o d e w o r d ) 如果c 是_ 的g f ( q ) 一线性子空 扬州大学硕士学位论文 间，那么c 叫做线性码。l o g 。| ci 叫做c 的信息位数。 定义2 2 设c = ( c ，c ：，c 。) 是一个聆维向量，c 的非零坐标数称为c 的汉明权( h a m m i n g w e i g h t ) ，记为( c ) 对一个，z 位的q 元码c ，c l ，c 2 c 是两个不同的码字，我们称 w m ( q c 2 ) 是c 和c ：的( 汉明) 距离( h a m m i n gd i s t a n c e ) ，c 中两两互异的码字的汉明距离的 最小值称为c 的最小距离( m i n i m a ld i s t a n c e ) ，记为d 特别地，若c 是线性码，最小距离d 也是最小非零汉明权。 在编码理论中，信息位数决定了编码选择范围的大小，而最小距离是衡量码c 的检错 和纠错性能的唯一指标。一般的，最小距离为d 的码c ，可以检查出不超过d 1 个错；若 用于坌q 错 则可以纠正至多不超过 爿个错，其中【】表示不超过的最大整数。编码理 论中的个重要问题就是寻找信息位数和最小距离都比较大( 相x 寸石- q k n ) 的码。 定义2 3 线性码c 称为循环码是指若码字c = ( c 。，c 1 ，c 。一，) c ，则c 的循环移位 ( 巳小c 。，c ，c 州) 也是c 中的码字。从而c 的所有循环移位都是c 中的码字。 我们可以把码字c = ( c o ，c 1 ，c n 一。) 表示为一个多项式 c ( x ) = c o + c l x + + 巳一l x “一1 g f ( q ) x 于是 x c ( x ) = c o x + c , x 2 + + c n 一2 x ”一1 + c 。一i x 4 c n l + c o x + c l x 2 + + c n 一2 x ( m o dx 刀- 1 ) 对应c 的循环移位( 巳小c o ，q ，c 柚) 从而对任意的厂( x ) 卯( g ) 【工】， 厂( x ) c ( x ) ( m o dx ”一1 ) 都对应到c 中的码字。在这种对应下，我们可以把看成卵( 留) 向量 _ v _ i mr = g f ( q ) x ( x 以一1 ) ，这样循环码c 就是r 的理想。下面我们就将循环码和r 的理 想等同起来。抽象代数的知识告诉我们r 是主理想环。设c 是由g ( 工) 生成的，于是 c = ( g ( 工) ) = f ( x ) g ( x ) l f ( x ) r ) 涂j 徉：川线性码构造认证码 为方便起见，我们可以取g ( x ) r 是x ”一1 的首一多项式因子。同时，这种取法是唯一的， 我们称g ( x ) 是c 的生成多项式( g e n e r a t e dp o l y n o m i a l ) ，而 ( x ) ：三；称为c 的校验多项式 g u j ( p a r i t y - c h e c kp o l y n o m i a l ) 设c 是码长为甩= q 一1 ，校验多项式为h ( x ) 的循环码。设h ( x ) = 啊( 工) 吃( x ) h s ( x ) ， 其中囊( x ) ( 1 i s ) 是d 。次不可约多项式。于是c 的信息位数k = d i m 舒( ，) c 设万是 g f ( q ”) 中的+ 个本原元( p r i m i t i v ee l e m e n t ) ，1 一分别是囊( x ) ( 1 i s ) 的。个根。于是c 中 的每个码字可以表示成( 见 5 ) 吃( z ) = x + x q + 哪g 从而c ( a 。，1 7 1 2 ， 口，) 的h a m m i n g 权可以表示成如下的形式 b ( c ( 口l ，口2 ，哎) ) = i i o f g ”一2 , c i o ) = 口”- 1 - # i l o i 2 ，是奇数，且! 土是奇数； 门 刀，劫：2 ，是偶数，或盟是偶数； n 设0 k m 一1 ，a g f ( q ) ，b g f ( q ) ，定义 瓯( 口，6 ) ：乞碣“一删 x g f ( q ) 1 3 _ _ 一 设眈。o ) = 口，x ，”+ a x + b p ，x o 是纯，。 ) = 0 在g f ( q ) 中的一个解( 如果存在的话) ，则 我们有如下的结果。 定理2 1 2 ( 见 1 4 ) 扬州大学颂士学位论文 1 4 ( 1 ) 若m d 为奇数，则纯。( 工) = 0 的解存在且唯一，于是 驰= ( - 1 ) m - 高嚣“矿若：p 叫- l ( 删m o d ： 其中7 7 ( ) 是二次剩余符号。 ( 2 ) ? 著m d 为偶数，则纯6 ( 工) = o 无解，唯解或有p 2 d 个解，于是 文( 口，b ) = ( 一1 ) 西r n 乞一，( 嘞，+ “p 詈， ( 一1 ) 昙+ 1 - 一，( 口。b ，“p 三十。， 0 ， 若纯6 ( 工) = 0 有唯一解， 若纯6 ( x ) = o 劫2 4 个解， 若纯。( 工) = o 有无解。 第3 章利用g o id 函数构造认证码 本章我们用g o l d 函数构造循环码，再由它构造新的认证码。通过计算该函数，我们可 以得到这种认证码的层值，该值能够渐进达到组合界。 3 1 构造循环码 设p 是奇素数， q = p ”，万是g f ( q ) 的一个本原元，0 七聊一1 且后，z 2 d 2 9 c d ( m ，后) ，f f d ，= m t ，s = m d ，g o = p d 定义w e i l 和瓯( 口，6 ) = ，( “，+ 1 + 捌 x e g f ( q ) 则足( 口，b ) 的详细计算见第二章，定理2 。1 2 设噍( 工) ，吃( z ) g f ( p 。) z 】分别是万一小n ，万一的极小多项式，c 是以 ( x ) 噍o ) 为校验多 项式的循环码，则c 定义在6 f ( p ) 上，码长为9 1 ，维数为2 ，_ g lc 中的码字可以表示 成c ( 口，6 ) = ( 亿( 口“) + 切) ) ：，其中口，6 g f ( q ) 而c ( 口，6 ) 的h a m m i n g 权可以表示 成 吲如6 ”叫_ 汩”号。磊，) 蹦c o a , c o b ) 设( 口，b ，“) 为码字c ( 口b 1 中u 出现的次数。 定理3 1 若s 为奇数，且口0 ，则 ( 1 ) 如果u 0 ，我们有 忡点炉 p 巍叫， ( 2 ) 如果“= 0 ，我们有 若s 为奇数， 若s 为偶数且s 2 是奇数， 若s 2 为偶数 扬州大学硕士学位论文 m 炉 p 颡毒 若s 为奇数， 若s 为偶数且s 2 是奇数， 若s 2 为偶数 证明：记7 v 是亿，( a x ，+ 1 + 搬) = “在卵( g ) 中解的个数。则 m = 慨篆爱 由于 p r ：t r 打，( ( _ ，( “p k + l + b x ) - “) ) x e g f ( q ) m g f ( p 7 ) ：g + 乞一。( 乞啊一 + 砌) w e g f ( p ) x e g f ( q ) = g + 0 一o ，一训( 踟，动) o * g f ( p ) ( 1 ) 若s = m d 是奇数，则 ，= 悔器；篡伟若p 趔- l ( 删m o d 其中j c 0 是方程( 伽) px p ”+ ( 伽冷+ ( 动) = o 的解( 对任意的6 g f ( q ) ，口g f ( q ) 。解都是 唯一的) 。由于缈g f ( p 4 ) _ h d lk ，因此方程等价于口p 。x p 2 + a x + b ，= o 故与缈无关。 ：矿，+ ( 一1 ) 川7 7 ( 一口) p 争刁( 甜) h 一) ) e 6 ，( p ) = p ”+ ( 一1 ) ”1 叩( 一口) p j 7 7 ( 一( a x o ，1 ) 一蹦) g ( 7 7 ，z ) m - ! = p ”一p 2 其中7 7 是g f ( p ) 上的二次剩余，g ( q ，z ) 是卵( p ) 上的g a u s s 和。 若p 兰3 ( m o d4 ) ，和类似，我们可得 涂睿：朋线性码构造认证码 脚“小t 州州r - - - - - m 3 m 咖m - - 2 - t 磊咖) h ( 矿h ) ) = p “+ ( 一1 ) 剃( 打) 抽7 7 ( 一口) p ( 一( ，) 一“) g ( ，7 ，z ) = p r o - , + ( 一1 ) 引( 历) 抽7 ( 一n ) p ( 一( ，) 一“) ( 一1 ) h ( 打) = p ”一p2 ( 2 ) 若s = m d 是偶数，则与上面的讨论相似，我们有下面的结论 s k ( c o a ，础) = ( 一1 ) 五m 乞吲+ p ：， ( 一1 ) 争幺一，t 蛐山) 户， 若口p x p ”+ 烈+ 6 = 0 有唯一解， 若口，x ，2 + a x + b ，= o 葡2 。个解，( 5 ) 若口p 工，”+ 烈+ 6 ：0 有无解 1 7 _ 一 其中确是方程口，工，”+ a x + b p = o 的一个解( 也是( 踟) ，x p 2 t + 伽+ ( 砌) 户= 0 的一个解 如果存在的话) 于是我们有 若口p x p ”+ 甜+ 6 p ：0 有唯一解，则 ：p m t + ( 一1 ) 云p 詈一乞。( 一，( 蛳，“h ) ) * g f ( p ) 若口口x ，“+ a x + b p o 鄢2 4 个解，则 若( 甜0 ，) + 群= 0 ， 若，( 9 ) + “o ：p m ，+ ( 1 ) 刍+ 1p 詈+ d 一以n 巾( 一n ；矿( 。d ，+ 1 ) 一”) ) w e g f ( p 。) 若口尸工，“+ a x + b p = o 无解，则n ：p m 综上所述，我们可得结论。口 3 2 构造认证码 我们可以构造认证码： 若亿，( a x o 尹) + “= o ， 若巩( ，+ 1 ) + “o 一 生： 。p 旦“ 旦一 y ， ) r i ， 1 一 ，一、 ( + 叫 卜 沙 扩 扛 + ： p 一 豳 竺矿 + 一厶 争 e l 旷 卜 “ + 吖 h ， p ，f，【 = 扬州大学硕士学位论文 ( s ，r ，k ，q ) = c ，g f ( p ) ，z ( q 一1 ) z g f ( p ) ， ：七k ) ) ( 6 ) 其中对任意的七= ( 七。，k ：) ek 和j s ，e k ( s ) = c ( a ，6 ) + k 2 ，c ( a ，6 ) 岛表示码字c ( a ，6 ) 的第 毛位元素。 上面构造的认证码具有如下参数 定理3 2 对由c 构造的认证码( 6 ) ，我们有： s | _ q 2 ，itj p 。，ikl = 夕( p ”- 1 ) 暑：三， ： p 。 p ”一+ p ( ) 7 2 p ”一1 若s 是奇数， ! 二二芈，若占为偶数且s ，2 是奇数， p m - t + ( p i t _ _ 1 ) - p m 2 一+ d - t ， 若s 2 是偶数。 口 丐正r 一酬“疋i 内蜘 。 上述定理构造的认证码的e 值可以达到组合界，而只值在聊专o 。时可以渐进达到组合 界。我们构造的认证码在t = 1 时的性能参数和定理2 6 中的认证码的性能差不多，但是在 我们的构造方案中t 的取法自由度更大( id ) 涂睿：川线性码构造认证码 第4 章利用函数口x p 1 + 肛2 + 7 x 构造 认证码 本章用函数a x 矿+ 1 + p x 2 + y x 构造另一种新的认证码。通过有限域上的理论，我们计 算出了这类认证码的e ，它能够渐进达到组合界。此外，这种认证码的e 值能够直接达到 组合界，因此它也是一种性能良好的认证码。 4 1 构造循环码 在这章里我们总设p 是奇素数，q = p ”，刀是g f ( q ) 的一个本原元，0 k m 一1 且 d = g c d ( m ，七) ，tld ，s = m d ，g o = p 4 s ( 口，y ) ：乞t r q p ( a x p k + l + 肛2 + ) 设 s k ( a ，y ) ，利用定理2 1 2 我们有下面的结果 对口，y g f ( q ) ，定义指数和 纥，口( x ) = + p x + 口x 则对 定理4 1 ( 见 1 3 ) 方程纯。，( x ) = - y p 在g f ( g ) 中至多有p 2 。个解并设而是其一个解( 如果 有的话) ，记p = 亿，p ( 一纯。( ) ) ，则我们有 ( 1 ) 若纯，口o ) = 一7 p 在g f ( g ) 中只有唯一解，则 f f 。p 州2 ，若q o - - l m o d 4 ， 蹦厉力2 1 ( 矗) 5 枷，若矧m o d 4 ( 2 ) 若纥，口( x ) = 一厂，在卵( g ) 中有p d 个解，则 f f 。p ( + 4 ) 门，若q o 三l m o d 4 ， 蹦展力2 ( 矗) 川驯z ，q o - = 3 m o d 4 ( 3 ) 若，口( x ) = 一y p 在凹( g ) 中有p 2 d 个解，则 f 乞。p ( m + 2 d ) 2 ， 若q 兰i r o o d 4 - ar t ， 蹦屈力2 1 ( 历) 5 z 川z 尚。- - 3 m o d 4 扬州大学硕士学位论义 ( 4 ) 若纥，( x ) = 一7 p 在卯( 9 ) 无解，贝l js , ( a ，y ) = 0 口 设j l z i ( x ) ，吃( x ) ，呜( x ) eg f ( p 7 ) x 】分别是乃却，万- 2g 一1 的极小多项式， c 是以 呜( 工) 吃( x ) 岛( 工) 为校验多项式的循环码，则c 定义在g f ( p ) 上，码长为g 一1 ，维数为3 m t ， 且c 中的码字可以表示成c ，厂) = ( t ( 筋“，”+ 伽2 。+ 肛) ) ：，其中口，7 g f ( q ) 而c ( a ，厂) 的h a m m i n g 权可以表示成 ( 和以朋= ( p t - 1 ) p r n - - g l p 。荔f ) 瓯( 国口，筇，彤) n ( a ，夕，7 ，u ) 为码字c ( 口，夕，y ) 中“出现的次数。 定理4 2 若s 为奇数，且a 0 ，则： ( 1 ) 如果甜0 ，我们有 炉k z z a l - f + d ，巍萋! ( 2 ) 如果“= 0 ，我们有 心= m _ t + d 囊，雾翥萋! 证明：记是，( a x 矿+ 1 + f l x + r x ) = “在g f ( g ) 中解的个数。则 m 彤炉慨篆三： 由于 p ，：乞嘣口( 机卅u ) j x e g f ( g ) m e g f ( p 1 = g + 乞一啊“乞q “一”、础恻曲 = g + 乞一p & ( 缈口，筇，o r ) ( 7 ) 涂睿：用线性码构造认证码 下面分情况讨论： ( 1 ) 若纯，口( x ) = 一y 尹在g f ( g ) 中只有唯一解，则对任意的国g f ( p d ) ，而也是方程 ( 缈口) 矿x p 2 k + ( 缈口) 工+ ( 筇) = 0 的解( 由于g f ( p 。) ，di 七从而国j d = c o ) 因此方 程等价于 若s 是偶数，将定理4 1 代入( 7 ) 可得 r = ：p ，”一，p 詈一乞n ，( 一f ( 口而，+ l + j 口葡2 卜) ) 毋6 ，( 一) p 。( p 一1 ) p 丁，若t ( a x o 1 + f i x 0 2 ) + 掰= o 【p ”。千p i ， a r r ，。( a x o ，+ 1 + p x 0 2 ) + “o 若s 是奇数且p 。兰l ( m o d4 ) ，和类似，我们可得 ：p 一p 7 7 y 妫乞勺扫( 一n ( 口风2 h ) ) = p m - t p r 刁( 一( a x o p k + l + 眠2 ) 一“) g ( 叩，z ) = p “p i 刀( 一亿，( 口山+ 鲰2 ) 一“) ( 一1 ) h 4 7 i p ”， 若 1 + p x 0 2 ) + “= o 扩。p 丁，若玩( a x o 小1 + 风2 ) + “o 其中叩是g f ( p 。) 上的二次剩余，g ( ，7 ，z ) 是g f ( p7 ) 上的g a u s s 和。 若s 是奇数且p 4 三3 ( m o d4 ) ，和和类似，我们可得 n = p - t + p 气厅) 5 刁t ( 护，( h f ( 小一切 = p “p 一( 万) 7 7 ( 一( a x o p 1 ) 一“) g ( 7 7 ，z ) = p “p 三2 ( 再) 57 7 ( 一r r ( a x o 踟) 一“) ( 咐( 汀) 万 i p 一7 ， 若( p 卅) + “= o 【p ”j d 2 ， 若( a x o 一+ 1 ) + 甜o 论 ( 2 ) 若纥，夕( z ) = 一厂p 在卵( g ) 中有p d 个解，与上而的讨论相似，我们有下面的结 若j 是奇数，将定理4 1 代入( 7 ) 可得 ：p 一p 争以。h ”p 蝴一口) ) g f ( p r rm + d lp ”。( p 。一1 ) p _ 。，若亿 j c o ，+ + 风2 ) + “= o 2 1州， 【p ”干p2 ，若巩以而+ 1 + 风2 ) + “0 若j 是偶数且p 4 兰l ( m o d4 ) ，和类似，我们可得 ：p 一p m r + d 7 7 ( 曲乞。巾( 一一( 8 山+ 球h ) ) g f ( p ) = p r o - , + p 下n t + a 一刁( 一( 口而山+ 厩2 ) 一甜) g ( 7 7 ：z ) m + d = p m - t p t 一叩( 一( a 而p t + l + 风2 ) 一“) h 一 其中卵是凹( p ) 上的- 次剩余，g ( 7 7 ，z ) 是g f ( p ) 上的g a u s s 和。 若s 是偶数且p 4 三3 ( r o o d4 ) ，和和类似，我们可得 n = p m - + p 气压) 7 阿( “- l ) ) = p r o - , + p 下。( j ) 17 7 ( 一( 1 ) 一“) g ( 7 7 ，z ) = p “p - c - * ( 行) ”1 ，7 。( 一 a x o ) 一“) ( 咐1 ( 何) 7 p ”7 ， 若玩( ) + “= o l p ”7 p 2 ， 若亿( a x o ，“) + “0 ( 3 ) 若，口( x ) = 一在凹( g ) 中有p 2 d 若s 是偶数，将定理4 1 代入( 7 ) 可得 解，与，j ：面的讨论相似，我们有下面的结论 m 风妒 吖 “ 替。 若 竿 矿 涂睿： j 线性码构造认证码 ：p 一p 弘彭叫文一 咖) ) ip “( p 。一1 ) p i “，若亿( o x o p * + i + f l x 0 2 ) + “= 0 ip ”干p i 州，若亿( 口踟+ f l x 0 2 ) + “o 。若s 是奇数且p 。兰l ( m o d4 ) ，和类似，我们有 ：p 一p 扣叩( ) t r ，( 可一已一f “+ 掰h ) ) o g f ( p ) = 。p _ + 扣，7 卜珑 1 + f l x o pi 2 ) 一“) g ( 叩，z ) p l ( a x o = ”。p 2 ，7 ( 一亿 ”1 + 2 ) 一“j g ( 叩，z ) ：p 删p 芎“7 7 ，卜亿( a x o 鼬+ 鲰2 ) 一甜) ( 一1 ) 川石 = 删p 2 7 7 卜以”+ 鲰2 ) 一甜j ( 一1 ) 。1 l p ”， 若( a ，+ 1 + 鲰2 ) + “= o 扩p 了”，若亿( 口而 1 + f l x 0 2 ) + “s o 其中7 7 。是卵( p ) 上的二次剩余，g ( 7 7 ，z ) 是g f ( p ) 上的g a u s s 和。 若s 是奇数且p 4 三3 ( m o d 4 ) ，和和类似，我们可得 ：p 一p 扣( 再) 川玎t ( ) 乞( 一产加一) ) = p “p p ( 压) ”27 7 ( 一( a x o p 1 ) 一“) g ( 7 7 ，z ) = p + p 兰2 “。( 历) 2 ，7 t ( 一a x o ：+ 1 ) 一“) ( 1 ( 再) 归 l p ”， 若亿( a x o ，“) + “= 0 p 叫+ p 一2 。，若吃( a x o ) + “0 综上所述，我们可得结论。口 4 2 构造认证码 利用前面的方法我们可以构造如下的认证码： ( s ，丁，k ，q ) = c ，g f ( p 气z ( q - 1 ) z x g f ( p f ) ， ：尼k ) ) ( 7 ) 其中对任意的k = ( 矗，k ：) k 和j s ，e ( s ) = c ( a ，b ，c ) 屯+ 七：，c ( a ，b ，c ) 。表示码字c ( 口，b ，c ) 扬州大学硕士学位论文 的第k 。位元素。 上面构造的认证码具有如下参数 定理4 3 对由c 构造的认证码( 7 ) ，我们有： s = q 3 ，itl - p ，ikl = p ( p - 1 ) z ： ，： p p - , + - p ( m - t 一) 2 + d ， 若j 是奇数， p ”- 1 。 竺二2 # ，若s 为偶数。口 p ”一1 。 上面构造的认证码的只值可以达到组合界，b 值可以渐进达到组合界( 朋专o 。) 这一小节中，我们利用函数结合方程解的问题构造出了一类循环码。利用指数和这一 有力工具，计算出了码字任一码字中的各字母出现的次数。由此计算出了所构造出的认证 码的冒充攻击概率和替换攻击概率，且此种认证码的冒充攻击概率和替换攻击概率能达到 组合界 滁睿：h j 线性码构造认证码 第5 章利用函数口x ，妯+ l + 肛，。i + y x 构 造认证码 本章用函数口x p + 1 + p x p + 1 + 7 x 构造第三种认证码。通过计算，得出这类认证码的b 值，该值能够渐进达到组合界。通过与近年来前人构造的其它认证码相比较，这种新的认 证码“b y , 够用较小的密钥空间达到同样的安全性能。 5 1 构造循环码 在这章里我们总设p 是奇素数，q = p ”，万是g f ( q ) 的一个本原元，0 k m - 1 且 d = g c d ( m ，七) ，tld ，s = m d