（应用数学专业论文）钟控生成器输出序列的特性分析及其在扩频通信中的应用.pdf

信息工程大学硕士学位论文 摘要 本文在已有同以m ，生成器、加法型组合生成器模型的基础上，综合运用代数学、测 度论、逻辑函数和随机过程等学科的理论研究了咒m m ：生成器、加法型组合生成器输出 序列的周期、线性复杂度、自相关特性、互相关特性、相关免疫性等密码学性质。研究发 现，面毛肘：生成器、加法型组合生成器输出序列均具有较长的周期，较高的线性复杂度， 且具有相关免疫性。通过计算机仿真还发现它们均具有尖锐的自相关特性和弱的互相关特 性，从而在码长固定的前提下，它们可提供较多的码字。鉴于这些良好的密码学特性，且 硬件易于实现，本文考查了它们在扩频通信系统中的应用。主要研究了由黝正肘，生成器 输出序列、加法型组合生成器输出序列生成的扩频波形的自相关函数和功率谱密度，并考 查了在单频正弦干扰条件下，黝以m ：生成器输出序列用作扩频码时直接序列扩频系统产 生的误码率；研究了加法型组合生成器输出序列作为扩频码时系统的抗广义平稳干扰性 能，讨论发现同厶膨，生成器输出序列、加法型组合生成器输出序列用在扩频通信系统中 是切实可行的。本文还利用概率论的知识建立了在线性反馈移位寄存器输出序列并不一定 服从均匀分布的条件下妇f 肘，生成器的概率模型，考查了其输出序列的一维分布，j 步 转移概率，有限维联合分布和数字特征等概率性质；并建立了非均匀输入条件下加、乘法 型组合生成器的概率模型，考查了它们输出序列的一维分布，七步转移概率及数字特征等 概率性质。研究结果表明它们分别是对输入序列服从均匀分布时的删，鸩生成器以及加、 乘法型组合生成器输出序列概率性质的有意义的推广。 关键词：向毛肘：生成器，加、乘法型组合生成器，周期，线性复杂度，相关免疫性， 扩频码 第1 页 信息工程大学 璇士学位论文 a b s 毯e b 黼c do nf h em o d e lo fm e 捌l 村2 群船艟o 矬d d 孤v ec o m b i l l g 髓e r a 峨b yl l 寡 i n g 埔噼 a i g 曲l 瓠m 蝴鞠l i a b l et | i c o r y ，l o 舀c a lf 妇c 6 a n dr 黼d o mp l 硼；e 鼹伽唧l p h 锄i v e l 弘也i sp a p e r s t i 坩ym ea i 黪c b r a i cp r o p c 币嚣o f t 1 1 eo u q u ts c q u 嘲。鼯o f 姒鸩g e 腿r a 白o r a d d i 矗v ec o m b i n e d g 啪鼎a t o r ，i l l d u d i n gp e r i o d ，l i l l e 郜c 0 忸p l e x i 怯麟，c c 舭诅a t i o n ，c 0 嘴l a t i o n - i 1 1 】1 玎_ i m i 哆r 鹉黼r c h s h o w st 1 1 a tt l l eo u t p 呲s e q u c 铭o f 黝村2 9 棚吣a d d i t i v cc o m b m c dg e 眦m l d fh a v el 蝴g p 酣o d ，l a r 蓦婶l i n 船rc 0 啪p l e x 谢e s ，o o n - e l a t i o 球枷蝴u 嫩够t h eo u 肇ms e q u e n c 鹤o ft h 黜a 重8 0 h a w 蜘g 辙l 协c c 旺镀a l i o n 强d w 懿l ( a 螂c ( 孵议矗蜒o n b y 瞰翠l l 溉s o w h 船恤c o d e l 黝鼬妇 蠡x e d ，穗e yc 8 l la 韵砖童o m o f c d e w 蕊h 燃联氆e 静o d 嘞刚c a 重西嚣簖丽s t i 锱 o f 氆e 掰，糊d 量l 矧蛔辩i s 髓黟量oo o 氆e 搬端如绷魄潍s 谯撼i 嚣l k 拓辨珏c 蕊。黯遮s p 瓣糕 蹲e 滋啪s y 艇镄瓠s o 氆霉彰l p 既托辩越l 培s 越l 辆烈瓣骥艇i 傩铀c 蛀傩赫dp o w 嚣峙c 扫r 8 | d e 毂s i 咎 o | | 邓嚷糯d 邓瞄内1 娃nw 8 v em a d eb y t h e 翻l l p u t 鞭碍瓣n c 髂o f 埘尬g e 豫t 嵋a d 碰t i v ec c 嘲_ b 主l 矧 g t 激掰a 击。乓a n ds t i i d i 酷t h e 删r a t e 窘c 1 1 慑叭e db ym ed i r e c ts o q u c cs p a ds p _ 。曲m m c o l m n 州c a n d ng y s t 锄w h e nt l l eo u t p u ts o q u 踟c e 8o f 窘a 咖fa c t s 船s p 蝴ds p a ：n l l mo o d ei l l _ l h ec o n d i d 0 i lo fs i n 羽争董 e q u e n c ys i m l s o i d a l 如t e f f 抵c e 唧1 0 t l l 瞎s ) 吲锄翎nr c 媾i 啦 s t a i o n a r yd i 姗b m i w h t h e 叫t i m ts e q u 蝴c 鹪o fa d d i 讯r cc o m b m c dg c n e 删o ra r et l s e d 鹪 印r e a ds 牌鼬n l mc o d 岛r 鼯e 种c hs h o w s1 1 l a ti ti sf e 勰i b l et o 印p l yl h 锄j ns p 哟ds p _ e c 蜘料n m 眦1 馐嫩c a t i o ns y s t 黜t h e p f o b 西i m y m o d d o f t 重l e 置峨鸩g 明珂a t o f i sa l s o c 0 m l c t e d w h 嫩 氆eo 甜枷ls o q u 戚l c e so 1 l 妇龆f 蠡鳓a c ks 啦磊f c 萄鼬群n o 鑫1 w a y s 翱h 癌tt m i o m l 击s t r 主i 心饿l 姆 璐纽g 镪# 捌皤b 矗醚l i 垮氆f y ，氆e 锄e 盛掇豫s i o 藏镬髓啜搦霸瓣，寿一s e p 妇商壕撒翔0 1 b 磊联l i 姨 蠡螨l e 藤黼稳晌j o h 蠡蹦跳疰。玛蠡g 珏撵穗越8 c 耋群o f 融掰l 糍掰ts a 孵e 珏o e t e 越i s 蕊辅鞋睦文 w ea l n 鼬m c tt h e 弘曲曲语l ym o d d 硝稿d i 蛀、啭搬醢l 铆i c 撕v eo o 瞄b i n e dg 嘲烈拍o fw 垂l e 娃 铂尊o u 够哦8 0 q u 鼯。髂o fl i n e 村诧e d b a d ks h i f t 蚓s t 鼎l l o ta l w a y s 酬临l l i tl h i i f o 强d i 蛐蜥。辑 撇dt l 摊。鹏d 渤黜i 曲d i s 舡i b u t i ，七一对e pt r a 煅i t i o np f o b a b i l i 咄f i g u c h 嬲l c i 群o f t h co 峨 i i t q 1 坤l l o oo ft l l 锄i sd i s c 啵s e d t h er e s u i t ss h o wm a tt h e ya r cs i g n i f i c a n tp l m n 嘶o nt ot h e 0 1 m u t8 。q u 啪c 鹤o f 黝f l 射2 9 锄e r 龇o r ，a d d i t i v c ，黼m t i p l i 训、，eo 响b i n 。dg 哪e r a t o rw h 蹦t h e o u t p l l ts 代w e n o 鹪o f l i i l e a r 诧文i b a c k 幽f tr e 舀s t e r 黜m m i tl l n i 触nd i s 灯i b u t i o n 1 ( 皑w o r d s ：必毛鸩g c 乱嗽t o f ，a d d i 石v e ，嘏u i 喇i 黼蝣v ec 0 i l l b i l l e d 学鼬贸a l o lp 喇o d l i j 擗黼 c c 旺叫e x i 颤o c 髓d a 垃i 翔m 嘶壤印重e a d 蹿l e i 确r l m d e t 第1 l 硪 原创性声明 本人声明所提交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表和撰写 过的研究成果，也不包含为获得信息工程大学或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文题目： 学位论文作者签 作者指导教师签 学位论文版权使用授权书 本人完全了解信息工程大学有关保留、使用学位论文的规定。本人授权信息工程大学 可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允许论文被查阅和借 阅；可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 盟揎垒盛墨捡出座到盟挂：睦金盘盈甚盔芷筮亟焦主盟廛旦 信息工程大学硕士学位论文 第一章引言 扩频通信技术最早在2 0 世纪5 0 年代中期被美国军方开始研究。简单地说，扩频通信 技术是一种信息传输方式，它把发送的信息转换为数字信号，然后用扩频码序列去调制数 字信号，以展宽信号的频谱；接收端通过相关接收，并用与发射端相同的扩频码序列去解 扩，最后经信息解调，恢复出原始所传输的信息。这里用来传输信息的信号带宽往往远大 于信息本身的带宽；频宽的扩展由独立于信息的扩频码来实现，与所传输的信息数据无关i 传输扩频信号的系统称为扩频系统。由于扩频通信技术采用了伪随机序列作为扩频调制的 基本信号，使它具有很多独特的优点：抗干扰能力强，发射功率谱密度低，隐蔽性好，抗 衰落能力强，对其它通信影响小，能实现码分多址和任意选址的功能。鉴于这些优点，扩 频通信技术得到迅速发展，已被应用于雷达、遥控、跟踪、导航、测距及信息保密等方面， 显示了它广泛的应用价值! 在扩频通信系统中，用作扩频码的伪随机序列应具备如下条件：( 1 ) 在各种移位不是 周期整数倍的条件下，序列都有低的自相关值；( 2 ) 在各种移位条件下，序列都有低的互 相关值；( 3 ) 周期长，码量大，线性复杂度高；( 4 ) 易于软件和硬件实现。所以寻找满足 这些条件的伪随机序列一直是学者们致力于研究的课题。自扩频技术出现以来，人们将研 究得到的坍序列，m 序列，g d 瞄序列“】，曰砌竹序列伫1 等用作扩频码。但是这些常用的 扩频码仍存在着这样那样的缺陷。肌序列由线性移位寄存器产生，具有良好的伪随机性， 但其中具有线性平移相异的序列数量很少，若要考虑其互相关特性进行筛选，则数量更少； 膨序列由非线性移位寄存器产生，硬件实现极为困难；选择平衡的g o 掰序列工作量又太 大【3 l ，8 删序列还不能实时产生【“。因此寻找伪随机性好、码量大、易于产生的伪随机 序列是许多学者长期不断的研究目标。 钟控生成器输出序列( 下简称为钟控序列) 是一类较新的伪随机序列。1 9 8 4 年在欧 洲密码学会议上b e m t 和p i p 盯f c 提出咖p 柚d g og e n 盯：l t o r l 5 1 ( “停走”生成器) ，后续 研究表明，“停走”生成器输出序列具有周期长、线性复杂度高、伪随机性好等特点，且 硬件容易实现。因此一经提出便受到学者们的高度关注。接下来许多学者又以“停走”生 成器为基础构造了多种钟控生成器。1 9 8 7 年在欧洲密码学会议上，瑞士的g 啪t l l 盯cg 提 出删m 型钟控生成器嘲( 下简称为删m 生成器) ，也称为“衮特”生成器；1 9 9 4 年丁 存生教授、肖国镇教授在专著【7 】中提出剐峨肘：型钟控生成器( 下简称为胁m ，生成器) ； 【7 】中还提出将钟控方法与非线性组合方法相结合而得到的钟控非线性组合生成器( 如加、 乘法型组合生成器) 。 由于钟控序列的良好性质，吸引了大批学者，因此对它们的研究也取得了一定的成果， 主要包括三个方面。首先是对钟控序列代数性质的研究：专著【7 】，文献 8 】对“停走”生 成器输出序列的线性复杂度及稳定性进行了分析，指出所得到的这类钟控序列的线性复杂 第l 页 信息工程大学硕士学位论文 度指数级地依赖于生成它的线性移位寄存器的级数，且其线性复杂度的稳定性在流密码意 义下是较为理想的，从而可以抵抗b a a 攻击佴1 ；专著 7 】，文献【6 】，【1 0 】，【1 1 】，【1 2 】用类 似的方法讨论了k m m 生成器输出序列的周期、线性复杂度及线性复杂度稳定性，得到 了与“停走”生成器类似的结论；文献【1 3 】还考察了删m 生成器输出序列的相关免疫性。 其次是对钟控序列概率性质的研究：黄晓英教授通过建立“停走”生成器、咒 ，肘生成 器、置m m ，生成器及加、乘法型组合生成器的概率模型，对它们的输出序列的概率性质 进行了系统的研究( 见文献【1 4 】、【1 5 】、【1 6 】、【1 7 】、【1 8 】) 。第三是对钟控序列信息论性质 的研究：文献【1 9 】、【2 0 】通过分析钟控序列与“原序列”间的平均互信息来分析钟控生成 器性能；文献 2 l 】全面研究了删m 生成器、胁毛肘，生成器、加法型组合生成器的输出 序列与原序列间的平均互信息。 文献【2 2 】【2 3 】曾分析将删膨生成器输出序列用作扩频通信系统的扩频码，并得到 黝，m 生成器输出序列用作扩频码时的平均误码率较小，将其用作扩频系统的扩频码是 可行的。因此将其它钟控序列用作扩频系统的扩频码是一个值得深入探讨的问题。 本文在已有黝以m ，生成器以及加、乘法型组合生成器概率模型的基础上，讨论了 五m 。m ，生成器输出序列、加法型组合生成器输出序列的周期，线性复杂度，相关免疫性， 相关特性等密码学性质；通过理论证明和计算机仿真说明将钟控序列用作扩频码是切实可 行的；并讨论了在输入序列不一定服从均匀分布的情况下，胁厶m ，生成器输出序列以及 加、乘法型组合生成器输出序列的某些概率性质；。 本课题的研究得到中国科学院信息安全国家重点实验室的开放课题基金项目和计算 机网络与信息安全教育部重点实验室开放课题基金项目资助。主要研究内容安排如下： 第一章引言部分介绍了扩频通信技术的概念及特点，对钟控序列的代数性质、概率性 质、信息论性质研究的一些成果和钟控序列在扩频通信中的应用等内容，最后概述本论文 的主要研究结果及研究方法。 第二章主要研究了脚。m ：生成器输出序列、加法型组合生成器输出序列的周期，线 性复杂度，相关免疫性，相关特性等密码学性质。 2 1 讨论了黝正m ，生成器输出序列的密码学特性。在胁m ，生成器模型中，设k 的 输出序列反馈函数的级数为七， 以、肘，的输出序列反馈函数的级数为掰，讨论得到了其 输出序列的周期为( 一1 ) ( 2 4 1 ) ，线性复杂度为2 m ( 2 一1 ) ，可见其周期和线性复杂度都 随着线性移位寄存器的级数呈指数级增长；其输出序列还具有良好的伪随机特性，包括在 例肘，生成器输出序列的一个周期内，o 总是比1 多一个；游程个数随着长度的增加而 逐渐减少等。证明了脚。 厶生成器输出序列具有相关免疫性，具有良好的相关特性，并 利用计算机仿真得到它的自相关性、互相关性等结果。 2 2 讨论了加法型组合生成器输出序列的密码学特性。在加法型组合生成器模型中， 设k ，蜀的输出序列反馈函数的级数为七， 、鸩的输出序列反馈函数的级数为研， 证明了其输出序列的周期为( 2 一l x 2 ”一1 ) ，线性复杂度为2 m ( 2 一1 ) ，可见加法型组合生 第2 页 信息工程大学硕士学位论文 成器输出序列同样具有较长的周期、较高的线性复杂度。加法型组合生成器输出序列还具 有良好的伪随机特性，其o 、1 个数分布虽然不具规律性，但从统计的结果发现0 、1 个数 差别不大，其游程个数随着长度的增加而逐渐减少。同时研究发现加法型组合生成器输出 序列具有良好的相关特性，并具有相关免疫性等结果。 2 3 总结本章，概括出厨毛m ：生成器输出序列、加法型组合生成器输出序列的密码 学性质。 鉴于恩以m ：生成器输出序列、加法型组合生成器输出序列具有尖锐的自相关特性和 弱的互相关特性，从而在码长固定的情况下，它们可提供较多的码字。又考虑到它们均是 由线性反馈移位寄存器输出序列进行钟控后产生的，故易于硬件实现。这些性质符合扩频 系统中伪随机序列作为扩频码序列的条件，因此第三章主要讨论了置m 。肘：生成器输出序 列、加法型组合生成器输出序列用作扩频通信系统中扩频码序列的可行性。 3 1 是背景知识，主要介绍了扩频通信的原理及特点，扩频通信的种类，扩频通信系 统中关于扩频码的研究现状等内容。 3 2 主要讨论了面f 。坎生成器输出序列在扩频通信中的应用。首先给出了由励正肘， 生成器输出序列臼，f o ) 生成的扩频波形c ( f ) 的数学表达式，然后讨论了c ( f ) 的自相关函 数和功率谱函数，并利用计算机仿真得到c ( f ) 的自相关函数图和功率谱图像。在直接序列 扩频系统模型中，以删m ，生成器输出序列为扩频码序列，在单频正弦干扰条件下，我 们得到了系统的处理增益和误码率图像。 3 3 讨论了加法型组合生成器输出序列在扩频通信中的应用。首先研究了加法型组合 生成器输出序列 置，开o 生成的扩频波形6 ( f ) 的自相关函数图和功率谱图像。在直接序 列扩频系统模型中，以加法型组合生成器输出序列为扩频码序列，研究了系统抗广义平稳 干扰的能力。 3 4 总结本章，研究结果表明将五m ，m ：生成器输出序列、加法型组合生成器输出序 列用作扩频通信系统中扩频码序列是切实可行的。 在输入序列服从均匀分布条件下，文献【1 8 】建立了“停走”生成器、删m 生成器、 同以m ，生成器以及加、乘法型组合生成器的概率模型，并讨论了它们输出序列的概率性 质，得到一系列有意义的结果。但考虑到输入序列并不一定服从均匀分布，故第四章讨论 了在输入序列未必服从均匀分布的情况下，胁毛m ：生成器及加、乘法型组合生成器输出 序列的某些概率性质。 4 1 讨论了在输入序列 q ，f o 、 4 ，f o 、 q ，l o 是定义在同一概率空间 上的三条独立o 、l 随机变量序列且满足p q = o ) = p 岛= o = p q = o = p ，f o 时 的假设条件下，咒m 耐：生成器输出序列的一维分布，| | 步转移概率，有限维联合分布及 数字特征。 4 2 讨论了在输入序列 巧”，疗o ， 露，露o ，_ | = l 、2 是定义在同一概率空间上 的四条独立o 、l 随机变量序列且满足p f ”= o = p 墨”= o = p ，i o 时的假设条件下， 第3 页 信息工程大攀颈士攀位论文 热、乘法溅维会生成器输出痔捌豹一维分蠢，露疹转移撅搴及数字特征。 碡，3 慧绥本章，概括窭在辕入痔歹l 不一是黻麸均匀分毒条黉下，秘f ；譬：生成器叛及 蕊、乘法激缀含生成器输出序弼煞概率经藏，弗攒嫩当p = 三霹，所得结采与文献【1 8 】鲶 结果一致，从而本章结论是对在输入序列服从均匀分布时的有意义的推广。 第赢章简要总结全文，并提出有待进一步解决的问题。 第4 蕊 信息工程犬学硕士学位论文 第二章两类钟控生成器输出序列豹特性分析 第一牵我们简单会绍了钟控序列的一些知识，这一章我们来具体分析两类锋控序列鄄 磊= j i 肘：嫩成器和加法型组合生成器输出序列的密码学性质。 2 1 埘，m ：生成器输出序列的特性分析 1 9 9 4 年，丁存生教授和肖国镇教授在专罄【7 】中提到的一种变形的“衮特”生成器， 即髭m 。嫩成器，并对其输出序列作了筒襄分析。文献【1 8 】用概率论的方法分析了剧帆j l 如 生成器输溅序列豹一些性质，证明了此序列其猎嶷好静伪随机性窝其它良好的密码学特 经。为了涤入蟪考察兹痔裂豹其它密码学性震激攒凝箕是否虿蘼终扩频逶绩静扩频弼，零 节将戳炎数方法瓣踅磁敞生成器翰塞穿襄遴器努耪。 2 1 1 戴 如钟控生成器模型 黝，尉2 生成器是由三个线性反馈移位寄存器( 脚蕊r ) 所组成。其构造如图2 ：1 所 示。 恒q 嚣2 1 弱f l 掰2 生成嚣糗蘩 这辍五f 凇l 、上f s r 2 、勰3 分别记为蔗、m 、j i 幺，其输出序列的反馈函数的缀 数分别记为厝、m 、鸩的级数；“o ”为模2 加。揪1 和勰2 组合而成的生成器简 称为鬣嵋嫩成器，髓t 钢l 和邢r 3 组合而成的嫩成器简称为圈生成器。翮峨l 如皱成器 可看份怒蒯峨和磊凇：两个“停走生成器”的棚加缀合。在鼢鸩生成器中，假定蔗的 输出黟列为黩，f q ，掰l 豹输出穿列为如，i 醇，搋的输出痔列为穗，i 芝啦，曼| j 两个“修 罗擞黝耥翩秘 o 戳强垃归翻。卜留酣裙卜留孙瓣 | 豫= | 毪= 信息工程大学硕士学位论文 魏捌鸬生成器豹赣窭捌够姆箍芸未 2 1 2 蒯鹄生成器输出序列的性质 序列的代数性质主要包括周期、线性复杂艘、相关性、相关免疫性等，下面就这魑性 质对戴w m ，生成器输出序列做一下讨论。 1 慰刺，生成器输出序列的周期 对于：元序列 q ，f o ) ，若存在藏熬数，使q = ，i = o ，l ，2 ，则称，为序剜 弦，f o 的个周期，此时序列 氆，f o 成为周期序捌，满足q = ，f = o ，l ，2 ，靛袋 夺歪熬数# 为净疑豹最小蠲翅，我 f 】逶常掰说豹瘸麓均指最小周魏渊。易知对予级数必妻 煞搬黟列 啦，i 哄，箕矮麓灸2 | 一l 朗。 是壤2 1 1 若在磁，鸩生成器串，足戆级数为露，j l 、l 磊豹级数为辨，那么赣爨缪 弼 焉，l o 躬餍期为( 岔一1 ) ( 2 “一1 ) 。 诞明在肼。肘：生成器中，对于肼i 生成器，宥( 2 ，2 “一1 ) = l ( 。为序列k ，f o 一 个周期内l 的个数) ，从而 吩；f o 的周期为( 2 一1 ) ( 2 肿一1 ) 【”。同理， 峙，f o 周期也为 ( 2 一1 ) ( 2 “一1 ) ，且 坼，j o ) ， u ，f o 平移棚舜，故胁m 2 生成器输出序列的尉期为 ( 2 一1 ) ( 2 ”一1 ) 。 w 以肴出，踅峨m ：生成器输出序列的周期随着置和 五、投的级数指数级增长， 删j 尉：嫩成器输出序列较掰序列具有更长的周期。 2 。鬣惦黛啦生成嚣输出序列的线性复杂度 定义2 1 。l 设事到，q ，岛， 满足齐次线瞧遂；毯关篆式 上 嚷= q 啄l = 岛唯一，+ 年l 舔m l + 椎2 嚷啪：扣一+ q 嚷_ | i f 称序刿 d 0 ，q ，啦， 为一个，阶齐次线住滋姻序列，其线性复杂度为满足阶数最小的 齐次线性递归关系式的阶数。规定常值序列 o ，o ，o ， 的线性复杂度为o ， l ，l ，l ，l 的线 性簸杂廉为l 。序列的线性复杂度是其不可预测性的一个重要度量指标，如果一条序别的 线性笈杂度是厶那么要知道像的任意2 个连续元素即可j 骥过 嚣一肘( 执成妇挣妒一 缸s 叼，) 算法来线性地预测熬个序列m ，在此意义下，序列的线性复 杂魔越巅越好。 周期垮裁趣，i 谚静生成函数烈力弼键为：吠毒) = ，且可表零舞 贰砖；多黯苁毋为序秀酶，f 母静反馈蘧数剃镌，f o 的线性复杂度为蛔，国 煞6 贸 信息工程大学硕士学位论文 下面我们来讨论咒m ：生成器输出序列的线性复杂度。 引理2 1 2 【2 5 1 若，o ) 为m 次本原多项式，则八一一1 ) 为不可约多项式，且其次数为 埘( 2 一1 ) 。 引理2 1 3 设坍序列“，f o ) 的周期为p ，若正整数屯、乇满足( 焉，力= l ， 幢，p ) = l ，则研序列如，f o 的岛、屯采样序列 ，f o ) ， ，f o ) 平移等价的充要条 件是：存在正整数，o r 州一l ，使是；2 7 丑( m o d p ) 成立。 引理2 1 4 川设伪随机序列二= k ，f o ) ，五= 馋，f o ) 的反馈函数分别是z ( 力， 五( 曲，那么工( - o - ) 茎三( - ) + 上巧) ( 这里五。占表示 口l o 岛，f o ) ，当且仅当( 正似五( 功) = 1 时等号成立。 定理2 1 5 若在删。m ：生成器中，k 的级数为七，m 、鸩的级数为埘，那么输出 序列j = 焉，f o 的线性复杂度为2 m ( 2 一1 ) 。 一 p lp l 证明记，= 2 一l 。令m ( o ) = o ，国( f ) = q ，国x f ) = f 一q ，f = l ，2 ， 则有 “ “。 m ( ，妒+ d = 肋( p ) + d ， 国x ，矽+ f ) = ，妒+ f 一( ，j p + f ) = ，妒一，l 缈( p ) + f m ( f ) = 开国i p ) + 国v ) ，栉o 。 珊( 力= 2 “、( p ) = 矿一一1 分别为埘序列 c f ，f o 中l ，o 的个数。 又记 ) = f o ) ，4 州) ，( 2 ) ，一 h = 屯( 。，丸1 1 ) ，k ( ：) 则序列“，f o ) 的母函数为： 纯( 时= ( o ) + 1 ) 工+ t 2 ) ，+ + ( p - i ) 石p 1 + ( 力，+ = ( o ，+ ( ，) 矿+ 2 ，) 矿+ + 研1 1 ) + t ，( 1 ) r + 2 咖口( 1 ) p + 】 + + 】，1 【4 ，- 1 ) + 口州，卜州，一1 ) x + 4 m 2 ，) + t ，- 1 ) 矿+ 1 = 0 o ) + ( ，) x + f k ( 2 ，) ，9 + + 可k j ) + 口2 h + 州i ，+ 巴2 h + 。i ，+ 】 + + ，1 【，- 1 ) + 4 一”p 1 ) x + 口2 4 埘产1 ) 工2 p + 一 不妨设序列 口，i 2o ) 的反馈函数为，( 的，序列 岛，f o 的反馈函数为g ( d ，序列 巳( ，h ，f o ，o f s p l 为m 序列h ，f o 的平移后的少1 采样序列，所以由引理 2 1 3 知，它们均和 q ，f o ) 平移等价，故它们的反馈函数均为序列 q ，f o 的反馈函数 第7 页 信息工程大学硕士学位论文 厂( 力，设它们的母函数为：等，f = o 1 ，p - l 。代入纯得： 器+ 工筹+ ，器+ 一1 镨 皑 r 鸟( 工9 ) ；立旦一。 ，( 工9 ) 由引理2 1 2 ，厂( 矿) = 八，一1 ) 为不可约多项式，所以八一1 ) 为序列二= 蚱，f o 的 反馈函数，且= 坼，f o 的线性复杂度为肼( 2 一1 ) 。 同理：g ( 一) 为序列；= m ，f o 的反馈函数，；= m ，f o ) 的线性复杂度为扰( 2 一1 ) 。 又因为，( 力，g ( 砷均为埘次本原多项式，所以，u ( 一。) ，g ( 。1 ) ) = 1 ， 由引理2 1 4 ，l 0 ) = 三 ) + 三( = 2 m ( 2 一1 ) 。 咒峨m ：生成器输出序列的线性复杂度随着置级数的增加呈指数级增长，具有较高的 线性复杂度，从而抗b 从攻击能力强。 3 删鸠生成器输出序列的伪随机性 3 1o 1 分布特性 o _ 1 分布特性是衡量序列伪随机性的一个重要指标。序列一个周期内0 、1 个数越接 近，说明其伪随机性越好。m 序列一个周期内l 总是比o 多一个例，胁f m 生成器输出 序列一个周期内o 比l 多一个呷】，它们均具有良好的o _ 1 分布特性。下面我们来考查 胁毛鸩生成器输出序列的o 1 分布特性。 设在肼。鸠生成器中，足的级数为i ，m 、鸠的级数为聊，m 的输出序列为 如，f o ，鸩的输出序列为编，f o ，令只= 2 一1 ，昱= 2 ”一l ，且 彳= s = l l 异+ l ： 屹 ” + 2 ： ( b - 1 ) + l( 悬i ) + 2 弓 s 2 s r s 日+ 2 屯日 ( 巧一i ，+ 2 是 ，曰= v 2 + 2 v 2 日 飞尼- l 卜2 h 思 ，则s = 彳。口。由咒鸩钟控生成器模型知， 序列“，f o 是硼“停走”生成器的输出序列，“，f o 是胁f ：“停走”生成器的输 第8 页 m _ 坼 毛，：忏 s 信息工程大学硕士学位论文 出序列，则中各列均为序列 q ，f o 的2 ”1 采样，矗中各列均为序列 岛，f o 的2 厮。采 样，故一、口中各列均为m 序列。但由于目前对于两条反馈不同的m 序列模2 加后产 生的序列的0 、1 个数研究还没有十分精确的结果，故通过数学方法证明脚鸩生成器输 出序列的o - 1 分布特性比较困难。但通过计算机对大量删肘：生成器输出序列进行统计 后发现，当k 、 、 如级数相同时，在黝鸩生成器输出序列的一个周期内，0 比l 的个数多一个。而当足与肘、 如级数不同时，o 、1 分布没有较强的规律性，但个数相 差也不太多。 3 2 游程特性 任意一个( o ，1 ) 序列总可以看成是由一段o 和一段1 相间的排列而成的。例如，序 列( o ，l ，1 ，1 ，o ，o ，l ，l ，l ，l ，o ) 就是由( o ) ，( 1 ，1 ，1 ) ，( o ，o ) ，( 1 ，l ，l ， 1 ) ，( 0 ) 这样5 段组成的。这样的段称为游程。游程所包含的元素个数称为它的长度吲。 游程特性也是反映一条序列伪随机性好坏的重要指标。若序列的长游程数目越少，说明它 的伪随机性越好。在栉级m 序列一个周期内，对于o ( 湃”( 2 ) ， v = ( ，q ，) e g f “1 ( 2 ) ，因为： p ，( 并，y ，z ) = w r + y + ，z ；揣， ( r + p + 1 ) ( 玢t ，) + z 0 ) = w 并+ “。】，+ 1 ，z ) * 2 ) 燃 p x = 岛】0 ( 。+ “y 十z ( 。) + ，z 糌w 掣) ， 摧0 矿 l 瓣扩 ) l 或矽( d l ，则对任意的露6 渺“( 2 ) ，珞树+ 甜y + z 秘+ y z 服从均匀 努毒，蠡骞容蘧瓿交量豹鞠互独立毪帮分雍懿麓匀羧蜀褥 琰厂( 茗，戤z ) = w t 盖+ 鼙y + r z 徽p x = 砖p 写f 。+ 拦。y + z 矿。，+ v 。z 茹1 ，。砖 聃翻r 。2 ) 一去p 饵= e l 2 从黼蕞，) w “，d = 2 p ，( x ，y z ) = w 并十y + j l ，z 卜1 2 的； h 澎形q ) = 矿= l ，记帮= 群卿，v 。力，o 歹茎菲，刘 p ( x ，z ) 。w - 苫+ ”】，+ v + z ， m p u 醛，y ，棼= 铲x + 3 ￥+ 1 玲 一p x = 砖，p 易+ 群街y + z 甜+ 力z = w 。磅， 溻i 礴j 时，仍有p ，( 置y z ) = w x + 】，十1 ，z ) 。寺，从而( 嵋，v ) ；o ； 巍f j 时，p 矿( x ，l z ) = w x + h y + ，z ) = p r = p 以】备( 砷十】；+ z 0 一+ 互2 w 田 + p x = 岛w # = o = 三一；+ 鲢登雩捌， ，“2 ” 所孩露：( w ，妒) ：照墅里望 警刨一等。 第l l 硪 信息工程大学硕士学位论文 易知，当雄充分大以后，墨r ，( w ，”m ，o ) 可以一致的小。 在脚。膨：生成器模型中，其输出序列可看作以厂y ，z ) 为反馈逻辑的非线性组合器。 综合i ，两种情况，由胁d 一朋妇秒定理，( x ，y ，z ) 是具有至少l 阶相关免疫的逻辑 函数，再由定义得： 定理2 1 7 胁肘：生成器输出序列具有相关免疫性。 5 脚肘：生成器输出序列的相关特性 序列的相关性包括自相关性和互相关性，它们分别由序列的自相关函数和互相关函数 一 俨i 定义。若序列4 = q ，f o 的周期为p ，则序列的自相关函数为：c - ( f ) = 叩( 吼) ，7 ( 以+ ，) ( 这 里叩( o ) = l ，7 ( 1 ) = 一1 ) ；对于两条周期为p 的序列二= q ，f o ，占= 伯，f o ，其互相关 函数为：c - 矗( f ) ：窆】7 ( 吒切( 岛。) 。m 序列的自相关值在周期处取最大值，其他位置均取值 一1 ，互相关值均较小，即有尖锐的自相关性和弱的互相关性，下面来考查玉。托生成 器输出序列的相关特性。 5 1 删。鼻如生成器输出序列的自相关特性 在咒m m ：生成器模型中，通过计算机对大量瓦忆膨，生成器输出序列进行统计后发 现，鼢毛鸩生成器输出序列虽然自相关值不具规律性，但均具有良好的自相关特性。这 里取k 、m 、m ：输出序列饷反馈函数均为7 次本原多项式进行说明，令足输出序列的 反馈多项式为，+ 石+ l ，m 输出序列的反馈多项式为，+ + ，+ 工2 + l ，m ，输出序列的 反馈多项式为j r 7 + 工6 + ，+ j r 4 + ，+ 工+ 1 ，它们均为本原多项式，可得彪鸩生成器输出 序列 一，f 2 0 ；同理令k 输出序列的反馈多项式为x 7 + ，+ ，+ + l ，肘，输出序列的反 馈多项式为，+ 矿+ ，+ x + l ，弘输出序列的反馈多项式为j 7 + + ，+ ，+ ，+ 善+ l ， 可得胁毛肘：生成器输出序列 暑2 ，f o ，由自相关函数的定义，并利用计算机仿真可得序 列 霹，f o 的自相关特性如图2 2 ，序列 墨2 ，f o 的自相关特性如图2 3 ： 第1 2 页 信息工程大学鞭士学位论文 黧2 2 劳瓣 ，i 鸯懿叁稿关特毪鞭2 3 序舞 # ，f 堪熬鑫稳关特戆 从阁2 。2 秘2 3 中可以看出，当置、毒磊、款级数为7 时，两条足瞄材，生成嚣输融 序列均谯疑周期处达到自相关峰值1 6 1 2 9 ，丽最大剐峰值为3 6 3 ，埘。尬生成器输出序捌 具有尖锐的自相关特性。 5 2 翮膨：生成器输出序列的互相关特性 序列 ，f o 、 岛2 ，f o 的取法同上，融驻相关函数的定义，遥过计算机模拟褥两 条序列的飘相关特性如图2 4 ： 围2 4 旁襄 ，i 啦帮 蕊2 ，f 噻瓣互穗若特缝 蠡黧2 莲箱，寒捌杖，i 噻、序列 蕊2 ，f 啦农髑期为1 6 1 2 9 豹债况下褥蘩夔互秘荚壤 的绝对德均小于枷，并通过对大量静鼢磊如嫩成器输出序列进行统计，都具有较小的 第1 3 贫 信息工程大学硕士学位论文 互相关值。故在码长固定的情况下，圈w m ，生成器输出序列可提供较多的码字。综上可 以看出，j 。m ：生成器输出序列具有良好的自相关特性和互相关特性。 至此，我们已对磊m 。肘，生成器输出序列的密码学特性进行了分析和讨论，结果表明， j i = m 。 如生成器输出序列具有较长的周期，较高的线性复杂度，良好的伪随机性，且具有 至少一阶相关免疫性。我们在对其相关特性进行计算机仿真时发现，在移位不是周期整数 倍条件下，序列都有低的自相关值；在各种移位条件下，序列都有低的互相关值，因此具 有较大的码量；置m m ，生成器易于软硬件实现，这些特征符合扩频通信系统中伪随机序 列作为扩频码的条件，因此脚。m 生成器输出序列在扩频通信系统中将具有很大的应用 价值。 研究还发现，当 t 、m 输出序列的反馈函数互为互反多项式时，删。肘：生成器输 出序列的伪随机性、相关特性等结果与文献【1 2 】中关于胁，膨生成器输出序列的研究结果 一致，可见面，膨生成器是一种特殊的五m 。膨，生成器。 2 2 加法型组合生成器输出序列的特性分析 加法型组合生成器是由两个停走生成器模2 相加构成的m ，文献【1 8 】对加法型组合生 成器的建立了概率模型，并研究了其输出序列的分布，数字特征，齐次马氏性、遍历性和 强平稳性等概率性质。文献【2 l 】还讨论了加法型组合生成器输出序列的符合率问题，本节 将以代数方法对加法型组合生成器输出序列的性质进行分析。 2 2 1 加法型组合生成器模型 由两个“停走生成器”模2 相加构成的组合生成器称为加法型组合生成器，它由四 个线性移位寄存器上月姗1 ，三，= 5 翼2 ”，j = 】，2 构成。其构造如图2 5 所示： 时钟 时钟 叵叫 。一 目 图2 5 加法型组合生成器模型 这里鄹兄1 ”、z 属识l ”、脓2 ( ”、盯船2 2 分别记为墨、吃、鸠、 毛，其输出 第1 4 页 信息工程大学硕士学位论文 序列的反馈函数的级数分别记为蜀、墨、m 、鸩的级数；“o ”为模2 加。设它们的 线性移位寄存器输出序列分别为 珞“，x “，砭“，一) 和 z ”，z f “，z “，” ，i = l 、2 ，则由 此得到的两个“停走”生成器的输出序列为 x ，x ，艇，) ，七= 1 、2 ，满足 f 璐= z 舻 1 掣吃，腔l ，扣1 、2 ， l 名 这里表示在实数域上求和。记 讧。，五，以，) = 扛j 1 o 硝”，硝”o 研“，叫1 o z 臻 。 下面我们来考察加法型组合生成器序列 矗，墨，以， 的性质。 2 2 2 加法型组合生成器输出序列的性质 类似的我们也主要研究加法型组合生成器输出序列的周期、线性复杂度、相关性、相 关免疫性等代数性质。 1 加法型组合生成器输出序列的周期 定理2 2 1 若加法型组合生成器中，k ，恐的级数为七，肘。、鸩的级数为埘，那 么输出序列 j 0 ，疗l 的周期为( 2 一1 ) ( 2 ”一d 。 证明在加法型组合生成器中，对于墨m 生成器，有( 2 “，2 ”一1 ) = l ( 2 “1 为序列 i ”，f o l 一个周期内l 的个数) ，从而 捌”，f o 的周期为( 2 一l x 2 ”一1 ) 陋1 。同理， “，f 2o ) 周期也为( 2 一1 ) ( 2 ”一1 ) ，且 耐”，f o ， 瑶”，f o 平移相异，故加法型组合生 成器输出序列的周期为( 矿一1 ) ( 2 ”一1 ) 。 同胁f 。肘：生成器输出序列类似，加法型组合生成器输出序列的周期随墨、局和m 、 m ，的级数指数级增长，从而具有较长的周期。 2 加法型组合生成器输出序列的线性复杂度 我们仍然用生成函数的方法来讨论加法型组合生成器输出序列的线性复杂度。 定理2 2 2 若在加法型组合生成器中，墨，蜀的级数为| ，膨。、鸩的级数为m ， 那么输出序列 x 。，拜芝l j 的线性复杂度为2 m ( 矿一1 ) 。 f _ f - lhf 一】 证明记p = 2 一1 。令“( d = 玲”，“协= i 一z ”，哟= z 圆，v 协= f 一z ”， f - l ，2 ，则有 ( ，l p + o = 万甜p ) + “( f ) 屯甲+ d = 印+ f 一“( 印+ d = ，妒一雄甜( p ) + f 一“d 第1 5 页 信息工程大学硕士学位论文 同理 = 玎球。( p ) + 甜i f ) “印+ f ) = 删( p ) + 1 ， 屯嘎p + f ) = ，w x p ) + v x f ) ，以0 “( p ) = “力= 2 “、”t ( 力= ，t ( p ) = 2 “1 1 分别为埘序列 z m ，f o ，七= l 、2 一个周 期内l ，o 的个数。 又记 嬲”，研“，雹”， = 现孙乏： ) ，厄：) ， 嬲习，厨“，墨”，- ) = 曩盈，乏盈，墨盈， 则序列 厨”，f o 的母函数为： 妒o 时= 乏：；) + 乏岛j + 乏岛j r 2 + + 乏：，x 川+ 乏：_ ，+ = 厄+ 厄，+ z 3 计，+ + 可z ： ) + 互0 m m 工9 + z 恐， + 叩) + 】 + + ，1 【z ：江1 ) + 2 ：0 ) + 。( p 1 ) j + z ：苌，) + 。( p 1 ) ，p + = z 黜) + 墨工+ z ：，) x 2 + + 互岛+ 2 婴州。) ，+ 乏。( 1 ) x 2 + 】 + + 工川【乏譬l ，+ z 当州，1 ) x 9 + z 三一州川) x 2 + 】 不妨设序列 刁“，f o 的反馈函数为为厂( 力，序