第四章 序列密码.ppt

第四章 序列密码 函f(a1, a2, a3, …, an)称为反馈函数，其中f(a1,a2,a3,…, an)是n元布尔函数，即n个变元a1, a2, a3, …, an可以独立地取0和1这两个可能的值.最后的函数值也为0或1。 反馈函数:b1+b3 反馈函数:b1+b3 反馈函数:b1+b2+b3+b4 试题 设g(x)=x^4+x^2+1，g(x)为GF（2）上的多项式，以其为连接多项式组成线性移位寄存器。画出逻辑框图。设法遍历其所有状态，并写出其状态变迁及相应的输出序列。 解答  破解流密码—插入法 插入法:要求能截获密文并可在明文中插入 * * 4.1 序列密码的基本概念 4.2 密钥流与密钥生成器 4.3 线性反馈移位寄存器序列 4.4 线性移位寄存器的一元多项式表示 4.5 随机性概念与M序列的伪随机性 序列密码的加密和解密就是用一个随机序列与明文序列叠加产生密文，用同一个随机序列与密文序列叠加来恢复明文。 若设明文为m，密钥为k，加密后的密文为c，则加密变换为：c＝m ? k，解密变换：m＝c? k，其中m，k，c是0、1随机序列，?表示模2加法运算。 4.1 序列密码的基本概念 图4.1 序列密码的加密和解密 序列密码的安全性主要依赖于密钥序列 当密钥序列是均匀分布的离散无记忆信源产生的随机序列时，相应的序列密码就是“一次一密”密码。 4.2 密钥流与密钥生成器 一般地，序列密码中对密钥流有如下要求： （1）极大的周期。因为随机序列是非周期的，而按任何算法产生的序列都是周期的，因此应要求密钥流具有尽可能大的周期。 （2）良好的统计特性。随机序列有均匀的游程分布。游程指序列中相同符号的连续段，其前后均为异种符号。 如 ……0 111 0000 10…… 中3个段分别为长为3的1游程、长为4的0游程、长为1的1游程。 一般要求其在一周期内满足：同样长度的0游程和1游程的个数相等，或近似相等。 （3）不能用级数较小的线性移位寄存器近似代替，即要有很高的线性复杂度。 （4）用统计方法由密钥序列k0 k1 k2 … ki …提取密钥生成器结构或种子密钥的足够信息在计算上是不可能的。 在密钥流生成器设计中，在考虑安全性要求的前提下还应考虑以下两个因素： （1）密钥K易于分配、保管、更换； （2）易于实现、速度快。 目前密钥流生成器大都是基于移位寄存器的，这种基于移位寄存器的密钥流序列称为移位寄存器序列。 4.3 线性反馈移位寄存器序列 移位寄存器是序列密码产生密钥序列的一个主要组成部分。 GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1 a2 ... an)组成，如图4.3所示。 图4.3 GF(2)上的n级反馈移位寄存器 每一个存储器称为移位寄存器的一级。 在任一时刻，这些级的内容构成该反馈移位寄存器的状态。 表4.1 三级反馈移位寄存器的输出状态表 图4.4 一个3级反馈移位寄存器 这个反馈移位寄存器的状态对应于一个GF(2)上的 n维向量，共有2n种可能的状态。 每一时刻的状态可用n长序列a1, a2, a3, …, an或n维行向量(a1, a2, a3, …, an)表示，其中ai是第i级存储器的内容。 每一级存储器ai都将其内容向下一级ai－1传递，并根据存储器当前状态计算f(a1, a2, a3, …, an)作为an下一时间的内容。 表4.1 三级反馈移位寄存器的输出状态表 图4.4 一个3级反馈移位寄存器 三级反馈移位寄存器，其初始状态为(a1,a2,a3)＝(1,0,1)， 输出可由表4.1求出，其输出序列为10111011101…，周期为4。 设一个GF(2)上的5阶反馈移位寄存器： 初始状态 s0 =(1,0,0,1,1). 反馈函数 0 1 1 0 0 1 输出 0,1,0,0,1 1,0,1,0,0 1,1,0,1,0 0,1,1,0,1 0,0,1,1,0 1,0,0,1,1 状态 5 4 3 2 1 0 时刻 反馈移位寄存器输出序列： 1001101001000010101110110001111100110… s31 输出是一个周期序列：周期为31=25-1 如果移位寄存器的反馈函数f(a1, a2, …, an)是a1,