流密码详解课件

第第2章章 流密码流密码李向东 中原工学院计算机学院 2011.9-2012.11第2章 流密码李向东 1 第第2章章 流密码流密码n2.1 流密码一般模型n2.2 线性反馈移位寄存器序列n2.3 线性复杂度及B-M算法n2.4 非线性序列生成器 n2.5 流密码算法2 第2章 流密码2.1 流密码一般模型22.1 流密码一般模型流密码一般模型n实用密码体制的分类32.1 流密码一般模型实用密码体制的分类32.1 流密码一般模型流密码一般模型n流密码流密码(stream cipher)(序列密码序列密码)体制模体制模型型明文序列明文序列:m=m1 m2 m3;密钥序列密钥序列:z=z1 z2 z3;密文序列密文序列:c=c1c2 c3;加密变换加密变换:ci=E(zi,mi)(i=1,2,3,);解密变换解密变换:mi=D(zi,ci)(i=1,2,3,).42.1 流密码一般模型流密码(stream cipher课堂讨论：n加密函数和解密函数都用异或运算，行不行？n什么样的加解密算法是高效、安全的？Why？n实用的流密码方案中，加解密算法是什么？5课堂讨论：加密函数和解密函数都用异或运算，行不行？5n流密码原理框图流密码原理框图信道信道ciD(zi,ci)cimiE(zi,mi)mi 密钥流 生成器zizi 密钥流 生成器 k k安全信道安全信道2.1 流密码一般模型流密码一般模型6流密码原理框图信道ciD(zi,ci)cimiE(zi,min流密码体制的安全性 当流钥序列是具有均匀分布的离散无记忆随机序列时,在理论上是不可破译的.n实用的困难性q真正的具有均匀分布的随机序列是不可能重复产生的.q密钥序列长(至少与明文序列一样长),其管理(存储、分配)难.n设计流密码体制的关键问题 设计产生密钥序列的方法.2.1 流密码一般模型流密码一般模型7流密码体制的安全性 2.1 流密码一般模型7n序列密码的分类序列密码的分类q同步流密码同步流密码(SSC:synchronous stream cipher)n产生密钥序列的算法与明文、密文无关产生密钥序列的算法与明文、密文无关.q自同步流密码自同步流密码(SSSC:self-synchronous stream cipher)n产生密钥序列的算法与以前的密文有关产生密钥序列的算法与以前的密文有关.2.1 流密码一般模型流密码一般模型8序列密码的分类2.1 流密码一般模型8q同步流密码同步流密码(SSC:synchronous stream cipher)n只要通信双方的密钥序列产生器具有相同的只要通信双方的密钥序列产生器具有相同的“种种子序列子序列”和相同的和相同的“初始状态初始状态”,就能产生相同就能产生相同的密钥序列的密钥序列.n通信双方必须保持精确同步通信双方必须保持精确同步,才能正确解密才能正确解密.n容易检测插入、删除、重播等主动攻击容易检测插入、删除、重播等主动攻击.n没有差错传播没有差错传播.q讨论：如何对讨论：如何对SSC的这种的这种“同步同步”性质进行性质进行形式化描述？形式化描述？2.1 流密码一般模型流密码一般模型9同步流密码(SSC:synchronous stream q同步流密码同步流密码(SSC:synchronous stream cipher)产生密钥序列的算法与明文、密文无关产生密钥序列的算法与明文、密文无关.ciE(zi,mi)mizi 密钥流生成器k2.1 流密码一般模型流密码一般模型10同步流密码(SSC:synchronous stream q自同步流密码自同步流密码(SSSC:self-synchronous stream cipher)产生密钥序列的算法与以前的密文有关产生密钥序列的算法与以前的密文有关.E(zi,mi)mizi 密钥流生成器kci2.1 流密码一般模型流密码一般模型11自同步流密码(SSSC:self-synchronous q自同步流密码自同步流密码(SSSC)n密钥流生成器是一种有记忆变换器密钥流生成器是一种有记忆变换器n密钥流与明文符号有关：密钥流与明文符号有关：i 时刻的密文不仅取决于时刻的密文不仅取决于i 时刻的明文，而且与时刻的明文，而且与i 时刻时刻之前的之前的l个明文符号有关个明文符号有关n具有有限的差错传播具有有限的差错传播n具有自同步能力具有自同步能力n把明文每个字符扩散在密文多个字符中把明文每个字符扩散在密文多个字符中,强化了抗统强化了抗统计分析的能力计分析的能力q问：问：SSSC是如何自同步的？请是如何自同步的？请email回应。回应。2.1 流密码一般模型流密码一般模型12自同步流密码(SSSC)2.1 流密码一般模型12n二元加法序列密码二元加法序列密码明文序列明文序列:m=m1 m2 m3;密钥序列密钥序列:z=z1 z2 z3;密文序列密文序列:c=c1 c2 c3;加密变换加密变换:ci=zi mi (i=1,2,3,);解密变换解密变换:mi=zi ci (i=1,2,3,).2.1 流密码一般模型流密码一般模型13二元加法序列密码明文序列:m=m1 m2 m3;第第2章章 流密码流密码n2.1 流密码一般模型n2.2 线性反馈移位寄存器序列n2.3 线性复杂度及B-M算法n2.4 非线性序列生成器 n2.5 流密码算法14 第2章 流密码2.1 流密码一般模型142.2 线性反馈移位寄存器序列线性反馈移位寄存器序列n伪随机序列伪随机序列 考虑二元序列考虑二元序列:a=ai=a0a1a2a3.q周期序列周期序列定义定义2.1 设a=(a0,a1,ai,)是一个二元序列，若存在正整数N和非负整数m，使得ai+N=ai对于任意i m成立，则称二元序列a是终归周期序列。如果m=0，则称序列a是严格周期序列，简称周期序列。而满足ai+Nai(i m)的最小正整数N被称为序列a的周期。152.2 线性反馈移位寄存器序列伪随机序列定义2.1 设a=2.2 线性反馈移位寄存器序列线性反馈移位寄存器序列定义定义2.2 设a=(a0,a1,ai,)是一个周期为N的二元序列，在一个周期内连续出现的最多的符号“0”（或1）的串，称为0（或1）的一个游程。在一个游程中，0（或1）的个数称为该游程的长度。（讨论：该定义有否歧义？）n伪随机序列伪随机序列q序列的游程序列的游程例例:在序列在序列 k=ki=001110100000111100中中,有有 长为长为1的的0游程一个游程一个;长为长为4的的0游程一个游程一个;长为长为5的的0游程一个游程一个;长为长为1的的1游程一个游程一个;长为长为3的的1游游程一个程一个;长为长为4的的1游程一个游程一个.162.2 线性反馈移位寄存器序列定义2.2 设a=(a02.2 线性反馈移位寄存器序列线性反馈移位寄存器序列定义定义2.3 设a=(a0,a1,aN1)和b=(b0,b1,bN1)是两个周期为N的二元周期序列，其相关函数定义为特别地，如果a=b，则Ra,a()被称为自相关函数，其中当=0，Ra,a(0)被称为同相自相关函数，而当0，Ra,a()被称为异相自相关函数。n伪随机序列伪随机序列q序列的相关函数序列的相关函数172.2 线性反馈移位寄存器序列定义2.3 设a=(a0,2.2 线性反馈移位寄存器序列线性反馈移位寄存器序列q例例 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,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.182.2 线性反馈移位寄存器序列例 2.1 已知序列a=0伪随机序列伪随机序列q哥伦布哥伦布(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)：序列的异相自相关函数是一个常数。：序列的异相自相关函数是一个常数。q满足上述三个条件的序列称为满足上述三个条件的序列称为拟噪声序列拟噪声序列,或或伪噪声序列伪噪声序列(pseudo noise sequence),简记为简记为:PN序列序列.qPN序列在序列在CDMA,通信同步通信同步,导航导航,雷达测距等雷达测距等领域有重要应用领域有重要应用.19伪随机序列哥伦布(Golomb,1955)随性假设 Solomon W.Golomb:Shimonoseki,Japan,October 10-14,200520Solomon W.Golomb:Shimonoseki伪随机序列伪随机序列q密钥序列密钥序列k=ki=k0k1k2k3.满足的条件满足的条件 G1,G2,G3和以下三个条件：和以下三个条件：(C1)周期周期p要长要长.如如p1050.(C2)生成容易生成容易.(C3)具有不可预测性具有不可预测性(unpredictability):当密钥序列当密钥序列k的的 任何部分泄露时任何部分泄露时,要分析要分析整个密钥序列整个密钥序列,在计算上是不可行的在计算上是不可行的.nC3决定了密码的强度决定了密码的强度,是序列密码理论是序列密码理论的核心的核心.n主要研究问题主要研究问题:线性复杂度线性复杂度,相关免疫性相关免疫性,不可预测性等不可预测性等.21伪随机序列密钥序列k=ki=k0k1k2k3.满足的an1a1a0f(x0,x1,xn1)n反馈移位寄存器反馈移位寄存器(FSR:Feedback Shift Register)qn个寄存器个寄存器:从右至左依次称为第从右至左依次称为第1,2,n 级级q反馈函数反馈函数 f(x0,x1,xn-1):GF(2)nGF(2).q工作原理工作原理:当一个时钟脉冲来到时当一个时钟脉冲来到时,第第i 级寄存器的内容传级寄存器的内容传送给第送给第i-1级寄存器级寄存器(i=2,3,n),第第1 级寄存器的内容为反级寄存器的内容为反馈移位寄存器的输出馈移位寄存器的输出.反馈函数反馈函数 f(x0,x1,xn-1)的值传送的值传送给第给第n级寄存器级寄存器.qFSR的输出序列的输出序列:a0,a1,a2,an,称为称为反馈移位寄存器反馈移位寄存器序列序列(FSR序列序列).伪随机序列伪随机序列22an1a1a0f(x0,x1,xn1)反馈移位q在任意时刻在任意时刻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).q共有共有2n个状态个状态.q反馈函数反馈函数 f(x1,x2,xn)是是n个变量的个变量的布尔函数布尔函数(Boolean function).反馈移位寄存器反馈移位寄存器(FSR)23在任意时刻t,第1至n级寄存器的内容反馈移位寄存器(FSRn例例2.2 设有限域设有限域GF(2)上的上的3级级FSR的反馈函数为的反馈函数为:f(x1,x2,x3)=x1 x2 x3初始状态为初始状态为s0=(1,0,1).求求FSR序列序列.解解:反馈移位寄存器序列反馈移位寄存器序列:a=1011;周期周期q=4.反馈移位寄存器反馈移位寄存器(FSR)24例2.2 设有限域GF(2)上的3级FSR的反馈函数为:反q如果反馈函数如果反馈函数 f(x1,x2,xn)是是n个变量的线性函个变量的线性函数数:f(x1,x2,xn)=c1xn+c2xn-1+cnx1 (ci 0,1)则称为则称为线性反馈移位寄存器线性反馈移位寄存器(LFSR:linear feedback shift register).输出的序列称为输出的序列称为线性反线性反馈移位寄存器序列馈移位寄存器序列,记为记为LFSR序列。序列。qLFSR序列序列a=(a0,a1,an-1,)满足递推关系式满足递推关系式:线性反馈移位寄存器线性反馈移位寄存器(LFSR)an1a1a0cncn-1c125如果反馈函数 f(x1,x2,xn)是n个变量的线性函q反馈函数反馈函数:f(x1,x2,xn)=c1xn+c2xn-1+cnx1 (ci 0,1)q如果如果cn=0，则称，则称LFSR是是退化的退化的；否则称；否则称LFSR是是非退化的非退化的。q把多项式：把多项式：f(x)=1+c1x+c2x2+cnxn 称为称为LFSR的的特征多项式特征多项式(characteristic polynomial),或或级连多项式级连多项式、或、或生成多项式。生成多项式。线性反馈移位寄存器线性反馈移位寄存器(LFSR)26反馈函数:线性反馈移位寄存器(LFSR)26q例例2.3 已知如图所示的已知如图所示的3级级LFSR.特征多项式为：特征多项式为：f(x)=1+x2+x3 LFSR序列序列a=(a0,a1,an-1,)满足递推关系满足递推关系式式:an=an-2+an-3.如果设初始状态为如果设初始状态为:(0,0,1)即即a0=0,a1=0,a2=1，输出序列为输出序列为:0010111 周期为周期为7.线性反馈移位寄存器线性反馈移位寄存器(LFSR)an1an2an327例2.3 已知如图所示的3级LFSR.线性反馈移位寄存器q例例2.3 已知如图所示的已知如图所示的3级级LFSR.LFSR序列序列a=0010111的状态转移图的状态转移图线性反馈移位寄存器线性反馈移位寄存器(LFSR)00101010101111110011028例2.3 已知如图所示的3级LFSR.线性反馈移位寄存器线性反馈移位寄存器线性反馈移位寄存器(LFSR)qLFSR序列的性质序列的性质 定理2.1 任何任何n级级FSR序列都是终归序列都是终归周期序列，且其周期至多是周期序列，且其周期至多是2n 1。定义2.4 周期为周期为2n 1的的n级线性级线性LFSR序列称为序列称为最大长度最大长度(Maximal length)序序列列，简称为，简称为m-序列。序列。qm-序列序列 定理2.2 a是周期为是周期为2n 1的的m-序列的序列的充分必要条件充分必要条件是其特征多项式是其特征多项式f(x)为为n阶阶本原多项式。本原多项式。29线性反馈移位寄存器(LFSR)LFSR序列的性质 m-序列序列qm-序列的个数序列的个数 定理2.3 设设f(x)是是GF(2)上的上的n次本原多次本原多项式项式,则对任意非则对任意非0的初始状态的初始状态,由由f(x)生生成的成的m-序列是序列是循环等价循环等价(cyclically equivalent)的的.即即:一个一个n次本原多项式只能生成一个次本原多项式只能生成一个m-序列序列.定理2.4 二元域二元域GF(2)上的上的n级级m序列共序列共有有(2n-1)/n个个.30m-序列m-序列的个数 定理2.3 设f(xm-序列序列q例例2.3 3级级LFSR的特征多项式为的特征多项式为:f(x)=1+x2+x3 001010101011111100110初始状态为初始状态为:(1,0,1),输出序列为输出序列为:a=1011100.001010101011111100110初始状态为初始状态为:(0,0,1),输出序列为输出序列为:a=0010111 31m-序列例2.3 3级LFSR的特征多项式为:f(m-序列序列qm-序列的伪随机性序列的伪随机性 定理2.5 设设a 是一个是一个n级级m序列，周期为序列，周期为2n 1，则，则(1)在一个周期内，在一个周期内，0、1出现的次数分别为出现的次数分别为2n-1 1和和2n-1。(2)在一个周期内，总游程数为在一个周期内，总游程数为2n-1。其中，。其中，对对1 i n 2，长为，长为i的的0游程、游程、1游程各有游程各有2n-i-2个；长为个；长为n 1的的0游程游程1个，长为个，长为n的的1游程游程1个。个。(3)a 的自相关函数为的自相关函数为:32m-序列m-序列的伪随机性 定理2.5 设a 是一个n级mm-序列序列qm-序列的伪随机性序列的伪随机性 q例2.4 已知已知4级级m序列序列a=100010011010111,有有nn=4n7个个0,8个个1 n 游程总数为游程总数为8n长为长为1的的0游程游程2个个,长为长为1的的1游程游程2个个n长为长为2的的0游程游程1个个,长为长为2的的1游程游程1个个n长为长为3的的0游程游程1个个n长为长为4的的1游程游程1个个.33m-序列m-序列的伪随机性 例2.4 已知4级m序列a=m-序列序列nm-序列的密码学性质序列的密码学性质q(C1)周期长周期长:p=2n-1.如如n=166时时,p=1050 (9.353610465 1049).q(C2)生成容易生成容易:只要已知只要已知n次本原多项式次本原多项式,容易生成容易生成m序列序列.q(C3)m序列极不安全序列极不安全:只要泄露只要泄露2n位连续数字位连续数字,就可就可以完全确定反馈多项式的系数以完全确定反馈多项式的系数,从而得到从而得到m序列序列.已知已知ai,ai+1,ai+2n-1,由以下方程组可唯一解得由以下方程组可唯一解得 c0,c1,cn-1.34m-序列m-序列的密码学性质34 第第2章章 流密码流密码n2.1 流密码一般模型n2.2 线性反馈移位寄存器序列n2.3 线性复杂度及B-M算法n2.4 非线性序列生成器 n2.5 流密码算法35 第2章 流密码2.1 流密码一般模型352.3 序列的线性复杂度序列的线性复杂度给定一个长度为给定一个长度为N的二元密钥流序列的二元密钥流序列a,假定捕获了假定捕获了a的的一个长度为一个长度为m的部分的部分,不失一般性设为不失一般性设为(a0,a1,am 1),能否找到一个级数最短的能否找到一个级数最短的LFSR,生生成整个密钥流序列成整个密钥流序列a?n序列的密码分析问题序列的密码分析问题q问题一问题一:是否存在是否存在LFSR生成整个序列生成整个序列a？q问题二问题二:捕获序列捕获序列a多长的部分，才能找到多长的部分，才能找到LFSR生成整个序列生成整个序列a？怎样确保得到的？怎样确保得到的LFSR最短？最短？362.3 序列的线性复杂度给定一个长度为N的二元密钥流序列a2.3 序列的线性复杂度序列的线性复杂度n序列的序列的LFSRq设设a=(a0,a1,aN 1)是一个长度为是一个长度为N的序列，的序列，那么存在那么存在N级级LFSR，生成整个序列，生成整个序列a。q当当a是是LFSR序列时，序列时，存在存在存在存在着更短的着更短的LFSR生成生成整个序列整个序列q当当a是非是非LFSR序列时，序列时，也可能存在也可能存在也可能存在也可能存在着更短的着更短的LFSR生成整个序列生成整个序列a。aN1a1a0372.3 序列的线性复杂度序列的LFSR当a是LFSR序列时2.3 序列的线性复杂度序列的线性复杂度nB-M算法算法q设设a(N)=(a0,a1,aN 1)是一个长度为是一个长度为N的序列的序列,fN(x)是一个能生成是一个能生成a(N)且级数最小的且级数最小的LFSR的的特征多项式特征多项式,lN是是LFSR的级数的级数,则把则把 称为称为a(N)的的线性综合解线性综合解.qBerleKamp-Massey(1969)提出了求解提出了求解 的迭代算法的迭代算法.382.3 序列的线性复杂度B-M算法38B-M算法算法39B-M算法39B-M算法算法n例例2.5 设设a(10)=(0001101111),N=10,求其线性求其线性综合解综合解.解解:40B-M算法例2.5 设a(10)=(0001101111)B-M算法算法n例例2.5 设设a(10)=(0001101111),N=10,求其线求其线性综合解性综合解.解解:41B-M算法例2.5 设a(10)=(0001101111B-M算法算法n例例2.5 设设a(10)=(0001101111),N=10,求其线求其线性综合解性综合解.解解:42B-M算法例2.5 设a(10)=(0001101111B-M算法算法n例例2.5 设设a(10)=(0001101111),N=10,求其线求其线性综合解性综合解.解解:na(10)的线性综合解为的线性综合解为:f10(x)=1+x+x2+x5,l10=5.若取初值若取初值:a(0)=00011,则则f10(x)的的LFSR序序列列 a=0001101111 0011101000,周期为：周期为：25-1=31.43B-M算法例2.5 设a(10)=(0001101111B-M算法算法nB-M算法的性质算法的性质qB-M算法的时间复杂度为算法的时间复杂度为O(N2).定理定理定理定理2.62.6 给定长为N的序列a(N)=(a0,a1,aN1)，如果用B-M算法得到的线性综合解为(fN(x),lN)，则以fN(x)为生成多项式，产生的长为lN的LFSR就是生成序列a(N)的最短LFSR。定理定理定理定理2.7 2.7 给定长为N的序列a(N)=(a0,a1,aN1)，用B-M算法得到的线性综合解为(fN(x),lN)是唯一解的充要条件是2lNN。44B-M算法B-M算法的性质定理2.6 给定长为N的序列a(NB-M算法算法nB-M算法的性质算法的性质 定理2.8 设设a(N)=a0,a1,.,aN-1是是一一个个长长为为N的的序序列列,lN是是能能产产生生a(N)并并且且阶阶数数最最小小的的LFSR的的阶阶数数.则则当当2lN N时时,a(N)线线性性综综合合解解的的个个数数为为：45B-M算法B-M算法的性质 定理2.8 设a2.3 序列的线性复杂度序列的线性复杂度n序列的线性复杂度序列的线性复杂度 给定序列给定序列a，生成它的最短，生成它的最短LFSR的长度的长度lN就确定了。如果就确定了。如果2lN N，只需要捕获序，只需要捕获序列列a连续的连续的2lN个比特，就能得到它的唯一个比特，就能得到它的唯一解解(fN(x),lN)，以，以fN(x)为特征多项式的为特征多项式的lN 级级LFSR就可以生成整个序列就可以生成整个序列a。特别地，对于周期特别地，对于周期N很大，但很大，但lN 很小的很小的序列序列a，比如周期为，比如周期为2n 1的的n级级m-序列，序列，利用利用B-M算法，只要捕获序列算法，只要捕获序列a连续的连续的2lN个比特，即序列很小一部分，就可以重构个比特，即序列很小一部分，就可以重构整个序列。因此，整个序列。因此，lN 实际上度量了序列实际上度量了序列a的线性的不可预测性。的线性的不可预测性。462.3 序列的线性复杂度序列的线性复杂度 给定2.3 序列的线性复杂度序列的线性复杂度n序列的线性复杂度序列的线性复杂度 定义2.5 生成长为生成长为N的序列的序列a=(a0,a1,aN 1)的的LFSR的最短长度的最短长度lN被称为序列被称为序列a的的线性复杂度线性复杂度。qn阶阶m序列的线性复杂度序列的线性复杂度=n.472.3 序列的线性复杂度序列的线性复杂度 定 第第2章章 流密码流密码n2.1 流密码一般模型n2.2 线性反馈移位寄存器序列n2.3 线性复杂度及B-M算法n2.4 非线性序列生成器 n2.5 流密码算法48 第2章 流密码2.1 流密码一般模型482.4 非线性序列非线性序列生成器生成器n密钥流生成器的分解密钥流生成器的分解 Ruppe将密钥流生成器分成两部分：驱动部将密钥流生成器分成两部分：驱动部分和非线性组合部分分和非线性组合部分 q驱动部分：可由驱动部分：可由m-序列或其它长周期的序列或其它长周期的LFSR序列组成，序列组成，用于控制密钥流生成器的状态序列，并为非线性组合部分用于控制密钥流生成器的状态序列，并为非线性组合部分提供伪随机性质良好的序列提供伪随机性质良好的序列q非线性组合部分：利用驱动部分生成的状态序列生成满足非线性组合部分：利用驱动部分生成的状态序列生成满足要求的密码特性好的密钥流序列要求的密码特性好的密钥流序列驱动部分非线性组合部分492.4 非线性序列生成器密钥流生成器的分解驱动部分2.4 非线性序列非线性序列生成器生成器n非线性准则非线性准则 非线性组合部分可由布尔函数表示非线性组合部分可由布尔函数表示 qn元布尔函数元布尔函数f(x)的代数正规型：的代数正规型：502.4 非线性序列生成器非线性准则 502.4.1 非线性准则非线性准则q代数次数代数次数n当当f(x)的代数次数为的代数次数为1时，时，f(x)称为线性布尔函数称为线性布尔函数n当当f(x)的代数次数大于的代数次数大于1时，时，f(x)称为非线性布尔函数称为非线性布尔函数n对于非线性组合部分的布尔函数，应该具有尽可能大的代对于非线性组合部分的布尔函数，应该具有尽可能大的代数次数数次数 定义2.6 设设f(x)是一个是一个n元布尔函数，元布尔函数，在在f(x)的代数正规型中，一个乘积项中变的代数正规型中，一个乘积项中变量的个数称为该乘积项的量的个数称为该乘积项的次数次数。f(x)的代的代数正规型中，全体非零系数乘积项次数的数正规型中，全体非零系数乘积项次数的最大值称为最大值称为f(x)的的代数次数代数次数。512.4.1 非线性准则代数次数当f(x)的代数次数为1时，f2.4.1 非线性准则非线性准则q非线性度非线性度n是密码系统为抵抗线性攻击而提出的指标是密码系统为抵抗线性攻击而提出的指标n对于非线性组合部分的布尔函数，应该具有尽可能大的非对于非线性组合部分的布尔函数，应该具有尽可能大的非线性度线性度 定义2.7 设设L是是Z2上所有线性函数的集合，上所有线性函数的集合，即即L=u x+v|u Z2n,v Z2。则布尔。则布尔函数函数f(x)的的非线性度非线性度定义为定义为其中其中dH()是汉明是汉明距离距离.522.4.1 非线性准则非线性度是密码系统为抵抗线性攻击而提出2.4.1 非线性准则非线性准则q退化布尔函数退化布尔函数n自变量经过线性变换后，自变量经过线性变换后，n元布尔函数元布尔函数f(x)就简化为就简化为k元布尔函数元布尔函数g(x)n作为非线性组合部分的布尔函数应该避免退化性作为非线性组合部分的布尔函数应该避免退化性 定义2.8 设设f(x)是一个是一个n元布尔函数，如元布尔函数，如果存在果存在Z2上一个上一个k n（kn）的矩阵）的矩阵D，使得使得 f(x)=g(Dx)=g(y),则称则称f(x)是是退化的退化的。532.4.1 非线性准则退化布尔函数自变量经过线性变换后，n元2.4.1 非线性准则非线性准则q布尔函数的相关免疫性布尔函数的相关免疫性n相关免疫性是为防止攻击者对密码系统进行相关攻击而提出的相关免疫性是为防止攻击者对密码系统进行相关攻击而提出的指标指标n希望作为非线性组合部分的布尔函数应该具有希望作为非线性组合部分的布尔函数应该具有m阶相关免疫性，阶相关免疫性，m尽可能地大尽可能地大 定义定义2.9 设设f(x1,x2,xn)是是n个彼此个彼此独立、对称的二元随机变量的布尔函独立、对称的二元随机变量的布尔函数，称数，称f(x)是是m阶相关免疫的阶相关免疫的当且仅当且仅当当f=f(x1,x2,xn)与与x1,x2,xn中的中的任意任意m个随机变量个随机变量542.4.1 非线性准则布尔函数的相关免疫性相关免疫性是为防止2.4.1 非线性准则非线性准则q布尔函数的相关免疫性布尔函数的相关免疫性 定义2.10 设设 f(x1,x2,xn)是一个是一个n元元布尔函数，布尔函数，f(x)的的Walsh变换变换定义为定义为552.4.1 非线性准则布尔函数的相关免疫性 定义2.4.1 非线性准则非线性准则q布尔函数的相关免疫性布尔函数的相关免疫性q雪崩准则雪崩准则 定理2.9 设设1mn,n元布尔函数元布尔函数f=f(x1,x2,xn)是是m阶相关免疫的当且仅阶相关免疫的当且仅当对于任意满足当对于任意满足1wH()m的的 =(1,2,n)Z2n，f(x)的的Walsh谱都为谱都为0，即即 Sf()=0.这里这里wH()是汉明重量是汉明重量.定义2.11 设设f(x)是一个是一个n元布尔函数，如元布尔函数，如果对于任意满足果对于任意满足:wH(e)=1的的e=(e1,e2,en)Z2n，f(x)+f(x+e)是平衡函数，是平衡函数，则称则称 f(x)为满足为满足严格雪崩准则严格雪崩准则.562.4.1 非线性准则布尔函数的相关免疫性雪崩准则 2.4.1 非线性准则非线性准则q扩散准则扩散准则 定义2.12 设设f(x)是一个是一个n元布尔函数，元布尔函数，1mn 2，如果对于任意满足，如果对于任意满足:1wH(e)m 的的e=(e1,e2,en)Z2n，f(x)+f(x+e)是平衡函数，则称是平衡函数，则称 f(x)为满足为满足m次扩散准则次扩散准则.q非线性序列设计准则非线性序列设计准则n代数次数代数次数n非线性度非线性度n退化性退化性n相关免疫性相关免疫性n雪崩准则雪崩准则n扩散准则扩散准则 572.4.1 非线性准则扩散准则 定义2.12 2.4.2 非线性序列非线性序列生成器生成器n滤波生成器（滤波生成器（Filter geneator）q滤波生成器又叫前馈生成器，由几个滤波生成器又叫前馈生成器，由几个LFSR和和滤波（前馈）函数滤波（前馈）函数g(x)两部分组成两部分组成q滤波函数要求具有很好的非线性性质，以增强滤波函数要求具有很好的非线性性质，以增强生成器的抗攻击能力生成器的抗攻击能力LFSRg(x)582.4.2 非线性序列生成器滤波生成器（Filter ge滤波生成器滤波生成器nGeffe生成器生成器q使用三个级数两两互素的使用三个级数两两互素的LFSR，其中，其中LFSR1和和LFSR3作为多路复合器的输入，作为多路复合器的输入，LFSR2控制控制多路复合器的输出多路复合器的输出q滤波函数滤波函数LFSR1多路复合器选择控制LFSR3LFSR2 设设a1、a2和和a3分别是分别是LFSR、LFSR2和和L FSR3的输出，则的输出，则Geffe生成器的输出生成器的输出b为为:59滤波生成器Geffe生成器LFSR1多路复合器选择控制LFS滤波生成器滤波生成器nGeffe生成器生成器q大的周期和线性复杂度大的周期和线性复杂度 设设LFSR1、LFSR2和和L FSR3周期分别为周期分别为T1,T2和和T3，级数分别为，级数分别为n1,n2和和n3，则，则Geffe生成生成器的周期为器的周期为T1T2 T3，线性复杂度为，线性复杂度为(n11)n2n1n3.q不安全不安全 由于生成器的输出与由于生成器的输出与LFSR2的输出有的输出有75是相是相同的，通过观察输出序列可以获得同的，通过观察输出序列可以获得LFSR的初的初态和输出序列，即所谓的相关攻击破译态和输出序列，即所谓的相关攻击破译Geffe生成器。因此生成器。因此Geffe生成器是不安全的生成器是不安全的.60滤波生成器Geffe生成器60滤波生成器滤波生成器nJ-K触发器触发器qLFSR1输出序列输出序列ak,周期周期为为m.qLFSR2输出序列输出序列bk,周期周期为为n.qJ-K触发器输出序列触发器输出序列ck 令令c-1=0,有有 c0=a0,c1=(a1+b1+1)a0+a1,c2=(a2+b2+1)c1+a2,akckbkLFSR1JKLFSR261滤波生成器J-K触发器 令c-1=0,有akJ-K触发器触发器q如果如果gcd(m,n)=1，且，且a0+b0=0，则输出序列，则输出序列ck的周期为的周期为:(2m-1)(2n-1).qJ-K触发器输出序列触发器输出序列ck随机性好随机性好q不安全不安全 已知已知cn与与cn+1,便能对便能对an+1与与bn+1的一个作出判的一个作出判断断.cn=cn+1=0 an+1=0;cn=0,cn+1=1 an+1=1;cn=1,cn+1=0 bn+1=1;cn=cn+1=1 bn+1=0.62J-K触发器如果gcd(m,n)=1，且a0+b0=J-K触发器触发器q例例2.4.1 令令m=2,n=3,且且a0+b0=0,LFSR1输出序列输出序列 at=011,LFSR2输出序列输出序列 bt=1001011.有有 c0=a0=0,c1=(a1+b1+1)a0+a1=(1+0+1)0+1=1,c2=(a2+b2+1)c1+a2=(1+0+1)1+1=1,bk=0110 1001 1101 0100 1001 0.周期为周期为:L=(2m-1)(2n-1)=(22-1)(23-1)=21.63J-K触发器例2.4.1 令m=2,n=3,且a0+2.4.2 非线性序列非线性序列生成器生成器n钟控序列生成器钟控序列生成器q 钟控生成器（钟控生成器（Clock controlled generator）是由一个或几个是由一个或几个FSR输出序列，控制另一个输出序列，控制另一个FSR的时钟。的时钟。q走停生成器（走停生成器（Stop-and-Go generator）n当当LFSR1输出输出1时，时钟脉冲通过与门使时，时钟脉冲通过与门使LFSR2进进行一次移位，从而生成下一位；行一次移位，从而生成下一位；n当当LFSR1输出输出0，时钟脉冲无法通过与门使，时钟脉冲无法通过与门使LFSR2移位（走），从而移位（走），从而LFSR2重复输出前一位（停）重复输出前一位（停）LFSR1LFSR2642.4.2 非线性序列生成器钟控序列生成器LFSR1LFS钟控序列生成器钟控序列生成器q钟控序列的周期钟控序列的周期 设设LFSR1输出序列输出序列ak,周期为周期为2m-1，LFSR2输输出序列出序列bk,周期为周期为2n-1，则钟控序列，则钟控序列ck的周的周期为：期为：(2m-1)(2n-1).q钟控序列钟控序列 ck的线性复杂度为：的线性复杂度为：n(2m-1).65钟控序列生成器钟控序列的周期65钟控序列生成器钟控序列生成器q例2.6 设设LFSR1为一个为一个3级级m-序列，其特征多项序列，其特征多项式为：式为：f1(x)=1+x+x3，取初始值为，取初始值为a0=a1=a2=1,则则输出序列输出序列ak=1110100,周期为周期为23 1=7.设设LFSR2为一个为一个3级级m-序列，其特征多项式为：序列，其特征多项式为：f1(x)=1+x2+x3，取初始值为，取初始值为b0=b1=b2=1,则输出则输出序列序列bk=1110010,周期为周期为23-1=7.钟控序列钟控序列:ck=1110 0000 1011 1111 0001 1101 1111 1001 1000 1111 0000 1001 1 周期为：周期为：(2m 1)(2n 1)=(23 1)(23 1)=49.线性复杂度为：线性复杂度为：n(2m 1)=3(23 1)=21.66钟控序列生成器例2.6 设LFSR1为一个3级m-序列，其 第第2章章 流密码流密码n2.1 流密码一般模型n2.2 线性反馈移位寄存器序列n2.3 线性复杂度及B-M算法n2.4 非线性序列生成器 n2.5 流密码算法67 第2章 流密码2.1 流密码一般模型672.5 流密码算法流密码算法nRC4算法算法qRC4是由是由Rivest于于1987年开发的一种序列密码年开发的一种序列密码,它已被广泛应用于它已被广泛应用于Windows,Lotus Notes和其和其它软件它软件,还被用于安全套接字还被用于安全套接字(SSL)和无线通信系和无线通信系统等统等.qRC4优点是算法简单、高效，特别适于软件实现，优点是算法简单、高效，特别适于软件实现，加密速度比加密速度比DES大约快大约快10倍。倍。qRC4可以支持不同密钥长度，美国政府特别限定，可以支持不同密钥长度，美国政府特别限定，用于出口的用于出口的RC4的密钥长度不得超过的密钥长度不得超过40位。位。682.5 流密码算法RC4算法682.5 流密码算法流密码算法qRC4使用了一个使用了一个28字节大小的非线性数据表字节大小的非线性数据表(简简称称S表表),S表的值表的值S0,S1,S255是数字是数字0到到255的的一个排列。对一个排列。对S表进行非线性变换表进行非线性变换,得到密钥流。得到密钥流。qRC4对对S表的初始化算法表的初始化算法(两个计数器两个计数器I和和J,I=0,J=0)1.对对S表进行线性填充：表进行线性填充：SI=I,0I255；2.用密钥填充另一个用密钥填充另一个256字节的数组字节的数组K，如，如果密钥长果密钥长 度小于度小于256字节，则依次重复填字节，则依次重复填充，直至填满这个数组中：充，直至填满这个数组中：K0,K1,K255；3.对于对于I=0到到255重复以下步骤：重复以下步骤：(1)J=J+SI+KI（mod 256）；）；(2)交换交换SI和和SJ。692.5 流密码算法RC4使用了一个28字节大小的非线性数据RC4算法算法qRC4输出密钥流字节输出密钥流字节z的算法的算法1.I=0,J=02.I=I+1(mod 256);3.J=J+SI (mod 256);4.交换交换SI和和SJ;5.t=SI+SJ (mod 256);6.z=St.70RC4算法RC4输出密钥流字节z的算法1.I=0,J2.5 流密码算法流密码算法nA5算法算法qA5有两个版本：有两个版本：A5/1和和A5/2，前者有更高的，前者有更高的安全性，根据相关法规限制被仅用于欧洲范安全性，根据相关法规限制被仅用于欧洲范围，而后者用于其它地区。围，而后者用于其它地区。A5算法从未公布算法从未公布于众，但因为一些疏漏，该算法被于众，但因为一些疏漏，该算法被Bradford大学研究人员泄密，我国学者徐胜波、何大大学研究人员泄密，我国学者徐胜波、何大可和王新梅也由此于可和王新梅也由此于1994年率先实现年率先实现A5算法。算法。qA5是欧洲数字蜂窝移动电话系统（是欧洲数字蜂窝移动电话系统（GSM）采）采用的流密码算法，用于加密从移动台到基站用的流密码算法，用于加密从移动台到基站的连接。的连接。712.5 流密码算法A5算法712.5 流密码算法流密码算法nA5算法算法qGSM 会话每帧有会话每帧有228bitqA5算法的密钥长算法的密钥长64bitq有一个有一个22bit表征会话帧数表征会话帧数q每次产生每次产生228bit会话密钥。会话密钥。722.5 流密码算法A5算法72A5算法算法qA5算法算法73A5算法A5算法73A5算法算法qLFRS1:g1(x)=x19+x18+x17+x14+1;LFRS2:g2(x)=x22+x21+x17+x13+1;LFRS3:g3(x)=x23+x22+x19+x18+1.q时钟控制系统时钟控制系统n 输入输入:LFRS1(10)=x,LFRS2(11)=y,LFRS3(12)=zn控制逻辑控制逻辑:如果如果LFRS1(10)=LFRS2(11)=LFRS3(12),则则3个个LFRS都移都移1位位;否则相等的否则相等的2个个LFRS移移1位位,另另1个个LFRS不移位不移位.钟控函数：g(x,y,z)=xy+xz+yz q输出序列输出序列:LFRS1+LFRS2+LFRS3 74A5算法LFRS1:g1(x)=x19+x18+x17+x2.5 序列密码实例序列密码实例nA5算法工作过程算法工作过程q（1）将）将64比特密钥输入比特密钥输入LFSR；q（2）将）将22比特帧数与比特帧数与LFSR反馈值模反馈值模2加，再输入加，再输入LFSR；q（3）LFSR开始停走钟控；开始停走钟控；q（4）舍去产生的）舍去产生的100比特输出；比特输出；q（5）产生）产生114比特作为密钥流；比特作为密钥流；q（6）舍去产生的）舍去产生的100比特输出；比特输出；q（7）产生）产生114比特作为密钥流。比特作为密钥流。752.5 序列密码实例A5算法工作过程75第2章 习 题nP50:习题1-7.76第2章 习 题P50:习题1-7.76