《密码学ppt电子课件教案-第二章 序列密码》由会员分享，可在线阅读，更多相关《密码学ppt电子课件教案-第二章 序列密码（44页珍藏版）》请在金锄头文库上搜索。
1、2018/9/25,1,第二章 序列密码,一、序列密码的基本概念 二、线性反馈移位寄存器 三、B-M综合算法 四、非线性序列,一、序列密码的基本概念,2018/9/25,3,序列密码的分类,同步序列密码SSC(Synchronous Stream Cipher)： i与明文消息无关，密钥流将独立于明文。 特点： 对于明文而言，这类加密变换是无记忆的。但它是时变的。 只有保持两端精确同步才能正常工作。 对主动攻击时异常敏感而有利于检测 无差错传播(Error Propagation),2018/9/25,4,序列密码的分类,自同步序列密码SSSC(Self-Synchronous Stream
2、Cipher) i依赖于(kI,i-1,mi)，使密文ci不仅与当前输入mi有关，而且由于ki对i的关系而与以前的输入m1, m2 ,mi-1有关。一般在有限的n级存储下将与mi-1,mi-n有关。 优点：具有自同步能力，强化了其抗统计分析的能力 缺点：有n位长的差错传播。,2018/9/25,5,序列密码的分类,n级移存器 n 级移存器 ki f f ki ki ki mi Eki() ci ci Dki() mi,2018/9/25,6,序列的伪随机性,周期 序列kii0，使 对所有i，ki+p=ki 成立的的最小整数p 长为l的串(run) (kt , kt+1kt+l -1) 序列ki
3、的一个周期中， kt-1kt=kt+1=kt+l -1 kt+l 例：长为l的1串和长为l的0串：,2018/9/25,7,序列的伪随机性,周期自相关函数 周期为p的序列kii0，其周期自相关函数 R(j)=(AD)/p ， j=0, 1, 式中，A=0ip|：ki=ki+j，D=0ip：kiki+j。 同相自相关函数 当j为p的倍数，即pj时为，R(j)=1； 异相自相关函数 当j不是p的倍数时,2018/9/25,8,例22,二元序列111001011100101110010 周期p=7 同相自相关函数R(j)=1 异相自相关函数R(j)=1/7。,2018/9/25,9,Golomb随机
4、性假设PN序列,G1若p为偶，则0, 1出现个数相等，皆为p/2。若p为奇，则0出现个数为(p1)/2。 G2长为l的串占1/2l，且“0”串和“1”串个数相等或至多差一个。 G3R(j)为双值，即所有异相自相关函数值相等。这与白噪声的自相关函数(函数)相近，这种序列又称为双值序列(Two Value Sequence)。 PN序列可用于通信中同步序列、码分多址(CDMA)、导航中多基站码、雷达测距码等。但仅满足G1G3特性的序列虽与白噪声序列相似，但远还不能满足密码体制要求。,2018/9/25,10,满足密码体制的另外三个条件,C1周期p要足够大，如大于1050； C2序列kii0产生易于
5、高速生成； C3当序列kii0的任何部分暴露时，要分析整个序列，提取产生它的电路结构信息， 在计算上是不可行的，称此为不可预测性(Unpredictability)。 C3决定了密码的强度，是序列密码理论的核心。它包含了序列密码要研究的许多主要问题，如线性复杂度、相关免疫性、不可预测性等等。,二、线性反馈移位寄存器序列,2018/9/25,12,线性反馈移位寄存器序列概念,级数(Stages)：存储单元数。 状态(State)：n个存储单元的存数(ki, , ki+n-1) 反馈函数：f(ki, ki+1, , ki+n-1)是状态(ki, ki+n-1)的函数。 线性反馈移位寄存器(LFSR
6、)：f 为线性函数 非线性反馈移位寄存器： f 为非线性函数,2018/9/25,13,反馈移位寄存器,x1, x2, xn f (ki, ki+1, ki+n-1) ki+n ki+n-1 ki+n-2 ki+1 ki ki-1.,k1 k0 xn xn-1 x2 x1,2018/9/25,14,线性反馈移位寄存器,f(x)为线性函数，输出序列满足下式 cn -cn-1 -cn-2 -c1 -c0 ki+n-1 ki+n-2 ki+1 ki ki-1, k1, k0 xn xn-1 x2 x1,2018/9/25,15,二元线性移位寄存器,二元条件下ki0, 1，cj 0, 1， 即断开或连
7、通，为模2加，反馈函数可写成n阶线性递推关系式 cn cn-1 cn-2 c1 c0 ki+n-1 ki+n-2 ki+1 ki ki-1, , k1 , xn xn-1 x2 x1,2018/9/25,16,线性反馈移位寄存器,例 n=4的LFSR。输出序列满足ki4ki3ki=0。初始状态为1000。序列的周期为15=241。 c4 c3 c2 c1 c0 ki 0 0 0 1 线性移存器序列的最长周期为2n1。,2018/9/25,17,状态转移和相应输出,时刻 状 态 输 出 3 2 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 2 0 1 0 0 0 3 0 0 1 0
8、 0 4 1 0 0 1 1 5 1 1 0 0 0 6 0 1 1 0 0 7 1 0 1 1 1 8 0 1 0 1 1 9 1 0 1 0 0 10 1 1 0 1 1 11 1 1 1 0 0 12 1 1 1 1 1 13 0 1 1 1 1 14 0 0 1 1 1 15 0 0 0 1 1,2018/9/25,18,m序列,为2n1的LFSR序列称为m序列。 m序列是一类PN序列。 n级m序列kii0循环地遍历所有2n1个非零状态，且任一非零输出皆为kii0的移位，或为其循环等价(Cyclically equivalent)序列。 初始状态不同2n1个的m序列共有2n1个,他们的
9、全体记为(f), 他们只是状态前后次序之别。,2018/9/25,19,特征多项式,以LFSR的反馈系数所决定的多项式 又称反馈多项式。式中，c0=cn=1 反多项式 称作是LFSR的联接多项式。cn0称之为非奇异LFSR。,2018/9/25,20,特征多项式,定义:给定序列 kii0, 幂级数 称为该序列的生成函数 定理3-1 令kii0(f)，f(x)是反馈多项式，令k(x)是kii0的生成函数，则 其中,2018/9/25,21,特征多项式,证：,a(x)就是移存器初始值所对应的多项式,2018/9/25,22,特征多项式,系: 证：(f)的每个元素均可由a(x)/f (x)惟一决定，
10、式中，deg(a(x)n，另一方面，(f)有2n个元素。而deg(a(x)n的多项式也恰有2n个。,2018/9/25,23,多项式的周期,多项式f(x)的周期p为使f(x)除尽xn-1的最小整数n的取值。 序列的周期与生成序列特征多项式的周期密切相关。 引理3-2: 令f(x)为n次式，周期为p，令kii0(f)，则kii0的周期pp。,2018/9/25,24,多项式的周期,引理3-3 令f(x)是周期为p的n次既约多项式，令kii0(f)，则kii0的周期为p。 证：令kii0周期为p，由引理3-2-3，有pp，则有，deg(u(x)p，由(3-2-12)式有k(x)=a(x)/f*(x
11、)，故有， 由此可得 因为f(x)为n次既约式， deg(a(x)n，因此有f(x)(1xp)但f(x)的周期为p，故有p|p所以p=p。,2018/9/25,25,多项式的周期,引理3-4 令f(x)为n次式，令kii0(f)为m序列，则f(x)为既约的。 证：采用反证法。假定f(x)=f1 (x)f2(x)，f1(x)为既约式，次数为n1, n20，n1 n2。由(3-2-14)式，1/f1*(x)(f1)，故由引理3-2-3及附录3A，1/f1* (x)的周期除尽。类似地有。由定理3-2-1知1/f1*(x)应是kii0的移位，.因而其周期为2n1，惟一可能是n=n1，即f(x)=f1(
12、x)。,2018/9/25,26,m序列的性质,定理3-5 以f(x)为特征多项式的LFSR的输出序列是m序列的充要条件为f(x)是本原的。 系n级LFSR生成的不等价m序列共有(2n1)/n个。 定理 3-6 m序列满足Golomb的三条伪随机假设。,2018/9/25,27,m序列的性质,m序列否满足密码要求？ m-C1：n级m序列的周期为2n1，n大，周期指数地加大，例如n=166时，p=1050(9.353610465 1049)。 m-C2：只要知道n次本原多项式，m序列极易生成。 m-C3：m序列极不安全，只要泄露2n位连续数字，就可完全确定出反馈多项式系数。,2018/9/25,
13、28,m序列的破译,已知ki, ki+1, ki+2n，由递推关系式可得出下式 式中有n个线性方程和n个未知量，故可惟一解出ci，0in-1。,三、B-M综合算法,2018/9/25,30,根据密码学的需要，对于LFSR主要考虑下面两问题： (1)如何利用级数尽可能小的LFSR产生周期长、统计特性好的序列； (2)已知一个序列a，如何构造一个尽可能短的LFSR来产生a。,2018/9/25,31,B-M综合算法,2018/9/25,32,2018/9/25,33,BM综合算法的描述,2018/9/25,34,四、 非线性序列,2018/9/25,36,非线性序列,线性复杂度：能产生周期序列 kii 0的LFSR的最小级数n。 显然，n级m序列的线性复杂度为n。 线性复杂度是研究和设计密码的重要指标和工具。 一个伪随机序列若其线性复杂度低，就易于由部分序列综合出生成它的LFSR。一般移存器序列的线性复杂度nL2n。L大不一定就安全；但L小肯定是不安全的!,
