流密码的基本概念汇总

2020/1/11第三章流密码一、流密码的基本概念二、线性反馈移位寄存器序列三、非线性序列2020/1/12一、流密码的基本概念2020/1/13流密码的基本概念流密码是将明文划分成字符(如单个字母)，或其编码的基本单元(如0,1数字)，字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现。流密码强度完全依赖于密钥序列的随机性(Randomness)和不可预测性(Unpredictability)。核心问题是密钥流生成器的设计。保持收发两端密钥流的精确同步是实现可靠解密的关键技术。2020/1/14流密码的框图kI安全信道kI······KGKGkikimicicimiEki(mi)···Eki(mi)2020/1/15流密码的框图消息流：m=m1m2…mi，其中miM。密文流：c=c1c2…ci…=Ek1(m1)Ek2(m2)…Eki(mi)…，ciC。密钥流：{ki}，i0。一个完全随机的非周期序列，可以实现一次一密体制。但需要无限存储单元和复杂的输出逻辑函数f。i是第i时刻密钥流生成器的内部状态，以存储单元的存数矢量描述。加法流密码：ci=Eki(mi)=miki2020/1/16有限状态自动机FA(FinitestateAutomaton)具有离散输入和输出（输入集和输出集均有限）的一种数学模型有限状态集S={si|i=1,2,…,l}有限输入字符集X={Xi|i=1,2,…,m}有限输出字符集Y={Yk|k=1,2,…,n}转移函数Yj＝f1(sj,Xj)Sj+1＝f2(sj,Xj)第j时刻输入XjX，输出YjY2020/1/17例2-1S={s1,s2,s3},X={x1,x2,x3},Y=(y1,y2,y3)转移函数f1x1x2X3s1s2s3y1y2y3y3y1y2y2y3y1f2x1x2X3s1s2s3s2s3s1s1s2s3s3s1s22020/1/18FA的状态图表示若输入为x1x2x1x3x3x1初始状态s1输出为y1y1y2y1y3y12020/1/19作为FA的密钥流产生器同步流密码的密钥流产生器可看为一个参数为k的FA输出集Z，状态集Σ，状态转移函数φ和输出函数ψ，初态0设计的关键是φ和ψφiψkkkzi2020/1/110作为FA的密钥流产生器具有非线性的φ的FA理论很不完善，通常采用线性φ以及非线性的ψ可将此类产生器分为驱动部分和非线性组合部分。驱动部分控制状态转移非线性组合部分提供统计特性良好的序列2020/1/111两种常见的密钥流产生器LFSR非线性组合函数ziLFSRLFSRLFSR非线性组合函数zi2020/1/112流密码的分类同步流密码SSC(SynchronousStreamCipher)：i与明文消息无关，密钥流将独立于明文。特点：对于明文而言，这类加密变换是无记忆的。但它是时变的。只有保持两端精确同步才能正常工作。对主动攻击时异常敏感而有利于检测无差错传播(ErrorPropagation)2020/1/113流密码的分类自同步流密码SSSC(Self-SynchronousStreamCipher)i依赖于(kI,i-1,mi)，使密文ci不仅与当前输入mi有关，而且由于ki对i的关系而与以前的输入m1,m2,…,mi-1有关。一般在有限的n级存储下将与mi-1,…,mi-n有关。优点：具有自同步能力，强化了其抗统计分析的能力缺点：有n位长的差错传播。2020/1/114流密码的分类n级移存器n级移存器…………kiffkikikimiEki(·)ciciDki(·)mi2020/1/115序列的伪随机性周期序列{ki}i0，使对所有i，ki+p=ki成立的的最小整数p长为l的串(run)(kt,kt+1…kt+l-1)序列{ki}的一个周期中，kt-1kt=kt+1=…=kt+l-1kt+l例：长为l的1串和长为l的0串：10001,01110.ll2020/1/116序列的伪随机性周期自相关函数周期为p的序列{ki}i0，其周期自相关函数R(j)=(A－D)/p，j=0,1,…式中，A={0ip|：ki=ki+j}，D={0ip：kiki+j}。同相自相关函数当j为p的倍数，即pj时为，R(j)=1；异相自相关函数当j不是p的倍数时2020/1/117例2－2二元序列111001011100101110010…周期p=7同相自相关函数R(j)=1异相自相关函数R(j)=－1/7。2020/1/118Golomb随机性假设－PN序列G1．若p为偶，则0,1出现个数相等，皆为p/2。若p为奇，则0出现个数为(p1)/2。G2．长为l的串占1/2l，且“0”串和“1”串个数相等或至多差一个。G3．R(j)为双值，即所有异相自相关函数值相等。这与白噪声的自相关函数(函数)相近，这种序列又称为双值序列(TwoValueSequence)。PN序列可用于通信中同步序列、码分多址(CDMA)、导航中多基站码、雷达测距码等。但仅满足G1～G3特性的序列虽与白噪声序列相似，但远还不能满足密码体制要求。2020/1/119满足密码体制的另外三个条件C1．周期p要足够大，如大于1050；C2．序列{ki}i0产生易于高速生成；C3．当序列{ki}i0的任何部分暴露时，要分析整个序列，提取产生它的电路结构信息，在计算上是不可行的，称此为不可预测性(Unpredictability)。C3决定了密码的强度，是流密码理论的核心。它包含了流密码要研究的许多主要问题，如线性复杂度、相关免疫性、不可预测性等等。2020/1/120二、线性反馈移位寄存器序列2020/1/121线性反馈移位寄存器序列概念级数(Stages)：存储单元数。状态(State)：n个存储单元的存数(ki,…,ki+n-1)反馈函数：f(ki,ki+1,…,ki+n-1)是状态(ki,…,ki+n-1)的函数。线性反馈移位寄存器(LFSR)：f为线性函数非线性反馈移位寄存器：f为非线性函数2020/1/122反馈移位寄存器x1,x2,…xnf(ki,ki+1,…ki+n-1)ki+nki+n-1ki+n-2ki+1kiki-1.,…,k1k0xnxn-1x2x12020/1/123线性反馈移位寄存器f(x)为线性函数，输出序列满足下式cn-cn-1-cn-2-c1-c0ki+n-1ki+n-2ki+1kiki-1,…,k1,k0xnxn-1x2x11010),,(njjijniiniikckkfk2020/1/124二元线性移位寄存器二元条件下ki{0,1}，cj{0,1}，即断开或连通，为模2加，反馈函数可写成n阶线性递推关系式cncn-1cn-2c1c0ki+n-1ki+n-2ki+1kiki-1,…,k1,k0，xnxn-1x2x1njjijkc002020/1/125线性反馈移位寄存器例n=4的LFSR。输出序列满足ki－4＋ki－3＋ki=0。初始状态为1000。序列的周期为15=24－1。c4c3c2c1c0ki0001线性移存器序列的最长周期为2n－1。2020/1/126状态转移和相应输出时刻状态输出321000000111100002010003001004100115110006011007101118010119101001011011111110012111111301111140011115000112020/1/127m序列为2n－1的LFSR序列称为m序列。m序列是一类PN序列。n级m序列{ki}i0循环地遍历所有2n－1个非零状态，且任一非零输出皆为{ki}i0的移位，或为其循环等价(Cyclicallyequivalent)序列。初始状态不同2n－1个的m序列共有2n－1个,他们的全体记为(f),他们只是状态前后次序之别。2020/1/128特征多项式以LFSR的反馈系数所决定的多项式又称反馈多项式。式中，c0=cn=1反多项式称作是LFSR的联接多项式。cn0称之为非奇异LFSR。njjjnnnxcxxcxcxccxf0112210...)(nnnnncxcxcxcxfxxfxc1110*...)1()()(2020/1/129特征多项式定义:给定序列{ki}i0,幂级数称为该序列的生成函数定理3-1令{ki}i0(f)，f(x)是反馈多项式，令k(x)是{ki}i0的生成函数，则其中0)(iiixkxk)()()(*xfxaxk100)()(njjjlljlnxkcxa2020/1/130特征多项式证：)()()()())(())(()()(0)(10000)min(000*,xatlnxkcxaxkcxkcxkcxcxkxfxknjjnjtnjtnjjlnjnljljlnjljlnjnjljljlnnlllniiia(x)就是移存器初始值所对应的多项式2020/1/131特征多项式系:证：(f)的每个元素均可由a(x)/f(x)惟一决定，式中，deg(a(x))n，另一方面，(f)有2n个元素。而deg(a(x))n的多项式也恰有2n个。}))(deg()(/)({)(nxaxfxaf＝2020/1/132多项式的周期多项式f(x)的周期p为使f(x)除尽xn-1的最小整数n的取值。序列的周期与生成序列特征多项式的周期密切相关。引理3-2:令f(x)为n次式，周期为p，令{ki}i0(f)，则{ki}i0的周期p’p。2020/1/133多项式的周期引理3-3令f(x)是周期为p的n次既约多项式，令{ki}i0(f)，则{ki}i0的周期为p。证：令{ki}i0周期为p’，由引理3-2-3，有p’p，则有，deg(u(x))p，由(3-2-12)式有k(x)=a(x)/f*(x)，故有，由此可得。因为f(x)为n次既约式，deg(a(x))n，因此有f(x)(1＋xp’)但f(x)的周期为p，故有p|p’所以p’=p。)()()()1(xfxuxaxp＇)()()()1(xfxuxaxp2020/1/134多项式的周期引理3-4令f(x)为n次式，令{ki}i0(f)为m序列，则f(x)为既约的。证：采用反证法。假定f(x)=f1(x)·f2(x)，f1(x)为既约式，次数为n1,n20，n1n2。由(3-2-14)式，1/f1*(x)(f1)，故由引理3-2-3及附录3A，1/f1*(x)的周期除尽。类似地有。由定理3-2-1知1/f1*(x)应是{ki}i0的移位，.因而其周期为2n－1，惟一可能是n=n1，即f(x)=f1(x)。2020/1/135m序列的性质定理3-5以f(x)为特征多项式的LFSR的输出序列是m序列的充要条件为f(x)是本原的。系n级LFSR生成的不等价m序列共有(2n－1)/n个。定理3-6m序列满足Golomb的三条伪随机假设。2020/1/136m序列的性质m序列否满足密码要求？m-C1：n级m序列的周期为2n－1，n大，周期指数地加大，例如n=166时，p=1050(9.353610465×1049)。m-C2：只要知道n次本原多项式，m序列极易生成。m-C3：m序列极不安全，只要泄露2n位连续数字，就可完全确定出反馈多项式系数。2020/1/137m序列的破译已知ki,ki+1,…,ki+2n，由递推关系式可得出下式式中有n个线性方程和n个未知量，故可惟一解出ci，0in-1。