《密码学02－流密码》由会员分享，可在线阅读，更多相关《密码学02－流密码（90页珍藏版）》请在金锄头文库上搜索。
1、辟定干滤誉灌林滇佩贴设庸餐饯买即钢子狗看帮趟蒲坊下辣恢缀挑板瓷注密码学02流密码密码学02流密码本科生必修课：现代密码学本科生必修课：现代密码学第二章第二章 流密码流密码主讲教师：董庆宽研究方向：密码学与信息安全Email ：个人主页：http:/ 2.1 流密码的基本概念流密码的基本概念布尔函数简介布尔函数简介2.2 2.2 线性反馈移位寄存器线性反馈移位寄存器2.3 2.3 线性移位寄存器的一元多项式表示线性移位寄存器的一元多项式表示 2.4 2.4 m m序列的伪随机性序列的伪随机性2.5 2.5 m m序列密码的破译序列密码的破译2.6 2.6 非线性序列非线性序列本章提要本章提要览掷
2、吮柠剑咐画灼抡剁袱奎当来拆瞄杯窘个取治桶识积疡腊挚门正废渭韵密码学02流密码密码学02流密码2流密码概况流密码概况流密码流密码(stream cipher)是一种重要的密码体制是一种重要的密码体制l明文消息按字符或比特逐位加密明文消息按字符或比特逐位加密l流密码也称为序列密码流密码也称为序列密码(Sequence Cipher)流密码在手工和机械密码时代是主流技术流密码在手工和机械密码时代是主流技术流密码在流密码在50年代得到飞跃式发展年代得到飞跃式发展l密钥流可以用移位寄存器电路来产生，也促进了线性和密钥流可以用移位寄存器电路来产生，也促进了线性和非线性移位寄存器发展非线性移位寄存器发展主要
3、用于专用和机密机构：军方，银行等主要用于专用和机密机构：军方，银行等l由于互联网是分组传输的，流密码的使用较少由于互联网是分组传输的，流密码的使用较少攀话相吩寨箱级减陨境晾绣牲径太灌欠傻宅赴蜀胳砰充思强珍渤烧捻见杨密码学02流密码密码学02流密码3流密码具有有效的数学分析工具流密码具有有效的数学分析工具l代数代数(如布尔代数如布尔代数)、有限域理论和谱分析理论等等、有限域理论和谱分析理论等等l流密码在现代密码学阶段的主要成果来自于密码分析流密码在现代密码学阶段的主要成果来自于密码分析很多密码学家因流密码研究而成名很多密码学家因流密码研究而成名l肖国镇，肖国镇，Massey，Berlikamp等
4、。等。l在在IEEE Transaction on Information Theory上能够发表的密码上能够发表的密码成果多数都是来自于流密码的相关研究成果多数都是来自于流密码的相关研究流密码基于硬件实现优势更明显，目前也有些算法是针对流密码基于硬件实现优势更明显，目前也有些算法是针对软件设计的软件设计的l如如Ecrypt计划中的算法，计划中的算法，RC4等等参考资料参考资料：伪随机序列及其应用，流密码学及其应：伪随机序列及其应用，流密码学及其应用，肖国镇著用，肖国镇著慌苍箭掐魏擎搀办幌匈盏胜劣鲸仕包糖赌恩怯枕鄂稍隅兰诚需屁挞撮韧浇密码学02流密码密码学02流密码42.1 流密码的基本概念流
5、密码的基本概念流密码的基本思想流密码的基本思想l利用密钥利用密钥k产生一个密钥流产生一个密钥流z=z0z1z2，并使用如下规则，并使用如下规则对明文串对明文串x=x0x1x2加密：加密： y=y0y1y2Ez0(x0)Ez1(x1) Ez2(x2)，密钥流密钥流l由密钥流发生器由密钥流发生器 f 产生：产生：zif(k,i)li是加密器中的记忆元件在时刻是加密器中的记忆元件在时刻 i 的状态的状态l f 是由是由k, i 产生的函数产生的函数喳樊蹬炙荷缚宏爪钨槐悬介辩苛宠碉轰漫拈癣千运味迈奈绪抖圾扇茨棕狙密码学02流密码密码学02流密码5 流密码流密码 分组密码分组密码内部记忆元件由一组移位寄
6、存器构成内部记忆元件由一组移位寄存器构成 冠陛誊擅踊谁茶眶售誓疽儿雪石蓄运民剩姆彪叔妊成柄榷逮轩斟俩宪滞僻密码学02流密码密码学02流密码6流密码与分组密码的区别：在于有无记忆性流密码与分组密码的区别：在于有无记忆性l流密码的滚动密钥由函数流密码的滚动密钥由函数f、密钥、密钥k和指定的初态和指定的初态0完全确定完全确定l此后由于输入加密器的明文可能影响加密器中的内部记此后由于输入加密器的明文可能影响加密器中的内部记忆元件的存储状态，因而忆元件的存储状态，因而i (i0)可能依赖于可能依赖于k，0，x0，x1，xi1，前前 i 个个明文和密钥及初态明文和密钥及初态l分组密码中，一组一组的加密，一
7、般等长分组密码中，一组一组的加密，一般等长l在分组内明文和密钥充分混淆，分组间一般互不影响，在分组内明文和密钥充分混淆，分组间一般互不影响，与分组连接模式有关与分组连接模式有关元掸迁株钩抛础夫虞湃啮务肥桥瞧厌芭邮娶蒂巾存诽耻巨葬狼件净赢谜凤密码学02流密码密码学02流密码72.1.1同步流密码同步流密码流密码可按记忆元件存储状态分类流密码可按记忆元件存储状态分类l按照加密器中记忆元件的存储状态按照加密器中记忆元件的存储状态i 是否依赖于输入的是否依赖于输入的明文字符流明文字符流，流密码可进一步分成，流密码可进一步分成同步同步和和自同步流密码自同步流密码两种两种li 独立于明文字符流的叫做同步流
8、密码，否则叫做自同独立于明文字符流的叫做同步流密码，否则叫做自同步流密码步流密码l由于由于自同步流密码的密钥流的产生与明文有关自同步流密码的密钥流的产生与明文有关，所以理论上难，所以理论上难于分析。于分析。l好的密码算法应该好的密码算法应该在理论上或基于实践检验能够证明其是安全在理论上或基于实践检验能够证明其是安全的或至少是没有明显漏洞的的或至少是没有明显漏洞的。l如果算法难于分析，则无法保证其安全性，也就无法放心使用，如果算法难于分析，则无法保证其安全性，也就无法放心使用，因此自同步流密码研究很少，很少采用。因此自同步流密码研究很少，很少采用。镜沙疵救求疼赞仪层抛眺试曾侨疗斜酚恶巷迅意厉缚须
9、古乒整臼篇徊销妆密码学02流密码密码学02流密码8目前大多数研究成果都是关于同步流密码的目前大多数研究成果都是关于同步流密码的l由由于于zif(k,i)与与明明文文无无关关，此此刻刻的的密密文文字字符符yi=Ezi(xi)也也不不依依赖赖于于此此前前的的明明文文字字符符，这这样样可可将将同同步步流流密密码码的的加加密器分成密器分成密钥流产生器密钥流产生器和和加密变换器加密变换器两个部分。两个部分。l设解密变换为设解密变换为xi=Dzi(yi)。同步流密码体制模型如下图。同步流密码体制模型如下图芭裕撒掇惑忻疗锻竭憎憾冰浚鬼朗窟蕴围苫严弃人挡脚董弦菜块近少事桂密码学02流密码密码学02流密码9加密
10、变换加密变换Ezi可有多种选择，保证变换可逆性即可可有多种选择，保证变换可逆性即可l比如明文流和密钥流对应位异或比如明文流和密钥流对应位异或l实际数字保密通信系统一般都是二元的实际数字保密通信系统一般都是二元的0,1,在有限域在有限域GF(2)上讨论上讨论二元加法流密码二元加法流密码是目前最常用的流密码体制是目前最常用的流密码体制l加密变换可表示为加密变换可表示为yizi xi，加法流密码体制模型加法流密码体制模型金其存贵您炽孝虽菌苞冒黑初忱叠酬珊坷月跑坤吠稼防券卧欧颈曲纱述托密码学02流密码密码学02流密码10一次一密密码一次一密密码(One Time Padding 一次一密乱码本一次一密
11、乱码本)是加法是加法流密码的原型流密码的原型l其中密钥的长度至少和明文的长度一样长，是无条件安全的，但其中密钥的长度至少和明文的长度一样长，是无条件安全的，但实用性较差，因而不能广泛应用。实用性较差，因而不能广泛应用。l如果加法流密码中，如果加法流密码中，ziki，即直接将密钥，即直接将密钥k(k至少和明文一样长至少和明文一样长)用作滚动的密钥流，则加法流密码就是一次一密密码。用作滚动的密钥流，则加法流密码就是一次一密密码。流密码体制中如果密钥有限，则安全性一般低于一次一密流密码体制中如果密钥有限，则安全性一般低于一次一密l从信息论意义上讲，对从信息论意义上讲，对k比特长的串进行任何固定变换，
12、其信息量比特长的串进行任何固定变换，其信息量至多为至多为k比特，即密钥流再长，其安全性最大也就是密钥长度，而比特，即密钥流再长，其安全性最大也就是密钥长度，而一次一密的密钥长度至少和明文一样。一次一密的密钥长度至少和明文一样。同步流密码算法的设计主要是密钥流产生器的设计同步流密码算法的设计主要是密钥流产生器的设计l密钥产生器目标是：使得密钥密钥产生器目标是：使得密钥k经其扩展成的密钥流序列经其扩展成的密钥流序列z具有如下具有如下性质：性质：l极大的周期，良好的统计特性，抗差分分析，抗线性分析等极大的周期，良好的统计特性，抗差分分析，抗线性分析等呀苍嚷小琅派阻煌嚏妄冈蛊缘嘻炭滋秽娶泡谈介弹索烽拾
13、悯惰唤侧汕邱华密码学02流密码密码学02流密码112.1.2 有限状态自动机有限状态自动机流密码中任意时刻流密码中任意时刻密钥流密钥流和和密文密文的输出与状态密切的输出与状态密切相关。可以用有限状态自动机这一数学模型来表述相关。可以用有限状态自动机这一数学模型来表述有限状态自动机是具有离散输入和输出有限状态自动机是具有离散输入和输出（输入集和（输入集和输出集均有限）输出集均有限）的一种数学模型的一种数学模型，由，由3部分组成：部分组成：l有限状态集有限状态集S=si|i=1,2,l 共有共有l个可能状态个可能状态l有限输入字符集有限输入字符集A1=Aj(1)| j=1,2,m和有限输出字符集和
14、有限输出字符集A2=Ak(2)| k=1,2,n。l转移函数转移函数:lAk(2)=f1(si, Aj(1)，sh=f2(si, Aj(1)l即在状态为即在状态为si，输入为，输入为Aj(1)时，输出为时，输出为Ak(2)，而状态转移为，而状态转移为sh。捆悼泛乍毕伤括听饼颊学加靠烛敖晌盲蛙向桥溉裔达誉州扣棋豪拓振绩插密码学02流密码密码学02流密码12【例【例21】lS=s1,s2,s3，lA1=A1(1),A2(1),A3(1)，A2=A1(2),A2(2),A3(2),转转移移函函数由表数由表21给出给出f1A1(1)A2(1)A3(1)s1A1(2)A3(2)A2(2)s2A2(2)A
15、1(2)A3(2)s3A3(2)A2(2)A1(2)f2A1(1)A2(1)A3(1)s1s2s1s3s2s3s2s1s3s1s3s2询峙建钒况角杠涝聋勇眨砧吻映斟伯经邀蚁属碌馆狂但纺缆枫许沟洒贰罐密码学02流密码密码学02流密码13有限状态自动机可用有向图表示，称为转移图有限状态自动机可用有向图表示，称为转移图转移图的顶点对应于自动机的状态转移图的顶点对应于自动机的状态l若若状状态态 si在在输输入入Ai(1)时时转转为为状状态态sj，且且输输出出一一字字符符Aj(2)，则则在在转转移移图图中中，从从状状态态si到到状状态态 sj有有 一一 条条 标标 有有(Ai(1), Aj(2)的的有有
16、向弧线，如图向弧线，如图巡波纤所虎凿谢决魂霸间洲剑洼渔淌子谐膝间送舶烯苞雁善纵浆盖舞胎苍密码学02流密码密码学02流密码14在例在例21中，若中，若l输入序列为输入序列为A1(1)A2(1)A1(1)A3(1)A3(1)A1(1)l初始状态为初始状态为s1，l则得到状态序列为：则得到状态序列为：l输出字符序列为：输出字符序列为：s1s2s2s3s2s1s2A1(2)A1(2)A2(2)A1(2)A3(2)A1(2)继投卤捶录绎熟曳瓣斜唇录贯峙辉宗佬铱疥眠桥蔗行氯判往刽痢笆瓣稿征密码学02流密码密码学02流密码152.1.3 密钥流产生器密钥流产生器同步流密码的关键是密钥流产生器同步流密码的关键
17、是密钥流产生器(Key Generator)l一般可将其看成一般可将其看成一个参数为一个参数为k的有限状态自动机的有限状态自动机，由一个输出符号，由一个输出符号集集Z、一个状态集、一个状态集、两个函数、两个函数和和以及一个初始状态以及一个初始状态0 0组成组成l状态转移函数状态转移函数：i ii i+1+1，将当前状态，将当前状态i i变为一个新状态变为一个新状态i i+1+1l输出函数输出函数: : i iz zi i，当前状态，当前状态i i变为输出符号集中的一个元素变为输出符号集中的一个元素z zi i。密钥流生成器设计的关键在于密钥流生成器设计的关键在于l找出适当的状态转移函数找出适当
18、的状态转移函数和输出函数和输出函数，使得输出序列，使得输出序列z满足密钥满足密钥流序列流序列z应满足的几个条件，并且要求在设备上是节省的和容易实应满足的几个条件，并且要求在设备上是节省的和容易实现的。为了实现这一目标，必须采用现的。为了实现这一目标，必须采用非线性函数非线性函数 坏廉找臃籍卿鹃落刚殃笑姥拆荐镶埋立口部垄妊瑟间煞只戚影捶绪唱庚纶密码学02流密码密码学02流密码16由于由于具有非线性的具有非线性的的有限状态自动机理论很不完善的有限状态自动机理论很不完善，相，相应的密钥流产生器的分析工作受到极大的限制。应的密钥流产生器的分析工作受到极大的限制。相反地，当相反地，当采用线性的采用线性的
19、和非线性的和非线性的时，将能够进行深时，将能够进行深入的分析并可以得到好的生成器。入的分析并可以得到好的生成器。l为方便讨论，可将这类生成器分成为方便讨论，可将这类生成器分成驱动部分和非线性组合驱动部分和非线性组合部分部分l驱动部分驱动部分控制生成器的状态转移，并为非线性组合部分提供统计控制生成器的状态转移，并为非线性组合部分提供统计性能好的序列；性能好的序列；l非线性组合部分非线性组合部分要利用这些序列组合出满足要求的密钥流序列。要利用这些序列组合出满足要求的密钥流序列。叔涣框术愁都兰嘎俯障殿缀援袭姑熊玻林良要蛇钮钻蜒啼垣丙灭威露残慑密码学02流密码密码学02流密码17目前最为流行和实用的密
20、钥流产生器如图所示，其目前最为流行和实用的密钥流产生器如图所示，其驱动部分是一个或驱动部分是一个或多个线性反馈移位寄存器多个线性反馈移位寄存器。l前者称为滤波生成器，或前馈生成器前者称为滤波生成器，或前馈生成器l后者称为非线性组合生成器后者称为非线性组合生成器l还有钟控生成器，缩减生成器，停走生成器等还有钟控生成器，缩减生成器，停走生成器等l在非线性生成器中介绍在非线性生成器中介绍耙古臆增革姨葫花己烈骡签抛咽衍杯邦碧鞘狮玄哟矗庆棠造铂壕债鸭型藏密码学02流密码密码学02流密码18密钥流序列密钥流序列z应满足的几个条件：应满足的几个条件：一般来说，一般来说，KG(密钥产生器密钥产生器)的输入的输
21、入(种子密钥种子密钥k)是较短的，其输出为周期序列是较短的，其输出为周期序列l对于二元序列，如果种子密钥对于二元序列，如果种子密钥k为为n比特，则其周期最大比特，则其周期最大为为2nl因为一旦密钥产生器的某一时刻的存储状态与前面的某一时刻因为一旦密钥产生器的某一时刻的存储状态与前面的某一时刻的状态相同，则在其它参数不变的情况下，输出开始重复的状态相同，则在其它参数不变的情况下，输出开始重复l这个重复周期太小则不安全这个重复周期太小则不安全l希望一个周期的长度很长，这样在加密有限的明文时只希望一个周期的长度很长，这样在加密有限的明文时只需要一个周期内的某个片断，就像真随机的一样需要一个周期内的某
22、个片断，就像真随机的一样灿僚谩榷壹廷腻甲措伐颜沟枫烩胚脉痰裔尤欢侠枯估诊镶昌硒较欢鸽眺舜密码学02流密码密码学02流密码19基于以上考虑，密钥产生器目标是：使得密钥基于以上考虑，密钥产生器目标是：使得密钥k经其扩展经其扩展成的密钥流序列成的密钥流序列z具有如下性质：具有如下性质：种子密钥的长度种子密钥的长度（一般来说就是流密码的密钥长度）（一般来说就是流密码的密钥长度）足够长足够长l比如比如128比特，这样密钥空间将有比特，这样密钥空间将有2128规模，抗穷搜索攻击规模，抗穷搜索攻击极大的周期极大的周期：一般来说不应小于：一般来说不应小于255良好的统计特性良好的统计特性l密钥流序列密钥流序列
23、k具有均匀的具有均匀的n-元分布，即在一个周期环上，某特定形元分布，即在一个周期环上，某特定形式的式的n-长长bit串与其求反，两者出现的频数大抵相当串与其求反，两者出现的频数大抵相当(例如，均匀的例如，均匀的游程分布游程分布) 襄了皂敏嚷烫信紫埃屯头蝉配攀敲豪战烂乾怎英枫理脑犊魂拓艺视圆互还密码学02流密码密码学02流密码20密钥流序列密钥流序列z不可由一个低级的不可由一个低级的LFSR产生，也不可与一产生，也不可与一个低级个低级LFSR产生的序列只有比率很小的相异项产生的序列只有比率很小的相异项；l如果密钥流序列周期为如果密钥流序列周期为n，而人为改变其，而人为改变其1比特后周期急剧变小，
24、比特后周期急剧变小，例如变为例如变为n/t，则序列的安全性就大为减小。，则序列的安全性就大为减小。抗统计分析抗统计分析l利用统计方法由密钥流提取关于利用统计方法由密钥流提取关于KG结构或结构或k的信息在计算上不可的信息在计算上不可行；行；混乱性混乱性. 即即z的每一的每一bit均与均与z的大多数的大多数bit有关；有关；扩散性扩散性. 即即z任一任一bit的改变要引起的改变要引起z在全貌上的变化。在全貌上的变化。抗线性分析抗线性分析l其中的其中的LSFR就是线性反馈移位寄存器，就是线性反馈移位寄存器，linear shift feedback register，在下一节介绍，在下一节介绍蓄技逸
25、题命合敦纂咸责俏堕颐哭感鸟食亚避之懊藐署姐好案梆瓤视佬亥摸密码学02流密码密码学02流密码21布尔函数简介布尔函数简介n元布尔函数元布尔函数f(x1,xn)定义为定义为f：F2nF2l表示方法有三种：逻辑关系式，真值表，多元多项式表示方法有三种：逻辑关系式，真值表，多元多项式多元多项式：如多元多项式：如 f(x1,x2,x3,x4)x1x2x3x4l异或异或 x1 x2 x1x2 (在在GF(2)上的上的“”(模模2加加)l逻辑逻辑“与与” x1 x2 x1x2 (GF(2)上的上的“乘法乘法”)l逻辑逻辑“或或” x1 x2 x1x2+x1x2 其真值表为：其真值表为：l非非 1x l幂幂
26、xtxxx=x t0lx0=1;布尔函数的高次项只有如下形式布尔函数的高次项只有如下形式lxi1xi2xikx1x2x1 x2000011101111虑腰握挟拈讯茁矗编筐煤翼切拖杆愈酉焦奥这膨投茁郊榔伦绍貌皮扛锌榨密码学02流密码密码学02流密码22布尔函数的重量布尔函数的重量W(f)：真值表中函数值列里：真值表中函数值列里”1”的个数的个数lf(x1,x2)x1 x2 = x1x2+x1x2的重量的重量W(f)3布尔函数的次数布尔函数的次数lf(x1,xn)a0一个乘积项一个乘积项 的次数定义为的次数定义为r最大次数定义为布尔函数的次数最大次数定义为布尔函数的次数 def(f)def(f)1
27、时，称为仿射函数时，称为仿射函数 ：f(x1,xn)a0l若仿射函数的常数项若仿射函数的常数项a00，则称为线性函数，则称为线性函数def(f)1时，称为非线性函数时，称为非线性函数郁鞠别班豌卉嫩械端差谆挤爱帖邹叶这将帮棺眷样津戍副趁邯藏谦闽郸衰密码学02流密码密码学02流密码232.2 线性反馈移位寄存器线性反馈移位寄存器移位寄存器是序列密码产生密钥流的一个主要组成部分移位寄存器是序列密码产生密钥流的一个主要组成部分lGF(2)上一个上一个n 级反馈移位寄存器由级反馈移位寄存器由n 个二元存储器个二元存储器与与一个反馈函一个反馈函数数f(a1,a2,an)组成，如图所示组成，如图所示l每一存
28、储器称为移位寄存器的一级每一存储器称为移位寄存器的一级移位寄存器的状态移位寄存器的状态l在任一时刻，这些级的内容构成该反馈移位寄存器的在任一时刻，这些级的内容构成该反馈移位寄存器的状态状态l每一状态对应于每一状态对应于GF(2)上的一个上的一个n维向量，共有维向量，共有2n种可能的状态。种可能的状态。l每一时刻的状态可用每一时刻的状态可用n长序列长序列 a1,a2,an或或n维向量维向量 (a1,a2,an)表示，其中表示，其中ai是第是第i级存储器的内容。级存储器的内容。衬判鬃阵达卿猜面庚缓诚抢琉胎镐蕊枉桑弧圃壳述爱木脖纸微坟铣箔怎势密码学02流密码密码学02流密码24初始状态初始状态0 0
29、由用户确定由用户确定l属于密钥属于密钥k的一部分的一部分状态转换规则状态转换规则（线性）：（线性）：l当第当第i个移位时钟脉冲到来时，每一级存储器个移位时钟脉冲到来时，每一级存储器ai都将其内都将其内容向下一级容向下一级ai-1传递，并根据寄存器此时的状态传递，并根据寄存器此时的状态a1,a2,an计算计算f(a1,a2,an)，作为下一时刻的，作为下一时刻的an反馈函数反馈函数f(a1,a2,an)是是n元布尔函数，即元布尔函数，即n个变个变元元a1,a2,an可以独立地取可以独立地取0和和1这两个可能的值，这两个可能的值，l函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后函数中的运算有逻辑
30、与、逻辑或、逻辑补等运算，最后的函数值也为的函数值也为0或或1。圭篆吞麓梨余厌浇脚抓徒层亭龚帐晌凸斯睹琴涕婴敌潍溢弦咱树嘶库改狐密码学02流密码密码学02流密码25例例：下下图图是是一一个个3级级反反馈馈移移位位寄寄存存器器，其其初初始始状状态态为为(a1,a2,a3)=(1,0,1)，输出可由表，输出可由表2.2求出求出该该3 3级反馈移位寄存器级反馈移位寄存器的状态和输出如下的状态和输出如下状态（a3,a2,a1)输出1 0 11 1 01 1 10 1 11 0 11 1 0101110即输出序列为即输出序列为101110111011，周期为，周期为4雌罩哀迭信近溃嵌滑赋湿乾辱企拄纠镊珍
31、潜挫软萄秽倪贪廓鼎件徐址暮镑密码学02流密码密码学02流密码26线性反馈移位寄存器线性反馈移位寄存器LFSR l如果移位寄存器的反馈函数如果移位寄存器的反馈函数f(a1,a2,an)是是a1,a2,an的线性函数，则称之为线性反馈移位寄存器的线性函数，则称之为线性反馈移位寄存器LFSR（linear feedback shift register），此时），此时f可写为可写为lf(a1,a2,an)=cna1 cn-1a2 c1anl其中常数其中常数ci=0或或1，可用开关的断开和闭合来实现，可用开关的断开和闭合来实现剥孪绸湿扒丘咖养乎鹅煤短萨躁蛤焕想眉浮丘慕宠绿辱郑鬃炒伶选盈烛盈密码学02流
32、密码密码学02流密码27输出序列输出序列at满足满足 l an+t= cnat cn-1at1 c1ant-1l其中其中t为非负正整数。为非负正整数。二元情况下二元情况下(GF(2)，ci=0或或1刚好可以用开关的断开和刚好可以用开关的断开和闭合来表示，其中开关断开相当于没有连接线。闭合来表示，其中开关断开相当于没有连接线。lciani1等于等于0或或ani1恰好可用开关的断开和闭合来实现恰好可用开关的断开和闭合来实现线性反馈移位寄存器因其实现简单、速度快、有较为线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点成熟的理论等优点而成为构造密钥流生成器的最重要而成为构造密钥流生成器的
33、最重要的部件之一。的部件之一。垂辟圃谈祭话非篆疆胁逾关借麓慈虞励蚀馈非兼婚院湃版秧扁磺碧喉逞吊密码学02流密码密码学02流密码28【例2-3】下图是一个】下图是一个5级线性反馈移位寄存器，级线性反馈移位寄存器，其初始状态为（其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可，可求出输出序列为求出输出序列为 1001101001000010101110110001111100110周期为周期为31。凛魏坞涂智赢捞失袱改千卿史尔湍茧扰胶藕实靶臆循爸铣去兼济玻刃乳秦密码学02流密码密码学02流密码29在线性反馈移位寄存器中总是假定在线性反馈移位寄存器中总是假定c1,c2,cn中
34、中至少有一个不为至少有一个不为0，否则，否则f(a1,a2,an)0，在，在n个脉冲后状态必然是个脉冲后状态必然是000，且这个状态必将一直，且这个状态必将一直持续下去。持续下去。l若只有一个系数不为若只有一个系数不为0，设仅有，设仅有cj不为不为0，实际上是一种，实际上是一种延迟装置。延迟装置。l一般对于一般对于n级线性反馈移位寄存器，总是假定级线性反馈移位寄存器，总是假定cn=1。l线性反馈移位寄存器线性反馈移位寄存器输出序列的性质完全由其反馈函数输出序列的性质完全由其反馈函数决定决定学祟汇妨废敛侣原描挽刃纂社啮搅辆挫春佛恃租剁鼠刀嘎僚减量仇芬芳榜密码学02流密码密码学02流密码30LFS
35、R的周期的周期ln级线性反馈移位寄存器最多有级线性反馈移位寄存器最多有2n个不同的状态。个不同的状态。l若其初始状态为若其初始状态为0，则其状态恒为，则其状态恒为0。l若其初始状态非若其初始状态非0，则其后继状态不会为，则其后继状态不会为0。因此。因此n级线性级线性反馈移位寄存器的状态周期小于等于反馈移位寄存器的状态周期小于等于2n-1。l其输出序列的周期与状态周期相等，也小于等于其输出序列的周期与状态周期相等，也小于等于2n-1。只要选择合适的反馈函数便可使序列的周期达到最只要选择合适的反馈函数便可使序列的周期达到最大值大值2n-1，周期达到最大值的线性序列称为，周期达到最大值的线性序列称为
36、m序列序列l 其状态转移图是一个大圈其状态转移图是一个大圈敞拧登霹君鲸耕友官吩喂抿锄赶拾欠院喷取聊蔬丝慷旦氮虎扦酗沁毡伐淮密码学02流密码密码学02流密码312.3 线性移位寄存器序列的一元多项式表示线性移位寄存器序列的一元多项式表示设设n级线性移位寄存器的输出序列级线性移位寄存器的输出序列ai满足递推关系式满足递推关系式lan+k= c1ank1 c2ank2 cnak (*)l对任何对任何k 1成立。成立。l这种递推关系可用一个一元高次多项式表示这种递推关系可用一个一元高次多项式表示 p(x)=1+c1x+c2x2+cn-1xn-1+cnxn称这个多项式为称这个多项式为LFSR的特征多项式
37、。的特征多项式。特征多项式按如下方式获得：特征多项式按如下方式获得：l在在(*)式中两边同时加上式中两边同时加上an+k有有l 01an+k c1ank1 c2ank2 cnak 楷耳喇远鹅荧前民鞋驹幼婶裸儿哺汾客崭渤漱伐央点股锭晶随柬煤娩做恩密码学02流密码密码学02流密码32每一个时钟信号，寄存器中的内容从左向右移动一次，最左边的写入反馈每一个时钟信号，寄存器中的内容从左向右移动一次，最左边的写入反馈信号，最右边的移出。因此一个寄存器代表一次符号迟延，因而引入迟延信号，最右边的移出。因此一个寄存器代表一次符号迟延，因而引入迟延算子算子DlD(ank)ank1表示迟延一位，表示迟延一位，D2
38、(ank)ank2表示迟延两位表示迟延两位(两拍两拍)即即lD2(ank)D(D(ank)D(ank1)=ank2l同理有同理有Dn(ank)ak表示迟延表示迟延n位。位。l引入恒等算子引入恒等算子I=D0，I(ank) =ank于是递推式于是递推式01an+k c1ank1 c2ank2 cnak可表示成可表示成l 0I(ank)+c1D(ank)+c2D2(ank)+cnDn(ank)l即即0(I+c1D+c2D2+cnDn)ankl以以x表示表示D，则有则有p(x)ank=0于是可知于是可知p(x)可以描述可以描述LFSR的全部特征，可以由的全部特征，可以由p(x)来研究来研究LFSR然
39、瞳阜馅撩斤婉顽落稀荧攒董坞塌胺峪否之给婚煽课耻喷汉矾毕惊蜘漫韵密码学02流密码密码学02流密码33线性反馈移位寄存器与特征多项式是一一对应的线性反馈移位寄存器与特征多项式是一一对应的l如果知道了线性反馈移位寄存器的结构，可以写出它如果知道了线性反馈移位寄存器的结构，可以写出它的特征多项式的特征多项式l同样可以根据特征多项式画出移位寄存器的结构。同样可以根据特征多项式画出移位寄存器的结构。设设n级线性移位寄存器对应于递推关系级线性移位寄存器对应于递推关系(*)，l由于由于ai GF(2) (i=1,2,n)，所以共有，所以共有2n组初始状态，组初始状态，即有即有2n个递推序列，其中非恒零的有个递
40、推序列，其中非恒零的有2n-1个个l记记2n-1个非零序列的全体为个非零序列的全体为G(p(x)。l一般的一般的cn=1，如果，如果cn0则发生次数退化则发生次数退化精侦鼠暇酿太秘灌碑胡隋辨俞抿帆录噎只呕洲助卫柳瓣一崩旺宪渤札况雌密码学02流密码密码学02流密码34定义定义2-1 给定序列给定序列ai,幂级数幂级数称为该序列的称为该序列的生成函数生成函数。l把把输输出出序序列列的的每每一一项项按按顺顺序序依依次次看看作作级级数数的的系数（系数（xt 表示迟延表示迟延t个节拍）个节拍）定定 理理 2-1设设 p(x)=1+c1x+c2x2+cn-1xn-1+cnxn是是GF(2)上上的的多多项项
41、式式，G(p(x)中中任任一一序序列列ai的的生生成函数成函数A(x)满足：满足： 其中其中卯咙扫薛腥究韶洗恬苫黍忍昌锑煞谐嚏帧吐唯间溯敞电啡禹铁汾琵赞警雷密码学02流密码密码学02流密码35证明：证明： 由递推等式不难得出由递推等式不难得出lan+1=c1an c2an-1 cna1lan+2=c1an+1 c2an cna2ll两边分别乘以两边分别乘以xn,xn+1,，再求和，再求和l左边左边an+1xn+an+2xn+1+ A(x)(a1+a2x+anxn-1)l右边逐列相加整理得右边逐列相加整理得l右边右边=c1xA(x)(a1+a2x+an-1xn-2)l +c2x2A(x)(a1+
42、a2x+an-2xn-3)l +l +cnxnA(x)移项整理得移项整理得 l(1+c1x+c2x2+cn-1xn-1+cnxn) A(x) =(a1+a2x+anxn-1) +c1x(a1+a2x+an-1xn-2) +c2x2(a1+a2x+an-2xn-3) +cn-1xn-1a1l即即p(x)A(x)= = (x)可郝赛甸焚足奏键抒蚌铂契嚼噶奎亥新铡兽遏痘董芝柿峪坚拥交恿盎侮看密码学02流密码密码学02流密码36 (x)的次数小于的次数小于nl因此共有因此共有2n1个不同的非个不同的非0表达式表达式l而每一个初态都对应不同的而每一个初态都对应不同的 (x)，共有，共有2n1个个初态初态
43、l所以初态和所以初态和 (x)是一一对应的是一一对应的l初始状态、初始状态、 (x)、G(p(x)三者一一对应三者一一对应箔侈很周炊羊降风燃她预按娟犊虱结途艘型肿漓花仓最噬贼洽眨大煌萝作密码学02流密码密码学02流密码37定理定理2-2 p(x)|q(x)的充要条件是的充要条件是G(p(x) G(q(x)l证明：若证明：若p(x)|q(x)，可设，可设q(x)p(x)r(x)，因此，因此 l l而而 (x)次数小于等于次数小于等于n1，r(x)次数为次数为nqn，所以，所以 (x)r(x)次数小于等于次数小于等于nqn+(n1)= nq1。l根据定理根据定理2-1的推导过程，可知的推导过程，可
44、知 (x)r(x)唯一对应一个唯一对应一个q(x)生成的序列，而显然有生成的序列，而显然有lq(x)A(x)p(x)r(x)A(x) (x)r(x)，即该序列为，即该序列为A(x)。l所以若所以若ai G(p(x)，则也有，则也有ai G(q(x)，即，即G(p(x) G(q(x)原耽呸之极谦硒奠辖识干充巨厉沸撮芯而笼舰描莆琉徊臀睡昼屯鼻属梗猪密码学02流密码密码学02流密码38l反之，若反之，若G(p(x) G(q(x)，则对于次数小于，则对于次数小于n的多的多项式项式 (x)，存在序列，存在序列ai G(p(x)，以，以 为生成函数为生成函数 根据定理根据定理2-1的推导过程，当的推导过程
45、，当 (x)1时，当然也存在时，当然也存在序列序列ai G(p(x)以以 为生成函数为生成函数 由于由于G(p(x) G(q(x)，序列，序列ai G(q(x)，所以存，所以存在函数在函数r(x)，使得，使得ai的生成函数也等于的生成函数也等于 ， 从而从而 ，即，即q(x)p(x)r(x)，所，所以以p(x)|q(x)。 证毕证毕组皇纬眷周吞屹灰康枫悬熄柒英剿嗡需嫩骑劣呆防盎壬淡膜逊注按应悸乱密码学02流密码密码学02流密码39l定理定理2-2 说明可用说明可用n级级LFSR产生的序列，也可产生的序列，也可用级数更多的用级数更多的LFSR来产生来产生l反之一个反之一个LFSR序列的特征多项式
46、可能有多个，序列的特征多项式可能有多个，需要的移位寄存器个数也不同需要的移位寄存器个数也不同l2.6节将介绍线性复杂度概念，极小多项式的次数节将介绍线性复杂度概念，极小多项式的次数定义定义2-2 设设p(x)是是GF(2)上的多项式，使上的多项式，使p(x)|(xp-1)的最小的最小p称为称为p(x)的周期或阶的周期或阶医色崔衷陷萨咸郴程映真戎挝攘置圭擂骡尚酵尔勾骚乖蒂嘴潞黔栓聚壁侨密码学02流密码密码学02流密码40定理定理2-3 若序列若序列ai的特征多项式的特征多项式p(x)定义在定义在GF(2)上，上，p是是p(x)的周期，则的周期，则ai的周期的周期r|p。l证明：证明：(首先证明首
47、先证明ai至少是以至少是以p为周期重复的为周期重复的)l由由p(x)周期的定义得周期的定义得p(x)|(xp-1)，因此存在，因此存在q(x)，使得，使得 xp-1 =p(x)q(x)，l又由又由p(x)A(x) (x)可得可得p(x)q(x)A(x)q(x) (x)l所以所以(xp-1)A(x)=q(x) (x)。由于。由于q(x)的次数为的次数为p-n， (x)的次数不超过的次数不超过n-1，所以，所以(xp-1)A(x)的次数不超过的次数不超过(p-n)+(n-1)=p-1。l对于任意的特征多项式为对于任意的特征多项式为p(x)的的A(x)，xpA(x) - A(x)的次数低于的次数低于
48、p1，也就是，也就是A(x)移位移位p次后对应位相等，从而相消去次后对应位相等，从而相消去)l 这就证明了对于任意正整数这就证明了对于任意正整数i都有都有ai+p=ail设设p=kr+t,0 tr，则，则ai+p=ai+kr+t=ai+t=ai，所以，所以t=0，即，即r|p。（证毕）。（证毕）鲤沫茁勺登秉闷蔗骇噶颗画怖罢朵猎绢须弄盆峙苔冠杉颠军扛雹婆策鲸燎密码学02流密码密码学02流密码41n级级LFSR输出序列的周期输出序列的周期r不依赖于初始条件，而依赖于不依赖于初始条件，而依赖于特征多项式特征多项式p(x)。l我们感兴趣的是我们感兴趣的是LFSR遍历遍历2n-1个非零状态，这时序列的周
49、期达到个非零状态，这时序列的周期达到最大最大2n-1，这种序列就是，这种序列就是m序列序列。显然对于特征多项式一样，而仅。显然对于特征多项式一样，而仅初始条件不同的两个初始条件不同的两个m输出序列，一个记为输出序列，一个记为ai(1)，另一个记为，另一个记为ai(2)，其中一个必是另一个的移位，即存在一个常数，其中一个必是另一个的移位，即存在一个常数k，使得，使得lai(1)=aik(2),i=1,2,下面讨论特征多项式满足什么条件时，下面讨论特征多项式满足什么条件时，LFSR的输出序列的输出序列为为m序列。序列。定义定义2-3 仅能被非仅能被非0常数或自身的常数倍除尽，但不能被其常数或自身的
50、常数倍除尽，但不能被其它的多项式除尽的多项式称为既约多项式或不可约多项式它的多项式除尽的多项式称为既约多项式或不可约多项式l不可约多项式的讨论与域有关，不同的域，多项式是否既约可能不可约多项式的讨论与域有关，不同的域，多项式是否既约可能是不同的是不同的窒冗钱弹盘傀实犹算老教惮想腐濒矿志崇包獭拇六遥玖秘洲戍残轿异轧摧密码学02流密码密码学02流密码42定理定理2-4 设设p(x)是是n次不可约多项式，周期为次不可约多项式，周期为m，序列，序列ai G(p(x)，则，则ai的周期为的周期为m。l证明：设证明：设ai的周期为的周期为r，由定理，由定理2.3 有有r|m，所以，所以r m。l设设A(x
51、)为为ai的生成函数，的生成函数，A(x)= (x)/p(x)，即，即p(x)A(x)= (x)0， (x)的次数不超过的次数不超过n-1。而。而lA(x)= =a1+a2x+arxr-1+xr(a1+a2x+arxr-1)l +(xr)2(a1+a2x+arxr-1)+l = (a1+a2x+arxr-1)/(1-xr)l = (a1+a2x+arxr-1)/(xr-1)l于是于是A(x)=(a1+a2x+arxr-1)/(xr-1) (x)/p(x)，l即即 p(x)( a1+a2x+arxr-1)= (x)(xr-1)l因因p(x)是不可约的，所以是不可约的，所以gcd(p(x), (x
52、) =1，p(x)|(xr-1)，因此，因此m r。l综上综上r=m。（证毕）。（证毕）残甭弹洛扒篆按洪硫仕枣福棺姥歹骋挫衣座咐捣晒主铆躬茎嫁汤饥丛晰全密码学02流密码密码学02流密码43定理定理2.5 n级级LFSR产生的序列有最大周期产生的序列有最大周期2n-1的必的必要条件是其特征多项式为不可约的。要条件是其特征多项式为不可约的。l证明：设证明：设n级级LFSR产生的序列周期达到最大产生的序列周期达到最大2n-1，除，除0序序列外，每一序列的周期由特征多项式惟一决定，而与初始列外，每一序列的周期由特征多项式惟一决定，而与初始状态无关。状态无关。l(只要有一条序列为只要有一条序列为m序列，
53、则所有非序列，则所有非0序列都是序列都是m序列序列)l设特征多项式为设特征多项式为p(x)，若，若p(x)可约，可设为可约，可设为p(x)=g(x)h(x)，其中其中g(x)不可约，且次数不可约，且次数k2，当，当1 i n-2时，时，n长长m序列的一个周期内，长为序列的一个周期内，长为i的的0游程数游程数目等于序列中如下形式的状态数目：目等于序列中如下形式的状态数目： 10001*，其中，其中n-i-2个个*可可任取任取0或或1。由遍历性，这种状态共有。由遍历性，这种状态共有2n-i-2个。同理可得长为个。同理可得长为i的的1游游程数目也等于程数目也等于2n-i-2，所以长为，所以长为i的游
54、程总数为的游程总数为2n-i-1。赊易晕婶勿隐露倪某弟场硫埋要况脚晰商学腰吨伙申刃雹涛屡演羹触扔尿密码学02流密码密码学02流密码56l由于寄存器中不会出现全由于寄存器中不会出现全0状态，所以状态，所以不会出现不会出现0的的n游程游程，但由状态遍历性但由状态遍历性必有一个必有一个1的的n游程游程，而且，而且1的游程不会更大，的游程不会更大，因为若出现因为若出现1的的n+1游程，就必然有两个相邻的全游程，就必然有两个相邻的全1状态，但状态，但这是不可能的，因为如果这样移位寄存器将永远是全这是不可能的，因为如果这样移位寄存器将永远是全1状态状态l这就证明了这就证明了1的的n游程必然出现在如下的串中
55、：游程必然出现在如下的串中：”01110”其中其中1共有共有n个，首尾是个，首尾是0。l当这当这n+2位通过移位寄存器时，便依次产生以下状态：位通过移位寄存器时，便依次产生以下状态：l 0111 (n-1个个1) 111(n个个1) 1110(n-1个个1)l而而0111 (n-1个个1)和和1110(n-1个个1)这两个状态只可能出现这两个状态只可能出现一次，而它们包含在了全一次，而它们包含在了全1状态中，所以不会有状态中，所以不会有1的的n-1游程游程l如果存在如果存在1的的n-1游程，则必有形式游程，则必有形式0110，它与，它与0111(n个个1)矛盾矛盾奈剐钎兴奖乱藤贯孤裁蛤阅逮桂侦
56、拒踩疆奴札饭到越折紊泄颅瘦邱控悬迷密码学02流密码密码学02流密码57l0的的n-1游程有一个游程有一个1001(n-1个个0)，不可能有两个，不可能有两个0的的n-1游程，否则由状态重复可知周期小于游程，否则由状态重复可知周期小于2n-1l于是在一个周期内，总游程数为于是在一个周期内，总游程数为l11 2n-1l 采用构造法采用构造法lai是周期为是周期为2n-1的的m序列，对于任一正整数序列，对于任一正整数(02n-1)，ai+ai+在一个周期内为在一个周期内为0的位的的位的数目正好是序列数目正好是序列ai和和ai+对应位相同的位的数对应位相同的位的数目目lR() 钵簇壁我伏定矽啡敷毗馁瓤
57、族靴父瘴亲灭解继革很奋推借沽据盟码呛镶靳密码学02流密码密码学02流密码58l设序列设序列ai满足递推关系满足递推关系lah+n=c1ah+n1 c2ah+n2 cnahl故故ah+n+=c1ah+n+1 c2ah+n+2 cnah+l即即ah+n ah+n+=c1(ah+n1 ah+n+1) c2(ah+n2 ah+n+2) cn(ah ah+)l令令bj=aj aj+，则由递推序列，则由递推序列ai可推得递推序列可推得递推序列biai+ai+lbi满足满足bh+n=c1bh+n1 c2bh+n2cnbhlbi也是也是m序列。为了计算序列。为了计算R()，只要用只要用bi在一个周期在一个周期
58、中中0的个数减去的个数减去1的个数，再除以的个数，再除以2n-1，即，即l R()= = （证毕）（证毕）编贸亮澄僻线近得吧淌白代偿坑矗搜木刃翟帧疏辖翼聪识郝罪账朴雌终吭密码学02流密码密码学02流密码592.5 m序列密码的破译序列密码的破译有限域上的有限域上的二元加法序列密码二元加法序列密码是目前最为常用的是目前最为常用的序列密码体制序列密码体制设滚动密钥生成器是线性反馈移位寄存器，产生设滚动密钥生成器是线性反馈移位寄存器，产生的密钥是的密钥是m序列。又设序列。又设Sh和和Sh1是序列中两个连续是序列中两个连续的的n长向量（两个连续的状态），其中长向量（两个连续的状态），其中lSh ，Sh
59、1曝迄漂捍皖卜儡淀贤毛缕弄证蓉袒盔因奶森豪萝界芯歇役柑棒掳碧籽七檬密码学02流密码密码学02流密码60设序列设序列ai满足线性递推关系满足线性递推关系lah+n=c1ah+n1 c2ah+n2 cnah可表示为：可表示为：l l即即Sh1MSh，M是其中矩阵是其中矩阵又设敌手知道一段长为又设敌手知道一段长为2n的明密文对的明密文对lxx1x2.x2n，yy1y2.y2n于是由二元加法流密码加密变换变型算法于是由二元加法流密码加密变换变型算法zi=xi yi可得长为可得长为2n的密钥序列的密钥序列 zz1z2.z2n连居瘁份府深搽架赶酮缠札缆腊点响掉监栈妆林贵管掣堵溅掌拘概寸海男密码学02流密码
60、密码学02流密码61由长为由长为2n的密钥序列可推出的密钥序列可推出LFSR连续的连续的n+1个状态：个状态：lS1=(z1z2.zn)T 记为记为 (a1a2.an)T （此处教材中少了转置符号）（此处教材中少了转置符号）lS2=(z2z3.zn+1)T 记为记为 (a2a3.an+1)TllSn+1=(zn+1zn+2.z2n)T 记为记为 (an+1an+2.a2n)T作矩阵作矩阵X=(S1S2Sn)l则则(an+1an+2.a2n)(cncn-1.c1) =(cncn-1.c1)X若若X可逆，则可逆，则(cncn-1.c1)(an+1an+2.a2n)X1即即2n个元素构成一个行向量和
61、一个矩阵，从而可以推导出个元素构成一个行向量和一个矩阵，从而可以推导出密钥产生器的生成多项式。密钥产生器的生成多项式。攫吮蜜锁脑氏摔完喊瓣垮隅捻抡斗郧叉钠著斡势颇腕邪衫锚板弟著蔬董魏密码学02流密码密码学02流密码62而而X是由是由S1S2Sn作为列向量构成的，要证作为列向量构成的，要证X可逆，只需证可逆，只需证明这明这n个向量线性无关个向量线性无关证明：证明：l由序列递推式由序列递推式ah+n=c1ah+n1 c2ah+n2 cnahl可得向量之间递推关系可得向量之间递推关系 Sh+n=c1Sh+n1 c2Sh+n2 cnShl在二元域上在二元域上 Sh+n=c1Sh+n1c2Sh+n2cn
62、Sh l对于对于n级级m序列，序列，n是生成该序列的最小级数是生成该序列的最小级数设设m是使是使S1，S2，Sm 线性相关的最小整数，即存在一线性相关的最小整数，即存在一组不全为组不全为0的系数的系数l1，l2，lm，不妨设，不妨设l11使得使得m个非个非零向量满足零向量满足lSm+l2Sm1l3Sm2lmS10l即即 Sml2Sm1l3Sm2lmS1 （二元域加法）（二元域加法）晒龙睦牙客袋废拜谆灶晚坷若立邯恳苫屯硫删冒逃券绿寓笋锅念要捷禹布密码学02流密码密码学02流密码63那么对于任意整数那么对于任意整数i有，方程两边同时左乘有，方程两边同时左乘Mi 得得lSmiMiSmMi(l2Sm1
63、l3Sm2lmS1)l l2MiSm1l3MiSm2lmMiS1l l2Smi1l3Smi2lmSi1由于以上关系式对任意的由于以上关系式对任意的i都成立，所以它也给出都成立，所以它也给出了密钥流的一个递推关系式了密钥流的一个递推关系式l am+i=l2am+i1 l3am+i2 lmai+1l即密钥流可以由即密钥流可以由m1级级LFSR生成，而生成，而由已知由已知得得m序列序列密钥流的级数最小为密钥流的级数最小为n，所以必有，所以必有n=m1l而而m是使得是使得S1，S2，Sm线性相关的最小整数，现在线性相关的最小整数，现在nm所以所以n个向量个向量S1，S2，Sn必线性无关，即矩阵必线性无
64、关，即矩阵X可逆。可逆。匙紧卧番守阶瘩趟咙锤烈笺西攘拧泪辞沥兄堂姓杠鳃挞爵给添抑卉碉振寝密码学02流密码密码学02流密码64【例【例26】设敌手得到密文串设敌手得到密文串101101011110010和相应密文和相应密文串串011001111111001，并且假定敌手还知道密钥流是使用，并且假定敌手还知道密钥流是使用5级移位寄存器产生的，采用二元加法流密码。试破译该密级移位寄存器产生的，采用二元加法流密码。试破译该密钥流产生器，即求解出递推关系钥流产生器，即求解出递推关系l解：由明密文串立即可得相应得密钥流为二者对应位异或，得解：由明密文串立即可得相应得密钥流为二者对应位异或，得1101001
65、00001011l由已知的移位寄存器的级数由已知的移位寄存器的级数5，提取密钥流的前，提取密钥流的前10个比特，建立如个比特，建立如下方程：下方程：lSTn1CXl(a6a7a8a9a10)=(c5c4c3c2c1) ，即，即(0 1 0 0 0)=(c5c4c3c2c1)份骡泪沈哄馏歼错肛州舷旨乞尾馏聋衷蔓垄柔沽数傀痕趴嚷愈裔瞬涤仗聊密码学02流密码密码学02流密码65l而而 ，从而，从而(c5c4c3c2c1)(0 1 0 0 0)l 所以有所以有(c5c4c3c2c1)(10010)从而密钥流的递推关系为从而密钥流的递推关系为lai5=c2ai3 c5aiai3 ail矩阵的逆满足矩阵的
66、逆满足A-1=A*/|A|等于等于A的伴随阵除以的伴随阵除以A的行列式的行列式l解上述的方程组还可用克莱姆法则，解上述的方程组还可用克莱姆法则，ci|D 6-i|/|D |由由于矩阵满秩，于矩阵满秩，|D |1继蚤府匠缀渴旋哉拳诗酣场碎患咬完约琐澄琅浊矩魄裔鹤造芯炊况采谣仅密码学02流密码密码学02流密码66线性反馈移位寄存器（线性反馈移位寄存器（LFSR）的综合）的综合m-序列是满足序列是满足Golomb三条随机性公设的三条随机性公设的PN序列，但其不可以作为一个序列，但其不可以作为一个序列密码的密钥序列。因为：对序列密码的密钥序列。因为：对m-序列，知道其少量的比特以后是可以序列，知道其少
67、量的比特以后是可以破译的破译的l级数较少的移位寄存器如果其反馈函数为非线性的，则可能相当于一个级数级数较少的移位寄存器如果其反馈函数为非线性的，则可能相当于一个级数较大的线性反馈移位寄存器产生的序列较大的线性反馈移位寄存器产生的序列 LFSR的综合问题就在于根据序列的少量比特求出整个序列所满足的线性的综合问题就在于根据序列的少量比特求出整个序列所满足的线性递推关系。递推关系。l在前述方法中：先假定线性递推关系，然后由序列的各项应该适合之而导出在前述方法中：先假定线性递推关系，然后由序列的各项应该适合之而导出线性方程组线性方程组；但这样的方法不容易确定所适用的；但这样的方法不容易确定所适用的LF
68、SR的级数的级数n，从而不能导，从而不能导致恰当规模的线性方程组；并且当上述致恰当规模的线性方程组；并且当上述n很大时，求解相应规模线性方程组也很大时，求解相应规模线性方程组也很困难。（如破译中的方法。）很困难。（如破译中的方法。）l有些序列并不是有些序列并不是m序列，甚至是非线性反馈移位寄存器产生的序列，但该序序列，甚至是非线性反馈移位寄存器产生的序列，但该序列总能等效为一个列总能等效为一个LFSR，我们要解决的是根据序列的少量比特求出整个序列，我们要解决的是根据序列的少量比特求出整个序列满足的递推关系，即该序列的极小多项式和相应的线性复杂度。满足的递推关系，即该序列的极小多项式和相应的线性
69、复杂度。l著名的著名的Berlekamp-Massey迭代算法，简称迭代算法，简称B-M算法，可以解决以上问题算法，可以解决以上问题l参见伪随机序列及其应用，肖国镇，梁传甲，王育民，国防工业出版社参见伪随机序列及其应用，肖国镇，梁传甲，王育民，国防工业出版社炮乓肌铆毯殿绦粱载被爹仲匪虐例镍此冰永扛酬秤芳捏玛暮挨乌渗抉戮湾密码学02流密码密码学02流密码67在一个一般在一个一般n-FSR的状态图中，至少含有一个圈，且从的状态图中，至少含有一个圈，且从任意状态出发进动若干拍后必定进入某一个圈！这时得任意状态出发进动若干拍后必定进入某一个圈！这时得到的输出序列虽不必是周期序列，但去掉其前若干项后到的
70、输出序列虽不必是周期序列，但去掉其前若干项后即得到周期序列，也就是说这样的序列为即得到周期序列，也就是说这样的序列为终归周期序列终归周期序列。 M-序列序列l若一若一n-FSR的输出序列的周期达到最大值的输出序列的周期达到最大值2n，则称此序列为，则称此序列为(n级级)M-序列。序列。l显然，如果一个显然，如果一个n-FSR有一个输出序列为有一个输出序列为M-序列，则其状态图是序列，则其状态图是一个包含一个包含F2n中所有中所有2n个点的大圈，从而这个个点的大圈，从而这个n-FSR由任意初态产由任意初态产生的序列都是生的序列都是M-序列（一共有序列（一共有2n个且相互平移等价！），这个个且相互
71、平移等价！），这个n-FSR本身也就被称为本身也就被称为M-序列生成器，而相应的反馈函数被称为序列生成器，而相应的反馈函数被称为M-序列反馈函数。序列反馈函数。l例：例：.反馈函数为反馈函数为 的的3-FSR。xi是是寄存器状态，寄存器状态，痛谈滦乐搁访沂吏者疼赂驭松贱紫详猜淆坪历窥哺仪未奶皂泉盒贿皮甘轻密码学02流密码密码学02流密码68布尔函数布尔函数f(x1,x2,xn)是是n级级M-序列的反馈函数序列的反馈函数的必要条件是的必要条件是:l f(x1,x2,xn)是非奇异的，即是非奇异的，即f(x1,x2,xn)=x1+f0(x2,x3,xn)l 中中n-1元布尔函数元布尔函数f0(x2
72、,x3,xn) 还必须满足：还必须满足：lf0的重量的重量W(f0)是奇数；是奇数；l在在f0的任一表达中，的任一表达中，x2,x3,xn都出现；都出现；l在在f0的多项式表示中，项数为奇数、常数项的多项式表示中，项数为奇数、常数项1必出现、线性项必出现、线性项x2,x3,xn不能全出现、且不能全出现、且n-1次项次项x2x3xn一定出现。一定出现。啄枷缮嫁鸿寡愤富湿裂塞耳臣琐堂往九核彻屁豆岂溢架潞精唉常沽缆颓阵密码学02流密码密码学02流密码692.6非线性序列非线性序列密钥流生成器可分解为驱动子系统和非线性组合密钥流生成器可分解为驱动子系统和非线性组合子系统，如图所示子系统，如图所示 l驱
73、动子系统常用一个或多个线性反馈移位寄存器来实现，驱动子系统常用一个或多个线性反馈移位寄存器来实现，l非线性组合子系统用非线性组合函数非线性组合子系统用非线性组合函数F来实现，如图所来实现，如图所示。示。l本节介绍第本节介绍第2部分非线性组合子系统部分非线性组合子系统凹惦犁非怕纠揽忱枝率败战级哥页芥监阎纫糕雏妻随撒酣苦窒幽撅貌派评密码学02流密码密码学02流密码70定义：定义：二元序列的线性复杂度二元序列的线性复杂度指生成该序列的最指生成该序列的最短短LFSR的级数，最短的级数，最短LFSR的特征多项式称为的特征多项式称为二二元序列的极小特征多项式元序列的极小特征多项式l为了使密钥流生成器输出的
74、二元序列尽可能复杂，应保为了使密钥流生成器输出的二元序列尽可能复杂，应保证其证其周期尽可能大周期尽可能大、线性复杂度和不可预测性尽可能高线性复杂度和不可预测性尽可能高l常使用多个常使用多个LFSR来构造二元序列，称每个来构造二元序列，称每个LFSR的输出的输出序列为驱动序列序列为驱动序列l显然密钥流生成器输出序列的周期不大于各驱动序列显然密钥流生成器输出序列的周期不大于各驱动序列周期的乘积周期的乘积，因此，因此，提高输出序列的线性复杂度应从提高输出序列的线性复杂度应从极大化其周期开始极大化其周期开始下面介绍下面介绍4种由多个种由多个LFSR驱动的非线性序列生成驱动的非线性序列生成器器佰板靡褪谚
75、兢不戎染瞄羞项刑搁堡掇婪骚挑铃靳殉碉绩各堑贞牧巡闸见理密码学02流密码密码学02流密码712.6.1 Geffe序列生成器序列生成器lGeffe序列生成器由序列生成器由3个个LFSR组成，其中组成，其中LFSR2作为控作为控制生成器使用，如图所示制生成器使用，如图所示l当当LFSR2输出输出1时，时，LFSR2与与LFSR1相连接相连接l当当LFSR2输出输出0时，时，LFSR2与与LFSR3相连接相连接l若设若设LFSRi的输出序列为的输出序列为ak(i) (i=1,2,3)，则输出序，则输出序列列bk可以表示为可以表示为l ak(1)ak(2)+ ak(3)ak(2)+ak(3)倾深稍唁予
76、硫沿他淡奴满疼碳褂智琅泞壬赶拎绸讲巨姆柠也兰据阿戳季挝密码学02流密码密码学02流密码72Geffe序列生成器也可以表示为多路复合的形式，其中序列生成器也可以表示为多路复合的形式，其中LFSR1和和LFSR3作为多路复合器的输入，作为多路复合器的输入，LFSR2控制多路控制多路复合器的输出。复合器的输出。设设LFSRi的特征多项式分别为的特征多项式分别为ni次本原多项式，且次本原多项式，且ni两两互两两互素，则素，则lGeffe序列的周期为序列的周期为 ，线性复杂度为，线性复杂度为(n1+n3)n2+n3注意，这里如果注意，这里如果n和和m互素，由欧几里得算法可知，互素，由欧几里得算法可知，2
77、n1，2m1也互素，即周期也两两互素，再由和序列与乘积也互素，即周期也两两互素，再由和序列与乘积序列序列(对应元素相乘后所得序列对应元素相乘后所得序列)的性质，可得出以上结论的性质，可得出以上结论l互素时，乘积序列的周期等于各周期的乘积，和序列的周期等于互素时，乘积序列的周期等于各周期的乘积，和序列的周期等于最小公倍数，可知周期为三者乘积。此时的线性复杂度也满足最小公倍数，可知周期为三者乘积。此时的线性复杂度也满足乘乘积积和和和和的条件，固有以上结果。的条件，固有以上结果。Geffe序列的周期实现了极大化，且序列的周期实现了极大化，且0与与1之间的分布大体之间的分布大体上是平衡的。上是平衡的。
78、饯巾追无梭辟纫骇晓薄哦锥墅敛咯捐答丫尖焊傅糜鸿蔽亭凭荤宅勃耽阎黑密码学02流密码密码学02流密码732.6.2 J-K触发器触发器lJ-K触发器如下图所示，它的两个输入端分别用触发器如下图所示，它的两个输入端分别用J和和K表表示，其输出示，其输出ck不仅依赖于输入，还依赖于前一个输出位不仅依赖于输入，还依赖于前一个输出位ck-1，即，即lck=( )ck-1+x1l其中其中x1和和x2分别是分别是J和和K端的输入。由此可得端的输入。由此可得J-K触发器触发器的真值表，如表。的真值表，如表。00保原态，保原态，11翻一翻，翻一翻，余下看余下看J端端幕瞄塌为完暇褪昨怔亮钮寐藻旱欧儡蒸秉汗想惶窍周扣
79、捶丑跌程犀寅逃菩密码学02流密码密码学02流密码74利用利用J-K触发器的非线性序列生成器见图触发器的非线性序列生成器见图l令驱动序列令驱动序列ak和和bk分别为分别为m级和级和n级的级的m-序列，则有序列，则有lck=( )ck-1+ak=(ak+bk+1)ck-1+ak如果令如果令c-1=0，则输出序列的最初，则输出序列的最初3项为项为lc0=a0lc1=(a1+b1+1)a0+a1lc2=(a2+b2+1)(a1+b1+1)a0+a1)+a2当当m与与n互素且互素且a0+b0=1时，序列时，序列ck的周期为的周期为(2m-1)(2n-1)l两个序列同时回到两个序列同时回到a0和和b0时由
80、于时由于a0+b0=1，刚好恢复初态，刚好恢复初态景攫馈舍递钵慢篮桔尘队芒兄樊筐崇鸳店河斧瞧臀尧组特权练斤柿别邢唤密码学02流密码密码学02流密码75显然当输入的两个序列再次回到显然当输入的两个序列再次回到a0和和b0时时J-K触发器的输出又恢复到以上状态，由于触发器的输出又恢复到以上状态，由于m与与n互素，互素，(2m-1)和和(2n-1)也互素，当运行也互素，当运行p(2m-1)(2n-1)拍以后才能达到此状态。拍以后才能达到此状态。平镀役办例惕小惦悄岭耿歼碳戴媚华瓷罩邑蜘穷仕咆边父核蚕吃淄苏末激密码学02流密码密码学02流密码76例例27： 令令m=2,n=3，两个驱动，两个驱动m-序列
81、分别为序列分别为lak=0,1,1,和和bk=1,0,0,1,0,1,1,l于是，输出序列于是，输出序列ck是是0,1,1,0,1,0,0,1,1,1,0,1,0,1,0,0,1,0,0,1,0,l其周期为其周期为(22-1)(23-1)=21。由表达式由表达式ck=(ak+bk+1)ck-1+ak可得可得 ck=l因此，因此，如果知道如果知道ck中相邻位的值中相邻位的值ck-1和和ck，就可以推断，就可以推断出出ak和和bk中的一个中的一个。而一旦知道足够多的这类信息，就。而一旦知道足够多的这类信息，就可通过密码分析的方法得到序列可通过密码分析的方法得到序列ak和和bk。l为了克服上述缺点，
82、为了克服上述缺点，Pless提出了由多个提出了由多个J-K触发器序列触发器序列驱动的多路复合序列方案，称为驱动的多路复合序列方案，称为Pless生成器。生成器。腾赡持正懒盖津淡菏谈达臂侥锹耘葡能枉蛰擒蓟变秽脯居花喀振皮扁渍玻密码学02流密码密码学02流密码772.6.3 Pless生成器生成器lPless生成器由生成器由8个个LFSR、4个个J-K触发器和触发器和1个个循环计数器构成，由循环计数器进行选通控制，循环计数器构成，由循环计数器进行选通控制，如下图所示。假定在时刻如下图所示。假定在时刻t输出第输出第t(mod 4)个单个单元，则输出序列为元，则输出序列为a0b1c2d3a4b5c6箱
83、鱼吹粉舀疹锌洁吠茁聪刺挑决润慑羹罩衔爱竭讣椽狈寺难氢栈巧岸一褒密码学02流密码密码学02流密码782.6.4 钟控序列生成器钟控序列生成器钟控序列最基本的模型是用一个钟控序列最基本的模型是用一个LFSR控制另外一个控制另外一个LFSR的移位时钟脉冲，如图所示，一个最简单钟控序列生成器的移位时钟脉冲，如图所示，一个最简单钟控序列生成器l假设假设LFSR1和和LFSR2分别输出序列分别输出序列ak和和bk，其周期分别为，其周期分别为p1和和p2。l当当LFSR1输出输出1时，移位时钟脉冲通过与门使时，移位时钟脉冲通过与门使LFSR2进行一次移位，进行一次移位，从而生成下一位。从而生成下一位。l当当
84、LFSR1输出输出0时，移位时钟脉冲无法通过与门影响时，移位时钟脉冲无法通过与门影响LFSR2。因此。因此LFSR2重复输出前一位。假设钟控序列重复输出前一位。假设钟控序列ck的周期为的周期为p，可得如下，可得如下关系：关系：lp= ， 其中其中w1链软块逾吗笆活劫熏父经敌厕致瞄沪识姻梅养妙辩讼伴城挎茶山倡玩弦糕密码学02流密码密码学02流密码79ck的一个周期至少是的一个周期至少是LFSR1和和LFSR2同时回同时回到初始状态的时刻到初始状态的时刻lLFSR1运行一个周期，运行一个周期，LFSR2运行运行w1dt拍，拍，dgcd(w1,p2)l则则LFSR1运行（运行（p2/d）个周期后，）
85、个周期后，LFSR2刚好刚好运行运行dtp2/dtp2拍，即拍，即t个个整周期整周期，于是两个，于是两个LFSR都回到初态，这时运行了（都回到初态，这时运行了（p2/d）p1个个节拍，即所谓的周期节拍，即所谓的周期孵血谅牢选泣陀选找趁逾羞洱臣图付齿巾通信丝沾仔址蔽肄殴滴巢账含驮密码学02流密码密码学02流密码80又设又设ak和和bk的极小特征多项式分别为的极小特征多项式分别为GF(2)上的上的m和和n次本原多项式次本原多项式f1(x)和和f2(x)，且，且m|n。因此，。因此，p1=2m-1,p2=2n-1。又知。又知w1=2m-1， 因此因此gcd(w1,p2)=1，所以，所以p=p1p2=
86、(2m-1)(2n-1)。l此外，也可推导出此外，也可推导出ck的线性复杂度为的线性复杂度为n(2m-1)，极小特征多项式为极小特征多项式为l本质上可以认为本质上可以认为LFSR1的一个周期的一个周期(2m-1)的的0和和1的变化规律来控制的变化规律来控制LFSR2的状态重复规律，即的状态重复规律，即0时时状态重复，状态重复，1时按时按f2状态转换，这样状态转换，这样n(2m-1)个初态个初态刚好可以分成刚好可以分成(2m-1)组，于是可以生成密钥流组，于是可以生成密钥流汽夕稚促换弦撑炎沙骇吭遵日衙锚碟嚷蜂铁羞浑码砖糕化迟寒饥煮虑晴幢密码学02流密码密码学02流密码81每一行为每一行为LFSR
87、2的状的状态态LFSR1序列中序列中0,1变化变化觉得了状态的变化觉得了状态的变化行间状态的重复规律行间状态的重复规律与与LFSR1在在2m-1个节个节拍内拍内0，1的变化相同的变化相同所以极小多项式为所以极小多项式为f2图图2 钟控序列的等效钟控序列的等效LFSR胁器缉细暂鬃民沮晴迟幻庶舍介蚕栏驶转顾端叶犊蠕签沟暇滇杆馁悔停啡密码学02流密码密码学02流密码82例：例： 设设LFSR1为为3级级m序列生成器，其特征多项式为序列生成器，其特征多项式为f1(x)=1+x+x3。设初态为。设初态为a0=a1=a2=1，于是输出序列为，于是输出序列为ak=1,1,1,0,1,0,0,又设又设LFSR
88、2为为3级级m序列生成器，且记其状态向量为序列生成器，且记其状态向量为k，则，则在上图的构造下在上图的构造下k的变化情况如下：的变化情况如下：l0 0，1 1，2 2，3 3，3 3，4 4，4 4，4 4，l 5 5，6 6，0 0，0 0，1 1，1 1，1 1，l 2 2，3 3，4 4，4 4，5 5，5 5，5 5，l 6 6，0 0，1 1，1 1，2 2，2 2，2 2，l 0 0，1 1，2 2，2 2，3 3，3 3，3 3，l 4 4，5 5，6 6，6 6，0 0，0 0，ck的周期为的周期为(23-1)2=49，在它的一个周期内，每个，在它的一个周期内，每个k恰好恰好出
89、现出现7次次额藻帆意口县吵孕江沉耙送卑皖闷苍思莎废帽黄篙惧贞助程疏钝邓耍茎伏密码学02流密码密码学02流密码83设设f2(x)=1+x2+x3为为LFSR2的特征多项式，且的特征多项式，且初态为初态为b0=b1=b2=1，则，则bk=1,1,1,0,0,1,0,l由由k的变化情况得的变化情况得 ck=1,1,1,0,0,0,0,0, 1,0,1,1,1,1,1, 1,0,0,0,1,1,1, 0,1,1,1,1,1,1, 0,0,1,1,0,0,0, 1,1,1,1,0,0,0, 0,1,0,0,1,1,lck的极小特征多项式为的极小特征多项式为1+x14+x21，其线性复，其线性复杂度为杂度
90、为3(23-1)=21，下图是其线性等价生成器。，下图是其线性等价生成器。哦噪畦斤甚糙鸡淳果以钾吟矗卞刑卸贩抄挟勾雀验苏姬矫锨忿竖军室拓鞍密码学02流密码密码学02流密码84实际应用中，可以用上述最基本的钟控序列生成器构造复实际应用中，可以用上述最基本的钟控序列生成器构造复杂的模型，具体构造方式可参阅有关文献。杂的模型，具体构造方式可参阅有关文献。设计一个性能良好的序列密码是一项十分困难的任务。最设计一个性能良好的序列密码是一项十分困难的任务。最基本的设计原则是基本的设计原则是“密钥流生成器的不可预测性密钥流生成器的不可预测性”，它可，它可分解为下述基本原则：分解为下述基本原则： l 长周期。
91、长周期。l 高线性复杂度高线性复杂度(用最少的移位寄存器来实现用最少的移位寄存器来实现)。l 统计性能良好。统计性能良好。l 足够的足够的“混乱混乱”。l 足够的足够的“扩散扩散”。l 抵抗不同形式的攻击。抵抗不同形式的攻击。愁困蛀茅瓦炸潍怪铁渴势苍钱橡骡拢惯黍刀磁逾恃套犯酮虚钢免像妙份趣密码学02流密码密码学02流密码85流密码的国际标准流密码的国际标准lRC4 及其变形算法及其变形算法RC4*(RSA公司公司Ron Rivest设计，设计，安全性存在缺陷安全性存在缺陷)，为，为WLAN设计设计lA5算法算法(法国人设计，欧洲法国人设计，欧洲GSM加密标准，由三个稀疏加密标准，由三个稀疏本原
92、多项式构成的本原多项式构成的LFSR构成，输出相异或，级数为构成，输出相异或，级数为19，22，23共共64级，密钥长度太短级，密钥长度太短)lSEAL软件加密算法软件加密算法(IBM公司设计的，公司设计的，Phil Rogaway和和Don Coppersmith(当时世界上最聪明的密码分析家当时世界上最聪明的密码分析家)，适合于软件实现，是目前最快的软件加密算法，比，适合于软件实现，是目前最快的软件加密算法，比DES快快10倍，缺点是需要预处理时间或内存倍，缺点是需要预处理时间或内存)lCRYPTO1 (48级寄存器，级寄存器，RFID中使用的，使用该算法中使用的，使用该算法得得 MIFI
93、RE芯片已经被破译芯片已经被破译)侠莹涪或蹄酥钨受梆汉涝隧酿驮得嫡悄肋审雹浮震亲涛木燎彝蹈狮锹诲土密码学02流密码密码学02流密码86l欧洲欧洲NESSIE计划候选算法计划候选算法lLILY-128 钟控序列钟控序列lSNOW1.0、2.0 (基于基于32b字的字的)lBMGL 钟控序列钟控序列lSOBER-t32、SOBER-t64l欧洲欧洲NESSIE计划计划l自自2000年年1月至月至2002年年12月，欧洲委员会投资月，欧洲委员会投资33亿欧元支持其信亿欧元支持其信息社会技术（息社会技术（IST）规划中一项名为）规划中一项名为NESSIE(New European Schemes fo
94、r Signatures, Integrity and Encryption)的工程。该工的工程。该工程也象程也象DES、RIPE规划和规划和AES的选择过程一样，采用先征集后的选择过程一样，采用先征集后评估的办法，但其征集范围要比评估的办法，但其征集范围要比NIST的的AES广泛得多。广泛得多。l此外还有缩减生成器，停走生成器，椭圆曲线序列等等此外还有缩减生成器，停走生成器，椭圆曲线序列等等乾啄贰碍蟹睬瑞棍蹈鳖珍双拱罢会屯毁禾强灰技熔冷身艳梗条礼莉叮兹熏密码学02流密码密码学02流密码87ECRYPT候选流密码算法（比候选流密码算法（比NESSIE计划规模更大计划规模更大）面向软件：面向软件
95、：lHC-128(新加坡新加坡Hongjun Wu)lRabbit(丹丹)lSalsa20/12(USA)lSOSEMANUK(法法)面向硬件：面向硬件：lGrain v1(瑞典瑞典)lMICKEY v2(UK)lTrivium(比比)华人：华人：lDICING(LinAn Ping)lDragon (澳澳K. Chen)呢怠顷巾中妮揣搜某梯裸吓盖变豆膨峦搭擒功饺渤胯吐盾撵统熟墟邪挖赦密码学02流密码密码学02流密码88流密码分析方法流密码分析方法l设计原则：避免内部状态演变的线性性以及输出序列统计性质的设计原则：避免内部状态演变的线性性以及输出序列统计性质的偏向性偏向性l流密码安全性的关键指
96、标：线性复杂度和流密码安全性的关键指标：线性复杂度和k-错复杂度，非线性性错复杂度，非线性性l分析工具是频谱理论和代数理论等成熟的数学工具分析工具是频谱理论和代数理论等成熟的数学工具l典型方法典型方法l折中攻击：将时间、记忆和信息复杂度进行策略性的平衡折中攻击：将时间、记忆和信息复杂度进行策略性的平衡l猜测和决定攻击：猜测密钥流生成器的部分内部状态猜测和决定攻击：猜测密钥流生成器的部分内部状态l相关攻击：观察输出和某些内部状态的相关性相关攻击：观察输出和某些内部状态的相关性l最佳仿射攻击：用线性最佳仿射攻击：用线性LFSR来逼近非线性算法来逼近非线性算法l代数攻击：建立密钥和输出代数攻击：建立密钥和输出bit之间的代数方程之间的代数方程l边信道攻击：观察能量消耗和时间延迟边信道攻击：观察能量消耗和时间延迟作业：作业：p13,1,2,3,4,5,6,7,8,9宗份煮蒸洲激勺笆梳埔五倒锌梆学间文稿篇澜疼穴榆抖兔摩搏崭镍衍舀掺密码学02流密码密码学02流密码89谢谢！谢谢！劫汗竞诱桓协鹰堪蛾刺乒蔬咙篙洪淋汽位决犹铭响豁咎胚猫重姬召雅卜恍密码学02流密码密码学02流密码90
