（应用数学专业论文）流密码复杂性研究.pdf

扬州大学硕十学位论文 符号说明 4 一 g 元有限域； ( x ) x 的刀次多项式； 阳船( m ) 矩阵m 的秩； d e g ( 厂( x ) ) 厂( x ) 的i ! ：数； g c d ( x ，y ) x 和y 的公因子； o r 如，( x ) x 的阶； 乃( x ) 迹映射； 。( z ) 刀次分圆多项式； 三c ( s ) 序列s 的七错线性复杂度； 三g ( s ) 序列s 的线性复杂度； _ ( s ) 序列s 的非线性复杂度； 朱莉艳：流密码复杂性研究 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 4 3 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研 究成果。除文中已经标明引用的内容外，本论文不包含其他个人或集体已经发表 的研究成果9 对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。 本声明盼法律结果由本人承担。 学位论文作者签名： 煳栖 签字日期：z 内孑年多月，日 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向 国家有关部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅。 本人授权扬州大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学 技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 学位论文作者签名： 是肖格 导师签名： 签字日期：2 。昭年多月。日 签字日期：蝣b 凤。 日 朱莉艳：流密码复杂性研究 摘要 在信息时代的今天，随着通信技术和网络技术的高速发展和广泛应用，越来越 多的信息在网络上传输，信息的安全与保护显得愈发重要。密码学理论与技术也 逐渐成为信息科学与技术中的一个重要研究领域。流密码是现代密码学中的一个 重要的研究分支，并且随着移位寄存器理论的飞速发展，加上有效的数学工具， 使得流密码理论得到了长足的发展。本文主要研究基于反馈移位寄存器的流密码 安全性的重要度量指标线性复杂度、k 一错线性复杂度和周期，得到如下主要结果： 首先，本文对基于反馈移位寄存器的二进周期序列的非线性复杂度进行分析， 考虑了对给定非线性复杂度的值的二进周期序列的设计，并通过计算机搜索给出 了一些具有最小非线性复杂度的二进周期序列的形式。此外还给出一类特殊的序 列的非线性复杂度和线性复杂度； 其次，对基于线性反馈移位寄存器的周期序列的线性复杂度进行分析，阅读 了目前的周期序列的线性复杂度的一些快速算法。在此基础上，提出了c 上满足 条件g c d ( “，p ) = 1 的周期为妒”的序列s = ( s ，一。) 。的线性复杂度的快速 算法，并且给出如何将周期为印”的序列的线性复杂度的计算转化为周期为p ”的序 列的线性复杂度的计算的详细方法。由于本算法中扰个周期为p ”的序列的线性复 杂度的计算可以利用并行算法，因此大大降低了e 上周期为印”的序列的线性复杂 度的计算。 最后，利用将周期n = 印”的序列s 的线性复杂度转化为“个周期为p ”的子序 列的线性复杂度的思想，得到了序列s 的线性复杂度和七错线性复杂度的关系，并 给出了周期为p ”的序列的k 错线性复杂度严格小于线性复杂度的一个充要条件。 关键词：流密码，周期序列，s p a n ，线性复杂度，联合线性复杂度，k 错线性复 杂度，极小多项式，线性移位寄存器 扬州大学硕士学位论文 a b s tr a c t 2 一 w 曲t 1 1 er 印i dd e v e l o p m e ma i l dw i d ea p p l i c a t i o no fc o 删 i l u n i c a t i o na n dn 印v o r k ， m o r ea n dm o r ei n f o r m a t i o nh a sb e e nt m s m i t t e dt h r o u g ht h en e t w o r k t h e r e f o r e ，m e i n f o m a t i o ns e c u r i t ) ra n dp r o t e c t i o na r e g e t t i n g m o r ea n dm o r e i m p o r t a n t t h e c r ) ，p t o g r a p h yt h e o 巧a 1 1 dt e c l l n o l o g y w m c ha j m s a tt h ei n f o n n a t i o ns e c u r i t y ，h a l v e b e c o m et 1 1 ei m p o i r t a n tr e s e a r c hf i e l d si ni 删f o 肌a t i o ns c i e n c ea i l dt e c h l l o l o g y t h es t r e 锄 c i p h e ri so n eo ft h ei m p o n a n tb r a n c h e so fm o d e mc 巧p t o 伊a p h y t b g e t l l e rw i t l lt h e e f r e c t i v e l ym a t h e m a t i c a lt o o l sa n dt h ed e v e l o p m e n to fs 1 1 i rr e g i s t e rt h e o 巧h a sb r o u g h t 铲e a tp r 0 铲e s so fs t r e a mc i p h e rt h e o 巧t m sd i s s e r r t a t i o nm a i n l ys t u m e si m p o m m t m e a s u r ei n d e x 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 ya n dp e r i o d ， o nt h e s e c u r i t yo fs t r e a mc i p h e r sw h i c h2 u r eb a s e do no f f e e d b a c ks h mr e g i s t e r t h em a i ns 砌y i s 行o ms e v e r a lf o l l o w i n gr e s p e c t s ： f i r s t l y ，t h ea u t h o rs t u d i e dt h en o n l i n e a rc o m p l e x i 够o fp e r i o d i cb i n a 巧s e q u e n c e s w 1 1 i c ha r eb a s eo nf e e d b a c ks h i rr e g i s t e r ，a n dc o n s i d e r e dt h ed e s i g no fp e r i o d i cb i n a r y s e q u e n c e sw i t hn o n l i n e a rc o m p l e x i t y o fag i v e nv a l u e b e s i d e s ，s o m ef o m so f s e q u e n c e sw i t ht h em i i l i m u mn o i l l i n e a rc o m p l e x i 够w e r es e a r c h e db yc o m p u t e r i n a d d i t i o n ，t h en o n l i n e a rc o n l p l e x i t ya i l d1 i n e a rc o m p l e x i t yo fa 够p eo fs p e c i a ls e q u e n c e s w e r eg l v e n s e c o n d l y ，t h ea u t h o rs t u d i e dm el i n e a rc o m p l e x i 够o fp e r i o d i cs e q u e n c e sw m c ha r e b a s eo nl i n e a rf e e d b a c ks h i rr e g i s t e ra n dr e a d ss o m e 凤ta l g o r i t h mo fm el i n e a r c o m p l e x 时o fp e r i o d i cs e q u e n c e s a n dt h ea u t h o rp r e s e n ta ne m c i e n ta n da n r a c t i v ef 瓠t a l g o r i t h m t od e t e m i n et h el i n e a rc o m p l e x i 够o f印”- p e r i o d i cs e q u e n c ei nf i n i t ef i e l dc u n d e rg c d ，p ) = 1 b e s i d e s ，t h e 玑i t h o rp o i n t e do u th o wt or e d u c em ec a l c u l a t i o no ft h e l i n e a rc o m p l e x 埘o fa 印”一p e r i o d i cs e q u e n c et oc a l c u l a t i o no ft h el i n e a rc o m p l e x i t i e s 朱莉艳：流密码复杂性研究 3 o fc e r t a i np 7 - p e r i o d i cs e q u e n c e s a l s o ， c a l c u l a t i o n so ft h e1 i n e a rc o m p l e x i t i e so ft h e s e p 9 p e r i o d i cs e q u e n c e sc a nu s et h ep a r a l l e lp r o g r a m ，s ot l l e c a l c u l a t i o no ft 1 1 el i n e a r c o m p l e x i 够o fam p ”- p e r i o d i cs e q u e n c ec o u l d b em u c hf 如t e r f i n a l l y ，b yt h ec a l c u l a t i o no ft h e l i n e a rc o m p l e x i t yo fa印”一p e r i o d i cs e q u e n c e r e d u c et oc a l c u l a t i o no ft h el i n e a rc o m p l e x i t i e so fc e r t a i n p ”- p e r i o d i cs e q u e n c e s ，m e a u t l l o rg o tr e l a t i o nb e t w e e nt l l el i n e a rc o m p l e x i 够a n dt l l ek e r r o rl i n e a rc o m p l e x i t ) ，o f t 1 1 e 印”- p e r i o d i cs e q u e n c e s i i la d d i t i o n ，an e c e s s a r ya n ds u 伍c i e n tc o n d i t i o no f p ”- p e r i o d i cs e q u e n c e sw i l i c hi t sk e r r o rl i n e a rc o m p l e x 时i ss t r i c t l yl e s st h a i lt h el i n e a r c o m p l e x i t yw a sa l s os h o w e d k e yw o r d s ：s t r e 锄c i p h e r s ，p e r i o d i cs e q u e n c e s ，s p a n ，l i n e a rc o m p l e x i t ) ，j o i n tl i n e a r c 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 ，m i n i m a lp o l y n o m i 2 l l ，l i n e a rf e e d b a c ks 1 1 i r r e g i s t e r ； 朱莉艳：流密码复杂性研究 0 引言 密码技术应用于保护军事和外交通信的历史可以追溯到四千多年前。长期以 来，除了少数业余爱好者外，绝大多数研究都是官方组织秘密进行的。但是，随 着通信网络和计算机网络的普及，随着信息化程度的提高，每个人都将与信息的 生产、使用、存储、处理和传递密切相关，信息安全和保密问题成了人人都关心 的事情。现代密码学的应用不再局限于政治、军事和外交，其商业价值和社会价 值也得到了广泛的认同。 1 9 4 9 年，s h a n n o n 发表的保密系统的通信理论 1 为单钥密码系统建立了 理论基础，一个保密系统可以下述表示( 见图( 1 ) ) 。从此，密码学成为一门科学。 而微电子学的发展也为实现当时的密码学思想提供了实际手段。使得密码学，尤 其是流密码得到了长足的发展。1 9 7 6 年，d i f f i e 与h e l l m a n 发表的密码编码学 的新方向 2 提出的双钥( 或公钥) 密码系统导致了密码学史上的一场革命，为解 决通信网络中的信息安全提供了新的理论和技术基础。 图( 1 ) 保密系统 r 1 i 密码分析者 l 1 f 一 x y 囤恒困 阿k ，一怕甄蓓司： 密码按加密形式可分为流密码和分组密码，流密码又称为序列密码。今年来， 流密码的理论得到了长足的发展。相对而言，分组密码的研究进展较慢。其原因 有以下几点：其一，流密码中的同步密码结构较后者简单；其二，流密码有较为 理想的数学分析工具，如频谱理论和技术，代数等；其三，分组密码的一个不足 之处在于相同的明文组对应相同的密文组，这给密码分析者充分利用明文语言的 扬州大学硕士学位论文 6 多余度提供了可能性。这就是说，密文的串检验破译对分组密码是一种挑战；其 四，目前大多数国家的军事和外交保密通信似乎主要使用流加密方式。 从2 0 世纪8 0 年代中期到9 0 年代初，流密码的研究非常热，特别是在流密 码的设计方法、安全性度量指标、分析方法、用于设计流密码的各种组件( 如密码 布尔函数的构造与分析、非线性资源的生成和分析) 等方面取得了很大进展。 流密码的研究主要包括以下方面：其一，密码函数( 包括相关免疫函数、弹性 函数、b e n t 函数等) 的研究；其二，关于序列的设计，包括前馈序列( b e n t 序列、 几何序列等) 、对数序列、钟控序列、稀疏序列等；其三，对序列密码的攻击问题， 分为线性攻击、分别征服攻击( d i v i d ea n dc o n q u e r ) 以及最佳仿射攻击( b e s t a f f i n ea t t a c k ) 。线性攻击主要针对低线性度的序列，一般用b m 算法。分别征 服攻击主要针对非线性组合序列对驱动序列的依赖性。最佳仿射攻击主要针对序 列线性复杂度的不稳定性。 自从密码理论和技术诞生以来，密码体制的强度问题一直困扰着密码设计者 和密码分析者，问题的关键在于提出强度的新度量指标。六十年代末提出的线性 反馈移位寄存器b m 5 综合算法使得线性复杂度成为一些流密码系统强度的重要 指标。但直到八十年代中期，流密码的研究仅限于一些相关方法的探讨和线性复 杂度的分析。八十年代末期，我国学者首先创立了流密码的稳定性理论 1 3 4 ， 提出了“重量复杂度”、“球体复杂度”、“函数稳定性”等一系列流密码系统强度 度量的重要指标，引起了国际密码学界的广泛关注。当前，周期和线性复杂度仍 然是度量密钥流序列的安全强度最为重要的指标。 本文主要周期序列的线性复杂度，该篇论文的主要安排和主要进展如下： 第1 章：给出有关流密码的详细介绍，如流密码的定义、运行机制、工作模 式，及密钥流生成器的设计准则等。单钥密钥的两种形式一分组密码和流密码，流 密码的两种形式一同步流密码和自同步流密码。以及密钥流生成器的设计要求实现 简单，速率高，周期大，线性复杂度大以及具有良好的统计性质。并深入了解密 钥流生成器的常用驱动部分一线性反馈移位寄存器( l f s r ) 。例如线性反馈移位寄 朱莉艳：流密码复杂性研究 7 一 存器的定义，如何产生密钥流序列，以及线性反馈移位寄存器中主要考虑的问题。 第2 章：周期序列的复杂度分析。主要集中在对于给定非线性复杂度值得周 期序列的设计，通过计算机搜索给出具有最小非线性s p a n 值的周期序列。 第3 章：周期序列的线性复杂度的快速算法。利用有限域的已有结论，引入 到周期序列的线性复杂度的计算。第二节给出了g a m e s c h a n 算法及其推广算法， 第三节给出了x i a o w e i l a m i m a m u r a 算法，第三节给出了只上的周期为印”的序 列线性复杂度的快速算法，在c h e n 给出的定理和联合复杂度的定义下，将周期为 印”的序列线性复杂度的计算转化为求周期为p ”的甜个序列线性复杂度的和，并且 将周期为p ”序列的线性复杂度的计算转为求其联合线性复杂度。 第4 章： 给出了l 上周期为印”的序列s 的线性复杂度导后错复杂度的关 ， 系，同样基于c h e n 给出的定理，将周期为p ”的序列s 的线性复杂度粤后错复杂度 的关系推广到周期为印”的序列s 的线性复杂度导尼错复杂度的关系。 扬州大学硕上学位论文 1 流密码体制 1 1 流密码的定义 8 一 流密码( s t e 锄c i p h e r ) 也称序列密码。在流密码中消息被分成连续的符号 x = 一，x ：，用密钥流七= 岛，如，的第f 个元素砖对薯进行加密( 如图( 2 ) ) 。如 果密钥流经过三个符号之后重复，则称该流密码是周期的，否则称为非周期的。 图( 2 ) 流密码的运行机制 一密钥 明文 密钥流 加密 流密码与分组密码的之间的主要区别在于记忆性( 见图( 3 ) ) 。在流密码中， 密钥流元素的产生由该时刻流密码的内部状态和密钥共同决定。比较而言，刘密 码似乎比分组密码安全。这是由于在分组密码中，相同的明文组对应相同的密文 组，而流密码中却没有这种现象，因为明文的重复部分是用密钥流的不同部分加 密的。 图( 3 ) 流密码和分组密码的加密 炉& 隅) ，弓项七，) 流密码 y l卜 y l 卜 k 尸酬分组密码 y l y n 一 ；= 要一 一 朱莉艳：流密码复杂性研究 1 2 流密码的分类 9 加密器中存储器的状态随时间而变化，这一变化过程可用一个函数( 通常称为 状态转移函数) 来描述，记为z 。 根据状态转移函数z 是否依赖输入的明文符号( 字符或比特) ，可将流密码分 为两类： 1 ) 同步流密码( s y n c h r o n o u ss t e a mc i p h e r ) ：z 与输入的明文符号无关； 2 ) 自同步流密码( s e l f s y n c h r o n o u ss t e a mc i p h e r ) ：z 与输入的明文符号 有关。 在同步流密码中，密钥流的产生独立于消息流。因此，下一个状态仅与前一 个状态有关，而与输入无关。从而，状态序列与收到的符号序列无关。因此，加 密变换是无记忆的，但却是随时间而变化的。而生成器本身却是有记忆的，它需 要内部记忆来生成必要的状态序列。为了便于分析，习惯上将同步流密码的加密 变换与控制加密变换的时变参数的生成过程分开。实际使用的数字保密通信系统 一般都是二元系统，因而在有限域只上讨论的二元加法流密码( 如图( 2 ) ) 是目 前最受欢迎的流密码体制，其加密变换可表示为m = 一+ 砖。 1 3 密钥流生成器的设计准则 1 ) 长的周期：假设毛屯毛是o 一1 序列的密钥流，用 毛) 表示。是对于所 有的正整数f 满足t + v = 墨的最小正整数。若存在这样的，则称序列 砖) 以为 周期； 2 ) 线性复杂度准则：大的线性复杂度； 3 ) 统计准则：理想的游程分布( 对于任意长度，o 的游程个数和1 的游程个 扬州人学硕士学位论文 1 0 数相等) ； 4 ) 异相自相关函数为一个常数； 若有两个子序列s ，s 和s 彬& 川，s 竹，是前一序列后移f 位得到 后一序列，若s ”= s 则称对应于第f 位是相同的。这两个子序列中相同的位的数 目用门f 表示，不同的数目为d f = ，一，2 f ，定义尺( f ) = ( ，z f d r ) ，为自相关数。则有 f = 0 时，显然有甩f = r ，如= o ，r ( o ) = l ；当f o 时，称r ( f ) 为异相自相关函数。 5 ) 混乱：每个密钥流比特必须是所有或大多数密钥比特的一个复杂变换； 6 ) 扩散：子结构的冗余度必须扩散到大范围的统计中去； 7 ) 函数的非线性准则：相关免疫性，非线性度，雪崩准则等。 1 4 移位寄存器 移位寄存器的结构简单，运行速度快，到目前为止，实用的密钥流产生器大 多基于移位寄存器，移位寄存器理论也成了现代流密码体制的基础，下面简单讨 论有关移位寄存器的重要概念和理论。 移位寄存器是产生信号和序列的常用设备，它分为线性和非线性两大类。在 众多的工程领域有着广泛的应用，下面基于代数工具描述。 设r 为有限环乙( 聊2 ) 或有限域e ，记厂= l ri ，设玎为正整数，r 上的一个 以级移位寄存器( s h i f tr e g i s t e r ，简称移存器) 如下图所示。图中s ，是，最为，z 个存储单元，每个存储单元可存放火中的一个元素。在任一时刻s ，& ，最的值 称为该反馈移位寄存器的状态，共有r ”种可能的状态，( s ，是，鼠) 称为反馈移 位寄存器的初始状态，存储单元的个数门称为反馈移位寄存器的级数。布尔函数 厂( s ，是，鼠) 是状态( s ，是，瓯) 的函数，被称为反馈移位寄存器的反馈函数。 朱莉艳：流密码复杂性研究 图( 4 ) 移位寄存器工作原理 悃悃p 惆佃输訾锨蒯 当厂( s ，& ，瓯) 为非线性函数时，该反馈移位寄存器称为非线性反馈移位寄 存器；当厂( s ，逆，最) 为线性函数时，该反馈移位寄存器称为线性反馈移位寄存 器( l i n e a rf e e d b a c ks h i f tr e g i s t e r ) 。没经过一个移位脉冲，寄存器的每一位 的内容向右移动一位，不断地加上一位脉冲，移位寄存器的输出就变成了一个无 限的序列s ，是，瓯，显然这个序列满足如下的递归关系： 最+ 女= 厂( s ，瓯小，瓯+ ) ，尼 o 由此可见，上述反馈移位寄存器序列是由它的初始状态( s ，曼，瓯) 和反馈 函数( 枣) 唯一确定的。特别的，该移位寄存器的状态转移规律 ( 瓯，瓯小，& + 川) 一( 瓯小最+ ：，s + 。) 完全是由函数厂( 水) 确定的。 1 5 线性反馈移位寄存器 大多数密钥流产生器使用的都是线性反馈移位寄存器( 以下简记为l f s r ) ，主 要有以下方面的原因： 1 l f e r 适合硬件的实现； 2 l f s r 能产生大周期的序列； 3 l f s r 能产生具有很好统计特性的序列； 4 易于使用代数工具进行分析。 扬州人学硕士学位论文 1 2 l f s r 的输出序列可通过研究l f s r 的特征多项式得到。 定义1 5 1 口1 ：设，z 级l f s r 的输出序列为 s ) ，线性反馈函数 厂( s ，最) = e s + g 一。是+ + c 1 鼠 则多项式以( x ) = c 0 + c 1x + c 2 x 2 + + e l _ 1 + e x ”为该l f s r 的特征多项式 ( c 0 = g = 1 ) 。如果仇( x ) 的阶为刀，则称l s f r 是正则的。 定理1 5 2 h 1 ：若) 是卯( 2 ) 上的玎次多项式，也是序列 s ) 的特征多项 式，且有( x ) l ( ，+ 1 ) ，则 s ) 的周期，满足，i 聊。 定理1 5 3 4 l ：胛级l f e r 产生的状态序列有最大周期2 ”一l 的必要条件是其特 征多项式不可约。 定理1 5 4 h 1 ：若只( x ) 是不可约多项式，且存在只( x ) l ”+ 1 ) ，但对于任意 正整数尼 聊，( x ) 不整除矿+ 1 ，则由( x ) 产生的序列 s ) 的周期为聊。 定义1 5 5 h 1 ：所谓以次本原多项式见( x ) 是满足下列两个条件的不可约多项 式：1 ) 见( x ) ix 2 ”一1 + 1 ； 2 ) 对v d ， d2 刀一1 ，都有见( x ) 十一+ 1 ； 定义1 5 6 h 3 ：如果一个门级线性反馈移位寄存器输出序列的周期最大，为 2 ”一l ，这样的序列称为朋一序列。 定理1 5 7 h 1 ：氍) 为m 一序列的充要条件是只( x ) 为本原多项式。 聊一序列是流密码中使用最广泛的序列，也是一类研究比较成熟的序列，在 舒( 2 ) 上的甩级历一序列的数目有2 2 ”1 一胛个 4 ，聊一序列必循环遍历所有2 ”一1 个 状态，不同的聊一序列只能是这些状态的不同排列。特别地，如果l f s r 的一个输 出序列是所一序列，则它的所有非o 输出序列对应同一个朋一序列。 朱莉艳：流密码复杂性研究 2 二进周期序列的复杂度分析 一般地，流密码中以二进序列作为密钥流序列可以用来加密信息 1 1 ，在应 用中发现密钥流序列要有随机性，有很大的周期，和统计性等。其中随机性中有 两个重要的准则：线性复杂度和非线性复杂度。线性复杂度定义为产生密钥流序列 的最短的线性移位寄存器的长度。非线性复杂度定义为产生密钥流序列的最短移 位寄存器的长度。 现在的研究一般集中考虑线性复杂度，在计算线性复杂度时也提出了很多的 算法，其中著名的例如：b e r l e k a m p m a s s e y 算法 5 ，g a m e s c h e n 6 算法等，另 一方面，序列的线性复杂度虽然很大，但是却可以由较小长度的非线性移位寄存 器产生。因此研究序列的非线性复杂度也是很重要的。j a n s e n 、b o e k e e 在 7 中， r i z o m i l i o t i s 、k a l o u p t s i d i s 在 8 中都考虑了序列的非线性复杂度的问题， r i z o m i l i o t i s 在 9 中考虑了对于给定非线性复杂度的序列，其非线性复杂度达到 最大的条件。 本章内容考虑了给定非线性复杂度的值的周期序列的设计，通过计算机搜索 给出了一些具有最小非线性复杂度的周期序列的形式。此外给出一类特殊的序列 的非线性复杂度和线性复杂度。 2 1 周期序列的线性复杂度和极小多项式 设譬上s 。= s ) 脚，s 。的生成函数为彳( x ) = 岛+ + sx + = s x 。若 s 周期为， 贝。有s = 孓，s ，乳一。) ， 么( 石) = 查蔓二二圣! 气 笋。 特另i j 地， 彳( x ) 可以表示成有理函数罗苦，其中厂( x ) ，c ( x ) x 】， d e g c ( x ) d e g 厂( x ) ， g c d ( 厂( z ) ，c ( x ) ) = 1 。称厂为s 的极小多项式。 扬州大学顾十学位论文 1 4 _ 一 令g c d ( s v ( x ) ，l x ) 为冒 z 上两个多项式的最大公因子，则显然有s 的线性 复杂度 11 l c ( s ) = d e g ( f ( x ) ) = d e g ( 1 一x ) 一d e g ( g c d ( s 1 ( x ) ，l x ) ) ， 极小多项式为f ( x ) = 1 一x 面蕊i i i i 菇7 巧一x ) 。 2 2 周期序列s 的复杂度 考虑有限长度的二进序列s = 氐，s ，& 一。) ，其中s e 。 定义2 2 1 西1 ：布尔函数：fj e ，其中e = o ，1 ) ，则厂有唯一的多项式 表示，在e 中称为代数正规形式，记为厂的a n f 表示。 厂( 而，屯，) = + q 薯+ 口l ，一_ + + q 2 。五， ，= l l s ， ，也称口为在。上的本 原元。 定义3 1 2 n 引：令口是上的本原元，则口生成巧( 的乘法群) ，记为 巧= 。巧是包含所有口的幂的循环群。则x 的阶为七，定义为满足= p 的 最小的正整数七，其中e 是e 中的单位元。设x = 口，对某些f ，则 o ，j 沈，( x ) = d ，j ( 昆，( c z ) g c d ( f ，d ，c 拓，( c r ) ) 。 引理3 1 3 ：令x 为有限域乞。中的非零元，刀是满足g c d ( ，z ，p ”一1 ) = 1 的正整 数，则有x 和在哆中有相同的阶。 扬州人学硕士学位论文 2 0 证明：令口为。上的本原元，则口生成巧，且有口的阶为p ”一1 。存在某些 f ，使得x = 口，则有 d ，i 沈，( x ”) = ( p ”一1 ) g c d ( 刀f ，p ”一1 ) = ( p 朋一1 ) g c d ( f ，p ”一1 ) = d ，i 沈厂( x ) 。 口 定义3 1 4 n 7 1 ：令k 为特征为p 的有限域，行为满足p 干刀的正整数，f 为k 上 的玎次本原单位根，则多项式 。( x ) = 兀( x f 3 ) s = l g c d ( j ，”) = l 称为k 上的胛阶分圆多项式。 注：显然。 ) 不依赖于本原单位根f 的选取，且d e g ( 西。( x ) ) = 缈( 力) 。 定理3 1 5n 7 1 ：设k 为特征为p 的有限域，疗为正整数且p 干刀，则： 1 ) ，一1 = 兀d ( x ) ； c ，i 2 ) 。( z ) 的系数一定是k 的素域中的元素，而且在k 的素域是有理数的情况下甚 至都是整数。 3 2 b e r l e k a m p m a s s e y 算法( 简称b m 算法) b e r l e k 觚1 p m a s s e y 算法是由j l m a s s e y 在1 9 6 9 年提出的，是确定长有限二 进序列s 的线性复杂度的有效算法，其核心思想是归纳地求出一系列线性移位寄 存器 ，d e g ( z ) ) 厶，聆= 1 ，2 ，使得每个线性移位寄存器 均是生成给定序列& ，s ，晶一前，z 位氐，s ，最一。的最短线性移位 寄存器，从而 即为所求。算法描述如下： 算法3 2 1 嘲：设s = ( 氐，s ，瓯一。) 是一个长度为的二进序列，用 朱莉艳：流密码复杂性研究 2 1 表示特征多项式为z ( x ) ，并且线性复杂度为乙的移位寄存器序列， ，z = 1 ，2 ，。称 为s 。的线性综合解。 ( 1 ) 存在o ， 使得& = s = = 瓯一。= o ，o 。 令 哦= 吐= = 一，= o ， 氏5k ， 石( x ) = 以( x ) = 2 ( x ) = 1 ， = 如= = 乙= o 。并且任取一个+ 1 级线性移位寄存器 ，可取 厶+ 。( x ) = 1 一氏妒“，乙+ 。2 + 1 。 ( 2 ) 递归算法：假设对每个刀， 刀 ，己求出 ( 1 f ，z ) ， 其中= 乞= = 乙 乙+ 。乙+ ：厶，z ( x ) = 1 + e ，x + + q ，计算第刀步 的差值以= 瓯+ e ，- 鼠一- + g ，：最一：+ e ，邑一，分下列两种情况： 1 ) 若瓯= o ，则z + 。( x ) = z ( x ) ，乙+ ，= 乙； 2 ) 若吃o ，这时有聊( 1 聊 刀) 使得乙 乙+ l = k 2 = = 乙。 令+ l ( x ) = z ( x ) 一吃1 x ”一”厶( x ) ，乙+ 1 = m a x 乙，z + 1 一乙) 。 由此算法得到的 就是生成序列& ，s ，s 一，的一个最短的线性移位寄 存器，序列的线性复杂度即为0 。 下面就b m 算法生成给定序列的最短线性移位寄存器的唯一性给出条件。 定理3 2 2 3 ：对于给定长二进序列氐，s ，& - l ，假定生成该序列的最短 线性移位寄存器的级数为，则生成该序列的最短线性移位寄存器唯一存在的充 分必要条件是：0 2 。 推论3 2 3 口3 ：设k 是生成序列& ，s ，一，的最短线性移位寄存器的级数， 且f 2 ，则这个最短级数的线性移位寄存器是唯一的。 扬州人学硕士学位论文 3 3g 锄e s c h a n 算法及其推广算法： g 锄e s c h e n 提出了对周期= 2 ”的二进序列的线性复杂度的快速算法 6 ，其 时间复杂度仅需d ( ) 。丁存生 1 3 将该算法推广到对有限域o ( p 为素数) 上的 周期为p ”的序列的线性复杂度的计算。 定理3 3 1 嘲：设s = ( & ，s ，& ，) 是周期为2 ”的二进序列，s 的周期表示为 s = ( & ，s ，一。) 。 令三= ( & ，s ，& ，2 - 1 ) ，r = ( 瓯& m l ，一，晶一1 ) ，6 = 三+ r 。若6 = o ， 则z ( x ) = 彳l ) ( z ) ，因而c ( s ) = 三c ( ( 三) ) ；否则，z ( x ) = ( 1 一x ) 川2 彳。) ( x ) ，因而 三c ( s ) = 2 + 三c ( ( 6 ) ) ，这里( 三) 和( 6 ) 分别表示为第一个周期为三和6 的周期序 列。 算法3 3 2 ( g 鲫e s c h a n ) 算法蚴：设周期为= 2 ”的二元序列s = ( s ，s ，) ， 令a = ( 口0 ，q ，q 一。) ，计算s 的线性复杂度和极小多项式的算法如下： 初始值：，卜，口卜s ，三c 卜o ，厂卜l ； s t e p l ：如果，= 1 ，转向s t e p 2 ：否则，卜，2 ，三= ( ，q ，口f 一1 ) ， r = ( 口，q + l ，口2 ) ，6 卜三+ r ，转向s t 印3 ； s t e p 2 ：如果口= ( o ) ，停止；否则，三c 卜三c + 1 ，厂卜厂宰( 1 一z ) ，停止； s t e p 3 ：如果6 = ( 0 ，o ) ，则口卜三，转向s t e p l ；否则口卜6 ，三c 卜三c + ， 厂卜厂水( 1 一x ) 7 ，转向s t e p l 。 结果：最终可得s 的线性复杂度c ( s ) = 三c ，s 的极小多项式z = ( 1 一x ) 比。 丁存生 1 3 将g a m e s c h a n 算法推广为上周期为的序列的线性复杂度算 朱莉艳：流密码复杂性研究 法，这里p 是素数，g = p ”。 2 3 定理3 3 3 n 3 3 ：设s = ( 瓯，s ，是，) 是卯( g ) 上周期为p ”的序列，这里p 是素 数，g = p ”，s 的周期表示为s 。v = ( 瓯，s ，一。) 。令 4 = ( j - 1 ) 矿- ，薯川一，- 一一，) ，f = 1 ，2 ，p ，6 = 4 + 4 + + 4 。 1 ) 若6 o ，贝u z ( 石) = 石6 ) ( z ) ( 1 一z ) p - 1 矿一，因而 三c ( s ) = 三c ( ( 6 ) ) + ( p 一1 ) p ”一； 2 ) 若6 = o 且4 = 4 = = 彳p ，则z ( x ) = ) ( x ) ，因而c ( s ) = 三c ( ( 4 ) ) ； 3 ) 若6 = o 且4 = 4 = = 4 不成立，则 z ( x ) = ( 1 一x ) p 一1 p g c d ( ( 1 一x ) p 一1 ) p ”1 ，彳( x ) ) ， 这里彳= ( 4 ，4 + 4 ，4 + 4 + + 4 一。) ，6 = 4 + 4 + + 4 ，( 4 ) 和( 6 ) 分别 表示为第一个周期为4 和6 的周期序列。 算法3 3 4 n 驯：设s = ( & ，s ，) 是e 上周期为p ”的序列，其中p 是素数， g = p ”。则计算s 的线性复杂度和极小多项式的算法如下： 初始值：，卜，口卜s ，三c 卜0 ，卜1 ； s t e p l ：如果z = 1 ，转向s t e p 2 ：否则，卜，p ，4 = ( q f - 1 ) f ，q f _ 1 ) ，+ 1 ，嘞一1 ) ， 江1 ，2 ，p ，6 卜4 + 4 + + 4 ，彳卜( 4 ，4 + 呜，4 + 4 + + 4 1 ) ，转向 s t e p 3 ； r s t e p 2 ：如果a = ( 0 ) ，停止；否则，上c 卜三c + 1 ，厂卜厂乖( 1 一x ) ，停止； s t e p 3 ：如果6 = ( 0 ，o ) ，则口卜彳，卜p 一1 ，转向s t e p 4 ；否则口卜6 ， 三c 卜三c + ( p 一1 ) ，厂卜厂木( 1 一x ) ，一1 ) ，转向s t e p l 。 s t e p 4 ：如果r = 1 ，转向s t e p l ；否则，4 = ( 口( h ) ，q h ) ，+ 1 ，嘞一1 ) ，f ：1 ，2 ， 6 卜4 + 4 + + 4 ，彳卜( 4 ，4 + 4 ，4 + 4 + + 4 一1 ) ，转向s t e p 5 ； s t e p 5 ：如果6 = ( o ，o ) ，则口卜彳，卜，一1 ，转向s t e p 4 ；否则口卜6 ， c 卜三c + ，厂卜宰( 1 一x ) 一，转向s t e p l 。 结论：最终可得到s 的线性复杂度三c ( s ) = 三c ，s 的极小多项式z ( z ) ：( 1 一z ) 垢。 3 4x i a o w r e i l 锄i m a m u r a 算法： x i a o - w 色i _ l 锄- i m 锄啪提出了对有限域卯( g ) 上周期为p ”的序列的线性复 杂度的快速算法，其中p 是奇素数，g 是素数且是模p 2 的本原根。 定理3 4 1 n 4 | ：设s = ( & ，s ，最，) 是卵( g ) 上周期为p 一的序列，这里p 是 模p 2 的本原根，s 的周期表示为s = ( & ，s ，瓯一。) 。令 4 = ( & f - l 钔& 川_ i + 。，。一1 ) ，f = 1 ，2 ，p 1 ) 若42 4 = = 4 ，则z ( z ) = ) ( 力，因而三c ( s ) = 三c ( ( 4 ) ) ； 2 ) 否贝0 z ( z ) = 彳。) ( z ) ( 石) ，贝i j 三c ( s ) = 三c ( ( 6 ) ) + ( p 一1 ) p 一；其中 6 = 4 + 4 + + 4 ，( 4 ) 和p ) 分别表示为第一个周期为4 和6 的周期序列。 算法3 4 2 口4 | ：设s = ( 氐，s ，) 是上周期为p ”的序列，其中p 是素数，g 为模p 2 的本原根。则计算 s r 的线性复杂度和极小多项式的算法如下： 初始值：，卜，口卜5 r ，三c 卜0 ，卜1 ； s t e p l ：如果，= 1 ，转向s t e p 2 ：否则，卜，p ，转向s t e p 3 ； 查塾丝! 堕童塑墨銎丝塑窒竺 一一 s t e p 2 ：如果口：( o ) ，停止；否则，三c 卜三c + 1 ，卜木( 1 一功，停止； s t e p 3 ：令