（基础数学专业论文）跳频序列设计的研究和二次型函数的密码学性质.pdf

摘要 本文第一部分是围绕构造一类较好性质的跳频序列这一课题展开的：在跳 频通信系统中，跳频序列的汉明自相关和互相关特性的好坏在很大程度上决 定了系统| 睦能的优劣和容量的大小，本部分首先改进了g o n gg u a n g 等提出的 几种构造方法，利用已有的两值自相关扩频序列构造出一类新的跳频序列集 合，并利用数学思想处理其汉明相关特性，在选择合适参数时，跳频序列集合 可以达到相应的理论界限，能够较好地应用到跳频通信系统中 本文第二部分是匿绕二次型函数的密码学性质这一中心课题展开的：布尔 函数是密码学中一类重要的函数布尔函数的密码性能在一定程度上决定着 密码学体制的安全性本部分研究有限域上二次型函数的w a l s h 谱特性，并 针对有限域的特征为偶数2 和奇素数p 两种情况分别计算了各种形式下的二 次型函数的w a l s h 谱值问题最终转变为由一个二次型函数和一个线性方程 组成的方程组解的个数问题这样，一旦需要具有特定w a l s h 谱值个数的函数 时，可以很容易的从本文中找出满足条件的函数 关键词 跳颇序列，汉明相关函数，布尔函数，二次型，w a l s h 谱值 a b s t r a c t i nt h ef i r s tp a r to ft h i st h e s i sw ec o n c e n t r a t eo nt h ed e s i g no ff r e q u e n c yh o p - p i n gs e q u e n c e ss e tw i t hg o o dh a m m i n gc o r r e l a t i o n ：i nt h ef r e q u e n c yh o p p i n gs p r e a d s p e c t r u ms y s t e m s ，t h ea u t o - a n dc r o s sh a m m i n gc o r r e l a t i o np r o p e r t i e so ft h ec m p l o y s ds p r e a d i n gs e q u e n c e sp l a ya l li m p o 】x a n tr o l eo nt h ep e r f o r m a n c ea n dc a p a c i t y o ft h es y s t e m sw ei m p r o v es e v e r a lm e t h o d sb yg o n gg u a n gt oc o n s t r c tt h en e w f r e q u e n c yh o p p i n gs e q u e n c e ss e tf r o me x i s t i n g2 - v a l u ea u t o c o r r e l a t i o ns e q n e n c e si n c d m as y s t e m s a n dd e a lw i t ht h eh a m m i n gc o r r e l a 越o nb yt h em a t h e m a t i c s w i t h t h ea p p r o i a t ep a r a m e t e r s ，f r e q u e n c eh o p p i n gs e q u e n c e ss e tc a l la c h i e v et h er e l a t e d b o u n d ，w h i c hc a nb eu s e df o rf h m as y s t e m s t h es e c o n dp a r to f t h i st h e s i si sc o n c e n t r a t i n go nt h ec r y p t o g r a p h i cp r o p e r t i e so f q u a d r a t i cf a r mf u n c t i o n s ：b o o l e e mf u n c t i o n sp 1 解a ni m p o r t a n tr o l ei nc r y p t o l o g y a ts o m ed e g r e et h ec r y p t o g r a p h i cp r o p e r t i e sd e c i d e t h es e c u r i t yo ft h es y s t e m s t h es e c o n dp m ts t u d yt h ep r o p e r t i e so fw a l s hs p e c t r ao fq u a d r a t i cf o r mf u n c t i o n s o v e rf i n i t ef i e l d s 、a n dw c o u n ta l lt h ew a l s hs p e c t r ao fq u a d r a t i cf o r mf u n c t i o n w h e nt h ec h a r a c t e ro ft h ef i n i t ef i e l di se v e n2a n dp ，w h e r epi sp r i m e f i n a l l yt h e q u e s t i o ni st u r n e dt ot h ee n u m e r a t i o no fs o l u t i o n so faq u a d r a t i ce q u a t i o na n da l i n e a re q u a t i o no u rp r o o ft e c h n i q u ei sb a s e do i lc l a s s i f i c a t i o no fq u a d r a t i cf o r m s o v e rf i n i t ef i e l d s t h e no l l o ed 幅i r i n gt h eg i v e nn l n n b e ro ft h e 旭b hs p e c t r ao ft h e f u n c t i o n s ，w ec a r ll o o ku pt h er e s u l tc o r r e s p o n d i n gt ot h ec a s ei nt h i sp a r t k e yw o r d s f r e q u e n c yh o p p i n gs e q u e n c e s ，h a m m i n gc o r r e l a t i o n ，b o o l e a nf u n c t i o n ，q u a d r a t i c f o r m ，w a l s hs p e c t r a 湖北大学学位论文原创性声明和使用授权 说明 原创性声明 本人郑重声明t 所呈交的学位论文，是本人在导师的指导下，独立进行研 究工作所取得的成果除文中已经注明引用的内容外，本论文不含任何其他 个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的 个人和集体，均已在文中以明确方式标明本声明的法律后果由本人承担 论文作者签名；钐丽 签名日期：弘耐年上月玎日 学位论文使用授权说明 本人完全了解湖北大学关于收集、保存、使用学位论文的规定，即；按照 学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷 本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化 或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部 分或全部内容( 保密论文在解密后遵守此规定) 论文作者签名钐硫 签名日期：础年j 月才日 导师签名舻| 瑟 签名日期：少尹锌s 月侈日 一、序言 1 1 跳频序列研究在跳频系统中的重要性 跳频通信也是一种扩频技术，跳频系统的载波频率在很宽的频率范围内按 预定的图案( 码序列) 进行跳变发射机在某一特定的时间间隔中，用哪一个 频道发送信号，是由一个伪随机序列控制的，接收机的本地振荡信号频率如果 能与输入信号的频率按同一规律同步地跳变，则经过变频后，得到的中频信号 将原来的频率跳变解除应当指出的是，跳频系统完全不同于直接序列扩频系 统，每一个跳频的瞬闯用户所占用的信道带宽是窄频谱，只是由于跳频的速度 快，实现了在宏观上的频谱发展 跳频系统的载频受一个伪随机码控制，不断地、随机地跳变，可视作载频 按照一定规律变化的多频频移键控( m f s k ) 与直接扩频系统不同，跳频系统 中的伪随机序列并不直接传输，而是用来选择信道跳频系统主要由p n 码产 生器和频率合成器两部分组成，快速响应的频率合成器是频率跳变系统的关 键部件频率跳变系统的发射机在一个预定的频率集中，由p n 码序列控制频 率合成器，使发射频率能随机地由一个跳到另一个，接收机中的频率合成器也 按相同的顺序跳变，产生一个与发射频率只差一个中频的本振频率，经混频后 得到固定的中频信号，该中频信号经放大后送到解调器，恢复传送的信息此 外，混频器实际上担当了解调器的角色，只要收发双方同步，就可以将频率跳 变信号转换为一个固定频率的信号 与直接扩频系统一样，跳频系统也有较强的抗干扰能力对于单频干扰和 窄带干扰，跳频系统虽然不能象直扩系统那样把单频干扰和直扩干扰信号的 频谱扩展，并靠中频滤波器抑制通常带外的频谱分量，但跳频系统减少了单 频干扰和窄带干扰进入接受机的概率假设跳频系统在其跳频图案中有个 不重复的频率，干扰总数为j ，并随机地散步在整个跳频频段中，那么，干扰 落入某一个频道中的概率是p = j i v 所以从这个意义上讲，频率数值越 大，抗干扰能力就越强此外，跳频过程中，即使某一频道中出现一个较强的 干扰，也只能在某一个特定的时刻与所需信号发生频率碰撞因此，跳频系统 对于强干扰产生阻塞现象和近基站的远近效应有较强的抵抗能力 】 用于控制载波频率跳变的地址码序列称为跳频序列跳频序列的性能直接 关系到跳频系统的性能，因此，通常要求跳频序列：( 1 ) 自相关旁瓣要低；( 2 ) 互相关峰值要低；( 3 ) 数目要多；( 4 ) 线性复杂度要大；( 5 ) 各频隙的出现次 数基本相同 跳频序列的线性复杂度是衡量跳频扩频通信系统的保密强度的一个重要 指标为了获得最大强度的安全性，系统所采用的跳频序列要求具有尽可能大 的线性复杂度，因此，设计具有大线性复杂度的跳频序列是人们的一个研究重 点k u m u 设计了一类性能优良的跳频序列，并证明此类序列的线性复杂度 2 满足p + 2 1 曼2 p ，这里p 是指有限域的特征 1 2 跳频序列的研究现状与目前趋势 跳频序列族的设计主要涉及4 个参数：频隙数目口、序列长度l 、序列数 目以及汉明相关日。这些参数是互相约束的，研究这些参数之间的相互 关系，可以为跳频序列族的构造提供指导，并为评价各种构造方法的性能提供 判别标准 基于m 序列构造跳频序列族关于m 序列的数学研究早在1 9 5 0 年代中期 就开始了则始于1 9 7 0 年代基于m 序列构造跳频序列族有三种方法第一 种方法是使用m 状态序列，也就是使用不用的m 序列分配给不用用户，每个 用户的频率由m 序列的状态决定1 9 8 7 年，a a s h a a r 等m 分析了这种构 造方法的汉明相关性能 第二种方法使用抽头法1 9 7 4 年，a l e m p e l 和h g r e e n b e r g e r1 2 】提出了著 名的l - g 模型1 9 7 8 年，d v s a r a p e 和m b p u r s l e y 【3 j 指出l g 模型存在 严重的频隙滞留问题为解决这个问题，杨义先等人提出了基于g f 函) 上m 序列构造最佳跳频序列族的非连续抽头模型【5 和通用模型吼基于g ，妇。) 上 m 序列构造最佳跳频序列族的模型【1 l 】基于m 序列还可构造出三种一次重合 亭列族吼目前基于m 序列构造的跳频序列族具有最佳的汉明相关性能 第三种方法是时候非线性方法【在单个m 序列发生器上加非线性前馈 星辑，或者用几个m 序列发生器进行非线性组合。再通过抽头选取，从而得 鲫每度非线性的跳频序列这是实际跳频电台中经常采用的方法 1 9 8 2 年，p v k u m a r ，r a s c h o l t z 和l r w e l c h 【1 目提出了广义q 元b e n t 西数，论述了其性能并提出了各种情况下的构造方法 1 9 8 4 年，p v k u m a r1 1 目提出了两种基于广义q 元b e n t 函数构造的跳频 2 序列族，达到或接近最佳的汉明相关眭能，而且具有较大的缦眭复杂度 1 9 8 4 年，r a s c h o l t z 和l rw e l c h 【1 q 利用迹函数构造出了g m w 序列 这种序列具有与m 序列一样的双值自相关函数，并且其线性复杂度比m 序列 的线性复杂度大得多，引起了人们的极大关注，研究论文大量涌现 6 - 9 1 9 9 2 年，ma n t v 础e r 和l b o m e r1 8 】提出了g f ( 矿) 上的多元g m w 序列 通过研究发现【5 】，基于g m w 序列可以构造出具有最佳汉明相关性能的跳频 序列族 文献【2 0 1 提出了一种基于长度为l = p ，一1 的具有两值自相关函数的p 元伪随机序列构造跳频序列族的方法，将构造最佳跳频序列族的问题转化为 寻找具有两值自相关函数的p 元伪随机序列的问题 m 序列和g m w 序列 ( 包括广义g m w 序列) 是闻名已久的具有两值自相关函数的伪随机序列近 年来，m l u d k o v s l d 等、t h m i e s e t h 等“、l s ，n o l l “、g g g n g l l 。l 构 造出了一些新的具有两值自相关函数的p 元伪随机序列因此，它们都可以 按照文献 5 的思想用于构造具有最佳汉明相关性能的跳频序列族 1 3 布尔函数的密码学性质 密码按加密方式分为分组密码和流密码分组密码的典型代表是d e s 体 制，d e s 体制的安全强度取决于s 盒的安全性能，而s 盒可用一组布尔函数 来实现因此d e s 体制的安全程度研究最终归于一组布尔函数的非线性度、 扩散性、雪崩效应、平衡性等性能的研究， 流密码又称序列密码，它的安全性主要依赖于密钥流序列的安全性目前 最常用的密钥流生成器是非线性组合生成器和滤波生成器。它们的安全性与 用作菲线性组合函数或滤波函数的布尔函数有着密切的关系，研究这些流密 码系统的安全性归于相应布尔函数性质的研究 不仅如此，布尔函数在认证系统中也有十分重要的应用，比如利用布尔函 数可以构造单向函数、单向陷门函数和杂凑函数等 可见，对布尔函数的研究在密码学中是至关重要的然而并非任意一个布 尔函数都可以用于密码体制中，通过长期的反复实践和研究，人们发现，为了 保证密码系统有较强的保密功能，所使用的布尔函数必须满足一定的性质，如 平衡性、相关免疫性、有高的代数次数、高的菲线性度、其有扩散性和严格雪 崩特性等等关于这些性质有一个特别值得研究的问题是各性质之间的关系 问题布尔函数的某些性质之间往往存在着一定的制约关系，那么，一种性能 3 指标的实现或提高，可能必然的要降低另外一些性钱的指标这样以来。怎样 得到具有良好密码性质的布尔函数，就成为密码学上的一个重要研究课题 1 4 布尔函数的研究现状和目前趋势 目前关于布尔函数的密码学性质的研究主要包括以下几个方面：( 1 ) 非线 性次数；( 2 ) 非线性度( 相关度) ；( 3 ) 线性结构；( 4 ) 退化性；( 5 ) 相关免疫性； ( 6 ) 严格雪崩准则和扩散准则通常也将布尔函数的这些密码学性质成为布尔 函数的非线性准则， 为了防止攻击者对密码系统进行相关攻击，s i e g e n t h a l e r 提出了相关免疫 函数的概念 2 9 】，由于其重要的密码学价值，引起了许多学者的重视。人们对 其进行了大量研究，取得了一系列重要成果m i t c h e l l 于1 9 9 0 年首次讨论了 一阶裙关免疫函数的计数，给出了一阶楣关免疫函数个数的下界为2 ”，文 献f 3 0 中通过构造相应的正交矩阵，得到了一大批高阶相关免疫函数 b e n t 函数的构造一直是研究者所关心的问题构造方法分为两种，一种是 间接构造，即用已有的函数来构造新的b e n t 函数；另一种就是直接构造至 今所知道的赢接构造主要有两类：一种是m ( m a i o r m 砌k l a n d ) 类，另一类 是p s ( p a r t i a ls p r e a d ) 类 总之，布尔函数在密码学中具有重要地位，其研究不仅具有重要的理论意 义，而且具有一定的应用价值因此，对布尔函数的研究一直很活跃，也取得 了一系列的重要成果，但仍有许多问题有待解决，尤其是对某些函数类的研究 匝处于起步阶段 1 5 本文主要研究工作思路与论文内容组织 本文按如下形式组织t 第二、三部分分别是作者在两个方面的研究工作和 茂果 一类交织序列的汉明相关特性 这一部分我们主要研究跳频通信中跳频序列设计的相关问题，结合一种新 阿交织序列的构造方法，利用已有的较好的直接扩频序列来构造跳频系统中 向跳频序列。在合适的参数选取下，跳频序列的汉明相关特性可以达到或接近 里论界限， 二次型函数的w a l s h 谱特性 本部分主要研究二次型函数的密码学特性布尔函数的非线性准则是密码 4 ， 学中的一个重要研究内容本文拟给出有限域上的一般二次型函数，并计算其 w a l s h 谱值解决问题的办法是将问题转化为一个二次型方程和一个非线性方 程联立组成的方程组解的个数情况，主要理论是基于有限域上二次型函数的 几种标准型的分类理论 5 二、一类交织序列的汉明相关特性 2 1 引言 具有良好相关性质的序列在通信系统中具有十分重要的作用就跳频序列 而言，具有较大的序列周期、最佳或者接近最佳的汉明相关特性以及大的线 性复杂度是跳频序列设计要达到的目标国内外许多学者对它们进行了深刻 的研究，设计出了许多具有良好汉明相关特性的跳频序列 a b r a h a ml e m p e l 给出了应用到跳频通信中的序列问的汉明相关值所要满足的理论界，同时由 m 一序列构造出了跳频序列1 2 】k u m a r p 利用b e n t 函数构造出具有大的线性 复杂度的跳频序列 4 1 杨义先等人通过对一些已有的达到理论界限的直接扩 频序列的改造，特别是对于所有的两值自相关序列，设计出一些达到理论界限 的跳频序列，但除g m w 序列外，其他的都不具有较大的线性复杂度李超等 人也对n o 序列和k a s a m i 序列进行了汉明相关分析，就结果表明，这两类序 列的周期相关性能达到了理论界限，可以应用到直接扩频系统中，但是它们并 不同时具备良好的汉瞻相关特性f 2 0 】本章综合改进了g o n gg u a n g 等人 1 9 】 提出的构造方法，利用已有的两值自相关序列和移位序列构造新的序列，并分 折其汉明相关特性 2 2 基本定义与结论 这一节，我们介绍本章所用到的基本定义和结论 定义2 1 对于定义在字母集a 上周期为l 的序列x = ) 和y = 协) ， 定义它们之间的汉明相关函数为t l l 鲰y ( 小= h z j ，蜥+ ，】，0 f m ( x ，y ) = m a x h ( x ) ，日( y ) ，h ( x ，y ) ) 日t 。x m r a x ， m ( x ，y ) ) 一 在定义2 2 中，h ( x ) 表示汉明自相关的旁瓣，即序列x = 巧 与其自身 平移之间重合次数的最大值，该参数影响系统的同步性能；h ( x ，y ) 表示汉 明互相关的峰值，即序列x = 与序列y = 协) 在任意时延下重合次数的 最大值，该参数影响系统的抗干扰性能和多址组网性能；m ( x ，y ) 表示两个 序列汉明相关的峰值，即汉明自相关的最大旁瓣h ( x ) 、h ( y ) 与汉明互相关 的峰值h ( x ，y ) 三者中的最大值；日表示序列族的最大汉明相关，它是跳 频序列设计中的一个重要参数 1 9 7 4 年，a l e m p l e 和h g r e e n b e r g e r 分析了在给定频隙数目m 和序列长 度l 的情况下，跳频序列的汉明互相关及异相自相关的极限，其结果已成为 评价跳频序列族的重要判据之一 定理2 3 对于定义在字母集a 上周期为工的序列x = ) ，其中字母集 台a 中元素的个数为； a l = m ，那么序列x = 巧) 的汉明自相关值满足： 雎) 坠掣 这里b 是l 模m 的最小正剩余 证明详见文献【2 】 定理2 4 对于频隙集合a 上长度为l 的任意两个序列x = ) 和 y = 锄) ，设也，e 0 = 0 ，1 ，g 一1 ) 分别表示频隙 a 在序列x 和序列y 的 一个周期中出现的次数，且设所以 如此排列使得如形成一个递减数列，即 e 0 e 1 e 。一l ，那么，序列x 和序列y 之间的最大汉明相关为 m ( x , y ) 遴q - 1 竖2 兽笋挫 7 而且当满足下述条俘时。上式右边达到最小： ( 1 ) e o e q 一1 1 ； ( 2 ) d o d 1 5d q “d l 形成一个递增序列； ( 3 ) d q _ l d 0 1 证明详见文献f 2 这两个定理的物理意义是，当所有序列中的频隙均匀出现时，也就是说， 每个频隙在一个序列周期中的出现次数相同或基本相同时，序列的重合次数 才能达到最小同时，在给定条件下，任意序列只可能达到上面给出的理论界 限，不可能超出这些理论限 特别地，当序列中的元素在有限域g f ( q ) 上取值并且长度为l q “一1 时，那么上述理论界可以转化为t h ( x ) 矿一1( 1 ) 和 m ( x ，y ) q ”1( 2 ) 如果某跳频序列族的汉明白相关性能和互相关性能值达到了上述两式，则 称该跳频序列族具有最佳的汉明相关性能 定义2 ，5 设a = ( a o ，o ，) 是一条周期n 为序列，定义序列a 的周期 自祖关函数为 魄( r ) = 啦。知， 这里下标在模n 下有意义，+ 表示复数的共轭 当序列垒的分量啦( o5 t 0 ，定义厶( n ) = l ( l “1 ( n ) ) 定义2 8 设a = a o ，a ，一，a t 一1 ) 为一含有t 个长度为的序列集合 序列! 一( e o ，e - ，e t 一1 ) 为一整数序列，定义a 上的左移算子工为 工。( a ) = l 日( a o ) ，l 眈( a 1 ) ，一，l 8 7 - 1 ( a t 一1 ) ) 这里整数序列e 称为移位序列 2 3 序列集合的一种构造方法 首先我们给出新序列的构造方法 设n = 2 m ，a = ( a o ，a l ，n 2 m 一2 ) 是一条周期为2 “一1 的二元两值自相 关序列 坐= ( e 自，e ，e 一。) 为序列a 的移位序列，也就是说，l 略( 鱼) = ( o 。 ，。 州r - 叼一1 ) ，并且特别地，工。( 旦) = 0 ，这里t = 2 m 4 - 1 ，亏玩m l 8 ，( 旦) 称为序列a 按照e 进行移位后的序列 对于j 历：m _ 定义 。 ： ” 矾( 一) 。伊 。 i o o g h ( 一) = 0 这里a 是有限域g f ( 2 “) 上的一个本原元，卢= 一且玩( z ) = 打焉( z 2 ) + 讹z 7 t r ( - ) 表示从有限域g f ( 2 “) 到有限域g f ( 2 ”) 的迹函数 设集合a “= ( 锦，埘，a 孚一，) ，这里a = l e ( 蓟按照从左到右， 从上到下的方式依次读出小中的项数，这样可以得到一条新的序列业= ( s g ，s ，s 知一2 ) ，其周期为2 “一1 如果我们把新序列中的元索写成m t 阶矩阵u ，那么此矩阵u 中的列项恰好是序列g 按照e j 进行移位后的序列 l e ? ( g ) 这种方法构造出来的新序列韭，称为由g 和e h i 决定的交织序列矩阵 u 称为序列尘的矩阵形式 下面定理用来计算交织序列的相关值设0 r 2 “一1 ，r = r a t + t 2 且 0s7 l 2 m 一1 ，0 您 t 定理2 9 ： r 一1 r s h 洲5 善监型巡( n 删力删) 如果7 2 + j t 时，| p m + j ) 等于o ；其它情况等于1 证明：设序列l 7 ( 小) 的矩阵形式为u = ( ，巩，巩一1 ) 当0 j t 时，序列工7 ( 小) 中的第j 项为a r ，r = ( 8 h + 1 ) 。d t + 7 - 1 + 妒h 十j ) ) m o d 2 ”一1 ， 9 ， 当e 忆+ j ) m 。d t 。时；其它情况为0 r o o d2 “一1 这恰好为中第一个元 素，所以， 码= l ( 7 1 + 9 ( q + ) ) 。0 6 2 m 一1 ( a n + ，一p ( 龟+ j 】t ) 因此序列的相关值就有： r 一12 m 2t 一1 剖。薹码，z=缝。一(n+妒(q+j)j=o = o j = o 。l 二l _ = 兰二= 二二 2 4 序列的汉明相关特性 对于如上给定的移位序列集，设 ( “，2 ，r ，s ) = t o j r 一1 l 毋+ 。= e ；= o o 。r 哆+ 。一e + 2 r o ( m o d ( 2 m 一1 ) ) ) i 因为a 是两值自相关序列，所以当矩阵+ 小中第j 列作为一条序列所对应 的移位序列哆和矩阵骘中第j 列作为一条序列所对应的移位序列。莹+ 。满 足上述( 1 ) 式时，序列母和序列工7 ( 剪) 的相关值为2 m 一1 ，而其它情况相关 值为一1 那么s = s ) 的相关值为 f k ，韭( r ) = n ( e ”1 ) + ( t 一) ( 一1 ) 引理2 - 1 0 ：设置( a 。j ( 0 i 2 ”一1 ) 为从g f ( 2 n ) 到g f ( 2 m ) 上的d 一型 齐次函数，11d 2 “一1 ，且g c d ( d ，2 m 一1 ) = l - 那么序列集 塑= ( 打r ( 凰( a o ) ) 打m 、_ i ( a 1 ) ) ，打。p ( 凰( n 2 4 2 ) ) ) l o 兰i 2 m 一1 ) 与序列集s 有相同的相关值，其中s 是由一条周期为2 m 一1 的两值自相关序 列和移位序列集e = 生，翌) 所决定的交织序列，其中 = c 晶，e 扛，岛一- ，弓= 二裳：；： 证明参见文献 2 4 j 定理2 1 1 ：按照2 3 节给出的构造方法，可以构造出一类新的序列坐： ( s 3 ，s ，s 知一z ) ，其周期为2 “一1 其序列周期相关值为r 2 m1 ，一1 或 者2 “1 其汉明相关值日= 2 2 m 一2 1 1 ，2 2 m 一一1 或者2 一1 + 2 m 1 _ 1 0 证明：设业( t ) = t r ? n ( h t 。( ) ) ，则相关值为 魄，韭( r ) = ( 一1 ) “p ( 肌( 。) ) + ”r 陬。”7 ) 记t = t i t + t 2 ，r = q t + , r 2 ，进一步化简 魄，挫( r ) = ( 一1 ) 2 岬( 觇( 曲”。】) + ”r ( 乩( 一1 + 1 ”“”7 2 ) ) 我们可以记 ，( 讹，t 2 ) = r 静( 。2 “) + y ho l 注意到上面等式的里面的和为 当 2 m 2 ( 一1 ) 打r 胪1 7 阽静( 。2 2 ) + 妒+ 。机7 即( “2 叶r 2 ) 慨口”屯矿h l = 0 内和等于2 m 一1 = ( 一1 ) 打r 垆1 7 l ，庇) + “打1 7 肌出+ 它) 】) f ( t h ，t 2 ) = 届2 ”，( 帆，t 2 + 亿) f ( t h ，2 ) , 0 2 r 1f ( t k ，t 2 + t 2 ) 内和等于一1 所以问题的关键为求解满足内和等于2 m 一1 时的t 2 的个数，这样进而计 算相关值 设 l = l t 2 i f ( 7 h ，t 2 ) + a 2 r l t ，m ，t 2 + 匏) = 0 ) 令x = a “，上式可以化简为 2 = l zj t r 磬( ( 1 + a 2 ( v l t + 吨) z 2 ) + ( 7 + 7 k o l 2 ( t 1 t + 吨) z t = 0 ) 譬删 ”唧 通过文献 2 3 、 2 5 】可以得到2 = 1 或者2 “一i 这样比较容易地计算 出1 = 0 ，1 ，2 ，进而得出= 0 ，i ，2 因为r = ( 2 m 一1 ) n + ( t 一) ( 一1 ) 所以冗的取值分别为扩一1 ，一i 或 者2 m 一1 由基本事实：对于周期为l 的二元周期序列，其汉明相关值满足等式h = t r + l 贝0 有日= 2 2 m 一1 2 m 一1 一i ，2 2 “一1 一i 或者2 2 , - 一1 + 2 ”一1 一1 与理论界限( i ) 1 2 ) 相比较，当m = 2 或者m 取值较大时，构造的新序列 接近理论界限，并且有较大的线性复杂度，可以应用到跳频通信系统中 2 5 结论 本章通过任意一条两值自相关序列和移位序列构造出新的跳频序列新序 列具有较大的周期、低的相关性和大的线性复杂度当参数m 取值较小时，不 具有最佳的汉明相关性能，但是当参数m 取值较大时，序列间的汉明值接近 理论下界且具有大的线性复杂度，因而可以应用到跳频通信系统中同时若改 变第二部分中的移位序列，可以应用同样的方法计算其相关值关于两值自相 关序列，文献【2 1 2 3 给出了多种构造方法，所以在本章所用到的两值自相关 序列可以从中选择，那么可以按照给出的构造方法较方便的构造跳频序列 1 2 三、二次型函数的w a l s h 谱特性 3 1 引言 布尔函数在通信和密码系统中都占有非常重要的地位而其中，布尔函数 与其变元的相关性与流密码的相关攻击有着紧密联系因此在实际中，选择具 有一定性质的布尔函数是极为重要的，而w a l s h 谱的计算是研究布尔函数的 一个强有力的工具例如，通过分析布尔函数的w a l s h 谱值，我们可以有效的 区分它们文献 3 1 】研究了非零w a l s h 谱值个数为l 到8 的布尔函数，并给出 了构造文献【3 2 1 则研究了非零w a l s h 谱值个数为9 和1 0 的布尔函数本章 选择了一般二次型函数，并计算了在各种情况下的w a l s h 谱值这样，给定一 个二次型函数就可以从本文得出其w a l s h 谱值，并且如果需要具有特定w a l s h 谱值个数的函数时，就可以很容易的从文中找出满足条件的函数 3 2 预备知识 设p 为一个素数，f p 和如是分别含有p 和q 个元素的有限域，且q = p ” 含n 个变量的函数，：霹一岛称为昂上的布尔函数任取岛在昂上的一组 基( 。1 ，。) ，这样晶中的每一个元素可以惟一的表示成a l 。1 + + o 。，这里 ，口。昂，即决定了一个对应曙，岛其中i = ( 钆，z 。) 一銎1 戡 取一，矗) 为( 口l ，- - 1 a 。) 的一组对偶基，也就是t r ( a l 风) = 1 和t r ( c r 。岛) = 0 当i j ，这里 是从b 到b 的迹映射假设a 晶，则a 可以惟一的表示成 a = ；h z l + + a 。风考虑丁r ( 地) ，这里。= x l c q + + z 。 = 1 芦l + + a n 风， z ，入f q ，很容易得出t v ( a x ) = 入l z l + + h 。 定义3 1 设u = e i 2 1 r p 是p - t h 本原单位根函数，：岛一昂在b 上的 w m s h 谱变换定义为： ( a ) = 。d f ( x ) - t r ( 捌 x e 岛 这里 日，w ，的值称为函数，的w a l s h 谱值 定义3 2f q 上具有如下形式的多项式称为二次型多项式： mm q ( x l ，z m ) = a i j x i x j + b k x k + c t j = 1 k = 1 1 3 这里a i ) ( 1s t ，j m ) ，b k ( 1 sk s m ) ，c 都是凡中的元素，其中8 口不全为零， b 。和c 可以是非零的 当q ( z 1 )，z 。) 经过任意的不可逆仿射变换后都不能变成比它变量个数 少的二次型，称此二次型为非退化的 定义3 3 设，是含有n 个变量的布尔函数，q ( z 佃。) 是咒上有 m 个变量的二次型函数9 = ，( 国( z ，z 。) ) 称为含有n m 个变量的一般二次 型函数 习惯上一般把函数的输入元素写成( z l ，z 。) ，( a 一，a 。) ，其中如b ， h 日形式，则有 w g ( a ) =u ，( 口( “一“) ) 一n m 一+ 1 m 。m ) 扛i ，。t 。m ) 即 3 3p = 2 时9 ( 。) 的w a l s h 谱值 易知p = 2 时，u = - 1 定义马上的函数”，满足u ( o ) = q 一1 ，当0 z f q 时，u = 一1 定理3 4f 口上的任一个二次型0 ( 钆，。) 在任意的不可逆仿射变换 下都可以变成q 怡l j ，z 。) + c o 形式，其中q 。，z 。) 仅为以下7 种形式 中的某一种( 在任意的不可逆仿射变换下两两不相互等价且均为非退化的1 ： i ) 茹l 茁2 + t + 。2 t l x 2 t 越) x l x 2 + + x 2 t l x 2 t + x 2 t + l ( t 1 ) i i i ) 卫1 。2 + - - + 。2 一i t 2 t + 卫；抖1 ( t 0 ) i v ) 2 ：1 2 ：2 + + x 2 t 一3 2 孔一2 + 。；t l + x 2 t ( t 1 ) u ) t l ：9 2 + - - + z 2 t l z 2 t + z l + 1 + 蕾+ 1 ( 亡0 ) 们) ( x l x 2 + - + x 2 t l z 2 ) + q z ；一1 + 口z 玉( t 1 ) v i i )( x l ：c 2 + - 十x 2 t l x 2 t ) + 卫；一1 + 口z 刍+ x 2 t + 1o 1 ) 这里a 满足t r ( a ) = 1 设p ：表示方程q 协一，z 。) = z 的解 的个数，则以上7 种形式对应的解的个数分别为：9 2 “+ q t - 1 u ( z ) ，q “，g “， q 2 ，q 2 。+ 矿( 一1 ) n ，q 2 。一q t 一1 ( z ) ，g 赴与此同时a l 。】+ + m 茹m 变为 d l x l + + 如z m + d 0 证明可详见文献 3 4 】 1 4 设毛，表示下列方程组的解的个数： jq 7 ( x l ，z 。) = 。( 1 ) 1d l x l + + d 。z 。： ( 2 ) 其中q ( z l ， ，。) 为如上所定义的二次型，这里盛( 1 i m ) 不全为零 w g ( a ) = ( 一1 ) ”南( 一1 ) 7 ”m ”+ “。m ) + 脚怡h “) + 。】 忙l 、，z m ) 即 = ( 一1 ) t r 汹) r0 ，。( 一1 ) ”( v ( 1 ) ，扛+ 为方便起见，记f ( “) = 。如( 一1 ) m ) ，t ( ) = 。f 口( 一1 ) n ( 则对于常 数c o ，d o f q ，有f ( c o ) = ( 一1 ) 7 ( c 0 ) ，t ( d o ) = ( 一1 ) 7 r ( 南) 令x l ，一，z ，为出现在二次型q 协”，g 。) 中的变量，这样对于i ) ，u ) ，v i ) 时，r 分别为2 t ，2 t + l ，2 t 分下面两种情况考虑； 如果存在一个下标t r 使得咄0 ，选择。l ， ，。，b 满足方程( 1 ) ，然 后在岛中任意选择z r + ”，。i 一1 ，。州，。的值，则对于每一个y 晶可 以惟一的决定一个而日满足方程( 2 ) ，这样就有屯。= p z q r 当口为第i ) 种形式时，毛，；= 扩。+ 扩一”u ( = ) ， w g ( a ) = ( 窖m 一2 一q m - t - 2 ) f m ) r ( u ) + q m - t - 1 f ( c o ) t ( u ) 当q 为第t i ) 种形式时，5 v ：= q ”， w g ( a ) = q m - 2 f ( u ) t ( u ) 当q 为第俐) 种形式时，如，= q 2 ， w g ( a ) = q m - 2 p ( ) t ( u ) 当q 为第i v ) 种形式时，：= g ”， w g ( a ) = q m - 2 f ( u ) t ( u ) 当q 为第 ) 种形式时，屯# = g 一2 + q m - t - 2 ( 一1 ) n ( “， w g ( a ) = q m - 2 f ( 乜) t ( u ) + g m 一。一2 ( 一1 ) 丁7 ( 。( 一1 ) ，( 。+ c o ) z e f q 当q 为第v i ) 种形式时，目，：= q ”一q m - * - 2 v ( z ) ， w _ ( a ) = ( 口m 一2 + 旷”一。一2 ) f ( u ) t ( u ) 一q m 一一1 p ( c 0 ) t ( u ) 1 5 当q7 为第。i i ) 种形式时，屯：= q “， w g ( a ) = q m - 2 f ( u ) t ( ) 下面考虑西+ - = d r + 2 一一d m = 0 时用西，。来表示下列方程组的解的 个数： jo 协1 ，z ，) = 。 ld l x l + + d r 。，= y 则有6 ”= q 屹 当0 + 为第t ) 种形式时，考虑下面这个方程，设r = 2 t jx l x 2 + x 3 x 4 + 十口2 t l x 2 t = = ( 1 ) id l z l + d 2 x 2 + - + d 2 t i x 2 t = y ( 2 ) 由对称性，不妨设d r 0 ，则可以从( 2 ) 式中解出现得， 锄= - - - i z i + 寒射+ 警z 2 t - 1q - 詈 这样将的表达式代入蓟( 】) 式中，刚方程( 1 ) 变为： 叫。+ x 3 2 4 卜咖一乏巧+ 石y 蚴一z 以d ，。2 c - 1 代替。2 h ，尉上述方程可以化为t 2 t - l x l x 2 + x 3 x 4 + - + z 2 一1 办+ d 2 一l d 越。；一l + y x 2 t l = z ， j = l 再以。蕊l + d 2 i x 2 t 一1 代替z “以9 2 + d 2 t 。2 代替。2 “( 1 曼t t 一1 ) ，则 继续可以化简为： 令口= 名1 d 2 t l d 2 i 若卢= 0 且y = 0 时，结果见定理3 4 若口= 0 且口0 时，方程解的个数容易得到 若胆0 且= 0 时，刚可以归结为上述情况 若卢0 且y 0 时，对于任意的元索c 日，因为方程卢z 2 + y x ；c 的解 的个数为： 1 + ( 一1 ) 7 而( 笋) 这样我们就有： 1 r = | | 一 2 妒 +_ 如一如 埘 + 砚一勉 h 所以有 毛，：( t - 1 蚴邓。：。，) 1 + ( 一1 ) 7 7 _ ( 争 0 1 + c 2 = ；i = 1 ： q 2 t - a + ”( c 1 ) q “ 【l + ( 一1 ) 7 如争1 c 1 4 - c 2 = 2 ：q 2 t - 2 + 尹1 ( 一1 ) 7 _ ( 学) = 口= 0 且y = 0 卢= 0 且y 0 口0 且y = 0 p 0 且y 0 进而 w g ( a ) jq m - 2 f ( u ) t ( u ) 一q m - t f ( c o ) 一q m - t - 1 t ( u ) 口= 0 一lq m 一2 f ( u ) t ( u ) + q m t 一1 口。# ( 一1 ) 2 誊( 一1 ) 7