第2章-流密码

密码学第2章流密码2.1流密码的基本概念2.2线性反馈移位寄存器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流密码的基本概念密码学1.密钥流强度依赖：随机性不可预测性2.核心问题：密钥生成器的设计3.实现可靠解密的关键技术：同步密码学4.分组密码与流密码的区别：有无记忆性流密码的滚动密钥z0=f(k,σ0)由函数f、密钥k和指定的初态σ0完全确定。此后，由于输入加密器的明文可能影响加密器中内部记忆元件的存储状态，因而σi(i0)可能依赖于k，σ0，x0，x1，…，xi-1等参数。密码学根据加密器中记忆元件的存储状态σi是否依赖于输入的明文字符，流密码可进一步分成:同步流密码:σi独立于明文字符;（目前使用）自同步流密码:σi依赖于明文字符;可将同步流密码的加密器分成密钥流产生器和加密变换器两个部分。2.1.1同步流密码密码学图2.2同步流密码体制模型密码学同步流密码的加密变换Ezi可以有多种选择，只要保证变换是可逆的即可。实际使用的数字保密通信系统一般都是二元系统，因而在有限域GF(2)上讨论的二元加法流密码（如图2.3）是目前最为常用的流密码体制，其加密变换可表示为:yi=zixi。密码学图2.3加法流密码体制模型密码学密码设计者的最大愿望是设计一次一密的密码。实际使用时，密钥流序列具有如下性质：极大的周期良好的统计特性抗线性分析抗统计分析流密码的优点：加密速度快、容易实现密码学有限状态自动机是具有离散输入和输出（输入集和输出集均有限）的一种数学模型，由以下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有限状态自动机（FA,FinitestateAutomation）密码学例2.1S={s1,s2,s3}，A1={A(1)1,A(1)2,A(1)3}，A2={A(2)1,A(2)2,A(2)3}，转移函数由表2.1给出。表2.1转移函数f1和f2A1(1)A2(1)A3(1)A1(1)A2(1)A3(1)S1A1(2)A3(2)A2(2)S1S2S1S3S2A2(2)A1(2)A3(2)S2S3S2S1S3A3(2)A2(2)A1(2)S3S1S3S2密码学有限状态自动机可用有向图表示，称为转移图。转移图的顶点对应于自动机的状态，若状态si在输入A(1)i时转为状态sj，且输出一字符A(2)j，则在转移图中，从状态si到状态sj有一条标有(A(1)i,A(2)j)的弧线，见图2.4。密码学A1(1)A2(1)A3(1)A1(1)A2(1)A3(1)S1A1(2)A3(2)A2(2)S1S2S1S3S2A2(2)A1(2)A3(2)S2S3S2S1S3A3(2)A2(2)A1(2)S3S1S3S2密码学例：若输入序列为: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图2.4有限状态自动机的转移图密码学同步流密码的关键是密钥流产生器。一般可将其看成一个参数为k的有限状态自动机，由一个输出符号集Z、一个状态集∑、两个函数φ和ψ以及一个初始状态σ0组成。关键在于找出适当的状态转移函数φ和输出函数ψ。使得输出序列z满足密钥流序列z应满足的几个条件，并且要求在设备上是节省的和容易实现的。为了实现这一目标，必须采用非线性函数。2.1.3密钥流产生器密码学由于具有非线性的φ的有限状态自动机理论很不完善，相应的密钥流产生器的分析工作受到极大的限制。当采用线性的φ和非线性的ψ时，将能够进行深入的分析并可以得到好的生成器；可将这类生成器分成驱动部分和非线性组合部分（如图2.6）；驱动部分控制生成器的状态转移，并为非线性组合部分提供统计性能好的序列；非线性组合部分要利用这些序列组合出满足要求的密钥流序列。密码学图2.6密钥流生成器的分解密码学图2.7常见的两种密钥流产生器目前最为流行和实用的密钥流产生器如图2.7所示，其驱动部分是一个或多个线性反馈移位寄存器。密码学移位寄存器是流密码产生密钥流的一个主要组成部分。GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,…,an)组成.2.2线性反馈移位寄存器图2.8GF(2)上的n级反馈移位寄存器密码学每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维向量，共有2n种可能的状态。每一时刻的状态可用n长序列a1,a2,…,an或n维向量(a1,a2,…,an)表示，其中ai是第i级存储器的内容。密码学初始状态由用户确定，当第i个移位时钟脉冲到来时，每一级存储器ai都将其内容向下一级ai-1传递，并根据寄存器此时的状态a1,a2,…,an计算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)输出101110111011101110101110即输出序列为101110111011…，周期为4。密码学如果移位寄存器的反馈函数f(a1,a2,…,an)是a1，a2，…，an的线性函数，则称之为线性反馈移位寄存器LFSR（linearfeedbackshiftregister）。此时f可写为：f(a1,a2,…,an)=cna1cn-1a2…c1an其中常数ci=0或12加法。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个不同的状态。若其初始状态为0，则其状态恒为0。若其初始状态非0，则其后继状态不会为0。因此n级线性反馈移位寄存器的状态周期小于等于2n-1。其输出序列的周期与状态周期相等，也小于等于2n-1。只要选择合适的反馈函数便可使序列的周期达到最大值2n-1，周期达到最大值的序列称为m序列。密码学设n级线性移位寄存器的输出序列满足递推关系an+k=c1an+k-1c2an+k-2…cnak(*)对任何成立。这种递推关系可用一个一元高次多项式P(x)=1+c1x+…＋cn+1xn-1＋cnxn表示，称这个多项式为LFSR的特征多项式或特征多项式。2.3线性移位寄存器的一元多项式表示密码学流密码的安全性取决于:随机性无法预测伪随机序列:要求截获比周期短的一段时不会泄露更多信息。周期：序列{ki},使得对所有的ki+p=ki的最小整数p长为L的串（游程）：设{ai}=(a1a2a3…)为0、1序列，例如00110111，其前两个数字是00，称为0的2游程；接着是11，是1的2游程；再下来是0的1游程和1的3游程。2.4m序列的伪随机性密码学自相关函数：GF(2)上周期为T的序列{ai}的自相关函数定义为：R(τ)=(1/T)∑(-1)ak(-1)ak+τ,0≤τ≤T-1定义中的和式表示序列{ai}与{ai+τ}（序列{ai}向后平移τ位得到）在一个周期内对应位相同的位数与对应位不同的位数之差。同相自相关函数：当τ=0时，R(τ)=1；异相自相关函数：当τ≠0时，R(τ)为异相自相关函数。密码学例：二元序列111001011100101110010……周期为7同相自相关函数为：1异相自相关函数为：-1/7密码学Golomb对伪随机周期序列提出了应满足的如下3个随机性公设：①在序列的一个周期内，0与1的个数相差至多为1。②在序列的一个周期内，长为i的游程占游程总数的1/2i(i=1,2,…)，且在等长的游程中0的游程个数和1的游程个数相等。③异相自相关函数是一个常数。这种序列叫PN序列，类似白噪声序列。满足公设的序列可以用于通信、CDMA寻址、导航基站测距等。m序列满足Golomb的3个随机性公设。密码学从密码系统的角度看，一个伪随机序列还应满足下面的条件：①{ai}的周期相当大。②{ai}的确定在计算上是容易的。③由密文及相应的明文的部分信息，不能确定整个{ai}。m序列不满足③,m序列用于通信较多，用于密钥流不够安全。密码学设序列{ai}满足线性递推关系：设敌手知道一段长为2n的明密文对，即已知2.5m序列密码的破译122nxxxx122nyyyy1122hnhnhnnhacacaca密码学于是可求出一段长为2n的密钥序列其中,由此可推出线性反馈移位寄存器连续的n+1个状态：122nzzzziiiiiizxyxxz1121222312311122122nnnnnnnnnnnSzzzaaaSzzzaaaSzzzaaa记为记为记为密码学而若X可逆，则122311221112111nnnnnnnnnnnnaaaaaaaaacccaaacccX111122nnnnncccaaaX密码学例2.6设敌手得到密文串101101011110010和相应的明文串011001111111001，假定敌手还知道密钥流是使用5级线性反馈移位寄存器产生的，破译过程如下：（1）计算出相应的密钥流为110100100001011。（2）用密钥流中前10个比特建立如下方程123452345667891054321345674567856789aaaaaaaaaaaaaaacccccaaaaaaaaaaaaaaa密码学即而54321110101010001000010011001000100ccccc111010010011010010010010010000110010010110010010110