资源描述:
《应用密码学 教学课件 作者 林东岱 曹天杰第四章 序列密码.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第四章序列密码曹天杰中国矿业大学计算机学院4.1序列密码的基本概念4.2密钥流与密钥生成器4.3线性反馈移位寄存器序列4.4线性移位寄存器的一元多项式表示4.5随机性概念与M序列的伪随机性序列密码的加密和解密就是用一个随机序列与明文序列叠加产生密文,用同一个随机序列与密文序列叠加来恢复明文。若设明文为m,密钥为k,加密后的密文为c,则加密变换为:c=mk,解密变换:m=ck,其中m,k,c是0、1随机序列,表示模2加法运算。4.1序列密码的基本概念序列密码的安全性主要依赖于密钥序列,当密钥序列是均匀分布的离散无记忆信源产生的随机序列时,相应的序列密码就是“一次一密
2、”密码。如图4.1序列密码的加密和解密示意图。图4.1序列密码的加密和解密同步序列密码定义:如果密钥序列产生算法与明文无关,则所产生的密钥序列也与明文无关,我们称这类序列密码为同步序列密码。对于同步序列密码,只要通信双方的密钥序列产生器具有相同的种子密钥和相同的初始状态,就能产生相同的密钥序列。同步序列密码的一个优点是没有错误传播,当通信中某些密文字符产生了错误,只影响相应字符的解密,不影响其他字符。自同步序列密码定义:如果密钥序列产生算法与明文(密文)相关,则所产生的密钥序列与明文(密文)相关,我们称这类序列密码为自同步序列密码。设密钥序列产生器具有n位存储,则其密文
3、位ci不仅与当前的明文位mi相关,而且与后面的n个明文位mi+1,mi+2,mi+3,…,mi+n相关。假设在通信过程中密文位ci发生了错误,则导致明文位mi错误,而且还导致后n个明文位mi+1,mi+2,mi+3,…,mi+n也发生错误,造成错误传播。4.2密钥流与密钥生成器一般地,序列密码中对密钥流有如下要求:(1)极大的周期。因为随机序列是非周期的,而按任何算法产生的序列都是周期的,因此应要求密钥流具有尽可能大的周期。(2)良好的统计特性。随机序列有均匀的游程分布。游程指序列中相同符号的连续段,其前后均为异种符号。连续段的比特位数称为该游程的长度,如……01110
4、00010……中3个段分别为长为3的1游程、长为4的0游程、长为1的1游程。一般对周期为2n的序列,可要求其在一周期内满足:同样长度的0游程和1游程的个数相等,或近似相等。(3)不能用级数较小的线性移位寄存器近似代替,即要有很高的线性复杂度。(4)用统计方法由密钥序列k0k1k2…ki…提取密钥生成器结构或种子密钥的足够信息在计算上是不可能的。因为按任何确定性算法产生的序列都是周期性的。若密钥周期P很短,则从下面两组密文:m1k1,…,mLkL和mP+1kP+1,…,mP+LkP+L,(相加得m1mP+1,…,mLmP+L)以及语言冗余度,就可获得—些关于明
5、文的信息,因而周期长是必要的;良好的随机统计特性是为了更好地掩盖明文。高线性复杂度可用于防止从部分密钥序列通过线性关系简单推出整个密钥流序列。若知道一些明密文对(mi,ci),(mi+1,ci+1),…,便可简单地确定部分密钥序列ki,ki+1,...。因此,安全的密码系统应能抵抗从部分密钥ki,ki+1,...确定整个密钥序列的攻击。在密钥流生成器设计中,在考虑安全性要求的前提下还应考虑以下两个因素:(1)密钥K易于分配、保管、更换;(2)易于实现、速度快。目前密钥流生成器大都是基于移位寄存器的,这种基于移位寄存器的密钥流序列称为移位寄存器序列。通常采用的方法是,由线
6、性移位寄存器(LFSR)和一个非线性组合函数即布尔函数组合,构成一个密钥流生成器,如图4.2所示的密钥流生成器。4.2密码流生成器(a)由一个线性移位寄存器和一个滤波器构成。(b)由多个线性移位寄存器和一个组合器构成。通常将这类生成器分解成两部分,其中线性移位寄存器部分称为驱动部分,另一部分称为非线性组合部分。其工作原理都是将驱动部分即线性移位寄存器在j时刻的状态变量x作为一组值输入非线性组合部分的f,将f(x)作为当前时刻的kj。驱动部分负责提供非线性组合部分使用的周期大、统计性能好的序列,而非线性组合部分以各时刻移位寄存器的状态组合出密钥序列j时刻的值kj,驱动部分
7、负责状态转移。4.3线性反馈移位寄存器序列移位寄存器是序列密码产生密钥序列的一个主要组成部分。GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1a2...an)组成,如图4.3所示。图4.3GF(2)上的n级反馈移位寄存器每一个存储器称为移位寄存器的一级。在任一时刻,这些级的内容构成该反馈移位寄存器的状态。这个反馈移位寄存器的状态对应于一个GF(2)上的n维向量,共有2n种可能的状态。每一时刻的状态可用n长序列a1,a2,a3,…,an或n维行向量(a1,a2,a3,…,an)表示,其中ai是第i级存储器的内容。每一