（基础数学专业论文）两种新型的伪随机序列生成器的构造与分析.pdf

摘要 文中引进了两种新型的伪随机序列生成器：缩控生成器与缩扩生成器，它 们是由缩减生成器分别与一种新型的钟控生成器及自扩生成器组合构成的，均 由两个三元的线性反馈移位寄存器( l f s r ) 构成文中分别讨论了缩控序列 与缩扩序列的周期、符号分布、线性复杂度等密码学性质，并且对这种新型的 缩控序列的稳定性也进行了分析，讨论了其1 , 2 重量复杂度；对缩扩序列还给 出了其特征多项式，但对其线性复杂度的下界只给出了猜想最后，文中对几 种控制型生成器的主要密码学指标进行了比较，结果表明缩控序列与缩扩序列 的周期及线性复杂度均优于钟控序列( 文献【3 1 ) 与缩减序列( 文献 3 】) ，符号分 布也更加确定，因此二者是更加良好的密钥流序列，更适合于流密码系统中的 应用 关键词：伪随机序列；线性反馈移位寄存器；周期；线性复杂度；1 ，2 重量 复杂度；特征多项式 a b s t r a c t i nt h i sp a p e r ，w ep r e s e n tt w on e wt y p e so f p s e u d o - r a n d o ms e q u e n c eg e n e r a t o r ：t h ee d i t i n gg e n e r a t o ra n dt h es h r i n k i n g - e x t e n d e dg e n e r a t o r ( c a l l e ds e - g e n e r a t o ri ns h o r t ) t h e y a r eb o t hc o n s t r u c t e db yu s i n gt w ot e r n a r yl i n e a rf e e d b a c ks h i rr e 舀s t e r s ( l f s r ) b o t ht h e e d i t e ds e q u e n c e s a n dt h es e - s e q u e n c e s p e r i o d ，s y m b o ld i s t r i b u t i o na n dl i n e a rc o m p l e x i t y a r ed i s c u s s e di nt h i sp a p e r i na d d i t i o n ，w ea l s oa n a l y s i st h es t a b i l i t yo ft h i sn e we d i t e d s e q u e n c eb yd i s c u s s i n gi t s1 ，2 c o m p l e x i t yo fw e i g h t ，a n dg i v et h ec h a r a c t e r i s t i cp o l y n o m i a l o ft h es e - s e q u e n c ea sw e l l ，b u tw ej u s tg i v et h es e - s e q u e n c e sl o w e rb o u n do fl i n e a rc o i n - p l e x i t ya sac o n j e c t u r e i nt h ee n d t h em a i nc r y p t o g r a p h yi n d e x e so fs e v e r a lc o n t r o l l e d g e n e r a t o r sa r ec o m p a r e di nt h ep a p e r i ti ss h o w nt h a tt h ep e r i o da n dl i n e a rc o m p l e x i t yo f t h ee d i t e ds e q u e n c ea n dt h es e - s e q u e n c ea r eb o t hs u p e r i o rt ot h o s eo ft h es t o p - g os e q u e n c e ( r e f e r e n c e 3 ) a n dt h es h r i n k i n gs e q u e n c e ( r e f e r e n c e 3 ) ，a n dt h es y m b o ld i s t r i b u t i o no ft h e s e t w os e q u e n c e sa r ea l s oc l e a r e rt h a nt h o s et w o ，8 0t h e ya r eb e t t e rp s e u d o - r a n d o ms e q u e n c e s a n dm o r es u i t a b l ef o rp r a c t i c ei m p l e m e n t a t i o no fs t r e a mc i p h e rs y s t e m s k e yw o r d s ：p s e u d o - r a n d o ms e q u e n c e ；l f s r ；p e r i o d ；l i n e a rc o m p l e x i t y ；1 ，2 c o m p l e x i t y o fw e i g h t ；c h a r a c t e r i s t i cp o l y n o m i a l 1 1 第一章基础知识 1 1引言 密码按加密形式可分为流密码和分组密码，由于流密码具有结构比较简 单，有较为理想的数学工具等优势，近年来得到了长足地发展，目前最受欢迎 的流密码是所谓的二元加法流密码( 见文献【1 2 】) 二元加法流密码与二元一 次一密密码( 文献【1 2 】) 显然是相似的，这无疑是许多密码设计者和使用者重 视这类密码的主要原因在实用流密码中，密文长度远大于密钥长度，这样， 密码设计者最大的愿望就是设计出一个滚动密钥生成器，使得输出序列对于一 个资源有限的密码分析者来说，与完全随机的二元序列无任何区别，因此，设 计性能良好的密钥流序列始终是流密码学的一个研究热点2 0 世纪6 0 年代， g o l o m b 提出了伪随机序列的标准，即要有极大的周期、高的线性复杂度、相对 平衡以及伪随机序列的稳定性等 线性反馈移位寄存器( 简记为l f s r ) 因其实现简单、速度快、有较为成熟 的理论等优点而成为构造密钥流生成器最重要的部件之一目前比较成熟和实 用的流密码系统都是基于l f s r 构造的，可以把这些系统分为两大类：一类是 l f s r 和非线性布尔函数的组合( 文献【1 2 】) ，像非线性组合流密码和前馈流密 码都属此类；另一类是用一个l f s r 去控制另一个l f s r ，像钟控生成器( 文 献【3 】) 与缩减生成器( 文献【3 】) 本文就将介绍两种新型的伪随机序列生成器：缩控生成器与缩扩生成器 其中，缩控生成器是将文献 1 3 】中的缩控生成器的钟控方式加以改变所得到的 一种新型的缩控生成器；缩扩生成器是将自扩生成器与缩减生成器组合构造的 一种新型的伪随机序列生成器我们将看到，这两种新型的伪随机序列生成器 产生的密钥流序列均具有大的周期，高的线性复杂度，符号分布也比较均衡 虽然大的周期与线性复杂度并不能保证该序列是密码学意义上绝对安全的序 列，但足以表明能够经的起普遍的攻击，诸如b m 算法等，因此是适合于流 密码系统中的应用的 1 2基本概念 定义1 2 1 设a = 。t ) 是g f ( 3 ) 上的序列，称a 为周期序列，如果存在r 0 满足啦+ r = a i ，对o ；满足啦竹= a i ，i = 0 ，1 ，的最小正整数r 称为a 的最 小周期，记为p ( a ) = r 如果a 是一个周期序列，r 是其一个周期，我们也记 a = a o ，a 1 ，0 r 一1 ) 为r 维向量空间g f ( 3 ) ( ) = “0 0 ，a 1 ，a ，一1 ) ia t g f ( 3 ) 中 一个r 维向量。 设，( z ) = z ”一岛一1 z ”1 一岛一2 2 7 n 一c l z c o ，c 4 g f ( 3 ) 如果月中元素满 足下面的递归关系：a 。+ k = c n 一1 a n + 一1 + + c l a k + 1 + c o a k ，k = 0 ，l ，则称a 为 一个线性反馈移位寄存器序列，简称为l f s r 序列，( z ) 就称为a 的一个特 征多项式；次数最低的特征多项式称为a 的极小多项式，极小多项式的次数称 为序列a 的线性复杂度，记为l ( a ) 定义1 2 2 称形式幂级数s 。( z ) = 主8 n x ”为序列s = s 女) 的生成函数注 意到当序列s 的周期为n 时，s 一( z ) ：s ( z ) 曼z k n ，其中( 石) ：笔1 s 。扩 定义1 2 3 设，( z ) 是g f ( 3 ) 上一个多项式，( z ) 0 且，( o ) 0 ，则使 f ( x ) iz 8 1 的最小正整数e 称为，( z ) 的阶，记为o r d ( f ) = e 定义1 2 4 设f ( z ) 是g f ( 3 ) 上一个多项式，i ( z ) 的次数为n ( 钆1 ) ，如果 o r d ( f ) = 3 ”一1 ，则，( z ) 为g f ( 3 ) 上的本原多项式 定义1 2 5 如果，( z ) 为g f ( 3 ) 上的本原多项式，则以，( z ) 为特征多项式的 序列a 就称为g f ( 3 ) 上的n 级m 一序列 定义1 2 6 设a 是g f ( 3 ) 上的n 级m 一序列，在a 的两个长为t t 一1 的0 游程中任选一个插入0 ，则将得到的序列称为修改过的m 一序列，简记为n 级 m m 一序列 定义1 2 7 设s = 矾 是c f ( 3 ) 上周期为的一个序列，序列s 的u 重量 复杂度定义为： w c ( s ) 2 r a i n ：。l ( s + t ) 其中序列t 也以为周期，w ( ) 表示t 的汉明( h a m m i n g ) 重量，即r 在 2 其一个周期n 内非零分量的个数，l ( s + t ) 表示序列s 与t 和的线性复杂度 1 3基本性质与引理 性质1 3 1 设a 是g f ( 3 ) 上的n 级m 一序列，则a 具有下列性质： ( 1 ) p ( a ) = 3 ”一1 ( 2 ) 序列a 满足平衡性即在a 的一个周期段内，1 与2 各出现3 1 次，o ，出现3 1 1 次 ( 3 ) 在a 的一个周期段中，游程总个数为2 扩游程具体分布如下； ( a ) 对于1sk n 一2 ，每个a c f ( 3 ) ，长为k 的a 游程有2 2 3 n - k - 2 ； ( b ) 长为n 一1 的0 游程有两个，长为住一1 的1 游程和2 游程各有一 个； ( c ) 长为n 的1 游程与2 游程各出现一次，没有长为扎的0 游程 ( 4 ) 每一个非0 的礼维向量出现且仅出现一次 ( 5 ) 令d = ( 铲一1 ) 2 ，将a 分成两部分：a = ( a 1 ，a z ) ，其中a = ( a o ，a 1 ，o 扛1 ) ，a 2 = ( a d ，a d + 1 ，a 2 d - 1 ) ，贝4 a 2 = 2 a 1 即a i + d = 2 a i ，i = 0 ，1 ，d 一 1 特另0 的，若a = 0 ，贝0a t + d = 0 ，v i 20 证明由m 一序列的性质，( 1 ) 一( 4 ) 是显然的下面只证( 5 ) ： 据文献1 3 】中的定理：设几级m 一序列s 。的k 个平移序列守，j = 1 一k ， 任取k 个常数l j , j = 1 一k ，则序列塞o s 尹或为0 序列，或为s ”的一个平移 序列故此处我们只需考察序列a 与其平移序列z 4 a ，这里z 表示左移算子， a = ( a d ，a d + 1 ，) 取l l = 1 2 = 1 g f ( 3 ) ，又 a ：a oa la 2 o 扣ln dn d + l a 2 d 一1 z d a ：a dn d + 1n d + 2 a 2 d la oa l a d 一1 通过观察发现：l l a + l 。x 4 a 的周期减为原序列4 的周期的一半，因而它不会是 序列a 的平移序列故l l a + 1 2 x 4 a 就是0 序列，由此得a = 2 a ，即a 2 = 2 a 3 证毕 注在礼级m m 一序列a 中，长为n 一1 和长为礼的0 游程将各出现一次；长 为n 的1 游程和2 游程也各出现一次在一个周期段内，每个元素各出现3 1 次 引理1 3 2 设序列s = 钆) 的周期为( 未必是最小周期) ，记以下两个多项 式 f ( x ) = ( 1 一x n ) g o d ( 1 一z ，g n ( 窑) ) ；g ( x ) = s ( z ) 9 c d ( 1 一z ，s ( z ) ) 则i ( x ) 是序列s = s e ) 的极小多项式，且s 。( z ) = g ( z ) ，( z ) ；这里g c d ( ，) 表示最 大公因式，s ( z ) ：隹1 粕矿 n = o 证明参见文献【3 】 4 第二章一种新型的缩控生成器 2 1新的缩控生成器的构造 在文献【1 3 】中，作者将钟控生成器与缩减生成器组合构造了一种缩控生 成器，使得生成的缩控序列的各项密码学指标较钟控序列或缩减序列都有了很 大的提高下面，我们将钟控方式加以改变，从而得到了缩控生成器的一种新 模型首先给出它的定义： 定义2 1 1 设a = h ) ，b = b j 是g f ( 3 ) 上的两个l f s r 序列，输出序列 s = ) 由以下规则决定：在时刻j ，如果6 j = 2 ，则删除序列a 的当前输出位； 如果6 j = 1 ，则输出序列a 的当前输出位；如果如= 0 ，则在当前输出位的前一 位添加0 ，1 或2 ，具体如下：若j 兰0 ( m o d 3 ) ，则添加o ；若j ；1 ( m o d 3 ) ，则添加l ； 否则添加2 我们称这是一个缩控生成器，得到的序列s 就称为序列b 控制序 列a 得到的缩控序列，记为e d i t ( a ，b ) 下面是生成这种缩控序列的具体算法： i n p u t ：g f ( 3 ) 上的l f s r 序列a ，b o u t p u t ：长为m 的缩控序列s 1 k = j = i 一0 2 w h i l e ( k 1 ) ，并且假定这里的礼 级m m 一序列总是将0 插入第一个长为n 一1 的0 游程中得到的；设s 为b 控 制a 生成的缩控序列下面我们就分别讨论序列s 的周期、线性复杂度、符号 6 分布及1 ，2 重量复杂度 引理2 2 1 缩控序列s 是周期序列，且2 3 ”为s 的一个周期 证明由第一节的注知：当b o ，1 ) 时，下标k 增加；当如 1 ，2 ) 时，下 标i 增加在n 级m m 一序列的一个周期段中，每个元素均出现了3 ”1 次因 此，当j = 3 “时，i = 七= 2 3 n - 1 ；当j = 2 - 3 “时，i = 七= 4 3 ”1 ；当j = 3 竹+ 1 时，i k 63 一- = 2 3 n 注意到此时下标i 与j 都到达了各自新一轮周期的 起始位置，从而缩控序列s 也就开始重复，这表明了s 是周期序列注意到此 时k = 2 3 n ，故v k 0 ，有s + 2 扩= s k 成立，故2 3 n 为s 的一个周期证毕 定理2 2 1 缩控序列s 的最小周期p ( s ) = 2 3 ”或扩 证明由引理2 2 i 知：p ( s ) 1 2 3 n 假设p ( s ) 是2 3 ”或3 “的真因子，则必 有p ( s ) 1 2 3 ”1 因为b 是t t 级m m 一序列，故每个扎维向量在b 的一个最小周期内出现且 仅出现一次我们不妨设吗= 蚺。- 一吩+ 。一l = 1 ，对某j 0 ，为b 中t t 维1 一 向量由于受b 的控制，从而。受b + r 的控制，r = 0 ，1 ，n 一1 在引 理2 2 1 的证明中知( 2 3 ”1 ，2 3 ”1 ，3 “) 是一个配对，因此b + 弘+ r 控制a i 朋舻一t r = 0 ，1 ，n 一1 而p ( b ) = 3 ”，故6 j 抄押= 幻扣( v j o ) 所以在s 的一个长为 2 3 ”1 的周期段内，它的元均是在b ：( 幻，+ 1 ，b + 。n 一- ) 的控制下生成的又 由于8 k j 竹= + r 8 针23 。一押= n 。m3 。一l 扪r = 0 ，1 ，扎一1 而2 3 ”1 又为s 的 一个周期，故有+ r = a i j + 2 3 n - 1 们r = 0 ，1 ，n 一1 注意到当礼 1 时，3 1 n ，因此2 3 1 + n 一1 + 1 3 n ，故集合 “，a i ，+ l ，+ 2 , 3 n - l + n - - 1 ) 出现在a 的一个最小周期内然而，两个相同的n 维 向量( a i j ，a q + 1 ，a i j + n - 1 ) 与( n 计2 铲- 1 ，+ 2 3 n - l + n - 1 ) 在a 的一个最小周期内 却出现了两次，这是个矛盾! 从而假设错误，p ( s ) = 2 3 ”或3 ”证毕： 下面我们给出缩控序列线性复杂度的估计： 定理2 2 2 缩控序列s 的线性复杂度l ( s ) 为： ( 1 ) 若s 2 召“( 1 ) 0 且s 2 3 ”( 2 ) 0 ，则l ( s ) = 2 3 ”； ( 2 ) 若s 23 ”( 1 ) = 0 或s 23 ”( 2 ) = 0 ，但不同时为0 ，则3 ”1 l ( s ) 2 3 ”一l ； ( 3 ) 若s 2 。3 “( 1 ) = 0 且s 2 。3 “( 2 ) = 0 ，贝03 “一1 l ( s ) 2 3 ”一2 7 证明因2 3 “为s 的一个周期，故f ( x ) = x 2 3 “一1 = ( z 2 1 ) 3 “= 0 + 1 ) 3 ”p 一1 ) 扩 为s 的一个特征多项式设厶( 茹) 为序列s 的极小多项式，则 ( 圳，( z ) ，因 此厶( z ) = 一1 ) 。0 + 1 ) b ，这里o 3 n ，6s3 n 另一方面：据引理1 3 2 知： 厶( z ) = ( 1 一x 2 3 “) 乃c d ( 伊铲( z ) ，1 一z 2 铲) ，这里9 c d ( ，) 表示最大公因式，故有： ( 1 ) 若s 2 。3 ”( 1 ) 0 且s 2 3 4 ( 2 ) 0 时， g c d ( s 2 铲( z ) ，1 一z 2 铲) = 1 ，故l ( x ) = 1 一z 2 3 “，l ( s ) = 2 3 ” ( 2 ) 若$ 2 3 - ( 1 ) = 0 或s 2 铲( 2 ) = 0 ，但不同时为0 时， g c d ( s 2 + 扩 ) ，1 一z 2 。3 忭) = ( 1 一z ) 。或( 1 + z ) 8 ，c 1 ，d 1 从而 厶( 茹) = ( 1 一z ) 3 n - - c ( 1 + z ) 3 n 或厶( z ) = ( 1 一z ) 3 “( 1 - f z ) 扩一8 所以l ( s ) 2 3 ”一l ； 假设l ( s ) 3 n 一1 ，贝0o 3 n 一1 ，b 3 n 一1 ，从而厶( z ) i ( z 一1 ) 3 1 ( z + 1 ) 扩，即 ，8 ( 刮( z 2 驴1 1 ) ，而这表明2 3 ”1 是s 的一个周期，与定理2 2 1 矛盾! 故假设 错误，即成立：3 ”1 3 ”一1 成立，即得3 “ l ( s ) 2 妒一2 证 毕 注意到序列的线性复杂度与周期的关系，有下面的推论： 推论2 2 1 当舻3 “( 1 ) 0 且s 2 伊( 2 ) 0 时，缩控序列s 的最小周期p ( s ) = 2 3 ” 8 证明由序列的线性复杂度不会超过它的周期可知 注利用推论2 2 1 ，我们可以这样判断缩控序列s 的最小周期：首先，如果 满足推论2 2 1 ，则p ( s ) = 2 3 “；如果推论2 2 1 的条件不满足，就依次比较8 与 8 i + 3 n ( o 3 “一1 ) ，直到对于某一下标二者不等，即可说明p ( s ) = 2 3 n ，否则 p ( s 1 = 3 n 根据这种新型的缩控序列的构造，我们可以给出缩控序列符号分布的一个 更加具体的范围： 定理2 2 3 设缩控序列s 的最小周期p ( s ) = 2 3 n ，则在s 的一个周期段 内，7 0 ，i i , i2 ，出现的次数为： 3 “一1sn 4 3 ”一1 证明令d = ( 3 - 1 ) 2 仅考虑缩控序列s 的一个周期，记s = ( 8 0 ，s 1 ，8 2 , 3 n - - i ) 由本节开始处的假设知，在序列b 的一个周期段内，n 维0 一向量总出现在前 d + i 个元内，设面= ( - 0 ，- 1 ，瓦。一，一。) 是从b 的前d + 1 个元素中删掉所有的0 元后得到的；记百= ( - b o ，一l ，_ 2s 一一，) 是从b 的一个最小周期内删除所有的0 元后得到的，由性质1 3 1 ( 5 ) 可知：百= ( 万，2 - 0 ) 现在将a 分成三部分：a = ( a o ，a 1 ，a 2 ) ，这里a 产( a 粥。- 1 ，a 。一t + 1 1 ，a i 3 n - l + 3 n - ，一1 ) ( i = 0 ，1 ，2 ，) 再用百去控制a 生成缩控序列君，因为君是从s 中除掉所有由b 中o ，对 应的添加的元素后得到的，故君是s 的一个子序列注意到此时百中无7 0 ，故 弓的增长与j 的增长一致，即巧= j ，0 从而 ( 面，2 _ ，面，2 面，一d ，2 一d ) 依次控制 ( a o ，a 1 ，a 2 ，a o ，a 1 ，a 2 ) 对控制对( 西，a ) ， = 0 ，1 ，2 我们可得到a 中的元素a j ，如果对应的弓= 1 ，( 0 j 3 ”1 1 ) ；而对( 2 西，a ) ，i = 0 ，1 ，2 ，我们可得到a 中的元素，如果对应的 9 瓦= 2 ( 0 j 3 一t 一1 ) 因此，序列琴中包含了a 0 = 0 ，1 ，2 ) 的全部元素即写 就包含了a 中的全部元素由于a 为n 级m m 一序列，g f ( 3 ) 中每个元均出现 妒- 1 次，故7 0 ，1 ，2 在s 中至少出现妒- 1 次，即n 3 ”1 另一方面，根据缩控序列的构造，我们知道当= 0 时，在a 中添加哪个元 依赖于j m o d 3 的取值故通过放缩，假设每种情况都取到最大，就可得到在s 的一个最小周期内，7o ，1 ，2 最多出现3 1 + 3 3 1 = 4 驴- 1 次，即n 3 ”一1 时，因为此时厶= ( 1 一z ) 。( 1 + z ) 4 ，( c 3 ”1 ，d 3 n - i ) ，所以： g c d ( f 。( 1 一x n ) ，a x + r s ( 1 一x n ) ) = 五 从而a ( s ) n 23 “证毕 在给定的条件下，我们还得到了缩控序列s 的2 重量复杂度首先看一个 引理： 引理2 3 1 设序列s t 的最小周期均为2 3 n ，记n = 2 扩，且在序列r 的一 个最小周期段内，w n ( t ) = 2 ，那么： ( 1 ) 若t ( z ) = + 2 x j ( i j ) ，则 嘲沪瑚唧m 垫i n 。d e g 莉矿万者导篙碧篇习丽 其中，0sksn 一1 9 ( x ) = z ( p 一1 ) 3 。+ + z 3 + 1 ，p 不能被3 整除 ( 2 ) 若t ( z ) = 2 一十z j ( i j ) ，贝0 唰p = 拶m 婵i n 。叫d e g 丽f 庐群簪舞舞告萨啊丽 其中，0 后n 一1 ，g ( x ) = z ( p 一1 ) 3 + - 4 - z 矿- 4 - 1 ，p 不能被3 整除 证明若t ( z ) = 一十2 x j ( i 歹) ，则 一， 、= r茹+ 2 x j 矿+ 2 x j t(z)=tn(z)z肼2￥万2浠k= 0 删 、w ， 不失一般性，设j i = 3 p ，其中3 不能整除p 于是 + 2 = ( 1 + 2 一) = ( 1 + 2 x ) 3 。 ( p 一1 ) 3 + + z 3 + 1 ) 眦t ：笔篙铲：蔫：凳 再代入岛( s ) 2 m ( 一i n ) ：2 d e gf , f , g c d ( h l , ，l r t + i t ) 即得结果 若t n ( x ) = 2 x + x j ( i 5 3 ”1 ，则w c 2 ( s ) = l ( s ) ( 3 ) 如果铲_ 1 l ( s ) 5 3 ”1 ，则w c 2 ( s ) = 2 3 ” 证明( 1 ) 在引理2 3 i ( i ) 的条件下，考虑到： g c d ( f 。( 1 一z ) 铲一3 ( 1 + z ) 铲，g ( x ) h + r s ( 1 一z ) 3 ”一3 ( 1 + 石) 3 “) = ( 1 一z ) 3 ”一3 ( 1 + z ) 3 ” 利用引理2 3 1 ( 1 ) 即得： w c 2 ( s ) = ( 3 ”一3 + 3 “+ l ( s ) ) 一( 3 “一3 。+ 3 ”) = l ( s ) ( 2 ) 首先注意到： m a x g c d ( f 。( 1 一x 2 3 n ) ，( 1 一z ) 3 g ( z ) h + t s ( 1 一x 2 3 n ) ) = m a x g c d ( f s ( 1 一z ) 3 n - - 3 k ( 1 - i - z ) 铲，z 口( z ) ，5 + ( 1 一z ) 3 n - 3 ( 1 + z ) 3 “) 其次，注意到对v0 2 3 ”这样我们得到 m a x g c d ( f 。( 1 一x 2 3 n ) ，( 1 一z ) 3 z 9 ) 厶+ r s ( 1 一z 2 3 ”) ) = 1 一z 2 3 “ 利用引理2 3 i ( i ) 得： 缈c t ( s ) = ( 2 3 “+ l ( s ) ) 一2 3 ”= l ( s ) ( 3 ) 与( 2 ) 的证明相同，此时v0 k n 一1 ，l ( s ) + 3 。 3 n 一时，在这些序列的每个周期段的任意对应位置上改变1 个或2 个比特，线性复杂度就增至2 3 n ，故此时序列的线性复杂度稳定性较差 1 3 第三章缩扩生成器 注意到缩控序列的生成可以分解为两步：首先基序列通过钟控生成器生成 钟控序列；其次控制序列与第一步得到的钟控序列再通过缩减生成器就得到了 缩控序列受此启发，我们将自扩生成器与缩减生成器组合构造了一种新型的 伪随机序列生成器一一缩扩生成器 3 1缩扩生成器的构造 下面我们先来介绍自扩生成器与缩减生成器 自扩生成器 设a = 是g f ( 3 ) 上的 级l f s r 序列，取定( i - ，i 2 ，如) ，1 i l i 。 i ks 几1 ，输出序列a 7 = n ：) 由以下规则决定：在时刻，如果 ( a t + i 1 ，a 蚪一，吼梳) 中有f 个0 ，0 1 k ，则输出a t ，再连续输出z 个0 ，这就是 一个自扩生成器，得到的序列就称为自扩序列 缩减生成器 设序列a = n t ，b = b j ) 是g f ( 3 ) 上任意两条l f s r 序列，输出序列 z = 钆 由以下规则决定：在时刻j ，如果= 0 或1 ，则输出当前的j ；如果 幻= 2 ，则放弃输出这就是一个缩减生成器，输出的序列称为由序列b 控制序 列a 得到的缩减序列 新的伪随机序列生成器一一缩扩生成器就是将上面两种生成器组合得到 的： 定义3 1 1 设序列a = 啦) ，b = 6 j ) 分别是g f ( 3 ) 上的7 t 级，? i t 级l f s r 序列，输出序列s = 8 k ) 是通过以下两步给出的：第一步，对序列a = o t ) ，取 定( i l ，i 2 ，i k ) ，1 i 1 2 i n 一1 ，在时刻t ，如果( a t “l ，a t 嘞，a t 艄) 中有l ( o z k ) 个0 ，则输出a t ，然后连续输出f 个0 ，这样就得到了a 的自扩序 列a 7 ；第二步，对于序列a 7 ，口，输出s = 乳) 由以下规则决定：在时刻t ，如果 仇= 0 或1 ，则输出相应的o ；否则放弃输出我们说这就是一个缩扩生成器( 简 1 4 记为s e - 生成器) ，输出序列s = s t ) 就称为缩扩序列( 简记为s e - 序列) 具体算法如下： i n p u t ：g f ( 3 ) 上的两条l f s r 序列a ，日 o u t p u t ：长为m 的s e - 序列 1 k = f = j = l _ o ； 。 2 w h i l e ( i t ) d o这里t 是远大于m 的一个数 ( a ) c o u n t ( a i “。，啦怕，a t “。) 中0 的个数，设为n ； ( b ) t h e n = a t ，a 川s = 0 ，a l 。= o ； ( e ) i 卜i + 1 ，l 卜f + n + 1 ，n 卜o ； 3 w h i l e ( k m ) d o ( a ) i f 吩2 ，t h e n 船= ；k k + 1 ，j j + l ； ( b ) e l s ej - 歹+ 1 ； 4 r e t u r n s 由此可见，最终得到的缩扩序列s 实质上就是序列b 控制序列a 的自扩 序列a 而得到的缩减序列 3 2缩扩序列的性质 下面我们先介绍两个重要的引理： 引理3 2 1 序列a 7 = 是基于n 级m 一序列a = h ) 的自扩序列，则 尸( a 7 ) = ( 3 ”一1 ) + k ( 2 一1 3 “一一1 ) 证明首先考虑集合 t ：t = 0 ，1 ，2 ，3 “一2 ，该集合中恰有侥3 ”。个t 使 ( a 州，a 州。，a t 帆) 中恰有1 个0 ，其中f - 0 ，1 ，k 一1 ；恰有3 一。一1 个t 使得 1 5 ( a t + qa t + i 2 ，o 。卅。) 全为0 因此，当序列a 走过3 ”一1 个比特时，a 的自扩序 列走过： k ( 3 ”一1 ) + f c l 3 ”一一k = ( 3 “一1 ) + k 2 k 一1 3 ”一。一k = ( 3 ”一1 ) + k ( 2 一1 3 ”一一1 ) l = 0 证毕 推论3 2 1 在自扩序列的定义中，如果我们令k = 1 ，则此时得到的礼级m 一 序列a 的自扩序列a 的最小周期p ( a ) = 4 3 ”1 2 注此时自扩生成器简化为：在时刻t ，考察( a t ，a t + i l ) ，如果a t “。= 0 ，则输出 a 。，再接着输出一个o ；否则只输出a t 例g f ( 3 ) 上的3 级m 一序列a ，极小多项式为f ( x ) = z 3 一z 2 2 ，在k = 1 且 l = 2 的情况下，得到的a 的自扩序列a 7 为： 输出 a=2012212020011 1021121010022 对于缩减序列，下面的性质是明显的： 性质3 2 1 设序列a ，b 是g f ( 3 ) 上任意两条l f s r 序列，最小周期分别为 瓦，死，序列z 为序列b 控制序列a 得到的缩减序列设b 在一个最小周期内 o ，与1 的个数和为r ，且设它们的下标依次为：0 j o j 1 矗一1 t b 一1 ， 则对v k 0 ，t 0 ，总有z k + = a i + m 证明由缩减序列的定义，输出序列z 的比特下标每增加r ，序列a 的比特 下标就增加证毕 引理3 2 2 设序列a = a i ) ，b = ( b ) 为g f ( 3 ) 上两个l f s r 序列，最小周 期分别为已，瓦，并且t b t a ，其中b 为n 级m 一序列记r 为b 在一个最小周 期内7 0 ，与w 1 的个数之和，则由序列口控制序列a 得到的缩减序列z 的最小 周期p ( z ) = r t a 甘g c d ( t a ，t b ) = 1 证明先看充分性( = ) ：已知( 瓦，t b ) = 1 1 6 首先，易于验证r 冗为缩减序列z 的一个周期：找出b 中0 ，与1 的位 置，设为0 i o i 1 i r - 1 ，则由性质3 2 1 ，v k20 有： + r l = “+ 死矗= 啦= 讯 故r 瓦为序列z 的一个周期 下面设p ( z ) = t ，即t r 死，不妨设t = t r + s ，t 0 ，0 8 r ，先来证明 s = o ： 反证：假设8 0 ，则0 8 r ，因为有下式成立： n 幻+ k t b = 勺+ 打= 句+ 打+ t = z j + k r + t r + s = 啦，扣+ f r 6 + k t b 由于阢，t b ) = 1 ，所以当k 取遍0 ，1 ，2 ，死一1 时，k t b m o d t 。亦取遍0 ，1 ，2 ，死一 1 ，故t 1 i j 扣+ t t b i j ，即i j 如4 - t t b 三i j ( m o d t a ) ，具体地： j = 0 如一l o = t o 疋一t t b j = 1i s + l i l = 7 2 1 死一t t j = kz 。s + 一i k = u k 瓦一t t b 其中u o ，u 1 ，“n 又因为0 s r ，故0 i ，卅一i j t b f i s + i i j i 卧k + i k j = l u j 一i 露兮= u k 故有： i 5 一i o = i s + 1 一t 1 = = t s + k 一缸= 下面取x 为左移位算子，即x b o ，b 。，5 2 ，) = 6 ，b z ， ，则由上式可知： x i o b 与x “b 中比特2 的位置是完全相同的，考虑到且为n 级m 一序列，由 性质1 3 1 的( 5 ) 可知i 。一i o 必为b 的一个周期，也即死k 一面，而i ，一i o t b ，从 而矛盾! 所以8 = 0 1 7 下面证明t = b ：由于t h 已辛t r r t a 兮t i t ，又由上面的证明过程知： 0 + t t b = i a m o d t 。) ，从而得t 。l r r b ，又m ，t b ) = 1 ，故瓦h 由此得t = 瓦，所以 下面看必要性的证明( ：争) ：已知p ( z ) = t = r 死 反证；假设，t b ) = d 1 ，则 篝： 其中s ，t n 对w 0 ，因为有下式成立： z j + s r 2 + s t b2 “白+ 死t 2a i j2 勺 故t s r 兮r 冗阿兮瓦i s ，而我们又知道8 是瓦得一个真因子，即s 1 ) 级m 一序列，且 它的自扩序列a 7 = a ：) 是在k = 1 ，i 1 = 2 的情况下得到的；序列b = 如) 总假 设为n 级m m 一序列这样在推论3 2 1 及引理3 2 2 的基础上，我们可以马上 得到s e 一序列s 的最小周期： 定理3 2 1 缩扩序列s 的最小周期p ( s ) = 8 3 2 n 一一4 3 ”1 证明因为a = a i 为n 级m 一序列，序列b = b ) 为n 级m m 一序列， 故p ( a ) = 3 ”一1 ，p ( b ) = 3 “，且序列b 在其一个最小周期内7 0 ，与1 的个数之和 r = 2 3 n 一1 据推论3 2 1 知：a 的自扩序列a 7 的最小周期p ( a 7 ) = 4 3 n - - l _ 2 ；据引理3 2 2 ， 首先p ( b ) = 3 “ 4 3 “一1 2 = p ( a 7 ) ，且g c d ( p ( a 7 ) ，p ( 日) ) = g c d ( 4 3 ”一1 2 ，3 ”) = 1 ， 故s e 一序列s 的最小周期 p ( s ) = r p ( a 7 ) = 2 3 ”1 ( 4 3 ”1 2 ) = 8 3 凯一4 3 ”1 证毕 1 8 设x 为左移算子，我们用( x t ( a ) ) 田= ( a i ，a i + d ，) 表示序列a 的t 平移 后的d 采样序列在序列b 的一个最小周期内，找出与1 的位置依次为 0 t o i 1 i r - 1 p ( b ) 一1 ，这里r 是b 的一个最小周期内0 ，与1 的个 数之和 引理3 2 3 设是a 的自扩序列，则( x 如( ) ) p ( 口) ) 与( ( a ，) ) ( 尸( 功) 平移等 价，其中j 可取任意整数 证明据推论3 2 1 知：p ( a ，) = 4 3 n - 1 _ 2 ；而p ( b ) = 3 ”，故g c d ( p ( a ) ，p ( b ) ) = 1 下面我们为了书写方便，记p ( a ，) = p ，p ( b ) = q ，即q p ，并且g c d ( p ，q ) = 1 从而存在整数u ，可，使得u p + v q = 1 成立，将此式两边分别乘以i o 与j 得到： 旧u p i o + v q i o = ，i 。 两式相减得 j i o v q ( j i o ) = u p ( j i o ) 寺j 三i o + k q ( m o d p ) 即 j 三i o + k p ( b ) ( m o d p ( a ，) ) 此即表明( x i o ( a ，) ) p ( 日) ) 与( x j ( a ，) ) p ( 口) ) 平移等价证毕 注由于上述j 可以取任意整数，特别地j = 0 时，( x 如( a ，) ) ( p ( 且) ) 与( a 7 ) 扣( b ) 平移等价 利用引理3 2 3 ，我们下面给出s e 一序列的符号分布定理： 定理3 2 2 在缩扩序列s 的一个最小周期内，1 与2 各出现r 3 ”1 次， ”o j ，至多出现2 r ( 3 n 一1 ) 次这里r 是序列b 一个最小周期内7 0 ，与1 的个 数之和 证明为了书写简便，记尸( ) = p ，p ( b ) = q ，则q 2 n 一3 证明只需证明a 中最长的0 游程的长度不小于2 n 一3 即可 事实上，在a 7 的连续4 3 1 2 个比特中，最长的0 游程出现两次，它出 现在当( a t ，a t + l ，a t 卸一1 ) = ( 1 ，0 ，0 ) 或( 2 ，0 ，0 ) 时对应的a 7 的0 游程中， 下面我们证明这个最长的0 游程的长度不小于2 n 3 ： 对应于a t = 1 ，a 7 的输出为1 个7 1 7 和1 个0