第2章-流密码

1、密码学基础密码学基础-UESTC第第2章章 流密码流密码2.1 流密码的基本概念流密码的基本概念2.2 线性反馈移位寄存器线性反馈移位寄存器2.3 线性移位寄存器的一元多项式表示线性移位寄存器的一元多项式表示2.4 m序列的伪随机性序列的伪随机性2.5 m序列密码的破译序列密码的破译2.6 非线性序列非线性序列密码学基础密码学基础-UESTC一次一密密码一次一密密码 一种理想的加密方案，叫做一次一密密码（一种理想的加密方案，叫做一次一密密码（one-time pad），由），由Major Joseph Mauborgne和和AT&T公公司的司的Gilbert Vernam1917年发明

2、的。年发明的。 一次一密乱码本是一个大的不重复的真随机密钥字一次一密乱码本是一个大的不重复的真随机密钥字母集，密钥字母集被写在几张纸上，并一起粘成一母集，密钥字母集被写在几张纸上，并一起粘成一个乱码本。个乱码本。 发方用乱码本中的每一密钥字母准确地加密一个明发方用乱码本中的每一密钥字母准确地加密一个明文字符。加密是明文字符和一次一密乱码本密钥字文字符。加密是明文字符和一次一密乱码本密钥字符的模符的模26加法。加法。密码学基础密码学基础-UESTC一次一密密码一次一密密码 m密文 COne-Time Padk bits of random key K1 0 0 1 1 0 1 0 1 00 1

3、1 1 0 1 1 0 1 11 1 0 1 0 0 0 1 1 1使用随机数序列，并且只能使用一次k0 0 = 00 1 = 11 0 = 11 1 = 0异或密码学基础密码学基础-UESTC流密码的基本思想流密码的基本思想:密钥密钥:k产生一个密钥流产生一个密钥流:z=z0 z1，明文串明文串:x=x0 x1 x2加密：加密： y=y0 y1 y2=Ez0(x0)Ez1(x1)Ez2(x2)。密钥流发生器密钥流发生器f： zi=f(k,i)，i是加密器中的记忆元件（存储器）在时刻是加密器中的记忆元件（存储器）在时刻i的状态的状态，f是由密钥是由密钥k和和i产生的函数。产生的函数。2.1 流

4、密码的基本概念流密码的基本概念密码学基础密码学基础-UESTC流密码流密码: 同步流密码和自同步流密码同步流密码和自同步流密码i独立于明文字符的叫做同步流密码，否独立于明文字符的叫做同步流密码，否则叫做自同步流密码。则叫做自同步流密码。在同步流密码中，由于在同步流密码中，由于zi=f(k,i)与明文字与明文字符无关，因而此时密文字符符无关，因而此时密文字符yi=Ezi(xi)也也不依不依赖于此前的明文字符赖于此前的明文字符。因此，可将同步流密。因此，可将同步流密码的加密器分成密钥流产生器和加密变换器码的加密器分成密钥流产生器和加密变换器两个部分。两个部分。2.1.1 同步流密码同步流密码密码学

5、基础密码学基础-UESTC图图2.2 同步流密码体制模型同步流密码体制模型 izxEiixiyiz izyDi滚动密钥生成器iyixiz滚动密钥生成器安全信道kk密码学基础密码学基础-UESTC图图2.3 加法流密码体制模型加法流密码体制模型二元加法流密码是目前最为常用的流密码体制，其二元加法流密码是目前最为常用的流密码体制，其加密变换可表示为加密变换可表示为yi=zi xi。 密码学基础密码学基础-UESTC一次一密密码是加法流密码的原型。事一次一密密码是加法流密码的原型。事实上，如果密钥用作滚动密钥流，则加法流实上，如果密钥用作滚动密钥流，则加法流密码就退化成一次一密密码。密码就退化成一次

6、一密密码。实际使用中，密码设计者的最大愿望是实际使用中，密码设计者的最大愿望是设计出一个滚动密钥生成器，使得密钥经其设计出一个滚动密钥生成器，使得密钥经其扩展成的密钥流序列具有如下性质：扩展成的密钥流序列具有如下性质：极大的极大的周期周期、良好的统计特性良好的统计特性、抗线性分析抗线性分析。 密码学基础密码学基础-UESTC有限状态自动机是具有离散输入和输出（输入有限状态自动机是具有离散输入和输出（输入集和输出集均有限）的一种数学模型，由以下集和输出集均有限）的一种数学模型，由以下3部部分组成：分组成： 有限状态集有限状态集S= si | i=1,2,l 。 有限输入字符集有限输入字符集A1=

7、 A(1)j| j=1,2,m和有限输和有限输出字符集出字符集A2=A(2)k |k=1,2,n。 转移函数转移函数A(2)k=f1(si, A(1)j )，sh=f2(si, A(1)j) 即在状态为即在状态为si，输入为输入为A(1)j时，输出为时，输出为A(2)k，而状而状态转移为态转移为sh。2.1.2 有限状态自动机有限状态自动机密码学基础密码学基础-UESTC有限状态自动机可用有向图表示，称为有限状态自动机可用有向图表示，称为转移图。转移图。转移图的顶点对应于自动机的状态，若转移图的顶点对应于自动机的状态，若状态状态si在输入在输入A(1)i时转为状态时转为状态sj，且输出一字且输

8、出一字符符A(2)j，则在转移图中，从状态则在转移图中，从状态si到状态到状态sj有有一条标有一条标有(A(1)i, A(2)j)的弧线的弧线密码学基础密码学基础-UESTC密码学基础密码学基础-UESTC图图2.4 有限状态自动机的转移图有限状态自动机的转移图密码学基础密码学基础-UESTC若输入序列为若输入序列为A(1)1 A(1)2 A(1)1 A(1)3 A(1)3 A(1)1，初始状态为初始状态为s1，则得到状态序列则得到状态序列s1s2s2s3s2s1s2输出字符序列输出字符序列A(2)1 A(2)1 A(2)2 A(2)1 A(2)3 A(2)1密码学基础密码学基础-UESTC密

9、钥流产生器密钥流产生器: 参数为参数为k的有限状态自动机，的有限状态自动机，一个输出符号集一个输出符号集Z、一个状态集一个状态集、两个函数、两个函数和和以及一个初始状态以及一个初始状态0组成。组成。状态转移函数状态转移函数:ii+1，将当前状态将当前状态i变为一个新变为一个新状态状态i+1，输出函数输出函数:izi，当前状态当前状态i变为输出符号集中的变为输出符号集中的一个元素一个元素zi。2.1.3 密钥流产生器密钥流产生器密码学基础密码学基础-UESTC图图2.5 作为有限状态自动机的密钥流生成器作为有限状态自动机的密钥流生成器密码学基础密码学基础-UESTC关键关键:和和，使得输出序列使

10、得输出序列z满足密钥流序列满足密钥流序列z应满足的几个条件，并且要求在设备上是节省的应满足的几个条件，并且要求在设备上是节省的和容易实现的。为了实现这一目标，必须采用非和容易实现的。为了实现这一目标，必须采用非线性函数。线性函数。采用线性的采用线性的和非线性的和非线性的时，将能够进行深入时，将能够进行深入的分析并可以得到好的生成器。的分析并可以得到好的生成器。可将这类生成器分成驱动部分和非线性组合部可将这类生成器分成驱动部分和非线性组合部分分.驱动部分控制生成器的状态转移，并为非线性驱动部分控制生成器的状态转移，并为非线性组合部分提供统计性能好的序列；组合部分提供统计性能好的序列；非线性组合部

11、分要利用这些序列组合出满足要非线性组合部分要利用这些序列组合出满足要求的密钥流序列。求的密钥流序列。密码学基础密码学基础-UESTC图图2.6 密钥流生成器的分解密钥流生成器的分解密码学基础密码学基础-UESTC图图2.7 常见的两种密钥流产生器常见的两种密钥流产生器密码学基础密码学基础-UESTC移位寄存器是流密码产生密钥流的一个主要组成移位寄存器是流密码产生密钥流的一个主要组成部分。部分。GF(2)上一个上一个n级反馈移位寄存器由级反馈移位寄存器由n个二元存储个二元存储器器与一个与一个反馈函数反馈函数f(a1,a2,an)组成，如图组成，如图2所示。所示。2.2 线性反馈移位寄存器线性反馈

12、移位寄存器密码学基础密码学基础-UESTC图图2 GF(2)上的上的n级反馈移位寄存器级反馈移位寄存器存储器存储器存储器存储器存储器存储器存储器存储器密码学基础密码学基础-UESTC在任一时刻，这些级的内容构成该反馈移位寄存在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于器的状态，每一状态对应于GF(2)上的一个上的一个n维向维向量，共有量，共有2n种可能的状态。种可能的状态。每一时刻的状态可用每一时刻的状态可用n维向量维向量(a1,a2,an)表示，其中表示，其中ai是第是第i级存储器的内容。级存储器的内容。密码学基础密码学基础-UESTC初始状态初始状态由用户确定。由用户

13、确定。反馈函数反馈函数f(a1,a2,an)是是n元布尔函数，即函数的自元布尔函数，即函数的自变量和因变量只取变量和因变量只取0和和1这两个可能的值。这两个可能的值。函数中的运算有函数中的运算有逻辑与、逻辑或、逻辑补等逻辑与、逻辑或、逻辑补等运算。运算。密码学基础密码学基础-UESTC例例 图图3 是一个是一个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 0 1

14、01110表表2.2 一个一个3级反馈移位级反馈移位寄存器的状态和输出寄存器的状态和输出即输出序列为即输出序列为101110111011，周期为周期为4。密码学基础密码学基础-UESTCGF(2)上的上的n级线性反馈移位寄存器级线性反馈移位寄存器nnnnacacacaaaf121121),( 线性反馈移位寄存器线性反馈移位寄存器LFSR（linear feedback shift register）密码学基础密码学基础-UESTC输出序列输出序列at满足：满足：nnnnacacacaaaf121121),( 11312212111 nnnnnnnnacacacaacacaca线性反馈移位寄存器

15、：线性反馈移位寄存器：实现简单、速度快、有较为成熟的理论，实现简单、速度快、有较为成熟的理论，成为构造成为构造密钥流生成器的最重要的部件之一密钥流生成器的最重要的部件之一。, 2 , 1,1111 tacacacatntntntn密码学基础密码学基础-UESTC例例 下图是一个下图是一个5级线性反馈移位寄存器，其初始状级线性反馈移位寄存器，其初始状态为（态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)可求出输出序列为可求出输出序列为1001101001000010101110110001111100110周期为周期为31。密钥流的周期密钥流的周期 给定密钥流给定密钥流 ，如果，如果

16、存在整数存在整数r，使得对于任意，使得对于任意 ，都有，都有 ，则称则称 r为该密钥流的一个周期，称满足为该密钥流的一个周期，称满足 的的最小正整数最小正整数为该密钥流的最小周期或简称为该密钥流的最小周期或简称周周期期。123 ,inaa a aaiairiaairiaa密码学基础密码学基础-UESTC总是假定总是假定c1,c2,cn中至少中至少 0，否则，否则 f(a1,a2,an)0。 总是假定总是假定cn=1。LFSR输出序列的性质：输出序列的性质：完全由其反馈函数决定。完全由其反馈函数决定。n级级LFSR状态数：状态数：最多有最多有2n个。个。n级级LFSR的状态周期：的状态周期： 2

17、n-1。输出序列的周期输出序列的周期=状态周期状态周期， 2n-1。选择合适的反馈函数可使序列的周期达到最大值选择合适的反馈函数可使序列的周期达到最大值2n-1 ，周期达到最大值的序列称为周期达到最大值的序列称为m序列序列。密码学基础密码学基础-UESTC设设n级线性移位寄存器的输出序列满足递推关系级线性移位寄存器的输出序列满足递推关系an+k=c1an+k-1 c2an+k-2 cnak (*) 用延迟算子用延迟算子 D(Dak=ak-1) 作为未定元，给出的反作为未定元，给出的反馈多项式为：馈多项式为： p(D)=1+c1D+cn-1Dn-1cnDn 这种递推关系这种递推关系 可用一个一元

18、高次多项式可用一个一元高次多项式p(x)=1+c1x+cn-1xn-1cnxn表示，称这个多项式为表示，称这个多项式为LFSR的特征多项式的特征多项式或或特征特征多项式。多项式。2.3 线性移位寄存器的一元多项式表示线性移位寄存器的一元多项式表示记记2n-1个非零序列的全体为个非零序列的全体为G(p(x)密码学基础密码学基础-UESTC定义定义2.1 给定序列给定序列ai，幂级数幂级数称为该序列的称为该序列的生成函数生成函数。11( )iiiA xax密码学基础密码学基础-UESTC定理定理2.1 设设p(x)=1+c1x+cn-1xn-1+cnxn是是GF(2)上的上的多项式，多项式，G(p

19、(x)中任一序列中任一序列ai的生成函数的生成函数A(x)满满足：足：)()()(xpxxA 111( )()nin ijn ijijxcxa x其中其中密码学基础密码学基础-UESTC证明：证明： 在等式在等式an+1=c1an c2an-1 cna1an+2=c1an+1 c2an cna2 两边分别乘以两边分别乘以xn,xn+1,，再求和，可得再求和，可得A(x)-(a1+a2x+anxn-1)=c1xA(x)-(a1+a2x+an-1xn-2)+c2x2A(x)-(a1+a2x+an-2xn-3)+cnxnA(x)(1+c1x+cn-1xn-1+cnxn)A(x)=(a1+a2x+an

20、xn-1)+c1x(a1+a2x+an-1xn-2)+c2x2(a1+a2x+an-2xn-3)+cn-1xn-1a1移项移项整理整理密码学基础密码学基础-UESTC(1+c1x+cn-1xn-1+cnxn)A(x)=(a1+a2x+anxn-1)+c1x(a1+a2x+an-1xn-2)+c2x2(a1+a2x+an-2xn-3)+cn-1xn-1a1移项移项整理整理。xxaxcxAxpniijjjinin证证毕毕 111)()()()( 1)(deg)()()(: nxxpxxA 注注意意密码学基础密码学基础-UESTC定理定理2.2 p(x)|q(x)的充要条件是的充要条件是G(p(x)

21、 G(q(x)。证明证明 (1)必要性：必要性：若若p(x)|q(x)，可设可设q(x)=p(x)r(x)，因此因此所以若所以若aiG(p(x)，则则aiG(q(x)，即即G(p(x) G(q(x)。)()()()()()()()()()(xqxrxxrxpxrxxpxxA 密码学基础密码学基础-UESTC上述定理说明上述定理说明可用可用n级级LFSR产生的序列，也可用产生的序列，也可用级数更多的级数更多的LFSR来产生。来产生。).(| )()()()(,)()()(1)()(),()(),()()(1)(, 1)()()()(),(),()(xqxpxrxpxqxqxrxpxqxraxrx

22、qGaxqGxpG。xpxpGax。xpxxpGaxxqGxpGiiii故故的的生生成成函函数数使使为为生生成成函函数数以以为为生生成成函函数数以以若若 (2)充分性：充分性：图图2.6 密钥流生成器的分解密钥流生成器的分解密码学基础密码学基础-UESTC输出序列输出序列at满足：满足：nnnnacacacaaaf121121),( 11312212111 nnnnnnnnacacacaacacaca线性反馈移位寄存器：线性反馈移位寄存器：实现简单、速度快、有较为成熟的理论，实现简单、速度快、有较为成熟的理论，成为构造成为构造密钥流生成器的最重要的部件之一密钥流生成器的最重要的部件之一。, 2

23、 , 1,1111 tacacacatntntntn密钥流的周期密钥流的周期 给定密钥流给定密钥流 ，如果，如果存在整数存在整数r，使得对于任意，使得对于任意 ，都有，都有 ，则称则称 r为该密钥流的一个周期，称满足为该密钥流的一个周期，称满足 的的最小正整数最小正整数为该密钥流的最小周期或简称为该密钥流的最小周期或简称周周期期。123 ,inaa a aaiairiaairiaa密码学基础密码学基础-UESTC定义定义2.2 设设p(x)是是GF(2)上的多项式，使上的多项式，使p(x)|(xp-1)成立的最小正整数成立的最小正整数p称为称为p(x)的周期的周期或或阶阶。密码学基础密码学基础

24、-UESTC定理定理2.3 若序列若序列ai的特征多项式的特征多项式p(x)定义在定义在GF(2)上，上，p是是p(x)的周期，则的周期，则ai的周期的周期r|p。证明：证明：.|0,0 ,.,3 ,2 , 1,1)()1deg(1)(deg(,)(deg()()()()1()()()()()()()()()()(1),()1( | )(prtaaaarttkrpiaapxAxnxnpxqxqxxAxxqxxAxqxpxxAxpxqxpxxqxxpititkripiipipppp 所所以以则则设设故故得得由由于于得得又又使使 密码学基础密码学基础-UESTC n n级级LFSRLFSR输出序列

25、的周期输出序列的周期r: r: 不依赖于初始条件，不依赖于初始条件，而依赖于特征多项式而依赖于特征多项式p(x)p(x)。 LFSRLFSR遍历遍历2 2n n-1-1个非零状态，这时序列的周期达个非零状态，这时序列的周期达到最大到最大2 2n n-1-1，这种序列就是这种序列就是m m序列序列。 对于对于特征多项式一样特征多项式一样，而仅初始条件不同的两，而仅初始条件不同的两个输出个输出m m序列，一个记为序列，一个记为 a a(1)(1)i i ，另一个记为另一个记为 a a(2)(2)i i ，其中一个必是另一个的移位，即存在一个其中一个必是另一个的移位，即存在一个常数常数k k，使得使

26、得a a(1)(1)i i=a=a(2)(2)k+ik+i, i=1,2, i=1,2,密码学基础密码学基础-UESTC下面讨论特征多项式满足什么条件时，下面讨论特征多项式满足什么条件时，LFSR的输的输出序列为出序列为m序列序列。密码学基础密码学基础-UESTC定理定理2.4 设设p(x)是是n次不可约多项式，周期为次不可约多项式，周期为m，序序列列aiG(p(x)，则则ai的周期为的周期为m。证明：设证明：设ai的周期为的周期为r，由定理由定理2.3有有r|m，所以所以rm。设设A(x)为为ai的生成函数，的生成函数，A(x)= (x) / p(x)，即即p(x)A(x)= (x)0， (

27、x)的次数不超过的次数不超过n-1。而而A(x)=aixi-1=a1+a2x+arxr-1 +xr(a1+a2x+arxr-1) +(xr)2(a1+a2x+arxr-1)+=a1+a2x+arxr-1/(1-xr)=a1+a2x+arxr-1/(xr-1)密码学基础密码学基础-UESTC112112( )( )1( )( )()( )(1)( ) | ( )(1)gcd( ( ), ( )1( ) | (1),rrrrrrrraa xa xxA xxp xp x aa xa xxxp xxxp xxp xxmrmr因此故 密码学基础密码学基础-UESTC定理定理2.5 n级级LFSR产生的序

28、列有最大周期产生的序列有最大周期2n-1的必的必要条件是其特征多项式为不可约的。要条件是其特征多项式为不可约的。证明：设证明：设n级级LFSR产生的序列周期达到最大产生的序列周期达到最大2n-1。反证法：反证法：设特征多项式为设特征多项式为p(x)，若若p(x)可约，可设可约，可设为为p(x)=g(x)h(x)，其中其中g(x)不可约，且次数不可约，且次数k2，当当1in-2时，时，n长长m序列的一个周期内，长序列的一个周期内，长为为i的的0游程游程数目等于序列中如下形式的状态数目：数目等于序列中如下形式的状态数目： 10001* *，其中，其中n-i-2个个*可任取可任取0或或1。这种状。这

29、种状态共有态共有2n-i-2个。同理可得长为个。同理可得长为i的的1游程数目也等于游程数目也等于 2n-i-2，所以长为所以长为i的游程总数为的游程总数为2n-i-1。密码学基础密码学基础-UESTC由于寄存器中不会出现全由于寄存器中不会出现全0状态，所以不会出现状态，所以不会出现0的的n游程，但必有一个游程，但必有一个1的的n游程，而且游程，而且1的游程不的游程不会更大，因为若出现会更大，因为若出现1的的n+1游程，就必然有两个游程，就必然有两个相邻的全相邻的全1状态，但这是不可能的。这就证明了状态，但这是不可能的。这就证明了1的的n游程必然出现在如下的串中：游程必然出现在如下的串中：当这当

30、这n+2位通过移位寄存器时，便依次产生以下状位通过移位寄存器时，便依次产生以下状态：态： 10 111 0n个110 111n个1111n个11111 0n个密码学基础密码学基础-UESTC由于由于 ， 这两个状态只能各出现这两个状态只能各出现一次，所以不会有一次，所以不会有1的的n-1游程。游程。110 111n个11111 0n个21111 122nn ini 于是在一个周期内，总游程数为于是在一个周期内，总游程数为0的的n-1游程只有一个游程只有一个:1000101个个 n密码学基础密码学基础-UESTC ai是周期为是周期为2n-1的的m序列，对于任一正整数序列，对于任一正整数(02n

31、-1)，ai+ai+在一个周期内为在一个周期内为0的位的数目的位的数目正好是序列正好是序列ai和和ai+对应位相同的位的数目。对应位相同的位的数目。设序列设序列ai满足递推关系：满足递推关系： 序序列列。也也是是项项式式，所所以以因因为为对对应应同同样样的的特特征征多多满满足足：序序列列令令故故mbbcbcbcbbaabaacaacaacaaacacacaacacacaihnnhnhnhjjjjhhnnhnhnhnhnhnhhnnhnhnhhnnhnhnh,)()()(221122211122112211 12112212)(11 nnnnR 故故密码学基础密码学基础-UESTC上节课回顾上节

32、课回顾n级线性反馈移位寄存器生成序列为级线性反馈移位寄存器生成序列为m序列当且仅当序列当且仅当其特征多项式是其特征多项式是本原多项式本原多项式。m序列满足序列满足Golomb对对伪随机周期序列伪随机周期序列提出了应满足提出了应满足的的3个随机性公设，即个随机性公设，即 ai中中0与与1出现的概率基本上相同出现的概率基本上相同; 0与与1在序列中每一位置上出现的概率相同在序列中每一位置上出现的概率相同; 通过对序列与其平移后的序列做比较，不能给通过对序列与其平移后的序列做比较，不能给出其他任何信息。出其他任何信息。密码学基础密码学基础-UESTC2.5 m序列密码的破译序列密码的破译寻找寻找m序

33、列的递推关系式。序列的递推关系式。密码学基础密码学基础-UESTC设滚动密钥生成器是线性反馈移位寄存器，产生设滚动密钥生成器是线性反馈移位寄存器，产生的密钥是的密钥是m序列。序列。2.5 m序列密码的破译序列密码的破译11211,hhhhhhhnhnaaaaSSaa密码学基础密码学基础-UESTC设序列设序列ai满足线性递推关系：满足线性递推关系：可表示为可表示为1122h nh nh nnhac ac ac a 12112110 1 000 0 10hhhhnnnh nh naaaaccccaa 密码学基础密码学基础-UESTC或或 Sh+1=MSh，其中其中又设敌手知道一段长为又设敌手知道

34、一段长为2n的明文的明文-密文对，即已知密文对，即已知12101000010ccccMnnn122nxx xx122nyy yy密码学基础密码学基础-UESTC于是可求出一段长为于是可求出一段长为2n的密钥序列的密钥序列其中其中 ,由此可推出线性反馈移位寄存由此可推出线性反馈移位寄存器器连续的连续的n+1个状态个状态：1 22nzz zziiizxy1121222312311122122nnnnnnnnnnnSz zza aaSz zza aaSzzzaaa记为记为记为密码学基础密码学基础-UESTC做矩阵做矩阵而而则则12nXSSS122311221112111nnnnnnnnnnnnaaa

35、aaaaaacccaaacccX111122nnnnncccaaaX密码学基础密码学基础-UESTC例例 设敌手得到密文串设敌手得到密文串: : 101101011110010和相应的明文串和相应的明文串: : 011001111111001相应的密钥流相应的密钥流: : 110100100001011进一步假定敌手还知道密钥流是使用进一步假定敌手还知道密钥流是使用5 5级线性反馈级线性反馈移位寄存器产生的，那么敌手可分别用密文串中移位寄存器产生的，那么敌手可分别用密文串中的前的前1010个比特和明文串中的前个比特和明文串中的前1010个比特建立如下个比特建立如下方程方程12345234566

36、7891054321345674567856789aaaaaaaaaaaaaaacccccaaaaaaaaaaaaaaa密码学基础密码学基础-UESTC即即而而543211 1 0 1 01 0 1 0 00 1 0 0 00 1 0 0 11 0 0 1 00 0 1 0 0ccccc11 1 0 1 00 1 0 0 11 0 1 0 01 0 0 1 00 1 0 0 10 0 0 0 11 0 0 1 00 1 0 1 10 0 1 0 01 0 1 1 0密码学基础密码学基础-UESTC从而得到从而得到所以所以密钥流的递推关系为密钥流的递推关系为543210 1 0 0 11 0 0

37、 1 00 1 0 0 00 0 0 0 10 1 0 1 11 0 1 1 0ccccc543211 0 0 1 0ccccc55233iiiiiac ac aaa密码学基础密码学基础-UESTC71线性反馈移位寄存器（线性反馈移位寄存器（LFSR）的综合）的综合根据密码学的需要，对于根据密码学的需要，对于LFSR主要考虑下面两问题：主要考虑下面两问题：(1)如何利用级数尽可能小的如何利用级数尽可能小的LFSR产生周期长、统计特性好产生周期长、统计特性好的序列；的序列；(2)已知一个序列已知一个序列a，如何构造一个尽可能短的，如何构造一个尽可能短的LFSR来产生来产生a。密码学基础密码学基础

38、-UESTC72线性反馈移位寄存器的综合问题就在于线性反馈移位寄存器的综合问题就在于根据序列根据序列的少量比特求出整个序列所满足的线性递推关系的少量比特求出整个序列所满足的线性递推关系。一个自然的想法就是：先假定线性递推关系，然一个自然的想法就是：先假定线性递推关系，然后由序列的各项应该适合之而导出线性方程组；后由序列的各项应该适合之而导出线性方程组；但这样的方法有其不易行之处在于：但这样的方法有其不易行之处在于：不容易确定所适用的不容易确定所适用的LFSRLFSR的级数的级数n n，从而就不能，从而就不能导致恰当规模的线性方程组；导致恰当规模的线性方程组；当上述的当上述的n n很大时，求解相

39、应规模的线性方程组很大时，求解相应规模的线性方程组也很困难。也很困难。事实上，对于事实上，对于线性反馈移位寄存器的线性反馈移位寄存器的综合问题已经出现了著名的解法：综合问题已经出现了著名的解法： Berlekamp-Massey Berlekamp-Massey迭代算法迭代算法，简称，简称B-MB-M算法算法。线性反馈移位寄存器（线性反馈移位寄存器（LFSR）的综合）的综合密码学基础密码学基础-UESTC73B-MB-M算法描述算法描述InputInput：S SN N=a=a0 0a a1 1a a2 2a aN-1N-1Step1Step1：置：置f f0 0(x)=1(x)=1，L L0

40、 0=0=0（初值）（初值）Step2Step2：设：设f ，i=0,1,2,i=0,1,2,n,n（0 0 nNnN）均已求）均已求出，且出，且L L0 0 L L1 1 L L2 2 L Ln n。设。设 , ,由此计算由此计算 。Step3Step3：当：当d dn n=0=0时，取时，取f fn+1n+1(x)=f(x)=fn n(x),L(x),Ln+1n+1=L=Ln n。 当当d dn n=1=1时，若时，若L Ln n=0,=0,则取则取f fn+1n+1(x)=x(x)=xn+1n+1+1,L+1,Ln+1n+1=n+1=n+1； 否则否则, ,找出找出m(0m(0 mn)m

41、n)使使L Lm m L Lm+1m+1= =L Lm+2 m+2 = = =L Ln n, ,取取f fn+1n+1(x)=f(x)=fn n(x)+x(x)+xn-mn-mf fm m(x),L(x),Ln+1n+1=maxL=maxLn n,n+1- L,n+1- Ln n 。对于对于n=0,1,2,n=0,1,2,，重复，重复Step2Step2与与Step3Step3，直至，直至n=N-1n=N-1OutputOutput：f nnLnLnnnxcxcxcxf)(2)(2)(11)(nnLnnLnnnnnnacacacad)(2)(21)(1密码学基础密码学基础-UESTC74B-M

42、B-M算法举例算法举例 输入：S8=10101111输出：ndnfnLnmfm0101234567811001011x1121x21x321xx321xx431xx1122244421x250011121x密码学基础密码学基础-UESTC75有关有关B-MB-M算法的结果算法的结果 应用应用B-MB-M算法，若以算法，若以N N长序列长序列S SN N为输入，得到输出为输入，得到输出f ，则，则以以f fN N(x)(x)为联接多项式的为联接多项式的L LN N-LFSR-LFSR是产是产生生S SN N的最短的最短LFSRLFSR，且当，且当 时，迭代至第时，迭代至第2L2LN N步就得到最

43、终输出，即：步就得到最终输出，即： 。当当 时，产生时，产生S SN N的最短的最短LFSRLFSR只是只是上述一个；当上述一个；当 时，产生时，产生S SN N的最短的最短LFSRLFSR一共有一共有 个。个。由上述定理知，在前面的例子中，由上述定理知，在前面的例子中，以以f f8 8(x)=(x)=1+1+x x3 3+x+x4 4为联接多项式的为联接多项式的4-4-LFSRLFSR是唯一是唯一的产生的产生S S8 8=10101111=10101111的最短的最短LFSRLFSR。2NLN2NLNNNLLLxfLxfNN),(),(222NLNNLN22密码学基础密码学基础-UESTC7

44、6有关有关B-MB-M算法的结果算法的结果对于周期序列，也可应用B-M算法求出产生它的最短LFSR的联接多项式，不过须注意：一定得是针对两个周期段去求才正确！ 对周期为p的序列a=a0a1a2，应用B-M算法于S2p=a0a1ap-1a0a1ap-1求出时，必f2p(x)的次数必为L2p，且以f2p(x)为联接多项式的L2p-LFSR是唯一的产生a的最短LFSR。 。ppLLLxfLxfpp2222),(),(22密码学基础密码学基础-UESTC77线性复杂度概念线性复杂度概念能够产生（有限长或周期）序列a的最短LFSR的级数称为a的线性复杂度，记为(a)；约定：(0)=0。若对序列a应用B-

45、M算法产生的输出为，则(a)=L。研讨研讨：若a为n-级m-序列，则(a)= 。n密码学基础密码学基础-UESTC2.6 非线性序列非线性序列 为了使密钥流生成器输出的二元序列尽可能复杂，为了使密钥流生成器输出的二元序列尽可能复杂，应保证其应保证其周期尽可能大周期尽可能大、线性复杂度线性复杂度和和不可预测不可预测性尽可能高性尽可能高，因此常使用多个，因此常使用多个LFSR来构造二元序来构造二元序列，称每个列，称每个LFSR的输出序列为的输出序列为驱动序列驱动序列，显然密，显然密钥流生成器输出序列的周期不大于各驱动序列周钥流生成器输出序列的周期不大于各驱动序列周期的乘积，因此，提高输出序列的线性

46、复杂度应期的乘积，因此，提高输出序列的线性复杂度应从极大化其周期开始。从极大化其周期开始。密码学基础密码学基础-UESTC二元序列的二元序列的线性复杂度线性复杂度: 指生成该序列的最短指生成该序列的最短LFSR的级数。的级数。二元序列的二元序列的极小特征多项式极小特征多项式: 最短最短LFSR的特征多的特征多项式。项式。介绍介绍4种由多个种由多个LFSR构成的构成的非线性序列生成器非线性序列生成器。密码学基础密码学基础-UESTCGeffe序列生成器由序列生成器由3个个LFSR组成，其中组成，其中LFSR2作作为控制生成器使用，如图为控制生成器使用，如图2.12所示。所示。2.6.1 Geff

47、e序列生成器序列生成器密码学基础密码学基础-UESTC图图2.12 Geffe序列生成器序列生成器) 1(ka)2(ka)3(kakb)3()2()3()2() 1()2()3()2() 1(kkkkkkkkkkaaaaaaaaab 设设LFSRi的特征多项式分的特征多项式分别为别为ni次本原多项式，且次本原多项式，且ni 两两互素两两互素则则Geffe序列的周期序列的周期=3121ini线性复杂度线性复杂度=1323nnnn密码学基础密码学基础-UESTCGeffe序列的周期实现了极大化，且序列的周期实现了极大化，且0与与1之间的分之间的分布大体上是平衡的。布大体上是平衡的。密码学基础密码学

48、基础-UESTCJ-K触发器如图触发器如图2.14所示，它的两个输入端分别用所示，它的两个输入端分别用J和和K表示，其输出表示，其输出ck不仅依赖于输入，还依赖于前不仅依赖于输入，还依赖于前一个输出位一个输出位ck-1，即即其中其中x1和和x2分别是分别是J和和K端的输入。由此可得端的输入。由此可得J-K触触发器的真值表，如表发器的真值表，如表2.3。2.6.2 J-K触发器触发器1211kkcxxcx密码学基础密码学基础-UESTC图图2.14 J-K触发器触发器1211kkcxxcx密码学基础密码学基础-UESTC密码学基础密码学基础-UESTC图图2.15 2.15 利用利用J-KJ-K

49、触发器的非线性序列生成器触发器的非线性序列生成器ak :m级级m序列序列 bk:n级级m序列序列111kkkkkkkkkcabcaabca利用利用J-K触发器的非线性序列生成器见图触发器的非线性序列生成器见图2.15。密码学基础密码学基础-UESTC当当m与与n互素且互素且a0+b0=1时，序列时，序列ck的周期为的周期为(2m-1)(2n-1)。111kkkkkkkkkcabcaabca密码学基础密码学基础-UESTC例例2.7 令令m=2,n=3，两个驱动两个驱动m序列分别为序列分别为ak=0,1,1,和和bk=1,0,0,1,0,1,1,于是，输出序列于是，输出序列ck是是0,1,1,0

50、,1,0,0,1,1,1,0,1,0,1,0,0,1,0,0,1,0,其周期为其周期为(22-1)(23-1)=21。密码学基础密码学基础-UESTC 由由ck=(ak+bk+1)ck-1+ak可得可得 因此，如果知道因此，如果知道ck中相邻位的值中相邻位的值ck-1和和ck，就可就可以推断出以推断出ak和和bk中的一个。而一旦知道足够多的这中的一个。而一旦知道足够多的这类信息，就可通过密码分析的方法得到序列类信息，就可通过密码分析的方法得到序列ak和和bk。为了克服上述缺点，为了克服上述缺点，Pless提出了由多个提出了由多个J-K触发器序列驱动的多路复合序列方案，称为触发器序列驱动的多路复

51、合序列方案，称为Pless生成器。生成器。11,0,1kkkkkaccbc密码学基础密码学基础-UESTCPless生成器由生成器由8个个LFSR、4个个J-K触发器和触发器和1个循环个循环计数器构成，由循环计数器进行选通控制，如图计数器构成，由循环计数器进行选通控制，如图2.16所示。假定在时刻所示。假定在时刻t输出第输出第t(mod 4)个单元，则个单元，则输出序列为输出序列为a0b1c2d3a4b5d62.6.3 Pless生成器生成器密码学基础密码学基础-UESTC图图2.16 2.16 PlessPless生成器生成器密码学基础密码学基础-UESTC钟控序列最基本的模型是用一个钟控序

52、列最基本的模型是用一个LFSR控制另外一控制另外一个个LFSR的移位时钟脉冲，如图的移位时钟脉冲，如图2.17所示。所示。2.6.4 钟控序列生成器钟控序列生成器密码学基础密码学基础-UESTC图图2.17 2.17 最简单的钟控序列生成器最简单的钟控序列生成器密码学基础密码学基础-UESTC假设假设LFSR1和和LFSR2分别输出序列分别输出序列ak和和bk，其其周期分别为周期分别为p1和和p2。假设钟控序列假设钟控序列ck的周期为的周期为p，可得如下关系：可得如下关系：1212gcd,p ppwp1110piiwa密码学基础密码学基础-UESTCf1(x): ak 的极小特征多项式的极小特

53、征多项式, GF(2)上上m次本原次本原f2(x): bk的极小特征多项式的极小特征多项式, GF(2)上上n次本原次本原且且m|n。因此，因此，p1=2m-1,p2=2n-1。又又w1=2m-1， gcd(w1,p2)=1，所以所以p=p1p2=(2m-1)(2n-1)。此外此外 ck的线性复杂度的线性复杂度=n(2m-1)极小特征多项式极小特征多项式: 212mfx密码学基础密码学基础-UESTC例例 设设LFSR1为为3级级m序列生成器，其特征多项式为序列生成器，其特征多项式为f1(x)=1+x+x3。设初态为设初态为a0=a1=a2=1，于是输出序于是输出序列为列为ak=1,1,1,0,1,0,0,。又设又设LFSR2为为3级级m序列生成器，且记其状态向量序列生成器，且记其状态向量为为k，则在图则在