《流密码详解教材》由会员分享，可在线阅读，更多相关《流密码详解教材（77页珍藏版）》请在金锄头文库上搜索。
1、1,现代密码学,21世纪高等学校计算机规划教材,Modern Cryptography,李向东 中原工学院计算机学院 124197985 2011.9-2012.1,2,第2章 流密码,李向东 中原工学院计算机学院 124197985 2011.9-2012.1,3,第2章 流密码,2.1 流密码一般模型 2.2 线性反馈移位寄存器序列 2.3 线性复杂度及B-M算法 2.4 非线性序列生成器 2.5 流密码算法,4,2.1 流密码一般模型,实用密码体制的分类,5,2.1 流密码一般模型,流密码( stream cipher)(序列密码)体制模型,明文序列: m= m1 m2 m3 ; 密钥序
2、列: z=z1 z2 z3 ; 密文序列: c= c1c2 c3 ; 加密变换: ci=E(zi,mi) (i=1,2,3,); 解密变换: mi=D(zi, ci) (i=1,2,3,).,6,课堂讨论：,加密函数和解密函数都用异或运算，行不行？ 什么样的加解密算法是高效、安全的？Why？ 实用的流密码方案中，加解密算法是什么？,7,流密码原理框图,2.1 流密码一般模型,8,流密码体制的安全性 当流钥序列是具有均匀分布的离散无记忆随机序列时, 在理论上是不可破译的. 实用的困难性 真正的具有均匀分布的随机序列是不可能重复产生的. 密钥序列长(至少与明文序列一样长), 其管理(存储、分配)难
3、. 设计流密码体制的关键问题 设计产生密钥序列的方法.,2.1 流密码一般模型,9,序列密码的分类 同步流密码(SSC: synchronous stream cipher) 产生密钥序列的算法与明文、密文无关. 自同步流密码(SSSC: self-synchronous stream cipher) 产生密钥序列的算法与以前的密文有关.,2.1 流密码一般模型,10,同步流密码(SSC: synchronous stream cipher) 只要通信双方的密钥序列产生器具有相同的“种子序列”和相同的“初始状态”,就能产生相同的密钥序列. 通信双方必须保持精确同步,才能正确解密. 容易检测插入
4、、删除、重播等主动攻击. 没有差错传播. 讨论：如何对SSC的这种“同步”性质进行形式化描述？,2.1 流密码一般模型,11,同步流密码(SSC: synchronous stream cipher) 产生密钥序列的算法与明文、密文无关.,2.1 流密码一般模型,12,自同步流密码(SSSC: self-synchronous stream cipher) 产生密钥序列的算法与以前的密文有关.,2.1 流密码一般模型,13,自同步流密码(SSSC) 密钥流生成器是一种有记忆变换器 密钥流与明文符号有关： i 时刻的密文不仅取决于i 时刻的明文，而且与i 时刻之前的l个明文符号有关 具有有限的差
5、错传播 具有自同步能力 把明文每个字符扩散在密文多个字符中,强化了抗统计分析的能力 问：SSSC是如何自同步的？请email回应。,2.1 流密码一般模型,14,二元加法序列密码,明文序列: m= m1 m2 m3 ; 密钥序列: z= z1 z2 z3 ; 密文序列: c= c1 c2 c3 ; 加密变换: ci=zimi (i=1,2,3,); 解密变换: mi=zici (i=1,2,3,).,2.1 流密码一般模型,15,第2章 流密码,2.1 流密码一般模型 2.2 线性反馈移位寄存器序列 2.3 线性复杂度及B-M算法 2.4 非线性序列生成器 2.5 流密码算法,16,2.2 线
6、性反馈移位寄存器序列,伪随机序列 考虑二元序列: a=ai=a0a1a2a3 . 周期序列,定义2.1 设a= (a0, a1,ai,)是一个二元序列，若存在正整数N和非负整数m，使得ai+N=ai对于任意i m成立，则称二元序列a是终归周期序列。如果m=0，则称序列a是严格周期序列，简称周期序列。而满足ai+Nai (i m)的最小正整数N被称为序列a的周期。,17,2.2 线性反馈移位寄存器序列,定义2.2 设a= (a0, a1,ai,)是一个周期为N的二元序列，在一个周期内连续出现的最多的符号“0”（或1）的串，称为0（或1）的一个游程。在一个游程中，0（或1）的个数称为该游程的长度。
7、（讨论：该定义有否歧义？）,伪随机序列 序列的游程,例: 在序列 k=ki=001110100000111100中, 有 长为1的0游程一个; 长为4的0游程一个; 长为5的0游程一个; 长为1的1游程一个; 长为3的1游程一个; 长为4的1游程一个.,18,2.2 线性反馈移位寄存器序列,定义2.3 设a=(a0,a1,aN1)和b=(b0,b1,bN1)是两个周期为N的二元周期序列，其相关函数定义为 特别地，如果a=b，则Ra,a()被称为自相关函数，其中当 =0，Ra,a(0)被称为同相自相关函数，而当0， Ra,a()被称为异相自相关函数。,伪随机序列 序列的相关函数,19,2.2 线
8、性反馈移位寄存器序列,例 2.1 已知序列a=0101110 0101110，则 a是周期为7的周期序列; a一共有4个游程：00,1,0,111，长度分别为2,1,1,3； 求a的自相关函数: a=0101110, a =1011100, Ra,a(0)=(-1)0+0+(-1)1+1+(-1)0+0 +(-1)1+1 +(-1)1+1 +(-1)1+1 +(-1)0+0=7, a=0101110, Ta =1011100, Ra,a(1)=(-1)0+1+(-1)1+0+(-1)0+1 +(-1)1+1 +(-1)1+1 +(-1)1+0 +(-1)0+0=-1, a=0101110, T
9、2a =0111001, Ra,a(2)=(-1)0+0+(-1)1+1+(-1)0+1 +(-1)1+1 +(-1)1+0 +(-1)1+0 +(-1)0+1=-1, Ra,a(3)= Ra,a(4)= Ra,a(5)= Ra,a(6)=-1.,20,伪随机序列,哥伦布(Golomb, 1955)随性假设,(G1)：在一个周期内，0与1出现的个数至多相差1。也即，如果N为偶数，则在一个周期内0与1的数目各占N/2；如果N为奇数，则在一个周期内0的数目为(N+1)/2或者(N-1)/2，相应地1的数目为(N-1)/2或者(N+1)/2。 (G2)：在一个周期内，长度为i 的游程个数占游程总数的
10、1/2i，i=1,2, 。且在长度为i的游程中，0的游程与1的游程数目相等或至多相差一个。 (G3)：序列的异相自相关函数是一个常数。,满足上述三个条件的序列称为拟噪声序列, 或伪噪声序列(pseudo noise sequence), 简记为: PN序列. PN序列在CDMA,通信同步, 导航, 雷达测距等领域有重要应用.,21,Solomon W. Golomb: Shimonoseki, Japan, October 10-14, 2005,22,伪随机序列,密钥序列k=ki=k0k1k2k3 .满足的条件 G1,G2,G3和以下三个条件：,(C1) 周期p要长. 如p1050. (C2
11、) 生成容易. (C3)具有不可预测性(unpredictability): 当密钥序列k的 任何部分泄露时,要分析整个密钥序列, 在计算上是不可行的.,C3决定了密码的强度, 是序列密码理论的核心. 主要研究问题: 线性复杂度, 相关免疫性,不可预测性等.,23,反馈移位寄存器(FSR: Feedback Shift Register) n个寄存器: 从右至左依次称为第1,2,n 级 反馈函数 f(x0, x1,xn-1): GF(2)nGF(2). 工作原理: 当一个时钟脉冲来到时, 第i 级寄存器的内容传送给第i-1级寄存器(i=2,3,n),第1 级寄存器的内容为反馈移位寄存器的输出.
12、 反馈函数 f(x0, x1,xn-1)的值传送给第n级寄存器. FSR的输出序列: a0, a1,a2,an, 称为反馈移位寄存器序列(FSR序列).,伪随机序列,24,在任意时刻t, 第1至n级寄存器的内容 st =(at, at+1,at+n-1)GF(2)n 称为FSR在时刻t 的状态(state). s0 =(a0, a1,an-1) 称为FSR的初始状态. 在时刻t+1 的状态为: st+1=(at+1, at+2,at+n), at+n =f(at, at+1,at+n-1). 共有2n个状态. 反馈函数 f(x1, x2,xn)是n个变量的布尔函数(Boolean functi
13、on).,反馈移位寄存器(FSR),25,例2.2 设有限域GF(2)上的3级FSR的反馈函数为: f(x1, x2, x3)=x1x2x3 初始状态为s0=(1,0,1). 求FSR序列. 解: 反馈移位寄存器序列: a =1011; 周期q=4.,反馈移位寄存器(FSR),26,如果反馈函数 f(x1, x2,xn)是n个变量的线性函数: f(x1, x2,xn) =c1xn+c2xn-1+cnx1 (ci0,1) 则称为线性反馈移位寄存器(LFSR: linear feedback shift register). 输出的序列称为线性反馈移位寄存器序列, 记为LFSR序列。 LFSR序列
14、a= (a0, a1,an-1,) 满足递推关系式:,线性反馈移位寄存器(LFSR),27,反馈函数: f(x1, x2,xn) =c1xn+c2xn-1+cnx1 (ci0,1) 如果cn=0，则称LFSR是退化的；否则称LFSR是非退化的。 把多项式： f(x)=1+c1x+c2x2+cnxn 称为LFSR的特征多项式(characteristic polynomial), 或级连多项式、或生成多项式。,线性反馈移位寄存器(LFSR),28,例2.3 已知如图所示的3级LFSR. 特征多项式为： f(x)=1+x2+x3 LFSR序列a=(a0, a1,an-1,) 满足递推关系式: an
15、=an-2+an-3. 如果设初始状态为: (0,0,1) 即a0=0,a1=0,a2=1， 输出序列为: 0010111 周期为7.,线性反馈移位寄存器(LFSR),29,例2.3 已知如图所示的3级LFSR. LFSR序列a= 0010111的状态转移图,线性反馈移位寄存器(LFSR),30,线性反馈移位寄存器(LFSR),LFSR序列的性质,定理2.1 任何n级FSR序列都是终归周期序列，且其周期至多是2n 1 。,定义2.4 周期为2n 1的n级线性LFSR序列称为最大长度(Maximal length)序列，简称为m-序列。,m-序列,定理2.2 a是周期为2n 1的m-序列的充分必
16、要条件是其特征多项式f(x)为n阶本原多项式。,31,m-序列,m-序列的个数,定理2.3 设f(x)是GF(2)上的n次本原多项式,则对任意非0的初始状态,由f(x)生成的m-序列是循环等价(cyclically equivalent)的. 即: 一个n次本原多项式只能生成一个m-序列.,定理2.4 二元域GF(2)上的n级m序列共有(2n-1)/n个.,32,m-序列,例2.3 3级LFSR的特征多项式为: f(x)=1+x2+x3,初始状态为: (1,0,1), 输出序列为: a=1011100.,初始状态为: (0,0,1), 输出序列为: a=0010111,33,m-序列,m-序列的伪随机性,定理2.5 设a 是一个n级m序列，周期为2n1，则 (1) 在一个周期内，0、1出现的次数分别为2n-11和
