（信号与信息处理专业论文）基于k错线性复杂度的周期序列计数与刻划研究.pdf

杭州电子科技大学硕士学位论文 摘要 密码学的理论与技术逐渐成为信息科学与技术中的一个非常重要的研究领域。可以说， 社会的信息化程度越高，商业越发达，信息安全就显得越来越重要，密码学的应用就越来越 广泛。自古以来，密码体制的强度问题是密码设计者和分析者研究的核心内容。序列密码是 现代密码学中的一个重要组成部分，伪随机性是序列密码中的焦点问题。线性复杂度是衡量 密钥流序列密码强度的一个重要指标，但是线性复杂度高的序列不一定是安全的密钥流序列， 因而s t a m p 和m a r t i n 提出了舡错线性复杂度衡量指标。设计具有大的线性复杂度和舡错线性 复杂度的序列是密码学和通信中的热点问题。n i e d e r r e i t e r 首次发现了而上许多满足这个要 求的周期序列，提出稳定肛错线性复杂度的概念以便研究具有最大肛错线性复杂度的周期序 列。 本文主要基于g a m e s c h a r t 算法研究了周期序列的线性复杂度、舡错线性复杂度、给定 缸错线性复杂度的序列个数等问题。主要工作和创新点如下： 1 通过研究周期为2 ”的二元序列线性复杂度，提出使用方体理论构造稳定肛错线性复杂 度序列的方法，给出该方法的许多实例。证明了周期为n = 2 厅的二元序列可以分解为若干互不 相交的方体，从而给出一个研究肛错线性复杂度的新方法。 2 通过研究周期为2 疗的二元序列线性复杂度，提出将肛错线性复杂度的计算转化为求 h a m m i n g 重量最小的错误序列。基于g a m e s c h a n 算法，讨论了线性复杂度为2 n _ 1 的2 露周期二 元序列的6 错线性复杂度分布情况。在大多数情况下，给出了对应6 错线性复杂度序列的计 数公式。同时通过计算机编程分别给出了n = 4 和n = 5 时，6 一错线性复杂度为l ( r ，c ) 的个数。基于 上述结论，指正了王军硕士论文中的一个重要错误。 3 基于g a m e s c h a n 算法，讨论了线性复杂度为2 - m 的2 玎一周期二元序列的缸错线性复杂度 分布情况。当( 所，玲= ( 2 ，2 ) ，( 3 ，4 ) ，( 4 ，2 ) ，( 5 ，4 ) ，( 6 ，4 ) ，( 7 ，8 ) ，( 8 ，2 ) 时，分别给出了对应缸错线性复杂度序 列的计数公式。对于一般的m ，也可以通过该方法给出对应缸错线性复杂度序列的计数公式。 关键词：流密码；周期序列；线性复杂度；肛错线性复杂度；缸错线性复杂度分布 杭州电子科技大学硕士学位论文 a b s t r a c t t h e t h e o r ya n dt e c h n o l o g yo fc r y p t o g r a p h yi sb e c o m i n go n eo ft h em o s ti m p o r t a n tr e s e a r c h f i e l d so fi n f o r m a t i o ns c i e n c ea n dt e c h n o l o g y i ts h o u l db es a i dt h a t ，t h eh i g h e rt h ed e g r e eo f i n f o r m a t i o ns o c i e t y , t h em o r ed e v e l o p e db u s i n e s s ，i n f o r m a t i o ns e c u r i t yb e c o m e sm o r ei m p o r t a n t ， a n dt h e r e a r em o r ee x t e n s i v ec r y p t o g r a p h ya p p l i c a t i o n s t h ei n t e n s i t yo fc i p h e rs y s t e mh a sb e e n s t u d i e db y c i p h e rd e s i g n e ra n da n a l y z e r sa n d h a sb e c o m et h ek e yp r o b l e ms i n c ec i p h e rt h e o r ya n d t e c h n o l o g ye m e r g e d s t r e a mc i p h e ri so n eo ft h ei m p o r t a n tb r a n c h e so fm o d e r nc r y p t o g r a p h y , m o r e a n dm o r ew o r k sf o c u so nh o wt oe v a l u a t ep s e u d o r a n d o ms e q u e n c e s 1 1 1 el i n e a rc o m p l e x i t yi sa n i m p o r t a n tm e a s u r e m e n to fp s e u d o r a n d o ms e q u e n c e s h o w e v e r , as e q u e n c ew i t hl a r g el i n e a r c o m p l e x i t yi sn o tan e c e s s a r i l ys a f es t r e a mc i p h e r , t h u st h es a f em e a s u r e m e n to fk - e r r o rl i n e a r c o m p l e x i t yw a sp r o p o s e db ys t a m pa n dm a r t i n d e s i g n i n gas e q u e n c ew i t hh i g hl i n e a rc o m p l e x i t y a n dk - e r r o rl i n e a rc o m p l e x i t yi sah o tt o p i ci nc r y p t o g r a p h ya n dc o m m u n i c a t i o n s n i e d e r r e i t e rf i r s t n o t i c e dm a n yp e r i o d i cs e q u e n c e sw i t hh i 【g hk - e r r o rl i n e a rc o m p l e x i t yo v e rt h ef m i t ef i e l df q ，a n d p r o p o s e dt h ec o n c e p to fs t a b l ek - e r r o rl i n e a rc o m p l e x i t yt os t u d ys e q u e n c e sw i t hh i g l lk - e r r o rl i n e a r c o m p l e x i t y b a s e do ng a m e s - c h a r ta l g o r i t h m ，t h i sp a p e rm a i n l ys t u d i e sl i n e a rc o m p l e x i t y 、k - e r r o rl i n e a r c o m p l e x i t y 、t h en u m b e ro fs e q u e n c e s 、析t l lg i v e nk - e r r o rl i n e a rc o m p l e x i t ya n ds oo n t h em a i n w o r ka n di n n o v a t i o n sa r ea sf o l l o w s ： 1 b ys t u d y i n gl i n e a rc o m p l e x i t yo fb i n a r ys e q u e n c e sw i t hp e r i o d2 “，t h em e t h o du s i n gc u b e t h e o r yt oc o n s t r u c ts e q u e n c e sw i t hm a x i m u ms t a b l ek - e r r o rl i n e a rc o m p l e x i t yi sp r e s e n t e d ，a n d m a n ye x a m p l e sa r eg i v e nt oi l l u s t r a t et h ea p p r o a c h i ti sp r o v e dt h a tab i n a r ys e q u e n c ew i t hp e r i o d n = 2 甩c a nb ed e c o m p o s e di n t os o m ed i s j o i n tc u b e s 1 1 1 ec u b et h e o r yi san e wd i r e c t i o nf o rs t u d y i n g k - e r r o rl i n e a rc o m p l e x i t y 2 b ys t u d y i n gl i n e a rc o m p l e x i t yo fb i n a r ys e q u e n c e sw i mp e r i o d2 ”，i ti sp r o p o s e dt h a tt h e c o m p u t a t i o no fk - e r r o rl i n e a rc o m p l e x i t ys h o u l db ec o n v e r t e dt of i n d i n ge r r o rs e q u e n c e sw i t h m i n i m a lh a m m i n gw e i g h t b a s e do i lg a m e s c h a na l g o r i t h m ，6 - e r r o rl i n e a rc o m p l e x i t yd i s t r i b u t i o n o f2 一- p e r i o d i cb i n a r ys e q u e n c e sw i t hl i n e a rc o m p l e x i t y 少一li sd i s c u s s e d i nm o s tc a s e s ，t h ec o m p l e t e c o u n t i n gf u n c t i o n so nt h e6 - e r r o rl i n e a rc o m p l e x i t yo f2 n - p e r i o d i cb i n a r ys e q u e n c e sa r ep r e s e n t e d m e a n w h i l e ，t h ec o u n t i n gf u n c t i o n sa r ev e r i f i e db yc o m p u t e rp r o g r a m m i n gf o rn = 4a n dn = 5 a sa c o n s e q u e n c eo f t h e s er e s u l t s ，a ni m p o r t a n te r r o ro ft h et h e s i so fw a n gj u ni sc o r r e c t e d 3 b yg a m e s - c h a na l g o r i t h m ，k - e r r o rl i n e a rc o m p l e x i t yd i s t r i b u t i o no f2 ”- p e r i o d i cb i n a r y s e q u e n c e sw i t h l i n e a r c o m p l e x i t y 岁- m a r e d i s c u s s e d w h 胁伽，砂= ( 2 ，2 ) ，( 3 ，4 ) ，( 4 ，2 ) ，( 5 4 ) ， 杭州电子科技大学硕士学位论文 ( 6 ，4 ) ，( 7 ，8 ) ，( 8 ，2 ) ，t h ec o m p l e t ec o u n t i n gf u n c t i o n so nt h ek - e r r o rl i n e a rc o m p l e x i t ya r ep r e s e n t e d r e s p e c t i v e l y f o rg e n e r a lm ，t h ec o m p l e t ec o u n t i n gf u n c t i o n so nt h ek - e r r o rl i n e a rc o m p l e x i t yo f 2 - p e r i o d i cb i n a r ys e q u e n c e sw i t hl i n e a rc o m p l e x i t y2 - mc a na l s ob eo b t a i n e du s i n gas i m i l a r a p p r o a c h k e y w o r d s ：s t r e a mc i p h e r , p e r i o d i cs e q u e n c e s ：l i n e a rc o m p l e x i t y , k - e r r o rl i n e a rc o m p l e x i t y ；k - e r r o r l i n e a rc o m p l e x i t yd i s t r i b u t i o n 1 1 1 杭州电子科技大学硕士学位论文 第1 章绪论 1 1 引言 密码学是一门很古老的学科，大概人类社会出现战争的同时便产生了密码，但那时并没 有系统的理论基础。从2 0 世纪到现在，很多事件都和密码学有关。1 9 2 9 年，美国国务卿暂 停了密码分析行动，这个错误决定致使美国在日本偷袭珍珠港事件中付出了惨重的代价，之 后不久，又重新启动了密码分析计划。二战中盟军的密码分析成绩显著，这是密码分析的“黄 金时期 。太平洋战役中，美国密码工作者破译了日本军的密码，得到了重要的信息，使中途 岛海战取得了胜利；在欧洲，破译了e n i g m a 密码后，盟军也得到了帮助。二战后，密码发展 到了科学研究领域【1 刀。1 9 4 9 年，香农发表了保密系统的信息理论【3 】后，单钥密码体制和 密码学都有了理论基础，密码学从此形成了- i - j 科学。但从1 9 4 9 年到1 9 7 5 年，密码学的研 究进展比较慢。直到1 9 7 6 年，密码学的新方向【4 】的发表，公钥密码体制产生，密码学新 的一页开启，有了新的理论来解决信息安全，从而开创了密码学新的时代。此外，在1 9 7 7 年， 美国数据加密标准( d e s ) 被美国国家标准局正式公布并实施。由此现代密码学诞生。从此， 密码学在理论上和应用上都得到了飞速的进展，渐渐形成了一门综合学科。信息化时代的到 来使网络和通信技术发展迅猛，随时都有海量信息进行传输或交换，密码学知识能保证每个 人的敏感信息不被泄露或篡改，于是人们关注点集中于信息安全保密，因此密码学进展迅速。 而当今，密码学的应用已广泛渗透在各行各业，甚至是日常生活中。 1 2 线性复杂度的研究背景、意义和现状 密码学通过加密变换，把可读的文件转变为不能理解的乱码，对信息数据起了保护作用。 随着密码理论、技术的产生，密码设计者和分析者就主要探索密码体制强度问题。密码体制 是一个密码系统的简称，由五部分组成，即：1 明文空间；2 密文空间；3 密钥空间；4 加密 算法；5 。解密算法。 目前，流行加密技术的特征都是算法复杂性理论，基础是密码学，主要分为2 类：对称 密码学、非对称密码学。而对称密码又可分为序列密码和分组密码。序列密码是保密通信中 的一个重要的密码体制，在实际应用当中具有一定的优势，尤其在机密单位优势比价明显。 香农在1 9 4 9 年时已严格证明：如果有一个真随机密钥流序列，那么其对应的流密码是一 定安全的【5 】。但是，完全重复地产生相同的随机序列是不可能的，只能用伪随机序列代替随 机序列，流密码体制的强度完全依赖于密钥流产生器所生成的伪随机序列的随机性和不可预 测性。因此，寻找评价伪随机序列随机性和不可预测性的度量指标成为许多密码学研究者的 课题。 密钥流序列随机性度量指标主要有：串分布、自相关值、周期和线性复杂度。安全性问 杭州电子科技大学硕士学位论文 题一直是密码体制强度的重要度量指标，特别是6 0 年代末诞生了著名的b m 综合算法【6 l ， 使得序列密码线性复杂度成为衡量密钥流序列随机性的一个重要指标，之后许多相关研究成 果随即提出1 7 芦j 。如果序列o ) 的线性复杂度为l c ( s ) ，则只要知道该序列的任意2 l c ( s ) 个连续 元素，就可通过解线性方程组或用b m 算法找到该序列所满足的齐次线性递归关系式来确定 整个序列，因此为了抗击已知明文攻击，密钥流序列的线性复杂度必须足够大。对于一般序 列，b m 算法目前仍然是最优的。关于特殊的周期序列，1 9 8 3 年g a m e s 和c h a n 给出了周期 为砂的二元序列线性复杂度的快速算法【9 】，使得线性复杂度算法的研究更进了一步，许多人 进一步推广了他们的工作【lo 1 1 】。这些推广算法本质上都没有突破g a m e s 和c h a n 的思想。 一个安全的序列并不必须要有高线性复杂度，如果它是不稳定的，一个周期中若干个元 素的改变会导致安全性明显降低，这样的序列仍属于密码学意义上的弱序列。线性复杂度的 稳定性和不可预测性关系紧密，因此密钥流序列的线性复杂度既要足够大，又要够稳定。 在8 0 年代后期，我国学者丁肖单第一个发现这个问题，并提出了重量复杂度、球体复 杂度球面周期、球体周期、函数稳定性等流密码稳定性度量指标【l0 1 ，并且建立了这些指标间 的相互关系，因而率先创立了流密码的稳定性理论，使流密码强度问题的研究取得了巨大突 破，引起了国际密码学界的广泛关注。 1 9 9 3 年，s t a m p 和m a r t i n 提出了一种新的指标融错线性复杂度用来衡量线性复杂度稳定 性，其类似球体复杂度度量指标，同时也定义了肛错线性复杂度曲线【1 2 1 。设o ) 是周期为的 g 元序列，当改变( s ) 的一个周期中至多颤蜓照鲫位后，得到的所有序列的线性复杂度中最小 的线性复杂度，称为o ) 的缸错线性复杂度。这使得线性复杂度的稳定性研究有了进一步发展， 很快肛错线性复杂度就被广大学者进行了大量应用。k u r o s a w a 等给出2 - 周期二元序列s 的 舡错线性复杂度严格小于线性复杂度g ) 的最小值【1 3 】为：k l i l i n - 2 2 。乩川，其中阿0 ( 6 ) 表示整 数b 在二进制表示下的h a m m i n g 重量。当k 较小时，n i e d e r r e i t e r 首次发现了厢上许多具有 大的线性复杂度和舡错线性复杂度的序列【1 4 】。胡红钢和冯登国通过序列的广义离散傅立叶变 换构造了一些两上具有极大l 错线性复杂度的周期序列【l 5 1 。 2 0 0 3 年，l a u d e r 和p a t e r s o n 将g a m e s c h a n 算法和s t a m p m a r t i n 算法同时推广，给出了 一个计算2 - _ 周期的二元序列线性复杂度曲线的算法，该算法可以同时计算2 ”周期的二元序 列的线性复杂度和肛错线性复杂度，随后也得到了一些推广算法【1 6 - 2 0 l 。s t a m p - m a r t i n 算法有 一个非常重要的模式：求线性复杂度时，我们把序列中的一些元素改变，使得线性复杂度在 某一步骤后减少m ，而在之后的步骤所有可能的线性复杂度减少之和不大于m ，则对应求线 性复杂度的算法一般可以推广为求缸错线性复杂度的算法。文献 2 1 】中求矿周期g f ( p m ) 上序 列珏错线性复杂度的算法显然满足s t a m p m a r t i n 模式。实际上，迄今为止所有求缸错线性复 杂度的算法均满足s t a m p m a r t i n 模式，如算法【2 2 ，2 3 ，2 4 ，2 5 】。目前，周期和线性复杂度仍然 是度量密钥流安全强度的两个最为重要的指标。 对于线性复杂度及其稳定性的研究，一方面是设计线性复杂度和“错线性复杂度的快速 算法，另一个方面是对周期序列的线性复杂度及其稳定性进行理论分析。对于线性复杂度和 2 杭州电子科技大学硕士学位论文 极小多项式理论分析的文章也很岁8 , 2 4 , 2 6 ，2 7 】。而人们之所以研究线性复杂度的稳定性，是因为 少量元素发生变化可能会引起线性复杂度的急剧下降。那么多少元素发生变化会引起线性复 杂度的下降? k u r o s a w a 等引入了最小错误m i n e r r o r ( s ) 的概念【2 8 】来描述这个问题，将其定义为 使得序列0 ) 线性复杂度下降所至少要改变的元素个数，即缸错线性复杂度曲线的第一个跃变 点对应的k 值。那么，具体是哪些位置发生变化会引起线性复杂度的下降? 文献 1 3 】引入错误 序列来阐述这个问题。下降后的线性复杂度又是多少呢? 即当k = m i n e r r o r ( s ) 时，后错线性复杂 度的值是多少? 针对这些问题，文献 1 3 研究了2 刀周期二元序列线性复杂度与缸错线性复杂 度的关系，给出了用线性复杂度的h a m m i n g 重量表示的最小错误m i n e r r o r ( s ) 的值，并给出了 k = m i n e r r o r ( s ) 时b 错线性复杂度的上界。缸错线性复杂度曲线的概念和m i n e r r o r ( s ) 的提出引起 了许多研究者的注意【2 0 , 2 9 , 3 0 ，3 1 ，3 2 1 。n i u 和x i a o 讨论了在p 是素数且2 是模，的本原根的条件 下，周期为2 矿的二元序列的m i n e r r o ro ) 的上下界【3 0 1 。牛志华、白恩健和肖国镇讨论了矿矿 周期g 元序列的线性复杂度与缸错线性复杂度的一些关系【3 2 1 。对2 y 周期二元序列( 其中p 是素数，2 是模矿的本原根) ，谭林和戚文峰详细讨论了m i n e r r o rg ) 与线性复杂度的关系【3 3 1 ， 并确定了m i n e r r o r0 ) 的上下界。以上这些研究表明学者们已经开始考虑周期序列的稳定性及 线性复杂度之间可能存在的某种内在联系。而找出这种联系不但有利于得到计算周期序列线 性复杂度和肛错线性复杂度的快速算法，而且可以直接通过分析周期序列线性复杂度进一步 分析其稳定性。 因此，亟需研究这样的序列，即使序列的少量元素发生变化其线性复杂度却没有下降。 针对这个问题，我们提出稳定肛错线性复杂度的概念。设s 是周期为的g 元序列，当改变 s 的一个周期中至多颤0 删位后，得到的所有序列的线性复杂度均不小于s 原来的线性复杂 度，称s 具有稳定肛错线性复杂度。 对周期序列的线性复杂度及其稳定性进行理论分析的另一个重要原因是了解周期序列线 性复杂度和髓错线性复杂度的统计特性，如计算数学期望、分布、方差掣1 4 弘枷】。1 9 8 6 年， r u e p p e l 对二元序列线性复杂度的随机性进行了更深层次的研究，并猜测周期二元序列的线性 复杂度的期望值接近它的周期，并给出了线性复杂度为的2 一周期二元序列的具体个数【4 。 2 0 0 2 年，m e i d l 和n i e d e r r e i t e r 运用离散傅里叶变换( d f t ) 与广义离散傅里叶变换( g d f t ) ，给 出了任意有限域g f ( q ) 上周期序列线性复杂度的数学期望值和肛错线性复杂度的一些有用的 下界【1 8 】，证明了r u e p p e l 的猜测。丁存生、肖国镇等优秀的学者对序列的线性复杂度及球体 复杂度之间的相互制约关系【1 0 】进行了猜测。随后，n i e d e r r e i t e r 通过进一步研究，指出可以得 到线性复杂度和缸错线性复杂度同时达到最大值的序列【3 6 ，3 7 3 8 1 ，从而推翻了丁肖单的猜测。 2 0 0 5 年，m e i d l 给出了k = l 和2 时线性复杂度为2 ”的2 以周期二元序列的肛错线性复杂度 分布情况1 4 2 j ；在2 0 0 7 年，朱风翔和戚文峰给出了k = - 2 和3 时线性复杂度为2 厅1 的2 矗周期二 元序列的缸错线性复杂度分布情况【4 3 1 ；文献【4 4 】给出了k - - 3 和4 时线性复杂度为r 的2 ，1 周期 二元序列的肛错线性复杂度分布情况；我国学者苏明研究了2 一周期二元序列的线性复杂度和 1 错线性复杂度，并且指出了这些序列具有固定的1 错线性复杂度【4 s 】。 3 杭州电子科技大学硕士学位论文 本文通过研究周期为2 行的二元序列线性复杂度，提出使用方体理论构造稳定舡错线性复 杂度序列的方法，而且给出了该方法的许多实例。证明了周期为- 2 刀的二元序列可以分解为 若干互不相交的方体，从而给出一个研究缸错线性复杂度的新方向。通过研究周期为2 开的二 元序列线性复杂度，提出将肛错线性复杂度的计算转化为求h a m m i n g 重量最小的错误序列。 基于g a m e s c h a n 算法【9 】，讨论了线性复杂度为2 - m 的2 ”一周期二元序列的缸错线性复杂度分 布情况。 1 3 论文的主要工作及内容安排 本论文主要研究基于缸错线性复杂度的周期序列计数与刻划，主要着重于具有固定线性 复杂度的2 甩周期二元序列的舡错线性复杂度分布情况。传统的对周期序列线性复杂度的研究 许多局限于采用纯数学方法。本论文的最大特色是采用计算机构造仿真和数学理论分析证明 相结合的整体思路：设计有效算法一 构造仿真序列实例- 发现一般规律和构造一般算法 数学理论分析证明。这样的过程使纯理论证明的缺陷得到了解决，避免了错误的发生。如文 献【4 6 采用纯数学方法，得出的结论未经过计算机编程验证，这就造成了定理4 2 和定理5 2 的错误；而文献 4 7 1 是经过计算机仿真给出的正确结果。 本文共分六个章节，结构安排如下： 第一章详细介绍了密码学和线性复杂度的一些背景知识、研究意义和发展现状，以及论 文的内容安排和作者取得的主要成果； 第二章介绍了和本文相关的密码学和序列密码的基础知识，密码学基础知识介绍了对称 密码和非对称密码，序列密码部分介绍了起源、定义、原理和分类，最后介绍了寄存器序列， 肌序列，以及著名的b m 算法； 第三章详细介绍了周期序列线性复杂度这一概念和舡错线性复杂度的相关概念和背景知 识，并分别介绍了线性复杂度和缸错线性复杂度的计算方法g a m e s c h a r t 算法和s t a m p m a r t i n 算法； 第四章首先提出稳定缸错线性复杂度及方体理论，通过研究周期为2 n 1 的二元序列线性复 杂度，提出将肛错线性复杂度的计算转化为求h a m m i n g 重量最小的错误序列。基于g a m e s c h a n 算法和s t a m p m a r t i n 算法，讨论了线性复杂度为2 刀1 的2 行周期二元序列的6 错线性复杂度分布 情况，然后给出了其大部分计数公式，同时通过计算机编程分别验证了n = 4 和n = 5 时6 错线性 复杂度为三( l c ) 的个数的准确性，确保了理论与实际的统一。基于上述结论，指正了王军关于 周期序列的缸错线性复杂度分析和研究f 4 8 】这篇硕士论文中给出的6 错公式的错误； 第五章基于g a m e s c h a n 算法和s t a m p m a r t i n 算法，讨论了伽，幼固定时线性复杂度为矽m 周期为2 以的二元序列的船错线性复杂度的分布情况； 第六章为全文的总结和展望。 本文完成的主要工作和结果如下： 1 本文通过研究周期为砂的二元序列线性复杂度，提出使用方体理论构造稳定七- 错线性 4 杭州电子科技大学硕士学位论文 复杂度序列的方法，给出该方法的许多实例。证明了周期为n = 2 一的二元序列可以分解为若干 互不相交的方体，从而给出一个研究缸错线性复杂度的新方法。 2 通过研究周期为2 行的二元序列线性复杂度，提出将肛错线性复杂度的计算转化为求 h a m m i n g 重量最小的错误序列。基于g a m e s c h a n 算法和s t a m p m a r t i n 算法，讨论了线性复杂 度为2 一1 的2 开周期二元序列的6 错线性复杂度分布情况。在大多数情况下，给出了对应6 错线 性复杂度序列的计数公式。同时通过计算机编程分别给出了n = 4 和n = 5 时，6 错线性复杂度为 上( ，c ) 的个数。基于上述结论，指正了王军学术论文中的一个重要错误。 3 基于g a m e s c h a n 算法和s t a m p m a r t i n 算法，讨论了固定线性复杂度即线性复杂度为 2 n m 的2 一一周期二元序列的肛错线性复杂度分布情况。当( 研，妨= ( 2 ，2 ) ，( 3 ，4 ) ，( 4 ，2 ) ，( 5 ，4 ) ，( 6 ，4 ) ，( 7 ，8 ) ， ( 8 ，2 ) 时，给出了对应缸错线性复杂度序列的计算公式。对于一般的m ，也可以通过该方法给出 对应缸错线性复杂度序列的计算公式。 5 杭州电子科技大学硕士学位论文 第2 章基础知识介绍 本章首先给出了密码学的基础知识，其中详细介绍了对称密码体制和非对称密码体制的 工作原理；接着着重介绍了密码学中序列密码的起源和定义、基本原理、分类以及密码实现 机制；其次介绍了移位寄存器序列、反馈移位寄存器序列和线性反馈移位寄存器序列；同时 详细介绍了m 序列的伪随机性和密钥流生成器；最后介绍- j b e r l e k a m p m a s s e y 算法。 2 1 密码学的基础知识 密码学( c r y p t o g r a p h y ) 是一门试图通过各种安全而且有效的密码技术去解决各种信息安 全和通信安全的科学和技术【4 9 】。在密码学中，没有加密的信息称为( p l a i n t e x t ) ；加密后的信息 称为密文( c i p h e r - t e x t ) ；把明文转换成密文叫做加密( e n c r y p t i o n ) ；把密文变为明文称为解密 ( d e c r y p t i o n ) ；加解密都是受控于密钥( k e y ) 。给定一个密钥，就可以确定一对具体的加密变换 和解密变换。 密码技术的基本功能是保密通信的信息。经典的加密通信模型如图2 1 所示： 文 密钥 图2 1 加密体制 密码编码学和密码分析学组成了密码学。密码编码是为了设计密码体制来确保安全；而 攻破密码体制是密码分析完成的。编码和分析既对立又依存，辨证统一【删。根据加密过程是 否可以推导出解密过程，密码体制分为：对称密钥密码体制( 私钥密码体制) ；非对称密钥密 码体制( 公钥密码体制) 。 2 1 1 对称密码体制 对称密钥密码体制是一种传统的密码体制。在对称密钥加密系统中，加、解密双方均采 用相同的密钥，即使二者不同，也能够由其中的一个很容易地推导出另一个，因此，在这种 密码体制中，有加密能力就意味着有解密的能力。按加密的方式可将对称密码算法分为两类： 一种算法称为序列密码算法或流密码算法；另一种算法称为分组密码算法。由于两者每次处 理不同的数据量，使得序列密码和分组密码的设计思路、分析方法不同。接下来介绍这两种 算法。 一、序列密码，又称为流密码【7 2 够1 5 引。序列密码是指明文划分成字符( 如二元数字) 逐位 地、对应地加密，同步地产生一样的密钥流完成解密，流密码强度完全依赖于密钥流产生器 生成序列的随机性和不可预测性。序列密码变换算法与时间有关，算法实现速度快，错误传 6 杭州电子科技大学硕士学位论文 播率低，硬件实现简单。但是对于密文的插入或修改等敏感度低，统计混乱程度不足，其主 要应用在新一代的移动通信中。 设计序列密码算法的实质是构造有效的伪随机序列生成器，主要有4 种方法：一，基于线 性反馈移位寄存器；二，通过分组密码序列化；三，基于模运算；四，一些如r c 4 ，s e a l 等 快速算法，主要用于软件的实现【s o 。 流密码经过一段时间发展后，理论基础、安全性分析都比较完善，运行速度也够快。它 一般应用在专用密码机中。 二、分组密码，也称之为块密码。是将明文消息编码表示后的数字序列，划分成为固定 大小的组或块，各组分别在密钥的控制下变换成等长的输出数字序列( 而序列密码正好相反， 它只能一次加密一个位或者一个字符) 。其工作方式是将明文分成长度固定的组，如6 4 比特或 1 2 8 比特，对于不足6 4 比特或1 2 8 比特的尾组用适当的方式进行填充，将其扩充为一个整组， 然后进行正常的加密。由于尾组的扩充，使密文的长度会大于明文的长度。然后用同一密钥 和算法对每一组加密，输出固定长度的密文。分组密码加密函数实际是从n 比特明文块到n 比 特密文块的映射乓： 0 ，1 ) “一 0 ，1 ) “，行为块长，解密函数b = 乓1 满足b ( 乓( 朋) ) = m 。为了 保证解密的唯一性，要求加密函数必须是一一映射。可以把加密函数看成长度为n 的比特串 上的置换，不同的密钥后定义不同的置换。 分组密码的安全性要求在不知道密钥k 的情况下，即使能得到全部密文，并且知道加密 函数的全部计算细节，也无法得到相应的明文。例如，对于6 4 比特分组，对之进行穷尽的数 据量为2 “，这是一个2 0 位的十进制数，即使用每秒运算亿万次以上的大型计算机进行攻击， 平均穷尽时间也需要数年。当热这仅是理论数据，在攻击密码时还有其他约束条件，如文字、 数据、规律等信息，所以实际所需的攻击时间要短的多。 分组密码不仅可以加密数据，也可以用在其他方面，如构造伪随机数生成器、流密码、 认证码、和哈希函数。分组密码也是众多消息认证技术、数据完整性机制、实体认证协议及 数字签名方案的核心部件。在目前有四个比较著名的分组密码算法标准：美国i b m 公司研制 的“d e s ( 数据加密标准) ”；密码学专家j a m e s l m a s s e y 设计的“s a f e r ，j o a nd a e m e n 和v i n c e n t r i j m e n 共同完成的“r i j n d a e l ，来学嘉博士设计的“i d e a ( 际数据加密算法) ” 5 9 1 。 分组密码是现代密码学中的一个重要的研究方向，其诞生和发展有着广泛的使用背景和 重要的理论意义【6 晰3 1 。文献 6 4 】详细阐述了近年来分组密码呈现出的发展趋势。 分组密码发展时间短，是一个独立的不随时间变化的固定算法，算法结构严谨，破译复 杂度高，对密文攻击敏感度高，但是同样存在缺点，即分组加解密操作速度慢，错传误传现 象较严重。分组密码一次处理的数据量为一个分组，而分组大小般为8 位的整数倍，因而一 般都应用于软件实现，而且处理速度比较快，可以内嵌到软件模块中，因此，分组密码算法 被广泛地应用于各种软件应用系统中【6 ”。 2 1 2 非对称密码体制 7 杭州电子科技大学硕士学位论文 非对称密钥密码体制也就是公钥密码体制，是由d i f f i e 和h e l l m a n 于1 9 7 6 年首次提出的一 种密码技术【6 6 1 。与对称密码体制相比，公钥密码体制有两个不同的密钥，分别实施加密与解 密。一个密钥称为私钥，需要秘密保存好；另一个密钥称为公钥，不需要保密，可以公开。 密码体制的发布由信源完成，它将加密密钥公开，使每一个需要和它通信的人都可以取得， 从而可以向其发送加密消息。相反，它将解密密钥保密，用于解密收到的密文，攻击者虽然 也可以得到加密密钥，但由于不能由此推导出解密密钥，故不能解密密文。公钥密码体制公 开发布密钥，成功解决了密钥分配问题，其产生对于密码学有革命性的意义，开启了密码学 的新篇章。 2 2 序列密码 2 2 1 序列密码的起源和定义 序列密码源于v e m a m 密码算法【6 7 】，它由美国电报g w v e m a m 公司在1 9 1 7 年发明，当 时为了将2 6 个英文字母编码，把每个字母编成5 b i t 二元数字，称之为五单元波多电码。这样 每个电报明文可以变换成每个字母对应二元b i t 组合的长序列，即 m = 朋l 历2 m 3 m f m f 1 0 ，1 j 要加密传输时，可以取相同长度的二元数字序列： k = k l k 2 k 3 k f k f 【o ，l j 加密算法过程将k 和m 安位异或得到相应的密文序列，即 q = m f0 k i ( m o d 2 ) i = 1 , 2 ，3 c = c l c 2 c 3 q q t o ，1 j 解密电报时，利用相同的密钥纸带对密文进行再加密，即逐位相加模2 可得出明文对应的二 元码： 聊f = m 净c fo 尼f ( m o d 2 ) i = 1 , 2 ，3 如果密钥序列k ；之间是相互独立的且是随机的，那么v e m a m 密码就是真正意义上的一次一 密，相对应的唯密文攻击是绝对安全的。但这样做的缺陷就是密钥序列必须和明文的二元序 列一样长，这使得密钥交换和密钥管理变得相当繁琐和复杂。因此必须设计一个方案，使得 可以从一个有限的密钥序列产生用于加解密的足够长的密钥序列，并且即使被攻击者截获的 一段密钥序列，也无从得知接下来的任何有用的密钥序列。 具体的说，序列密码即流密列6 8 】，是对明文信息逐位加解密的对称密码。其加解密的过 程如下图2 2 所示。其中，k e y 是密钥源，即系统的初始密钥，它可以通过通信双方事先约定 或者通过安全信道进行交换，另外还可以在公共信道使用密钥交换协议进行密钥交换。在拥 有相同密钥源k e y 的前提下，通过密钥序列生成器k u ( k e y s t r e a mg e n e r a t o r ) 同步生成用于 加解密的密钥序列：k o k l k k 川。将明文膨分解成明文序列m o m l 朋m 川，其中 m l m 。生成对应的密文序列为： c = c o c l c f 巳一l = 氏( 肌o ) e l , 。( m 1 ) e k , ( 肌j ) e l ( 聊川) 8 杭州电子科技大学硕士学位论文 k i 和分别是密钥序列和明文序列。当对应的q = ( 所，) = 朋；0 屯，则称此类算法为序列密 码。 密文序 明文序列锄，列 c ， 密 钥 序 列 纯 公开信道 密文序 列 解密序列锄；) 圆圆 密钥序列生成 密钥源k e y 密 钥 序 列 纯 密钥序列生成 篆嚣卜或安全信道广1 密钥源吻 图2 2 序列密码加解密过程图 2 2 2 序列密码的原理 序列密码的工作原理很简单，如上图2 2 所示，输入端的明文序列m ，和密钥序列生成器 产生的密钥序列k ；按比特对比特进行模二加运算作为加密过程，对应的解密过程是将从信道 传来的密文序列q 和同步的密钥序列k i 做相同于加密时的模二加，输出解密明文m ，。也就是 说加解密运算只是简单的模二加运算，其安全强度完全依赖于密钥序列的随机性。因此序列 密码的核心就是密钥序列生成器的设计，要产生充分随机的密钥序列，需满足以下要求： 1 密钥源k e y 要有足够的长度，一般在1 2 8 位以上； 2 产生的密钥序列忽要有极大周期； 3 在一个周期内，某定长的刀位比特串与其反比特串，两者出现的频数大抵相当。即k 满足均匀的n 元分布； 4 利用统计的方法由k 去破译脚的结构或者预测k i 在计算上时不可行的； 5 序列溉 满足混乱性，即序列的每一位均与其他多数位有关； 6 序列 七， 满足扩散性，即雪崩效应，序列的每一位的改变将改变接下来序列的全貌； 7 序列 七； 满足不可预测性，即己知密文和对应的明文并不能确定和预测整个阮 。 2 2 3 序列密码的分类 序列密码可以分为同步序列密码和自同步序列密码两类。 2 2 3 1 同步序列密码 如果密钥序列生成器的设计是独立于明文和密文的，那么此类序列密码称为同步序列密 码【6 9 1 ，其加密过程可用如下的关系式来表述： 9 杭州电子科技大学硕士学位论文 s “l = k ( s ，缸吵) i = o , 1 ，2 ，3 k i = c ( s 。k e y ) i = 1 , 2 ，3 c j = e ( k i ，m f ) f = 1 , 2 ，3 其中，切为密钥源，墨为密钥序列生成器所处的状态，s o 为其初始状态，k ，为用于加 密的密钥序列，m ，和c ，分别是明文序列和对于的密文序列。k 是状态函数，g 是密钥序列生 成函数，k 和g 合在一起就是密钥序列产生器k g ( k e y s t r e a mg e n e r a t o r ) 。e 是加密输出函 数，用于运算密钥序列和明文序列产生密文。 2 2 3 2 自同步序列密码 如果密钥序列生成器是初始密钥和一定长度的以往密文位的函数，那么这种密钥序列称 作是自同步序列