《现代密码学 第2章》由会员分享，可在线阅读，更多相关《现代密码学 第2章（59页珍藏版）》请在金锄头文库上搜索。
1、第2章 流密码,2.1 流密码的基本概念 2.2 线性反馈移位寄存器 2.3 线性移位寄存器的一元多项式表示 2.4 m序列的伪随机性 2.5 m序列密码的破译 2.6 非线性序列,流密码的基本思想是利用密钥k产生一个密钥流z=z0z1，并使用如下规则对明文串x=x0 x1x2加密： y=y0y1y2=Ez0(x0)Ez1(x1)Ez2(x2)。 密钥流由密钥流发生器f产生： zi=f(k,i)，这里i是加密器中的记忆元件（存储器）在时刻i的状态，f是由密钥k和i产生的函数。 流密码的滚动密钥z0=f(k,0)由函数f、密钥k和指定的初态0完全确定。,2.1 流密码的基本概念,分组密码与流密码
2、的区别就在于有无记忆性。 图2.1 分组密码和流密码的比较,2.1 流密码的基本概念,根据加密器中记忆元件的存储状态i是否依赖于输入的明文字符，流密码可进一步分成同步和自同步两种。i独立于明文字符的叫做同步流密码，否则叫做自同步流密码。 在同步流密码中，由于zi=f(k,i)与明文字符无关，因而此时密文字符yi=Ezi(xi)也不依赖于此前的明文字符。因此，可将同步流密码的加密器分成密钥流产生器和加密变换器两个部分。,2.1.1 同步流密码,图2.2 同步流密码体制模型,2.1.1 同步流密码,常用的流密码：在有限域CF(2)上讨论的二元加法流密码，其加密变换可表示为yi=zi xi。,2.1
3、.1 同步流密码,图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 有限状态自动机,例2.1 S=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
4、.1.2 有限状态自动机,有限状态自动机可用有向图表示，称为转移图。转移图的顶点对应于自动机的状态，若状态si在输入A(1)i时转为状态sj，且输出一字符A(2)j，则在转移图中，从状态si到状态sj有一条标有(A(1)i,A(2)j)的弧线，见图2.4。,2.1.2 有限状态自动机,图2.4 有限状态自动机的转移图,2.1.2 有限状态自动机,例2.1中，若输入序列为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.1.2 有限状态自动机,
5、同步流密码的关键是密钥流产生器。 一般可将其看成一个参数为k的有限状态自动机，由一个输出符号集Z、一个状态集、两个函数和以及一个初始状态0组成（如图2.5）。,2.1.3 密钥流产生器,图2.5 作为有限状态自动机的密钥流生成器,状态转移函数:ii+1，将当前状态i变为一个新状态i+1，输出函数:izi，当前状态i变为输出符号集中的一个元素zi。 密钥流生成器设计的关键：找出适当的状态转移函数和输出函数，使得输出序列z满足密钥流序列z应满足的几个条件，并且要求在设备上是节省的和容易实现的。为了实现这一目标，必须采用非线性函数。,2.1.3 密钥流产生器,驱动部分控制生成器的状态转移，并为非线性
6、组合部分提供统计性能好的序列；而非线性组合部分要利用这些序列组合出满足要求的密钥流序列。,图2.6 密钥流生成器的分解,2.1.3 密钥流产生器,目前最为流行和实用的密钥流产生器如图2.7所示，其驱动部分是一个或多个线性反馈移位寄存器。,图2.7 常见的两种密钥流产生器,2.1.3 密钥流产生器,移位寄存器是流密码产生密钥流的一个主要组成部分。GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,an)组成，如图2.8所示。,2.2 线性反馈移位寄存器,图2.8 GF(2)上的n级反馈移位寄存器,例2.2 图2.9是一个3级反馈移位寄存器，其初始状态为(a1,a2,a
7、3)=(1,0,1)，输出可由表2.2求出。,图2.9 一个3级反馈移位寄存器,2.2 线性反馈移位寄存器,表2.2 一个3级反馈移位 寄存器的状态和输出,2.2 线性反馈移位寄存器,即输出序列为101110111011， 周期为4。,如果移位寄存器的反馈函数f(a1,a2,an)是a1，a2，an的线性函数，则称之为线性反馈移位寄存器LFSR（linear feedback shift register）。此时f可写为 f(a1,a2,an)=cna1cn-1a2c1an 其中常数ci=0或1，是模2加法。ci=0或1可用开关的断开和闭合来实现，如图2.10所示。,2.2 线性反馈移位寄存器
8、,图2.10 GF(2)上的n级线性反馈移位寄存器,2.2 线性反馈移位寄存器,输出序列at满足an+t=cnat cn-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级线性反馈移位寄存器,2.2 线性反馈移位寄存器,设n级线性移位寄存器的输出序列ai满足递推关系 an+k=c1an+k-1 c2an+k-2 cnak (*) 对任何成立。这种
9、递推关系可用一个一元高次多项式 P(x)=1+c1x+cn+1xn-1cnxn 表示，称这个多项式为LFSR的特征多项式或特征多项式。 共有2n组初始状态，即有2n个递推序列，其中非恒零的有2n-1个，记2n-1个非零序列的全体为G(p(x)。,2.3 线性移位寄存器的一元多项式表示,定义2.1 给定序列ai，幂级数 A(x)=aixi-1 称为该序列的生成函数。 定理2.1 设p(x)=1+c1x+cn-1xn-1+cnxn是GF(2)上的多项式，G(p(x)中任一序列ai的生成函数A(x)满足： A(x)=(x)/p(x) 其中 ,2.3 线性移位寄存器的一元多项式表示,证明： 在等式 a
10、n+1=c1anc2an-1cna1 an+2=c1an+1c2ancna2 两边分别乘以xn,xn+1,，再求和，可得 A(x)-(a1+a2x+anxn-1) =c1xA(x)-(a1+a2x+an-1xn-2) +c2x2A(x)-(a1+a2x+an-2xn-3)+cnxnA(x),定理2.1 设p(x)=1+c1x+cn-1xn-1+cnxn是GF(2)上的多项式，G(p(x)中任一序列ai的生成函数A(x)满足： A(x)=(x)/p(x) ,移项整理得 (1+c1x+cn-1xn-1+cnxn)A(x) =(a1+a2x+anxn-1)+c1x(a1+a2x+an-1xn-2)
11、+c2x2(a1+a2x+an-2xn-3)+cn-1xn-1a1 即 p(x)A(x)=cn-ixn-iajxj-1=(x) (证毕) 注意在GF(2)上有a+a=0。,定理2.1 设p(x)=1+c1x+cn-1xn-1+cnxn是GF(2)上的多项式，G(p(x)中任一序列ai的生成函数A(x)满足： A(x)=(x)/p(x) ,定理2.2 p(x)|q(x)的充要条件是 G(p(x)G(q(x)。,证明：若p(x)|q(x)，可设q(x)=p(x)r(x)，因此 A(x)=(x)/p(x)= (x)r(x)/p(x)r(x)=(x)r(x)/q(x) 所以若aiG(p(x)，则aiG
12、(q(x)， 即G(p(x) G(q(x)。,反之，若G(p(x) G(q(x)，则对于多项式(x)，存在序列aiG(p(x)以A(x)=(x)p(x)为生成函数。特别地，对于多项式(x)=1，存在序列aiG(p(x)以1/p(x)为生成函数。由于G(p(x) G(q(x)，序列aiG(q(x)，所以存在函数r(x)，使得ai的生成函数也等于r(x)q(x)，从而1/p(x)=r(x)q(x)，即q(x)=p(x)r(x)，所以p(x)|q(x)。(证毕),定义2.2 设p(x)是GF(2)上的多项式，使p(x)|(xp-1)的最小p称为p(x)的周期或阶。 定理2.3 若序列ai的特征多项式
13、p(x)定义在GF(2)上，p是p(x)的周期，则ai的周期r|p。,证明：由p(x)周期的定义得p(x)|(xp-1)，因此存在q(x)，使得xp-1=p(x)q(x)，又由p(x)A(x)= (x)可得p(x)q(x)A(x)=(x)q(x)，所以(xp-1)A(x)=(x)q(x)。由于q(x)的次数为p-n，(x)的次数不超过n-1，所以(xp-1)A(x)的次数不超过(p-n)+(n-1)=p-1。这就证明了对于任意正整数i都有ai+p=ai。 设p=kr+t,0tr，则ai+p=ai+kr+t=ai+t=ai，所以t=0，即r|p。（证毕）,定义2.3 仅能被非0常数或自身的常数倍
14、除尽，但不能被其他多项式除尽的多项式称为即约多项式或不可约多项式 。 定理2.4 设p(x)是n次不可约多项式，周期为m，序列aiG(p(x)，则ai的周期为m。 定理2.5 n级LFSR产生的序列有最大周期2n-1的必要条件是其特征多项式为不可约的。,2.3 线性移位寄存器的一元多项式表示,定理2.4 设p(x)是n次不可约多项式，周期为m，序列aiG(p(x)，则ai的周期为m。,2.3 线性移位寄存器的一元多项式表示,证明：设ai的周期为r，由定理2.3有r|m，所以rm。 设A(x)为ai的生成函数，A(x)=(x)p(x)，即p(x)A(x)=(x)0，(x)的次数不超过n-1。而
15、A(x)=aixi-1=a1+a2x+arxr-1+xr(a1+a2x+arxr-1) +(xr)2(a1+a2x+arxr-1)+=a1+a2x+arxr-1/(1-xr) =a1+a2x+arxr-1/(xr-1),于是A(x)=a1+a2x+arxr-1/(xr-1)=(x)p(x)，即 p(x)(a1+a2x+arxr-1)=(x)(xr-1) 因p(x)是不可约的，所以gcd(p(x),(x)=1，p(x)|(xr-1)，因此mr。综上r=m。（证毕）,定理2.5 n级LFSR产生的序列有最大周期2n-1的必要条件是其特征多项式为不可约的。,2.3 线性移位寄存器的一元多项式表示,证
16、明：设n级LFSR产生的序列周期达到最大2n-1，除0序列外，每一序列的周期由特征多项式惟一决定，而与初始状态无关。设特征多项式为p(x)，若p(x)可约，可设为p(x)=g(x)h(x)，其中g(x)不可约，且次数kn。由于G(g(x) G(p(x)，而G(g(x)中序列的周期一方面不超过2k-1，另一方面又等于2n-1，这是矛盾的，所以p(x)不可约。（证毕） 该定理的逆不成立，即LFSR的特征多项式为不可约多项式时，其输出序列不一定是m序列。,例2.4 f(x)=x4+x3+x2+x+1为GF(2)上的不可约多项式，这可由x,x+1,x2+x+1都不能整除f(x)得到。以f(x)为特征多项式的LFSR的输出序列可由 ak=ak-1ak-2ak-3ak-4(k4) 和给定的初始状态求出，设初始状态为0001，则输出序列为000110001100011，周期为5，不是m序列。,2.3 线性移位寄存器的一元多项式表示,定义2.4 若n次不可约多项式p(x)的阶为2n-1，则
