《序列密码体制》PPT课件.ppt

《《序列密码体制》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《序列密码体制》PPT课件.ppt（52页珍藏版）》请在三一办公上搜索。

1、应 用 密 码 学,张仕斌 万武南 张金全 孙宣东编著,西安电子科技大学出版社,二00九年十二月,第4章 序列密码体制,知识点：,密码学中的随机数 序列密码的概念 线性反馈移位寄存器 非线性序列简介 常用序列密码 序列密码的应用,4.1 密码学中的随机数,在密码学都要涉及到随机数？因为许多密码系统的安全性都依赖于随机数的生成，例如DES加密算法中的密钥，RSA加密和数字签名中的素数。,4.1.1 随机数的使用,序列密码的保密性完全取决于密钥的随机性。如果密钥是真正的随机数，则这种体制在理论上就是不可破译的。但这种方式所需的密钥量大得惊人，在实际中是不可行的。目前一般采用伪随机序列来代替随机序列

2、作为密钥序列，也就是序列存在着一定的循环周期。这样序列周期的长短就成为保密性的关键。如果周期足够长，就会有比较好的保密性。现在周期小于1010的序列很少被采用，周期长达1050的序列也并不少见。,何谓伪随机数生成器（PRNG）？假定需要生成介于1和 10 之间的随机数，每一个数出现的几率都是一样的。理想情况下，应生成0到1之间的一个值，不考虑以前值，这个范围中的每一个值出现的几率都是一样的，然后再将该值乘以 10。,由任何伪随机数生成器返回的数目会受到 0 到 N 之间整数数目的限制。因为常见情况下，伪随机数生成器生成 0 到 N 之间的一个整数，返回的整数再除以 N。可以得出的数字总是处于

3、0 和 1 之间。对生成器随后的调用采用第一次运行产生的整数，并将它传给一个函数，以生成 0 到 N 之间的一个新整数，然后再将新整数除以 N 返回。,4.1.2 伪随机数产生器,目前，常见随机数发生器中N 是2321（大约等于 40 亿），对于 32 位数字来说，这是最大的值。但在密码学领域，40 亿个数根本不算大！,伪随机数生成器将作为“种子”的数当作初始整数传给函数。由伪随机数生成器返回的每一个值完全由它返回的前一个值所决定。因此，最初的种子决定了这个随机数序列。如果知道用于计算任何一个值的那个整数，那么就可以算出从这个生成器返回的下一个值。伪随机数生成器是一个生成完全可预料的数列（称为

4、流）的确定性程序。一个编写得很好的的PRNG可以创建一个序列，而这个序列的属性与许多真正随机数的序列的属性是一样的。例如：（1）PRNG可以以相同几率在一个范围内生成任何数字；（2）PRNG 可以生成带任何统计分布的流；（3）由PRNG生成的数字流不具备可辨别的模。,4.1.3 基于密码算法的随机数产生器,1使用软件方法的随机数产生器,一个常用的随机数产生器是属于线形拟合生成器一类的。这类生成器相当普遍，它们采用很具体的数学公式：Xn+1=(aXn+b)mod c即第 n+1 个数等于第 n 个数乘以某个常数 a，再加上常数 b。如果结果大于或等于某个常数 c，那么通过除以 c，并取它的余数来

5、将这个值限制在一定范围内。注意：a、b 和 c 通常是质数。,2使用硬件方法的随机数产生器,目前生成随机数的几种硬件设备都是用于商业用途。得到广泛使用的设备是 ComScire QNG，它是使用并行端口连接到 PC 的外部设备，它可以在每秒钟生成 20,000 位，这对于大多数注重安全性的应用程序来说已经足够了。另外Intel 公司宣布他们将开始在其芯片组中添加基于热能的硬件随机数发生器，而且基本上不会增加客户的成本。迄今为止，已经交付了一些带有硬件 PRNG 的 CPU。,4.1.4 伪随机数的评价标准,（1）看起来是随机的，表明它可以通过所有随机性统计检验。现在的许多统计测试。它们采用了各

6、种形式，但共同思路是它们全都以统计方式检查来自发生器的数据流，尝试发现数据是否是随机的。确保数据流随机性的最广为人知的测试套件就是 George Marsaglia 的 DIEHARD 软件包（请参阅）。另一个适合此类测试的合理软件包是 pLab（请参阅）。（2）它是不可预测的。即使给出产生序列的算法或硬件和所有以前产生的比特流的全部知识，也不可能通过计算来预测下一个随机比特应是什么。（3）它不能可靠地重复产生。如果用完全同样的输入对序列产生器操作两次将得到两个不相关的随机序列。,4.2 序列密码的概念及模型,序列密码算法将明文逐位转换成密文，如下图所示。m,密钥流发生器（也称为滚动密钥发生器

7、）输出一系列比特流：K1，K2，K3，Ki。密钥流（也称为滚动密钥）跟明文比特流，m1，m2，m3，mi，进行异或运算产生密文比特流。加密：C i=miK i 在解密端，密文流与完全相同的密钥流异或运算恢复出明文流。解密：m i=C iK i 显然，miK iK i=m i,事实上，序列密码算法其安全性依赖于简单的异或运算和一次一密乱码本。密钥流发生器生成的看似随机的密钥流实际上是确定的，在解密的时候能很好的将其再现。密钥流发生器输出的密钥越接近随机，对密码分析者来说就越困难。,如果密钥流发生器每次都生成同样的密钥流的话，对攻击来说，破译该算法就容易了。,假的Alice得到一份密文和相应的明文

8、，她就可以将两者异或恢复出密钥流。或者，如果她有两个用同一个密钥流加密的密文，她就可以让两者异或得到两个明文互相异或而成的消息。这是很容易破译的，接着她就可以用明文跟密文异或得出密钥流。现在，无论她再拦截到什么密文消息，她都可以用她所拥有的密钥流进行解密。另外，她还可以解密，并阅读以前截获到的消息。一旦Alice得到一明文/密文对，她就可以读懂任何东西了。,这就是为什么所有序列密码也有密钥的原因。密钥流发生器的输出是密钥的函数。这样，Alice有一个明文/密文对，但她只能读到用特定密钥加密的消息。更换密钥，攻击者就不得不重新分析。,流密码是将明文划分成字符(如单个字母)，或其编码的基本单元(如

9、0,1数字)，字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现。流密码强度完全依赖于密钥序列的随机性(Randomness)和不可预测性(Unpredictability)。核心问题是密钥流生成器的设计。保持收发两端密钥流的精确同步是实现可靠解密的关键技术。,流密码的分类:,1.自同步序列密码,自同步序列密码就是密钥流的每一位是前面固定数量密文位的函数，下图和下页图描述了其工作原理。其中，内部状态是前面n比特密文的函数。该算法的密码复杂性在于输出函数，它收到内部状态后生成密钥序列位。,自同步流密码SSSC(Self-Synchronous Stream Cipher)内部状态i

10、依赖于(kI,i-1,mi)，使密文ci不仅与当前输入mi有关，而且由于ki对i的关系而与以前的输入m1,m2,mi-1有关。一般在有限的n级存储下将与mi-1,mi-n有关。,2同步序列密码,同步流密码SSC(Synchronous Stream Cipher)：内部状态i与明文消息无关，密钥流将独立于明文。特点：对于明文而言，这类加密变换是无记忆的。但它是时变的。只有保持两端精确同步才能正常工作。对主动攻击时异常敏感而有利于检测无差错传播(Error Propagation),同步序列密码同样可防止密文中的插入和删除，因为它们会使系统失去同步而立即被发现。然而，却不能避免单个位被窜改。,优

11、点：具有自同步能力，强化了其抗统计分析的能力缺点：有n位长的差错传播。,密钥流序列的性质,密码设计者的最大愿望是设计出一个滚动密钥生成器，使得密钥经其扩展成的密钥流序列具有如下性质：极大的周期良好的统计特性抗线性分析抗统计分析。,实际上,序列密码不可能做到“一次一密”但若密钥流生成器生成的密钥周期足够长，且随机性好，其安全强度可以得到保证！因此，序列密码的设计核心在于密钥流生成器的设计，序列密码的安全强度取决于密钥流生成器生成的密钥周期、复杂度、随机（伪随机）特性等。,4.3 线性反馈移位寄存器,产生密钥序列的最重要部件是线性反馈移位寄存器(LFSR),是因为:(1)LFSR非常适合于硬件实现

12、;(2)能产生大的周期序列;(3)能产生较好统计特性的序列;(4)其结构能应用代数方法进行很好的分析.,移位寄存器是流密码产生密钥流的一个主要组成部分。GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,an)组成，如下页图所示。,每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维向量，共有2n种可能的状态。每一时刻的状态可用n长序列“a1,a2,an”n维向量“(a1,a2,an)”来表示，其中ai是第i级存储器的内容。初始状态由用户确定，当第i个移位时钟脉冲到来时，每一级存储器ai都将其内容向

13、下一级ai-1传递，并计算f(a1,a2,an)作为下一时刻的an。,反馈函数f(a1,a2,an)是n元布尔函数，即n个变元a1,a2,an 可以独立地取0和1两个可能的值，函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后的函数值也为0或1。,例：下图是一个3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由下表求出。,即输出序列为，周期为4。,如果f(a1,a2,an)是(a1,a2,an)的线性函数，则称之为线性反馈移位寄存器LFSR（linear feedback shift register），否则称为非线性移位寄存器。此时f可写为：f(a1,a2,an)=

14、cna1 cn-1a2 c1an 其中常数ci=0或1，是模2加法。ci=0或1可用开关的断开和闭合来实现，如下图所示，这样的线性函数共有2n个。,输出序列at满足：an+t=cnatcn-1at+1c1an+t-1 其中，t为非负正整数。线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。,例：下图是一个5级线性反馈移位寄存器，其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出输出序列为，周期为31。,在线性反馈移位寄存器中总是假定c1,c2,cn中至少有一个不为0，否则f(a1,a2,an)0，这样的话，在n个脉

15、冲后状态必然是000，且这个状态必将一直持续下去。若只有一个系数不为0，设仅有cj不为0，实际上是一种延迟装置。一般对于n级线性反馈移位寄存器，总是假定cn=1。n级线性反馈移位寄存器的状态周期小于等于2n-1。输出序列的周期与状态周期相等，也小于等于2n-1。只要选择合适的反馈函数便可使序列的周期达到最大值2n-1。定义1：n级线性反馈移位寄存器产生的序列ai的周期达到最大值2n-1时，称ai为n级m序列。,根据密码学需要，对于线性移位寄存器需考虑以下问题：（1）如何利用级数尽可能小的线性移位寄存器产生周期长、统计性能好的序列；（2）已知一个序列ai，如何构造一个尽可能短的线性移位寄存器来产

16、生它。因为n级线性移位寄存器的输出序列ai满足递推关系：an+k=c1an+k-1c2a n+k-2cnak，对任何k1成立。这种递推关系可用一个一元高次多项式 p(x)=1+c1x+cn-1xn-1cnxn 表示，称这个多项式为LFSR的特征多项式。由于aiGF(2)(i=1,2,n)，所以共有2n组初始状态，即有2n个递推序列，其中非恒零的有2n-1个，记2n-1个非零序列的全体为G(p(x)。,定义2：给定序列ai，幂级数，称为该序列的生成函数。,定义3：设p(x)是GF(2)上的多项式，使p(x)|(xp-1)的最小p称为p(x)的周期或阶。,定理1：设p(x)=1+c1x+cn-1x

17、n-1cnxn是GF(2)上的多项式，G(p(x)中任一序列ai的生成函数A(x)满足：A(x)=(x)/p(x)，其中=(a1+a2x+anxn-1)+c1x(a1+a2x+an1xn-2)+c2x(a1+a2x+an2xn-3)+cn-1xn-1a1。定理1说明了n级线性移位寄存器的特征多项式和它的生成函数之间的关系。,定理2：若序列ai的特征多项式p(x)定义在GF(2)上，p是p(x)的周期，则ai的周期r|p。n级LFSR输出序列的周期r不依赖于初始条件，而依赖于特征多项式p(x)。我们感兴趣的是LFSR遍历2n-1个非零状态，这时序列的周期达到最大2n-1，这种序列就是m序列。,例

18、3：设f(x)=x4+x3+x2+x+1是GF(2)上的不可约多项式，但是它的输出序列是，周期是5，不是m序列。解：f(x)的不可约性由多项式x，x+1，x2+x+1不能整除f(x)而得。对于k5，输出序列用ak=ak-1a k-2a k-3ak4 检验即可。,定义4：仅能被非零常数或者本身的常数倍除尽，不能被其他多项式整除的多项式称为不可约多项式。,特征多项式满足什么条件时，LFSR的输出序列为m序列。,定理3：n级LFSR产生的序列有最大周期2n-1的必要条件是其特征多项式为不可约多项式。该定理的逆不成立，即LFSR产生的特征多项式为不可约多项式，但其输出序列不一定是m序列。,定义5：若n

19、次不可约多项式p(x)的阶为2n-1，称其为n次本原多项式。定理4：ai为n级m序列的充要条件是其特征多项式p(x)为n次本原多项式。,例4：设p(x)=x4+x+1,是4次本原多项式，以其为特征多项式的线性移位寄存器的输出是周期是24-1=15的m序列。解：p(x)|(x15-1),但是不存在l15，使得p(x)|(xl-1)，所以p(x)阶是15。p(x)的不可约性由x，x+1，x2+x+1不能整除p(x)而得，因此p(x)是本原多项式。对于k5，输出序列用ak=ak-1ak4 检验即可。虽然n级线性移位寄存器产生的m序列具有良好的伪随机性，但是直接用其构造密钥流序列是极不安全的。因为利用

20、2n个输出位可以找到它的起始状态和特征多项式。,若特征多项式p(x)=x3+x+1，初始状态为（101）的移位寄存器产生序列为(101001)。设明文为（011010），那么密文为（110011）。破译者计算mc得到密钥系列(101001)，那么可以得到下列矩阵方程式：得到c31，c20，c11，从而得到特征多项式：p(x)=x3+x+1,4.4 非线性序列简介,线性移位寄存器序列密码在已知明文攻击下是可破译的这一事实促使人们向非线性领域探索。目前研究的比较充分的由非线性移位寄存器，对线性移位寄存器进行非线性组合等。为了使密钥流生成器输出的二元序列尽可能复杂，应保证其周期尽可能大、线性复杂度和

21、不可预测性尽可能高，因此常使用多个LFSR来构造二元序列，称每个LFSR的输出序列为驱动序列，显然密钥流生成器输出序列的周期不大于各驱动序列周期的乘积，因此，提高输出序列的线性复杂度应从极大化其周期开始。,1Geffe序列生成器,Geffe序列生成器由3个LFSR组成（如下图），其中LFSR2作为控制生成器使用。,当LFSR2输出1时，LFSR2与LFSR1相连接；当LFSR2输出0时，LFSR2与LFSR3相连接。若设LFSRi的输出序列为a(i)k(i=1,2,3)，则输出序列bk可以表示为：,设LFSRi的特征多项式分别为ni次本原多项式，且ni两两互素，则Geffe序列的周期为，线性复

22、杂度为。,2J-K触发器,其中，x1和x2分别是J和K端的输入。,J-K触发器如下图所示，它的两个输入端分别用J和K表示，其输出ck不仅依赖于输入，还依赖于前一个输出位ck-1，即,在下图中，令驱动序列ak和bk分别为m级和n级m序列，则有,利用J-K触发器的非线性序列生成器,如果令c-1=0，则输出序列的最初3项为：,当m与n互素且a0+b0=1时，序列ck的周期为(2m-1)(2n-1)。,3Pless生成器,Pless生成器由8个LFSR、4个J-K触发器和1个循环计数器构成，由循环计数器进行选通控制，如下图所示。假定在时刻t输出第t(mod 4)个单元，则输出序列为：a0 b1 c2

23、d3 a4 b5 d6,4钟控发生器,钟控发生器是由控制序列（由一个或多个移位寄存器来控制生成）的当前值决定被采样的序列寄存器移动次数（即由控制序列的当前值确定采样序列寄存器的时钟脉冲数目）。控制序列和被采样序列可以是源于同一个LFSR（称为自控），也可以源于不同的LFSR（称为他控），还可以相互控制（称为互控）。钟控发生器示意图如下图所示。,当控制序列当前值为1时，被采样序列生成器被时钟驱动k次后输出；当控制序列当前值为0时，被采样序列生成器被时钟驱动d次后输出。另外，停走式发生器也是一种钟控模型，它由2个LFSR组成。其中，LFSR-1控制LFSR-2的时钟输入。当且仅当LFSR-1的时间

24、t-1的输出为1时，LFSR-2在时间t改变状态（也即LFSR-1输出时钟脉冲，使LFSR-2进行输出并反馈以改变移位寄存器的状态）。,5收缩和自收缩发生器,收缩发生器是又控制序列的当前值决定被采样序列移位寄存器是否输出。该发生器由2个LFSR组成。LFSR-1、LFSR-2分别按各自时钟运行，LFSR-1在时间t-1时刻的输出为1时，LFSR-2在时间t时刻输出为密钥流，否则舍去。自收缩发生器从一个LFSR抽出2条序列，其中一条为控制序列，另一条为百采样序列。当控制序列输出为1时，采样序列输出为密钥流，否则舍去。此外，还有多路复合序列，这类序列也归结为非线性组合序列。,基于LFSR的序列密码

25、非常适合于硬件实现，但是不特别适合软件实现。这导致出现了一些关于序列密码被计划用于快速软件实现的新建议，因为这些建议大部分具有专利，因此这里不讨论它们的技术细节。比较常用的序列密码是A5、SEAL和RC4序列密码算法，A5是典型的基于LFSR的序列密码算法，SEAL和RC4不是基于LFSR的序列密码算法，而是基于分组密码的输出反馈模式（OFB）和密码反馈模式（CFB）来实现的。其他不基于LFSR的序列密码生成器的安全性基于数论问题的难解性，这些生成器比基于LFSR的生成器要慢很多。,4.5 常用的序列密码算法,A5序列密码算法是利用欧洲数字蜂窝移动电话（GSM）加密的序列密码算法，它用于从用户

26、手机至基站的连接加密，GSM会话每帧数据包含228比特，A5算法每次会话将产生228比特的密钥，算法的密钥长度为64比特，还包含有一个22比特的帧数。A5算法有两个版本：强A5/1和弱A5/2。A5算法是一种典型的基于LFSR的序列密码算法，它由三个LFSR组成，是一种集控制与停走于一体的钟控模型，但是A5算法没有完全公开，因而各种资料的描述也不尽相同，重要是第二个和第三个LFSR的联接多项式以及钟控的位置。A5算法的3个LFSR中LFSR-1、LFSR-2、LFSR-3的级数分别为19、22和23。LFSR-1的反馈抽头是18、17、16、13，LFSR-2的反馈抽头是21、20、16、12

27、，LFSR-3的反馈抽头是22、21、18、17（如下页图的数字表示抽头的位置）。,4.5.1 A5序列密码算法,4.5.2 SEAL序列密码算法,4.5.3 RC4序列密码体制,RC4是Ron Rivest 1987年为RSA设计，是一个可变密钥长度、面向字节操作的序列密码 基本思想：对于n位长的字，它总共N=2n个可能的内部置换状 态矢量S，这些状态是保密的，密钥流K由S中N个元素按照一定方式选出一个元素而生成。每生成一个K值，S中的元素就被重新置换一次密钥调度算法（KSA）伪随机数生成算法（PRGA）,密钥调度算法KSA,KSA算法描述如下：For i=0 to N-1 doSi=i;j

28、=0;For i=0 to N-1 doJ=(j+Si+KI mod L)mod N;Swap(Si,Sj),伪随机数生成算法PRGA,i=0；J=0；While(true）i=（i+1）mod N；J=（j+Si)mod N;Swap(Si,Sj);T=(Si+Sj)mod N;Output k=St;,实例,RC4目前使用在：（1）SSL（安全套接字）中广泛使用（2）WEP(Wired Equivalent Privacy:有线对等保密)IEEE 802.11(http:/,习 题,13级线性反馈移位寄存器在c3=1时可有4种线性反馈函数，设其初始状态为(a1,a2,a3)=(1,0,1)，求各线性反馈函数的输出序列及周期。2设n级线性反馈移位寄存器的特征多项式为p(x)，初始状态为(a1,a2,an-1,an)=(0001)，证明输出序列的周期等于p(x)的阶。3设n=4,初始状态为(a1,a2,a3,a4)=(1,1,0,1)，求此非线性反馈移位寄存器的输出序列及周期。4已知流密码的密文串1010110110和相应的明文串0100010001，而且还已知密钥流是使用3级线性反馈移位寄存器产生的，试破译该密码系统。,