流密码的基本概念汇总.ppt

第三章第三章 流密码流密码一、流密码的基本概念一、流密码的基本概念二、线性反馈移位寄存器序列二、线性反馈移位寄存器序列三、非线性序列三、非线性序列2024/5/25 周六1一、流密码的基本概念一、流密码的基本概念2024/5/25 周六2 流密码的基本概念流密码的基本概念n流密码是将明文划分成字符(如单个字母)，或其编码的基本单元(如0,1数字)，字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现。n流密码强度完全依赖于密钥序列的随机性随机性(Randomness)和不可预测性不可预测性(Unpredictability)。n核心问题是密钥流生成器的设计核心问题是密钥流生成器的设计。n保持收发两端密钥流的精确同步是实现可靠解密的关键技术。2024/5/25 周六3流密码的框图流密码的框图kI 安 全 信 道 kI KG KG ki ki mi ci ci mi Eki(mi)Eki(mi)2024/5/25 周六4 流密码的框图流密码的框图n消息流消息流：m=m1m2mi，其中miM。n密密文文流流：c=c1c2ci=Ek1(m1)Ek2(m2)Eki(mi)，ciC。n密钥流：密钥流：ki，i0。一个完全随机的非周期序列，可以实现一次一密体制。但需要无限存储单元和复杂的输输出出逻逻辑辑函函数数f。i是第i时刻密钥流生成器的内部状态内部状态，以存储单元的存数矢量存数矢量描述。n加法流密码：加法流密码：ci=Eki(mi)=mi ki2024/5/25 周六5有限状态自动机有限状态自动机FA(Finite state Automaton)n具有离散输入和输出（输入集和输出集均有限）的一种数学模型n有限状态集S=si|i=1,2,ln有限输入字符集X=Xi|i=1,2,mn有限输出字符集Y=Yk|k=1,2,nn转移函数nYjf 1(sj,Xj)nSj+1 f 2(sj,Xj)第j时刻输入Xj X，输出YjY 2024/5/25 周六6例2-1nS=s1,s2,s3,X=x1,x2,x3,Y=(y1,y2,y3)n转移函数f1x1x2X3s1s2s3y1y2y3y3y1y2y2y3y1f2x1x2X3s1s2s3s2s3s1s1s2s3s3s1s22024/5/25 周六7FA的状态图表示 若输入为x1x2x1x3x3x1初始状态s1输出为y1y1y2y1y3y12024/5/25 周六8作为作为FAFA的密钥流产生器的密钥流产生器n同步流密码的密钥流产生器可看为一个参数为k的FAn输出集Z，状态集，状态转移函数和输出函数，初态0n设计的关键是和ikkkzi2024/5/25 周六9作为作为FAFA的密钥流产生器的密钥流产生器n具有非线性的的FA理论很不完善，通常采用线性以及非线性的n可将此类产生器分为驱动部分和非线性组合部分。n驱动部分控制状态转移n非线性组合部分提供统计特性良好的序列2024/5/25 周六10两种常见的密钥流产生器LFSR非线性组合函数ziLFSRLFSRLFSR非线性组合函数zi2024/5/25 周六11 流密码的分类流密码的分类n同步流密码同步流密码SSC(Synchronous Stream Cipher)：i与明文消息无关，密钥流将独立于明文。n特点：特点：n对于明文而言，这类加密变换是无无记记忆忆的的。但它是时时变变的的。n只有保持两端精确同步才能正常工作。n对主动攻击时异常敏感而有利于检测n无差错传播差错传播(Error Propagation)2024/5/25 周六12流密码的分类流密码的分类n自同步流密码自同步流密码SSSC(Self-Synchronous Stream Cipher)i依赖于(k kI,i-1,mi)，使密文ci不仅与当前输入mi有关，而且由于ki对i的关系而与以前的输入m1,m2,mi-1有 关。一 般 在 有 限 的n级 存 储 下 将 与mi-1,mi-n有关。n优点优点：具有自同步能力，强化了其抗统计分析的能力n缺点缺点：有n位长的差错传播。2024/5/25 周六13流密码的分类流密码的分类 n级移存器 n 级移存器 ki f f ki ki kimi Eki()ci ci Dki()mi 2024/5/25 周六14 序列的伪随机性序列的伪随机性n周期周期 序列kii0，使 对所有i，ki+p=ki 成立的的最小整数pn长为长为l的串的串(run)(kt,kt+1kt+l-1)序列ki的一个周期中，kt-1kt=kt+1=kt+l-1 kt+l 例：长为l的1串和长为l的0串：2024/5/25 周六15序列的伪随机性序列的伪随机性n周期自相关函数周期自相关函数 周期为p的序列kii0，其周期自相关函数 R(j)=(AD)/p，j=0,1,式 中，A=0ip|：ki=ki+j，D=0ip：kiki+j。n同相同相自相关函数自相关函数 当j为p的倍数，即pj时为，R(j)=1；n异相自相关函数异相自相关函数 当j不是p的倍数时2024/5/25 周六16例22 二元序列111001011100101110010 周期p=7 同相自相关函数R(j)=1 异相自相关函数R(j)=1/7。2024/5/25 周六17Golomb随机性假设随机性假设PN序列序列 G1若p为偶，则0,1出现个数相等，皆为p/2。若p为奇，则0出现个数为(p1)/2。G2长为l的串占1/2l，且“0”串和“1”串个数相等或至多差一个。G3R(j)为双值，即所有异相自相关函数值相等。这与白噪声的自相关函数(函数)相近，这种序列又称为双双值值序列序列(Two Value Sequence)。PN序列可用于通信中同步序列、码分多址(CDMA)、导航中多基站码、雷达测距码等。但仅满足G1G3特性的序列虽与白噪声序列相似，但远还不能满足密码体制要求。2024/5/25 周六18满足密码体制的另外三个条件满足密码体制的另外三个条件C1周期p要足够大，如大于1050；C2序列kii0产生易于高速生成；C3当序列kii0的任何部分暴露时，要分析整个序列，提取产生它的电路结构信息，在计算上是不可行的，称此为不可预测性不可预测性(Unpredictability)。C3决定了密码的强度，是流密码理论的核心。它包含了流密码要研究的许多主要问题，如线性复杂度、相关免疫性、不可预测性等等。2024/5/25 周六19二、二、线性反馈移位寄存器序列线性反馈移位寄存器序列2024/5/25 周六20线性反馈移位寄存器序列概念线性反馈移位寄存器序列概念n级数级数(Stages)：存储单元数。n状态状态(State)：n个存储单元的存数(ki,ki+n-1)n反馈函数：反馈函数：f(ki,ki+1,ki+n-1)是状态(ki,ki+n-1)的函数。n线性反馈移位寄存器线性反馈移位寄存器(LFSR)：f 为线性函数n非线性反馈移位寄存器：非线性反馈移位寄存器：f 为非线性函数2024/5/25 周六21反馈移位寄存器反馈移位寄存器 x1,x2,xn f(ki,ki+1,ki+n-1)ki+n ki+n-1 ki+n-2 ki+1 ki ki-1.,k1 k0 xn xn-1 x2 x12024/5/25 周六22 线性反馈移位寄存器线性反馈移位寄存器 f(x)为线性函数，输出序列满足下式 cn -cn-1 -cn-2 -c1 -c0 ki+n-1 ki+n-2 ki+1 ki ki-1,k1,k0 xn xn-1 x2 x12024/5/25 周六23二元线性移位寄存器二元线性移位寄存器 二元条件下ki0,1，cj 0,1，即断开或连通，为模2加，反馈函数可写成n阶线性递推关系式 cn cn-1 cn-2 c1 c0 ki+n-1 ki+n-2 ki+1 ki ki-1,k1,k0，xn xn-1 x2 x1 2024/5/25 周六24 线性反馈移位寄存器线性反馈移位寄存器例例 n=4的LFSR。输出序列满足ki4ki3ki=0。初始状态为1000。序列的周期为15=241。c4 c3 c2 c1 c0 ki 0 0 0 1 线性移存器序列的最长周期为最长周期为2n1。2024/5/25 周六25状态转移和相应输出状态转移和相应输出 时刻时刻 状状 态态 输输 出出 3 2 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 2 0 1 0 0 0 3 0 0 1 0 0 4 1 0 0 1 1 5 1 1 0 0 0 6 0 1 1 0 0 7 1 0 1 1 1 8 0 1 0 1 1 9 1 0 1 0 0 10 1 1 0 1 1 11 1 1 1 0 0 12 1 1 1 1 1 13 0 1 1 1 1 14 0 0 1 1 1 15 0 0 0 1 1 2024/5/25 周六26m序列序列n 为2n1的LFSR序列称为m序列。m序列是一类PN序列。n n级m序列kii0循环地遍历所有2n1个非零状态，且任一非零输出皆为kii0的移位，或为其循环等循环等价价(Cyclically equivalent)序列。n初始状态不同2n1个的m序列共有2n1个,他们的全体记为(f),他们只是状态前后次序之别。2024/5/25 周六27 特征多项式特征多项式n以LFSR的反馈系数所决定的多项式 又称反馈多项式反馈多项式。式中，c0=cn=1n反多项式反多项式 称作是LFSR的联接多项式联接多项式。cn0称之为非奇异非奇异LFSR。2024/5/25 周六28特征多项式特征多项式定义定义:给定序列 kii0,幂级数幂级数称为该序列的生成函数生成函数定定理理3-1 令kii0(f)，f(x)是反馈多项式，令k(x)是kii0的生成函数，则 其中 2024/5/25 周六29特征多项式特征多项式证证：a(x)就是移存器初始值所对应的多项式2024/5/25 周六30特征多项式特征多项式 系系:证证：(f)的每个元素均可由a(x)/f(x)惟一决定，式中，deg(a(x)n，另 一 方 面，(f)有 2n个 元 素。而deg(a(x)n的多项式也恰有2n个。2024/5/25 周六31多项式的周期多项式的周期n多多项项式式f(x)的的周周期期p为使f(x)除尽xn-1的最小整数n的取值。n序列的周期与生成序列特征多项式的周期密切相关序列的周期与生成序列特征多项式的周期密切相关。引理引理3-2:令f(x)为n次式，周期为p，令kii0(f)，则kii0的周期pp。2024/5/25 周六32多项式的周期多项式的周期引引理理3-3 令f(x)是周期为p的n次既约多项式，令kii0(f)，则kii0的周期为p。证证：令kii0周期为p，由引理3-2-3，有pp，则有，deg(u(x)p，由(3-2-12)式有k(x)=a(x)/f*(x)，故有，由此可得 。因为f(x)为n次既约式，deg(a(x)0，n1 n2。由(3-2-14)式，1/f1*(x)(f1)，故由引理3-2-3及附录3A，1/f1*(x)的周期除尽。类似地有。由定理3-2-1知1/f1*(x)应是kii0的移位，.因而其周期为2n1，惟一可能是n=n1，即f(x)=f1(x)。2024/5/25 周六34m序列的性质序列的性质 定定理理3-5 以f(x)为特征多项式的LFSR的输出序列是m序列的充要条件为f(x)是本原的。系系 n级LFSR生成的不等价m序列共有(2n1)/n个。定理定理 3-6 m序列满足Golomb的三条伪随机假设。2024/5/25 周六35m序列的性质序列的性质m序列否满足密码要求序列否满足密码要求？nm-C1：n级m序列的周期为2n1，n大，周期指数地加大，例如n=166时，p=1050(9.353610465 1049)。nm-C2：只要知道n次本原多项式，m序列极易生成。nm-C3：m序列极不安全，只要泄露2n位连续数字，就可完全确定出反馈多项式系数。2024/5/25 周六36 m序列的破译序列的破译 已知ki,ki+1,ki+2n，由递推关系式可得出下式 式中有n个线性方程和n个未知量，故可惟一解出ci，0in-1。2024/5/25 周六37三、三、非线性序列非线性序列2024/5/25 周六38非线性序列非线性序列n线性复杂度：线性复杂度：能产生周期序列 kii 0的LFSR的最小级数n。显然，n级m序列的线性复杂度为n。n线性复杂度是研究和设计密码的重要指标和工具线性复杂度是研究和设计密码的重要指标和工具。n一个伪随机序列若其线性复杂度低，就易于由部分序列综合出生成它的LFSR。一般移存器序列的线性复杂度nL2n。L大不一定就安全；但L小肯定是不安全的!2024/5/25 周六39非线性前馈序列非线性前馈序列nLFSR虽然不能直接作为密钥流用，但可作为驱动源以其输出推动一个非线性组合函数组合函数所决定的电路来产生非线性序列。这就是所谓非线性前馈序列生成器非线性前馈序列生成器。nLFSR用来保证密钥流的周期长度、平衡性等n非线性组合函数用来保证密钥流的各种密码性质，以抗击各种可能的攻击。2024/5/25 周六40非线性前馈序列非线性前馈序列 LFSR F ki研究的中心问题研究的中心问题：前馈函数F与输出序列的周期性、随机性、线性复杂度以及相关免疫性之间的关系。2024/5/25 周六41多路选择多路选择(Multiplexing)序列序列 有n种输入序列b0(t),bn-1(t)，在地址序列a1(t),am-1(t)的控制下决定输出取自某个输入比特。例如取m级LFSR生成m序列作地址控制，取n级LFSR生成的m序列作为输入序列。2024/5/25 周六42多路选择多路选择(Multiplexing)序列序列 可供选择的输入 多路选择器 多路选择密码多路选择密码 2024/5/25 周六43J-K触发器触发器 J-K触发器是一个非线性器件，有两个输入端j，k和一个内部状态，即输出为qi,，其逻辑真值如表3-3-2所示。一般令q-1=0。表表3-3-2 J Kqi Geffe1973采用三个LFSR，其中两个的输 0 0qi-1 出通过一个J-K触发器进行复合。如图3-3-9 0 10所示。还可进一步推广由s1个LFSR 1 01进行复合。LFSR-1的时钟必须较其它s 1 1 个LFSR的时钟快log2(s)倍，其中s为2的 幂次。2024/5/25 周六44 Geffe生成器生成器 2中择1多路选择器 LFSR-2 选择 b(t)LFSR-3 LFSR-1 图图3-3-9 Geffe生成器生成器 多路复合器输入两两成对，并以J-K触发器进行复合后送入多路复用器。这类生成器的安全性不高，易受相关攻击。2024/5/25 周六45钟控序列生成器钟控序列生成器 钟控序列10多年前提出的一种新的密钥流生成法，这种方法所生序列的线性复杂度与生成器输入参数间具有指数的关系。这类序列易于由硬件实现。钟控移位寄存器的级连是一种重要的序列的流密码备选体制。2024/5/25 周六46本章到此 结束。谢谢大家！2024/5/25 周六47