（信号与信息处理专业论文）流密码的设计与分析.pdf

摘要 摘要 本文的研究内容主要集中在两部分内容上，一是伪随机序列随机性评估指标 一线性复杂度的研究，得到了三个有用的结论；二是基于s 盒的流密码设计，提 出了一种高安全强度s 盒的设计方法，给出了一种基于s 盒的流密码算法，并给 出了各个设计阶段的实验结果。作者主要取得的研究成果如下： 1 研究了伪随机序列伪随机性评估指标一线性复杂度，主要讨论了g f ( 口) 上的 周期为= 印的二进制周期序列线性复杂度与k 错线性复杂度之间的关 系，得到了三个有用的结论，即工c 。忸”) 工如) ) = 1 ，g ( x ) 工g ) 是既约的，d e g ( g e ) ) 1 一x ”) ，只要求 出工g ) 的最小系数，就得到了序列的线性复杂度。( 1 一x ”) 在不同的有限域分解 的情况是不同的，所以才推导出这么众多的关于不同周期的二元序列的线性复杂 度的快速算法。 2 2 4l 卜错线。陛复杂度的快速算法 由于序列的线性复杂度存在着不稳定性，当改变周期序列的一个周期的一些 元素后，线性复杂度变化很大，因此线性复杂度作为度量序列的伪随机性指标是 不完善的，因此，引入了序列稳定性指标k 错线性复杂度。k 错线性复杂度是评 价一个序列线性复杂度稳定性好坏的一个很重要的指标，关于序列的k 错线性复 杂度快速算法有很多。这里只是介绍一下s t 锄p m 硼i n 快速算法，因为此算法是 北京工业大学工学硕士学位论文 其它算法的基础。 g f ( 2 ) 上周期为= 2 ”的序列，当改变一个周期的k 位比特后，能够得到 影) ( 2 1 4 ) 个周期为的序列。如果用b m 综合算法或者g m e s c h a l l 快速算法计算其线 x 、 性复杂度，要重复应用f 。j1 次，即使其中k ，不是很大，计算量也是很大 ，= o j 的。因此，引入了序列的k 一错线性复杂度快速算法的研究。下面介绍g ，( 2 ) 上周 期为= 2 ”序列的k - 错线性复杂度的快速算法，即s t m p m a n i n 算法。 序列的k - 错线性复杂度k 是指一个周期序列改变k 位比特后，得到 #ff、 f 。j1 个序列中最小的线性复杂度，k 错线性复杂度小于等于原始序列j ”的线 j ；0 j 性复杂度。在g 锄e s c h a n 算法中仅当6 0 时，线性复杂度增加，因此当6 o 时， 在允许改变的k 位元素内，改变原始序列5 “的最少的元素位数，使6 ：o ，从而 使线性复杂度减小。g a m e s c h a n 算法要用n 个步骤地序列折半加的运算，每 次的折半加运算得到一个矢量6 ，应注意在每一次使6 = o 时，要保证在此之前 的每一步骤的6 = 0 不被改变，并且每一次改变原始序列j “的元素位数加起来不 能大于k ，这样保证了改变序列最小的元素个数，而使线性复杂度降为最小，是 完全遵循者序列k 错线性复杂度的定义得。 在s t 蛐l p m a n i n 算法中，引入了代价( c o s t ) 的概念。 定义3 在g a m e s - c h a n 的算法中，当第，0 拜) 步6 o 时，改变当前序列j ” 的一位元素时，原始序列s “被改变的最少的元素个数定义为代价。 s 拄吼p m a n i n 算法中用t 是在每一步使6 = o 所需的总代价。 s t a r r l p m a n i n 算法： 初始值：= 2 “，s = 0 0 ，s - s ) c o s f ( f 】= ( 1 l l l f _ o ，1 ，一1 ，三k o 。 1 如果 1 ，那么 2 = ，2 ，三= o o ，_ ，j 一1 ) ，五= o ，j s 2 一1 ) ， 6 = 工+ 晨，丁= 以m i n ( c o sr 【f l c o s f 【f + d 一1 6 3 如果，s 七，男b 么七= 一r 1 ) f _ 1 ，2 ，一1 循环 女口果6 = 1 ，男b 么 如果c o s r 【f 】c o s f d + 卅，那么 ，= r 。，c o s 州= c o s f 【f + 卅一c o s f 【f 】 否则c o s f 【f 】= c o s f 【f 】一c o s f b + 】 否则c o s r 【f 】= c o s r 【f 】+ c o s f 【f + 州 2 ) s = 上，转到1 。 4 如果丁 七，那么三k = k + ，s = 6 c o s ， f 】= m i n ( c o s f d l c o s r f + b ，f = o ，l ，一1 。转至01 。 5 如果= 1 ，且= 1 ，c o sr 0 】 t ，那么三h = 三k + 1 最后得到的k 就是该序列的k 错线性复杂度。 s t 吼p m a r t i n 算法提出以后，在该算法的基础上，蔡勉老师川又推导出了周 期为n 2 的二元周期序列的k 错线性复杂度，周期为p ”的二元周期序列的k 一错 线性复杂度等等。线性复杂度和k 错线性复杂度的快速算法，都给本课题的研究 带来极大的启发，在快速算法的基础上，推导出了周期为p 。的二元周期序列的 线性复杂度与k 错线性复杂度之间的关系，也得出几个相关的结论。 2 3 周期为印9 周期序列线性复杂度与k 错线性复杂度的关系 线性复杂度和k _ 错线性复杂度是度量流密码安全性的重要指标，那么这二者 之间有没有什么关系呢? k a o r uk u r s o w a 【”l 讨论了周期为2 “的二元周期序列的 线性复杂度与k 错线性复杂度之间的关系，给出了使k 错线性复杂度小于线性 复杂度的一个最小的k 值，定义m i n e n w ( s ) 是满足三c * 峪“) l x ”) ，g g ) = s “g ) g c d p w g l l 一工”) 。这里， 1 8 一 g c d q 0 t 0 ) ) = 1 ，g g ) 六g ) 是既约的，d e g b o ) ) d e g 舨g ) ) ，o ) 为s 。的 极小多项式，d e g 阢g ) ) = 工为s 。的线性复杂度三，式子( 1 1 9 ) 是线性复杂度 的有理式形式1 1 9 1 。 所以可以证明 三c $ ”) = d e g b ) ) = d c g ( 1 一x “) 一d e g 毽c d p “b ) ，1 一x “) ) = 一d e g c d $ ”b 1 1 一) ) ( 2 2 0 ) 推理2 3 3 假定1 一x ”不可约分的分解为 g ) ，五g x ，z 0 ) ，这相当于 1 一x ”= g ) 五g ) ，g ) ，那么周期序列s 的生成函数可以表示如下： 荆= 等= 躺+ 湍+ 躺 弦z - ， 其中g c d 0 。g l ：g ) ) = 1 ，并且d e g b ，g ) ) ( 6 1 “1 + 6 2 村2 十- 十岛) 其中6 l ，6 ：以是既约多项式z g ) 的最小次数。 2 周期序歹| _ | 垒性复杂度的分布 从方程( 2 2 4 ) 、方程( 2 2 5 ) 和方程( 2 2 7 ) ，可以知道1 一x ”被不可约分的 完全分解，也就是说， l x ”= 厂0 ) 正g ) z 0 ) ，那么可以知道 1 一z ”= 一g ) 7 ”g ) ：，g ) 。假设： g c d 心“b l l x “) = z ng 坊zg ) z “g ) o ”l ，“2 ，“f p ” 从推理2 3 2 可以得到如下的定理。 定理2 3 2 假定序列s 是有限域g f 0 ) 上周期序列，周期是= 印”。序列s 的生成函数可以被表示为如下等式。 荆= 涔= 篇+ 篇+ 一+ 揣 其中，g c d k 。b ) z “g ) ) = 1 并且d e gg j 0 ) 雪崩测试变量曲线( ，黝c 0 ) 曲线) 如下： - 4 1 北京工业大学工学硕士学位论文 2 、 l 嘲m r ) n( ( 酽 c口 匹 。 ) ( (。() c 一 丈于4 的个封 有8 5 干，占 ? 而。 弼 1 而 贼 镕 l ”f 总数的6 6 。： i m f。i 5il 6 ) e 矾 i i j e _ _ 辑翳要囊 非线性复杂度为1 0 5 雪崩测试变量曲线( ，5 c 0 ) 曲线) 如下 0 0o om 1 i 。i ( )j “i ( 渊， 太于4 的个数一 个，占总数猷 ) j6 1 体 僦i ( 。耐。 删一删舢岫 。 过?1i f? r _ ) ( ：e p j 。 删8 4 2 图47s 雪崩测试变鞋【i 打线 4 、置换盒s 。 非线性复杂度为1 0 7 雪崩测试变量曲线( 删c g ) 曲线) 如下： 图4 8s 雪崩测试变昔曲线 5 、置换盒s 。 非线性复杂度为1 0 9 雪崩测试变量曲线( 用翻c 0 ) 曲线) 如下： 北京工业大学工学硕士学位论文 c(c)o 。 )(。 o d) 瓢 ) 霄 ) j【 奉于型 。 ： 稚；j 口 阿” 口口b b * 日e 。m 1 禳 je 1 ： i i 3 豫打 _4 # 雠。 # “ ，嚣。” 图4gs s 雪崩测试变鼍曲线 6 、置换盒s 。 非线性复杂度为1 0 4 雪崩测试变量曲线( 只蜘c g ) 曲线) 如下： 圈l l1 0s 。雪崩测试变颦曲线 7 、置换盒s ， 非线性复杂度为l 叭 雪崩测试变量曲线( 删c g ) 曲线) 如下： 罔41 1s ，雪崩测试变量曲线 8 、置换盒s 。 非线性复杂度为1 0 4 雪崩测试变量曲线( 冗鲥c b ) 曲线) 如下： 蚓41 2s 。雪崩测试变革曲线 4 4 最终s 盒的性能验证 经过进化方法和进化算法对上边产生的“s 盒进化池”进行若干轮进化，从 最终的“s 盒进化池中”选取一个s 盒，作为后边基于流密码算法中使用的s 盒。 该s 盒的内容如下： 6 2 2 1 9 ，2 3 6 ，2 1 4 ，2 1 9 ，3 5 ，6 5 ，“o ，1 0 2 ，1 2 8 ，2 0 9 ，1 8 0 6 3 ，1 3 4 ，1 2 5 ，2 2 ，2 1 7 ，4 9 ，4 9 5 ，8 l ，2 1 2 ，l8 8 ，1 4 4 ，1 8 l ，6 9 l | 9 ，4 ，1 1 3 ，2 1 9 ， 1 0 3 ，1 3 6 ，1 9 6 ，1 9 6 ，3 3 ，6 0 ，”3 ，1 8 1 ，4 6 ，1 1 2 ，2 1 4 ，1 7 7 ，1 6 0 ，8 8 ，1 1 7 ，1 4 ，3 ，3 2 ，2 4 0 ，2 2 8 ，9 5 1 7 9 ，1 5 3 ，4 1 ，2 1 2 ，2 29 ，1 5 8 ，2 3 0 ，2 4 4 ， 1 9 1 1 4 3 ，7 1 ，1 9 4 ，2 3 4 ，2 4 6 ，3 0 ，1 1 7 ，4 8 ，9 4 ，2 0 0 ，1 5 3 ，9 5 ，1 29 2 1 7 ，4 5 ，8 l ，2 5 i ，i l o ，9 0 ，2 8 ，1 3 8 ，8 l ，1 2 9 ，1 4 0 2 5 ，2 3 9 ，2 2 9 ，1 2 6 ，l 2 5 ，3 1 7 ，2 5 5 ，7 3 ，1 9 4 ，7 2 ，2 1 1 ，1 9 8 ，2 4 0 ，2 3 4 ，1 3 3 ，2 2 ，1 9 3 ，1 0 8 ，1 6 3 ，3 2 ，7 6 ，6 9 ，1 7 5 ，6 2 ，5 4 ，4 7 ，1 0 0 ，2 4 7 ，2 0 3 ，1 6 6 ，2 1 2 ，8 2 ，1 5 4 ，3 4 ，2 4 ，2 4 0 ，1 5 ，1 0 8 ，2 3 1 1 5 9 ，7 5 ，2 4 4 ，3 l ，1 4 1 ，1 4 2 。2 2 7 t 2 1 4 ，6 6 1 1 0 t 2 1 2 ，1 4 9 ，l9 2 0 9 ，1 4 2 ，5o ，97 1 7 5 。7 2 2 1 9 ，2 9 ，1 7 6 ，2 4 2 ，2 1 4 。1 9 9 ，1 4 3 ，2 4 7 。1 2 7 ，9 5 ，2 4 2 ，4 0 2 8 ，2 ，8 8 ，6 9 ，2 4 3 ，l l7 ，2 1 0 ，2 4 5 ，2 1 6 ，4o 5 6 1 3 0 。l5 l ，2 5 0 ，1 5 5 ，2 5 4 ，5 2 ，2 2 6 ，2 4 3 ，2 0 9 ，2 4 4 ，1 6 4 ，1 2 3 ，3 4 ，2 1 6 ，1 0 3 2 1 l ，6 8 ，1 2 9 ，1 8 8 ，5 4 ，9 ，5 2 ，2 3 8 ，1 5 6 ，1 9 l ，2 4 5 ，1 7 6 ，2 2 4 7 2 1 8 ，1 3 i ，1 2 4 j 0 1 1 5 3 ，8 4 。2 2 2 ，1 5 9 ，5 4 ，2 1 5 ，1 8 9 2 4 6 ，2 4 6 ，1 5 3 ，1 9 0 ，1 8 5 ，2 1 8 ，1 2 4 2 3 ，1 9 8 ，1 5 4 ，7 7 ，0 ，2 2 5 ，5 4 ，1 5 7 ，2 2 4 6 4 ，1 4 ，1 4 ，8 9 ，3 7 ，2 4 2 ，1 8 9 ，1 9 2 6 4 ，i5 5 ，3 5 3 4 ，1 3 ，5 6 4 5 北京工业大学工学硕士学位论文 6 4 ，l 2 0 ，2 4 8 ，2 ，2 ，2 3 7 2 2 0 ，5 ，2 2 5 ，6 2 ，1 5 6 ，2 l i 6 8 1 3 ，5 6 ，1 9 3 ，1 5 6 ，6 7 ，1 6 ，1 1 8 下边是对该s 盒进行密码特性分析，主要集中在两个方面的分析：非线性度 和严格雪崩特性。在文中【3 8 】中已经证明，s 盒具有高的非线性度和良好的严格雪 崩特性，就可以认为s 盒是密码特性强的置换盒。正是基于这个证明，本文只是 对s 盒的这两个方面进行分析，分析结果如下： 最终s 盒的非线性度是1 1 2 最终s 盒雪崩测试变量曲线( r 魏c 曲线) 如下： () 。 r( 。 飘 ) | ) ，太于4 的数 ) ) () ( 01( 赢 )o i 0 5 个，占 伍iee 蕊 8 20 3 0 - j j 、： 漱晓；i 黼喜；要1 蒌巍j 嚣甍i i i 鬻鞲= 姗疆薹薯罄踊瓤登戮l 氍嚣m 溅_ 叠麟i 。 本章是基于s 盒流密码算法设计中很重要的一环，置换盒安全强度如何，直 接决定了算法的安全强度。主要完成高安全强度置换盒的设计与分析，采用进化 方法和进化算法对初始“s 盒进化池”进行密码特性进化，从而产生出需要的s 盒。引进了生物学中的“进化论”思想，对产生的“s 盒池”中的s 盒进行“进 化”，从而使其密码特性更加强壮，这也是本算法设计的一个创新点。但是由于 进化方法中有些步骤是随机性的，所以对进化策略的评价是一个难点，而且进化 的方向很难控制，这也是需要迸一步研究的问题。 一4 6 第5 章基于s 盒的流密码算法设计 第5 章基于s 盒的流密码算法设计 本章主要内容是完成基于s 盒的流密码算法设计。最常见的流密码密钥流生 成器是非线性组合生成器或非线性滤波生成器，安全性取决于非线性组合函数或 非线性滤波函数的布尔函数特性，对布尔函数的研究也是密码学研究的重要部 分。基于s 盒的流密码密钥流生成器的研究是流密码算法设计的一个新研究点， s 盒密码特性的好坏直接关系到算法的安全强度。s 盒的密码特性好可以完全隐 蔽掉原始密钥的信息，使破译者破译密码的强度大大增加，所以s 盒是基于s 盒 流密码算法的核心。本章主要给出基于s 盒流密码算法的设计原理以及算法各个 部分的具体细节，具体包括算法s 盒的初始化、算法的工作过程等。 5 1 基于s 盒的流密码算法设计原理 算法的设计原理主要就是密钥流生成器的设计原理，密钥流生成器的设计主 要是基于s 盒来完成的，图5 1 给出了算法的设计原理逻辑图。 产生的密钥 图5 1 算法的设计原理逻辑图 图5 一l 算法的设计原理逻辑图 在本算法中，主要包括：计数器l 、计数器2 、密钥初始化s 盒、高安全强 北京工业大学工学硬士学位论文 度s 盒以及一个非线性运算部件。其中，计数器的作用是控制密钥初始化s 盒， 从密钥初始化s 盒中随机的选取数值，作为非线性部件的输入，它们保证密钥初 始化s 盒在使用中是随时改变的。关于密钥初始化s 盒会在后边的初始化过程中 具体讲述，这里不详细介绍。非线性部件的主要作用是在输入的作用下，产生一 个输出y ，该输出y 作为置换盒s 的下标，即作为置换盒的寻址地址，从而从置 换盒中最终选取加密用到的密钥流。 此算法设计原理简单，用到的运算也非常少，计算复杂度相对很低，可以适 应于高速、大容量的网路环境中，而不至于造成瓶颈。算法的安全性主要是通过 s 盒来保证，它可以完全隐蔽掉原始密钥的信息，从而使破译工作变得复杂。 5 2s 盒的初始化 算法的初始化过程主要是放在密钥初始化s 盒上，它的主要作用魁和嚣换盒 一起，在非线性部件的作用下，最终完成加密密钥流的选取。密钥初始化s 盒的 初始化快与慢直接决定了算法的工作速度，该初始化过程可以帮助打乱原始密钥 的信息。 算法中，用一个8 8 的s 盒作为密钥初始化s 盒。实际上，它就是一个大小 为2 5 6 的b y t e 数组。该算法中用到的密钥可以设定为6 4 位、1 2 8 位和2 5 6 位。 具体密钥填充密钥初始化s 盒的过程可以分为两步：一先用初始密钥依次填充s 盒，具体过程如图5 2 所示。二是对填充完的s 盒进行随机的扰乱，以便于隐藏 初始密钥的信息。 图5 2 初始密钥填充逻辑示意图 用初始密钥填充完密钥初始化s 盒后，要对该s 盒进行扰乱，从而有效地隐 藏初始密钥的信息。扰乱的过程直接影响了算法初始化的快慢，所以这里的扰乱 力求快速、简洁，从而保证算法初始化时间的最小化。具体扰乱过程如下：假定 密钥初始化s 盒是s 【2 5 6 】_ ，七l ，七：， ，置换盒s ： 2 5 6 】= 慨，s ，s ：。 。 那么 一4 8 第5 章基于s 盒的流密码算法设计 对于f = 0 到2 5 5 ，= ( ，+ s 。+ t 。) m o d 2 8 对于密钥初始化s 盒而言 交换和七 以上就是密钥初始化s 盒的初始化过程，后边的扰乱过程是基于r c 一4 算法 设计的。特点是运算形式简单，算法速度快，便于实现。 5 3 算法加密过程 算法分为两大部分：一是计数器对密钥初始化s 盒的操作；二是非线性部分 的运算操作以及对高安全强度s 盒的选取。 计数器可以用f 和_ 来表示，初始值为0 。算法分以下三部来阐述： 计数器对密钥初始化s 盒的操作。 操作可以保证密钥初始化s 盒在算法工作过程中，是时刻随机改变的。具体 过程如下： f - o + 1 ) m o d 2 8 ，= ( ，+ 七。) m c h d 2 8 交换i 和七， 非线性运算操作 ，= 眠+ 七，) m 。d 2 8 + 仁，) m 。d 2 8 ) m 。d 2 8 f 是由密钥初始化s 盒作为输入产生的，是一个8 比特的数值。它作为从高 安全强度s 盒中选取数值的下标。 高安全强度s 盒的选取操作 操作是在上一步产生的f 控制下完成的，是算法的最后一步，它的输出是最 终要加密的密钥流序列。具体选取过程可以如图5 3 所示，高安全强度s 盒 排列成1 6 1 6 的矩阵。 北京工业大学工学硕士学位论文 图5 - 3 选取过程逻辑图 从上图可以看出。非线性输出的8 b i t 数值分为两大部分，前4 比特用来决定 矩阵的列坐标，后4 比特用来决定矩阵的行坐标。从选取的过程可以看出， 输入和输出是完全正交的，即输入作为输出的一个定址。 5 4 本章小结 本章是在第四章的基础上，完成基于s 盒的流密码算法设计。主要包括三大 部分内容：一是阐述算法的设计原理，算法主要是依据s 盒完成密钥流生成器的 设计其结构简单，便于实现。二是介绍算法s 盒的初始化，算法的初始化直接 影响算法的工作速度，是算法实现需要考虑的一环节。三是算法的加密过程，由 于流密码的加密特点，密钥流需要持续产生一段时间，所以密钥流生成器的工作 持续性需要考虑。 一5 0 结论 结论 密码学与信息安全技术是信息科学与信息技术的重要分支，各种信息安全协 议大都植根于“好”的密码算法。由于密码学的特殊性，在密码学的应用上不能 借用国外现有的密码体制( r c 4 、d e s 、i d e a 、a e s 等) ，而应当立足于自行研 究和设计。 流密码作为密码学的一个重要分支，近年来研究取得了飞速的发展。关于流 密码的研究主要集中在两个方面：流密码算法的设计和流密码算法的评估指标。 自从线性复杂度成为评价序列伪随机性的一个重要评估指标后，流密码算法评估 指标的研究取得了飞速的发展。本论文的开始部分也对序列的线性复杂度和k 错线性复杂度进行了研究和分析，主要讨论了周期为印”的二元周期序列的线性 复杂度和k 错线性复杂度之间的关系，并得到了三个重要的结论。 接下来分析了分组密码中非线性部件s 盒的密码特性，给出了一种利用加密 快速生成s 盒的方法。此算法主要采用了i d e a 中的m a 结构，算法结构简单， 便于软硬件实现。在s 盒生成算法的基础上，引用生物学中的“进化论”思想， 提出对初始“s 盒进化池”进行最优化选择的一个进化方法，并给出了具体的进 化方法和进化算法，实验结果表明，通过对“s 盒进化池”进行密码特性进化后， “s 盒进化池”中的s 盒密码特性大大变好。此结果表明，利用进化方法对“s 盒进化池”进行密码特性进化，是一种产生高安全强度s 盒的可行方法。 最后利用生成的高安全强度s 盒，完成了基于s 盒的流密码算法的设计。该 算法利用密钥初始化s 盒和非线性运算，产生输出的定位地址，从而从高安全强 度s 盒中选取最终的加密密钥。该算法设计思想简单，初始化速度快，便于软硬 件实现，可以应用到大的、高速的网络环境中。 北京工业大学工学硕士学位论文 参考文献 l 孙宏，杨义先，无线局域网协议8 0 2 1 l 安全性分析电子学报，2 0 0 3 年7 月， 第7 期 2c h i c h u n ，y u j e nc h e n ，s t r e a mc i p h e rf o rg s mn e t w o r k si e e ei n t e r n a t i o n a l c o n f e r e n c eo n ，v o l u m e ：1 1 8 2 2j u n e2 0 0 ，8 0 一8 4v 0 1 1 3 丁存生，肖国镇，流密码学及其应用国防工业出版社，1 9 9 4 年9 月 4 蔡勉流密码及其稳定性测量指标的算法研究西安电子科技大学博士生论 文，1 0 7 0 1 一t n o l 8 4 5l i ng a n ，s t a ns i m m o n s ，s t a f f o r dt a v a r e s ，an e wf a m l i yo fs t r e a mc i p h e r b a s e do nc a s c a d e ds m a l ls b o x e s i e e ee l e c t r i c a l a n dc o m d u t e r e n g i n e e r i n g ，2 0 0 1 v o l u m e ：1 ，1 3 一1 6m a y2 0 0 1 6h o n g s a i n0 0 i ，h i g h s p e e ds t r ea i t lc i p h e r a d v a n c e di n f o r m a t i o nn e t l 】r o r k i n g a n d a p p l i c a t i o n ，2 0 0 4 ，a i n a2 0 0 4 ，1 8 “ i n t e r n a t i o n a lc o n f e r e n c e o n ，v o l u m e ：2 ，2 0 0 4 p a g e s ：3 9 4 2 7 g a i i l e sra ，c h a nah af a s ta l g o r i t h mf o rd e t e r m i n gt h ec o m p l e x i t y p s e u d o r a n d o ms e q u e n c ew i t hp e r i o d2 “i e e et r a n s i nt h e o r y，j a n 1 9 8 3 ，v 0 1 i t 一2 9 ，p p 1 4 4 一1 4 6 8g u o z h e nx i a o ，s h i m i nw e i ，af a s ta l g o r i t h mf o rd e t e r m i n i n gt h el i n e a r c o m p l e x i t y o fa s e q u e n c ew i t hp e r i o dp “ o v e r g f ( q ) i n f o r r 【l a t i o n t h e o r y ，i e e e t r a n s a c t i o n s o n ，v o l u m e ：4 6 ，i s s u e ：6 ，s e p t 2 0 0 0 p a g e s ：2 2 0 3 2 2 0 6 9m a s s e yjl ，s e r o n e ks l i n e a rc o m p l e x i t yo fp e r i o d i cs e q u e n c e s ：ag e n e r a l t h e o r ya d v a n c e si nc r y p t o l o g y c r y p t o 9 6 1 9 9 6 3 5 8 3 7 l l os t a m pa n dm a r t i ncf a na l g o r i t h i i 】f o rk e r r o rl i n e a rc o m p l e x i t yo f b i n a r ys e q u e n c e s w i t hp e r i o d2 “i e e e t r a n s i n f r m t h e o r y ，j u l 1 9 9 3 ，v 0 1 3 9 ，p p 1 3 9 8 1 4 0 l 一5 2 参考文献 1 1 蔡勉，王宏，周期为n = n 2 “v 的序列线性复杂度的快速算法电子与信息学 报，2 0 0 2 0 2 4 ( 0 0 3 ) 一3 7 0 3 7 6 1 2 蔡勉，自国强，序列k 一错线性复杂度算法通信学报2 0 0 0 0 2 l ( 0 0 1 ) 6 4 6 7 1 3k u r o s a d ak ，s a t of 等，ar e l a t i o n s h i pb e t w e e n1i n e a rc o m p l e x it ya n d k e r r o r1 i n e a r c o i p l e x i t y i n f o r m a t i o n t h e o r y ，i e e et r a n s a c t i o n s 0 n ，v o l u m e ：4 6 ，i s s u e ：2 ，m a r c h2 0 0 0p a g e s ：6 9 4 6 9 8 1 4m i o gp a r k ，y e o n h e ec h o i ，m o o n s e o gj u n ，m o d i f i e da 5s t r e a mc i p h e ru s i n g s b o x e s a d v a n c e dc o 胁u n i c a t i o nt e c h n 0 1 0 9 y ，2 0 0 4 ，t h e6 ni n t e r n a t i o n a l c o n f e r e n c eo n v 0 1 u m e ：2 0 0 4 1 5 王育民，刘建伟，通信网的安全理论与技术西安电子科技大学出版社，1 9 9 9 年4 月第一版 1 6b e r l e k a m per ，a 1 9 e b r i cc o d i n gt h e o r y n e wy o r k ：m c g r a w h i l l ，1 9 6 8 1 7 r u e p p e l r a ， g o o d s t r e a mc i p h e r sa r eh a r dt o d e s i g n s e c u r i t y t e c h n 0 1 0 9 y ，1 9 8 9 p r o c e e d i n g ， 1 9 8 9i n t e r n a t i o n a lc a r n a h a nc o n f e r e n c e o n ，o c t 3 5 ，1 9 8 9p a g e s ：1 6 3 1 7 4 1 8 肖国镇，非线性生成器相关分析研究的频谱方法西北电讯工程学院，1 9 8 4 年1 0 月 1 9 赵方明，田芳，林洪涛，i e e e 无线局域网的一种新的加密机制山东大学学 报( 工学版) ，2 0 0 3 年4 月，第3 3 卷第2 期 2 0 魏仕民，肖国镇，陈钟，确定周期为2 ”p ”二元序列线性复杂度的快速算法 中国科学，2 0 0 2 年6 月，第3 2 卷第3 期 2 l 冯登国，肖国镇序列周期稳定性信度量指标电子学报，1 9 9 4 年， v b l 2 2 n o i p 8 6 9 0 2 2t a k a y a s u k a i d a ，a na l g o r i t h mf o rt h e 七一e r r o rl i r l e a r c o m p l e x i 妙o f s e q u e n c e s o v e r g f 0 “) 谢t hp e r i o d p “，pap r i m e i n f o n n a t i o na 1 1 d c o m p u t a t i o n1 5 1 ，1 3 4 1 4 7 ( 1 9 9 9 ) a r t i c l ei di n c o 1 9 9 8 - 2 7 6 8 2 3m a s s e yjl s h if t r e g is t e rs y n t h e s isa n db c h d e c o d i n g i e e e t r a n s i t ，j a n 1 9 6 9 1 2 2 1 2 7 - 5 3 北京工业大学工学碗士学位论文 2 4 白恩健，张斌，二元周期序列的线性复杂度与k 一错线性复杂度的关系电子与 信息学报，2 0 0 2 1 2 ，v 0 1 2 4n o 1 2 2 5 p a u ldk u n d a r e w i c h d ，s t e v eje ，ac p l d - b a s e dr c _ 4c r a ck i n gs y s t e m p r o c e e d i n go f l e1 9 9 9i e e ec a i l a d i a i lc o r 庇r c l l c eo ne 1 e c 廿i c a l a 1 1 dc o m p u t 血g e n g i n e e r i n gs h a wc o n f e r e n c ec e m e r ，e d m o m i o n ，舢b e r t a ，c a l l a d am a y9 一1 21 9 9 9 2 5p p r a s i t h s a n g a r e ， p k r i s h n a m u r t h y ，a n a l y s i so fe n e r g yc o n s u m p t i o no f r c 4a n da e sa l g o r i t h m si n 坩i e r l e s sl a n s i e e eo 一7 8 0 3 82 0 0 3 2 7 叶存云，杨晓元，有限序列线性复杂度和的研究数学的实践与认识，1 9 9 2 ， 56 4 2 8mzw a n g ，l i n e a rc o m p l e x i t yp r o f i l e sa n dj u m pc o m p l e x i t y i n f o r m a t i o n p r o c e s s i n gl e t t e r s6 l( 1 9 9 7 ) 1 6 5 1 6 8 2 8c h a o p i n gx i n g ，k w o ky a nl a i i l ，s e q u e n c ew i t ha l m o s tp e r f e c tl i n e a r c o i n p l e x i t yp r o f i l e sa n dc u r v e so v e rf i n i t ef i e l d s i e e et r a n s a c t i o n so n i n f o r m a t i o nt h e o r y ，v o l ，4 5 ，n 0 4 ，m y1 9 9 9 h a r a l dn i e d e r r e i t e r ，p e r i o d i cs e q u e n c e sw i m l a 培ek e n d rl i n e a rc o m p l e x i 吼i e e e t r a n s a c t i o n so ni n f o m a t i o nt h e o 吼v o l 4 9 ，n o 2 ，f e b n l a r y2 0 0 3 3 0h a r a l dn i e d e r r e i t e r ，p e r i o d i cs e q u e n c e sw i t hl a r g ek e r r o rl i n e a r c o m p l e x i t y 工e e e t r a n s a c t i o n s0 ni n f o r m a t i o n t h e o r y ，v 0 1 4 9 ，n d 2