第2章01--流密码(LFSR)

1、1第第2 2章章 流密码流密码( (序列密码序列密码) )一、流密码的基本概念一、流密码的基本概念二、线性反馈移位寄存器序列二、线性反馈移位寄存器序列三三、线性移位寄存器的一元多项式表示、线性移位寄存器的一元多项式表示四四、m序列的伪随机性序列的伪随机性五、五、m序列密码的破译序列密码的破译2 流密码的基本概念流密码的基本概念n流密码是将明文划分成字符流密码是将明文划分成字符( (如单个字母如单个字母) )，或其编码，或其编码的基本单元的基本单元( (如如0, 10, 1数字数字) )，字符分别与密钥流作用进，字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现。行加密，解密时以同

2、步产生的同样的密钥流实现。n流密码强度流密码强度完全依赖于密钥序列的随机性完全依赖于密钥序列的随机性( (Randomness)Randomness)和不可预测性和不可预测性( (Unpredictability)Unpredictability)。n核心问题核心问题是密钥流生成器的设计是密钥流生成器的设计。n保持收发两端密钥流的保持收发两端密钥流的精确精确同步同步是实现可靠解密的关是实现可靠解密的关键技术键技术。iiikmciiikcm加密加密解密解密3流密码的框图流密码的框图kI 安 全 信 道 kI KG KG ki ki mi ci ci mi Eki(mi) Eki(mi)4 流密码

3、的框图流密码的框图n消息流：消息流：m=m1m2mi，其中，其中mi M。n密文流：密文流： c=c1c2ci=Ek1(m1)Ek2(m2) Eki(mi)，ci C。n密钥流：密钥流：ki，i 0。 一个完全随机的非周期序列，可以实现一次一密体制。但一个完全随机的非周期序列，可以实现一次一密体制。但需要需要无限存储单元无限存储单元和和复杂的输出逻辑函数复杂的输出逻辑函数f f。 i i是第是第i i时刻时刻密钥流生成器的内部状态，以存储单元的存数矢量描述。密钥流生成器的内部状态，以存储单元的存数矢量描述。),(iikfk5 流密码的分类流密码的分类(1)n同步流密码同步流密码SSC(Sync

4、hronous Stream Cipher)： i与明文消息无关，密钥流将独立于明文。与明文消息无关，密钥流将独立于明文。n特点：特点：n对于明文而言，这类加密变换是无记忆的。但它是时变对于明文而言，这类加密变换是无记忆的。但它是时变的。的。n只有保持两端精确同步才能正常工作。只有保持两端精确同步才能正常工作。n对主动攻击时异常敏感而有利于检测对主动攻击时异常敏感而有利于检测n无差错传播无差错传播( (Error Propagation)Error Propagation) 6流密码的分类流密码的分类(2)n自同步流密码自同步流密码SSSC(Self-Synchronous Stream Ci

5、pher) i i依赖于依赖于( (k kI I, , i-1i-1, ,m mi i) )，使密文使密文c ci i不仅与当前输不仅与当前输入入m mi i有关，而且由于有关，而且由于k ki i对对 i i的关系而与以前的输入的关系而与以前的输入m m1 1, , m m2 2 , , ,m mi-1i-1有关。一般在有限的有关。一般在有限的n n级存储下将级存储下将与与m mi-1i-1, , ,m mi-ni-n有关。有关。n优点：优点：具有自同步能力，强化了其抗统计分析的具有自同步能力，强化了其抗统计分析的能力能力n缺点：缺点：有有n n位位长的差错传播长的差错传播。密钥流与明文流不

6、相互独立！密钥流与明文流不相互独立！7同步流密码n密钥流产生器密钥流产生器n加密变换器加密变换器n主要问题：设计一个滚动的密钥产生器，主要问题：设计一个滚动的密钥产生器，使使k经其扩展成一个密钥流具有以下性质：经其扩展成一个密钥流具有以下性质：极大的周期、良好的统计特性、抗线性极大的周期、良好的统计特性、抗线性分析、抗统计分析分析、抗统计分析。有限状态自动机有限状态自动机FA8有限状态自动机有限状态自动机FA(Finite state Automation)n具有离散输入和输出（输入集和输出集均有具有离散输入和输出（输入集和输出集均有限）的一种数学模型限）的一种数学模型n有限状态集有限状态集S

7、=si|i=1,2,ln有限输入字符集有限输入字符集X= Xi|i=1,2,mn有限输出字符集有限输出字符集Y= Yk|k=1,2,nn转移函数转移函数nYjf 1(sj ,Xj)nSj+1 f 2(sj ,Xj)第第j时刻输入时刻输入Xj X ，输出输出YjY第第j时刻输入时刻输入Xj X ，状态变为状态变为Sj+1S9例nS=s1,s2,s3,X=x1, x2,x3,Y=(y1,y2,y3)n转移函数转移函数f1x1x2X3s1s2s3y1y2y3y3y1y2y2y3y1f2x1x2X3s1s2s3s2s3s1s1s2s3s3s1s210FA的状态图表示 若输入为若输入为x1x2x1x3x

8、3x1初始状态初始状态s1状态序列：状态序列：s1s2s2s3s2s1s2输出序列：输出序列： y1 y1 y2 y1 y3 y111作为作为FAFA的密钥流产生器的密钥流产生器n同步流密码的密钥流产生器可看为一同步流密码的密钥流产生器可看为一个参数为个参数为k的的FAFAn输出集输出集Z Z，状态集，状态集，状态转移函数，状态转移函数和输出函数和输出函数，初态，初态 0 0n设计的关键是设计的关键是和和ikkkzi),(0Z采用非线性函数采用非线性函数12作为作为FAFA的密钥流产生器的密钥流产生器n具有非线性的具有非线性的的的FA理论很不完善，通理论很不完善，通常采用线性状态转移函数常采用

9、线性状态转移函数以及非线性的以及非线性的输出函数输出函数n可将此类产生器分为驱动部分和非线性可将此类产生器分为驱动部分和非线性组合部分。组合部分。n驱动部分控制状态转移驱动部分控制状态转移n非线性组合部分提供统计特性良好的序列非线性组合部分提供统计特性良好的序列),(0ZLFSR13两种常见的密钥流产生器LFSR非线性组合函数ziLFSRLFSRLFSR非线性组合函数zi14第四章第四章 流密码流密码一、流密码的基本概念一、流密码的基本概念二、二、线性反馈移位寄存器序列线性反馈移位寄存器序列三三、线性移位寄存器的一元多项式表示、线性移位寄存器的一元多项式表示四四、m序列的伪随机性序列的伪随机性

10、五、五、m序列密码的破译序列密码的破译15线性反馈移位寄存器序列概念线性反馈移位寄存器序列概念移位寄存器是流密码产生密钥流的一个主要组成部分。移位寄存器是流密码产生密钥流的一个主要组成部分。GF(2)上一个上一个n级反馈移位寄存器由级反馈移位寄存器由n个二元存储器与个二元存储器与一个反馈函数一个反馈函数f(a1,a2,an)组成，如图所示。组成，如图所示。每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于移位寄存器的状态，每一状态对应于GF(2)上的一个上的一个n维向量，共有维向量

11、，共有2n种可种可能的状态。每一时刻的状态可用能的状态。每一时刻的状态可用n长序列表示长序列表示: a1,a2,an16例：例： 3级反馈移位寄存器，其初始状态为级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由表求出输出可由表求出状态状态（a1,a2,a3)输出输出1 0 11 1 01 1 10 1 11 0 11 1 0 101110非线性反馈移位寄存器非线性反馈移位寄存器17 如果移位寄存器的反馈函数如果移位寄存器的反馈函数f(a1,a2,an)是是a1，a2，an的线性函数，则称之为线性反馈移位寄存器的线性函数，则称之为线性反馈移位寄存器LFSR（linea

12、r feedback shift register）。）。此时此时f可写为可写为其中常数其中常数ci=0或或1，是模是模2加法。加法。ci=0或或1可用开关的断开和闭合来实现，如上图所示。可用开关的断开和闭合来实现，如上图所示。nnnnacacacaaaf121121),(18 输出序列输出序列at满足满足an+t=cnatcn-1at+1c1an+t-1其中其中t为非负正整数。为非负正整数。 线性反馈移位寄存器因其实现简单、速度快、有较为成线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。

13、之一。19例，下图是一个例，下图是一个5级线性反馈移位寄存器，其初始状态为级线性反馈移位寄存器，其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出输出序列为：可求出输出序列为：14aaf1001101001000010101110110001111100110输出序列为输出序列为反馈函数：反馈函数：周期：周期：3120 在线性反馈移位寄存器中总是假定在线性反馈移位寄存器中总是假定c1,c2,cn中至中至少有一个不为少有一个不为0，否则，否则f(a1,a2,an)0，这样的话，这样的话，在在n个脉冲后状态必然是个脉冲后状态必然是000，且这个状态必将一直，且这个状态必将

14、一直持续下去。持续下去。 若只有一个系数不为若只有一个系数不为0，设仅有，设仅有cj不为不为0，实际上是，实际上是一种延迟装置。一般对于一种延迟装置。一般对于n级线性反馈移位寄存器，总级线性反馈移位寄存器，总是假定是假定c0=1。21n线性反馈移位寄存器输出序列的性质完全由其反馈函数线性反馈移位寄存器输出序列的性质完全由其反馈函数决定。决定。nn级线性反馈移位寄存器最多有级线性反馈移位寄存器最多有2n个不同的状态。个不同的状态。n若其初始状态为若其初始状态为0，则其状态恒为，则其状态恒为0。若其初始状态非。若其初始状态非0，则其后继状态不会为则其后继状态不会为0。n因此因此n级线性反馈移位寄存

15、器的状态周期小于等于级线性反馈移位寄存器的状态周期小于等于2n-1。n其输出序列的周期与状态周期相等，也小于等于其输出序列的周期与状态周期相等，也小于等于2n-1。n只要选择合适的反馈函数便可使序列的周期达到最大值只要选择合适的反馈函数便可使序列的周期达到最大值2n-1，周期达到最大值的序列称为周期达到最大值的序列称为m序列序列。nnnnacacacaaaf121121),(22第四章第四章 流密码流密码一、流密码的基本概念一、流密码的基本概念二、二、线性反馈移位寄存器序列线性反馈移位寄存器序列三三、线性移位寄存器的一元多项式表示、线性移位寄存器的一元多项式表示四四、m序列的伪随机性序列的伪随

16、机性五、五、m序列密码的破译序列密码的破译23设设n级级LFSR的输出序列满足递推关系的输出序列满足递推关系an+k=c1an+k-1 c2an+k-2 cnak (*)对任何对任何k1成立。这种递推关系可用一个一元高次多项式成立。这种递推关系可用一个一元高次多项式 P(x)=1+c1x+cn-1xn-1cnxn表示，称这个多项式为表示，称这个多项式为LFSR的的特征多项式特征多项式。4.3 线性移位寄存器的一元多项式表示线性移位寄存器的一元多项式表示24实例：（画出下列个移存器的逻辑框图，写出相应的线实例：（画出下列个移存器的逻辑框图，写出相应的线性递推式，并讨论由它们所产生的序列）性递推式

17、，并讨论由它们所产生的序列）1、不可约多项式2、可约多项式3、本原多项式4、环式移存器1)(234xxxxxf) 1)(1(1)(334xxxxxxf1)(4xxxf1)(4 xxf25答案：答案：1 1、该移存器产生三类周期相同（全为、该移存器产生三类周期相同（全为5 5）的序列及一个全）的序列及一个全零序列。零序列。2 2、该移存器产生五类周期分别为、该移存器产生五类周期分别为6 6、3 3、3 3、2 2、1 1的序列及的序列及一个全零序列。一个全零序列。3 3、该移存器产生周期为、该移存器产生周期为1515的的m序列及一个全零序列。序列及一个全零序列。1、不可约多项式2、可约多项式3、

18、本原多项式4、环式移存器1)(234xxxxxf) 1)(1(1)(334xxxxxxf1)(4xxxf1)(4 xxf26本原多项式本原多项式n设设p(x)是是GF(2)上的多项式，使上的多项式，使p(x)|(xp-1)的最小的最小p称为称为p(x)的周期或者阶的周期或者阶。n仅能被非仅能被非0常数或自身的常数倍除尽，但不能被其他常数或自身的常数倍除尽，但不能被其他多项式除尽的多项式称为多项式除尽的多项式称为不可约多项式不可约多项式。n若若n次不可约多项式次不可约多项式p(x)的阶为的阶为2n-1，则称，则称p(x)是是n次本原多项式次本原多项式。以本原多项式为连接多项式产生的非零序列均是以本原多项式为连接多项式产生的非零序列均是m序列。序列。271)(4xxxf例：本原多项式例：本原多项式因为，因为，f(x)|(x15-1)，但不存在比，但不存在比15小的常数小的常数m，使，