第讲流密码总结

第2章流密码2.1流密码的基本概念2.2线性反馈移位寄存器2.3线性移位寄存器的一元多项式表示2.4m序列的伪随机性2.5m序列密码的破译2.6非线性序列习题流密码的基本思想:密钥:k产生一个密钥流:z=z0z1…，明文串:x=x0x1x2…加密：y=y0y1y2…=Ez0(x0)Ez1(x1)Ez2(x2)…。密钥流发生器f：zi=f(k,σi)，σi是加密器中的记忆元件（存储器）在时刻i的状态，f是由密钥k和σi产生的函数。2.1流密码的基本概念(序列密码)图2.1分组密码和流密码的比较1x1yizixEyiixkk无记忆元件iymxlyxEyk内部记忆元件分组密码与流密码的区别就在于有无记忆性流密码的滚动密钥z0=f(k,σ0)由函数f、密钥k和指定的初态σ0完全确定。此后，由于输入加密器的明文可能影响加密器中内部记忆元件的存储状态，σi(i0)可能依赖于k，σ0，x0，x1，…，xi-1等参数。流密码:同步流密码和自同步流密码σi独立于明文字符的叫做同步流密码，否则叫做自同步流密码。在同步流密码中，由于zi=f(k,σi)与明文字符无关，因而此时密文字符yi=Ezi(xi)也不依赖于此前的明文字符。因此，可将同步流密码的加密器分成密钥流产生器和加密变换器两个部分。2.1.1同步流密码图2.2同步流密码体制模型izxEiixiyizizyDi滚动密钥生成器iyixiz滚动密钥生成器安全信道kk图2.3加法流密码体制模型二元加法流密码是目前最为常用的流密码体制，其加密变换可表示为yi=zixi。一次一密密码是加法流密码的原型。事实上，如果（即密钥用作滚动密钥流），则加法流密码就退化成一次一密密码。实际使用中，密码设计者的最大愿望是设计出一个滚动密钥生成器，使得密钥经其扩展成的密钥流序列具有如下性质：极大的周期、良好的统计特性、抗线性分析、抗统计分析。有限状态自动机是具有离散输入和输出（输入集和输出集均有限）的一种数学模型，由以下3部分组成：①有限状态集S={si|i=1,2,…,l}。②有限输入字符集A1={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有限状态自动机有限状态自动机可用有向图表示，称为转移图。转移图的顶点对应于自动机的状态，若状态si在输入A(1)i时转为状态sj，且输出一字符A(2)j，则在转移图中，从状态si到状态sj有一条标有(A(1)i,A(2)j)的弧线图2.4有限状态自动机的转移图若输入序列为A(1)1A(1)2A(1)1A(1)3A(1)3A(1)1，初始状态为s1，则得到状态序列s1s2s2s3s2s1s2输出字符序列A(2)1A(2)1A(2)2A(2)1A(2)3A(2)1密钥流产生器:参数为k的有限状态自动机，一个输出符号集Z、一个状态集∑、两个函数φ和ψ以及一个初始状态σ0组成。状态转移函数φ:σi→σi+1，将当前状态σi变为一个新状态σi+1，输出函数ψ:σi→zi，当前状态σi变为输出符号集中的一个元素zi。2.1.3密钥流产生器图2.5作为有限状态自动机的密钥流生成器关键:φ和ψ，使得输出序列z满足密钥流序列z应满足的几个条件，并且要求在设备上是节省的和容易实现的。为了实现这一目标，必须采用非线性函数。采用线性的φ和非线性的ψ时，将能够进行深入的分析并可以得到好的生成器。可将这类生成器分成驱动部分和非线性组合部分.驱动部分控制生成器的状态转移，并为非线性组合部分提供统计性能好的序列；非线性组合部分要利用这些序列组合出满足要求的密钥流序列。图2.6密钥流生成器的分解图2.7常见的两种密钥流产生器移位寄存器是流密码产生密钥流的一个主要组成部分。GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,…,an)组成，如图2.8所示。图2.8GF(2)上的n级反馈移位寄存器2.2线性反馈移位寄存器每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维向量，共有2n种可能的状态。每一时刻的状态可用n长序列a1,a2,…,an或n维向量(a1,a2,…,an)表示，其中ai是第i级存储器的内容。初始状态由用户确定，当第i个移位时钟脉冲到来时，每一级存储器ai都将其内容向下一级ai-1传递，并计算f(a1,a2,…,an)作为下一时刻的an。反馈函数f(a1,a2,…,an)是n元布尔函数，即n个变元a1,a2,…,an可以独立地取0和1这两个可能的值，函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后的函数值也为0或1。例2.2图2.9是一个3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由表2.2求出。图2.9一个3级反馈移位寄存器表2.2一个3级反馈移位寄存器的状态和输出状态（a3,a2,a1)输出101110111011101110110111即输出序列为110111011101…，周期为4。如果f(a1,a2,…,an)是a1,a2,…,an的线性函数，则称之为线性反馈移位寄存器LFSR（linearfeedbackshiftregister）。此时f可写为f(a1,a2,…,an)=cna1cn-1a2…c1an其中常数ci=0或1，是模2加法。ci=0或1可用开关的断开和闭合来实现，如图2.10所示。图2.10GF(2)上的n级线性反馈移位寄存器输出序列{at}满足an+t=cnatcn-1at+1…c1an+t-1其中t为非负正整数。线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。例2.3图2.11是一个5级线性反馈移位寄存器，其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出输出序列为1001101001000010101110110001111100110…周期为31。图2.11一个5级线性反馈移位寄存器在线性反馈移位寄存器中总是假定c1,c2,…,cn中至少有一个不为0，否则f(a1,a2,…,an)≡0，这样的话，在n个脉冲后状态必然是00…0，且这个状态必将一直持续下去。若只有一个系数不为0，设仅有cj不为0，实际上是一种延迟装置。一般对于n级线性反馈移位寄存器，总是假定cn=1。n级线性反馈移位寄存器的状态周期小于等于2n-1。输出序列的周期与状态周期相等，也小于等于2n-1。只要选择合适的反馈函数便可使序列的周期达到最大值2n-1.周期达到最大值的序列称为m序列。设n级线性移位寄存器的输出序列{ai}满足递推关系an+k=c1an+k-1c2an+k-2…cnak(*)对任何k=1成立。这种递推关系可用一个一元高次多项式p(x)=1+c1x+…＋cn+1xn-1＋cnxn表示，称这个多项式为LFSR的特征多项式或特征多项式。2.3线性移位寄存器的一元多项式表示n设n级线性移位寄存器对应于递推关系(*)，由于ai∈GF(2)(i=1,2,…,n)，所以共有2n组初始状态，即有2n个递推序列，其中非恒零的有2n-1个，记2n-1个非零序列的全体为G(p(x))。定义2.1给定序列{ai}，幂级数称为该序列的生成函数。定理2.1设p(x)=1+c1x+…+cn-1xn-1+cnxn是GF(2)上的多项式，G(p(x))中任一序列{ai}的生成函数A(x)满足：A(x)=(x)/p(x)其中=(a1+a2x+…+anxn-1)+c1x(a1+a2x+…+an-1xn-2)+c2x2(a1+a2x+…+an-2xn-3)+…+cn-1xn-1a1证明：在等式an+1=c1anc2an-1…cna1an+2=c1an+1c2an…cna2…两边分别乘以xn,xn+1,…，再求和，可得A(x)-(a1+a2x+…+anxn-1)=c1x[A(x)-(a1+a2x+…+an-1xn-2)]+c2x2[A(x)-(a1+a2x+…+an-2xn-3)]+…+cnxnA(x)移项整理得(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即(证毕)注意在GF(2)上有a+a=0。定理2.2p(x)|q(x)的充要条件是G(p(x))G(q(x))。上述定理说明可用n级LFSR产生的序列，也可用级数更多的LFSR来产生。定义2.2设p(x)是GF(2)上的多项式，使p(x)|(xp-1)的最小p称为p(x)的周期或阶。定理2.3若序列{ai}的特征多项式p(x)定义在GF(2)上，p是p(x)的周期，则{ai}的周期r|p。n级LFSR输出序列的周期r不依赖于初始条件，而依赖于特征多项式p(x)。我们感兴趣的是LFSR遍历2n-1个非零状态，这时序列的周期达到最大2n-1，这种序列就是m序列。显然对于特征多项式一样，而仅初始条件不同的两个输出序列，一个记为{a(1)i}，另一个记为{a(2)i}，其中一个必是另一个的移位，即存在一个常数k，使得a(1)i=a(2)k+i,i=1,2,…下面讨论特征多项式满足什么条件时，LFSR的输出序列为m序列。•序列的周期整除特征多项式的周期•若特征多项式是不可约的，则序列的周期等于特征多项式的周期•序列有最大周期特征多项式是不可约的•序列有最大周期特征多项式是本原多项式小结流密码的安全性取决于密钥流的安全性，要求密钥流序列有好的随机性，以使密码分析者对它无法预测。也就是说，即使截获其中一段，也无法推测后面是什么。如果密钥流是周期的，要完全做到随机性是困难的。严格地说，这样的序列不可能做到随机，只能要求截获比周期短的一段时不会泄露更多信息，这样的序列称为伪随机序列。2.4m序列的伪随机性有限域上的二元加法流密码（如图2.3）是目前最为常用的流密码体制，设滚动密钥生成器是线性反馈移位寄存器，产生的密钥是序列。又设Sh和Sh+1是序列中两个连续的n长向量，其中2.5m序列密码的破译11211,hhhhhhhnhnaaaaSSaa设序列{ai}满足线性递推关系：可表示为1122hnhnhnnhacacaca121121101000010hhhhnnnhnhnaaaaccccaa或Sh+1=M·Sh，其中又设敌手知道一段长为2n的明密文对，即已知12101000010ccccMnnn122nxxxx122nyyyy于是可求出一段长为2n的密钥序列其中,由此可推出线性反馈移位寄存器连续的n+1个状态：122nzzzziiiiiizxyxxz1121222312311122122nnnnnnnnnnnSzzzaaaSzzzaaaSzzzaaa记为记为记为做矩阵而若X可逆，则12nXSSS122311221112111nnnnnnnnnnnnaaaaaaaaacccaaacccX111122nnnnncccaaaX下面证明X的确是可逆的。因为X是由S1,S2,…,Sn作为列向量，要证X可逆，只要证明这n个向量线性无关。由序列递推关系：可推出向量的递推关系：1122hnhnhnnhacacaca1