（应用数学专业论文）前馈网络流密码的还原方法.pdf

n a n j i n gu n i v e r s i t yo f a e r o n a u t i c sa n d a s t r o n a u t i c s t h eg r a d u a t es c h o o l c o l l e g eo fs c i e n c e t h er e d u c t i v et e c h n i q u eo ff e e d f o r w a r d n e t w o r ks t r e a mc i p h e r a t h e s i si n m a t h e m a t i c s b y n a m ew u z h e n g a d v i s e d b y p r o f c a ox i w a n g s u b m i t t e di np a r t i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o rt h ed e g r e eo f m a s t e ro fs c i e n c e f e b r u a r y , 2 0 1 0 8085删2删8iiiii_m y 承诺书 本人声明所呈交的硕士学位论文是本人在导师指导下进 行的研究工作及取得的研究成果。除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得南京航空航天大学或其他教育机构的学位 或证书而使用过的材料。 本人授权南京航空航天大学可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名：多、抄 日期： 塑! ! ! i 。丝 一 i 南京航空航天大学硕十学位论文 摘要 在信息时代的今天，信息的安全与可靠已经成为人们越来越关注的问题。前馈网络( 也称滤 波生产器) 作为一类重要的密钥流生产器，其设计和分析一直是流密码研究的一个重要方向。在 其安全分析中，相关分析和线性分析是最有效的两种攻击手段。本文针对前馈网络流密码在不 同条件下的安全问题作了一些探讨，并给出了一种有效攻击方法。 本文所给出的攻击方法是在未知系统密钥条件下的一种已知明文攻击方法，它解决了上述 两种针对前馈网络流密码的攻击方法中共同的一个难点问题，即在滤波函数未知条件下无法对 系统实施攻击。就此问题，本文推j 发展了频谱理论的一个重要结论，并巧妙地将其运用于前 馈网络流密码的分析中。由此给出了一种仅利用足够长的前馈密钥序列就能还原滤波函数的方 法，即对于一个前馈网络系统，在非线性滤波函数和抽头集两个系统密钥参数均未知的情行下， 仅由足够长的前馈输出序列就能够实现这两个参数的求解还原。 关键词：前馈网络，前馈序列，w a l s h 谱，m 序列，非线性滤波函数，线性反馈移位寄存器 前馈网络流密码的还原方法 a b s t r a c t i ni n f o r m a t i o nt i m e s ，t h es e c u r i t ya n d r e l i a b i l i t yo fi n f o r m a t i o nh a sb e c o m eag r o w i n gc o n c e r n f e e d f o r w a r dn e t w o r k ( a l s ok n o w na sf i l t e rg e n e r a t o r ) a sak i n do ft h ei m p o r t a n tk e ys t r e a mg e n e r a t o r s ， i t sd e s i g na n da n a l y s i sh a sb e e nah o t s p o to fs t r e a mc i p h e r s o ni t ss e c u r i t ya n a l y s i s ，c o r r e l a t i o n a n a l y s i sa n dl i n e a ra n a l y s i sa r et h et w om o s te f f e c t i v em e a n so fa t t a c k s i nt h i sp a p e r , t h es e c u r i t y i s s u e so ff e e d f o r w a r dn e u r a ln e t w o r ks t r e a mc i p h e ru n d e rd i f f e r e n tc o n d i t i o n sa r ed i s c u s s e d ，a n da l l e f f e c t i v ea t t a c km e t h o di sg i v e n t h ea t t a c km e t h o dp r e s e n t e di nt h i sp a p e ri sak n o w np l a i n t e x ta t t a c km e t h o d ，w h i c hi su n d e rt h e c o n d i t i o no ft h eu n k n o w ns y s t e mk e y , i ts o l v e sad i f f i c u l tp r o b l e mw h i c ht h ea b o v e m e n t i o n e dt w o m e a n so fa t t a c k i n gf e e d f o r w a r dn e t w o r kh a v ei nc o m m o n ，n a m e l y , t h et w om e a n sc a nn o ta t t a c kt h e s y s t e mw i t h o u tt h ef i l t e rf u n c t i o n t os o l v et h ep r o b l e m ，a ni m p o r t a n tc o n c l u s i o no fs p e c t r a lt h e o r yi s g e n e r a l i z e da n da p p l i e dt ot h ea n a l y s i so ff e e d f o r w a r dn e t w o r k ss k i l l f u l l yi nt h i sp a p e r a n dt h e n ，a m e t h o df o rr e v e r t i n gt h ef i l t e rf u n c t i o nw i t ht h ef e e d f o r w a r dk e ys e q u e n c e sw h i c ha l el o n ge n o u g hi s g i v e n t h a ti s ，f o raf e e d f o r w a r dn e t w o r k ，i ft h et w op a r a m e t e r s ，n o n l i n e a rf i l t e rf u n c t i o na n dt a ps e t ， a r en o tg i v e n ，w ec a l ls t i l lr e v e r tt h et w op a r a m e t e r so n l yu s i n gf e e d f o r w a r ds e q u e n c e sw h i c ha r el o n g e n o u g h k e yw o r d s ：f e e d f o r w a r dn e t w o r k ，f e e d f o r w a r ds e q u e n c e s ，w a l s hs p e c t r a ，ms e q u e n c e s , n o n l i n e a rf i l t e r f u n c t i o n ，l i n e a rf e e d b a c ks h i l lr e g i s t e r i i 南京航空航天大学硕十学何论文 目录 第一章引言1 1 1 研究背景介绍1 1 2 本文的研究内容及论文安排2 第二章流密码原理。4 2 1 流密码的基本概念4 2 1 1 流密码的一般原理4 2 1 2 流密码分类5 2 2 密钥流的密码学性质5 2 2 1 序列的周期性和随机统计性6 2 2 2 序列的线性复杂度6 2 2 3 小结7 2 3 线性反馈移位寄存器序列7 2 3 1 移位寄存器7 2 3 2 线性反馈移位寄存器一8 2 3 3m 序列的性质。9 第三章前馈网络流密码及频谱理论1 0 3 1 前馈网络流密码的模型1 0 3 2 前馈序列的密码学性质1 1 3 3 频谱理论1 2 3 3 1 一阶w a l s h 谱的定义及其主要性质1 2 3 3 2 布尔函数的w a l s h 谱表示1 3 3 3 3 一阶循环w a l s h 谱的实质意义1 3 第四章已知系统密钥条件下前馈网络的攻击1 4 4 1 密码分析学概述1 4 4 2 分别征服相关攻击方法：1 5 4 3 最佳仿射逼近攻击方法1 7 4 4 j 、结1 9 第五章未知系统密钥条件下前馈网络的攻击2 1 5 1 一阶循环w a l s h 谱的一个性质及重要推广。21 5 2 一阶循环w a l s h 谱在前馈网络攻击中的应用2 4 5 2 1 攻击原理分析2 4 5 2 2 攻击步骤及实例2 8 第六章结论3 3 参考文献3 4 致谢3 6 在学期间的研究成果及发表的学术论文3 7 i i i 前馈网络流密码的还原方法 图表清单 图2 1 流密码原理图4 图2 2 同步流密码5 图2 3 自同步流密码5 图2 4 甩级反馈移位寄存器8 图3 1 单输出前馈网络1 0 图3 2 多输出前馈网络1 0 图4 1 非线性组合流密码1 5 表5 1 二次方程误差结果3 0 表5 1 三次方程误差结果3 1 l 南京航空航天人学硕士学位论文 第一章引言 1 1 研究背景介绍 密码技术早在几千年前已经用于保护军事和外交通信，但是古代的密码技术可以说只是一 种艺术，而不是一种科学，因为那个时期的密码技术更多的是依靠密码专家的直觉、经验和技 巧，缺乏系统的理论和方法。直到1 9 4 9 年s h a n n o n 发表了“c o m m u n i c a t i o nt h e o r yo fs e c r e c y s y s t e m s ”【l 】一文为单钥密码系统建立了理论基础，密码学才真正成为一门科学。1 9 7 6 年d i f t i e 和h e l l m a n 发表的“n e w d i r e c t i o ni nc r y p t o g r a p h y ”【2 】提出了一种崭新的密码体制( 公钥体制) ， 为解决通信网络中的信息安全提供了新的理论和技术基础，导致了密码学上的一场革命。近年 来，随着通信技术和计算机网络的高速发展，密码学无论是在理论上还是在应用上都得到了飞 速发展。 密码学是研究密码系统和通信安全的一门学科，包含密码编码学和密码分析学。前者寻求 保证消息保密性或真实性的加密算法，而后者则是研究己加密消息的破译或消息的伪造。二者 既相互对立又密切相关，双方的相互作用促进了密码学的发展。 密码按加密方式可分为流密码( 序列密码) 和分组密码，两者各有特点。相对而言，流密码 历史悠久，有较为理想的数学分析工具( 如频谱理论和代数方法) ，且加解密易于电子线路硬件 实现，实时性好，这些优势使其理论在近年来得到很大发展。在实际应用中，特别是在专用和 机密机构中，流密码体制保持着其重要地位，目前大多数国家的军事和外交保密通信都主要使 用流密码加密方式。 流密码系统设计的主要任务就是研究如何用一个较短的初始密钥生成一个长的安全的密钥 序列，所以它的密码强度主要取决于密钥流生成器的设计。一个安全的密钥流生成器必须使用 非线性变换，一般包含驱动部分和非线性组合部分。驱动部分控制存储器的状态转移，提供周 期大、统计特性好的序列供组合部分使用，而非线性组合部分则用于控制和提高生成器输出密 钥序列的统计特性、线性复杂度及其稳定性，保证输出密钥流序列的强度。 当前流密码学界所关注的三大流密码系统为前馈网络流密码、非线性组合流密码和钟控流 密码。前两个系统所生产的密钥流序列具有较好的统计特性，但线性复杂度不易控制，而后者 的线性复杂度可以很大，但统计特性不理想。三者之中，由于前馈网络流密码模型设计实现最 为简洁( 只用了一个线性移位寄存器l f s r ) ，而提高密钥序列的线性复杂度效果显著，故应用最 为广泛。 长期以来，人们对流密码的安全性及攻击方法进行了大量的研究。现有的攻击还原分析方 法基本都适用于前馈网络流密码系统。利用输入输出的相关性来攻击类似网络是研究最多且最 前馈网络流密码的还原方法 有效的一种方法。1 9 7 8 年，b l a s e r 和h e i n z m a n n 最早提出针对非线性组合生成器的相关攻击。1 9 8 5 年s i e g e n t h a l e r 吸收图论中的“d i v i d ea n d c o n q u e r ”算法的思想给出了一种被称为“分别征服” ( d c ) 的相关攻击方法f 3 】，利用移存器输出序列与密钥流序列之间的相关性恢复线性反馈移存 器的初始状态。1 9 8 8 年w m e i e r 和o s t a f f e l b a c h 提出了一种使用概率迭代译码算法的快速相关攻 击【4 】，不需要穷尽l f s r 的所有可能初态就能找出正确的初态，从而大大提高了攻击效率。但此 方法的攻击效果依赖于移存器反馈多项式的项数，项数较大( l o ) 时，攻击效果就不明显了。1 9 8 7 年，丁存生、肖国镇等利用相关分析思想给出了所谓的b a a 攻击方法，并提出了为保证前馈流 密码有足够的保密性，必须在其设计过程中考虑序列线性复杂度的稳定性问题，建立了一套相 应的流密码稳定性理论p 】。针对相关攻击方法效果受至u l f s r 的级数限制的问题，e r i cf i l i o l 在 2 0 0 0 年的印度密码年会上提出了采样攻击方法【6 】，其优点是：仅需考虑移位寄存器的长度，而 不必管反馈多项式具有什么样的形式；与已知较好的攻击方法相比，大幅度降低了计算复杂度。 针对前馈网络密码系统的攻击，除了运用上述分析法，常j h j 的分析方法还有线性校验子分析1 7 j 、 线性一致性分析【s j 以及改良的快速相关攻击【9 l 等。另外目前不少人还利用概率统计理论和频谱 理论知识来收集各种流密码模型的信息泄漏以及提高攻击方法的成功率1 1 5 1 。 当今，流密码的研究虽然没有分组密码、公钥密码、数字签名、身份识别等领域的研究那 么热，但是它在信息安全领域仍然占据着重要地位。而作为一类重要的流密码体制，前馈网络 流密码系统安全及其输出密钥流序列的密码学性质仍需要人们更深入地去研究和探索 1 6 - 2 2 1 。 比如，对系统中非线性滤波函数的研究 2 3 - 2 9 】，如何设计一个相关免疫性、非线性性、严格雪 崩性、扩散特性、平衡性、差分均匀性好的滤波函数对该体制序列密码的安全性有着至关重要 的影响。另外，目前新的前馈网络流密码系统有自同步前馈、有记忆前馈、多输出前馈、混沌 前馈【3 0 】等。对新前馈密码系统密码特性和安全性的分析，如何提高现有攻击方法的成功率，发 展新的分析方法是前馈网络流密码研究的新方向。 1 2 本文的研究内容及论文安排 本文研究的是一类重要的流密码体制前馈网络流密码的攻击还原方法。文中介绍了该 模型的一些密码学性质，主要研究分析了已知系统密钥条件和未知系统密钥条件两种情形下对 该密码体制的攻击还原方法。两种情形由于条件不同故而求解目标也有所不同。情形一是在网 络系统密钥非线性滤波函数已知的条件下，利用输出密钥流序列求取初始密钥。情形二是在非 线性滤波函数未知的条件下，仅由输出密钥流序列来求解还原网络系统密钥参数。本文的主要 创新点： ( 1 ) 将频谱理论的一个结果进行了重要推广，并给出了严格的理论证明。 ( 2 ) 利用频谱理论知识，巧妙地将推广的结论运用于前馈网络模型的分析中，给出了一种在 1 2 南京航空航天大学硕十学位论文 未知网络系统密钥参数条件下攻击还原前馈网络系统参数的有效方法。即在前馈网络系统中非 线性滤波函数和抽头集这两个参数均未知的情形下，仅由输出密钥流序列就可能实现这两个参 数的求解还原，并给出了具体的求解方法和应用实例。另外利用本文的方法还可以快速辨明密 钥流生成器是否采用了前馈网络体制。 本文的结构安排如下： 第一章简单概述了前馈网络流密码的研究背景、现状及发展趋势，并简单介绍了本文在前 馈网络系统方面的研究结果。 第二章简要介绍了流密码体制的基本概念、原理以及线性移位寄存器理论。 第三章系统介绍了前馈网络流密码系统的模型和密码学性质，并简单介绍频谱理论的基础 知识。 第四章介绍分析了当前在已知系统密钥条件下对前馈网络的两种主要攻击方法，即分别征 服相关攻击法和最佳仿射逼近攻击法，并对比分析了两种方法的优缺点。 第五章将频谱理论的一个性质作了推广，并将推广的结论应用于前馈网络分析。给出了一 种在未知系统密钥条件下攻击前馈网络的可行方法，实现了在唯输出密钥条件下就能还原前馈 网络的滤波函数和抽头集，并给出了应用实例。 第六章为结论。 3 前馈网络流密码的还原方法 第二章流密码原理 2 1 流密码的基本概念 密码体制按加密方式的不同可分为流密码和分组密码。在分组密码中，明文被分成固定长 度m 的若干组，每一组明文在初始密钥所确定的加密变换的作用下得到固定长度n 的密文。 即分组密码是用固定的变换来处理明文序列组，相同的明文组对应相同的密文组。就此而言， 流密码比分组密码要安全。这是因为流密码是将明文字符串与同等长度的密钥流序列逐位地加 密成密文，明文的重复部分所对应的密钥流是不同的，故对应的密文部分一般是不同的。同时， 由于不存在数据扩展和错误扩散，加、解密速度快，且易于硬件实现，流密码在实际中得到广 泛的应用。 2 1 1 流密码的一般原理 在流密码系统中，由于明文序列与密钥序列是逐位作用，因此密钥序列必须与明文序列具 有相同的长度。显然这样的密钥序列在现实中是难于分配和管理的，实际应用中的密钥序列都 是由密钥空间中较短的初始密钥经过某些算法生成的。 通常一个实际的流密码系统可用六元组( k ，m ，c ，晟，d t ，z ) 来描述。k 为密钥空间， m 为明文空间，c 为密文空间。对于每一个密钥尼k ，由算法z 确定一个二进制密钥序列 z ( k ) = z 0 毛，z 2 。最和d k 分别表示密钥尼在算法z 作用下生成的加密和解密算法，常用的 算法为模2 加运算。当明文为聊= 历o ，m l ，一，m 川时，在初始密钥尼下的加密过程如下： ( 1 ) 由算法z 和尼确定密钥序列z ( k ) = z o ，z 1 ，z 2 。 ( 2 ) 对f = 0 ，l ，力一1 ，计算q = 聊foz f ，即得密文c = c o ，q ，巳一1 。一 ( 3 ) 对密文c = c o ，c l ，乞一l 的解密过程为：对f = 0 ，1 ，2 一l ，计算肌，= c i0z i ，即恢复 明文朋= m o ，垅l ，m 州。流密码系统可用图2 1 表示。 4 图2 1 流密码原理图 l 南京航空航天大学硕士! 学位论文 由流密码系统的上述工作原理可知，流密码系统的安全性完全由密钥序列z ( 尼) 决定。因 此，流密码系统设计的主要任务就是研究如何用一个较短的初始密钥生成一个长的安全的密钥 序列，它的密码强度也主要取决于密钥流生成器的设计。通常密钥流z ( k ) 是一个由初始密钥k 通过确定性算法产生的伪随机序列。如果密钥流z ( 尼) = z 0z ，z ：是由一个离散无记忆的信源 所产生的均匀分布的随机序列，则该系统显然是不可破的，我们称其为“一次一密”系统。但 这样的系统对密钥的管理要求太高，现实中是不可用的。 2 1 2 流密码分类 流密码体制根据密钥序列与明、密文的关系，可分为同步流密码和白同步流密码。密钥序 列的生产与明密文无关的流密码被称为同步流密码，密钥序列的生产与已经产生的密文有关的 流密码则被称为白同步流密码。其结构分别如图2 2 和图2 3 。 图2 2 同步流密码图2 3 自同步流密码 在同步流密码中，密钥流的产生是独立于消息流的，其加密变换是无记忆的。只要初始密 钥k 和生成器装置一样，就能产生出相同的密钥序列。这种体制的一个优点是没有错误扩散， 单个密文比特位的传输错误不会影响后续的比特位，即由于外界干扰所造成的一个密文位的传 输错误只影响对应位的一个明文位的译码。 而在自同步流密码中，由于密文参与了后续密钥的生产，因而具有一定的错误传播特性。 即单个密文比特位的传输错误会影响后续若干比特位的密文位译码，而影响相应的明文位。 由于自同步流密码的密钥序列的生产参与了不确定因素消息流，因而较难从理论上对其进 行研究分析。目前的大多数流密码研究成果都是关于同步流密码的。 2 2 密钥流的密码学性质 流密码体制安全的核心问题是密钥流生成器的设计，所以力求使生产的密钥序列是近乎完 美的随机序列是密码设计者所追求的目标。我们知道，实际使用的密钥序列都是通过固定算法 生成的，是不可能完全随机的，所以一定存在某些方面的不随机性。 5 前馈网络流密码的还原方法 2 2 1 序列的周期性和随机统计性 无特别说明，本文所讨论的序列均为二兀域g f ( 2 ) 上的序歹u 。 定义2 1 对于序y o s _ = s i ) ，若存在正整数丁使得，对v f ，均有艮r = s ，则称点= “) 为 周期序列，满足上述关系的最小正整数丁，称为苎= “) 的周期。 定义2 2 在周期序列点= s f 的一个周期中，若s i l s i = s i + l = = s i + f - l s m ，则称 ( s is + l ，s i + - i ) 为序列点= 缱) 的一个长为，的游程。 定义2 3 周期为t 的序列s = s i ) 的自相关函数定义为 尺( ) = 7 1 乙f = o t - i ( 一1 ) p ， o 丁。 当j 0 时，r ( j 1 也称异相自相关函数， 为了度量二元伪随机周期序列的随机性， g o l o m b 随机性假设1 3 2 】： r ( 0 ) = 1 。 g o l o m b 对序列的随机性提出下述三条假设，即 ( 1 ) 在序列的一个周期内，0 与1 的个数相差至多为l ： ( 2 ) 在序列的一个周期圈内，长为1 的游程数占总游程数的l 2 ，长为2 的游程数占1 2 2 ， 长为n 的游程数占1 2 ”，且在等长的游程中，o ，1 游程各占一半； ( 3 ) 序列的异相自相关函数是一个常值。 条件( 1 ) 和( 2 ) 表明序列在一个周期内0 和l 出现的概率和分布几乎相同。条件( 3 ) 表明通过对 序列与其平移后的各序列作比较，不能搜集到任何信息。严格满足上述三个条件的伪随机序列 是很少的，后续将介绍的m 序列满足这三个条件。 2 2 2 序列的线性复杂度 ， 定义2 4 序列羔= “ 的线性复杂度是指使得序列各项满足如下线性迭代关系式的最小正 整数三，记作c q ) 。 墨+ a i s f l + 口2 斗2 + + 口上s i _ 工= 0 ，l f n 其中n 为序列苎= s i ) 的长度，口l ，口2 ，a 上为g f ( 2 ) 上三个固定常数。 如果用线性反馈移位寄存器来生产一个序列，显然，它的线性复杂度就是能产生此序列的 最短线性反馈移位寄存器的阶数，此时关系式中的个固定常数即为线性反馈移位寄存器的反 馈系数。 关于序列的线性复杂度的计算有一个很有效的算法，即著名的b e r l e k a m p m a s s e y ( b m ) 算 法【3 3 , 3 4 ，可在，z 三时间计算出线性复杂度为的n 长序列的线性复杂度。序列的线性复杂度有 重要的密码学意义。 引理2 1 3 1 1k s = s i ) 是g f ( 2 ) 上周期序列，且序列 s ，) 的线性复杂度为l 1 ，则只要 1 6 南京航空航天大学硕+ 学位论文 知道 s ，) 中任意连续的2 位就可确定整个序列辑) 及产生“) 的极小多项式。 引理2 1 说明对于一个线性复杂度为的序列，只需知道该序列的任意2 个连续元素，就 能够利用b m 算法确定整个序列。显然，作为流密码体制加密过程中的密钥流序列必须具有足 够火的线性复杂度。因而线性复杂度是度量密钥流序列的密码学强度的一个重要指标。 2 2 3 小结 在实际应用中，密钥序列都是通过固定算法生产的，一般都是周期序列。为了满足密码体 制的安全性要求，防j 上一些简单、快速攻击方法的威胁，密钥序列至少应当具有一定的伪随机 性准则。对密钥序列的设计一般要符合以下几个要求： ( 1 ) 序列要有足够火的周期。 ( 2 ) 序列的随机统计特性应尽可能满足g o l o m b 的随机性公设。 ( 3 ) 要通过序列的任意局部部分来分析获取整个序列，在计算簧上是不可行的。 ( 4 ) 序列的生产要高效快速。 上述要求中第( 3 ) 条要求决定了密码体制的强度，是流密码理论的核心。主要是用来防止从 局部密钥流分析重构出整个密钥序列，它包含了流密码要研究的许多主要问题，如相关免疫性、 线性复杂度以及不可预测性等。最后一条要求是基于密钥流生成器的实刚性而提出的，要保证 流密码加解密速度快的强势。 目前，火多数流密码体制中的密钥流生成器都是基于移位寄存器原理。主要原因是因为移 位寄存器结构简单，运行速度快，而且理论成熟。不同的安全部门和安全对象所采用的移位寄 存器的级数并没有统一标准，当前一般认为带有安全参数的1 0 0 级移位寄存器序列是足够安全 的。为此，下节就简要介绍一下移位寄存器的重要概念和理论。 2 3 线性反馈移位寄存器序列 移位寄存器序列是通过一种常用的电子设备“移位寄存器”所产生的序列，由于其结构简 单，运行速度快，因而在通信中有着广泛的应用。 2 3 1 移位寄存器 一个咒级反馈移位寄存器是指如图2 4 的电子设备。 它由两个部分组成： ( 1 ) 寄存部分，由刀个寄存单元墨，是，组成，每个寄存单元可存放0 或1 。 ( 2 ) 计算部分，z 个寄存单元墨，是，最输入到计算部分，计算厂( s ，是，最) 。 其中，某一时刻，墨，是，的值称为反馈移位寄存器的当前状态，共有2 ”中可能的状态， 寄存单元的个数以称为反馈移位寄存器的级数。厂( s ，是，瓯) 是，z 元布尔函数，称为反馈函数。 7 前馈网络流密码的还原方法 图2 4 n 级反馈移位寄存器 列 每经过一次时间脉冲，寄存单元的内容向右移动一位，最右端寄存单元的内容作为输出， 而函数值厂( s ，是，) 则反馈到最左端的寄存单元。如此下去，移位寄存器的输出序列即为无 穷序列s ，s ：，鼠，显然，此序列满足如下递推关系： 最+ 。= 厂( 最，瓯小，最+ n - i ) ， ( k = 1 ，2 ，3 ，) 易知，输出序列完全由初态( 墨，是，最) 和反馈函数唯一确定。 根据反馈函数是否是线性函数，反馈移位寄存器可以分为非线性反馈移位寄存器( n l f s r ) 和线性反馈移位寄存器( l f s r ) 。非线性反馈移位寄存器的理论分析比较困难，在目前的密钥 流生产器中应用较少，而线性反馈移位寄存器的分析理论已经很成熟，应用非常广泛。 2 3 2 线性反馈移位寄存器 线性反馈移位寄存器的反馈函数是如下线性齐次函数： 厂( 五，x 2 ，) = a n + 口。一l 恐+ + a l x n( a f g f ( 2 ) ) 。 即此时的计算部分其实就是一个加法器。 7 在n 级l f s r 中，总是假定a 。= 1 ，否则，z 级l f s r 可退化为n 一1 级。由于n 级l f s r 共有2 ”个状态，而在线性运算下，全0 状态不可能转入其它状态，非全0 状态也不可能转入全 0 状态，所以l f s r 的状态圈最多遍历2 ”一1 个状态，故n 级l f s r 的输出序列的最大周期为 2 ”一1 。 定义2 5 如果一个n 级l f s r 的输出序列的周期为2 “一1 ，这样的序列称为m 序列。 定义2 6 ，z 级l f s r 的反馈函数为f ( x a ，x 2 ，) = 五+ q 一1 恐+ + q ，则称多项式 g ( x ) = a n x ”+ a n _ i x ”1 + + 口2 ，+ a l x + 1 为该n 级l f s r 的特征多项式。 特征多项式是表征l f s r 结构特征的数学模型。一旦有了特征多项式，l f s r 的输出序列特 性也就完全确定了。关于特征多项式有如下引理【3 5 】： 引理2 2n 级l f s r 的特征多项式为g ( x ) ，若有g ( x ) lz ”+ 1 ，则l f s r 的输出序列的周 8 1 南京航空航天大学硕士学位论文 期丁满足丁i m 。 引理2 3n 级l f s r 的输出序列有最大周期2 ”一1 的必要条件是特征多项式是不可约的。 由引理2 - 3 知，如果一个n 级l f s r 的输出序列为m 序列，那么它的特征多项式就是不可 约的。但并非所有的不可约多项式所生成的序列都是m 序列。 定义2 7 设m = m i n klg ( x ) x 2 + 1 ) ，m 称为多项式g ( 力的阶。若，1 次不可约多项式 g ( x ) 的阶为2 ”一l ，则称g ( x ) 为本原多项式。 引理2 4 刀级l f s r 的输出序列是m 序列的充要条件是其特征多项式为n 次本原多项式。 2 3 3m 序列的性质 m 序列由于其白身的性质和容易实现的特点，在通信中有着广泛的应用。容易验证，z 级 m 序列具有一些优良的伪随机序列的统计特性： ( 1 ) 一个周期内，0 的个数为2 ”1 一l ，1 的个数为2 ”1 。 ( 2 ) 一个周期内，总游程数为2 ”1 ，对于1 f n 一2 ，长为i 的游程数为2 ”1 ，且0 ，l 游 程各占一半。长为n 一1 的游程只有一个0 游程，长为n 的游程只有一个1 游程。 ( 3 ) 序列的异相白相关函数为常值一1 丁。( t = 2 ”一1 ) 从上可知，达到最人周期2 ”一1 的，l 级m 序列满足g o l o m b 的随机性公设，具有理想的随 机统计特性。然而，n 级m 序列是绝对不能直接用来作为密钥序列使用的，因为它的线性复杂 度仅为n ，密码分析者只需截获连续2 刀位密钥序列就能利用b m 算法轻松还原整个密钥序列。 所以，在保密通信中使用m 序列时，一定还要同时加以其他手段。通常，m 序列是用来作为密 钥序列生产器的驱动部分，用以保证密钥序列的周期尽可能大。 另外n 级m 序列有如下特殊的平移可加性： 性质2 1 设a 是周期为丁的m 序列，则对v s ，t z + ，有 f 乜。r 口：j o ，s = m o d r 。 一一 l a ，s tm o d t 其中为序列的左移变换，0 。 9 前馈网络流密码的还原方法 第三章前馈网络流密码及频谱理论 3 1 前馈网络流密码的模型 二元加法流密码系统的核心问题就是密钥生成器，它的安全性和运算效率直接决定了该密 码系统的安全性和加解密速度。线性反馈移位寄存器虽然能产生随机统计性能良好的序列，但 是其输出序列的线性复杂度太低，很容易被攻击还原。所以单独的l f s r 不能作为安全的密钥 流生成器，必须在生成器中使用非线性变换。一类在密码设计和扩频通信领域中有着广泛应用 的重要的密钥流生成器就是前馈网络，也称为非线性滤波生产器。它由一个二元线性反馈移位 寄存器和一个非线性滤波函数( 或称前馈逻辑) 组成。按照前馈网络的输出类型可分为单输出前 馈网络和多输出前馈网络。一般来讲，我们把前馈网络输出的密钥流序列就称为前馈序列。两 种输出类型的结构分别如图3 1 和图3 2 。由于前馈网络系统只用了一个线性反馈移位寄存器， 所以在工程上有很大的实用价值。 l o a 口 非线性滤波函数厂( x ) 密钥流星 明文流 。夕r 、密文流。 图3 1 单输出前馈网络 图3 2 多输出前馈网络 一 南京航空航天大学硕十学位论文 图3 1 中l f s r ( r ) 均表示级数为，的线性反馈移位寄存器，其特征多项式一般均采用本原 多项式，以保证l f s r 的输出序列a = 口0 是统计性能优良的r n 序列。在此我们设其特征多项 式为g ( x ) = c r x 7 + q l x ”1 + + c 2 x 2 + q x + l ，则当给定一个，_ 维非零状态( 口0 ，q ，口，一1 ) 作 为l f s r 的初态时，则有口= ：。c ，口，k 厂。而l f s r 的这个初态，一般即为前馈网络 系统的初始密钥。厂( x ) 是一个n 元非线性布尔函数( n ，) ，称为滤波函数，其目的是使前 馈序列z = z ，) 在继承m 序列的优良统计性能的同时能增加其自身的线性复杂度。 图中的五( 1 f n ) 表示抽头，其值为位置序，是指把l f s r 当其位置的比特信息作为第f 维分量进入滤波函数厂( x ) ，且若f j ，则有而 x j 。一般要求t ，即各抽头均抽白l f s r 的当前状态中。不失一般性，我们规定= 0 ，则有乙= f ( a f + 西，a m ：，a f ) 。( i = 0 ，1 ，2 ，) 而对于多输出前馈网络中的f ( x ) 则是一个，z 元非线性多输出布尔函数( n 进m 出) ，其输出 可以看成是m 个n 元布尔函数。即厂( 工) = ( z ( 工) ，正( x ) ，工，( x ) ) ，( m 甩) ，其中每个z ( x ) 都必须是非线性布尔函数，它产生m 条前馈序列蜀，互2 ，毛。相比之下，多输出前馈网络系 统在密钥量的产生和加密速度上有很大优势。 本文主要讨论单输出前馈网络系统。对于多输出前馈网络，由于其各个输山分量之间会存 在着一定的制约关系，使其研究变得比较复杂，目前在这方面较为深入的研究尚不多见。 特别地，当，= ，z 的情形下，此时如果l f s r 产生的是一个周期为2 ”一1 的m 序列，那么所 有周期为2 ”一1 的二元序列都能通过选择适当的滤波函数由此密钥流生成器所产生。由此可见 这种生成器在理论上是很诱人的。 在前馈网络系统中，线性反馈移位寄存器的主要作用是通过一个较短的初始密钥产生了统 计性能良好而且周期达到最大的驱动序列，而非线性滤波函数的作用则是极大地提高了前馈序 列的线性复杂度。下节将介绍前馈序列的一些性质。 3 2 前馈序n i l , 0 密码学性质 本文所讨论的前馈网络系统中，均默认l f s r 的输出序列为m 序列。 我们设图3 1 中的l f s r 的特征多项式为，次本原多项式g ( x ) ，非线性滤波函数为n 元布 尔函数厂，并设厂的代数次数为m ，则有l f s r 的输出序列周期为t = 2 7 - 1 。则前馈序列兰必 为周期序列，且有如下性质p 6 。： 性质3 1 前馈序列兰的周期石是l f s r 的输出序列周期丁的因子，即五i 丁。 性质3 2 前馈序列互的线性复杂度c 乜) 满足： c 乜) ：。c ： 由性质3 2 可知前馈序列的线性复杂度的上界受滤波函数的代数次数限制。特别地，若滤 波函数为线性函数，则前馈序列的复杂度将不大于线性反馈移位寄存器的级数，所以滤波函 前馈网络流密码的还原方法 数必须是非线性的，而且次数不能太低。对于一般的前馈序列，要计算其复杂度或估计复杂度 的一个下界是困难的。但是对于一些特殊情形，则有如下结果： 引理3 1 t 3 6 1 若滤波函数厂( 五，j c 2 ，) = ：“岛薯西+ 1 一x u 七- l + z ( 五，屯，) ，其中 e i 巳，e 小，g f ( 2 ) 且不全为0 ，k n ，z ( 葺，恐，矗) 是次数小于k 的布尔函数，则由 厂( 五，x 2 ，毛) 产生的前馈序列圣的线性复杂度c 乜) 满足： c ( 兰) c ：一( n - k ) 。 从上分析，均说明前馈序列的复杂度与相应的滤波函数的次数紧密相关。另外，前馈序列 的统计特性也取决于滤波函数，若滤波函数f ( x ) 是平衡函数，则前馈序列也是平衡序列。反 之，如果f ( x ) 不平衡，则前馈序列必不平衡。另外，通过增加前馈函数的项数可以改善前馈 序列的统计特性3 7 1 。 3 3 频谱理论 我们知道布尔函数是实现密码体制的一个重要工具，特别是作为某些流密码中重要的组件， 布尔函数的性质在很火程度上决定了这些密码的安全强度。在前馈网络系统中，布尔函数的特 性就决定了前馈序列的性能，它是前馈网络流密码设计的关键所在。众所周知。频谱分析技术 是研究布尔函数的一个非常重要的手段，它是刻画布尔函数某些密码学性质最有力的工具。 3 3 1 一阶w a l s h 谱的定义及其主要性质 w a l s h 变换是研究布尔函数的重要工具，许多特征都可通过其w a l s h 谱来表示。先给出一 些定义： 定义3 1 设x = ( 五，x 2 ，) ，w - - - - ( ，w 2 ，) e ，w 与x 的点积定义为 w x = w i 五o 屯o 0 互。 定义3 2 对于n 元布尔函数厂( x ) ：e 专e ，x f ，称 0 ( w ) = 石1 厂( 工) ( 一1 ) ”。和& 小w ) = 击( 一1 ) m 胁j ， w f 1 2 为厂( x ) 的一阶线性w a l s h 谱和一阶循环w a l s h 谱。 注意到( 一1 ) ，1 = 1 2 f ( x ) 容易推出两种谱有如下关系： & 小w ) = 。- 一2 2 s 邑y ( ( w w ) ) ，, w w ；：e 。0 由关系式可知如果我们知道布尔函数的一种谱特征，则亦可确定布尔函数的另一种谱特征。 南京航空航天人学硕士学位论文 究竟先用哪种谱来研究，可根据具体情况而定。下面给出w a l s h 谱的两个重要性质： 性质3 3 ( p l a