流密码详解

1第2章流密码李向东中原工学院计算机学院[e-mail]2011.9-2012.12第2章流密码2.1流密码一般模型2.2线性反馈移位寄存器序列2.3线性复杂度及B-M算法2.4非线性序列生成器2.5流密码算法32.1流密码一般模型实用密码体制的分类......流密码私钥密码分组密码密码体制基于大数分解困难问题公钥密码基于离散对数困难问题42.1流密码一般模型流密码(streamcipher)(序列密码)体制模型明文序列:m=m1m2m3…;密钥序列:z=z1z2z3…;密文序列:c=c1c2c3…;加密变换:ci=E(zi,mi)(i=1,2,3,…);解密变换:mi=D(zi,ci)(i=1,2,3,…).5课堂讨论：加密函数和解密函数都用异或运算，行不行？什么样的加解密算法是高效、安全的？Why？实用的流密码方案中，加解密算法是什么？6流密码原理框图信道ciD(zi,ci)cimiE(zi,mi)mi密钥流生成器zizi密钥流生成器kk安全信道2.1流密码一般模型7流密码体制的安全性当流钥序列是具有均匀分布的离散无记忆随机序列时,在理论上是不可破译的.实用的困难性真正的具有均匀分布的随机序列是不可能重复产生的.密钥序列长(至少与明文序列一样长),其管理(存储、分配)难.设计流密码体制的关键问题设计产生密钥序列的方法.2.1流密码一般模型8序列密码的分类同步流密码(SSC:synchronousstreamcipher)产生密钥序列的算法与明文、密文无关.自同步流密码(SSSC:self-synchronousstreamcipher)产生密钥序列的算法与以前的密文有关.2.1流密码一般模型9同步流密码(SSC:synchronousstreamcipher)只要通信双方的密钥序列产生器具有相同的“种子序列”和相同的“初始状态”,就能产生相同的密钥序列.通信双方必须保持精确同步,才能正确解密.容易检测插入、删除、重播等主动攻击.没有差错传播.讨论：如何对SSC的这种“同步”性质进行形式化描述？2.1流密码一般模型10同步流密码(SSC:synchronousstreamcipher)产生密钥序列的算法与明文、密文无关.ciE(zi,mi)mizi密钥流生成器k10(,),(,),(,).:::()::iiiiiiiiFkzfkcEzmkFf密钥流生成器的内部状态密钥流生成器的初始状态种子初始密钥状态转移函数密钥流生成函数2.1流密码一般模型11自同步流密码(SSSC:self-synchronousstreamcipher)产生密钥序列的算法与以前的密文有关.1111(,,...,,)(,,...,,)(,),(,).::iiiiliiiliiiiiFcckFmmkzfkcEzmFf状态转移函数密钥流生成函数E(zi,mi)mizi密钥流生成器kci2.1流密码一般模型12自同步流密码(SSSC)密钥流生成器是一种有记忆变换器密钥流与明文符号有关：i时刻的密文不仅取决于i时刻的明文，而且与i时刻之前的l个明文符号有关具有有限的差错传播具有自同步能力把明文每个字符扩散在密文多个字符中,强化了抗统计分析的能力问：SSSC是如何自同步的？请email回应。2.1流密码一般模型13二元加法序列密码明文序列:m=m1m2m3…;密钥序列:z=z1z2z3…;密文序列:c=c1c2c3…;加密变换:ci=zimi(i=1,2,3,…);解密变换:mi=zici(i=1,2,3,…).2.1流密码一般模型14第2章流密码2.1流密码一般模型2.2线性反馈移位寄存器序列2.3线性复杂度及B-M算法2.4非线性序列生成器2.5流密码算法152.2线性反馈移位寄存器序列伪随机序列考虑二元序列:a={ai}=a0a1a2a3….周期序列定义2.1设a=(a0,a1,…,ai,…)是一个二元序列，若存在正整数N和非负整数m，使得ai+N=ai对于任意im成立，则称二元序列a是终归周期序列。如果m=0，则称序列a是严格周期序列，简称周期序列。而满足ai+N＝ai(im)的最小正整数N被称为序列a的周期。162.2线性反馈移位寄存器序列定义2.2设a=(a0,a1,…,ai,…)是一个周期为N的二元序列，在一个周期内连续出现的最多的符号“0”（或1）的串，称为0（或1）的一个游程。在一个游程中，0（或1）的个数称为该游程的长度。（讨论：该定义有否歧义？）伪随机序列序列的游程例:在序列k={ki}=001110100000111100中,有长为1的0游程一个;长为4的0游程一个;长为5的0游程一个;长为1的1游程一个;长为3的1游程一个;长为4的1游程一个.172.2线性反馈移位寄存器序列定义2.3设a=(a0,a1,…,aN1)和b=(b0,b1,…,bN1)是两个周期为N的二元周期序列，其相关函数定义为特别地，如果a=b，则Ra,a()被称为自相关函数，其中当=0，Ra,a(0)被称为同相自相关函数，而当0，Ra,a()被称为异相自相关函数。伪随机序列序列的相关函数NNRNibabaii,)1()(10,182.2线性反馈移位寄存器序列例2.1已知序列a=01011100101110…，则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,T2a=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.19伪随机序列哥伦布(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的游程个数占游程总数的1/2i，i=1,2,…。且在长度为i的游程中，0的游程与1的游程数目相等或至多相差一个。(G3)：序列的异相自相关函数是一个常数。满足上述三个条件的序列称为拟噪声序列,或伪噪声序列(pseudonoisesequence),简记为:PN序列.PN序列在CDMA,通信同步,导航,雷达测距等领域有重要应用.20SolomonW.Golomb:Shimonoseki,Japan,October10-14,200521伪随机序列密钥序列k={ki}=k0k1k2k3….满足的条件G1,G2,G3和以下三个条件：(C1)周期p要长.如p1050.(C2)生成容易.(C3)具有不可预测性(unpredictability):当密钥序列k的任何部分泄露时,要分析整个密钥序列,在计算上是不可行的.C3决定了密码的强度,是序列密码理论的核心.主要研究问题:线性复杂度,相关免疫性,不可预测性等.22an1…a1a0f(x0,x1,…,xn1)反馈移位寄存器(FSR:FeedbackShiftRegister)n个寄存器:从右至左依次称为第1,2,…,n级反馈函数f(x0,x1,…,xn-1):GF(2)nGF(2).工作原理:当一个时钟脉冲来到时,第i级寄存器的内容传送给第i-1级寄存器(i=2,3,…,n),第1级寄存器的内容为反馈移位寄存器的输出.反馈函数f(x0,x1,…,xn-1)的值传送给第n级寄存器.FSR的输出序列:a0,a1,a2,…,an,…称为反馈移位寄存器序列(FSR序列).伪随机序列23在任意时刻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个变量的布尔函数(Booleanfunction).反馈移位寄存器(FSR)24例2.2设有限域GF(2)上的3级FSR的反馈函数为:f(x1,x2,x3)=x1x2x3初始状态为s0=(1,0,1).求FSR序列.解:反馈移位寄存器序列:a=1011…;周期q=4.反馈移位寄存器(FSR)时刻状态输出3级2级1级01011111002111130111410115110025如果反馈函数f(x1,x2,…,xn)是n个变量的线性函数:f(x1,x2,…,xn)=c1xn+c2xn-1+…+cnx1(ci{0,1})则称为线性反馈移位寄存器(LFSR:linearfeedbackshiftregister).输出的序列称为线性反馈移位寄存器序列,记为LFSR序列。LFSR序列a=(a0,a1,…,an-1,…)满足递推关系式:线性反馈移位寄存器(LFSR))(2211nkacacacaknknknknan1…a1a0niiniac1cncn-1c126反馈函数:f(x1,x2,…,xn)=c1xn+c2xn-1+…+cnx1(ci{0,1})如果cn=0，则称LFSR是退化的；否则称LFSR是非退化的。把多项式：f(x)=1+c1x+c2x2+…+cnxn称为LFSR的特征多项式(characteristicpolynomial),或级连多项式、或生成多项式。线性反馈移位寄存器(LFSR)27例2.3已知如图所示的3级LFSR.特征多项式为：f(x)=1+x2+x3LFSR序列a=(a0,a1,…,an-1,…)满足递推关系式:an=an-2+an-3.如果设初始状态为:(0,0,1)即a0=0,a1=0,a2=1，输出序列为:0010111周期为7.线性反馈移位寄存器(LFSR)an1an2an3时刻状态输出3级2级1级0100010100210113110041111501116001128例2.3已知如图所示的3级LFSR.LFSR序列a=0010111的状态转移图线性反馈移位寄存器(LFSR)时刻状态输出3级2级1级0100010100210113110041111501116001100101010101111110011029线性反馈移位寄存器(LFSR)LFSR序列的性质定理2.1任何n级FSR序列都是终归周期序列，且其周期至多是2n1。定义2.4周期为2n1的n级线性LFSR序列称为最大长度(Maximallength)序列，简称为m-序列。m-序列定理2.2a是周期为2n1的m-序列的充分必要条件是其特征多项式f(x)为n阶本原多项式。30m-序列m-序列的个数定理2.3设f(x)是GF(2)上的n次本原多项式,则对任意非0的初始状态,由f(x)生成的m-序列是循环等价(cyclicallyequivalent)的.即:一个n次本原多项式只能生成一个m-序列.定理2.4二元域GF(2)上的n级m序列共有(2n-1)/n个.31m-序列例2.33级LFSR的特征多项式为:f(x)=1+x2+x300101010