西安电子科技大学《现代密码学》教学课件第二章.

本科生必修课《现代密码学》第二章流密码主讲教师：董庆宽副教授研究方向：密码学与信息安全电子邮件：[e-mail]个人主页：内容提要1.流密码的基本概念2.线性反馈移位寄存器3.非线性序列4.流密码算法2/第二章流密码2.1流密码的基本概念流密码(streamcipher)，也称为序列密码(SequenceCipher)，是一种重要的密码体制明文消息按字符或比特逐位加密流密码的基本思想利用密钥k产生一个密钥流z=z0z1z2…，并使用如下规则对明文串x=x0x1x2…加密：y=y0y1y2…＝Ez0(x0)Ez1(x1)Ez2(x2)…流密码与分组密码的区别：在于有无记忆性流密码的密钥流是由已知记忆状态导出当前状态与记忆元件初始状态、密钥k、输入的明文和状态转换函数导出分组密码对明文一组一组的加密，组间一般没有关系3/第二章流密码内部记忆元件………kxiyiyi=Ezi(xi)无记忆元件kx1yly=Ek(x)...xmy1流密码示意图分组密码示意图2.1流密码的基本概念流密码在50年代得到飞跃式发展密钥流可以用移位寄存器电路来产生，因此基于硬件实现优势更明显也有些算法是针对软件设计的，如Ecrypt计划中的算法，RC4等主要用于专用和机密机构：军方，外交，银行等资源受限环境(如RFID标签)、伪随机数生成器、链路加密等环境加密速度快，实现简单，同步流密码不存在错误扩散问题，对一些有扰信道而言是良好的选择流密码具有有效的数学分析工具代数(如布尔代数)、有限域理论和谱分析理论、概率论等等很多密码学家因流密码研究而成名：肖国镇，Massey，Berlikamp等。参考资料：肖国镇著《伪随机序列及其应用》，《流密码学及其应用》4/第二章流密码2.1.1同步流密码流密码的滚动密钥流由密钥流发生器f产生：zi＝f(k,σi)内部记忆元件由一组移位寄存器构成，这里假设有n个移位寄存器σi是加密器中的记忆元件在时刻i的状态，可表示为σi=(an,an-1,…,a1)f是由k,σi产生的函数流密码的滚动密钥由函数f、密钥k和指定的初态σ0完全确定此后由于输入加密器的明文可能影响加密器中的内部记忆元件的存储状态，因而σi(i0)可能依赖于k，σ0，x0，x1，…，xi－1，即前i个明文和密钥及初态5/第二章流密码：2.1流密码的基本概念anσi=(a1,a2,…,an)an-1...a1FeedbackShiftRegister,FSR2.1.1同步流密码流密码可按记忆元件存储状态分类按照加密器中记忆元件的存储状态σi是否依赖于输入的明文字符流，流密码可进一步分成同步和自同步流密码两种σi独立于明文字符流的叫做同步流密码，否则叫做自同步流密码由于自同步流密码的密钥流产生与明文有关，所以理论上难于分析。好的密码算法应该在理论上或基于实践检验能够证明其是安全的或至少是没有明显漏洞的。如果算法难于分析，则无法保证其安全性，也就无法放心使用，因此自同步流密码研究很少，很少采用。6/第二章流密码：2.1流密码的基本概念2.1.1同步流密码目前大多数研究成果都是关于同步流密码的由于zi＝f(k,σi)与明文无关，此刻的密文字符yi=Ezi(xi)也不依赖于此前的明文字符，这样可将同步流密码的加密器分成密钥流产生器和加密变换器两个部分。设解密变换为xi=Dzi(yi)。同步流密码体制模型如下图7/第二章流密码：2.1流密码的基本概念安全信道kk滚动密钥生成器………滚动密钥生成器………zizixiyiEzi(xi)………xiyiDzi(yi)2.1.1同步流密码加密变换Ezi可有多种选择，保证变换可逆性即可比如明文流和密钥流对应位异或实际数字保密通信系统一般都是二元的{0,1},在有限域GF(2)上讨论二元加法流密码是目前最常用的流密码体制加密变换可表示为yi＝zixi，加法流密码体制模型同步流密码算法的设计主要是密钥流产生器的设计密钥产生器目标是：使密钥k经其扩展成的密钥流序列z具有：极大的周期，良好的统计特性，抗差分分析，抗线性分析等性质8/第二章流密码：2.1流密码的基本概念安全信道kk滚动密钥生成器………滚动密钥生成器………zizixiyi………xiyi2.1.2有限状态自动机流密码中任意时刻密钥流和密文的输出与状态密切相关。可以用有限状态自动机这一数学模型来表述有限状态自动机是具有离散输入和输出（输入集和输出集均有限）的一种数学模型，由3部分组成：有限状态集S={si|i=1,2,…,l}共有l个可能状态有限输入字符集A1={Aj(1)|j=1,2,…,m}和有限输出字符集A2={Ak(2)|k=1,2,…,n}。转移函数:输出转移函数：Ak(2)=f1(si,Aj(1))，状态转移函数：sh=f2(si,Aj(1))即在状态为si，输入为Aj(1)时，输出为Ak(2)，而状态转移为sh。9/第二章流密码：2.1流密码的基本概念2.1.2有限状态自动机【例2－1】S={s1,s2,s3}，A1={A1(1),A2(1),A3(1)}，A2={A1(2),A2(2),A3(2)}，转移函数由表2－1给出。f1为输出转移函数，f2为状态转移函数10/第二章流密码：2.1流密码的基本概念f1A1(1)A2(1)A3(1)s1A1(2)A3(2)A2(2)s2A2(2)A1(2)A3(2)s3A3(2)A2(2)A1(2)f2A1(1)A2(1)A3(1)s1s2s1s3s2s3s2s1s3s1s3s22.1.2有限状态自动机有限状态自动机可用有向图表示，称为转移图转移图的顶点对应于自动机的状态若状态si在输入Ai(1)时转为状态sj，且输出一字符Aj(2)，则在转移图中，从状态si到状态sj有一条标有(Ai(1),Aj(2))的有向弧线，如图在例2-1中，若输入序列为A1(1)A2(1)A1(1)A3(1)A3(1)A1(1)初始状态为s1，则得到状态序列为：输出字符序列为：11/第二章流密码：2.1流密码的基本概念s1(A2(1),A3(2))s3(A2(1),A2(2))s2(A2(1),A1(2))(A3(1),A3(2))(A1(1),A1(2))(A1(1),A3(2))(A3(1),A2(2))(A1(1),A2(2))(A3(1),A1(2))s1s2s2s3s2s1s2A1(2)A1(2)A2(2)A1(2)A3(2)A1(2)2.1.3密钥流产生器同步流密码的关键是密钥流产生器(KeyGenerator)一般可将其看成一个参数为k的有限状态自动机，由一个输出符号集Z、一个状态集∑、两个函数φ和ψ以及一个初始状态σ0组成状态转移函数φ：σi→σi+1，将当前状态σi变为一个新状态σi+1输出函数ψ:σi→zi，当前状态σi变为输出符号集中的一个元素zi。密钥流生成器设计的关键在于找出适当的状态转移函数φ和输出函数ψ，使得输出序列z满足密钥流序列z应满足的几个条件，并且要求在设备上是节省的和容易实现的。为了实现这一目标，必须采用非线性函数12/第二章流密码：2.1流密码的基本概念φkσiψkkzi2.1.3密钥流产生器由于具有非线性的φ的有限状态自动机理论很不完善，相应的密钥流产生器的分析工作受到极大的限制。相反地，当采用线性的φ和非线性的ψ时，将能够进行深入的分析并可以得到好的生成器。为方便讨论，可将这类生成器分成驱动部分和非线性组合部分驱动部分控制生成器的状态转移，并为非线性组合部分提供统计性能好的序列；非线性组合部分要利用这些序列组合出满足要求的密钥流序列。13/第二章流密码：2.1流密码的基本概念k驱动子系统非线性组合子系统kzi密钥流生成器的分解2.2.1布尔函数简介n元布尔函数f(x1,…,xn)定义为f：F2nF2表示方法有三种：逻辑关系式，真值表，多元多项式多元多项式：如f(x1,x2,x3,x4)＝x1x2＋x3＋x4异或x1x2x1＋x2(在GF(2)上的“＋”(模2加)逻辑“与”x1x2x1x2(GF(2)上的“乘法”)逻辑“或”x1x2x1x2+x1＋x2其真值表为：非1＋x幂xt＝x·x…x=xt0x0=1;布尔函数的高次项只有如下形式xi1xi2…xik14/第二章流密码：2.2线性反馈移位寄存器x1x2x1x20000111011112.2.1布尔函数简介布尔函数的重量W(f)：真值表中函数值列里”1”的个数f(x1,x2)＝x1x2=x1x2+x1＋x2的重量W(f)＝3布尔函数的次数f(x1,…,xn)＝a0＋一个乘积项的次数定义为r最大次数定义为布尔函数的次数def(f)，也称为代数次数def(f)＝1时，称为仿射函数：f(x1,…,xn)＝a0＋若仿射函数的常数项a0＝0，则称为线性函数def(f)1时，称为非线性函数15/第二章流密码：2.2线性反馈移位寄存器nrniiiiiiiiirrrxxxa1...1...212121...riiixxx...21riiixxx...212.2.2线性反馈移位寄存器的结构与表示移位寄存器(FSR)是序列密码产生密钥流的主要组成部分GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,…,an)组成，如图所示移位寄存器的状态每一存储器称为移位寄存器的一级，具有0和1两个状态在任一时刻，这些级的内容构成该反馈移位寄存器的状态，可用GF(2)上的一个n维向量(a1,a2,…,an)表示，其中ai是第i级存储器的内容。共有2n种可能的状态。初始状态σ0由用户确定，属于密钥k的一部分16/第二章流密码：2.2线性反馈移位寄存器anan-1...a1f(a1,a2,…,an)a2输出序列2.2.2线性反馈移位寄存器的结构与表示状态转换规则根据FSR的工作原理，当第i个移位时钟脉冲到来时a1被移出，作为输出序列在第i时刻的输出bit其它每一级存储器ai都将其内容向下一级ai-1传递同时，根据时钟脉冲到来前寄存器的状态a1,a2,…,an计算出的an=f(a1,a2,…,an)也移入最左边的寄存器反馈函数f(a1,a2,…,an)是n元布尔函数函数中的运算有逻辑与、逻辑或、逻辑补、或其它运算最后的函数值为0或1。可能是线性或非线性布尔函数17/第二章流密码：2.2线性反馈移位寄存器anan-1...a1f(a1,a2,…,an)a2输出序列2.2.2线性反馈移位寄存器的结构与表示例：下图是一个3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由表2.2求出18/第二章流密码：2.2线性反馈移位寄存器a3a2a1f(a1,a2,a3)＝a1a2a3输出序列该3级反馈移位寄存器的状态和输出如下状态（a3,a2,a1)输出101110111011101110101110即输出序列为101110111011…，周期为4在一个一般n-FSR的状态图中，至少含有一个圈，且从任意状态出发进动若干拍后必定进入某一个圈！这时得到的输出序列虽不必是周期序列，但去掉其前若干项后即得到周期序列，也就是说这样的序列为终归周期序列2.2.2线性反馈移位寄存器的结构与表示线性反馈移位寄存器LFSR如果反馈函数f(a1,a2,…,an)是a1,a2,…,an的线性函数(线性布尔函数)，则称之为线性反馈移位寄存器(LinearFeedbackShiftRegister,LFSR)，此时f可写为f(a1,a2,…,an)=cna1cn-1a2…c1an二元情况下(GF(2))，常数ci=0或1，刚好可用开关的断开和闭合来实现根据反馈函数输出序列{at}满足如下递