第3-4讲 流密码概述

流密码基本概念线形反馈移位寄存器简介m序列特性非线性序列第二章流密码2100}{mmmmmii)()()()(210210mEmEmEmEckkkk加密变换为：2100}{kkkkkii)()()()(210210cDcDcDcDmkkkk脱密变换为：流密码的加密方式2.1流密码基本概念按加密方式不同，密码体制可分为流密码和分组密码。1、什么是流密码（序列密码）在实用的流密码中，加密变换通常采用二元加法运算。即：iiikmciiikcm特点：使用随机密钥，且密钥不重用。一次一密的安全性是基于密钥的随机性，由于密钥是真正随机的，没有人能预测到密钥流。弱点：密钥管理的困难性。密码系统的安全性取决于密钥流的性能密钥流是完全随机序列，被称为一次一密密码。Shannon从理论上证明了该体制在唯密文攻击条件下是理论上保密的，这是密码学中唯一的一个能够被证明是无条件安全的密码。这个体制的特点是：使用随机密钥，且密钥不重用。一次一密的安全性是基于密钥的随机性，由于密钥是真正随机的，没有人能预测到密钥序列。一次一密是否现实？存在问题：1、密钥的传输与存贮2、一次一变结论：“一次一密”密码虽然是理论保密的，却很不实用能不能找到一种类似的方法，既可以降低密钥管理的难度，又能达到必须的安全性呢？一个可行的方法是：用一个较小的密钥伪随机地生成密钥流，该密钥流在具有有限计算能力的对手看来是随机的。这种流密码不是无条件安全的，仅是计算上安全的。因此，现代流密码设计的关键是如何生成“随机性”好的密钥序列，这部分称为密钥发生器。密钥发生器组成：驱动部分和非线性组合部分驱动部分控制密钥发生器的状态序列，并为非线性组合部分提供统计特性好的序列。非线性组合部分通过一系列复杂变换，将输入序列组合成密码学特性好的序列。密钥流生成器我们希望密钥发生器驱动部分提供的序列应该实现简单，且具有较好的统计特性，那么，存在这样的序列么？线性移位寄存器序列正是满足该要求的序列。常见的两种密钥流产生器2、流密码分类若密钥是一个完全随机的非周期序列，则可实现一次一密体制，这需要无限的存储单元和复杂的逻辑函数。实际中，流密码多采用有限的存储单元和确定性算法，使用有限的存储单元和确定性算法来实现。因此，可以使用有限状态自动机来描述。密钥流生成器的有限状态自动机描述LSFR（线形移位寄存器）非线性变换1(,)sifKi(,)ifK()ikiEmikiC根据与明文信息的关系，流密码可以分为同步流密码和自同步流密码两类i1、同步流密码σi独立于明文字符的叫做同步流密码，否则叫做自同步流密码。对明文而言，同步流密码的加密变换是无记忆的；解密要求密钥流与加密密钥严格同步。2、自同步流密码σi与明文m1,m2,…,mi-1有关，称为自同步流密码。密钥流生成器。。。k()kiEmmici反馈移存器是序列密码设计中常用乱源,其目的在于以种子密钥为序列的初态，按照确定的递推关系，产生一个周期长、线性复杂度高、统计特性好的初始乱源，然后利用非线性函数、有记忆变换等密码变换，最终产生抗破译能力强的乱数序列。线性移位寄存器序列是构造密钥流序列的基础。2.2线性移位寄存器简介1、反馈移存器结构12rf3一个反馈移位寄存器由两部分组成：移位寄存器和反馈函数，其抽象的简单逻辑框图如上图所示。我们称这一函数为该组合门电路的反馈逻辑函数，表示为：),,,(211rrxxxfx函数f是一个含有r个逻辑变元的布尔函数2、布尔函数简介一般地，我们定义n元布尔函数为如下映射：记为，其中22:FFfn)(xf2221)(,),,,(FxfFxxxxnn一个n元布尔函数是否给定，关键在于该函数之值是否对于每组自变量均已确定，如果把每组自变量与其所对应的函数值全部列成表格，这种表格就叫做反馈函数的真值表。（1）真值表例如),()(21xxfxfxf(x)001101010110（2）多项式表示21)(xxxf3、线性反馈移存器定义定义1：若反馈移存器的反馈逻辑函数是线性函数，则称该反馈移存器为线性反馈移存器，否则称为非线性反馈移存器。13424级线性反馈移存器1233级非线反馈性移存器2、反馈移存器工作原理假设在j时刻其内部状态为：),,,(21rjjjaaa在j+1时刻其内部状态变为：),,,(11rjjjaaa其中：),,,(21rjjjjaaafa此时的输出为j时刻的最高级：rja反馈移存器的功能完全由其反馈逻辑函数来决定移存器受时钟脉冲控制，在某一时刻各级都有一个确定的值，我们把此时刻各级的值称为移存器的一个内部状态132001001100110111011101010状态图：为了从直观上描述反馈移存器的状态转移情况，可以使用一些方框及联接这些方框的箭头组成的图形，在数学上，把表示反馈移存器功能的图形称为状态转移图。在状态图中，从任意状态出发，依次取出各状态相同位置的分量，即得到输出序列。3级线性移位寄存器产生序列为：0111010……和一个全零序列。3、序列和周期移存器序列表示为：iaaaaa210对于序列，若存在整数p使得对任意整数k有成立，称满足该式的最小正整数p为序列的周期。iaaaaa210pkkaa最长周期:，能达到最长周期的线性移存器序列称为m序列。12r4、线性移存器表示方法12341、逻辑框图表示含有4个二元存储器，2，3，4级的开关是连通的，参与反馈。2、线性递推式表示一个r级线性移存器的线性递推式表示为：)(2211rnacacacarnrnnn1234)4(432naaaannnn含义：表示序列中第n个信号与其前r个信号的线性制约关系。3、反馈多项式表示1234一个r级线性移存器的反馈多项式表示为：1)(111xcxcxcxfrrrr1)(234xxxxf用反馈多项式表示，可利用有限域的理论深入细致的考查移存器序列的特性。给定反馈多项式f(x)后，f(x)产生的序列A就完全确定；但给定一个序列A，能产生序列的多项式f(x)有很多。其中，能产生序列A的次数最小的多项式称为序列的极小多项式。极小多项式的次数就是能产生序列的最短移存器级数，通常称其为序列的线性复杂度。内容之间的联系移存器工作原理；表示方法布尔函数基础目的移存器序列流密码的初始乱源应用2.3m序列特性重点：线性移位寄存器产生的序列特性理想序列随机特性好周期足够长由反馈多项式决定设初态为00010001，1000，1100，1110，1111，0111，1011，0101，1010，1101，0110，0011，1001，0100，0010，0001状态图：含有15个状态，所以序列的周期为15。序列：按状态图的状态转移关系，依次取出各状态相同位置的一个分量，即得序列：011110101100100……本原多项式1)(4xxxf结论：产生一个周期为15的序列及一个全零序列。1、本原多项式本原多项式所产生的序列是最长周期序列，即，称为m序列。21rm序列在密码学中有广泛的应用。该移存器的周期是最长周期。称能产生m序列的移存器为本原移存器，该移存器对应的反馈多项式为本原多项式。2、m序列特性定义1：游程若干个信号连续出现的现象称游程。)(210aaaa给定序列a1001两端为0中间连续k个1，称长为k的1游程。0110两端为1中间连续k个0，称长为k的0游程。如0110为一个长为2的1游程，101为一个长为1的0游程。若存在一段序列：（一）基本定义定义2：设a是周期为p的二元序列，则称函数piaaaiipC1)1(1)(为周期序列a的自相关函数。其指数位表示在一个周期内对应位相同的位数与对应位不同的位数模二加。0()1R0当时，当时，称为异自相关函数()R（二）一般伪随机序列的特性1、在序列的一个周期内，0、1的个数相差最多一个。2、在序列的一个周期内，长为1的游程占游程总数的，长为2的游程占游程总数的，长为i的游程占游程总数的，且在等长的游程中0的游程个数和1的游程个数相等。1221212i3、异自相关函数是一个常数。1）说明：序列中0、1出现的概率基本相同2）说明：0、1在序列中每一位置上出现的概率相同；3）说明通过对序列与其平移后的序列作比较，不能给出其它任何信息。r级m序列的一个周期中，1出现个，0出现个。12r121r性质1：“0、1”信号频次本原多项式1)(4xxxf序列的一个周期：011110101100100（三）m序列的特性性质2：在r级m序列的一个周期中，没有大于r的游程（1）长度为r的1游程有1个；（2）长度为r-1的0游程有1个；（3）长度为的0、1游程各有个；（4）游程总数为个，且0、1游程各占一半。)21(rkkkr2212r长度为1的1游程数：32r长度为1的0游程数：32r长度为1的游程总数：22r占游程总数的1/2同理长度为2的游程占游程总数的1/4长度为k的游程占游程总数的1/2k例如对4级m序列一个周期中长度为4的1游程，1个；长度为4的0游程，0个；长度为3的1游程，0个；长度为3的0游程，1个；长度为2的0、1游程各有1个；长度为1的0、1游程各有2个。11101011001000111101011001000111010110010001…本原多项式1)(4xxxf二元域上的r级m序列的自相关函数满足：2201,21;1()(1)211/(21),.riiraaarriC若是的倍数其它性质3：自相关特性2.4非线性序列密钥流生成器可分解为驱动子系统和非线性组合子系统。驱动子系统常用一个或多个线性反馈移位寄存器来实现。非线性组合子系统用非线性组合函数F来实现。1、Geffe序列生成器LFSR2作为控制生成器使用。当LFSR2输出1时，LFSR2与LFSR1相连接；当LFSR2输出0时，LFSR2与LFSR3相连接。设LFSRi的输出序列为{a(i)k}(i=1,2,3)，则输出序列{bk}可以表示为123212323kkkkkkkkkkbaaaaaaaaa多路复合器表示的Geffe序列生成器设LFSRi的特征多项式分别为ni次本原多项式，且ni两两互素，则Geffe序列的周期为3121ini2、J-K触发器JLFSR2LFSR1kckbJKRkakcK它的两个输入端分别用J和K表示，其输出ck不仅依赖于输入，还依赖于前一个输出位ck-1，即1211kkcxxcx3、Pless生成器由多个J—K触发器序列驱动的多路复合序列方案4、钟控序列生成器钟控序列最基本的模型是用一个LFSR控制另外一个LFSR的移位时钟脉冲。假设LFSR1和LFSR2分别输出序列{ak}和{bk}，其周期分别为p1和p2。当LFSR1输出1时，移位时钟脉冲通过与门使LFSR2进行一次移位，从而生成下一位。当LFSR1输出0时，移位时钟脉冲无法通过与门影响LFSR2。因此LFSR2重复输出前一位。设计一个性能良好的序列密码是一项十分困难的任务。最基本的设计原则是“密钥流生成器的不可预测性”，它可分解为下述基本原则：①长周期。②高线性复杂度。③统计性能良好。④足够的“混乱”。⑤足够的“扩散”。⑥抵抗不同形式的攻击