流密码详解学习资料

第2章流密码(mìmǎ)李向东中原(zhōngyuán)工学院计算机学院124197985@2011.9-2012.11第一页，共76页。第2章流密码(mìmǎ)2.1流密码(mìmǎ)一般模型2.2线性反馈移位寄存器序列2.3线性复杂度及B-M算法2.4非线性序列生成器2.5流密码(mìmǎ)算法2第二页，共76页。2.1流密码一般(yībān)模型实用密码体制(tǐzhì)的分类3第三页，共76页。2.1流密码(mìmǎ)一般模型流密码(mìmǎ)(streamcipher)(序列密码(mìmǎ))体制模型明文序列:m=m1m2m3…;密钥序列:z=z1z2z3…;密文(mìwén)序列:c=c1c2c3…;加密变换:ci=E(zi,mi)(i=1,2,3,…);解密变换:mi=D(zi,ci)(i=1,2,3,…).4第四页，共76页。课堂(kètáng)讨论：加密函数(hánshù)和解密函数(hánshù)都用异或运算，行不行？什么样的加解密算法是高效、安全的？Why？实用的流密码方案中，加解密算法是什么？5第五页，共76页。流密码(mìmǎ)原理框图信道ciD(zi,ci)cimiE(zi,mi)mi密钥流生成器zizi密钥流生成器kk安全信道2.1流密码(mìmǎ)一般模型6第六页，共76页。流密码体制的安全性当流钥序列(xùliè)是具有均匀分布的离散无记忆随机序列(xùliè)时,在理论上是不可破译的.实用的困难性真正的具有均匀分布的随机序列(xùliè)是不可能重复产生的.密钥序列(xùliè)长(至少与明文序列(xùliè)一样长),其管理(存储、分配)难.设计流密码体制的关键问题设计产生密钥序列(xùliè)的方法.2.1流密码一般(yībān)模型7第七页，共76页。序列密码(mìmǎ)的分类同步流密码(mìmǎ)(SSC:synchronousstreamcipher)产生密钥序列的算法与明文、密文无关.自同步流密码(mìmǎ)(SSSC:self-synchronousstreamcipher)产生密钥序列的算法与以前的密文有关.2.1流密码一般(yībān)模型8第八页，共76页。同步流密码(SSC:synchronousstreamcipher)只要通信双方的密钥序列产生器具有相同的“种子序列”和相同的“初始状态”,就能产生相同的密钥序列.通信双方必须保持精确同步,才能正确解密.容易检测插入、删除、重播等主动攻击.没有差错传播.讨论：如何对SSC的这种“同步”性质进行(jìnxíng)形式化描述？2.1流密码一般(yībān)模型9第九页，共76页。同步(tóngbù)流密码(SSC:synchronousstreamcipher)产生密钥序列的算法与明文、密文无关.ciE(zi,mi)mizi密钥流生成器k2.1流密码一般(yībān)模型10第十页，共76页。自同步流密码(SSSC:self-synchronousstreamcipher)产生密钥序列的算法(suànfǎ)与以前的密文有关.E(zi,mi)mizi密钥流生成器kci2.1流密码(mìmǎ)一般模型11第十一页，共76页。自同步流密码(SSSC)密钥流生成器是一种有记忆变换器密钥流与明文符号有关：i时刻的密文不仅取决于i时刻的明文，而且与i时刻之前的l个明文符号有关具有有限的差错传播具有自同步能力把明文每个字符扩散(kuòsàn)在密文多个字符中,强化了抗统计分析的能力问：SSSC是如何自同步的？请email回应。2.1流密码(mìmǎ)一般模型12第十二页，共76页。二元加法(jiāfǎ)序列密码明文序列:m=m1m2m3…;密钥序列:z=z1z2z3…;密文(mìwén)序列:c=c1c2c3…;加密变换:ci=zimi(i=1,2,3,…);解密变换:mi=zici(i=1,2,3,…).2.1流密码一般(yībān)模型13第十三页，共76页。第2章流密码(mìmǎ)2.1流密码一般模型2.2线性反馈移位(yíwèi)寄存器序列2.3线性复杂度及B-M算法2.4非线性序列生成器2.5流密码算法14第十四页，共76页。2.2线性反馈移位(yíwèi)寄存器序列伪随机(suíjī)序列考虑二元序列:a={ai}=a0a1a2a3….周期序列定义2.1设a=(a0,a1,…,ai,…)是一个二元序列(xùliè)，若存在正整数N和非负整数m，使得ai+N=ai对于任意im成立，则称二元序列(xùliè)a是终归周期序列(xùliè)。如果m=0，则称序列(xùliè)a是严格周期序列(xùliè)，简称周期序列(xùliè)。而满足ai+N＝ai(im)的最小正整数N被称为序列(xùliè)a的周期。15第十五页，共76页。2.2线性反馈移位(yíwèi)寄存器序列定义2.2设a=(a0,a1,…,ai,…)是一个(yīɡè)周期为N的二元序列，在一个(yīɡè)周期内连续出现的最多的符号“0”（或1）的串，称为0（或1）的一个(yīɡè)游程。在一个(yīɡè)游程中，0（或1）的个数称为该游程的长度。（讨论：该定义有否歧义？）伪随机序列(xùliè)序列(xùliè)的游程例:在序列k={ki}=001110100000111100中,有长为1的0游程一个;长为4的0游程一个;长为5的0游程一个;长为1的1游程一个;长为3的1游程一个;长为4的1游程一个.16第十六页，共76页。2.2线性反馈(fǎnkuì)移位寄存器序列定义(dìngyì)2.3设a=(a0,a1,…,aN1)和b=(b0,b1,…,bN1)是两个周期为N的二元周期序列，其相关函数定义(dìngyì)为特别地，如果a=b，则Ra,a()被称为自相关函数，其中当=0，Ra,a(0)被称为同相自相关函数，而当0，Ra,a()被称为异相自相关函数。伪随机(suíjī)序列序列的相关函数17第十七页，共76页。2.2线性反馈(fǎnkuì)移位寄存器序列例2.1已知序列a=01011100101110…，则a是周期为7的周期序列;a一共(yīgòng)有4个游程：00,1,0,111，长度分别为2,1,1,3；求a的自相关函数:a=0101110,a=1011100…,Ra,a(0)=(-1)0+0+(-1)1+1+(-1)0+0+(-1)1+1+(-1)1+1+(-1)1+1+(-1)0+0=7,a=0101110,Ta=1011100…,Ra,a(1)=(-1)0+1+(-1)1+0+(-1)0+1+(-1)1+1+(-1)1+1+(-1)1+0+(-1)0+0=-1,a=0101110,T2a=0111001…,Ra,a(2)=(-1)0+0+(-1)1+1+(-1)0+1+(-1)1+1+(-1)1+0+(-1)1+0+(-1)0+1=-1,Ra,a(3)=Ra,a(4)=Ra,a(5)=Ra,a(6)=-1.18第十八页，共76页。伪随机(suíjī)序列哥伦布(Golomb,1955)随性假设(jiǎshè)(G1)：在一个周期内，0与1出现的个数至多相差(xiānɡchà)1。也即，如果N为偶数，则在一个周期内0与1的数目各占N/2；如果N为奇数，则在一个周期内0的数目为(N+1)/2或者(N-1)/2，相应地1的数目为(N-1)/2或者(N+1)/2。(G2)：在一个周期内，长度为i的游程个数占游程总数的1/2i，i=1,2,…。且在长度为i的游程中，0的游程与1的游程数目相等或至多相差(xiānɡchà)一个。(G3)：序列的异相自相关函数是一个常数。满足上述三个条件的序列称为拟噪声序列,或伪噪声序列(pseudonoisesequence),简记为:PN序列.PN序列在CDMA,通信同步,导航,雷达测距等领域有重要应用.19第十九页，共76页。SolomonW.Golomb:Shimonoseki,Japan,October10-14,200520第二十页，共76页。伪随机(suíjī)序列密钥序列k={ki}=k0k1k2k3….满足的条件(tiáojiàn)G1,G2,G3和以下三个条件(tiáojiàn)：(C1)周期p要长.如p>1050.(C2)生成容易.(C3)具有不可预测性(unpredictability):当密钥序列k的任何部分泄露时,要分析整个(zhěnggè)密钥序列,在计算上是不可行的.C3决定了密码的强度,是序列密码理论的核心.主要研究问题:线性复杂度,相关免疫性,不可预测性等.21第二十一页，共76页。an1…a1a0f(x0,x1,…,xn1)反馈移位寄存器(FSR:FeedbackShiftRegister)n个寄存器:从右至左依次(yīcì)称为第1,2,…,n级反馈函数f(x0,x1,…,xn-1):GF(2)nGF(2).工作原理:当一个时钟脉冲来到时,第i级寄存器的内容传送给第i-1级寄存器(i=2,3,…,n),第1级寄存器的内容为反馈移位寄存器的输出.反馈函数f(x0,x1,…,xn-1)的值传送给第n级寄存器.FSR的输出序列:a0,a1,a2,…,an,…称为反馈移位寄存器序列(FSR序列).伪随机(suíjī)序列22第二十二页，共76页。在任意时刻t,第1至n级寄存器的内容st=(at,at+1,…,at+n-1)GF(2)n称为(chēnɡwéi)FSR在时刻t的状态(state).s0=(a0,a1,…,an-1)称为(chēnɡwéi)FSR的初始状态.在时刻t+1的状态为:st+1=(at+1,at+2,…,at+n),at+n=f(at,at+1,…,at+n-1).共有2n个状态.反馈函数f(x1,x2,…,xn)是n个变量的布尔函数(Booleanfunction).反馈(fǎnkuì)移位寄存器(FSR)23第二十三页，共76页。例2.2设有限域GF(2)上的3级FSR的反馈函数(hánshù)为:f(x1,x2,x3)=x1x2x3初始状态为s0=(1,0,1).求FSR序列.解:反馈移位寄存器序列:a=1011…;周期q=4.反馈(fǎnkuì)移位寄存器(FSR)时刻状态输出3级2级1级01011111002111130111410115110024第二十四页，共76页。如果(rúguǒ)反馈函数f(x1,x2,…,xn)是n个变量的线性函数:f(x1,x2,…,xn)=c1xn+c2xn-1+…+cnx1(ci{0,1})则称为线性反馈移位寄存器(LFSR:linearfeedbackshiftregister).输出的序列称为线性反馈移位寄存器序列,记为LFSR序列。LFSR序列a=(a0,a1,…,an-1,…)满足递推关系式:线性反馈(fǎnkuì)移位寄存器(LFSR)an1…a1a0cncn-1c125第二十五页，共76页。反馈(fǎnkuì)函数:f(x1,x2,…,xn)=c1xn+c2xn-1+…+cnx1(ci{0,1})如果cn=0，则称LFSR是退化的；否则称LFSR是非退化的。把多项式：f(x)=1+c1x+c2x2+…+cnxn称为LFSR的特征多项式(characteristicpolynomial),或级连多项式、或生成多项式。线性反馈(fǎnkuì)移位寄存器(LFSR)26第二十六页，共76页。例2.3已知如图所示的3级LFSR.特征(tèzhēng)多项式为：f(x)=1+x2+x3LFSR序列a=(a0,a1,…,an-1,…)满足递推关系式:an=an-2+an-3.如果设初始状态为:(0,0,1)即a0=0,a1=0,a2=1，输出序列为:0010111周期为7.线性反馈(fǎnkuì)移位寄存器(LFSR)an1an2an3时刻状态输出3级2级1级0100010100210113110041111501116001127第二十七页，共76页。例2.3已知如图所示的3级LFSR.LFSR序列a=0010111的状态(zhuàngtài)转移图线性反馈(fǎnkuì)移位寄存器(LFSR)时刻状态输出3级2级1级0100010100210113110041111501116001100101010101111110011028第二十八页，共76页。线性反馈(fǎnkuì)移位寄存器(LFSR)LFSR序列(xùliè)的性质定理2.1任何n级FSR序列都是终归(zhōngguī)周期序列，且其周期至多是2n1。

定义2.4周期为2n

1的n级线性LFSR序列称为最大长度(Maximallength)序列，简称为m-序列。m-序列

定理2.2

a是周期为2n

1的m-序列的充分必要条件是其特征多项式f(x)为n阶本原多项式。29第二十九页，共76页。m-序列(xùliè)m-序列(xùliè)的个数定理2.3设f(x)是GF(2)上的n次本原多项式,则对任意(rènyì)非0的初始状态,由f(x)生成的m-序列是循环等价(cyclicallyequivalent)的.即:一个n次本原多项式只能生成一个m-序列.

定理2.4二元域GF(2)上的n级m序列共有(2n-1)/n个.30第三十页，共76页。m-序列(xùliè)例2.33级LFSR的特征(tèzhēng)多项式为:f(x)=1+x2+x3001010101011111100110初始状态为:(1,0,1),输出(shūchū)序列为:a=1011100.001010101011111100110初始状态为:(0,0,1),输出序列为:a=001011131第三十一页，共76页。m-序列(xùliè)m-序列(xùliè)的伪随机性定理2.5设a是一个n级m序列，周期为2n1，则(1)在一个周期内，0、1出现的次数分别为2n-11和2n-1。(2)在一个周期内，总游程数为2n-1。其中，对1in2，长为i的0游程、1游程各有2n-i-2个；长为n1的0游程1个，长为n的1游程1个。(3)a的自相关函数为:

32第三十二页，共76页。m-序列(xùliè)m-序列(xùliè)的伪随机性例2.4已知4级m序列a=100010011010111,有n=47个0,8个1游程(yóuchénɡ)总数为8长为1的0游程(yóuchénɡ)2个,长为1的1游程(yóuchénɡ)2个长为2的0游程(yóuchénɡ)1个,长为2的1游程(yóuchénɡ)1个长为3的0游程(yóuchénɡ)1个长为4的1游程(yóuchénɡ)1个.33第三十三页，共76页。m-序列(xùliè)m-序列的密码学性质(C1)周期长:p=2n-1.如n=166时,p=1050(9.3536104651049).(C2)生成容易:只要已知n次本原(běnyuán)多项式,容易生成m序列.(C3)m序列极不安全:只要泄露2n位连续数字,就可以完全确定反馈多项式的系数,从而得到m序列.已知ai,ai+1,…,ai+2n-1,由以下方程组可唯一解得c0,c1,…,cn-1.34第三十四页，共76页。第2章流密码(mìmǎ)2.1流密码一般模型2.2线性反馈移位寄存器序列(xùliè)2.3线性复杂度及B-M算法2.4非线性序列(xùliè)生成器2.5流密码算法35第三十五页，共76页。2.3序列(xùliè)的线性复杂度给定一个长度为N的二元密钥流序列a,假定捕获了a的一个长度为m的部分,不失一般性设为(a0,a1,…,am1),能否(nénɡfǒu)找到一个级数最短的LFSR,生成整个密钥流序列a?序列(xùliè)的密码分析问题问题一:是否存在LFSR生成整个序列a？问题二:捕获序列a多长的部分，才能找到LFSR生成整个序列a？怎样确保得到的LFSR最短？36第三十六页，共76页。2.3序列(xùliè)的线性复杂度序列的LFSR设a=(a0,a1,…,aN1)是一个长度为N的序列，那么存在(cúnzài)N级LFSR，生成整个序列a。当a是LFSR序列(xùliè)时，存在着更短的LFSR生成整个序列(xùliè)当a是非LFSR序列(xùliè)时，也可能存在着更短的LFSR生成整个序列(xùliè)a。aN1…a1a037第三十七页，共76页。2.3序列(xùliè)的线性复杂度B-M算法设a(N)=(a0,a1,…,aN1)是一个长度为N的序列,fN(x)是一个能生成a(N)且级数最小的LFSR的特征多项式,lN是LFSR的级数,则把<fN(x),lN>称为a(N)的线性综合(zōnghé)解.BerleKamp-Massey(1969)提出了求解<fN(x),lN>的迭代算法.38第三十八页，共76页。B-M算法(suànfǎ)39第三十九页，共76页。B-M算法(suànfǎ)例2.5设a(10)=(0001101111),N=10,求其线性综合(zōnghé)解.解:40第四十页，共76页。B-M算法(suànfǎ)例2.5设a(10)=(0001101111),N=10,求其线性综合(zōnghé)解.解:41第四十一页，共76页。B-M算法(suànfǎ)例2.5设a(10)=(0001101111),N=10,求其线性综合(zōnghé)解.解:42第四十二页，共76页。B-M算法(suànfǎ)例2.5设a(10)=(0001101111),N=10,求其线性综合(zōnghé)解.解:a(10)的线性综合解为:f10(x)=1+x+x2+x5,l10=5.若取初值:a(0)=00011,则f10(x)的LFSR序列(xùliè)a=00011011110011101000…,周期为：25-1=31.43第四十三页，共76页。B-M算法(suànfǎ)B-M算法(suànfǎ)的性质B-M算法(suànfǎ)的时间复杂度为O(N2).定理2.6给定(ɡěidìnɡ)长为N的序列a(N)=(a0,a1,…,aN1)，如果用B-M算法得到的线性综合解为(fN(x),lN)，则以fN(x)为生成多项式，产生的长为lN的LFSR就是生成序列a(N)的最短LFSR。定理2.7给定长为N的序列a(N)=(a0,a1,…,aN1)，用B-M算法得到的线性综合解为(fN(x),lN)是唯一解的充要条件是2lNN。44第四十四页，共76页。B-M算法(suànfǎ)B-M算法(suànfǎ)的性质

定理2.8

设a(N)={a0,a1,..,aN-1}是一个长为N的序列,lN是能产生a(N)并且阶数最小的LFSR的阶数.则当2lN

>N时,a(N)线性综合解的个数为：45第四十五页，共76页。2.3序列(xùliè)的线性复杂度序列(xùliè)的线性复杂度给定序列a，生成它的最短LFSR的长度lN就确定了。如果2lNN，只需要捕获序列a连续的2lN个比特，就能得到它的唯一解(fN(x),lN)，以fN(x)为特征多项式的lN级LFSR就可以生成整个(zhěnggè)序列a。特别地，对于周期N很大，但lN很小的序列a，比如周期为2n1的n级m-序列，利用B-M算法，只要捕获序列a连续的2lN个比特，即序列很小一部分，就可以重构整个(zhěnggè)序列。因此，lN实际上度量了序列a的线性的不可预测性。46第四十六页，共76页。2.3序列(xùliè)的线性复杂度序列(xùliè)的线性复杂度定义2.5生成长为N的序列a=(a0,a1,…,aN1)的LFSR的最短长度(chángdù)lN被称为序列a的线性复杂度。n阶m序列的线性复杂度=n.47第四十七页，共76页。第2章流密码(mìmǎ)2.1流密码一般模型(móxíng)2.2线性反馈移位寄存器序列2.3线性复杂度及B-M算法2.4非线性序列生成器2.5流密码算法48第四十八页，共76页。2.4非线性序列(xùliè)生成器密钥流生成器的分解Ruppe将密钥流生成器分成两部分：驱动部分和非线性组合部分驱动部分：可由m-序列或其它长周期的LFSR序列组成，用于控制(kòngzhì)密钥流生成器的状态序列，并为非线性组合部分提供伪随机性质良好的序列非线性组合部分：利用驱动部分生成的状态序列生成满足要求的密码特性好的密钥流序列………┇驱动部分┇非线性组合部分┇………49第四十九页，共76页。2.4非线性序列(xùliè)生成器非线性准则非线性组合(zǔhé)部分可由布尔函数表示n元布尔函数f(x)的代数正规型：50第五十页，共76页。2.4.1非线性准则(zhǔnzé)代数(dàishù)次数当f(x)的代数次数为1时，f(x)称为线性布尔函数(hánshù)当f(x)的代数次数大于1时，f(x)称为非线性布尔函数(hánshù)对于非线性组合部分的布尔函数(hánshù)，应该具有尽可能大的代数次数

定义2.6

设f(x)是一个n元布尔函数，在f(x)的代数正规型中，一个乘积项中变量的个数称为该乘积项的次数。f(x)的代数正规型中，全体非零系数乘积项次数的最大值称为f(x)的代数次数。51第五十一页，共76页。2.4.1非线性准则(zhǔnzé)非线性度是密码系统为抵抗线性攻击而提出的指标对于非线性组合(zǔhé)部分的布尔函数，应该具有尽可能大的非线性度

定义2.7设L是Z2上所有线性函数的集合，即L={ux+v}|uZ2n,vZ2}。则布尔函数f(x)的非线性度定义为其中dH()是汉明距离.52第五十二页，共76页。2.4.1非线性准则(zhǔnzé)退化(tuìhuà)布尔函数自变量经过线性变换后，n元布尔函数(hánshù)f(x)就简化为k元布尔函数(hánshù)g(x)作为非线性组合部分的布尔函数(hánshù)应该避免退化性

定义2.8

设f(x)是一个n元布尔函数，如果存在Z2上一个kn（k<n）的矩阵D，使得

f(x)=g(Dx)=g(y),则称f(x)是退化的。53第五十三页，共76页。2.4.1非线性准则(zhǔnzé)布尔函数(hánshù)的相关免疫性相关免疫性是为防止攻击者对密码系统进行相关攻击而提出的指标希望作为(zuòwéi)非线性组合部分的布尔函数应该具有m阶相关免疫性，m尽可能地大

定义2.9设f(x1,x2,…,xn)是n个彼此独立、对称的二元随机变量的布尔函数，称f(x)是m阶相关免疫的当且仅当f=f(x1,x2,…,xn)与x1,x2,…,xn中的任意m个随机变量54第五十四页，共76页。2.4.1非线性准则(zhǔnzé)布尔函数(hánshù)的相关免疫性定义2.10设f(x1,x2,…,xn)是一个(yīɡè)n元布尔函数，f(x)的Walsh变换定义为55第五十五页，共76页。2.4.1非线性准则(zhǔnzé)布尔函数(hánshù)的相关免疫性雪崩(xuěbēng)准则

定理2.9设1≤m≤n,n元布尔函数f=f(x1,x2,…,xn)是m阶相关免疫的当且仅当对于任意满足1≤wH()≤m的=(1,2,…,n)Z2n，f(x)的Walsh谱都为0，即

Sf()=0.这里wH()是汉明重量.

定义2.11

设f(x)是一个n元布尔函数，如果对于任意满足:wH(e)=1的e=(e1,e2,…,en)Z2n，f(x)+f(x+e)是平衡函数，则称f(x)为满足严格雪崩准则.56第五十六页，共76页。2.4.1非线性准则(zhǔnzé)扩散(kuòsàn)准则定义2.12设f(x)是一个n元布尔函数，1≤m≤n2，如果对于任意满足(mǎnzú):1≤wH(e)≤m的e=(e1,e2,…,en)Z2n，f(x)+f(x+e)是平衡函数，则称f(x)为满足(mǎnzú)m次扩散准则.非线性序列设计准则代数次数非线性度退化性相关免疫性雪崩准则扩散准则

57第五十七页，共76页。2.4.2非线性序列(xùliè)生成器滤波生成器（Filtergeneator）滤波生成器又叫前馈生成器，由几个LFSR和滤波（前馈）函数g(x)两部分(bùfen)组成滤波函数要求具有很好的非线性性质，以增强生成器的抗攻击能力…LFSRg(x)58第五十八页，共76页。滤波(lǜbō)生成器Geffe生成器使用三个级数两两互素的LFSR，其中(qízhōng)LFSR1和LFSR3作为多路复合器的输入，LFSR2控制多路复合器的输出滤波函数LFSR1多路复合器选择控制LFSR3LFSR2设a1、a2和a3分别是LFSR、LFSR2和LFSR3的输出，则Geffe生成器的输出b为:59第五十九页，共76页。滤波(lǜbō)生成器Geffe生成器大的周期和线性复杂度设LFSR1、LFSR2和LFSR3周期分别为T1,T2和T3，级数分别为n1,n2和n3，则Geffe生成器的周期为T1T2T3，线性复杂度为(n1＋1)n2＋n1n3.不安全由于生成器的输出与LFSR2的输出有75％是相同的，通过观察输出序列可以获得LFSR的初态和输出序列，即所谓的相关攻击破译(pòyì)Geffe生成器。因此Geffe生成器是不安全的.60第六十页，共76页。滤波(lǜbō)生成器J-K触发器LFSR1输出序列(xùliè){ak},周期为m.LFSR2输出序列(xùliè){bk},周期为n.J-K触发器输出序列(xùliè){ck}令c-1=0,有

c0=a0,

c1=(a1+b1+1)a0+a1,

c2=(a2+b2+1)c1+a2,…JK

ck00011011ck-1

01{ak}{ck}{bk}LFSR1JKLFSR261第六十一页，共76页。J-K触发器如果gcd(m,n)=1，且a0+b0=0，则输出序列{ck}的周期为:(2m-1)(2n-1).J-K触发器输出序列{ck}随机性好不安全已知cn与cn+1,便能对an+1与bn+1的一个(yīɡè)作出判断.cn=cn+1=0an+1=0;cn=0,cn+1=1an+1=1;cn=1,cn+1=0bn+1=1;cn=cn+1=1bn+1=0.62第六十二页，共76页。J-K触发器例2.4.1令m=2,n=3,且a0+b0=0,LFSR1输出(shūchū)序列{at}=011…,LFSR2输出(shūchū)序列{bt}=1001011….有c0=a0=0,c1=(a1+b1+1)a0+a1=(1+0+1)0+1=1,c2=(a2+b2+1)c1+a2=(1+0+1)1+1=1,…{bk}=011010011101010010010….周期为:L=(2m-1)(2n-1)=(22-1)(23-1)=21.JK

ck00011011ck-1

01

63第六十三页，共76页。2.4.2非线性序列(xùliè)生成器钟控序列生成器钟控生成器（Clockcontrolledgenerator）是由一个或几个FSR输出序列，控制另一个FSR的时钟。走停生成器（Stop-and-Gogenerator）当LFSR1输出1时，时钟脉冲通过与门使LFSR2进行一次移位，从而生成下一位；当LFSR1输出0，时钟脉冲无法(wúfǎ)通过与门使LFSR2移位（走），从而LFSR2重复输出前一位（停）LFSR1LFSR264第六十四页，共76页。钟控序列(xùliè)生成器钟控序列的周期(zhōuqī)设LFSR1输出序列{ak},周期(zhōuqī)为2m-1，LFSR2输出序列{bk},周期(zhōuqī)为2n-1，则钟控序列{ck}的周期(zhōuqī)为：(2m-1)(2n-1).钟控序列{ck}的线性复杂度为：n(2m-1).65第六十五页，共76页。钟控序列(xùliè)生成器例2.6设LFSR1为一个3级m-序列，其特征多项式为：f1(x)=1+x+x3，取初始值为a0=a1=a2=1,则输出(shūchū)序列{ak}=1110100,周期为231=7.设LFSR2为一个3级m-序列，其特征多项式为：f1(x)=1+x2+x3，取初始值为b0=b1=b2=1,则输出(shūchū)序列{bk}=1110010,周期为23-1=7.钟控序列:{ck}=1110000010111111000111011111100110001111000010011…周期为：(2m1)(2n1)=(231)(231)=49.线性复杂度为：n(2m1)=3(231)=21.66第六十六页，共76页。第2章流密码(mìmǎ)2.1流密码一般模型2.2线性反馈移位(yíwèi)寄存器序列2.3线性复杂度及B-M算法2.4非线性序列生成器2.5流密码算法67第六十七页，共76页。2.5流密码(mìmǎ)算法RC4算法RC4是由Rivest于1987年开发的一种序列密码,它已被广