次课流密码最新课件

1、2021-11-22次课流密码PPT课件 (2)1第三章第三章 流密码流密码一、流密码的基本概念一、流密码的基本概念二、二、线性反馈移位寄存器序列线性反馈移位寄存器序列三、线性移位寄存器的一元多项式表示三、线性移位寄存器的一元多项式表示四、四、m序列的伪随机性序列的伪随机性五、五、m序列密码的破译序列密码的破译2021-11-22次课流密码PPT课件 (2)2一、流密码的基本概念一、流密码的基本概念2021-11-22次课流密码PPT课件 (2)3 流密码的基本概念流密码的基本概念n流密码是将明文划分成字符流密码是将明文划分成字符( (如单个字母如单个字母) )，或其编码，或其编码的基本单元的

2、基本单元( (如如0, 10, 1数字数字) )，字符分别与密钥流作用进，字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现。行加密，解密时以同步产生的同样的密钥流实现。n流密码强度流密码强度完全依赖于密钥序列的随机性完全依赖于密钥序列的随机性( (Randomness)Randomness)和不可预测性和不可预测性( (Unpredictability)Unpredictability)。n核心问题核心问题是密钥流生成器的设计是密钥流生成器的设计。n保持收发两端密钥流的保持收发两端密钥流的精确精确同步同步是实现可靠解密的关是实现可靠解密的关键技术键技术。iiikmciiikcm

3、加密加密解密解密2021-11-22次课流密码PPT课件 (2)4流密码的框图流密码的框图kI 安 全 信 道 kI KG KG ki ki mi ci ci mi Eki(mi) Eki(mi)2021-11-22次课流密码PPT课件 (2)5 流密码的框图流密码的框图n消息流：消息流：m=m1m2mi，其中，其中mi M。n密文流：密文流： c=c1c2ci=Ek1(m1)Ek2(m2) Eki(mi)，ci C。n密钥流：密钥流：ki，i 0。 一个完全随机的非周期序列，可以实现一次一密体制。但一个完全随机的非周期序列，可以实现一次一密体制。但需要需要无限存储单元无限存储单元和和复杂的输

4、出逻辑函数复杂的输出逻辑函数f f。 i i是第是第i i时刻时刻密钥流生成器的内部状态，以存储单元的存数矢量描述。密钥流生成器的内部状态，以存储单元的存数矢量描述。),(iikfk2021-11-22次课流密码PPT课件 (2)6 流密码的分类流密码的分类(1)n同步流密码同步流密码SSC(Synchronous Stream Cipher)： i与明文消息无关，密钥流将独立于明文。与明文消息无关，密钥流将独立于明文。n特点：特点：n对于明文而言，这类加密变换是无记忆的。但它是时变对于明文而言，这类加密变换是无记忆的。但它是时变的。的。n只有保持两端精确同步才能正常工作。只有保持两端精确同步

5、才能正常工作。n对主动攻击时异常敏感而有利于检测对主动攻击时异常敏感而有利于检测n无差错传播无差错传播( (Error Propagation)Error Propagation) 2021-11-22次课流密码PPT课件 (2)7流密码的分类流密码的分类(2)n自同步流密码自同步流密码SSSC(Self-Synchronous Stream Cipher) i i依赖于依赖于( (k kI I, , i-1i-1, ,m mi i) )，使密文使密文c ci i不仅与当前输入不仅与当前输入m mi i有关，而且由于有关，而且由于k ki i对对 i i的关系而与以前的输入的关系而与以前的输入

6、m m1 1, , m m2 2 , ,m mi-1i-1有关。一般在有限的有关。一般在有限的n n级存储下将与级存储下将与m mi-i-1 1,m mi-ni-n有关。有关。n优点：优点：具有自同步能力，强化了其抗统计分析的能力具有自同步能力，强化了其抗统计分析的能力n缺点：缺点：有有n n位位长的差错传播长的差错传播。密钥流与明文流不相互独立！密钥流与明文流不相互独立！2021-11-22次课流密码PPT课件 (2)8同步流密码n密钥流产生器密钥流产生器n加密变换器加密变换器n主要问题：设计一个滚动的密钥产生器，主要问题：设计一个滚动的密钥产生器，使使k经其扩展成一个密钥流具有以下性质：经

7、其扩展成一个密钥流具有以下性质：极大的周期、良好的统计特性、抗线性极大的周期、良好的统计特性、抗线性分析、抗统计分析分析、抗统计分析。有限状态自动机有限状态自动机FA2021-11-22次课流密码PPT课件 (2)9有限状态自动机有限状态自动机FA(Finite state Automation)n具有离散输入和输出（输入集和输出集均有具有离散输入和输出（输入集和输出集均有限）的一种数学模型限）的一种数学模型n有限状态集有限状态集S=si|i=1,2,ln有限输入字符集有限输入字符集X= Xi|i=1,2,mn有限输出字符集有限输出字符集Y= Yk|k=1,2,nn转移函数转移函数nYjf 1

8、(sj ,Xj)nSj+1 f 2(sj ,Xj)第第j时刻输入时刻输入Xj X ，输出输出YjY第第j时刻输入时刻输入Xj X ，状态变为状态变为Sj+1S2021-11-22次课流密码PPT课件 (2)10例nS=s1,s2,s3,X=x1, x2,x3,Y=(y1,y2,y3)n转移函数转移函数f1x1x2X3s1s2s3y1y2y3y3y1y2y2y3y1f2x1x2X3s1s2s3s2s3s1s1s2s3s3s1s22021-11-22次课流密码PPT课件 (2)11FA的状态图表示 若输入为若输入为x1x2x1x3x3x1初始状态初始状态s1状态序列：状态序列：s1s2s2s3s2

9、s1s2输出序列：输出序列： y1 y1 y2 y1 y3 y12021-11-22次课流密码PPT课件 (2)12作为作为FAFA的密钥流产生器的密钥流产生器n同步流密码的密钥流产生器可看为一同步流密码的密钥流产生器可看为一个参数为个参数为k的的FAFAn输出集输出集Z Z，状态集，状态集，状态转移函数，状态转移函数和输出函数和输出函数，初态，初态 0 0n设计的关键是设计的关键是和和ikkkzi),(0Z采用非线性函数采用非线性函数2021-11-22次课流密码PPT课件 (2)13作为作为FAFA的密钥流产生器的密钥流产生器n具有非线性的具有非线性的的的FA理论很不完善，通理论很不完善，

10、通常采用线性状态转移函数常采用线性状态转移函数以及非线性的以及非线性的输出函数输出函数n可将此类产生器分为驱动部分和非线性可将此类产生器分为驱动部分和非线性组合部分。组合部分。n驱动部分控制状态转移驱动部分控制状态转移n非线性组合部分提供统计特性良好的序列非线性组合部分提供统计特性良好的序列),(0ZLFSR2021-11-22次课流密码PPT课件 (2)14两种常见的密钥流产生器LFSR非线性组合函数ziLFSRLFSRLFSR非线性组合函数zi2021-11-22次课流密码PPT课件 (2)15第三章第三章 流密码流密码一、流密码的基本概念一、流密码的基本概念二、二、线性反馈移位寄存器序列

11、线性反馈移位寄存器序列三、线性移位寄存器的一元多项式表示三、线性移位寄存器的一元多项式表示四、四、m序列的伪随机性序列的伪随机性五、五、m序列密码的破译序列密码的破译2021-11-22次课流密码PPT课件 (2)16线性反馈移位寄存器序列概念线性反馈移位寄存器序列概念移位寄存器是流密码产生密钥流的一个主要组成部分。移位寄存器是流密码产生密钥流的一个主要组成部分。GF(2)上一个上一个n级反馈移位寄存器由级反馈移位寄存器由n个二元存储器与个二元存储器与一个反馈函数一个反馈函数f(a1,a2,an)组成，如图所示。组成，如图所示。每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈

12、移位寄每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于存器的状态，每一状态对应于GF(2)上的一个上的一个n维向量，共有维向量，共有2n种可能的状态。每种可能的状态。每一时刻的状态可用一时刻的状态可用n长序列表示长序列表示: a1,a2,an2021-11-22次课流密码PPT课件 (2)17132第7时刻 0 0 1第0时刻 0 0 1第1时刻 1 0 0第2时刻 1 1 0第3时刻 1 1 1第4时刻 0 1 1第5时刻 1 0 1第6时刻 0 1 0产生序列为：1001110例：例：3级级LFSR2021-11-22次课流密码PPT课件

13、(2)18例：例： 3级反馈移位寄存器，其初始状态为级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由表求出输出可由表求出状态状态（a1,a2,a3)输出输出1 0 11 1 01 1 10 1 11 0 11 1 0 101110非线性反馈移位寄存器非线性反馈移位寄存器2021-11-22次课流密码PPT课件 (2)19 如果移位寄存器的反馈函数如果移位寄存器的反馈函数f(a1,a2,an)是是a1，a2，an的线性函数，则称之为线性反馈移位寄存器的线性函数，则称之为线性反馈移位寄存器LFSR（linear feedback shift register）。）。此时

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

15、1-22次课流密码PPT课件 (2)21例，下图是一个例，下图是一个5级线性反馈移位寄存器，其初始状态为级线性反馈移位寄存器，其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出输出序列为：可求出输出序列为：14aaf1110输出序列为输出序列为反馈函数：反馈函数：周期：周期：312021-11-22次课流密码PPT课件 (2)22 在线性反馈移位寄存器中总是假定在线性反馈移位寄存器中总是假定c1,c2,cn中至中至少有一个不为少有一个不为0，否则，否则f(a1,a2,an)0，这样的话，这样的话，在在n个脉冲后状态必然是个脉冲后状态必然是000，且这个状态必将一直，且

16、这个状态必将一直持续下去。持续下去。 若只有一个系数不为若只有一个系数不为0，设仅有，设仅有cj不为不为0，实际上是，实际上是一种延迟装置。一般对于一种延迟装置。一般对于n级线性反馈移位寄存器，总级线性反馈移位寄存器，总是假定是假定cn=1。2021-11-22次课流密码PPT课件 (2)23n线性反馈移位寄存器输出序列的性质完全由其反馈函数线性反馈移位寄存器输出序列的性质完全由其反馈函数决定。决定。nn级线性反馈移位寄存器最多有级线性反馈移位寄存器最多有2n个不同的状态。个不同的状态。n若其初始状态为若其初始状态为0，则其状态恒为，则其状态恒为0。若其初始状态非。若其初始状态非0，则其后继状

17、态不会为则其后继状态不会为0。n因此因此n级线性反馈移位寄存器的状态周期小于等于级线性反馈移位寄存器的状态周期小于等于2n-1。n其输出序列的周期与状态周期相等，也小于等于其输出序列的周期与状态周期相等，也小于等于2n-1。n只要选择合适的反馈函数便可使序列的周期达到最大值只要选择合适的反馈函数便可使序列的周期达到最大值2n-1，周期达到最大值的序列称为周期达到最大值的序列称为m序列序列。nnnnacacacaaaf121121),(2021-11-22次课流密码PPT课件 (2)24第三章第三章 流密码流密码一、流密码的基本概念一、流密码的基本概念二、二、线性反馈移位寄存器序列线性反馈移位寄

18、存器序列三、线性移位寄存器的一元多项式表示三、线性移位寄存器的一元多项式表示四、四、m序列的伪随机性序列的伪随机性五、五、m序列密码的破译序列密码的破译2021-11-22次课流密码PPT课件 (2)25设设n级级LFSR的输出序列满足递推关系的输出序列满足递推关系an+k=c1an+k-1 c2an+k-2 cnak (*)对任何对任何k1成立。这种递推关系可用一个一元高次多项式成立。这种递推关系可用一个一元高次多项式 P(x)=1+c1x+cn+1xn-1cnxn表示，称这个多项式为表示，称这个多项式为LFSR的的特征多项式特征多项式。2.3 线性移位寄存器的一元多项式表示线性移位寄存器的

19、一元多项式表示2021-11-22次课流密码PPT课件 (2)26实例：（画出下列个移存器的逻辑框图，写出相应的线实例：（画出下列个移存器的逻辑框图，写出相应的线性递推式，并讨论由它们所产生的序列）性递推式，并讨论由它们所产生的序列）1、不可约多项式2、可约多项式3、本原多项式4、环式移存器1)(234xxxxxf) 1)(1(1)(334xxxxxxf1)(4xxxf1)(4 xxf2021-11-22次课流密码PPT课件 (2)27答案：答案：1 1、该移存器产生三类周期相同（全为、该移存器产生三类周期相同（全为5 5）的序列及一个全零序）的序列及一个全零序列。列。2 2、该移存器产生五类周期分别为、该移存器产生五类周期分别为6 6、3 3、3 3、2 2、1 1的序列及一个的序列及一个全零序列。全零序列。3 3、该移存器产生周期为、该移存器产生周期为1515的的m序列及一个全零序列。序列及一个全零序列。1、不可约多项式2、可约多项式3、本原多项式4、环式移存器1)(234xxxxxf) 1)(1(1)(334xxxxxxf1)(4xxxf1)(4 xxf2021-11-22次课流密码PPT课件 (2)28本